完全信息静态博弈课件

1、完全信息静态博弈第第2章章 完全信息静态博弈完全信息静态博弈 电影美丽心灵中，有人向纳什提出了这样一个问题，问题的背景如下：在一个舞会上，有两个以上的男士，有比男士更多的魅力十足的女士，但只有一个金发女郎，男人开始邀请舞伴，但只能邀请一次请一个女郎作为舞伴，所有男士更喜欢金发女郎，但有女伴比无女伴要好，如果两个男士同时邀请一个女士，两人都会被拒绝。假设你作为一个男士，你会如何邀请舞伴？完全信息静态博弈2.1 纳什均衡的定义纳什均衡的定义纳什均衡是博弈论中纳什均衡是博弈论中最重要最重要的概念，各种非合作博弈模型的均衡概的概念，各种非合作博弈模型的均衡概念都是建立在纳什均衡基础之上的念都是建立在纳

2、什均衡基础之上的。纳什均衡是个策略组合 ，它满足两个要求。1.对每个局中人 ，能够预期到对手采用策略组合 。2.对每个局中人 ， 是他应对 的最好的策略。纳什均衡的定义纳什均衡的定义定义定义2.1 设 为一具有完全信息的策略型博弈模型，称策略组合 为G的一个纳什均纳什均衡衡。如果对 是在 i的对手策略组合为 条件下局中人i的最优反应策略，即 或 对 。如果以上不等式对严格成立，称 为 G 的严格纳什均衡严格纳什均衡。),(*iisssiN*isi*is*isn1n1u,u,S,S,NGiiiiiiSSsSssss,),(*,iiN S *iiss),(max),(*iiissiiissussu

3、ii),(),(*iiiiiissussuiiSs *s完全信息静态博弈 在完全信息静态博弈中可用纳什均衡预测每个参与人的策略，进而预测我们所关心的各种博弈结果。 扩展型博弈模型的纳什均衡定义为它所对应的策略型博弈的纳什扩展型博弈模型的纳什均衡定义为它所对应的策略型博弈的纳什均衡均衡。 例例2.1 囚徒困境问题囚徒困境问题 在例1.6给出的囚徒困境问题中， 是惟一的严格纳什均衡。（对斯密“看不见的手”的质疑） 策略组合 都不是纳什均衡。 这个模型中，基于自利理性的假设，局中人为了各自利益选择坦白的策略，其结果是双方各获得-5的支付。 显然双方可以得到更好的结局，即双方都采取抵赖策略各得-1的支

4、付（帕累托最优），自利理性选择的结果并非帕累托最优，从个体利益出发的行为往往不能实现社会的最大利益；不止如此，自利理性本身存在内在矛盾从个体利益出发的行为最终也不一定能真正实现个体的最大利益，甚至会得到相当差的结果。 )C,C(*s)D,D(),C,D(),D,C(完全信息静态博弈 例例2.2 伯川德（伯川德（Berchand） 均衡均衡设有生产同质产品的两个企业，同时独立地确定产品的价格。已知该产品市场需求函数为 ，满足 。这里q代表产量，p代表价格。两个企业具有相同的单位成本 . 企业的利润函数如下：这里 表示两个企业的价格分别为 时，市场对于企业的产品的需求量。)(pDq 0)(pDCC

5、C21)2 , 1,(),()(),(jippDCpppjiiijii),(jiippDjipp ,. 2 , 1,0)(21)(),(jipppppDpppDppDjijiijiijii完全信息静态博弈 上述企业价格竞争问题可以归结为完全信息静态博弈模型 其中: 局中人集合 。 策略集合 表示企业所有可行价格构成的集合。 支付函数 。 为求该模型的纳什均衡，可先将策略组合集合中的点分为4类，分别讨论它们是否能构成纳什均衡。2121u,u,S,S,NG 2 , 1N ,CSS212 , 1,),(),(jippppujiijii完全信息静态博弈 第1类， 第2类， 第3类 ， 第4类 , （1

6、）当 ， 不是纳什均衡。 （2）当 ， 不是纳什均衡。 （3）当 ， 不是纳什均衡。 （4）当 ， 是纳什均衡。称其为伯川德均衡伯川德均衡。11212(,)RppppC212121221(,)(,)RppppCppppC),(),(122121213CppppCppppR),(21214CppppR121),(Rpp),(21pp221),(Rpp),(21pp321),(Rpp),(21pp421),(Rpp12(,)( ,)ppC C完全信息静态博弈2.2 求纳什均衡的划线法求纳什均衡的划线法 划线法划线法 对于二人有限博弈 ， ， G 可由支付矩阵 给出。 设 为G的纳什均衡。即 是局中

7、人2对于 的最优反应， 是局中人1对于 的最优反应。2121u,u,S,S,NG 2 , 1N ),(),(),(),(),(),(),(),(),(2211222222212111121211112121mnmnmmmmnnnnmnbababababababababa),(*2*1*sss *2s*1s*1s*2s完全信息静态博弈 G的纳什均衡可由以下划线法划线法求得。 例例2.4在囚徒困境问题中，其支付矩阵为 应用划线法，支付矩阵中的元素（-5，-5）下都划上了短线，其所对应的策略组合为纳什均衡，且是严格的纳什均衡，)1, 1()0,8(8,0)5,5(DCDC完全信息静态博弈 例例2.5

8、 斗鸡博弈斗鸡博弈 两个人举着火棍从独木桥的两端走向中央进行火拼，每个人都有两种战略：继续前进，或退下阵来。若两个人都继续前进，则两败具伤；若一方前进，另一方退下来，前进者胜利，退下来的丢了面子；若两人都退下来，两人都丢面子，支付矩阵如下： 用划线法可得严格纳什均衡（退，进），（进，退）。 （试写出金发女郎博弈的矩阵，并求出NE）)0,0()2,0(0,2)3,3(退进退进完全信息静态博弈 例例2.6 智猪博弈智猪博弈 猪圈里圈着两头猪，一头大猪，一头小猪。猪圈的一边有一个猪食槽，另一边安装一个按钮，按一下按钮会有10个单位的猪食进槽。但谁按按钮就需要付2个单位的成本。若大猪先到，大猪吃到9个

9、单位，小猪吃到1个单位；若同时到，大猪吃7个单位，小猪吃3个单位；若小猪先到，大猪吃6个单位，小猪吃4个单位，支付矩阵如下。 严格纳什均衡为大猪“按”，小猪“等待”。)0,0()1,9(44)1 ,5(，等待按等待按完全信息静态博弈 例例2.7 在例1.8中的大堤维护博弈中，支付矩阵为 利用划线法可得纳什均衡（维护，维护），（不维护，不维护）。 为了保护生命财产的安全，政府可以立法，如果参与人不维护大堤，需付罚款5，则有支付矩阵 这时该博弈有惟一的纳什均衡（维护，维护）。)10,10()14,10(1014)4,4），（不维护维护不维护维护)15,15()14,15(1514)4, 4），（不

