混合策略纳什均衡课件.ppt

1、12/9/20221混合策略纳什均衡 Mixed Strategy Nash Equilibrium理学院 顾聪12/9/20222两个参与人各拿一枚硬币，并选择出正面向上还是反面向上。若两枚硬币是一致的(即全部正面或全部反面)，则参与人2赢走参与人1的硬币；若两枚硬币不一致(一正一反)，参与人1赢得参与人2的硬币。支付矩阵如下：参与人1参与人2 -1，1 1，-1 1，-1 -1，1正面反面正面反面由划线法可知，该博弈不存在纳什均衡。所以采取纯策略不存在稳定的纳什均衡解。4.1 4.1 严格竞争博弈和混合策略严格竞争博弈和混合策略1.1.混合策略的提出混合策略的提出猜硬币博弈猜硬币博弈12/

2、9/20223在这类博弈中，不存在纯策略纳什均衡。参与人的支付取决于其他参与人的策略；以某种概率分布随机地选择不同的行动。每个参与人都想猜透对方的策略，而每个参与人又不愿意让对方猜透自己的策略。这种博弈的类型是什么？如何找到均衡？上述博弈的特征是：上述博弈的特征是：12/9/20224策略：参与人在给定信息集的情况下选择行动的规则，它规定参与人在什么情况下选择什么行动，是参与人的“相机行动方案”。纯策略：如果一个策略规定参与人在每一个给定的信息情况下只选择一种特定的行动，称为纯策略，简称“策略”，即参与人在其策略空间中选取唯一确定的策略。混合策略：如果一个策略规定参与人在给定的信息情况下以某种

3、概率分布随机地选择不同的行动，称为混合策略。参与人采取的不是明确唯一的策略，而是其策略空间上的一种概率分布。2.2.混合策略、混合策略博弈和混合策略纳什均衡混合策略、混合策略博弈和混合策略纳什均衡12/9/20225 混合策略 vs.纯策略(不确定性 vs.确定性)在博弈 中，博弈方 的策略空间 ，则博弈方 以概率分布 随机在其 个可选策略中选择的“策略”，称为一个“混合策略”，其中 对 都成立，且 纯策略可以理解为混合策略的特例，即在诸多策略中，选择该纯策略的概率为1，选其他纯策略的概率为0.为何参与人可能会选择带不确定性的混合策略而放弃确定性的纯策略？参与人主观因素造成的犹豫不决 外在客观

4、因素的不确定性带来应对策略的不确定性 迷惑对手：为了让其它参与人不能清楚了解自己的选择,;,11nnuuSSGi,1ikiissSki1(,)iiikppp10ijpkj,1 11iikpp12/9/20226),(*21n*1 2 )iiiiiiiiiinuuSui即，如果对于所有的，有(,(,)，其中，表示参与人 的期望效用。混合策略扩展博弈：博弈方在混合策略的策略空间(概率分布空间)的选择看作一个博弈，就是原博弈的“混合策略扩展博弈”。混合策略纳什均衡(MNE)：由最优的混合策略构成的混合策略组合：12/9/20227121212121212111()(,)nnnnmmmijjnjijj

5、njjjjE pppp u sss 对于任意混合策略组合：若各参与人最终确定的组合(纯策略组合)为参与人的支付为发生此情况的概率为 参与人的期望效用：121(,),(,)iniiimipp pppppP12121(,),)nijjnjiiimsssSss1212(,)nijjnju sss1212njjnjppp3.3.期望效用期望效用(Expected Payoff)(Expected Payoff)12/9/20228 由于混合策略伴随的是支付的不确定性，因此参与人关心的是其期望效用。最优混合策略：是指在给定对方的混合策略的情况下，使期望效用函数最大的混合策略。在两人博弈里，混合策略纳什均

6、衡是两个参与人的最优混合策略的组合。12/9/20229 23，3-1，1-1，00，流浪流浪流浪汉流浪汉政府政府救济救济不救济不救济寻找工作寻找工作虽这模型没有PNE，却有下述的MNE：参与人以一定的概率选择某种策略，然后计算相应于不同概率的期望效用。4.4.一个例子一个例子社会福利博弈社会福利博弈12/9/202210设：设：政府政府救济的概率救济的概率=1/2；不救济的概率不救济的概率1-1-=1/2。流浪汉流浪汉寻找工作的期望效用：寻找工作的期望效用：1/22+1/2 1=1.5流浪的期望效用：流浪的期望效用：1/23+1/2 0=1.53 ,2-1 ,3-1 ,1 0 ,0救济救济不

