完全信息静态博弈

《完全信息静态博弈》由会员分享，可在线阅读，更多相关《完全信息静态博弈（41页珍藏版）》请在金锄头文库上搜索。

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

2、策略组合 ，它满足两个要求。1.对每个局中人 ，能够预期到对手采用策略组合 。2.对每个局中人 ， 是他应对 的最好的策略。纳什均衡的定义纳什均衡的定义定义定义2.1 设 为一具有完全信息的策略型博弈模型，称策略组合 为G的一个纳什均纳什均衡衡。如果对 是在 i的对手策略组合为 条件下局中人i的最优反应策略，即 或 对 。如果以上不等式对严格成立，称 为 G 的严格纳什均衡严格纳什均衡。2在完全信息静态博弈中可用纳什均衡预测每个参与人的策略，进而预测我们所关心的各种博弈结果。扩展型博弈模型的纳什均衡定义为它所对应的策略型博弈的纳什扩展型博弈模型的纳什均衡定义为它所对应的策略型博弈的纳什均衡均衡

3、。例例2.1 囚徒困境问题囚徒困境问题在例1.6给出的囚徒困境问题中， 是惟一的严格纳什均衡。（对斯密“看不见的手”的质疑）策略组合 都不是纳什均衡。这个模型中，基于自利理性的假设，局中人为了各自利益选择坦白的策略，其结果是双方各获得-5的支付。显然双方可以得到更好的结局，即双方都采取抵赖策略各得-1的支付（帕累托最优），自利理性选择的结果并非帕累托最优，从个体利益出发的行为往往不能实现社会的最大利益；不止如此，自利理性本身存在内在矛盾从个体利益出发的行为最终也不一定能真正实现个体的最大利益，甚至会得到相当差的结果。 3例例2.2 伯川德（伯川德（Berchand） 均衡均衡设有生产同质产品的

4、两个企业，同时独立地确定产品的价格。已知该产品市场需求函数为 ，满足 。这里q代表产量，p代表价格。两个企业具有相同的单位成本 . 企业的利润函数如下：这里 表示两个企业的价格分别为 时，市场对于企业的产品的需求量。4上述企业价格竞争问题可以归结为完全信息静态博弈模型 其中:局中人集合 。策略集合 表示企业所有可行价格构成的集合。支付函数 。为求该模型的纳什均衡，可先将策略组合集合中的点分为4类，分别讨论它们是否能构成纳什均衡。5第1类， 第2类， 第3类 ， 第4类 , （1）当 ， 不是纳什均衡。（2）当 ， 不是纳什均衡。（3）当 ， 不是纳什均衡。（4）当 ， 是纳什均衡。称其为伯川德

5、均衡伯川德均衡。62.2 求纳什均衡的划线法求纳什均衡的划线法划线法划线法对于二人有限博弈 ， ， G 可由支付矩阵 给出。设 为G的纳什均衡。即 是局中人2对于 的最优反应， 是局中人1对于 的最优反应。7G的纳什均衡可由以下划线法划线法求得。例例2.4在囚徒困境问题中，其支付矩阵为应用划线法，支付矩阵中的元素（-5，-5）下都划上了短线，其所对应的策略组合为纳什均衡，且是严格的纳什均衡，8例例2.5 斗鸡博弈斗鸡博弈 两个人举着火棍从独木桥的两端走向中央进行火拼，每个人都有两种战略：继续前进，或退下阵来。若两个人都继续前进，则两败具伤；若一方前进，另一方退下来，前进者胜利，退下来的丢了面子

6、；若两人都退下来，两人都丢面子，支付矩阵如下：用划线法可得严格纳什均衡（退，进），（进，退）。（试写出金发女郎博弈的矩阵，并求出NE）9例例2.6 智猪博弈智猪博弈猪圈里圈着两头猪，一头大猪，一头小猪。猪圈的一边有一个猪食槽，另一边安装一个按钮，按一下按钮会有10个单位的猪食进槽。但谁按按钮就需要付2个单位的成本。若大猪先到，大猪吃到9个单位，小猪吃到1个单位；若同时到，大猪吃7个单位，小猪吃3个单位；若小猪先到，大猪吃6个单位，小猪吃4个单位，支付矩阵如下。严格纳什均衡为大猪“按”，小猪“等待”。10例例2.7 在例1.8中的大堤维护博弈中，支付矩阵为利用划线法可得纳什均衡（维护，维护），（