10、维护维护不维护维护完全信息静态博弈2.3 最优反应映射与纳什均衡最优反应映射与纳什均衡 定义定义2.2 局中人的最优反应映射局中人的最优反应映射 局中人i的最优反应映射是一个定义于策略组合集合S, 取值于策略集 的子集的集值映射（映射值为集合的映射称为集值映射）， ，满足 定义2.2表明，局中人i的最优化反应映射 仅与 有关。 反应函数反应函数 当 为单点集时，称 为局中人i的最优反应函数最优反应函数，简称反应函数反应函数。这时将 记为 。),(max),()(iiiSsiiiiiissustuStsriiiiSsr)(iSiS)(sriis)(sri)(sri)(sri)(iisBR完全信息

11、静态博弈 定义定义2.3 最优反应映射最优反应映射 n个参与人的最优反应映射的乘积 称为博弈G的最优反应映射最优反应映射。 博弈的最优反应映射与纳什均衡之间的关系博弈的最优反应映射与纳什均衡之间的关系 定理定理2.1 为策略型博弈 的纳什均衡的充要条件是 。 设 为一集值映射。若 ，称x为 的不不动点动点。 利用不动点概念，定理2.1可以如下叙述。 命题命题2.4 s是策略型博弈G的纳什均衡的充要条件是 s是最优反应映射 r (s) 的不动点，即 s r (s) 。, 2 , 1, )(),()()()()(2121nisrttttsrsrsrsriinnS*s n1n1u,u,S,S,NG)

