混合策略纳什均衡

博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,博弈论 第三章 混合策略纳什均衡,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二节 混合策略纳什均衡的求解方法,二、支付最大化法,例：扑克牌对色游戏,(p,77,),无纯策略,NE,给定混合策略,p,甲,=(r,1-r); p,乙,=(q,1-q),甲,(p,甲, p,乙,)=,r,q,(-1),+(1-q),1+,(1-r),q,1+,(1-q),(-1),= 2r(1-2q)+(2q-1),乙,(p,甲, p,乙,)=,q,r,1,+(1-r),(-1),+,(1-q),r,(-1)+,(1-r),1,=2q(2r-1)-(2r-1),混合策略纳什均衡是甲在策略空间,上以概率分布,p,甲,*,=,（,1/2,，,1/2,）进行选择，乙也在策略空间,p,乙,*,=,（,1/2,，,1/2,）进行选择,Max ,甲,(p,甲, p,乙,),r,q,*,=1/2,f,.,o,.,c,.,1,-2q=0,Max ,乙,(p,甲, p,乙,),q,r,*,=1/2,f,.,o,.,c,.,2,r-1=0,1,第二节 混合策略纳什均衡的求解方法,二、反应对应法,例：扑克牌对色游戏,(p,77,),无纯策略,NE,给定混合策略,p,甲,=(r,1-r); p,乙,=(q,1-q),甲,(p,甲, p,乙,)= 2r(1-2q)+(2q-1),整理原则：一项含,r,，一项不含,r,乙,(p,甲, p,乙,)=,2q(2r-1)-(2r-1),整理原则：一项含,q,，一项不含,q,按照,NE,的条件，一个策略组合如过是一个,NE,，那么其中的每一个策略都是参与人针对其他参与人策略组合的最优反应，在纯策略,NE,中，这个“最优反应”可能是一个具体的纯策略,(,离散情形,),，也可能是一个反应函数,(reaction function,如连续情形、古诺模型,),。而在一个混合策略,NE,中，这个“最优反应”将是一个概率或很多个概率,被称为“反应对应”,(reaction correspondence),2,第二节 混合策略纳什均衡的求解方法,二、反应对应法,例：扑克牌对色游戏,(p,77,),先看甲的最优反应，记为,r,*,=R(q),：,观察,甲,(p,甲, p,乙,)= 2r(1-2q)+(2q-1),r,q,0,1,（红）,1,(,红,),1/2,1/2,r,*,=R(q),反应对应曲线,3,第二节 混合策略纳什均衡的求解方法,二、反应对应法,例：扑克牌对色游戏,(p,77,),再看乙的最优反应，记为,q,*,=R(r),：,观察,乙,(p,甲, p,乙,)=,2q(2r-1)-(2r-1),r,q,0,1,（红）,1,(,红,),1/2,1/2,q,*,=R(r),反应对应曲线,4,第二节 混合策略纳什均衡的求解方法,二、反应对应法,例：扑克牌对色游戏,(p,77,),作为,NE,，各个参与人的反应应该同时为最优，只有两个反应对应的交点满足,NE,：,r*=1/2, q*=1/2,NE,支付为：,甲,(p,甲, p,乙,)= 2r(1-2q)+(2q-1)=0,乙,(p,甲, p,乙,)=,2q(2r-1)-(2r-1)=0,r,q,0,1,（红）,1,(,红,),1/2,1/2,q*=R(r),r,*,=R(q),5,第二节 混合策略纳什均衡的求解方法,二、反应对应法,作业：社会福利博弈。使用反应对应法找到纳什均衡。,流浪汉,寻找工作 游荡,救济,政府,不救济,3,，,2,-1,，,3,-1,，,1,0,，,0,6,第三节 寻找多重纳什均衡,例：情侣博弈,两个（多个）纯策略纳什均衡,问题：纳什均衡找完了吗？有无混合策略纳什均衡？,一、支付最大化法,给定混合策略,p,陈明,=(r,1-r); p,钟信,=(q,1-q),Max ,陈明,(p,陈明, p,钟信,)=,r,3q+(1-q),+,(1-r),0,+2,(1-q),=r(4q-1)+2(1-q),Max ,钟信,(p,陈明, p,钟信,)=,q,(2r+0)+,(1-q),r,+3,(1-r),=q(4r-3)+(3-2r),NE,：,(r*, q*)=(3/4, 1/4),二、反应对应法,r,q,7,第三节 寻找多重纳什均衡,二、反应对应法：情侣博弈,先看陈明的最优反应，记为,r,*,=R(q),：,陈明,(p,陈明, p,钟信,),=r(4q-1)+2(1-q),r,q,0,1,（钟信德语）,1,(,陈明德语,),1/4,r,*,=R(q),8,第三节 寻找多重纳什均衡,二、反应对应法：情侣博弈,再看钟信的最优反应，记为,q,*,=R(r),：,钟信,(p,陈明, p,钟信,)=q(4r-3)+(3-2r),r,q,0,1,（钟信德语）,1,(,陈明德语,),1/4,q,*,=R(r),3/4,9,第三节 寻找多重纳什均衡,二、反应对应法：情侣博弈,反应对应曲线有三个交点：三个,NE,：,r*=0, q*=0,纯策略（确定性）,r*=3/4, q*=1/4,混合策略（不确定性）,r*=1, q*=1,纯策略（确定性）,r,q,0,1,（钟信德语）,1,(,陈明德语,),1/4,3/4,r,*,=R(q),q,*,=R(r),10,第三节 寻找多重纳什均衡,二、反应对应法：情侣博弈,支付的帕累托优势：初步印象,陈明,=r(4q-1)+2(1-q),，,钟信,=q(4r-3)+(3-2r),r*=0, q*=0,纯策略（确定性）,双方,NE,支付,:,陈明,*=3,，,钟信,*=2,r*=3/4, q*=1/4,混合策略（不确定性）,双方,NE,支付,:,陈明,*=3/2,，,钟信,*=3/2,r*=1, q*=1,纯策略（确定性）,双方,NE,支付,:,陈明,*=2,，,钟信,*=3,纯策略纳什均衡比混合策略纳什均衡具有支付优势，这称为帕累托优势,如果博弈同时存在纯策略纳什均衡和,混合策略纳什均衡，前者往往得到优先考虑,11,第三节 寻找多重纳什均衡,二、反应对应法：情侣博弈,夫妻之争博弈,12,第四节 纳什均衡的存在性,不同均衡概念的关系,优势均衡,纯策略纳什均衡,混合策略纳什均衡,13,第四节 纳什均衡的存在性,问题：是否所有的博弈都存在,NE,（纯的或混合的）？,Nash,在,1950,年证明：任何,有限博弈,，都至少存在一个,NE,。,纳什定理：,在一个由,n,个博弈方的,G=,S,1,，, S,n,; u,1, u,n,中，如果,n,是有限的，且,S,i,都是有限集，则该博弈至少存在一个纳什均衡，但可能包含混合策略,Wilson,（,1971,）证明，几乎所有有限博弈，都存在有限奇数个,NE,，包括纯策略,NE,和混合策略,NE,。,（纯策略）纳什均衡的存在性定理,(Debreu,1952,；,Glicksberg,1952,；,Fan,1952),：,考虑一个,n,人策略式博弈,如果每个参与人的纯策略空间,S,i,是欧氏空间中的非空、紧（闭而有界）的凸集,支付函数,u,i,(s),连续且对,s,i,拟凹,则博弈存在一个纯策略,Nash,均衡。,14,第四节 纳什均衡的存在性,例：凹但不连续的支付函数,二人博弈：策略空间为,S,1,=S,2,= (0, 1),支付函数：,反应对应：,反应对应曲线：,s,2,s,1,1/3,1/3,s,1,=,s,2,=,无纳什均衡,15,第四节 纳什均衡的存在性,问题：是否所有的博弈都存在,NE,（纯的或混合的）？,（纯策略）纳什均衡的存在性定理,(Debreu,1952,；,Glicksberg,1952,；,Fan,1952),：,考虑一个,n,人策略式博弈,如果每个参与人的纯策略空间,S,i,是欧氏空间中的非空、紧（闭而有界）的凸集,支付函数,u,i,(s),连续且对,s,i,拟凹,则博弈存在一个纯策略,Nash,均衡。,（混合策略）纳什均衡的存在性定理,(Glicksberg,1952),：,在,n,人策略式博弈中,如果每个参与人的纯粹策略空间,S,i,是欧氏空间中的非空、紧（闭而有界）的凸集,如果支付函数,u,i,(s),为连续函数,那么博弈至少存在一个混合策略,Nash,均衡,.,16,第五节 多重纳什均衡的筛选,一个博弈可能有多个均衡，但,仍然存在不稳定性你预测出现这个纳什均衡，因而有相应选择，我却以为会出现另一个，乃有我的选择，此时的组合可能并不构成纳什均衡,博弈论并没有一个一般的理论证明纳什均衡结果一定能出现,如何保证纳什均衡出现？,一、帕累托优势标准：按照支付大小筛选纳什均衡,例：猎人博弈,17,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,二、,风险优势标准：风险小的,NE,优先,假设概率，比较期望支付大小,例：虚拟博弈,两个纳什均衡，哪个更优？,假设,r=1/2, q=1/2,给定,q=1/2,：甲采用上策略的期望支付为：,9/2+0/2=4.5,甲采用下策略的期望支付为：,8/2+7/2=7.5,给定,r=1/2,：乙采用左策略的期望支付为：,9/2+0/2=4.5,乙采用右策略的期望支付为：,8/2+7/2=7.5,期望支付越大，风险越小：甲采用下策略，乙采用右策略,选择的纳什均衡为：（下策略，右策略）,18,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,二、,风险优势标准：风险小的,NE,优先,风险偏离损失乘积比较法,1.,甲：单独偏离均衡的损失,（,1,）偏离,A,的损失：,6-5=1,（,2,）偏离,B,的损失：,4-0=4,2.,乙：单独偏离均衡的损失,（,1,）偏离,A,的损失：,6-5=1,（,2,）偏离,B,的损失：,4-0=4,3.,风险优势标准方法：偏离,A,的损失,VS,偏离,B,的损失,11,44,4.,结论,（,1,）偏离,B,的损失更大：,16,（,2,）不偏离,B,选择的纳什均衡偏离损失更大者为：,B,即,(,下策略，右策略,),A,B,19,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,二、,风险优势标准：风险小的,NE,优先,风险偏离损失乘积比较法,1.,甲：单独偏离均衡的损失,（,1,）偏离,A,的损失：,6-5=1,（,2,）偏离,B,的损失：,4-0=4,2.,乙：单独偏离均衡的损失,（,1,）偏离,A,的损失：,6-5=1,（,2,）偏离,B,的损失：,4-0=4,3.,风险偏离损失乘积比较法：,偏离,A,的损失,VS,偏离,B,的损失,11,44,4.,结论,（,1,）偏离,B,的损失更大：,16,（,2,）不偏离,B,选择的纳什均衡偏离损失更大者为：,B,即,(,下策略，右策略,),A,B,20,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,二、,风险优势标准：风险小的,NE,优先,5.,风险偏离损失乘积比较法的缺陷：,例：假设,M,远远大于,m,1.,甲：单独偏离均衡的损失,(1),偏离,A,的损失：,(M-m)-M/2=M/2-m (2),偏离,B,的损失：,M-(M-m)=m,2.,乙：单独偏离均衡的损失,(1),偏离,A,的损失：,0-0=0 (2),偏离,B,的损失：,0-0=0,如果使用风险偏离损失乘积比较法：,偏离,A,的损失,VS,偏离,B,的损失,(M/2-m)0=m0,一种建议：,甲偏离,A,的损失,VS,甲偏离,B,的损失,M/2-mm,选择的纳什均衡为：,A,即,(D,，,L),A,B,21,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,二、,帕累托优势标准和风险优势标准的关系,如果帕累托优势标准和风险优势标准的选择冲突？,例：,帕累托优势标准法：选择的纳什均衡为,A,风险优势标准：,1.,甲：单独偏离均衡的损失,(1),偏离,A,的损失：,6-5=1 (2),偏离,B,的损失：,4-(-1000)=1004,2.,乙：单独偏离均衡的损失,(1),偏离,A,的损失：,6-5=1 (2),偏离,B,的损失：,4-(-1000)=1004,风险偏离损失乘积比较法：,偏离,A,的损失,VS,偏离,B,的损失,11,10041004,选择的纳什均衡为：,B,怎么办？,A,B,22,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,四、,聚点均衡,如果帕累托优势标准和风险优势标准都无法使用呢？,在现实生活中，参与人可能使用某些被博弈模型抽象掉的信息来达到一个“聚点,(focal pount),”均衡。这些信息可能与社会文化习惯、参与人过去博弈的历史等有关。,(Schelling, 1960),性别战：某一方的生日；社会地位,提名博弈,道路交通规则,廉价磋商,(Cheap talk),与协调博弈,尽管无法保证磋商会达成一个协议，即使达成协议也不一定会被遵守，但在一些博弈中，事前磋商确实可以使某些均衡实际上出现。,例：,两人同时给对方打电话,23,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,四、,聚点均衡,廉价磋商,(Cheap talk),尽管无法保证磋商会达成一个协议，即使达成协议也不一定会被遵守，但在一些博弈中，事前磋商确实可以使某些均衡实际上出现。,例：虚拟博弈中的事前告知,例：,两人同时给对方打电话,重复博弈、学习过程与协调模式,9,，,9,0,，,0,0,，,0,1,，,1,R,乙,甲,U,D,L,9,，,9,0,，,8,8,，,0,7,，,7,R,乙,甲,U,D,L,聚点,24,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,四、,聚点均衡,重复博弈与协调模式,假定博弈重复许多次，即使参与人最初难以协调行动，在博弈若干次后，某种特定的协调模式可能会形成，特别地，假定参与人每一轮根据其对手以前的,“,平均,”,战略来选择自己的最优战略，博弈可能收敛于一个纳什均衡。,以上情况并不保证必然出现纳什均衡,25,第三节多重纳什均衡的选择标准,四、相关均衡,（一）案例：,“,地域连坐,”,下的产品质量博弈,企业乙,好产品 差产品,好产品,企业甲,差产品,4,，,4,-8,，,-2,-2,，,-8,-2,，,-2,26,第三节多重纳什均衡的选择标准,四、相关均衡,（二）相关均衡,参与人主动设计某种形式的选择机制，形成制度安排，从而确定最终均衡,“,三鹿,”,事件出现后，河北省其他食品企业以后如何做？,4,，,4,-8,，,-2,-2,，,-8,-2,，,-2,27,第三节多重纳什均衡的选择标准,五、抗共谋均衡,（一）案例：抽象的选择,乙,左 右,上,甲,下,乙,左 右,上,甲,下,0,，,0,，,10,-5,，,-5,，,0,-5,，,-5,，,0,1,，,1,，,-5,丙：,A,-2,，,-2,，,0,-5,，,-5,，,0,-5,，,-5,，,0,-1,，,-1,，,5,丙：,B,28,第三节多重纳什均衡的选择标准,五、抗共谋均衡,（二）共谋偏离（集体偏离）均衡的激励,1.,如果,集体偏离,（上，左，,A,）,（,1,）起因：甲、乙集体偏离，选（下，右，,A,）,（,2,）结果：甲的支付,01,，乙的支付,01,（,3,）结论：甲、乙有集体偏离的动机， （上，左，,A,）非抗共谋均衡,29,第三节多重纳什均衡的选择标准,五、抗共谋均衡,（二）共谋偏离（集体偏离）均衡的激励,2.,如果,集体偏离,（下，右，,B,）,（,1,）若甲、乙集体偏离，选（上，左，,B,）,-1-2,，,-1-2,（,2,）若甲、丙集体偏离，选（上，右，,A,）,-1-5,，,50,（,3,）若乙、丙集体偏离，选（下，左，,A,）,-1-5,，,50,（,4,）结论：缺乏集体偏离的激励，,（下，右，,B,）为,抗共谋均衡,30,猎鹿博弈：何为抗共谋均衡？,乙,猎鹿 打兔,猎鹿,甲,打兔,10,，,10,0,，,4,4,，,0,4,，,4,31,多人博弈中的共谋问题,防共谋均衡：如果一个博弈的米讴歌策略组合满足下列要求：,1,、没有任何单个博弈方的“串通”会改变博弈的结果，即单独改变策略无利可图,2,、给定选择偏离的博弈方又再次偏离的自由时，,没有任何两个博弈方的串通会改变博弈的结果,3,、依此类推，直到所有博弈方都参加的串通也不会改变博弈的结果,满足上述要求的均衡策略组合成为“防共谋均衡”,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,2.6.2,共谋和防共谋均衡,32,第五节 多重纳什均衡的筛选,如何保证纳什均衡出现？,三、,帕累托优势标准和风险优势标准的关系,如果帕累托优势标准和风险优势标准的选择冲突？,怎么办？,在帕累托优势标准和风险优势标准之间，理论给予帕累托优势标准以优先权，而风险优势只有在局中人面临不知道先哪个均衡好的不确定性时，才变得重要。当一个均衡具有帕累托优势时，局中人一定选择这个均衡，不确定性就不存在了。,理性假设与确定性环境,有限理性假设与不确定性环境,四、,聚点均衡,A,B,33,第四节 混合策略纳什均衡的求解方法,二、,对混合策略纳什均衡的进一步讨论,混合策略表示使用不同纯策略的大量参与人,Harsanyi,：混合可以解释为参与人收益上微小的不可观测变动的结果,博弈多次反复进行时参与人实施某一纯策略的不确定次数和时间,一个参与人实施混合策略的目的是给其他参与人造成不确定性，尽管其他参与人能推测到他选择某个纯策略的概率有多大，但却不知道他到底会选哪个纯策略。,34,练习：模型化下述划拳博弈：,两个老朋友在一起喝酒，每个人有四个纯战略：杠子、老虎、鸡和虫子，输赢规则是：杠子降鸡，鸡吃虫子，虫子降杠子，两人同时出令。如果一个打败另一个，赢的效用为,1,，输的效用为,-1,，否则效用为,0,，写出这个博弈的支付矩阵，这个博弈有纯战略均衡吗？计算其混合战略纳什均衡。,35,