7、不维护，不维护）。为了保护生命财产的安全，政府可以立法，如果参与人不维护大堤，需付罚款5，则有支付矩阵这时该博弈有惟一的纳什均衡（维护，维护）。112.3 最优反应映射与纳什均衡最优反应映射与纳什均衡定义定义2.2 局中人的最优反应映射局中人的最优反应映射局中人i的最优反应映射是一个定义于策略组合集合S, 取值于策略集 的子集的集值映射（映射值为集合的映射称为集值映射）， ，满足定义2.2表明，局中人i的最优化反应映射 仅与 有关。反应函数反应函数当 为单点集时，称 为局中人i的最优反应函数最优反应函数，简称反应函数反应函数。这时将 记为 。12定义定义2.3 最优反应映射最优反应映射n个参与

8、人的最优反应映射的乘积称为博弈G的最优反应映射最优反应映射。博弈的最优反应映射与纳什均衡之间的关系博弈的最优反应映射与纳什均衡之间的关系定理定理2.1 为策略型博弈 的纳什均衡的充要条件是 。设 为一集值映射。若 ，称x为 的不不动点动点。利用不动点概念，定理2.1可以如下叙述。命题命题2.4 s是策略型博弈G的纳什均衡的充要条件是 s是最优反应映射 r (s) 的不动点，即 s r (s) 。13例例2.8 在囚徒困境问题中， 是囚徒困境博弈的惟一纳什均衡。例例2.9 多囚徒困境问题将例1.6中两个囚徒推广为 个囚徒，且量刑的规则为，如果n个囚徒都抗拒，各判1年；如n个囚徒都坦白，各判5年；

9、如果n个囚徒中有的坦白，有的抗拒。坦白者释放，抗拒者判8年。这说明 是惟一的纳什均衡。14例例2.11 国际联盟博弈国际联盟博弈 为毗邻某海岸的三个国家，他们在这个海岸附近驻扎军队。要想控制整个海湾，至少需要两个国家联合起来。三国的兵力部署与相应的支付由以下支付矩阵给出 w选择陆地 w选择近海 支付向量的第1，2，3个分量分别给出的 的支付值。15局中人的最优反应映射为 ， ， ， 。因s为纳什均衡需满足 ，故纳什均衡仅能存在于策略组合 ， ， ， 中。 16 故 纳什均衡存在于策略组合 ， ， 中。 ， ， 从而该博弈的纳什均衡为 ， , ，相应的支付向量为 ， ， 。 17两国结成联盟控制

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

11、策略组合都是纳什均衡。特别是对于三人有限策略博弈模型,我们可给出纳什均衡的划线法。设参与人的策略集合分别为 ， , 对 .对每个 ， ，都可写出一个以3维向量为元素的m行n列的支付矩阵。19例例2.12 公共物品提供公共物品提供对于公共物品，提供者与不提供者都享受同样的效益，且公共物品提供的成本仅与其提供的服务水平有关，而与享用其效益的人数无关（如装路灯）。设甲、乙、丙三人决定是否提供某项公共物品。1 表示提供，0 表示不提供。提供者需付出成本。而收益为已被提供的公共物品的数量，分别就 讨论该博弈的纳什均衡。（1）当）当c=0.5，支付矩阵如下。，支付矩阵如下。丙提供： 丙不提供： 由划线法知

12、，（1，1，1）是纳什均衡。20（2）当）当c=1时，支付矩阵为时，支付矩阵为丙提供： 丙不提供： 任何一个策略组合都是纳什均衡。（3）c=1.5，支付矩阵为，支付矩阵为丙提供： 丙不提供： （0，0，0）为纳什均衡。212.4 求纳什均衡的反应函数法求纳什均衡的反应函数法如果博弈G 的n个局中人的最优反应映射都是反应函数，我们有如下定理。定理定理2.2 为博弈 的纳什均衡的充要条件是是局中人的n条最优反应曲线 ， 的交点。由定理2.2，可用以下两步求得纳什均衡可用以下两步求得纳什均衡。1.求出每个参与人的最优反应函数 ， 。2.求 ， 的交点。222-5 古诺古诺(Cournot)寡头竞争模

