纳什均衡专题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,情侣博弈的得益矩阵,1,2,足球,芭蕾,芭蕾,足球,2,1,小 丽,大 海,0,0,1,1,靠左走还是靠右走,在一个没有交通规范的农村小路骑自行车，你应该走在道路的哪一边？,假如别人靠右（左）走，你也 靠右（左）走，则不会相撞；反之，假如别人靠右（左）走，而你却反其道而行之，偏要靠左（右）走，则必然相撞。,假设行走顺利，每人获益为,1,，相撞，则获益为,1,，,画出得益矩阵,交通博弈,靠左行,靠右行,靠左行,靠右行,1,，,1,1,，,1,-1,，,-1,-1,，,-1,甲,乙,经典博弈故事之三智猪博弈,笼子里面有两只猪，一只比较大，一只比较小。笼子很长，一头有一个按钮，另一头是饲料的出口和食槽。按一下按钮，将有相当于,10,个单位的猪食进槽，但是按按钮以后跑到食槽所需要付出“劳动”，加起来要消耗相当于,2,个单位的猪食。问题是按钮和食槽分置笼子的两端，按按钮的猪付出劳动跑到食槽的时候，坐享其成的另一头猪早已吃了不少。如果大猪先到，大猪呼啦啦吃到,9,个单位，小猪只能吃到,1,个单位；如果同时到达，大猪吃到,7,个单位；小猪吃到,3,个单位；如果小猪先到，小猪可以吃到,4,个单位，而大猪吃到,6,个单位。,画出智猪博弈的得益矩阵,“智猪博弈”,(boxed pigs),按,等待,按,等待,5,，,1,4,，,4,9,，,1,0,，,0,大,猪,小 猪,经典博弈之四猎人博弈,设想在古代的一个地方，有两个猎人。那时候，狩猎是人们的主要生计。为了简单起见，假设主要的猎物只有两种：鹿，兔子。在古代，人类的狩猎手段还比较落后，弓箭威力也有限。在这样的条件下，我们可以进一步假设，两个猎人一起去猎鹿，才能猎获一只鹿，如果一个猎人单兵作战，他只能打到,4,只兔子。如果他打兔子，你去猎鹿，他可以打到,4,只兔子，而你一无所获，得,0,。,假设打到一只鹿，两家平分，每家管,10,天；打到,4,只兔子，只能供一家吃,4,天。,画出得益矩阵,猎人博弈得益矩阵,10,10,4,0,0,4,4,4,甲,乙,猎鹿,打兔,猎鹿,打兔,博弈论故事之五高薪养廉,“高薪养廉”是公务员制度方面的一种理论，我们分析一下“高薪”为什么能养廉？,假设甲乙为一家单位的主任和书记关系密切的国家公务员，,7,代表现在政府给他们的高薪。如果两人受贿，因为串谋而一时不被人发现，他们可以达到,9,的位置；而一旦“东窗事发”，他就要被撤职查办，不受贿一方得,8,画出得益矩阵,博弈论故事之五高薪养廉,我们把数据改变一下，变成薪水只有,2,，两个串谋，同时受贿还是得,9,；一方受贿，一方不受贿，则分别为,2,，,3,。,得益矩阵？,高薪养廉的得益矩阵,9,9,8,0,0,8,7,7,9,9,3,0,0,3,2,2,甲,受,贿,不,受,贿,受贿 不受贿,受,贿,不,受,贿,受贿 不受贿,乙,乙,甲,完全信息静态博弈,完全信息：各博弈方都完全了解所有博弈方各种情况下得益,静态：博弈方是同时决策的，或者虽然各博弈方决策的时间不一定真正一致，但他们在做决策时互相不知道其他博弈方的策略。,完全信息静态博弈：各博弈方同时决策，且所有博弈方对各方得益都了解的博弈。,如何求这一类博弈的解呢？博弈的结果如何？博弈各方最终的策略组合？,上策均衡法,上策均衡：一个博弈的某个策略组合中的所有策略都是各个博弈方各自的上策,上策：不管其它博弈方选择什么策略，一博弈方的某个策略给他带来的得益始终高于其它的策略，至少不低于其他策略的策略,囚徒的困境中的“坦白”；双寡头削价中“低价”。,上策均衡反应了所有方的绝对偏好，因此是非常稳定，可以作出最肯定的预测。,上策均衡不是普遍存在的，所以该方法失效,失效原因：,-3,，,-3,0,，,-6,-6,，,0,-1,，,-1,坦 白,不坦白,坦 白,不坦白,两个罪犯的得益矩阵,囚徒,2,囚,徒,1,严格下策反复消去法,严格下策：不管其它博弈方的策略如何变化，给一个博弈方带来的收益总是比另一种策略给他带来的收益小的策略,思路：,任何理性的博弈方都不可能选择严格下策,把不可能选择的严格下策先排除掉排除法，从而留下较好的策略,做法：,首先找出某博弈人的严格下策，把这个严格下策剔除后，剩下的是一个不包含已剔除劣策略的新的博弈；然后再剔除这个新的博弈中的严格下策；继续这个过程，直到没有劣策略存在。如果剩下的策略组合是唯一的，这个唯一的策略组合就是严格下策反复消去法的均衡,严格下策反复消去法,1,，,0,1,，,3,0,，,1,0,，,4,0,，,2,2,，,0,左,中,右,上,下,1,，,0,1,，,3,0,，,4,0,，,2,左,中,1,，,0,1,，,3,左,中,严格下策反复消去法,智猪博弈,按,等待,按,等待,5,，,1,4,，,4,9,，,1,0,，,0,大,猪,小 猪,严格下策反复消去法,适用面：,严格下策反复消去法的适用面比上策均衡要更大些,但也有很多博弈问题没有严格下策：田忌赛马、猜硬币、情侣博弈、交通博弈、石头剪刀布、此时，该方法失效。,最大的用处：简化博弈,失效原因,不同策略之间没有绝对的优劣，而只存在相对的、有条件的优劣,划 线 法,思路：,以策略之间的相对优劣关系，而不是绝对优劣关系为基础,先找出自己针对其他博弈方每种策略或策略组合（多人博弈）的最佳对策，然后在此基础上，通过对其他博弈方策略选择的判断，预测可能的结果和确定自己的最优策略,只有，两方均被划线的策略组合，才是稳定的策略表明给定一方采用该策略组合中的策略，则另一方也愿意采用该策略组合中的策略，该策略组合具有稳定性。,但是，许多博弈根本不不存在确定性的结果，划线法失效，比如猜硬币没有一个策略组合是双方同时愿意接受的，这样的博弈根本不可能有可以预言的博弈结果,也有时：情侣博弈中，用划线法有两个策略组合同时下面划线，这意味着两个策略组合中的双方策略都是对对方策略的最佳对策都具有内在的稳定性但具体那一个会出现，无法确定。,划线法,1,，,0,1,，,3,0,，,1,0,，,4,0,，,2,2,，,0,-5,，,-5,0,，,-8,-8,，,0,-1,，,-1,囚,徒,困,境,-1,，,1,1,，,-1,1,，,-1,-1,，,1,猜,硬,币,2,，,1,0,，,0,0,，,0,1,，,3,情,侣,博,弈,课堂习题,用划线法求出均衡解,C1,C2,C3,R1,R2,R3,0,，,4,4,，,0,5,，,3,4,，,0,0,，,4,5,，,3,3,，,5,3,，,5,6,，,6,箭 头 法,思路：,对博弈中的每一个策略组合进行分析，考察在每个策略组合处各个博弈方能否通过单独改变自己的策略而增加得益,与划线法一样都是基于策略之间的相对优劣关系进行分析的，所得到的结果也是一致的。,如果能，则从所分析的策略组合对应的得益数组引一箭头，到改变策略后策略组合对应的得益数组,最后，只有指向，没有离开的策略组合为均衡解稳定没有人愿意单独改变,箭 头 法,1,，,0,1,，,3,0,，,1,0,，,4,0,，,2,2,，,0,-3,-3,0,，,-6,-6,，,0,-1,，,-1,囚,徒,困,境,-1,，,1,1,，,-1,1,，,-1,-1,，,1,猜,硬,币,2,，,1,0,，,0,0,，,0,1,，,3,情,侣,博,弈,纳什均衡的定义,纳什均衡：所有参与人的最优策略的组合给定该策略中 别人的选择，没有人有积极性改变自己的选择。,策略空间：,博弈方 的第 个策略：,博弈方 的得益：,博弈：,纳什均衡：在博弈 中，如果由各个博弈方的各一个策略组成的某个策略组合 中，任一博弈方 的策略，都是对其余博弈方策略的组合,的最佳对策，也即 对任意 都成立，则称 为 的一个纳什均衡,纳什均衡的一致预测性质,一致预测：,如果所有博弈方都预测一个特定博弈结果会出现，所有博弈方都不会利用该预测或者这种预测能力，选择与预测结果不一致的策略，即没有哪个博弈方有偏离这个预测结果的愿望，因此预测结果会成为博弈的最终结果,稳定的和自我强制的，所以是真正可预测的,反之，不具有一致预测性的博弈结果，则难以避免预测和行为之间的矛盾，甚至是自我否定的。,只有纳什均衡才具有一致预测的性质,一致预测性是纳什均衡的本质属性,一致预测并不意味着一定能准确预测，因为有多重均衡，预测不一致的可能,寻找纳什均衡,C1,C2,C3,R1,R2,R3,100,，,100,0,，,0,50,，,101,50,，,0,1,，,1,60,，,0,0,，,300,0,，,0,200,，,200,纳什均衡：举例,广告博弈,纳什均衡：（做广告，做广告）,企业,1,企业,2,上次的作业,画出田忌赛马的得益矩阵,画出猜硬币博弈的得益矩阵,画出石头、剪子、布的得益矩阵,能否用我们今天的几种方法得到均衡解？,你觉得它们的最佳应对策略是什么？,严格竞争博弈和混合策略的引进,一、猜硬币博弈,-1,，,1,1,，,-1,1,，,-1,-1,，,1,正 面,反 面,猜硬币方,盖,硬,币,方,正 面,反 面,（,1,）不存在前面定义的纳什均衡策略组合,（,2,）关键是不能让对方猜到自己策略保持随机性,这类博弈很多，引出混合策略纳什均衡概念,混合策略、混合策略博弈 和混合策略纳什均衡,混合策略,：在博弈 中，博弈方 的策略空间为 ，则博弈方 以概率分布,随机在其 个可选策略中选择的“策略”，称为一个“混合策略”，其中 对 都成立，且,混合策略扩展博弈,：博弈方在混合策略的策略空间（概率分布空间）的选择看作一个博弈，就是原博弈的“混合策略扩展博弈）,混合策略纳什均衡,：包含混合策略的策略组合，构成纳什均衡,任何博弈一方单独改变自己的策略，或者随机选择各个纯策略的概率分布，都不能给自己增加任何利益,求混合策略纳什均衡,思路：,各个博弈方选择的纯策略的概率分布，要求满足使对方或其他博弈方采用不同策略的期望收益相同,一个例子,该博弈无纯策略纳什均衡，可用混合策略纳什均衡分析,博弈方,1,的混合策略,博弈方,2,的混合策略,2,，,3,5,，,2,3,，,1,1,，,5,C,D,A,B,博弈方,2,博,弈,方,1,策略 得益,博弈方,1,（,0.8,，,0.2,）,2.6,博弈方,2,（,0.8,，,0.2,）,2.6,p,A,+p,B,=1;p,C,+p,D,=1,齐威王田忌赛马,3,，,-3,1,，,-1,1,，,-1,1,，,-1,-1,，,1,1,，,-1,1,，,-1,3,，,-3,1,，,-1,1,，,-1,1,，,-1,-1,，,1,1,，,-1,-1,，,1,3,，,-3,1,，,-1,1,，,-1,1,，,-1,-1,，,1,1,，,-1,1,，,-1,3,，,-3,1,，,-1,1,，,-1,1,，,-1,1,，,-1,1,，,-1,-1,，,1,3,，,-3,1,，,-1,1,，,-1,1,，,-1,-1,，,1,1,，,-1,1,，,-1,3,，,-3,上中下,上下中,中上下,中下上,下上中,下中上,上,中,下,上,下,中,中,上,下,中,下,上,下,上,中,下,中,上,田 忌,齐,威,王,得益矩阵,Pa,Pb,Pc,Pd,Pe,Pf,Pg ph pi pj pk pl,多重均衡博弈和混合策略,情侣博弈的混合策略纳什均衡,2,，,1,0,，,0,0,，,0,1,，,3,时 装,足 球,时装,足球,丈 夫,妻,子,夫妻之争,妻子的混合策略,丈夫的混合策略,夫妻之争博弈的混合策略纳什均衡,策略 得益,妻子,（,0.75,，,0.25,）,0.67,丈夫,（,1/3,，,2/3,）,0.75,制式问题,1,，,3,0,，,0,0,，,0,2,，,2,A,B,A,B,厂商,2,厂,商,1,制式问题,制式问题混合策略纳什均衡,A B,得益,厂商,1,：,0.4 0.6 0.664,厂商,2,：,0.67 0.33 1.296,混合策略和严格下策反复消去法,在包括混合策略的情况下，关于严格下策反复消去法的结论仍然成立,即任何一方都不会采用任何严格下策，不管它们是纯策略还是混合策略,严格下策反复消去法不会消去任何纳什均衡，包括纯策略和混合策略,如果经过反复消去后留下的策略组合是唯一的，那么一定是纳什均衡,混合策略和严格下策反复消去法,3,，,1,0,，,2,0,，,2,3,，,3,1,，,3,1,，,1,L,R,U,M,D,博弈方,2,博,弈,方,1,博弈方,2,采用纯策略,L,时，博弈方,1,采用混合策略,(1/2,1/2,0),的得益,博弈方,2,采用纯策略,R,时，博弈方,1,采用混合策略,(1/2,1/2,0),的得益,混合策略反应函数,反应函数：一博弈方对另一博弈方每种可能的决策内容的最佳反应决策构成的函数,-1,，,1,1,，,-1,1,，,-1,-1,，,1,正 面,反 面,猜硬币方,正面,反面,猜硬币博弈,盖,硬,币,方,(r,1-r),：盖硬币方选择正反面的混合策略概率分布,(q,1-q),：猜硬币方选择正反面的混合策略概率分布,则,盖币方的期望支付为：,2r(1-2q)+(2q-1),猜币方的期望支付为：,2q(2r-1)-(2r-1),猜硬币博弈,r,q,1,1,1/2,1/2,盖币方的反应函数：,0,如果,q1/2,r=0,，,1,如果,q=1/2,1,如果,q1/2,q=0,，,1,如果,r=1/2,0,如果,r1/2,情侣博弈,2,，,1,0,，,0,0,，,0,1,，,3,时装,足球,丈夫,时装,足球,妻,子,夫妻之争,r,q,1,1,1/3,3/4,(r,1-r),：妻子的混合策略概率分布,(q,1-q),：丈夫的混合策略概率分布,纳什均衡的选择和分析方法扩展,多重纳什均衡博弈的分析,共谋和防共谋均衡,多重纳什均衡博弈的分析,帕累托上策均衡,风险上策均衡,聚点均衡,相关均衡,一、帕累托上策均衡,（鹰鸽博弈）,这个博弈中有两个纯策略,纳什均衡，（战争，战争）,和（和平，和平），显然,后者帕累托优于前者，所,以，（和平，和平）是本,博弈的一个帕累托上策均衡。,-5,，,-5,-10,，,8,8,，,-10,10,，,10,战争,和平,国家,2,战争,和平,国,家,1,战争与和平,二、风险上策均衡,考虑、顾忌博弈方、其他博弈方可能发生错误等时，帕累托上策均衡并不一定是最优选择，需要考虑：风险上策均衡。下面就是两个例子。,9,，,9,8,，,0,0,，,8,7,，,7,L,R,博弈方,2,U,D,博,弈,方,1,风险上策均衡（,D,，,R,）,5,，,5,3,，,0,0,，,3,3,，,3,鹿,兔子,猎人,2,鹿,兔子,猎,人,1,猎鹿博弈,风险上策均衡（兔子，兔子）,三、聚点均衡,利用博弈设定以外的信息和依据选择的均衡,文化、习惯或者其他各种特征都可能是聚点均衡的依据,城市博弈（城市分组相同）、时间博弈（报出相同的时间）是聚点均衡的典型例子,实验：城市博弈,规则：由两个人各自独立将上海、南京、长春、哈尔滨四个城市分为2组（每组 两个城市），若两人分法相同则各得100元，否则没有奖金。,一、多人博弈中的共谋问题,本博弈的纯策略纳什均衡：（,U,，,L,，,A,）、（,D,，,R,，,B,）,前者帕累托优于后者。博弈的结果会是什么呢？,（,U,，,L,，,A,）,有,共谋,(Coalition),问题：博弈方,1,和,2,同时偏离。,0,0,10,-5,-5,0,-5,-5,0,1,1,-5,L,R,U,D,博弈方,2,博,弈,方,1,博弈方,3A,-2,-2,0,-5,-5,0,-5,-5,0,-1,-1,5,L,R,U,D,博弈方,2,博,弈,方,1,博弈方,3B,共谋和防共谋均衡,二、防共谋均衡,如果一个博弈的某个策略组合满足下列要求：,（,1,）没有任何单个博弈方的“串通”会改变博弈的结果，即单独改变策略无利可图；,（,2,）给定选择偏离的博弈方有再次偏离的自由时，没有任何两个博弈方的串通会改变博弈的结果；,（,3,）依此类推，直到所有博弈方都参加的串通也不会改变博弈的结果。,称为“防共谋均衡”。,前面例子中：（,D,，,R,，,B,）是防共谋均衡,（,U,，,L,，,A,）不是防共谋均衡,杂货铺定位,设想有一个小居民点，居民住宅沿着一条公路均匀地排开。虽然在珠江三角洲都市化过程中这种沿公路修房子的做法理所应当受到批评，但是在一些比较偏僻的小地方，居民住宅沿道路排列的情况还算正常，至少可以说比较自然。现在设想有两家杂货铺要在这个小居民点开张，他们卖一样的东西，价格也完全一样。那么，两家杂货店开在什么地方好呢？,麦当劳与肯德鸡位置关系,摊贩为什么都往市场门口挤？,学校门口等出租车的争先行为,麦当劳与肯德鸡位置关系,囚徒困境博弈的思考,合作,不合作,合作,不合作,T,，,T,S,，,R,R,，,S,P,，,P,1,。满足什么条件，才是囚徒困境？,2,。采取什么手段能改变低效率结局？,