博弈论3. Mixed strategy and Nash equilibrium.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2014/3/11,张醒洲，大连,#,混合策略与纳什均衡,Mixed Strategy and Nash Equilibrium,张醒洲,2014/3/11,张醒洲，大连,1,如何预测博弈结果？,如何给局中人提建议？,学者的分析方法,2014/3/11,张醒洲，大连,2,最佳反应,如果对方有纯策略，你如何应对？,如果对方有混合策略，你如何应对？,如果你建立了关于对方行为的信念，如何反应？,2014/3/11,张醒洲，大连,3,纳什均衡,纯策略纳什均衡,混合策略纳什均衡,2014/3/11,张醒洲，大连,4,n,人博弈的标准式,参与人,参与人从,1,到,n,排序，设其中任一特定参与人的序号为,i,参与人,i,的策略空间,S,i,参与,人,i,可以,选择的策略集合,用,表示策略,是,策略集,中,的要素,参与,人,i,的收益函数,定义,在一个,n,人博弈的策略式（也称为标准式）表示中，参与人 的策略空间为,收益函数为,我们用,表示此博弈。,2014/3/11,张醒洲，大连,5,纯策略纳什均衡,方法：局中人对其他参与人的任意一个给定的策略做出最佳反应,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,2014/3/11,张醒洲，大连,6,纯策略纳什均衡,假定亚当选择歌剧，夏娃如何选择？,假定亚当选择拳击，夏娃如何选择？在这种情形夏娃会关注亚当的收益吗？,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,2014/3/11,张醒洲，大连,7,纯策略纳什均衡,假定夏娃选择,歌剧,，亚当如何,选择,？在这种情形亚当会关注夏娃的收益吗？,假定,夏娃,选择,拳击,，,亚当,如何,选择？,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,2014/3/11,张醒洲，大连,8,纯策略纳什均衡。有三个均衡结果,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,2014/3/11,张醒洲，大连,9,纯策略纳什均衡：三个纳什均衡,纳,什的最佳反应思路只能淘汰最差的结果（拳击，歌剧）,同时迁就对方不是均衡。,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,2014/3/11,张醒洲，大连,10,纯策略纳什均衡。关注他人？,均衡（歌剧，拳击）会出现吗？为什么？,关注他人？,距离和自由的价值？,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,亚当,1,3,0,1,1,2,2,2,歌剧,拳击,歌剧,拳击,夏娃,2014/3/11,张醒洲，大连,11,纳什均衡,求解思路：最佳应对（最佳反应）。,均衡判据：互为最佳反应策略导致的结果。,稳定性：单方面偏离均衡点是非理性的。,均衡的自我实现：尽管没有签订有约束力的协议，局中人会自利的选择一个可以导致均衡结果的策略。,协调问题：当有多个均衡时，协调是必要的。,前提：博弈结构与理性是局中人的共同知识,2014/3/11,张醒洲，大连,12,纳什均衡的条件，参阅课本,P.12,2014/3/11,张醒洲，大连,13,不存在纯策略纳什均衡的博弈,前面的例子中可能会有多个纯策略纳什均衡，这引起了协调问题。,问题：纳什均衡是否会在重复剔除严格劣势策略的过程中消失？回答是：不会。因为导致纳什均衡结果的策略绝对不会是严格劣势策略。,下面的例子说明：某些博弈不存在纯策略纳什均衡。,2014/3/11,张醒洲，大连,14,2014/3/11,张醒洲,，,大连,15,猜硬币博弈,模型,两个参与人,1,2,每个参与人的策略,空间为,H,T,收益,零和,试着找到纳什均衡,参与人,2,参与人,1,正面,背面,正面,-1,1,1,-1,背面,1,-1,-1,1,两个男孩各自有一个硬币并且他们必须选择将硬币的正面朝上还是背面朝上。如果两个硬币朝上的面相同（即都是正面或都是背面），则参与人,2,将赢得参与人,1,的硬币；否则，参与人,1,将赢得参与人,2,的硬币。,猜硬币,如果参与人的策略一致，是,(,正面，正面,),或,(,反面，反面,),，则参与人,1,会偏向于改变策略；,但是如果两者策略不一致，是,(,正面,反面,),或,(,反面,正,面,),，则参与人,2,偏向于改变策略。,参与人,2,正面,背面,正面,-1,1,1,-1,参与人,1,背面,1,-1,-1,1,没有一组策略满足,(NE),2014/3/11,张醒洲，大连,16,2014/3/11,张醒洲,，,大连,17,石头,-,剪刀,-,布博弈,此博弈也不存在纯策略纳什均衡，实际上是无人选择纯策略。,无论参与人,1,选择哪个纯策略，参与人,2,都可以打败他。,参与人,2,石头,剪刀,布,石头,0,0,1,0,0,1,参与人,1,剪刀,0,1,0,0,1,0,布,1,0,0,1,0,0,2014/3/11,张醒洲,，,大连,18,猜对方策略，并总结为概率分布,猜硬币博弈和划拳博弈的突出特点是每个参与人都试图猜中对方的策略。任何此类博弈都没有纯策略纳什均衡,不存在,1.1.C,节所定义的纳什均衡。,这一类博弈的解包含了不确定性：“一个参与人无法预言其他人在一次具体博弈中的行动，而代之以预测行动的概率分布”。,参与人通过观察、推断对手的行为只能得到概率分布而不是确定性判断。,2014/3/11,张醒洲,，,大连,19,纯策略，混合策略,考虑策略式（标准式）博弈,G=,S,1,S,n,;,u,1,u,n,此后我们定义,S,i,中的策略为参与人,i,的纯策略,在本节的完全信息同时行动博弈中，一个参与人的纯策略就是他可以选择的不同行动；,例如，在猜硬币的博弈中，,S,i,包含两个纯策略：正面与背面。,参与人,i,的一个混合策略是在其策略空间,S,i,中的,（一些或全部）纯策略上的概率分布。,2014/3/11,张醒洲,，,大连,20,概率和信念,随机事件,事件有明确定义,.,我们可以区分不同的事件,.,在进行观察或试验前,我们不能预言一个具体的事件会出现,.,我们可以判断哪些事件有可能出现,并且能预测每一个事件出现的可能性大小,.,概率,事件的概率是对一次随机试验中该事件出现的可能性的度量,如果对可能性的度量以某种客观规律或物质属性为基础,我们就用“概率”一词,如果对可能性的度量以个人经验、主观判断为基础，就使用“主观概率”、“信念”、“置信度”等术语。,2014/3/11,张醒洲,，,大连,21,概率分布,样本空间：,=,1,2,n,试验中可能出现的所有基本结果,i,的集合,事件由基本结果组成，是样本空间的子集。如果在试验中事件,A,中的一个结果出现了,就说事件,A,发生。,概率分布就是将总概率,P(,),1,分解到所有可能的样本点或事件上的一种方式,对于混合策略，样本空间对应行动集合。被某一混合策略赋予非零概率的纯策略构成该混合策略的支撑集。,2014/3/11,张醒洲,，,大连,22,混合策略：猜硬币,参与人,i,的一个混合策略是在其策略空间,S,i,中的概率分布,举例,:,猜硬币,S,2,包含两个纯策略即正面和反面,因此参与人,2,的一个混合策略为概率分布,(,q,1,-,q,),其中,q,为正面朝上的概率，,1,-,q,是背面朝上的概率,并且,0,q,1.,参与人,2,参与人,1,正面,q,背面,1,-q,正面,-1,1,1,-1,背面,1,-1,-1,1,混合策略,(0,1),是背面朝,上的纯策略,;,类似地,混合,策略,(1,0),是正面朝上的,纯策略。,2014/3/11,张醒洲,，,大连,23,混合策略,:,举例,参与人,2,的一个混合策略为概率分布,(,q,r,1-q-r,),其中,q,表示出左的概,率，,r,表示出中的概率，,1-q r,表示出右的概率。和前面一样，,0 q 1,并且还应满足,0 r 1,和,0 q+r 1/2),，要么是,M(,当,q 1/2),但不会是,B,，虽然,T,或,M,并不严格优于,B,关键：存在一个混合策略严格优于,B,如果参与人,1,以,1/2,的概率出,T,，以,1/2,的概率选,M,，则,1,的期望收益是,3/2,无论参与人,2,采取哪种策略（纯的,或混合的），参与人,1,的收益,3/2,都,大于其选,B,时所获得的收益。,参与人,2,L,q,R,1-q,T,3,0,参与人,1,M,0,3,B,1,1,图,1.3.1,这个,例子同时说,明了在“寻找另外一个严格优于,s,i,的策略”时，混合策略所起的,作用,。,2014/3/11,张醒洲,，,大连,28,用纯策略应对混合策略，如果列不偏执,图,1.3.2,表明，,一个纯策略可以是一个混合策略的最优反应，即使这一纯策略并不严格占优于其他纯策略。,在这个博弈中，,B,不是参与,人,1,对参与人,2,的纯策略,L,或,R,的最,优反应；,但是当,1/3 q,2/3,时，参与,人,1,对参与人,2,的混合策略,(q,1-q),的最优,反应是策略,B,。,参与人,2,L,q,R,1-q,T,3,0,参与人,1,M,0,3,B,2,2,Figure 1.3.2,根据信念，选择最优混合策略应对,建立信念之关键：用好辩证法，确定支撑集,2014/3/11,张醒洲，大连,29,2014/3/11,张醒洲,，,大连,30,给定列的混合策略，行的最优应对,令,(r,1-,r),为行参与人的混合策略,(,以概率,r,出正面,以概率,1-r,出背面,),；,给定行关于,列,的信念（,q,1-q),如果,列,出,正面,行的,期望,收益,是（,1-,2r,）,；,如果,列,出,背面,，行的,期望,收益,是（,2,r,-1,）,.,参与人,2,参与人,1,正面,q,背面,1-q,正面,r,-1,1,1,-1,背面,1,-r,1,-1,-1,1,对,任意,0,1,上的,q,，计算,r,的,最优,值,用,r*,(,q,),表示,。然后，当列选择,混,合策略,(,q,1-,q,),时，参与人,1,的最优反应是,(,r*,1-,r,*,),。,2014/3/11,张醒洲,，,大连,31,对,列,的混合策略，行最优反应,列的策略，或行的信念：,(,q,1-,q,),；,行,的策略反应：,(r,1-,r,),求解,r*,(,q,),当,列,的混合策略为,(,q,1-,q,),时，行选择,(r,1-,r,),的期望收益如下：,参与人,2,参与人,1,正面,q,背面,1-q,正面,r,-1,1,1,-1,背面,1,-r,1,-1,-1,1,（,1-,2r,）,q+,（,2,r,-,1,）,（,1-,q,）,=,（,2,r,1)(1-2,q,),r*,(,q,)=arg max,4(,r,-1/2)(1/2-,q,),2014/3/11,张醒洲,，,大连,32,对,于列,的混合策略，行的最优反应,列,:,(,q,1-,q,)q,0,1,行,:,(r,1-,r,),r*,(,q,)=arg max,4(r-1/2)(1/2-q,),图,1.3.3,当,q=1/2,时,，,行,的,期望,收益,4(r-1/2)(1/2-q,),与,r,无关,，即“,行的,所有混合策略,(r,1-r),都是无差异,的”,。或者说,，当,q=1/2,时，对于,0,到,1,之间的任何,r,，,(r,1-r),都是,(q,1-q),的最优反应。,2014/3/11,张醒洲,，,大连,33,最优反应,对应,对应是“集值函数”,这里，因为存在一个,q,，使得,r*,(,q,),有不止一,个值，,我们称,r*,(,q,),为参与人,1,的最优反应对应,。是一个更一般的概念。,2014/3/11,张醒洲,，,大连,34,对参与人,1,的混合策略，参与人,2,的最优反应,完全信息静态博弈中，参与人同时行动，,并且参与人,2,和参与人,1,会以相同的,思路,考,虑此博弈。,对参与人,1,的策略,(r,1-r),，参与人,2,的最优,反应是,(q*(r),1-q*(r),其中,q*(r)=arg max,4(q-1/2,)(,1/2-r),2014/3/11,张醒洲,，,大连,35,互为,最优反应对应，导致纳什均衡,最优反应,r*,(,q,),和,q*,(,r,),的交点确定了猜硬币博弈的纳什均衡：,如果参与人,i,的策略是,(1/2,1/2),，则参与人,j,的最,优反应是,(1/2,1/2),，满足纳什均衡的要求。,图,1.3.6,2014/3/11,张醒洲,，,大连,36,对混合策略纳什均衡的说明,在有混合策略纳什均衡的博弈中，并不需要参与人通过扔硬币、掷骰子或其他随机 化手段来选择每次的行动。,在每次玩博弈时每,一个参与人确定性的选择一个纯策略,.,但对方不具备关于这,一次选择的,充分信息,这时就要作相应的预测,将对方的行为理解为一个混合策略,并作出相应的对策,(chose a best response to a mixed strategy),更确切地，我们可以把参与人,j,的混合策略解释为参与人,i,对参与人,j,选择哪一个纯策略的不确定性。我们可以用“信念”来表示对这种不确定性的推断。,每次玩博弈时每一个参与人选择一个纯战略,正是利用了对手关于自已行为的不确定性。,2014/3/11,张醒洲,，,大连,37,混合策略纳什均衡,:,两人博弈,定义,.,在两个参与人,策略,式博弈,G=,S,1,S,2,;,u,1,u,2,中，混合策略,(,p,*,1,p,*,2,),是纳什均衡的充要条件为：每一参与人的混合策略是另一个参与人混合策略的最优反应，即,其中,2014/3/11,张醒洲,，,大连,38,纳什均衡,:,性别战博弈,此博弈存在两个纯策略纳什均衡,(Opera,Opera),和,(Fight,Fight),都是纳什均衡,2014/3/11,张醒洲,，,大连,39,纳什均衡,:,性别战博弈,混合策略组,:(r,1-r)=(2/3,1/3),和,(q,1-q)=(1/3,2/3),是一个纳什均衡,Pat,Chris,Opera,q,Fight,1-q,Opera,r,2,1,0,0,Fight,1,-r,0,0,1,2,2014/3/11,张醒洲,，,大连,40,纳什均衡的存在性,John Nash,“,Equilibrium points in n-person games,”Proceedings of the National Academy of Sciences,36(1950),48-49.,在一个,n,人策略式博弈中，如果参与人的数量以及每个参与人的策略空间都是有限的，那么此博弈存在至少一个纳什均衡，可能包含混合策略均衡。,2014/3/11,张醒洲,，,大连,41,Brower,的不动点定理,纳什定理的证明需用到不动点定理。作为不动点定理的一个简单例子，假定,f(x),是一个定义域和值域都在,0,1,之间的连续函数，则,Brower,的不动点定理保证了存在至少一,个不动点,即在,0,1,中存在至少一个值,x,*,，,使得,f,*,(x)=x,*,。图,1.3.13,给出了一个例子。,增补：再论混合策略下的随机选择,回忆前面两个例子中的一个重要发现,2014/3/11,张醒洲，大连,42,2014/3/11,张醒洲,，,大连,43,对,于列,的混合策略，行的最优反应,列,:,(,q,1-,q,)q,0,1,行,:,(r,1-,r,),r*,(,q,)=arg max,4(r-1/2)(1/2-q,),当,q=1/2,时,，,行,的,期望,收益,4(r-1/2)(1/2-q,),与,r,无关,，即“,行的,所有混合策略,(r,1-r),都是无差异,的”,。或者说,，当,q=1/2,时，对于,0,到,1,之间的任何,r,，,(r,1-r),都是,(q,1-q),的最优反应,。那么：,给定关于列的信念,q=1/2.,行参与人在正、反面之间随机选择，无论选正面还是反面，行的预期收益都是零。,纳什均衡,:,性别战博弈,Pat,Chris,Opera,q,Fight,1-q,Opera,r,2,1,0,0,Fight,1,-r,0,0,1,2,混合策略组合,:(r,1-r)=(2/3,1/3),和,(q,1-q)=(1/3,2/3),是一个纳什均衡。,如果相信对方的策略是,q=1/3,行的纯策略“歌剧”与纯策略“拳击”的预期收益都是,2/3.,所以，行可以在这两个纯策略之间随机选择。,2014/3/11,张醒洲,，,大连,44,增补：再论混合策略下的随机选择,混合策略均衡是一种“信念均衡”,导致均衡结果的一组混合策略，可以看成一组均衡的信念。,参与人的策略，是其他局中人关于该参与人将如何行动的信念或主观概率。,给定关于其他人行动的均衡信念，局中人的均衡策略的支撑集中的任意一个纯策略（或叫做行动）给他带来相同的预期收益，所以他可以在这些行动中随机选择。,所以，混合策略均衡是一种状态，其中参与人无法确定对手的实际行动。,2014/3/11,张醒洲，大连,45,均衡信念与随机选择的行动,Martin J.Osborne,Ariel Rubinstein.A course in Game,Theory.economics.utoronto.ca/osborne/cgt/index.html,引理,33.2,，定义,44.1,2014/3/11,张醒洲，大连,46,2014/3/11,张醒洲,，,大连,47,作业,3,1.9,什么,是,策略,式,博弈的,混合策略,?,什么,是策略式博弈,的,混合策略,纳什均衡,?,2014/3/11,张醒洲,，,大连,48,Assignment (1.13,选作,),