不完全信息博弈和贝叶斯均衡.ppt

,第三章：,不完全信息静态博弈,1,课件部分内容来源于网络，如有异议侵权的话可以联系删除，可编辑版！,主要内容：,一、不完全信息博弈和贝叶斯纳什均衡,二、贝叶斯均衡的应用,三、贝叶斯博弈与混合战略均衡,四、机制设计理论与显示原理,2,课件部分内容来源于网络，如有异议侵权的话可以联系删除，可编辑版！,第一节 不完全信息博弈和贝叶斯均衡,一、贝叶斯博弈,二、海萨尼转换,三、贝叶斯博弈的战略式描述,四、贝叶斯纳什均衡,一、贝叶斯博弈,完全信息（,complete information,）：每个参与人对其他参与人的,支付函数有准确的了解,；否则，为不完全信息（,incomplete information,）。,完美信息（,perfect information,）：在博弈过程的任何时点每个参与人都能,观察并记忆之前各局中人所选择的行动,，否则为不完美信息（,imperfect information,）。,前面两章我们讨论了完全信息博弈问题，但在现实生活中我们遇到更多的可能是不完全信息博弈问题。,例如：,在企业的新产品开发过程中，,企业对市场的需求可能并不清楚,；,在连锁店博弈中，,潜在的进入者可能并不知道连锁店在市场上的盈利情况,，等等。,像这种博弈,开始时就存在事前不确定性的博弈问题,是不完全信息博弈问题。,40,，,50,-10,，,0,30,，,80,-10,，,100,0,300,0,，,300,0,，,400,0,，,400,高成本情况 低成本情况,默许 斗争 默许 斗争,进入,不进入,进入者,在位者,市场进入博弈：不完全信息,在位者的成本有两种类型，而进入者并不知道在位者的成本类型。,显然，在这种情形下，进入者有关在位者的成本信息是不完全的。,当在位者具有不同的成本时，所表现出来的博弈情形是不同的，对应的均衡也是不一样的。,高成本情形,：,（进入，默许）（不进入，斗争）,低成本情形：,（不进入，斗争）,斗鸡博弈,两个所谓的勇士举着长枪，准备从独木桥的两端冲上桥中央进行决斗。每位勇士都有两种选择：冲上去,(,用,U,表示,),，或退下来,(,用,D,表示,),。若两人都冲上去，则两败俱伤；若一方上去而另一方退下来，冲上去者取得胜利,(,至少心理上是这样的,),，退下来的丢了面子；若两人都退下来，两人都丢面子。,存在两个纯战略,Nash,均衡,(,U,，,D,),和,(,D,，,U,),，也就是一个人冲上去，另一个就必须退下来。,当一个理性的参与人预测到对方将会冲上去时，明智的选择就是退下来；而当预测到对方将会选择退却时，就应该大胆地冲上去。,-,4,-,4,2,-,2,-,2,2,0,0,U,D,2,1,U,D,现在考虑这样的情形：假设参与人可能有这样的两种性格特征,(,类型,)“,强硬”,(,用,s,表示,),或“软弱”,(,用,w,表示,)所谓“强硬”的参与人是指那些喜欢争强好胜、不达目的誓不罢休的决斗者；而“软弱”的参与人是指那些胆小怕事、遇事希望息事宁人的决斗者。,可以想象，当具有不同性格特征的决斗者相遇时，表现出来的博弈情形将会不同。,斗鸡博弈：不完全信息,当参与人都为,强硬者,时,博弈存在两个纯战略,Nash,均衡,(,U,，,D,),和,(,D,U,),。,当参与人,1,为强硬者参与人,2,为软弱者时,博弈存在唯一的,Nash,均衡,(,U,D,),。,当参与人,1,为软弱者参与人,2,为强硬者时,博弈存在唯一的,Nash,均衡,(,D,U,),。,当参与人都为软弱者时,博弈存在唯一的,Nash,均衡,(,D,D),。,(1),参与人都为强硬者,(2),参与人,1,为强硬者参与人,2,为软弱者,(3),参与人,1,为软弱者参与人,2,为强硬者,(4),参与人都为软弱者,强硬 软弱,U D U D,1,2,1,，,1,0,，,0,1,，,0,0,，,2,0,，,0,-4,，,-4,0,，,-2,-4,，,-4,0,，,1,-2,，,0,0,，,0,-2,，,2,2,，,0,-4,，,-4,2,，,-2,-4,，,-4,U,D,U,D,强硬,软弱,斗鸡博弈：不完全信息,在“斗鸡博弈”中，虽然在博弈开始之前每位决斗者都知道自己的性格特征，但对对手的性格特征往往不甚了解。,在这种情况下即使所有的决斗者都看到了上面的四个战略式博弈，但对决斗者来讲，,仍存在着所谓的事前不确定性，即博弈开始之前就不知道的信息,。,具体而言，这意味着当博弈真正开始的时候，对,到底体现为哪一种博弈形势,并不清楚。,对于“强硬”的参与人,1,来讲，虽然他看到了上面的战略式博弈，但他不知道对手是“强硬”的还是“软弱”的，所以博弈开始之前他无法确定博弈是根据,(1),还是,(2),进行。这意味着“强硬”的参与人,1,面临着事前无法确定的信息。,同样，“软弱”的参与人,1,也会面临类似的问题。此时，“斗鸡博弈”就是一个不完全信息博弈问题。,从这一例子来看，博弈的参与人均存在,两种不同的类型,，即强硬和软弱；,由于参与人,1,不知道对手究竟是“强硬”的还是“软弱”的，因此，此时参与人,1,就好像在与两个决斗者进行决斗，一个是“强硬”的，另一个是“软弱”的；,当一个参与人并不知道在与谁博弈时，博弈的规则是无法定义的，,如何处理不完全信息导致的这一问题？,为了解决该问题，,海萨尼,提出了,Harsanyi,转换,。,海萨尼指出，引入虚拟参与人,自然，由自然先决定参与人的不同类型，将不完全信息博弈转换为不完美信息博弈。,二、海萨尼（,Harsanyi,）转换,为了解释,Harsanyi,转换的具体含义，我们对“斗鸡博弈”进行简化。,假设,参与人,1,是“强硬”的决斗者,，参与人,2,可能是“强硬”的也可能是“软弱”的，参与人1,不知道参与人,2,的类型，但参与人,2,知道自己的类型，而且这一假设为所有的参与人所知道。,Harsanyi,转换,对于简化的“斗鸡博弈”，,Harsanyi,转换是这样处理的：在原博弈中引入一个“虚拟”的参与人,“,自然”,(nature,，用,N,表示,),，构造一个参与人为两个决斗者和“自然”的三人博弈。,Harsanyi,转换,“,自然”首先行动决定参与人,2,的性格特征,(,即选择参与人,2,是“强硬”的还是“软弱”的,),，“自然”的选择参与人,1,不知道，但参与人,2,知道。,参与人,2,的特征,在“自然”选择后，参与人,1,和,2,再进行“斗鸡博弈”。,在新构造的三人博弈中，“自然”的支付不必考虑。参与人,1,和,2,的支付由“斗鸡博弈”决定。,如果“自然”选择参与人,2,的性格特征是“强硬”的，则意味着参与人,1,与“强硬”的参与人,2,进行决斗，博弈进入决策结,x,1,，其支付由,(1),决定；,如果“自然”选择参与人,2,的性格特征是“软弱”的，则意味着参与人,1,与“软弱”的参与人,2,进行决斗，博弈进入决策结,x,2,，其支付由,(2),决定。,海萨尼,通过引入“虚拟”参与人，将博弈的起始点由,x,1,或,x,2,提前至,x,0,，从而,将原博弈中参与人的事前不确定性转变为博弈开始后的不确定性,。,这种通过引入“虚拟”参与人来处理不完全信息博弈问题的方法称为,Harsanyi,转换,。,在,Harsanyi,转换中规定：参与人关于“自然”选择的推断为共同知识。,也就是说，两个决斗者不仅同时一起看到了“自然”随机选择参与人,2,的性格特征，而且同时一起看到了“自然”以一定的概率分布随机选择参与人,2,的性格特征。,在应用,Harsanyi,转换时，需要注意以下问题：,1)“,自然”的选择。在一般的不完全信息博弈问题中，,Harsanyi,转换规定“自然”选择的是参与人的,类型,(type),。除了根据参与人的支付来划分参与人的类型以外，还可以根据参与人的行动空间，甚至根据参与人掌握信息的多少,(,或程度,),来划分参与人的类型。,用,t,i表示参与人,i,的一个特定的类型，,T,i,表示参与人,i,所有类型的集合,(,亦称类型空间，,type space),，即 ，,t,=(,t,1,t,n,),表示所有参与人的类型组合，,t,-i,=(,t,1,t,i,-1,t,n,),表示除参与人,i,之外其他参与人的类型组合。所以，,t,=(,t,i,t,-i,),。,用 表示参与人,i,在知道自己类型为,t,i,的情况下，关于其他参与人类型的推断,(,即条件概率,),，则,2),参与人关于“自然”选择的推断：,用,p,(,t,1,t,n,),表示定义在参与人类型组合上的一个联合分布概率函数。,假设,p,ss,=0.2,，,p,sw,=0.3,，,p,ws,=0.25,，,p,ww,=0.25,。,其中，,p,ss,：决斗者,1,和决斗者,2,同时强硬的概率；,p,sw,：决斗者,1,强硬、决斗者,2,软弱的概率；,p,ws,：决斗者,1,软弱、决斗者,2,强硬的概率；,p,ww,：决斗者,1,软弱、决斗者,2,软弱的概率；,虽然决斗者,1,不知道决斗者,2,的类型，但由于决斗者,1,知道自己的类型，因此他可以根据贝叶斯公式推知决斗者,2,的类型分布。,例如,根据贝叶斯规则，“强硬”的决斗者,1,可以推知：,决斗者,2,是“强硬”的概率为,决斗者,2,是“软弱”的概率为,“软弱”的决斗者,1,可以推知：,决斗者,2,是“强硬的概率为,决斗者,2,是“软弱”的概率为,不完全信息博弈：完全信息博弈在不完全信息上的拓展，我们又将其称为贝叶斯博弈；,贝叶斯博弈：静态贝叶斯博弈和动态贝叶斯博弈；,三、贝叶斯博弈的战略式描述,贝叶斯博弈的定义,贝叶斯博弈包含以下五个要素：,参与人集合 ；,参与人的类型集合,T,1,T,2,；,参与人关于其他参与人类型的推断,；,(4),参与人类型相依的行动集,A,(,t,1,),A,(,t,n,),；,(5),参与人类型相依的支付函数,。,贝叶斯博弈中的战略,在贝叶斯博弈 中，参与人,i,的一个战略是从参与人的类型集,T,i,到其行动集的一个函数,s,i,(,t,i,),；,它包含了当自然赋予,i,的类型为,t,i,时，,i,将从可行的行动集,A,i,(,t,i,),中选择的行动。,用 表示给定其他参与人的战略 ，类型为,t,i,的参与人,i,选择行动,a,i,时的期望效用，则,其中，对 ，为给定,t,-i,时由,s,-i,所确定的其他参与人的行动组合,贝叶斯博弈的时间顺序如下：,“,自然”选择参与人的类型组合,t,=(,t,1,t,n,),，其中，参与人,i,观测到“自然”关于自己类型,t,i,的选择；虽然参与人,i,观测不到“自然”关于其他参与人类型,t,-i,的选择，但参与人,i,具有关于其他参与人类型的推断 ；,参与人同时选择行动，每个参与人,i,从行动集,A,i,(,t,i,),中选择行动,a,i,(,t,i,),；,参与人,i,得到,。,“,斗鸡博弈”的贝叶斯模型,参与人为决斗者,1,和,2,；,用,s,表示决斗者是“强硬”的，,w,表示决斗者是“软弱”的，所以,T,1,=,T,2,=,s,w,。,用,p,xy,表示“自然”选择类型组合,(,x,y,),的概率，并假设,p,xy,为共同知识，则决斗者,1,关于其对手类型的推断为,p,1,(,y,|,x,),。,决斗者,1,关于类型相依的行动空间,A,1,(,x,)=,U,D,，决斗者,2,关于类型相依的行动空间,A,2,(,y,)=,U,D,。,每位决斗者,i,的支付由前面的图决定。,在贝叶斯博弈中，对于一个理性的参与人,i,，当他只知道自己的类型,t,i,而不知道其他参与人的类型时，给定其他参与人的战略,s,-i,，他将选择使自己期望效用,(,支付,),最大化的行动 ，其中,四、,贝叶斯纳什均衡,纯战略贝叶斯,Nash,均衡,贝叶斯博弈 的纯战略贝叶斯,Nash,均衡是一个类型相依的行动组合 ，其中每个参与人在给定自己的类型,t,i,和其他参与人的类型相依行动 的情况下最大化自己的期望效用。,也就是，行动组合 是一个纯战略贝叶斯,Nash,均衡，如果对 ，,贝叶斯博弈纳什均衡的存在性,定理 一个有限的贝叶斯博弈一定存在贝叶斯,Nash,均衡。,类型,1,类型,2,左 右,左 右,3,，,1,2,，,0,3,，,0,2,，,1,0,，,1,4,，,0,0,，,0,4,，,1,上 下,甲,乙,静态贝叶斯博弈均衡举例：,表中甲、乙同时行动，甲只有一种类型，但乙有两种类型：,2,=,1,，,2,；甲不了解对方是哪一种类型，但他相信对方为,1,，,2,的概率各为,1/2,。求解均衡,。,乙：如果为,1,，有占优战略为“左”；如果为,2,，有占优战略为“右”,甲：由于甲相信对方为两种类型的可能性各为,1/2,，故甲考虑选“上”和“下”分别给他带来的期望收益；,结果选“上”，期望支付为,5/2,，选“下”，期望支付为,2,，因而甲的最佳选择是“上”。,纳什均衡为,s,1,*=,上；,s,2,*1,)=,左，,s,2,*(,2,)=,右。,贝叶斯,Nash,均衡的求解：,先以简化的“斗鸡博弈”为例。,强硬 软弱,U D U D,1,2,0,，,1,-2,，,0,0,，,0,-2,，,2,2,，,0,-4,，,-4,2,，,-2,-4,，,-4,U,D,强硬,用,p,表示决斗者,1,关于决斗者,2,的类型的推断，即,决斗者,1,认为决斗者,2,为强硬的概率为,p,。,(,x,(,y,z,),：,x,表示当决斗者,2,选择该方格所对应的战略时，决斗者,1,选择该方格所对应的战略规定的行动所得到的期望支付；,y,和,z,分别表示当决斗者,1,选择该方格所对应的战略时，“强硬”决斗者,2和“软弱”决斗者,2,选择该方格所对应的战略规定的行动所得到的期望支付。,给定决斗者,1,选择战略,U,，“软弱”决斗者,2,选择行动,D,的期望支付为,0,，选择行动,U,的期望支付为,-4,，行动,D,优于行动,U,；给定决斗者,1,选择战略,D,，“软弱”决斗者,2,选择行动,D,的期望支付为,1,，选择行动,U,的期望支付为,0,，所以，行动,D,优于行动,U,。这意味着战略,U,为软弱决斗者,2,的劣战略。,-,4,-4,2,-2,-,2,2,0,0,U,2,1,U,D,-,4,-4,2,0,-,2,0,0,1,D,D,U,-,4,-4,2,-2,-,2,2,0,0,U,2,1,UD,2,，,0,D,D,0,，,1,下面根据,p,的大小，求解博弈的纯战略贝叶斯,Nash,均衡。,1),假设 ，无论决斗者,2,选择战略,(,U,D,),还是,(,D,D,),，决斗者,1,的最优行动都是,U,。给定决斗者,1,的选择,U,，“强硬”决斗者,2,的最优行动为,D,。所以，博弈存在惟一的纯战略贝叶斯,Nash,均衡,决斗者,1,选择行动,U,，“强硬”决斗者,2,选择行动,D,，“软弱”决斗者,2,选择行动,D,。,情形,1,：给定决斗者,1,认为决斗者,2,为强硬的概率为,p,2),假设 ，博弈存在如下两个纯战略贝叶斯,Nash,均衡：,(1),决斗者,1,选择行动,U,，强硬”决斗者,2,选择行动,D,，“软弱”决斗者,2,选择行动,D,；,(2),决斗者,1,选择行动,D,，“强硬”决斗者,2,选择行动,U,，“软弱”决斗者,2,选择行动,D,。,求解另一种情形下“斗鸡博弈”的 贝叶斯,Nash,均衡,强硬 软弱,U D U D,1,，,1,0,，,0,1,，,0,0,，,2,0,，,0,-4,，,-4,0,，,-2,-4,，,-4,0,，,1,-2,，,0,0,，,0,-2,，,2,2,，,0,-4,，,-4,2,，,-2,-4,，,-4,U,D,U,D,强硬,软弱,求解另一种情形下“斗鸡博弈”的 贝叶斯,Nash,均衡,假设,“强硬”决斗者,1,关于决斗者,2,的类型推断 ；,“软弱”决斗者,1,关于决斗者,2,的类型推断 ；,“强硬”决斗者,2,关于决斗者,1,的类型推断 ；,“软弱”决斗者,2,关于决斗者,1,的类型推断 ；,强硬 软弱,U D U D,1,，,1,0,，,0,1,，,0,0,，,2,0,，,0,-4,，,-4,0,，,-2,-4,，,-4,0,，,1,-2,，,0,0,，,0,-2,，,2,2,，,0,-4,，,-4,2,，,-2,-4,，,-4,U,D,U,D,强硬,软弱,强硬 软弱,U D U D,1,，,1,0,，,0,1,，,0,0,，,2,0,，,1,-2,，,0,0,，,0,-2,，,2,2,，,0,-4,4,2,，,-2,-4,，,-4,U,D,D,强硬,软弱,强硬 软弱,U D U D,1,，,1,0,，,0,1,，,0,0,，,2,0,，,1,-2,，,0,0,，,0,-2,，,2,2,，,0,-4,，,-4,2,，,-2,-4,，,-4,U,D,D,强硬,软弱,强硬 软弱,U D D,1,，,1,1,，,0,0,，,2,0,，,1,0,，,0,-2,，,2,2,，,0,2,，,-2,-4,，,-4,U,D,D,强硬,软弱,强硬 软弱,U D D,1,，,1,1,，,0,0,，,2,0,，,1,0,，,0,-2,，,2,2,，,0,2,，,-2,-4,，,-4,U,D,D,强硬,软弱强硬 软弱,U D D,1,，,1,1,，,0,0,，,2,2,，,0,2,，,-2,-4,，,-4,U,D,强硬,软弱,U,是强硬的决斗者,1,的占优策略,强硬 软弱,U D D,1,，,1,1,，,0,0,，,2,0,，,1,0,，,0,-2,，,2,2,，,0,2,，,-2,-4,，,-4,U,D,D,强硬,软弱,对于强硬的决斗者,1,而言，有,因此，,U,是强硬的决斗者,1,的占优策略。,强硬 软弱,U D D,1,，,1,1,，,0,0,，,2,2,，,0,2,，,-2,-4,，,-4,U,D,强硬,软弱,因此，强硬的决斗者,2,选择,U,和,D,无差别。,对于强硬的决斗者,2,而言，有,所以，该博弈存在如下两个纯战略,Nash,均衡：,“强硬”的决斗者,1,选择行动,U,，“软弱”的决斗者,1,选择行动,D,；“强硬”的决斗者,2,选择行动,U,，“软弱”的决斗者,2,选择行动,D,。,“强硬”的决斗者,1,选择行动,U,，“软弱”的决斗者,1,选择行动,D,；“强硬”的决斗者,2,和“软弱”的决斗者,2,选择行动,D,。,