第3章 混合战略Nash均衡.ppt

,西北大学数学系,第一部分：,完全信息静态博弈,第三章混合战略,Nash,均衡,主要内容：,一、混合战略；,二、混合战略,Nash,均衡；,三、混合战略,Nash,均衡的求解。,主要内容：,一、混合战略；,二、混合战略,Nash,均衡；,三、混合战略,Nash,均衡的求解。,第三章混合战略,Nash,均衡,西北大学数学系,一、,混合战略,“猜硬币”博弈的例子,两个参与人各握有一枚硬币，双方同时选择是正面向上,(,记作,O,),还是背面向上,(,记作,R,),，即他们的战略空间都是,O,R,。若两枚硬币是一致的,(,即全部背面向上或者全部正面向上,),，参与人,2,赢得参与人,1,的硬币；若两枚硬币不一致，则参与人,1,赢得参与人,2,的硬币。,西北大学数学系,西北大学数学系,猜硬币博弈的特征：,每位参与人都想猜透对方的战略，而每位参与人又都不能让对方猜透自己的战略。,西北大学数学系,在“猜硬币”游戏中，我们会以,50%,的概率选择正面,(,O,),，以,50%,的概率选择反面,(,R,),。像这种以一定的概率分布来选择自己战略的行为，在博弈论中称之为,混合战略,(mixed strategy),。,西北大学数学系,纯战略：,参与人在给定信息下只选择一种特定战略,(,或行动,),。,西北大学数学系,混合战略：,参与人给定信息下,以某种概率分布,随机地选择不同的行动。它可以定义为战略空间,(,集,),上概率分布。,西北大学数学系,定义,1,：混合战略,在博弈 中，对任一参与人,i,，设 ，则参与人,i,的一个混合战略为定义在战略集 上的一个概率分布,其中 表示参与人,i,选择战略 的概率，即 满足：,西北大学数学系,混合战略解释了一个参与人对其他参与人所采取的行动的不确定性，它描述了参与人在给定信息下以某种概率分布随机地选择不同的行动或战略。,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,支付,1),纯战略时,西北大学数学系,2),混合战略时：,其中，为参与人,j,采取,中 的概率，表示 发生的概率。,西北大学数学系,其中，,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,看下面的例子：,西北大学数学系,参与人,1,的混合战略 参与人,2,的混合战略,；,在混合战略组合 下，战略组合,、和 出现的概率就分别为 。,西北大学数学系,参与人,1,采用纯战略,a,1,和,a,2,的期望效用分别为,参与人,1,在混合战略组合,=,(,1,2,),下的期望效用为,西北大学数学系,参与人,2,采用纯战略,b,1,和,b,2,的期望效用分别为,参与人,2,在混合战略组合,=,(,1,2,),下的期望效用为,西北大学数学系,主要内容：,一、混合战略；,二、混合战略,Nash,均衡；,三、混合战略,Nash,均衡的求解。,第三章混合战略,Nash,均衡,西北大学数学系,二、混合战略,Nash,均衡,提一个问题：,在“猜硬币,”,游戏中，我们往往会以,50%,的概率选择正面,(,O,),，以,50%,的概率选择反面,(,R,),，即选择混合战略,=(0.5,，,0.5),。那么有没有参与人会偏离混合战略,i,=(0.5,，,0.5),呢？,西北大学数学系,猜硬币游戏的期望收益：,2,q(,正面,)1-q(,反面,),p(,正面,)(1,-1)(-1,1),1-p(,反面,)(-1,1)(1,-1),1,西北大学数学系,参与人,1,在混合战略组合,=,(p,1-p),下的期望效用为,参与人,2,在混合战略组合,=,(q,1-q),下的期望效用为,西北大学数学系,在“猜硬币”博弈中，当双方都选择混合战略,i,=(0.5,，,0.5),时，双方的期望收益都为,0,。,西北大学数学系,如果参与人,1,保持混合战略,1,=(0.5,，,0.5),，那么无论参与人,2,选择其它什么样的混合战略，只要参与人,1,保持混合战略,1,=(0.5,，,0.5),不变，参与人,2,的期望收益都为,0,，不会增大。也就是说，偏离并不能给参与人,2,带来好处。,同理，偏离也不能给参与人,1,带来好处。,西北大学数学系,因此，在“猜硬币”博弈中，双方都不会偏离混合战略组合,=(0.5,，,0.5),(0.5,，,0.5),。像这样的混合战略组合我们称之为,混合战略,Nash,均衡,。,西北大学数学系,定义,2,：混合战略,Nash,均衡,在博弈 中，混合战略组合 为一个,Nash,均衡，当且仅当 。,西北大学数学系,结论,：,在博弈 中，混合战略组合 为一个,Nash,均衡，当且仅当 。,西北大学数学系,证明：,(,必要性,),由于纯战略,si,可看做退化的混合战略，因此必要性条件成立。,(,充分性,),由于,可得参与人,i,在混合战略 下的期望收益为,充分性得证。,西北大学数学系,考察如下战略式博弈：,显然，不存在纯战略的,Nash,均衡。,西北大学数学系,如果给定上面问题的一个混合战略：,参与人的收益分别为,西北大学数学系,参与人,1,的纯战略支付为：,显然，所给混合战略不小于任何一个纯战略的期望支付，因此，该混合战略为,Nash,均衡。,注意到，对于混合战略,Nash,均衡，参与人的每个纯战略支付等于混合战略支付。,西北大学数学系,考察如图的战略式博弈,2,b1 b2,a1 (2,1)(0,0),a2 (0,0)(1,2),1,显然，存在两个纯战略,Nash,均衡。,2,1/3 2/3,b1 b2,2/3 a1 (2,1)(0,0),1/3 a2 (0,0)(1,2),1,可以验证上述混合战略也是,Nash,均衡。,西北大学数学系,对简单的博弈问题，容易根据定义判断出,Nash,均衡。但对于一些复杂的博弈问题，要找到,Nash,均衡尤其是混合战略,Nash,均衡是非常不容易的。,为了求解混合战略,Nash,均衡，必须了解在选择混合战略的情况下，参与人如何剔除劣战略以及参与人最优混合战略的特性。,西北大学数学系,参与人,i,的最优混合战略的构成：给定其他参与人的选择,-i,，假设 为参与人,i,的最优混合战略，那么 有,西北大学数学系,命题,1,在参与人的最优混合战略 中，对 ，有,西北大学数学系,上述命题表明：,如果 是参与人,i,在给定对手选择混合战略,的最优混合战略，若混合战略规定参与人,i,以严格正概率选择纯战略 ，则 一定也是给定 下的一个最优战略。即所有以正概率进入最优混合战略的纯战略都是参与人,i,的最优战略，并且参与人,i,在所有这些纯战略之间一定是无差异的，也就是说参与人,i,的每一个正概率战略的期望支付是相等的。,西北大学数学系,相反的，如果参与人,i,有,n,个纯战略是最优的（支付相同），那么这些最优战略上的任一概率分布都是参与人,i,的最优混合战略。,西北大学数学系,在“猜硬币”游戏中，设参与人,1,的战略,为 ，参与人,2,的战略为,参与人,1,选择正面,(,O,),的期望收益为,参与人,1,选择反面,(,R,),的期望收益为,西北大学数学系,由于当且仅当 时，因此，当 时，参与人,l,的最优纯战略为选择正面,(,O,),；当 时选择反面,(,R,),。而当 时，参与人,1,无论选择正面,(,O,),还是反面,(,R,),都是无差异的。不仅如此，参与人,1,此时无论以什么样的概率分布选择正面,(,O,),和反面,(,R,),都是无差异的。,西北大学数学系,给定参与人,2,的战略 的情况下，参与人,1,的最优反应,参与人,1,的期望收益在,2-4,q,0,时随,p,递增；在,2-4,q0,，那么博弈的值大于,0,，即,v,0,。,命题,3,：,如果支付矩阵 是由 的每个元素都加上一个常数,c,得到，即 那么支付矩阵,U,和,U,所对应的零和博弈的,Nash,均衡战略相同，博弈的值相差,c,。,西北大学数学系,规划求解法,根据上述命题，我们可以得到求解一般零和博弈,Nash,均衡的方法：,(1),使支付矩阵中的所有元素都大于,0,。如果支付矩阵中有小于,0,的元素，可以通过加上一个常数使它们都大于,0,；,(2),求解定理,3.4,中的两个对偶线性规划问题。,西北大学数学系,规划求解法,西北大学数学系,规划求解法,设参与人,1,和参与人,2,的混合战略分别是 和 ，利用对偶线性规划求解方法求解该战略式博弈的,Nash,均衡，构造规划问题如下：,西北大学数学系,规划求解法,设参与人,1,和参与人,2,的混合战略分别是和，利用对偶线性规划求解方法求解该战略式博弈的,Nash,均衡，构造规划问题如下。,和,西北大学数学系,得到 ，参与人,1,的支付,v,=2,，参与人,1,的混合战略 。,对对偶问题求解，得到 参与人,2,的损失,v,=2,，因此，参与人,2,的混合战略 所以，该博弈存在一个混合战略,Nash,均衡,西北大学数学系,规划求解法,从理论上来讲，这两种方法对有限战略式博弈都是适用的，但从以上例子的求解过程来看，都存在着计算过程复杂，计算量大等问题，尤其是对多人,(,即参与人人数大于,2),博弈问题。当参与人人数大于,2,时，使用支撑法，就必须求解非线性方程组；而使用规划法，就必须求解一个无论是目标函数还是约束条件都是非线性的规划问题。总而言之，博弈均衡的计算问题是目前博弈论研究中没有得到很好解决的问题。,西北大学数学系,本章结束,西北大学数学系,