博弈论_纳什均衡湖南科技大学商学院2009-2010学年秋季学期李宾完全信息静态博弈非合作博弈与合作博弈个人理性vs 团体理性完全信息博弈每个局中人的策略集和支付函数都是共同知识静态博弈每个局中人同时独立地采取自己的策略，且只进行一次。石头、剪刀、布先讨论完全信息静态博弈最为简单的博弈类型；博弈研究的基础1智猪博弈环境：猪圈的一边有一个食槽，另一边有一个小猪食料输送按钮。按下按钮、再走到食槽按等待边，要耗费2个单位。食物进料8个单位。(2. 4)大猪先到，可吃7个单位按(3, 1)大小猪先到，可吃4个单位猪两猪同时到，大猪吃5个等待(7, -1)(0, 0)单位，小猪吃3个单位。夫妻爱好问题一对夫妻协商业余活动有两个选择妻子看足球比赛看芭蕾演出看足球看芭蕾更偏好在一起。若分开，各自的收益均为-1看足球(2, 1)(-1, -1)两人将分别采取什么策略？各自的收益是多丈少？夫看芭蕾(-1, -1)(1, 2)2猜钱币游戏一枚硬币，正面朝上还是反面朝上盖硬币的人一人盖住，让另一人猜若猜对，则猜的人+1正面反面分，盖的人-1分若猜错，则猜的人-1猜分，盖的人+1分。硬正面(1, -1)(-1, 1)两人分别采取什么样的币策略？各自的收益是多的反面(-1, 1)(1, -1)少？人符号表述这些例子都属于完全信息下的静态博弈三个基本要素都是共同知识每个局中人都是在明确这三个基本要素的前提下，选择自己的行动策略，以谋求自己收益的最大化局中人集合：N = {1, 2, ···, n}策略集：Si= {si} = {s1(i), s2(i), ···, sm(i)}, i∈N策略组合：s = (s1, s2, ···, sn), si∈Si, i ∈N支付函数：Pi(s)是策略组合s的函数。最大化Pi在G = [N, {Si}, {Pi}]中研究局中人对策略的选择3占优的定义在博弈G = [N, {Si}, {Pi}]中，若sk(i)和sh(i), 是局中人i的两个策略，对任意的策略组合s，都有：Pi(sk(i),s-i) > Pi(sh(i),s-i)，s-i ∈S-i则称局中人的策略sk(i)严格占优策略ssh(i)，或者称策略sh(i) 相对于k(i)是严格劣策略。s-i= (s1, s2, ···, si-1, si+1, ···, sn)当某个局中人的一个策略占优于另一个策略时，其它局中人的策略选择没有影响力。若＞号变为≥号，则成为弱占优，或弱劣策略占优均衡的定义对于局中人i，若存在一个策略s），都有k(i) ，使得该局中人的任何其它策略sPh(i)（h≠ki(sk(i),s-i) ＞Pi(sh(i),s-i)，s-i ∈S(i) 为局中人i的占优策略。-i，则称策略sk在博弈G = [N, {S人i都存在一个占优策略i}, {Pi}]中，如果每一个局中s(s*)称为占优策略均衡i*，则策略组合s* = （1*, sdominant-strategy equilibrium2*, ···, sn），简称为占优均衡。对应的支付称为占优均衡结果。4占优均衡的例子：囚徒困境嫌疑犯B承认不承认承认（-8，-8）（0，-10）嫌疑犯A不承认（-10，0）（-1，-1）重复剔除占优均衡重复剔出严格劣策略过程由于局中人不会选择自己策略集Si中的严格劣策略，所以如果存在这样的严格劣策略，那么可把它从策略集中删除掉，形成的新的策略集Si’，进而形成新的博弈G’。在博弈G’中，任何局中人对策略的选择，将与G中的策略选择相同。这一过程可以一直进行下去重复剔出严格劣策略可使得博弈中局中人的策略集变小，使得博弈分析变得简单。特别地，若经过重复剔出，所有局中人只剩下一个策略5重复剔除占优均衡那么，由所有局中人仅剩的策略所组成的策略组合，称为博弈G的重复剔除占优均衡。对应的支付结果，称为重复剔除占优均衡结果。例子：智猪博弈占优均衡一定是重复剔除占优均衡，但反过来不一定成立。例子：囚徒困境与智猪博弈在实际问题中总是希望可以重复剔出严格劣策略，但并不总是有效。例：夫妻爱好、猜钱币重复剔出严格劣策略的例子局中人2左中右上(4, 3)(5, 1)(6, 2)局中人1中(2, 1)(8, 4)(3, 6)下(3, 0)(9, 6)(2, 8)6不是重复剔除占优均衡的例子局中人2左中右上(4, 3)(5, 1)(6, 2)局中人1中(2, 1)(8, 4)(3, 6)下(5, 0)(9, 6)(2, 8)纯策略纳什均衡对于有些博弈问题，可以使用重复删除的严格劣策略的方法，得到重复剔除的占优均衡，从而回答了局中人关于策略选择的问题。但在很多博弈中，这一方法并不适用。例如夫妻爱好问题。更一般的解，需要用到纳什均衡。定义：纯策略纳什均衡点；Pi(s*)为均衡结果当局中人选定的策略组成纳什均衡后，形成一个平衡局面。任何一方单方面地改变自己的策略，只可能使自己的收益下降（或不变），而不会增加。7对纳什均衡的理解纳什均衡是所有参与人最优策略的组合：给定该策略中别人的选择，没有人有积极性改变自己的选择假设博弈中的所有参与人事先达成一项协议，规定出每个人的行为规则，那么，在没有外在强制力的约束时，参与方是否会自觉地遵守这个协议，或者说这个协议是否是自动实施的（self-enforcing）？给定别人遵守协议，没有人有积极性偏离协议。如果一个协议不构成纳什均衡，它不可能自动实施，因为至少有一个参与方会违背这个协议；不满足纳什均衡要求的协议是没有意义的。双矩阵博弈的划线法双矩阵博弈的定义支付函数aij、bij，（A，B）双矩阵博弈的表示方式在双矩阵博弈中，寻求纯策略纳什均衡的方法——划线法给定局中人1的策略为i，局中人2根据bij选择，划线给定局中人2的策略为j，局中人1根据aij选择，划线两个元素下面都有划线的，即为纯策略纳什均衡点定理2.2.2；例2.2.1，例2.1.2，例2.1.38用划线法求解智猪博弈环境：猪圈的一边有一个食槽，另一边有一个小猪食料输送按钮。按下按钮、再走到食槽边，要耗费2个单位。按等待食物进料8个单位。大猪先到，可吃7个单位按(3, 1)(2. 4)小猪先到，可吃4个单位大两猪同时到，大猪吃5个猪单位，小猪吃3个单位。等待(7, -1)(0, 0)用划线法求解夫妻爱好问题一对夫妻协商业余活动有两个选择妻子看足球比赛看芭蕾演出看足球看芭蕾更偏好在一起。若分开，各自的收益均为-1看足球(2, 1)(-1, -1)两人将分别采取什么策略？各自的收益是多丈少？夫看芭蕾(-1, -1)(1, 2)9用划线法求解猜钱币游戏一枚硬币，正面朝上还是反面朝上盖硬币的人一人盖住，让另一人猜若猜对，则猜的人+1分，盖的人-1分正面反面若猜错，则猜的人-1分，盖的人+1分。猜硬正面(1, -1)(-1, 1)两人分别采取什么样的币策略？各自的收益是多的少？人反面(-1, 1)(1, -1)用划线法求解双矩阵博弈把一人的某策略局中人B当作s-i，判断另一人的策略选择左中右上(1, 2)(1, 3)(0, 2)局中人A下(0, 4)(0, 2)(2, 0)10求解广告博弈的纳什均衡两个企业生产和销售同一种产品企业2每个企业都有“打广告”和“不打广告”两个选择打广不打广两家都打广告，会导致告告恶性竞争，利润反而比不上不打广告的情形打广若一家打广告、另一家企告(4, 4)(15, 1)不打，则打广告的高业1不打纳什均衡是什么？广告(1, 15)(10, 10)求解工作博弈的纳什均衡两个人合作做事情每个人都有“努力工作”工人2和“偷懒”两个选择两人收益分配结果如右努力图所示；有点类似于智工作偷懒猪博弈纳什均衡是什么？努力此例类似早年的“大锅饭”工工作(6, 6)(0, 8)人1偷懒(8, 0)(2, 2)11用划线法求解纳什均衡（提问）局中人B左中右上(10, 4)(1, 5)(98, 4)局中人A中(9, 9)(0, 3)(99, 8)下(1, 98)(0, 100)(100, 98)用划线法求解纳什均衡（提问）局中人2左中右上(1, 1)(1, 1)(0, 0)局中人1下(0, 0)(1, 2)(1, 2)12多重性与存在性的例子妻子夫妻爱好盖硬币的人问题猜钱币游看足球看芭蕾戏正面反面看足(2, 1)(-1, -1)猜丈球硬正面(1, -1)(-1, 1)夫看芭币蕾(-1, -1)(1, 2)的人反面(-1, 1)(1, -1)纳什均衡点与其它两个概念的区别定理2.2.1：重复剔除的占优均衡与纳什均衡证明：从定义出发，用反证法。适于熟悉定义纳什均衡点与多目标规划问题的区别博弈是参与者之间有相互影响的多人决策问题一个替代的思路：多目标规划问题纳什均衡点和多目标规划问题的求解是不同的概念囚徒困境的策略集、支付函数；收益用图表示B、C、D三点是非劣解，A点为劣解多目标规划有联合行动的意向，而G为个人竞争13弱占优的例子（一）剔出弱劣策略，有可能改变原博弈的一些特性B对A，策略“下”弱占优策略“上”左右对B，策略“右”弱占优策略“左”上（1, 1）（1, 1）但如果删除A的策略“上”，会删除掉潜在的A其它纳什均衡，即改变下（1, 1）（2, 2）了博弈的特性弱占优的例子（二）“2中”弱占优“2左”和“2右”用弱占优去剔除，不同的顺序会导致不同的结果删“2左”，会有（下，中）、（下，右）的纳什均衡删“2右”，会有（上，左）、（上，右）的纳什均衡局中人2左中右局中人上(1, 1)(1, 1)(0, 0)1下(0, 0)(1, 2)(1, 2)14颤抖的手重复剔除的占优均衡对人的理性要求很高局中人2相互知道对方是绝对理性的。每个局中人都对左右对手有充分的信念一个看起来可信的结果，在现实中不一定成局上(8, 10)(-100,9)立。（上，左）→中（下，左）人1下(7, 6)(6, 5)2在选左时手颤抖了一下第一次作业书：《博弈论及其应用》，汪贤裕、肖玉明第14页：第1.1题，第1.2题用策略式表述一个单次的“石头、剪刀、布”游戏。胜者赢1分，负者输1分，平局0分。然后设想一个行动方案，将此策略式博弈表述为一个扩展式博弈。第55页：第2.1题，第2.2题不用抄题目；直接写题号和解答。交作业的时间：9月29日（星期二）15三人博弈问题BBC的策C的策略：甲略：乙左右左右上0, 0, 10-5, -5, 0上-2, -2, 0-5, -5, 0AA下-5, -5, 01, 1, -5下-5, -5, 0-1, -1, 5三人博弈的划线法局中人C的支付结果写在支付向量第3个位置局中人集合N = {A, B, C}策略集集合SA= {上，下}，SB= {左，右}，SC= {甲，乙}策略组合的例子：s = （下，左，乙）提问：P2(s) = ?，P3(s) = ?策略组合的例子：s = （上，右，甲）提问：P1(s) = ?，P3(s) = ?16三人博弈的划线法s-A= （左，甲），（左，乙）给定某个s-A，看A的最优反应是什么？把s-A全部走完，在A的最优支付结果下划线s-B= ?给定某个s-B，看B的最优反应是什么？把s-B全部走完，在B的最优支付结果下划线s-C= ?给定某个s-C，看C的最优反应是什么？把s-C全部走完，在C的最优支付结果下划线无限策略博弈的求解思路回顾两个概念：有限博弈与无穷博弈完全信息静态博弈G的三个要素；s-i的写法差别在于，策略集SSi由无限多的策略组成，比如i= [0, +∞)如何求解无穷策略博弈？思路：寻找每个人的最优反应函数；求解最优反应函数方程组。对谁的反应？自变量：s-i；因变量：si∈Si。划线法是在有限策略集合里寻找最优反应函数17无限策略博弈的求解步骤第一步：写出支付函数Pi(si, s-i)第二步：判断Pi(si, s-i)是否关于si拟凹？定义：拟凹函数；严格拟凹函数对拟凹函数的直观认识；正例与反例通常遇到的是凹函数（二阶导数为负）；是凹函数，就一定严格拟凹。最优反应函数的定义第三步：Pi对si求偏导，相当于求极大值问题第四步：由n维方程组，求纯策略纳什均衡解例：古诺模型两个寡头垄断厂商，厂商1和厂商2，生产同种产品。产量分别是q1和q2，注意它们是变量。边际成本分别为c1和c2，正常数，无固定成本该产品的市场反需求函数：p = a -b(q1+ q2)参数a＞c1＞0，a＞c2＞0，b ＞0市场需求情况和两个厂商的成本都为共同知识两厂商之间不协商；同时作出产量的决策目标：追求利润最大化。问：各自均衡产量？18古诺模型求解第一步该产品的市场反需求函数：p = a -b(q1+ q2)写出两个厂商的利润函数π1(q1 , q2) = pq1-c1q1= [a -b(q1+ q2)] q1–c1q1π2(q1 , q2) = pq2-c2q2= [a -b(q1+ q2)] q2–c2q2古诺模型的求解步骤第一步：写出两个厂商的利润函数第二步：判断利润函数是否关于产量为凹第三步：若为凹，求偏导，让其等于0（MR = MC），获得si对s-i的最优反应函数第四步：联立两个厂商的最优反应函数，求解出均衡产量（q1*，q2*），此即为纳什均衡解将均衡产量代入利润函数，可得纳什均衡结果一个厂商的最优产量不仅仅取决于自己19多目标规划问题前面在有限策略博弈的囚徒困境例子中，看到纳什均衡解是多目标规划问题的劣解这里从无限策略博弈的古诺模型例子，看一看纳什均衡解与多目标规划问题的解之间的差异多目标规划问题的表述：(2.2.18)式问：多目标规划问题的非劣解是怎样的？因利润是由货币来度量的，而货币即便由不同的人持有，它们之间也是完全替代的，所以多目标规划问题可写成一个联合收益最大化问题联合收益最大化问题联合收益最大化问题的表述：(2.2.19)式为简化分析，取c1=c2=c，b=1令Q=q1+q2。求出Q*和π*联合收益问题的解与纳什均衡解的比较在联合收益问题下，总产量更少，利润更高，因为相当于只有一个垄断厂商纳什均衡解仍然不是多目标规划问题的非劣解非合作博弈的特征：竞争环境下的多人决策20例：伯川德模型在现实中，更多看到的是厂商之间进行价格竞争，而不是产量竞争。以价格为决策变量的模型，是伯川德模型（Bertrand model）两个寡头厂商生产同一类型产品厂商1和厂商2分别选择价格p1和p2；pi≥0消费者对厂商i的产品的需求函数是：q1(p1,p2) = a –p1+ bp2，0＜b ＜1q2(p1,p2) = a –p2+ bp1。两个厂商的产品是相互替代关系，但不是完全替代伯川德模型及其求解两个厂商都无固定成本，边际成本为c0＜c ＜a两个企业同时对价格进行选择问：均衡的价格组合是怎样的？先写出该博弈的三个构成要素：N、Si、Pi(s)判断利润函数是否为凹函数求偏导，得出最优反应函数联立两个厂商的最优反应函数，求出纳什均衡21例子：公地的悲剧某个牧民村里有n户牧民；假设他们情况相同有一片公共的草地，每年所有的牧民都会在这片草地上放牧养羊用qi表示第i户牧民养羊的头数。q1，q2，···qn羊的总放牧数量是：G=q1+q2+···+qn养一只羊的成本是常数c羊的卖价是v(G) ＞0。羊群数量越少，每只羊能吃到的草就越多，羊就卖得起价，v’(G) ＜0公地的悲剧羊群总数目的上升，一则供给增加，二则羊吃草不那么丰盛，两者使得卖羊的价格加速下降，即：v’’(G) ＜0。图示大概的形状每年春天，n个牧民同时分别选择羊的放牧数量。假设对放牧数量q割的。问：每户牧民的均衡放牧数量是多少？i的选择是连续的、可分先写出该博弈的三个构成要素：N、Si、Pi(s)22公地的悲剧求解步骤牧民i放牧qi只羊的净收益是：πi(qi , q-i) = pqi–cqi= [v(G)-c] qi= [v(q1+···+qi+···+qn)-c] qi判断利润函数是否关于qi为凹函数让一阶偏导等于0，得出隐式的最优反应函数v(G)-c+v’(G)qi= 0联立所有人的最优反应函数；考虑对称解加总数量G*的方程：(2.2.29)式纳什均衡解与社会计划解社会计划者问题Max π=Gv(G)-cG一阶条件与二阶条件：v’(G)G+v(G)-c=0判断纳什均衡解与社会计划解的大小放在一个方程中构造一个函数：f(G) = v(G) + Gv’(G)由函数值的相对大小和一阶导数，判断两个解大小分散均衡下的羊群放牧总数超过社会最优水平，源于每人只考虑自己的利益，造成公共草地被滥用23例子：豪泰林模型在古诺模型里，产品是同质的。但在现实当中，不同企业生产的产品总存在一些差异，不会完全同质，或者说不会完全替代豪泰林模型考虑产品销售在空间上的差异假定有一个长度为1的线性城市，消费者均匀地分布在[0, 1] 区间内，其分布函数的密度为1假设有两个商店分别处于城市两端，商店1位于x=0处，商店2位于x=1处。它们出售性能相同的产品每个商店的单位产品成本相同，均为常数c＞0豪泰林模型的描述消费者购买该产品存在旅行成本；旅行成本与消费者离商店的距离成正比，单位距离成本为常数t＞0消费者可以选择去哪家商店；若在坐标x处，去商店1的旅行成本是tx，去商店2的旅行成本是t(1-x)假定每个消费者都要消费1个单位的该产品问：两个商店的均衡价格是多少？一个商店虽然可以自主选择价格，但是要考虑到竞争对手的反应和竞争对手的价格对自己的影响网上购买与实体店购买；邮费vs. 公交费；一个kingston的2G U盘，网上卖48元，实体店卖60元24豪泰林模型的求解写出构成要素集，尤其是利润函数为此，需要先判断哪些消费者会去商店1，哪些会去商店2；即：找出对去两家商店无差异的消费者坐标，(2.2.38)式求积分，算出两商店所面对的需求函数写出利润函数，算其一阶导数和二阶导数判断利润函数是否为凹函数解出均衡价格组合和各自的均衡利润旅行成本越高，产品差异越大，均衡价格越高例：标准伯川德模型Bertrand model以价格为决策变量两个寡头厂商生产同一产品，边际成本为c厂商1和厂商2分别选择价格p1和p2；pi≥0标准伯川德模型的设定是：两个产品完全同质需求函数是：q(p) = a –bp，0＜a，0＜b两个企业进行价格战。如果价格相等，则平分市场。这里不能使用求偏导的方法，而要从纳什均衡的概念出发25对厂商1的分析对于厂商1，给定厂商2的价格为p2（即s-1）如果p1＞p2，那么消费者都会去买厂商2的产品，自己的销量为0，利润为0如果p1=p2，那么模型设定两个厂商平分市场，即：q1 = (a-bp)/2，利润是π1 = (p-c)(a-bp)/2如果p1＜p2，那么消费者都会购买厂商1的产品，自己的销量是整个市场的需求量，即：q1 = a-bp1，利润是π1 = (p1-c)(a-bp1)厂商1的最优反应是：p1比p2稍微低一点点，利润将比p1= p2时要高对厂商2的分析对于厂商2，给定厂商1的价格为p1（即s-2）如果p2＞p1，那么消费者都会去买厂商1的产品，自己的销量为0，利润为0如果p= (a-bp)/22=p1，那么模型设定两个厂商平分市场，即：q2 ，利润是π1 = (p-c)(a-bp)/2如果p2＜p1，那么消费者都会购买厂商2的产品，自己的销量是整个市场的需求量，即：q2 = a-bp2，利润是π2 = (p2-c)(a-bp2)厂商2的最优反应是：p2比pp1稍微低一点点，利润将比2= p1时要高26Bertrand均衡命题1：p1=p2＞c，不可能构成纳什均衡。因为此时每一方都有偏离的动机和激励此伯川德模型的纳什均衡解是：p1=p2=cBertrand均衡的涵义在于，如果两个企业经营完全相同的产品，且成本一样，那么价格战必定会使得每个企业都按照p=MC的原则来经营，即便此时的市场供给者并不是无穷多。如果两个企业的边际成本不同，那么从长期看，成本低的企业会把成本高的企业挤出市场。Bertrand悖论Bertrand竞争的均衡结果在现实中往往很难见到。两个厂商即便进行价格战，也通常不会吧价格降低到边际成本的水平。这被称为伯川德悖论（Bertrand paradox）几种解释生产能力限制；航空旅行市场从静态博弈转变到动态博弈，可出现p1=p2＞c 的竞争均衡结果产品差异27过渡：概率论初步至此，已介绍完纯策略纳什均衡纯策略纳什均衡的概念有限策略博弈的求解方法：划线法无限策略博弈的求解方法：最优反应函数下一步需介绍混合策略纳什均衡因混合策略纳什均衡和后面的不完全信息博弈都需要使用概率论的知识，所以先对概率论做一个初步的介绍对几个基本概念的定义“样本空间”的定义由一个特定随机试验所有可能发生的基本结果组成的集合，称为该试验的样本空间，以大写的Ω表示。例子：掷一个麻将骰子，它有六个面，某个面朝上是所期待的一个基本结果。则样本空间是：Ω= {1朝上，2朝上，3朝上，4朝上，5朝上，6朝上}28对几个基本概念的定义“样本点”的定义一个随机试验的每个可能发生的基本结果，称为样本点，用小写的ω表示。例子：ω1= 1朝上，……，ω6= 6朝上“基本事件”的定义由样本空间Ω的一个样本点组成的单点集合，称为基本事件。例子：{1朝上}，……，{6朝上}为基本事件对几个基本概念的定义“随机事件”的定义样本空间Ω的一个子集，称为随机事件例子：假设随机事件A为掷出奇数点，则A = {1朝上，3朝上，5朝上}例子：假设随机事件B为掷出最小的两个点，则B = {1朝上，2朝上}两个特殊的子集样本空间Ω是Ω的一个子集，称为必然事件空集Ǿ为不可能事件29事件间的关系与运算事件A与B的运算概率论中的含义A包含B事件B发生，则事件A一定发生A和B相等………………………，反之亦然A和B的交事件A和事件B同时发生有限个事件的交n个事件A1, …, An同时发生可列个事件的交可列个事件A1…An…同时发生事件间的关系与运算事件A与B的运算概率论中的含义A和B的并事件A和事件B中至少有一个发生有限个事件的并n个事件A1, …, An中至少有一个发生可列个事件的并可列个事件A1…An…中至少有一个发生事件A与B的差事件A发生，而事件B不发生30事件间的关系与运算事件A与B的运算概率论中的含义事件A的逆事件事件A的对立事件发生，当且仅当事（对立事件）件A不发生事件A与B互不相容（互斥）事件A与B不可能同时发生事件A1, …, An是n个事件A1, …, An中，仅发生且必发一个完全事件组生其中之一随机事件的概率古典定义设随机试验E的样本空间Ω仅包含有限个等可能的样本点，则事件A发生的概率为：#A 有利于A的样本点数mP(A) = -----= ---------------------#Ω试验E的样本总点数n31例题一个正六面体相对的两面上涂有相同的颜色，上下两面均涂有红色，前后两面均涂有黄色，左右两面均为蓝色。现在把它分割为27个小立方体，从中任取一块。求取到的小立方体上至少涂有两种不同颜色的概率。随机事件的概率公理化定义设随机试验E的样本空间为Ω，随机事件A包含于Ω，则将P(A)定义为满足下列三个条件的集合函数：(1) P(A)≥0(2) P(Ω)=1(3) 可列可加性，即事件A容，则P(∑A1，…，An…两两互不相i) = ∑P(Ai)32例题已知随机事件A、B、C两两互不相容，而且P(A) = P(B) = P(C) = 0.3计算：P(A+B+C) = ?概率论公理的推论P(Ǿ)=0如果AB= Ǿ，则P(A+B) = P(A) + P(B)如果事件A1, …, An是一个完全事件组，则P(∑Ai) =1如果事件A包含B，则P(A-B) = P(A) –P(B)如果事件A包含B，则P(A)≥P(B)；P(A)≤1广义加法公式：P(A+B) = P(A) + P(B) –P(AB)33条件概率的定义与计算条件概率如果事件A的概率大于零，则在事件A已经发生的条件下，事件B发生的条件概率定义为：P(AB)P(B|A) = -------------P(A)乘法公式与全概率公式乘法公式P(AB) = P(A) x P(B|A)，当P(A)>0= P(B) x P(A|B)，当P(B)>0全概率公式如果事件A1, …, A两两互不相容，其和为Ω，并且n是一个完全事件组，即它们P(Ai)＞0，i=1,2,…,n，则对任一事件B，有：P(B) = ∑P(Ai)P(B|Ai)34贝叶斯公式如果事件A1, …, An是一个完全事件组，并且P(Ai)＞0，i=1,2,…,n，P(B)＞0，则对正整数m（1≤m≤n），有：P(Am)P(B|Am) P(Am)P(B|Am)P(Am|B)= ------------= ----------------P(B) ∑P(Ai)P(B|Ai)例题甲、乙、丙三人通过抽签决定两张同一场次的参观票的归属。三个签上，两个写“有”，一个写“无”。抽签次序是，甲先，乙次，丙最后。从开始抽签之前的角度，计算乙抽到参观票的概率。从开始抽签之前的角度，计算：如果已知乙抽到了参观票，那么甲也抽到参观票的概率35随机变量“随机变量”的定义取值依赖于某个随机试验的结果，并随着试验结果不同而变化的变量，称之为随机变量例：投掷一个骰子，直到首次出现6点为止。那么投掷次数X就是一个随机变量。X = 1, 2, ……，n，……离散型随机变量“离散型随机变量”的定义设X是一个随机变量，如果X只取有限个或可列个值，则称X为离散型随机变量。其相应的概率P{X=xi}=pi，(i=1, 2, …, n)称为X的概率分布或分布律。上例中的投掷次数X即为离散型随机变量36离散型随机变量Xx1x2……xn……pp1p2……pn……pi≥0，i=1, 2, ……∑pi=1解题例：投掷一个骰子，直到首次出现6点为止。那么投掷次数X就是一个随机变量。写出X的分布律。pn= P{X=n} = ?X12……n……p…………37数学期望的定义如果离散型随机变量X的概率分布为P{X=xi=1, 2, …），且级数∑|xi} = pi（i|pi＜+∞，则称EX = ∑xipi为X的数学期望。涵义：随机变量X的平均值例题：投掷次数X的数学期望是多少？或者说，平均需投掷多少次骰子才首次出现6点？博弈论绕不开概率论混合策略纳什均衡需要用到数学期望的概念不完全信息博弈需要用到贝叶斯公式有的例题里会用到连续型随机变量的概念国庆假期里可看看概率论的书，前两章就足够38第一次作业出现的问题对概念的把握尚存在模糊之处具体的问题有这样几种策略式（规范式）与扩展式的转换；对同一个题目，两种表述方式应该等价什么是纳什均衡？第20页顶部；最优策略严格劣策略的判别重复剔除严格劣策略纳什均衡解与均衡结果是不同的概念不能只写答案，应有简要的解答过程第55页第2.2题乙1231(2, 0)(1, 1)(4, 2)甲2(3, 4)(1, 2)(2, 3)3(1, 3)(0, 2)(3, 0)39混合策略纳什均衡在猜钱币游戏的例子里，不存在纯策略纳什均衡，但博弈双方有可能用一种随机的方法来决定它的策略，从而存在一种混合策略纳什均衡什么是混合策略？在看定义之前，先给出一种直观的理解猜钱币游戏。一方可采用扔骰子的方式，来决定自己将采取什么策略，并且这一行为方式及规则是共同知识。骰子可以是2面的（硬币），也可以是6面的（麻将骰子）。由随机装置来选择一个纯策略混合策略盖的人猜的人的混合策略是（x, 1-x）盖的人的混合策略是（y, 1-y）正面反面x∈[0, 1], y∈[0, 1]y1-y正面x（1，-1）（-1，1）猜的人反面1-x（-1，1）（1，-1）40为什么要使用混合策略？如果自己的活动呈现出规律性，容易被对手对症下药。因此，有时候在自己的行为选择上加入随机性，反而有利于自己。孙子：攻而必取者，攻其所不守也；守而必固者，守其所必攻也。故善攻者，敌不知其所守；善守者，敌不知其所攻。微乎微乎，至于无形；神乎神乎，至于无声，故能为敌之司命为什么要使用混合策略？在“石头、剪刀、布”的游戏里，不存在纯策略纳什均衡的涵义是，无论你怎么选择，都不会有最优的纯策略。一个玩法是，准备一个随机序列，按照这个随机序列来选取自己的策略。不过，这个随机序列不能告诉其它人。在美军轰炸与萨达姆躲藏的博弈里，萨达姆对于躲藏地点的选择不能有规律性。坚固的掩体不一定安全。可用掷骰子的方法，来确定自己躲在哪里；让美军无从猜测，才是最佳的。41猜钱币游戏（1）使用6面的骰子；看给定猜的人的混合策略，找盖硬币的人盖的人的最优反应函数情形一：不管6面骰子的正面反面哪一面朝上，都猜“正面”，即以概率组合（1, 0）施加在自己的策略选猜硬正面(1, -1)(-1, 1)择（正面，反面）上币对此，盖的人的最优反的应是概率组合（0, 1）人反面(-1, 1)(1, -1)猜钱币游戏（2）情形二：当1-5朝上时，猜的人猜“正面”，即以盖硬币的人概率组合（5/6, 1/6）施加在自己的策略选择（正面，反面）上正面反面对此，盖的人选正面的猜期望支付是-2/3，选反硬正面(1, -1)(-1, 1)面的是2/3，币max -2/3 y + 2/3 (1-y)的最优选择是y=0；(0, 1)人反面(-1, 1)(1, -1)42猜钱币游戏（3）情形三：当1-4朝上时，猜的人猜“正面”，即以盖硬币的人概率组合（4/6, 2/6）施加在自己的策略选择（正面，反面）上正面反面猜对此，盖的人选正面的硬正面(1, -1)(-1, 1)期望支付是-1/3，选反币面的是1/3，故其最优反的应是概率组合（0, 1）人反面(-1, 1)(1, -1)猜钱币游戏（4）情形四：当1-3朝上时，猜的人猜“正面”，即以盖硬币的人概率组合（3/6, 3/6）施加在自己的策略选择（正面，反面）上正面反面对此，盖的人选正面的猜期望支付是0，选反面的硬正面(1, -1)(-1, 1)是0，在正面、反面之间币无差异，从而盖的人任的意的概率组合都无差异人反面(-1, 1)(1, -1)43猜钱币游戏（5）情形五：当1-2朝上时，猜的人猜“正面”，即以盖硬币的人概率组合（2/6, 4/6）施加在自己的策略选择（正面，反面）上正面反面猜对此，盖的人选正面的硬正面(1, -1)(-1, 1)期望支付是____，选反币面的是____，故其最优的反应是概率组合____人反面(-1, 1)(1, -1)猜钱币游戏（6）情形六：当1朝上时，猜的人猜“正面”，即以概盖硬币的人率组合（1/6, 5/6）施加在自己的策略选择（正面，反面）上正面反面猜对此，盖的人选正面的硬正面(1, -1)(-1, 1)期望支付是____，选反币面的是____，故其最优的反应是概率组合____人反面(-1, 1)(1, -1)44猜钱币游戏（7）情形七：无论哪面朝上，猜的人都猜“反盖硬币的人面”，即以概率组合（0, 1）施加在自己的策略选择（正面，反面）上正面反面猜对此，盖的人选正面的硬正面(1, -1)(-1, 1)期望支付是1，选反面的币是-1，故其最优反应是的概率组合（1, 0）人反面(-1, 1)(1, -1)从设定概率组合到期望支付结果猜的人的概率(1, 0)(5/6, (4/6, (3/6, (2/6, (1/6, (0, 1)组合1/6)2/6)3/6)4/6)5/6)盖的人的概率组合反(0,1)(0,1)(0,1)任意(1, 0)(1, 0)(1, 0)应抽象而言，骰子可以是100面的、10000面的……，相应的随机装置总可以造出来，从而[0, 1]之间的任意概率分布都可以产生出来。故可画出最优反应函数45猜钱币游戏（8）情形八：当1朝上时，盖的人猜“正面”，即以概盖硬币的人率组合（1/6, 5/6）施加在自己的策略选择（正面，反面）上正面反面猜对此，猜的人选正面的硬正面(1, -1)(-1, 1)期望支付是____，选反币面的是____，故其最优的反应是概率组合____人反面(-1, 1)(1, -1)从设定概率组合到期望支付结果盖的人的概率(1, 0)(5/6, (4/6, (3/6, (2/6, (1/6, 组合1/6)2/6)3/6)4/6)5/6)(0, 1)猜的人的概率组合反(1,0)(1,0)(1,0)任意(0, 1)(0, 1)(0, 1)应此例下的纳什均衡是所有局中人最优反应函数的交点混合策略纳什均衡：((1/2, 1/2), (1/2, 1/2))46引出混合策略纳什均衡的概念概率组合的向量（(1/2, 1/2), (1/2, 1/2)）构成一个纳什均衡。此时，猜的人以概率0.5选择正面，以概率0.5选择反面；盖的人也以概率0.5选择正面，以概率0.5选择反面；哪一方都没有激励偏离它与纯策略纳什均衡相区别的是，这一类纳什均衡被称为混合策略纳什均衡。纯策略纳什均衡是仅由0、1组成的概率组合关于混合策略博弈的符号标记混合策略的定义；见书上第32页，xi局中人i的混合策略就是定义在其纯策略集合S上的一个概率分布i混合策略集记为Xi混合策略组合记为x = (x1, x2, ···, xn)纯策略是混合策略的一个特例，相当于在xi中有且仅有一个分量取为了1，其它分量为0混合策略的n人非合作博弈的三个要素：32-3347混合策略纳什均衡的定义混合策略博弈的表示：G = [N, {X表示局中人i在混合策略组合i}, {P用Ex下的期望i}]，并支付i(x)重要的是理解混合策略博弈的概念，它与纯策略之间的区别。虽然它用一个随机装置来选择策略，但概率分布都是共同知识，所以混合策略博弈仍然是完全信息静态博弈。混合策略纳什均衡点的定义：第33页混合策略纳什均衡点的存在性定理2.3.1：x*是G的一个混合策略纳什均衡点的充分必要条件，是什么？推一下证明过程，目的是熟悉那些记号定理2.3.2：每个n人非合作博弈G = [N, {X{Pi}, i}]必有混合策略纳什均衡。需知道证明中的难点是Brouwer不动点定理对这一定理的引出过程超过了这门课的范围一个直观理解：一杯静止状态的水，记录下水分子的位置；摇动等其静止，必有一个水分子在原位置48解题思路（上）书上提供了对于2x2矩阵博弈的解题方法这里提供一种针对双矩阵博弈的更为一般性的方法，并不仅适用于2x2的情形第一步：写出混合策略组合A为x = (x1, x2, ···, xm)，x1+ x2+ ···+ xm=1B为y = (y1, y2, ···, yn)，y1+ y2+ ···+ yn=1第二步：给定A的混合策略是x，计算B在各个纯策略下的期望收益EB(x, sjB)；计算方法是使用线性期望求和解题思路（下）第三步：让B在n个纯策略之间的期望支付相等，即同时让其在所有n个纯策略的选择上无差异，这可获得n-1个等式方程第四步：给定B的混合策略是向量y，对A进行第二步和第三步，可获得m-1个等式方程第五步：联立所有方程，共n+m个线性方程，有n+m个未知数。若可得出唯一解(x*, y*)，则它就是该博弈的混合策略纳什均衡的候选解第六步：判断所有的数值是否在[0, 1]区间内49例1B左右上（4, 0）（2, 4）A下（1, 6）（5, 2）例2B左右上（a, 1）（-1, -1）A下（-1, -1）（1, 2）50例3：小偷与守卫的博弈一个守卫看守一个仓库有个小偷想来仓库偷东守卫西，但守卫可能睡觉也可能不睡觉睡不睡如果守卫睡觉，小偷可偷窃成功，获得正效用V，守卫因失职而受罚D偷(V, -D)(-P, 0)若守卫不睡觉，守卫能小抓住小偷，小偷受罚P偷小偷不偷、守卫睡，S不偷(0, S)(0, 0)第55页第2.2题计算混合策略纳什均乙衡之前，需剔除所有的严格劣策略1231(2, 0)(1, 1)(4, 2)甲2(3, 4)(1, 2)(2, 3)3(1, 3)(0, 2)(3, 0)51第二次作业书：《博弈论及其应用》，汪贤裕、肖玉明第55-56页：第2.3题，第2.7题，第2.8题，第2.10题，第2.11题。额外题目：当听课中存在不懂的地方时，可以自己提问，也可等待别人提问。请构造一个自己提问与等待别人提问的博弈。支付矩阵由你自己构造，但相对大小的差别，需加以说明。构造好以后，求出它的所有纳什均衡解。交作业的时间：10月15日（星期四）课堂测试：懦夫博弈两人开车迎面行驶每个司机都可在相撞前乙转向，避免撞车，但会被视为“懦夫”；另一人因勇敢而效用高转向向前如果两人都不想被视为懦夫而保持向前，则车转向1, 1-2, 2辆相撞，每人损失很大请找出此博弈的所有纳甲什均衡解向前2, -2-4, -452课堂测试中出现的问题四分之三的同学能够基本做对能够做到全对的是接近三分之一具体的问题有这样几种混合策略纳什均衡解的表述给定A的一个混合策略，计算B选择某个纯策略的期望支付时，不是让该期望支付等于0，而是先计算出表达式，然后让B在所有纯策略上的期望支付两两相等。只有在某个纯策略的期望支付恰好等于0时，才有其它纯策略下的期望支付也等于0。理解混合策略纳什均衡为什么要使用混合策略？一种解释是，如果自己的活动呈现出规律性，容易被对手对症下药。因此，有时候在自己的行为选择上加入随机性，反而有利于自己。另一种解释是从群体推断个体的角度。为什么有警匪一家的说法？从群体角度看，总有一些与匪贼串谋的警察，比如《无间道》。从而警察以某个概率抓匪贼的情形，可以理解为有一部分警匪合谋、能逃脱抓捕的结果。53为什么会有警匪一家的说法一方面，不可能所有的警察都与匪贼合谋，否则警察这一群体就失去其存在的合理性。另一方面，没有一个警察与匪贼合谋这种极端情形也是很难想像的。如果所有警察都是完全正义的、以抓贼为唯一目标，从而匪贼被抓得在此群体里绝迹，那么后续将要发生的事情就是“飞鸟尽，良弓藏，狡兔死，走狗烹”。警察这个群体会面临所谓的裁剪冗员的命运。受此潜在威胁的影响，有的警察就会故意放跑匪贼混合策略的麻烦混合策略的思想的确美妙，它使得现实世界中的博弈结果更为丰富和复杂。但是，有些情形也表明，不可过于迷恋混合策略均衡的想法一个例子是国家大事不可儿戏。当国家有重大决策需要做出时，如果以掷骰子的方式来选择自己的策略的话，那就太儿戏了。比如二战末期，美国用原子弹轰炸日本的城市。这种涉及上百万人性命的事情，如果其决策仅仅是靠掷骰子的方式做出的，那未免太荒唐了54混合策略的低效率一个课堂提问的博弈如右图所示乙其混合策略纳什均衡是奇数((0.3, 0.7), (0.3, 0.7))定理不问提问至少有一人提问的概率是：1－0.3×0.3＝0.91由于有人提问对提高大不家的福利都有好处，而问(0, 0)(10, 7)0.91的概率看起来并不甲低提问(7, 10)(7, 7)混合策略的低效率但是，当博弈的参与人不是两个，而是很多个的时候，情况就不一样了假设课堂有n个同学，是否提问这一行为选择在各人之间是相互独立、互不影响的可假设混合策略是((q1, 1－q1), (q2, 1－q2), ···, (qqn, 1－qn))，即各人不提问的概率依次是q1、2、···、qn。因已假设各人的行为是相互独立的，故可以考虑对称的情形，即每个人不提问的概率都为q55混合策略的低效率对于一人而言，只要其他人中有一人提问，自己的问题也就可以解决了，即可获得效用10其它人中，没有一人提问的概率是：qn-1其它人中，至少有一人提问的概率是：1－qn-1此人选择“不提问”的期望支付是：10(1－qn-1)此人选择“提问”的期望支付是：7可解出q*＝0.31/(n-1)当n=2时，两人博弈，某人不提问的概率是0.3混合策略的低效率但是，当参与者增加时，一个人不提问的概率跟着提高。参与者人数越多，则每个人袖手旁观的概率越大。当班上有61位同学时，每个人将以0.9801的概率选择不提问。这是多高的概率呢？！而没有一个人提问的概率是0.2940。这已经不是一个小概率了。n=2时，无人提问的概率仅为0.09参与人越多，则每个人都希望由别人去承担提问成本，结果大家都陷入囚徒困境：无人提问56第二章结束57