7、救济不救济1-1-寻找工作寻找工作 游荡游荡1-1-此时，流浪汉选择任何混合策略的期望效用都是1.5，则流浪汉的任何一种策略(纯的=1或=0或混合的01)都是政府所选择的混合策略的最优反应。12/9/202211 30.21 0.80.2 1 0.200.80.2 救济：不救济：3 ,2-1 ,3-1 ,1 0 ,0救济救济不救济不救济1-1-寻找工作寻找工作 游荡游荡1-而当而当 =0.2 1-=0.8 游荡游荡 寻找工作寻找工作如果流浪汉选择这个混合策略，政府的任何策略(混合的或纯的)带给政府的期望效用为-0.2。特别的，以1/2的概率分别选择救济和不救济当然也是政府对于流浪汉所选择的混合

8、策略的最有反应。这样，我们得到一个混合策略组合，每一个参与人的混合策略都是给定对方混合策略是的最优选择，从而构成混合策略纳什均衡。策略 期望收益政府 (0.5,0.5)-0.2流浪汉 (0.2,0.8)1.5 既然参与人在构成混合策略时选择不同纯策略之间是无差异的，他为什么不选择一个特定的纯策略而要以特定的概率随机地选择不同的纯策略呢？一个参与人选择混合策略目的是给其他参与人造成不确定性。海萨尼(Harsanyi,1973)对混合战略的解释是，混合策略均衡等价于不完全信息下的纯策略均衡：如社会福利博弈中，假定有两类特征的流浪汉，一类选择寻找工作，另一类选择游荡；每个流浪汉都知道自己的特征，但政

9、府并不知道流浪汉的准确特征，只知道流浪汉20%概率属第一类，80%概率属第二类。在这种情况下，政府在选择自己的策略时似乎面临的是一位选择混合策略的流浪汉。12/9/202213支付最大化法支付等值法最优反应函数法4.2 4.2 混合策略纳什均衡的求解混合策略纳什均衡的求解12/9/202214参与人1的混合策略为1=(q,1-q)(分别以概率q和1-q选择正面和反面)，参与人2的混合策略为2=(r,1-r)(分别以概率r和1-r选择正面和反面)。参与人1参与人2 -1，1 1，-1 1，-1 -1，1r 正面1-r 反面q 正面1-q 反面1.1.支付最大化法求纳什均衡支付最大化法求纳什均衡猜

10、硬币博弈猜硬币博弈12/9/202215参与人1参与人2 -1，1 1，-1 1，-1 -1，1r 正面1-r 反面q 正面1-q 反面E1(正面)=(-1)r+1(1-r)=1-2r参与人1选取反面的期望效用为 E1(反面)=1r+(-1)(1-r)=2r-1当给定参与人2选择混合策略1=(r,1-r)时，参与人1的选取正面的期望效用为 12/9/202216类似地，得到参与人2的期望效用为E2=E2(正面)r+E2(反面)(1-r)=(1-2q)(2r-1)由一阶条件：*12*121 11 1(,)*(,)122 22 2 (,)和分别是参与人 和参与人 的混合纳什均衡策略，为猜币博弈的纳