12、s(r*s*)(Yf)(XfX )(Yf完全信息静态博弈 例例2.8 在囚徒困境问题中， 是囚徒困境博弈的惟一纳什均衡。 例例2.9 多囚徒困境问题 将例1.6中两个囚徒推广为 个囚徒，且量刑的规则为，如果n个囚徒都抗拒，各判1年；如n个囚徒都坦白，各判5年；如果n个囚徒中有的坦白，有的抗拒。坦白者释放，抗拒者判8年。 这说明 是惟一的纳什均衡。),(),(,),(),(1111CDDrDCrCCDrCCr)C,C(), 4 , 3 , 2(n),(),(),(),(),(21CCCrCCrCCrCCrCCCn),(CCC完全信息静态博弈 例例2.11 国际联盟博弈国际联盟博弈 为毗邻某海岸的

13、三个国家，他们在这个海岸附近驻扎军队。要想控制整个海湾，至少需要两个国家联合起来。三国的兵力部署与相应的支付由以下支付矩阵给出 w选择陆地 w选择近海 支付向量的第1，2，3个分量分别给出的 的支付值。WSL,），（），（），（，（南北东西444000177666LS），（），（），（，（南北东西771444000717LSW，SL完全信息静态博弈 局中人的最优反应映射为 ， ， ， 。 因s为纳什均衡需满足 ，故纳什均衡仅能存在于策略组合 ， ， ， 中。 )()(11北南，西，陆北，西，陆 rr)()(11北南，东，陆北，东，陆 rr)()(11北南，西，海北，西，海 rr)()(11南南

14、，东，海北，东，海 rr)(srsii)(北，西，陆)(北，东，陆)(北，西，海)(南，东，海完全信息静态博弈 故 纳什均衡存在于策略组合 ， ， 中。 ， ， 从而该博弈的纳什均衡为 ， , ， 相应的支付向量为 ， ， 。 )(2东北，西，陆 r)(2东北，东，陆 r)(2西北，西，海 r)(东南，东，海 ir)(北，东，陆)(北，西，海)(南，东，海)(3陆北，东，陆 r)(3海北，西，海 r)(3海南，东，海 r)(北，东，陆)(北，西，海)(南，东，海) 1 , 7 , 7()7 , 1 , 7()7 , 7 , 1 (完全信息静态博弈 两国结成联盟控制海湾将会出现以下情况。 （1）

15、L与S联盟，分别将兵力部署于北、东，W将把兵力部署于陆地； （2）L与W联盟，分别把兵力部署于北、海，S将把兵力部署于西； （3）S与W联盟，分别将兵力部署于东、海，L将把兵力部署于南。 尽管三个国家都联合起来，总支付最大，但他们之间如无具有约束力的协议，这种联盟是不稳定的，因它不是一个纳什均衡。 由上例我们可以得出求多人有限策略型博弈的纳什均衡的方法，步骤如下：完全信息静态博弈 1.对S中所有的策略组合计算 ，如果 ，则从S剔除 ，剩余策略组合集合记为 。 2.对 中所有的策略组合S计算 。如 ，则从S中剔除 ，剩余集合记为 。 3.应用类似方法n步，如 ，从 中剔除 ，最后得到 。 中的策

16、略组合都是纳什均衡。 特别是对于三人有限策略博弈模型,我们可给出纳什均衡的划线法。 设参与人的策略集合分别为 ， , 对 .对每个 ， ，都可写出一个以3维向量为元素的m行n列的支付矩阵。)(1sr)(11srs 1s1S1S)(2sr22( )srs2s2S)(srsnn1nSnsnSnS,211mS,212nS,213kSiki,2 ,121完全信息静态博弈 例例2.12 公共物品提供公共物品提供 对于公共物品，提供者与不提供者都享受同样的效益，且公共物品提供的成本仅与其提供的服务水平有关，而与享用其效益的人数无关（如装路灯）。 设甲、乙、丙三人决定是否提供某项公共物品。1 表示提供，0

17、表示不提供。提供者需付出成本。而收益为已被提供的公共物品的数量，分别就 讨论该博弈的纳什均衡。 （1）当）当c=0.5，支付矩阵如下。，支付矩阵如下。 丙提供： 丙不提供： 由划线法知，（1，1，1）是纳什均衡。) 5 . 011 () 5 . 15 . 12() 5 . 125 . 1 () 5 . 25 . 25 . 2(0101，甲乙5 . 115 . 0，c)000() 15 . 01 () 115 . 0()25 . 15 . 1 (0101，甲乙完全信息静态博弈 （2）当）当c=1时，支付矩阵为时，支付矩阵为 丙提供： 丙不提供： 任何一个策略组合都是纳什均衡。 （3）c=1.5，

18、支付矩阵为，支付矩阵为 丙提供： 丙不提供： （0，0，0）为纳什均衡。101 (1.5 1.5 1.5)(0.5 2 0.5)0(2 0.5 0.5)(11 0.5)乙， ，甲， ， ，)011()112(121()222(0101，），甲乙)000() 101 () 110()211 (0101，甲乙101 (0.5 0.5 2)(0.5 1 1)0(1 0.5 1)(0 0 0)乙， ， ，甲， ，完全信息静态博弈2.4 求纳什均衡的反应函数法求纳什均衡的反应函数法 如果博弈G 的n个局中人的最优反应映射都是反应函数，我们有如下定理。 定理定理2.2 为博弈 的纳什均衡的充要条件是是局中

19、人的n条最优反应曲线 ， 的交点。 由定理2.2，可用以下两步求得纳什均衡可用以下两步求得纳什均衡。 1.求出每个参与人的最优反应函数 ， 。 2.求 ， 的交点。*12*(,)nssssn1n1u,u,S,S,NG)(iiisBRsni,2, 1)(iisBRni, 2 , 1)(iiisBRsni, 2 , 1完全信息静态博弈2-5 古诺古诺(Cournot)寡头竞争模型寡头竞争模型 古诺寡头竞争模型可以说是纳什均衡最早的版本，它比纳什(1959)本人的定义早了l00多年。在古诺模型里，有两个参与人，分别称为企业1和企业2；每个企业的战略是选择产量；支付是利润，成本是两个企业产量的 函数我

20、们用 代表第i个企业的产量， 代表成本函数， 代表逆需求函数(P是价格；Q(P)是原需求函数)。第i个企业的利润函数为： , i=1,2 0,)iq ( )iiC q12()PP qq1212( ,)()( )iiiiq qqP qqC q完全信息静态博弈 是纳什均衡产量意味着: 找纳什均衡,就是求函数极大值问题：对利润函数求导,并令其等于零：以上两个方程都是两企业产量的函数，即反映出两企业产量间的关系称做反应函数。 反应函数意味着每个企业的最优战略（产量）是另一个企业产量的函数。*12(,)q q*111211211argmax(,)()(),qq qq P qqC q*221221222a

21、rgmax(,)()(),qq qq P qqC q212212222()()()0P qqq P qqC qq112112111()()()0P qqq P qqC qq*112()qR q*221()qR q完全信息静态博弈反应函数的坐标图右图 两曲线的交叉点NE就是纳什均衡进一步简化： 假定每个企业具有相同的不变单位成本，即： 需求函数取线性形式： 最优化的一阶条件为： NE1q2q21()Rq12()R q*2q*1q*12(,)qq q111()C qq c222()C qq c12()Paqq21222,()0aqqqcq11211()0aqqqcq完全信息静态博弈反应函数为： 就

22、是说一个企业每增加一个单位的产量，另一个企业将减少1/2单位的产量。 故：（一）（一）每个企业的纳什均衡利润分别为：（二）（二）计算垄断企业的最优产量和均衡利润 1、利润函数： 2、最优产量： 3、垄断利润： *11221()()2qR qaqc*22111()()2qR qaqc*121()3qqac*21122121(,)(,)()9q qq qac()QMa xQ aQc*1212()()23Qacqqac2212()()49macac完全信息静态博弈寡头竞争时，总产量大于垄断产量，而总利润却小于垄断利润，其原因就在于每个企业在选择自己的最优产量时，只考虑对本企业利润的影响，而忽视对另一

23、企业的外部负效应。这是典型的囚徒困境。那么，两个企业可以联合吗？完全信息静态博弈2.6 混合战略纳什均衡混合战略纳什均衡有些博弈不存在纳什均衡。例一：小学生的手指配对游戏 两个小学生同时出手，并伸出一个或两个手指头，若配起来是奇数，则甲胜；是偶数，则乙胜。假设输者给赢者1美元，不同策略下的输赢图如下表： 假如两个选手的行动不是随 机的，这个博弈就没有均衡点没有均衡点。 这类博弈的最终结果难于作出这类博弈的最终结果难于作出 明确的预测，无法给参与博弈明确的预测，无法给参与博弈 的局中人提供明确的决策建议。的局中人提供明确的决策建议。一、混合策略与纯策略的区别一、混合策略与纯策略的区别 1、定义：

24、、定义：所谓混合策略，不是纯粹的这样做或者那样做，而是随机地以百分之多少选择这样做，以百分之多少选择那样做，且所有策略的概论和为1。 偶数者 1个指头 2个指头奇数者1个指头 2个指头-1，11，-1-1，11，-1完全信息静态博弈 2、区别：、区别：混合策略指按照一定的概率选择一种纯策略作为实际的行动。纯策略指纯粹的选择这种策略或者那种策略。混合策略包含原来的纯策略，或者说是纯策略的推广。二、混合策略的表示法二、混合策略的表示法纯策略组合的表示法是：混合策略组合的表示法:(p,1-p),(p,r,q,1-p-r-q)三、与混合策略相伴随的问题三、与混合策略相伴随的问题1、不确定性：避免纯策略

25、，避免策略具有规律性；2、期望支付（1）在概率论中）在概率论中，如果一个数量指标，由n个可能的取值 并且这些取值发生的概率分别是：那么我们可以将这个数量指标的期望值定义为以发生概率作为权数的所有可能取值得加权平均，即例如：扔两枚硬币，两个正面都朝上得5元，一个朝上一个朝下得1元，两个都朝下得0元。求得钱的期望值。12( ,.,)ns ss12,.,nx xx12,.,np pp1 122.nnp xp xp x完全信息静态博弈 现在来求“小学生的手指配对游戏”的期望值问题。设甲出一个指头的概率是p，乙出一个指头的概率是q。期望值用Ua(p,q),Ub(p,q) 则 Ua(p,q)=. Ub(p

26、,q)=. （2）更为一般的情况：）更为一般的情况：两个参与人各有m、n个策略，混合策略向量形式：若对于某个纯策略，有 ，而 对任意 都成立，那么混合策略p=(0,0,0,1,0,0)实际上就是i这一个纯策略。12(,.,)mpp pp0ip 11miip12( ,.,)nqq qq0jq 11njjq1ip 0kp ki完全信息静态博弈反应函数法反应函数法求混合策略纳什均衡求混合策略纳什均衡 1、“手指配对游戏”局中人甲的期望值为： Ua(p,q)=2p(1-2q)+(2q-1)当乙的混合策略为(q,1-q)，则甲的（最佳）函数是： 0 如果q1/2 p= 0,1 如果q=1/2 1 如果q

27、1/2 q= 0,1 如果p=1/2 1 如果p1/2 我们把甲、乙的反应函数在坐标轴中划出来，两个反应函数重叠的地方就是混合策略的纳什均衡。（如下图） 乙：偶数者 q:1个指头 2个指头奇数者 甲：p:1个指头 2个指头-1，11，-1-1，11，-1完全信息静态博弈0 1 qP11/2*1 1(,)( , )2 2p q从右图中可求出其混合策略的纳什均衡为：混合博弈的显著特征： 每一个参与人都想猜透对方的战略，而每一个参与人又都不能让对方猜透自己的战略。此类问题还有扑克比赛、橄榄球赛、战争等。完全信息静态博弈2、随机行动必要性的判别标准：假设你的行动在出招之前让对手知道，看是否对你有害处。

28、4、并非任何随机性都会凑效。如己方以75%、25%的概率出奇偶数，.。这种随机性的混合模式将会被对方利用，使己方一败涂地。5、可见随机性存在一种均衡模式，均衡模式，使得对方无论怎样利用，都不会占便宜。6、此博弈是一个零和博弈，即一方所得恰是另一方所失，也没有纳什均衡。 混合策略中应注意的几个问题混合策略中应注意的几个问题1、避免有规则有规则的思考与行动方式，因为这样就会被对方看穿并加以利用，从而使己方受损。利用随机性原理，努力作到不可预测。不可预测。完全信息静态博弈例2：社会福利博弈。 参与人是政府和一个流浪汉，流浪汉有两个战略：寻找工作或游荡；政府也有两个战略：救济或不救济。政府想帮助流浪汉，但前提是后者必须试图找工作；而流浪汉只有在得不到政府救济时才会找工作。支付矩阵如表： 此博弈也不存在前面定义的纳什均衡，但存在下面将要定义的混合战略纳什均衡。这里，混合战略混合战略指的是参与人以一定的概率随指的是参与人以一定的概率随机地选择某种战略。机地选择某种战略。 如 ：（1）政府以0.7的概率选择救济，以0.3的概率选择不救济；