博弈论完全信息静态博弈.ppt

知彼知己，百战不殆,摘自孙子兵法,完全信息静态博弈概念,各参与人对彼此的策略集、支付函数有准确了解博弈行为同时进行一些实例石头、剪子、布游戏彼此了解的两个厂商的价格战,完全信息静态博弈概念,有些实际博弈虽然决策不是在绝对时间意义上的“同时”但决策的时间先后差别跟博弈结果没有关系，也可看成是“同时进行的博弈”。如不同竞标单位作出的工程投标决策,纳什均衡(NashEquilibrium),定义。对于一个策略式表述的博弈G=N,Si,ui,iN。称策略组合s*=(s1,si,sn)是一个纳什均衡，如果对于每一个iN,si*是给定其他参与人选择s-i*=s1*,si-1*,si+1*,sn*情况下参与人i的最优策略（经济理性策略），即：ui(si*,s-i*)ui(si,s-i*),对于任意的siSi,任意的iN均成立。,一类简单的纳什均衡求解方法划线法一个抽象例子，见表图1-8,图1-8,纳什均衡(NashEquilibrium),先考虑A，当B分别采用策略L,C,R时，A的最优策略分别为M,U,D,图1-8,纳什均衡(NashEquilibrium),同理，当A分别采用U,M,D时，B的最优策略分别为注意两个元素都标有横杆的格子，对应的策略为纳什均衡（为什么？）,图1-8,纳什均衡(NashEquilibrium),纳什均衡(NashEquilibrium),纳什均衡、占优均衡、重复剔除严劣策略均衡的关系定理a每一个占优均衡、重复剔除严劣策略均衡一定是纳什均衡，但反过来不一定成立；定理b纳什均衡一定不能通过重复剔除严劣策略方法剔除。,纳什均衡的一致预测性质一致预测性：如果所有参与人都预测一个特定的博弈结果会出现，那么所有的参与人都没有偏离这个结果的愿望，这个预测结果最终将成为博弈的结果。纳什均衡具有一致预测性质。,纳什均衡(NashEquilibrium),纳什均衡应用举例：古诺模型,这里考虑连续形式的古诺模型两个企业，分别表示为企业1、企业2每个企业的策略是选择产量（用qi表示），支付是利润（用i表示），它是两个企业产量的函数，生产成本与产量有关，用Ci(qi)表示，市场出清价格为P=P(q1+q2)第i个企业的利润函数为：i=qiP(q1+q2)Ci(qi),i=1,2,（q1*,q2*）是均衡产量意味着：q1*argmax1(q1,q2*)q2*argmax2(q1*,q2)根据上面两个式子可以得出反应函数(reactionfunction)：q1*=R1(q2)q2*=R2(q1)两个反应函数的交叉点就是纳什均衡（q1*,q2*），见图1-9,纳什均衡应用举例：古诺模型,q2,q1,图1-9古诺模型的纳什均衡,NE,纳什均衡应用举例：古诺模型,R2,R1,纳什均衡应用举例：古诺模型,实际验证假定每个企业具有相同的不变单位成本，即C1(q1)=q1c,C2(q2)=q2c，价格出清函数取线性形式：P=a-(q1+q2)。根据q1*argmax1(q1,q2*)=q1P(q1+q2*)C1(q1)q2*argmax2(q1*,q2)=q2P(q1*+q2)C2(q2)通过求一阶导数，得,于是可得到反应函数为：,纳什均衡应用举例：古诺模型,纳什均衡应用举例：古诺模型,进而可以得出每个企业的纳什均衡产量下的利润，为,可以同垄断企业的最优决策类比,纳什均衡应用举例：古诺模型,垄断条件下的最优产量，可通过计算Q*argmax=Q*(a-Q*-c)求出最优的产量值,垄断条件下的最优利润为,最优纳什均衡总产量,最优纳什均衡利润总和,纳什均衡应用举例：古诺模型,古诺模型的启示寡头竞争的总产量大于垄断竞争产量的原因在于每个企业在选择自己的最优产量时，只考虑对本企业利润的影响，而忽视对另一个企业的外部负效应。这是一个典型的囚徒困境从另一个层面我们也了解到为什么国外有反垄断法，为什么有AT当GGmax时，v(G)=0。当草地上的羊很少时，增加一只羊也许不会对其他羊的价值有太大的不利影响，但随着饲养量的不断增加，每只羊的价值会急剧下降，因此假定：,可用图1-10描述这个特征,GmaxG,v,图1-10每只羊的价值随饲养总量的增加而下降曲线,公共地悲剧,均衡分析在该博弈中，每个农民的问题是选择gi以最大化自己的利润。假定购买一只羊羔的价格为c，那么利润函数为,公共地悲剧,公共地悲剧,最优化一阶条件为,该式表明，对于每个农民来说，增加一只羊有正负两方面效用,将上面n个式子相加，在同时除以n，得,公共地悲剧,整个社会的最优化饲养量，用G*表示，为,一阶最优化条件为,公共地悲剧,比较上面两个式子，可推出GG*.,反证法假设GG*,那么由于v0，因此v(G)v(G*)。类似的，由于v0,又可推出0v(G)v(G*)。另外，从GG*还可推出G/nG*,最后要价仲裁,许多公共部门的职工是不允许罢工的，这时有关工资的分歧通过具有约束力的仲裁解决。较为重要的仲裁形式有两类：协议仲裁和最后要价仲裁。在最后要价仲裁中，争议双方各自就工资水平要价，仲裁人选择其中之一作为仲裁结果；在协议仲裁中，仲裁人可自由选定任意工资水平作为仲裁结果。本例根据法伯（1982）的研究，导出在最后要价仲裁模型处于纳什均衡时，博弈双方对工资水平的要价。,最后要价仲裁,最后要价仲裁,最后要价仲裁,博弈论在实际中应用的一般分析框架,描述实际问题问题问题本身的描述（文字、图表为主）用数学模型描述描述合理易于处理,博弈论在实际中应用的一般分析框架,选择合适博弈模型完全信息静态博弈完全信息动态博弈合作博弈等等,博弈论在实际中应用的一般分析框架,描述博弈基本要素，如参与人参与人策略集各参与人的效用函数等等,博弈论在实际中应用的一般分析框架,博弈的均衡分析纳什均衡分析（纳什均衡与博弈结果的预测）一些相关分析（数学的、经济的、业内的）分析结果的“翻译”结论,前面介绍的纳什均衡分析方法对于相当多一类博弈问题无能为力。如图1-11的猜硬币博弈，不存在已经定义的各种均衡,图1-11猜硬币博弈,混合策略的提出,混合策略的提出,利用生活经验不难知道，若硬币是均匀的，以0.5的概率去猜测正面无疑是最佳决策这就引出了用概率来确定采用何种策略的方法，这就是混合策略(mixedstrategies)概念的由来在此之前所说的策略，实质上是以概率1选取某个确定的策略或行动，我们称之为纯策略(purestrategies),混合策略的提出,混合策略的定义：在博弈G=N,Si,ui,iN中，假设参与人i的纯策略构成的策略集合为Si=si1,sik，若参与人i以概率分布pi=(pi1,pik)在其k个可选策略中随机选择“策略”，称这样的选择方式为混合策略。这里，0pij1,对于j=1,k都成立，且有:pi1+pik=1纯策略可看成特殊的混合策略上述定义是在有限博弈前提下进行的,混合策略意义下的相关表述,混合策略意义下策略组合的表述x1X1,xnXn，其中Xi,i=1,n表示参与人i所有纯策略生成的概率空间，xi为参与人i的一个具体混合策略猜硬币博弈的一个混合策略就可记为（1/2,1/2）,(1/2,1/2)混合策略意义下支付函数如何表述？,预备知识关于风险结果的偏好,基本概念Lotteries（风险结果）.由机会点和该机会点发出的n个机会枝的概率及相应后果构成的结构称为lottery（抽奖，意译为风险结果）。一个风险结果可以表示为L=(p1,a1;pn,an)若确定性结果ci是众所周知的事实，风险结果也可以简记为L=(p1,pn),预备知识关于风险结果的偏好,若对前面介绍的效用理论进行概括仅满足序关系的效用为序数效用理论用支付函数表示的效用关系，采用的是基数效用理论上述两类关于确定性结果的偏好理论，无法描述决策者对不同风险结果的偏好程度,预备知识关于风险结果的偏好,针对风险结果的偏好，在一些相对合理假设的基础上，可以给出用以描述风险结果的支付函数用数学形式表述，就是说U是一个支付函数，满足U(p1,pK)U(p1,pK)当且仅当(ifandonlyif)某个决策者偏好(p1,pK)的程度高于(p1,pK),预备知识关于风险结果的偏好,描述关于风险结果的标准方法，是由博弈论的奠基人vonNeumann和Morgenstern，通过一系列独立性公理(independenceaxiom)，得出的期望效用函数或期望支付函数。详见文献4:713这些独立性公理，保证了通过确定性结果的支付函数u，推出决策者关于风险结果的偏好，可以用期望支付来表示。理性决策者选择风险结果的依据是期望支付的最大化,预备知识关于风险结果的偏好,简例对于两个风险结果(1/2,0;0,1;1/2,5)和(1/2,0;3/4,1;1/4,5)如果决策者更加偏好前者，则可用v-N-M效用表示上述偏好关系比如，令u(0)=0,u(1)=1,u(5)=4很容易验算这样定义的效用，满足风险结果偏好与期望效用的一致性,再谈混合策略,若允许每个参与人选择混合策略，则博弈结果就是一个关于纯策略组合得来一个风险结果为研究参与人行为，需要知道各参与人对这些风险结果的偏好关系博弈论假定每个参与人的偏好关系，可用期望支付函数表示。,再谈混合策略,于是可以定义基于混合策略意义下的博弈策略式表述定义基于(v-N-M效用的)策略式博弈由参与人集合每个参与人有一个（纯）策略集合对于每一个参与人来说，由所有参与人纯策略组合构成的风险结果空间，存在一个v-N-M效用,混合策略意义下的纳什均衡,定义，对于博弈G=N,Si,ui,iN，基于v-N-M效用的混合策略组合*是一个纳什均衡，若对于每一个i,以及i的任意一个混合策略i，*对应的期望支付至少和(i，*-i)的期望支付一样大,混合策略意义下的纳什均衡,换句话说，称混合策略组合*是一个纳什均衡，如果没有一个参与人通过偏离策略*i实现支付的增加可用数学形式简洁地写出（文科学生请练习）,一个定理,对于N-人静态博弈问题，设混合策略纳什均衡对应的策略组合为(Xi,Xi)。对于任意的i,若最优混合策略为Xi=x1,xl，00(不失一般性，假设前l个分量严格大于0)，记分量xk(k=1,l)对应的纯策略sk,则对于参与人i而言，sk与其他参与人的最优混合策略组合Xi形成的局势的支付值,等于纳什均衡混合策略组合(Xi,Xi)的支付值。即ui(sk,Xi)=ui(Xi,Xi)成立，k=1,l,一个算例,简单博弈，见图1-12先用划线法确定参与人1、2针对对手各纯策略下的最优纯策略反应。显然没有纯策略意义下的纳什均衡。,图1-12二人博弈,是否存在混合策略意义下的纳什均衡？,一个算例,设参与人1分别以pA、pB概率选择纯策略A和B根据前面介绍的关于混合策略纳什均衡定理参与人1以混合策略(pA、pB)与参与人2的纯策略C,D进行博弈时，相应支付值相等（为什么？）,图1-12二人博弈,一个算例,于是有,图1-12二人博弈,又根据,可以求出,一个算例,同理可求出参与人2的最优混合策略,图1-12二人博弈,在这样的混合策略组合下，参与人1相应的期望支付值为,一对夫妻要决定去看时装表演还是看足球赛。有关纯策略及相应支付情况如图1-13所示。,图1-13性别战博弈,性别战,性别战,纯策略均衡可通过划线法计算得出，为(时装，时装)，（足球，足球），支付值分别为（2,1）,(1,3)该博弈还有一个混合策略均衡,图1-13性别战,性别战,设pw（C）和pw(F)分别是妻子选择时装表演和足球的概率，ph(C)和ph(F)是丈夫选择时装表演和足球赛的概率。经计算，可得,图1-13性别战,性别战,当采用上面混合策略时，可以算出丈夫和妻子的收益期望，分别为,图1-13性别战,可以看出，该结果明显不如夫妻双方能交流协商,性别战变体1：制式问题,电器和电子设备往往有不同的原理或相关技术标准，通常称为制式图1-4就是一个2厂商的制式博弈模型该模型存在两个纯策略均衡，以及一个混合策略均衡,图1-14制式问题,性别战变体1：制式问题,纯策略均衡为（制式1，制式1）、（制式2、制式2）混合策略均衡为(0.4,0.6),(0.67,0.33)相应支付值分别为0.664和1.296,图1-14制式问题,性别战变体2：市场机会博弈,两个厂商同时发现一个市场机会，但这个市场容量并不大。如果只有一个厂商进入该市场，能赚到100个单位的利润，但如果两个厂商同时进入该市场，则他们不仅赚不到钱，而且要各亏损50单位。如果这两个厂商事先没有沟通和协商，就会出现如图1-15的博弈问题。,图1-15市场机会,性别战变体2：市场机会博弈,本博弈有（进入，不进入）、（不进入，进入）两个纯策略均衡，其中前一个均衡对厂商1有利，第二个均衡对厂商2有利此外，还有一个混合策略均衡，为(2/3,1/3),(2/3,1/3)期望支付均为0。,图1-15市场机会,性别战变体2：市场机会博弈,可以把混合策略(2/3,1/3),(2/3,1/3)解释为：约有2/3比例的厂商选择进入，1/3比例的厂商选择不进入,图1-15市场机会,22双矩阵博弈的图解法,双矩阵的含义以性别战为例，介绍22双矩阵博弈模型的图解法为便于说明，将性别战模型再次复制与此,一对夫妻要决定去看时装表演还是看足球赛。有关纯策略及相应支付情况如图1-16所示设妻子的混合策略为(r,1-r)，丈夫的策略为(q,1-q)。这里的r,q分别表示妻子或丈夫观看时装表演的概率为便于分析，将混合策略列于右上角,图1-16性别战,(r,1-r),(q,1-q),22双矩阵博弈的图解法,若丈夫以q的概率选择去看时装表演（以1-q的概率去看足球），则妻子选择时装和观看足球的期望收益分别为,图1-16性别战,(r,1-r),(q,1-q),22双矩阵博弈的图解法,比较1与2可知当q1/3时，则选择看时装表演,图1-16性别战,(r,1-r),(q,1-q),22双矩阵博弈的图解法,上述情况反映了妻子针对丈夫不同策略下的最佳反应，称为（妻子的）反应函数.,r,q,01/31图1-17妻子的反应函数,1,r=R1(q),可用图1-17表示妻子的反应函数,22双矩阵博弈的图解法,同理，可绘出丈夫的反应函数，见图1-18,r,q,01/31图1-18丈夫的反应函数,1,q=R2(r),3/4,22双矩阵博弈的图解法,r,q,01/31图1-17妻子的反应函数,1,r,q,01/31图1-18丈夫的反应函数,1,r=R1(q),q=R2(r),3/4,22双矩阵博弈的图解法,将这两张图合并，得到图1-19,r,q,01/31图1-19性别战的图解法,1,q,r=R1(q),q=R2(r),3/4,按照纳什均衡的定义，图上的三个交点既是参与人1的最优反应函数上的点，同时也是参与人2最优反应函数上的点,22双矩阵博弈的图解法,r,q,01/31图1-19性别战的图解法,1,q,r=R1(q),q=R2(r),3/4,这三个点的坐标为(0,0),(1/3,3/4),（1,1）。对应的三个策略分别是：（足球,足球）；妻子、丈夫分别以1/3、3/4的概率选择时装；（时装,时装）。,22双矩阵博弈的图解法,纳什于1950年提出并证明了纳什定理纳什定理的主要内容为：在一个有n个参与人的策略式博弈G=S1,Sn;u1,un中，如果n是有限的，且Si是有限集（i=1,n），则该博弈至少存在一个纳什均衡（在混合策略意义下）,纳什定理,纳什定理的一些说明,纳什定理的证明要用到不动点定理。所谓不动点定理，是指一个定义在XX上的函数f(x)，集合X是非空的、闭的、有界的和凸的函数f是连续的则至少存在一个x，使得f(x)=x,x被称为不动点,纳什定理的一些说明,不动点的图形解释见下图,纳什定理的一些说明,如果映射是不连续的，不动点就不一定存在,纳什定理的一些说明,映射选择的是n人最优反应对应其含义是，对于任意一个混合策略组合(p1,pn)，对于每一个参与人i，求出I针对其他参与人混合策略(p1,pi-1,pi+1,pn)的最优反应，然后构建n个参与人最优反应对应的笛卡尔积。一个最优混合策略组合就是这一对应集的不动点。,纳什定理的一些说明,因此只要证明前面的最优反应对应满足不动点定理条件就可以了。,多重纳什均衡解及其分析,纳什定理说明了纳什均衡在相当广泛的博弈模型中普遍存在但是纳什均衡只是理论模型的导出结果，其适用性存在一定局限纳什均衡的理论基础：如经济理性、决策准则一致性、共同知识等并不能涵盖现实行为（互惠性、利他性、不理性等）,多重纳什均衡解及其分析,帕雷托占优均衡帕雷托占优均衡的含义是：在多个纳什均衡中，若存在一个纳什均衡，其支付结果针对每个参与人而言都严格优于其它纳什均衡，则该纳什均衡是帕雷托占优纳什均衡。,一个战争与和平的博弈简例，见图1-20。该博弈有两个纯策略均衡（战争，战争），（和平，和平）。（和平，和平）在帕雷托占优意义上是较好的一个均衡策略。,图1-20帕雷托占优均衡,多重纳什均衡解及其分析,风险占优均衡(risk-dominantequilibrium)以图1-21为例该博弈有两个纯策略均衡（U，L）和（D，R）。显然，在帕雷托占优意义下，(U,L)要优于(D,R)。,图1-21风险占优均衡,多重纳什均衡解及其分析,但进一步分析不难发现，若参与人1选择策略U,万一参与人2选择策略R，参与人2损失只有1单位，但对于参与人1来说只能得到支付0。也就是说，策略U对于参与人1来说是风险较大的策略。,图1-21风险占优均衡,多重纳什均衡解及其分析,而另一个纯策略组合(D,R)则是风险占优的许多博弈实验研究表明，实际中，人们更愿意选择风险占优均衡,图1-21风险占优均衡,多重纳什均衡解及其分析,多重纳什均衡解及其分析,一个经典博弈问题：StagHunt两个人同时发现1头鹿和2只兔子，如果两人合力抓鹿，则可以把这头价值10单位的鹿抓住，兔子则跑掉；如果两个人都去抓兔子，则各可以抓到1只价值3单位的兔子，鹿就会跑掉；但如果一个人选择了抓兔子而另一个人选择了抓鹿，那么选择抓兔子的能抓到1只兔子，选择抓鹿的人则一无所获。由于两人来不及商量，决策必须瞬间作出,上述问题可表示为双矩阵形式，见图1-22该博弈也存在两个纯策略纳什均衡，分别为(鹿，鹿)、（兔子，兔子）其中风险占优的均衡为（兔子，兔子），均衡收益分别为（3,3）,图1-22猎鹿博弈,多重纳什均衡解及其分析,多重纳什均衡解及其分析,风险占优均衡的进一步说明。参与人对风险占优均衡的选择倾向，有一种强化的机制。当部分或所有参与人选择风险占优均衡的可能性增强的时候，任一参与人选择帕雷托占优均衡策略的期望支付会进一步减小，而这又使得帕雷托占优均衡策略的支付更小，从而形成一种选择风险占优均衡策略的正反馈机制，并使其出现的概率越来越大。,多重纳什均衡解及其分析,当参与人数目增加时，选择合作的风险将会更大，可借助该点考虑招标机制如何减少投标方勾结问题上述问题是我们知道建立诚信机制社会的重要意义上述问题引出一个博弈相关分支为协调博弈(coordinationgame),多重纳什均衡解及其分析,聚点均衡由实际问题抽象出来的博弈模型中，更多的一类问题是：多个纳什均衡间不存在帕雷托占优关系或明显的风险占优关系，如夫妻爱好问题的两个纯策略均衡。这时如何预测哪一个纳什均衡会出现是一个很有意义的问题以夫妻爱好博弈为例，在实际中往往二人很默契地知道如何进行博弈，双方往往知道怎么进行选择策略，且能够相互了解（这里面排除了互相协商后达成的一致）,实际博弈中参与人往往会利用博弈模型以外的信息，实现对特定博弈均衡一致关注的“聚点”这些信息如：参与人共同的文化背景或规范，共同的知识，具有特定意义事物的特征，某些特殊的数量、位置关系等,多重纳什均衡解及其分析,一些可能的“聚点”，如中午与12:00的聚点；夫妻爱好博弈中“（服装，服装）”与“今天是妻子生日”的聚点；参与人中地位不一致造成的均衡向有地位方倾斜的“聚点”，等等聚点均衡确实反映了人们在多重纳什均衡选择中的某些规律性，但因为涉及因素太多，对于一般博弈模型很难总结普遍规律，只能具体问题具体分析,多重纳什均衡解及其分析,多重纳什均衡解及其分析,相关均衡(correlatedequilibrium)实际上，在现实中遇到选择困难时，特别是在长期中反复遇到相似选择难题时，常会通过收集更多信息，形成特定的机制和规则，为某种形式的制度安排等主动寻找思路。相关均衡就是这样的一种均衡选择机制。,多重纳什均衡解及其分析,图1-23的一个博弈该博弈有两个纯策略均衡，为(U,L)和(D,R)，以及一个混合策略均衡(1/2,1/2),(1/2,1/2)两个纯策略均衡能使双方得到6单位支付，但支付水平相差较大,图1-23相关均衡,多重纳什均衡解及其分析,若采用混合策略均衡(1/2,1/2),(1/2,1/2)，则有1/4概率遇到最不希望的结局(U,R)，同时双方期望支付为2.5，也不理想,图1-23相关均衡,多重纳什均衡解及其分析,若建立这样的机制：抛一枚硬币，若正面朝上参与人1采用U，参与人2采用L；出现反面参与人1采用D，参与人2采用R的规则，这样的规则排除了最不利的(U,R)组合期望收益都等于3，处于相对公平状态,图1-23相关均衡,多重纳什均衡解及其分析,进一步发展上述思路，还可以建立一个更好的博弈机制，这就是相关均衡理论对于实际中比较复杂的博弈问题，参与人是否有能力设计这种机制，并且