11、什均衡。122(12)0,2(12)011,22EErqqrrq参与人1的期望效用为 E1=E1(正面)q+E1(反面)(1-q)=(1-2r)(2q-1)12/9/202217 23，3-1，1-1，00，流浪流浪1-流浪汉流浪汉政政府府救济救济不救济不救济1-工作工作*(,1)(1)()(3(1)(1)(1)(0(1)(51)5100.2GLGLGvv 假定政府的混合策略是；流浪汉的混合策略是，。政府的期望效用函数为：,求微分，得到政府最优化的一阶条件：故即：流浪汉以0.2的概率选择寻找工作，0.8的概率选择流浪。同理可以根据流浪汉的期望效用函数找到政府的最优混合策略。社会福利博弈社会福利

12、博弈12/9/202218 对*=0.2 的解释：如果流浪汉寻找工作的概率小于0.2，政府的最优选择是不救济；如果流浪汉寻找工作的概率大于0.2，政府的最优选择是救济。对*=0.5 的解释：如果政府救济的概率大于0.5，流浪汉的最优选择是流浪；如果政府救济的概率小于0.5，流浪汉的最优选择是寻找工作。混合策略纳什均衡的含义：纳什均衡要求每个参与人的混合战略是给定对方的混合战略下的最优选择。因此在社会福利博弈中，*=0.2，*=0.5 是唯一的混合策略纳什均衡。12/9/202219l 由上面的例子可以看出，参与人选择的混合策略均使对方选择纯策略的期望效用相等，促使各方均采取严格策合策略。l 所

13、以求解混合策略纳什均衡也可以采取如下方法：求出参与人的每个纯策略的期望效用，令其相等即可得到混合策略纳什均衡。2.2.支付等值法求纳什均衡支付等值法求纳什均衡12/9/202220参与人1的选取正面的期望效用为 参与人1的选取反面的期望效用为 E1(正面)=(-1)r+1(1-r)=1-2 rE1(反面)=1 r+(-1)(1-r)=2 r-1令纯策略期望效用相等：1221rr得类似地，令参与人2的纯战略期望效用相等得：21r21q猜硬币博弈12/9/20222114)1)(1(3)1(010.2 14)1,(假定最优混合策略存在，给定流浪汉选择混合策略3，2-1，3-1，10，0流浪流浪流浪

14、汉流浪汉政政府府救济救济不救济不救济寻找工作寻找工作政府选择纯策略救济的期望效用为：选择纯策略不救济的效用为：如果一个混合策略(而不是纯策略)是政府的最优选择，一定意味着政府在救济与不救济之间是无差异的社会福利博弈 12/9/202222 在讨论连续纯策略均衡时(如古诺模型)，我们使用了反应函数的概念。现在我们可以使用反应对应的概念来描述一个参与人对应于其他参与人混合策略的最优选择。两个概念的区别仅仅在于：反应函数表示的是一个参与人只有一个特定的策略是其他人给定策略的最优选择；反应对应允许一个参与人有多个(甚至无穷多个)策略是其他人给定策略的最优选择。3.3.最优反应函数法求纳什均衡最优反应函

15、数法求纳什均衡12/9/202223 纯策略均衡：反应函数(reaction function)在纯策略的范畴内，最优反应函数是各博弈方选择的纯策略对其他博弈方纯策略的反应。纯策略纳什均衡是博弈方反应函数的交叉点。混合策略均衡：反应对应(reaction correspondence)在混合策略的范围内，博弈方的决策内容为选择概率分布，最优反应函数就是一方对另一方的概率分布的反应。由于纯策略可以理解为混合策略，因此实际上最优反应函数的概念，也可以在混合策略概率分布之间反应的意义上统一起来。混合战略纳什均衡也是反应函数的交叉点。12/9/202224混合策略反应函数混合策略反应函数猜硬币博弈-1

16、，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方正面反面盖盖硬硬币币方方rq111/21/2)(2rRq)(1qRr(r,1-r)：盖硬币方选择正反面的混合策略概率分布(q,1-q)：猜硬币方选择正反面的混合策略概率分布12/9/202225夫妻之争博弈2，10，00，01，3电影足球丈夫丈夫电影足球妻妻子子rq111/31/3)(2rRq)(1rRr 混合策略反应函数混合策略反应函数(r,1-r)：丈夫的混合策略概率分布(q,1-q)：妻子的混合策略概率分布12/9/202226例题例题 监督博弈监督博弈a-c+F,-a-Fa-c,-a0 ,0a,-a检查检查1-不检查不检查税收机关

17、税收机关逃税逃税 1-不不逃税逃税 纳税人纳税人 其中，其中，a:应纳税款，应纳税款，C:检查成本，检查成本，F:罚款，罚款，a-c+F:检查到逃税者检查到逃税者,-a-F:除了要交税款又要交罚款除了要交税款又要交罚款求MNE两种方法：支付最大化方法支付最大化方法(求一阶导数为求一阶导数为0)；支付等值法支付等值法(即选两个纯战略是没差异即选两个纯战略是没差异)假定假定Ca十十F，在这个假设下，不存在纯战略纳什均衡。让我们来求解混合战略纳什均衡。12/9/202227假定假定Ca十十F，在这个假设下，不存在纯战略纳什均衡。让我们来求解混合战略纳什均衡。a:应纳税款，C:检查成本，F:罚款，a-

18、c+F:检查到逃税者,-a-F:除了要交税款又要交罚款用表示税收机关检查的概率，表示纳税人逃税的概率检查不检查(1-)不逃税(1-)逃税FaFCa,aCa,0,0aa ,给定，税收机关选择检查(=1)和不检查(=0)的期望收益分别为：)1()1(*00)1)()1aaCaFCaFCaGG），（），（令),0(),1(GG12/9/202228给定给定，纳税人选择逃税和和不逃税的期望收益分别为：，纳税人选择逃税和和不逃税的期望收益分别为：检查检查不检查不检查(1-)不逃税不逃税(1-(1-)逃税逃税FaFCa,aCa,0,0aa,得得FaC*aaaFaFapp)1)(0)1(*0)1），（），（