13、型寡头竞争模型 古诺寡头竞争模型可以说是纳什均衡最早的版本，它比纳什(1959)本人的定义早了l00多年。在古诺模型里，有两个参与人，分别称为企业1和企业2；每个企业的战略是选择产量；支付是利润，成本是两个企业产量的 函数我们用 代表第i个企业的产量， 代表成本函数， 代表逆需求函数(P是价格；Q(P)是原需求函数)。第i个企业的利润函数为： , i=1,2 23 是纳什均衡产量意味着: 找纳什均衡,就是求函数极大值问题：对利润函数求导,并令其等于零：以上两个方程都是两企业产量的函数，即反映出两企业产量间的关系称做反应函数。 反应函数意味着每个企业的最优战略（产量）是另一个企业产量的函数。24

14、反应函数的坐标图右图 两曲线的交叉点NE就是纳什均衡进一步简化： 假定每个企业具有相同的不变单位成本，即： 需求函数取线性形式： 最优化的一阶条件为： NE25反应函数为： 就是说一个企业每增加一个单位的产量，另一个企业将减少1/2单位的产量。 故：（一）（一）每个企业的纳什均衡利润分别为：（二）（二）计算垄断企业的最优产量和均衡利润 1、利润函数： 2、最优产量： 3、垄断利润： 26寡头竞争时，总产量大于垄断产量，而总利润却小于垄断利润，其原因就在于每个企业在选择自己的最优产量时，只考虑对本企业利润的影响，而忽视对另一企业的外部负效应。这是典型的囚徒困境。那么，两个企业可以联合吗？272.

15、6 混合战略纳什均衡混合战略纳什均衡有些博弈不存在纳什均衡。例一：小学生的手指配对游戏 两个小学生同时出手，并伸出一个或两个手指头，若配起来是奇数，则甲胜；是偶数，则乙胜。假设输者给赢者1美元，不同策略下的输赢图如下表： 假如两个选手的行动不是随 机的，这个博弈就没有均衡点没有均衡点。 这类博弈的最终结果难于作出这类博弈的最终结果难于作出 明确的预测，无法给参与博弈明确的预测，无法给参与博弈 的局中人提供明确的决策建议。的局中人提供明确的决策建议。一、混合策略与纯策略的区别一、混合策略与纯策略的区别 1、定义：、定义：所谓混合策略，不是纯粹的这样做或者那样做，而是随机地以百分之多少选择这样做，

16、以百分之多少选择那样做，且所有策略的概论和为1。 偶数者 1个指头 2个指头奇数者1个指头 2个指头-1，11，-1-1，11，-128 2、区别：、区别：混合策略指按照一定的概率选择一种纯策略作为实际的行动。纯策略指纯粹的选择这种策略或者那种策略。混合策略包含原来的纯策略，或者说是纯策略的推广。二、混合策略的表示法二、混合策略的表示法纯策略组合的表示法是：混合策略组合的表示法:(p,1-p),(p,r,q,1-p-r-q)三、与混合策略相伴随的问题三、与混合策略相伴随的问题1、不确定性：避免纯策略，避免策略具有规律性；2、期望支付（1）在概率论中）在概率论中，如果一个数量指标，由n个可能的取

17、值 并且这些取值发生的概率分别是：那么我们可以将这个数量指标的期望值定义为以发生概率作为权数的所有可能取值得加权平均，即例如：扔两枚硬币，两个正面都朝上得5元，一个朝上一个朝下得1元，两个都朝下得0元。求得钱的期望值。29 现在来求“小学生的手指配对游戏”的期望值问题。设甲出一个指头的概率是p，乙出一个指头的概率是q。期望值用Ua(p,q),Ub(p,q) 则 Ua(p,q)=. Ub(p,q)=. （2）更为一般的情况：）更为一般的情况：两个参与人各有m、n个策略，混合策略向量形式：若对于某个纯策略，有 ，而 对任意 都成立，那么混合策略p=(0,0,0,1,0,0)实际上就是i这一个纯策略