19、令)0,()1,(Gp得Faa*Faa*FaC*因此，混合战略纳什均衡是：因此，混合战略纳什均衡是：税收机关以税收机关以 的概率检查，纳税人以的概率检查，纳税人以 的概率选择逃税。的概率选择逃税。FaaFaCFaa*FaC*aaaFaFMNEccaFaF即税收机关以的概率选择检查：即纳税人以的概率选择逃税结论：结论：当逃税概率),0(),1(,GGFac即则税收机关最优选择是不检查 检查概率 Faa纳税人选逃税。),0(),1(,GGFac即当逃税概率，则税收机关最优选择检查Faa检查概率，纳税人选纳税。而当 ，则纳税人选择纳税与不纳税无差异FaaFac当逃税概率，则税收机关随机地选择检查或不

20、检查无差异 另一解释是：社会中有许多个纳税人，其中有 比例的纳税人选择逃税，比例的纳税人选择不逃税；税收机关以 比例随机地检查纳税人的纳税情况。纳税人选逃税概率越小；检查成本C 越高，纳税人逃税的概率就越大。为什么应纳税款越多，纳税人逃税的概率反而越小呢？这是因为，应纳税款越多，税收机关检查的概率越高，逃税被抓住的可能性越大，因而纳税人反而不敢逃税了。这一点或许可以解释为什么逃税现象在小企业中比在大企业中更为普遍，在低收入阶层比在高收入阶层更普遍。Fac)1(FacFaaFa,12/9/202231即：每一个有限博弈至少存在一个纳什均衡。1.1.纳什定理纳什定理(Nash,1950)(Nash

21、,1950)：在一个有n个博弈方的博弈 中，nnuuSSG,;,11如果n是有限的，且Si 都是有限集，则该博弈至少存在一个纳什均衡(纯策略的或混合策略的)。现实中的博弈都是可以当作有限博弈来解决。这样纳什均衡现实中的博弈都是可以当作有限博弈来解决。这样纳什均衡的存在就是普遍的。纳什均衡的普遍存在性是纳什均衡概念最的存在就是普遍的。纳什均衡的普遍存在性是纳什均衡概念最重要的性质。重要的性质。4.3 4.3 纳什均衡的存在性定理纳什均衡的存在性定理12/9/2022322.2.纳什定理的推广纳什定理的推广 纳什均衡的存在性定理2：当博弈方个数有限，战略集是非空、闭的、有界的，支付函数是连续且拟凹

22、的，则博弈至少存在一个纯战略纳什均衡。(Debreu,1952;Clicksberg,1952;Fan,1952)纳什均衡的存在性定理3：当博弈方有限，战略集是非空、闭的、有界的，支付函数是连续的，则博弈至少存在一个纳什均衡(纯战略的或混合战略的)。(Clicksberg,1952)12/9/202233 尽管纳什均衡非常重要，但不是说学到了这种分析方法你就能预测所有博弈的结果。纳什均衡分析仅仅保证有个体理性的智能人的博弈结果是唯一纯策略纳什均衡时的预测。实际情况是纳什均衡分析并不能保证对所有博弈的结果都作出准确的预测。现实中的博弈可能是下面三种情况之一：1、有许多博弈不存在纯策略纳什均衡；2、有些博弈是多重纳什均衡；3、博弈方可能是集体理性或有限理性。此时纳什均衡分析就不是绝对有效的。对这些问题有不同程度的解决，例如，实验经济学和行为经济学的成果为寻找有限理性时的博弈均衡提供了支持。一些新的均衡概念，例如，帕累托上策均衡、风险上策均衡、聚点均衡和相关均衡等为多重纳什均衡时的决策找到了方向。3.3.纳什均衡应用的局限性纳什均衡应用的局限性12/9/202234不同均衡概念的关系不同均衡概念的关系占优均衡占优均衡DSE重复剔除占优均衡重复剔除占优均衡IEDE纯策略纳什均衡纯策略纳什均衡PNE混合策略纳什均衡混合策略纳什均衡MNE