18、。30反应函数法反应函数法求混合策略纳什均衡求混合策略纳什均衡 1、“手指配对游戏”局中人甲的期望值为： Ua(p,q)=2p(1-2q)+(2q-1)当乙的混合策略为(q,1-q)，则甲的（最佳）函数是： 0 如果q1/2 p= 0,1 如果q=1/2 1 如果q1/2 q= 0,1 如果p=1/2 1 如果p1/2 我们把甲、乙的反应函数在坐标轴中划出来，两个反应函数重叠的地方就是混合策略的纳什均衡。（如下图） 乙：偶数者 q:1个指头 2个指头奇数者 甲：p:1个指头 2个指头-1，11，-1-1，11，-1310 1 qP11/2从右图中可求出其混合策略的纳什均衡为：混合博弈的显著特征

19、： 每一个参与人都想猜透对方的战略，而每一个参与人又都不能让对方猜透自己的战略。此类问题还有扑克比赛、橄榄球赛、战争等。322、随机行动必要性的判别标准：假设你的行动在出招之前让对手知道，看是否对你有害处。4、并非任何随机性都会凑效。如己方以75%、25%的概率出奇偶数，.。这种随机性的混合模式将会被对方利用，使己方一败涂地。5、可见随机性存在一种均衡模式，均衡模式，使得对方无论怎样利用，都不会占便宜。6、此博弈是一个零和博弈，即一方所得恰是另一方所失，也没有纳什均衡。 混合策略中应注意的几个问题混合策略中应注意的几个问题1、避免有规则有规则的思考与行动方式，因为这样就会被对方看穿并加以利用，

20、从而使己方受损。利用随机性原理，努力作到不可预测。不可预测。33例2：社会福利博弈。 参与人是政府和一个流浪汉，流浪汉有两个战略：寻找工作或游荡；政府也有两个战略：救济或不救济。政府想帮助流浪汉，但前提是后者必须试图找工作；而流浪汉只有在得不到政府救济时才会找工作。支付矩阵如表： 此博弈也不存在前面定义的纳什均衡，但存在下面将要定义的混合战略纳什均衡。这里，混合战略混合战略指的是参与人以一定的概率随指的是参与人以一定的概率随机地选择某种战略。机地选择某种战略。 如 ：（1）政府以0.7的概率选择救济，以0.3的概率选择不救济；（2）或以0.5、0.5的概率选择救济与不救济。流浪汉如何应对？结果

21、怎样？政府的混合战略：救济 0.5 流浪汉混合战略：游荡0.2 不救济 0.5 找工作0.8结论：每一个参与人的混合战略都是给定对方混合战略时的最优选择。这就是混合战略纳什均衡。 流浪汉 寻找工作 游荡 政府 救济不救济3，2-1，10，0-1，334 混合战略纳什均衡的求解混合战略纳什均衡的求解以社会福利博弈为例：最大化法最大化法求解混合战略纳什均衡求解混合战略纳什均衡设政府的混合战略： 流浪汉的混合战略：政府的期望效用函数为： 效用最大化条件：同理，流浪汉的期望效用函数： 效用最大化条件为： 故： 流浪汉 寻找工作 游荡 政府 救济不救济3，2-1，10，0-1，335例例3、监督博弈、监

22、督博弈税收税收 监督博弈是猜谜博弈的变种，它概括了诸如税收检查、质量检查、惩罚犯罪、顾主监督雇员等；这里以税收为例进行讨论。 支付矩阵 参与人 纯战略税收机关 检查，不检查 纳税人 逃税，不逃税 右表概括了对应不同纯战略组合的支付矩阵，其中,a是应纳税款；C是检查成本；F是罚款，假定C1/4p= 0,1 如果 q=1/4 0 如果 q3/4q= 0,1 如果 p=3/4 0 如果 p3/413/4p101/4q391、反应函数法可以同时找出纯策略纳什均衡和混合策略纳什均衡2、混合策略纳什均衡的意义: 如果小娟以3/4的概率选择芭蕾，陈明以1/4的概率选择足球，那么，小娟的期望收益是：而陈明的收益是：结论：混合策略的收益小于纯策略的收益，可见，纯策略具有支付优势。我们把这种表现为支付的优势叫做帕累托优势帕累托优势。40 英国支持巴顿 支持蒙帅美国支持巴顿 支持蒙帅4，32，21，13，4作业：作业：二战中，艾什豪威尔所领导的美英联军在支持巴顿将军还是支持蒙哥马利元帅的问题上，存在着博弈。其支付矩镇如下图，分别用反应函数法和最大值法求解其纳什均衡。41