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

1、第一部分： 完全信息静态博弈,第三章混合战略Nash均衡,主要内容： 一、混合战略； 二、混合战略Nash均衡； 三、混合战略Nash均衡的求解。,西北大学数学系,主要内容： 一、混合战略； 二、混合战略Nash均衡； 三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,西北大学数学系,一、混合战略,“猜硬币”博弈的例子 两个参与人各握有一枚硬币，双方同时选择是正面向上(记作O)还是背面向上(记作R)，即他们的战略空间都是O, R。若两枚硬币是一致的(即全部背面向上或者全部正面向上)，参与人2赢得参与人1的硬币；若两枚硬币不一致，则参与人1赢得参与人2的硬币。,西北大学数学系,西北大

2、学数学系,猜硬币博弈的特征： 每位参与人都想猜透对方的战略，而每位参与人又都不能让对方猜透自己的战略。,西北大学数学系,在“猜硬币”游戏中，我们会以50%的概率选择正面(O)，以50%的概率选择反面(R)。像这种以一定的概率分布来选择自己战略的行为，在博弈论中称之为混合战略(mixed strategy)。,西北大学数学系,纯战略： 参与人在给定信息下只选择一种特定战略(或行动)。,西北大学数学系,混合战略： 参与人给定信息下以某种概率分布随机地选择不同的行动。它可以定义为战略空间(集)上概率分布。,西北大学数学系,定义1：混合战略,在博弈 中，对任一参与人i，设 ，则参与人i的一个混合战略为

3、定义在战略集 上的一个概率分布 其中 表示参与人i选择战略 的概率，即 满足：,西北大学数学系,混合战略解释了一个参与人对其他参与人所采取的行动的不确定性，它描述了参与人在给定信息下以某种概率分布随机地选择不同的行动或战略。,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,支付,1) 纯战略时,西北大学数学系,2) 混合战略时： 其中， 为参与人j采取 中 的概率， 表示 发生的概率。,西北大学数学系,其中，,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,西北大学数学系,看下面的例子：,西北大学数学系,参与人1 的混合战略 参与人2 的混合战略

4、 ； 在混合战略组合 下，战略组合 、 、和 出现的概率就分别为 。,西北大学数学系,参与人1采用纯战略a1和a2的期望效用分别为 参与人1在混合战略组合=(1, 2)下的期望效用为,西北大学数学系,参与人2采用纯战略b1和b2的期望效用分别为 参与人2在混合战略组合=(1, 2)下的期望效用为,西北大学数学系,主要内容： 一、混合战略； 二、混合战略Nash均衡； 三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,西北大学数学系,二、混合战略Nash均衡,提一个问题： 在“猜硬币”游戏中，我们往往会以50%的概率选择正面(O)，以50%的概率选择反面(R)，即选择混合战略=(0.

5、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选择其它什么样的混合战略，只要

6、参与人1保持混合战略1=(0.5，0.5)不变，参与人2的期望收益都为0，不会增大。也就是说，偏离并不能给参与人2带来好处。 同理，偏离也不能给参与人1带来好处。,西北大学数学系,因此，在“猜硬币”博弈中，双方都不会偏离混合战略组合=(0.5，0.5),(0.5，0.5)。像这样的混合战略组合我们称之为混合战略Nash均衡。,西北大学数学系,定义2 ：混合战略Nash均衡,在博弈 中，混合战略组合 为一个Nash均衡，当且仅当 。,西北大学数学系,结论 ：,在博弈 中，混合战略组合 为一个Nash均衡，当且仅当 。,西北大学数学系,证明：(必要性)由于纯战略si可看做退化的混合战略，因此必要性

7、条件成立。 (充分性)由于 可得参与人i在混合战略 下的期望收益为 充分性得证。,西北大学数学系,考察如下战略式博弈：,显然，不存在纯战略的Nash均衡。,西北大学数学系,如果给定上面问题的一个混合战略：,参与人的收益分别为,西北大学数学系,参与人1的纯战略支付为：,显然，所给混合战略不小于任何一个纯战略的期望支付，因此，该混合战略为Nash均衡。,注意到，对于混合战略Nash均衡，参与人的每个纯战略支付等于混合战略支付。,西北大学数学系,考察如图的战略式博弈,2 b1 b2 a1 ( 2, 1) ( 0, 0) a2 ( 0, 0) ( 1, 2),1,显然，存在两个纯战略Nash均衡。,2

8、 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,在参与人的最优混合战略 中

9、，对 ，有,西北大学数学系,上述命题表明：,如果 是参与人i在给定对手选择混合战略 的最优混合战略，若混合战略规定参与人i以严格正概率选择纯战略 ，则 一定也是给定 下的一个最优战略。即所有以正概率进入最优混合战略的纯战略都是参与人i的最优战略，并且参与人i在所有这些纯战略之间一定是无差异的，也就是说参与人i的每一个正概率战略的期望支付是相等的。,西北大学数学系,相反的，如果参与人i有n个纯战略是最优的（支付相同），那么这些最优战略上的任一概率分布都是参与人i的最优混合战略。,西北大学数学系,在“猜硬币”游戏中，设参与人1的战略 为 ，参与人2的战略为 参与人1选择正面(O)的期望收益为 参与

10、人1选择反面(R)的期望收益为,西北大学数学系,由于当且仅当 时， ，因此，当 时，参与人l的最优纯战略为选择正面(O)；当 时选择反面(R)。而当 时，参与人1无论选择正面(O)还是反面(R)都是无差异的。不仅如此，参与人1此时无论以什么样的概率分布选择正面(O)和反面(R)都是无差异的。,西北大学数学系,给定参与人2的战略 的情况下，参与人1的最优反应 参与人1的期望收益在2-4q0时随p递增；在2-4q0时随p递减，因此，当 时，参与人1的最优反应 (即选择正面)；当 ，参与人1的最优反应 (即选择反面)。,西北大学数学系,西北大学数学系,支集：对于给定的参与人的混合战略i ，称i中所有

11、大于0的分量所对应的纯战略的集合为i的支集(记为 )，即,西北大学数学系,定理1：最优反应的引理,在有限n人战略式博弈 中，混合战略组合 为一个Nash均衡，当且仅当 ， 的支集 中每一个纯战略都是给定 下的最优反应。,西北大学数学系,可以根据最优反应引理求解两人两战略的战略式博弈的Nash均衡等值法。 例如：,西北大学数学系,根据最优战略的性质，有 即,西北大学数学系,求解上式可得 其中， ， 。,西北大学数学系,通过划线法可知下图所示博弈不存在纯战略Nash均衡。假设参与人1的混合战略为(p,1-p)参与人2的混合战略为(q,1-q)。 利用等值法可以得到 的结果,西北大学数学系,根据等值

12、法得,即,求解上式可得,西北大学数学系,通过划线法可知下图所示博弈存在纯战略Nash均衡(U, L)，(D, R)。假设参与人1的混合战略为(p,1-p)参与人2的混合战略为(q,1-q)。 利用等值法可以得到 的结果,西北大学数学系,根据等值法得,即,求解上式可得,西北大学数学系,主要内容： 一、混合战略； 二、混合战略Nash均衡； 三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,西北大学数学系,三、混合战略Nash均衡的求解,支撑求解法； 规划求解法；,西北大学数学系,1.支撑求解法,对于给定的有限n人战略式博弈 假设混合战略组合 为Nash均衡，考察 的支撑，对 ，设 ，

13、不失一般性，设 ，则参与人关于混合战略组合 的支集,西北大学数学系,1.支撑求解法,由最优反应的引理可得 其中， 为参与人i在混合战略Nash均衡下 的期望效用。,(1),西北大学数学系,1.支撑求解法,由概率分布的规范性条件，可得,(2),西北大学数学系,1.支撑求解法,给定的有限n人战略式博弈 支撑法求解Nash均衡的基本思路就是： 1) 构造出所有的混合战略均衡的支撑； 2) 对于每个给定的支撑，求解由(1)式和(2)式所确定的方程组。,西北大学数学系,1.支撑求解法,对于构造出来的支撑，在求解方程组的过程中，可能会出现以下问题： 1) 方程组的解不存在,原因在于所构造的支撑有问题，需要

14、构造新的支撑。 2) 解不满足非负性条件，即方程组的解虽然存在，但在解中存在小于0的情形。 3) 方程组的解存在，并且解都大于0，但对于给定的解， 与Nash均衡矛盾，即存在支撑战略期望效用小于非支撑战略期望效用的情况。,西北大学数学系,1.支撑求解法,例子：,不存在纯战略Nash均衡,不存在其支撑中只包含参与人一个战略的Nash均衡,西北大学数学系,可能的支撑包括,一个24战略组合： 四个23战略组合： 六个22战略组合：,西北大学数学系,假设支撑是24战略组合,各等式之间相互矛盾，因此不存在满足(1)式的解,西北大学数学系,假设支撑是23战略组合,各等式之间相互矛盾，因此不存在满足(1)式

15、的解,基于同样的原因， 、 和 都不可能为博弈的均衡支撑。,西北大学数学系,假设支撑是22战略组合,联立求解上述方程组，可得,给定 ， 参与人2选择纯战略C和D的所得大于在均衡中的所得。,西北大学数学系,假设支撑是22战略组合,联立求解上述方程组，可得,给定 ， 参与人2选择纯战略C和D的所得大于在均衡中的所得。 基于同样的原因 不是支撑。,西北大学数学系,假设支撑是22战略组合,联立求解上述方程组，可得,不满足非负性条件,基于同样的原因， 不可能为博弈的均衡支撑。,西北大学数学系,假设支撑是22战略组合,联立求解上述方程组，可得,给定 ， 参与人2选择纯战略A和C的所得小于在均衡中的所得。,

16、混合战略Nash均衡,西北大学数学系,1.支撑求解法,如果无法事前确定博弈的均衡支撑，那么就只能对所有可能的支撑逐一进行计算，从而使得计算量十分巨大。 如果能够在求解Nash均衡之前，就确定博弈的均衡支撑，那么就可以使计算量大大减少。 事实上，对于给定的支撑，在计算之前进行简单的分析，就有可能判断出给定的支撑是否合理，从而排除不合理的支撑，减少计算量。,西北大学数学系,支撑求解法存在的问题,由于目前尚未找到有效的判断博弈问题均衡支撑的简捷方法，随着博弈问题中参与人人数的增加以及战略空间的增大，判断均衡支撑的工作就会变得十分繁冗，因此，支撑求解法的运算量一般都会很大，即使对于我们经常讨论的两人有

17、限博弈问题也是如此。 因此，在利用支撑求解法的过程中，存在计算复杂性问题。,西北大学数学系,2.规划求解法,所谓规划求解法就是将求解博弈的混合战略Nash均衡，转换为一个规划问题进行求解。相对于支撑求解法，规划求解法对两人有限博弈问题的Nash均衡求解尤为有效。,西北大学数学系,2.规划求解法,在一个两人有限战略式博弈中： 设 ， 。 用矩阵 表示参与人1的支付，其中 表示参与人1在战略组合 下的支付，即 用矩阵 表示参与人2的支付，其中 表示参与人2在战略组合 下的支付，即 。设参与人1和2的混合战略分别为 和 ，则 ， 。,西北大学数学系,2.规划求解法,一个两人有限战略式博弈的Nash均

18、衡可以通过求解以下规划问题得到：,西北大学数学系,2.规划求解法,Em和En分别表示矩阵(1,1)1m和(1,1)1n ， 和 分别表示参与人1和2在Nash均衡下的期望支付。,西北大学数学系,2.规划求解法,其中， 表示在均衡下，参与人1采用任一纯战略得到的期望收益不大于均衡收益 即 表示在均衡下，参与人2采用任一纯战略得到的期望收益不大于均衡收益 ，即 在目标函数中， 和 意味着如果参与人1和2的选择不是均衡战略的话，目标函数就永远无法达到最优。,西北大学数学系,2.规划法求解混合战略Nash均衡,西北大学数学系,2.规划求解法,参与人1的支付矩阵为 参与人2的支付矩阵为,西北大学数学系,

19、2.规划求解法,参与人1和参与人2的混合战略分别是 和 ， 和 分别表示参与人1和2在Nash均衡下的期望支付。,西北大学数学系,利用规划求解方法求解该战略式博弈，构造规划问题如下,西北大学数学系,2.规划求解法,求解上述规划问题，可得博弈的三个Nash均衡，其中一个纯战略Nash均衡 和两个混合战略Nash均衡 和,西北大学数学系,2.规划求解法,有限人战略式博弈 。 对 ，设 ， 。 求解下列规划问题即可得到博弈的解： 其中， 为参与人在Nash均衡下的期望支付。,西北大学数学系,规划法求解多人战略式博弈的混合战略Nash均衡,参与人1的混合战略为 ，参与人2的混合战略为 ，参与人3的混合

20、战略为 。,西北大学数学系,2.规划求解法,西北大学数学系,2.规划求解法,，,，,，,西北大学数学系,2.规划求解法,其中， ， 和 分别表示参与人1，2和3在Nash均衡下的期望支付。,西北大学数学系,2.规划求解法,求解上述规划问题，可得博弈的六个纯战略Nash均衡 和一个混合战略Nash均衡 。,西北大学数学系,三、零和博弈,所谓零和博弈，是指在任何博弈情形下两个参与人的支付之和为零。,西北大学数学系,猜硬币游戏： 2 q (正面) 1-q (反面) p (正面) ( 1, -1) (-1, 1) 1-p (反面) (-1, 1) ( 1, -1),“石头、剪刀、布”游戏 2 石头 剪

21、刀 布 石头 （0,0） （1，-1） （-1,1） 1 剪刀 （-1,1） （0,0） （1，-1） 布（1，-1） （-1,1） （0,0）,西北大学数学系,零和博弈的支付矩阵：,基于零和博弈的定义，一个参与人的所得一定是另一个参与人的损失，因此，如果用U标示参与人1的支付矩阵，则参与人2的支付矩阵为-U，因此，零和博弈中如果给出了支付矩阵U（以下总假设U标示参与人1的支付），就意味着给出了两个参与人的支付。,西北大学数学系,零和博弈中参与人的极大极小化行为,给定参与人1的任一选择ai，参与人2选择战略使自己支付最大化的行为(即 )，就是选择战略使参与人1的支付最小化的行为(即 ) 由于在

22、任一情况下，参与人2都选择使参与人1的支付最小化的战略 ，因此，参与人1就会在使自己支付最小化的战略中，选择使自己的支付达到最大化所对应的战略 。,西北大学数学系,零和博弈中参与人的极大极小化行为,给定参与人2的任一选择bj，参与人1选择战略 ，与此同时，参与人2在使自己支付最小化(即参与人1支付最大化)的战略中，选择使自己的支付达到最大化(即损失降到最小)所对应的战略 。,西北大学数学系,规划求解法,参与人2的行为,0,max,min,参与人1的行为,西北大学数学系,定义4：鞍点,对于给定的零和博弈的支付矩阵，如果存在某个i*和j* ，使得 那么我们称i*行j*列所对应的点为支付矩阵U的鞍点

23、(saddle point)。,西北大学数学系,定理2,在零和博弈中，如果支付矩阵存在鞍点，那么鞍点所对应的战略组合就是博弈的Nash均衡。,为什么？,西北大学数学系,作为参与人1而言： 当固定参与人2的战略时（b3），当前选择（a2）是其最优战略，任何的偏离（a1或a3），不会给其带来好处。,作为参与人2而言： 当固定参与人1的战略时（a2），当前选择（b3）是其最优战略，任何的偏离（b1或b2），不会给其带来好处。,西北大学数学系,规划求解法,不存在定义3.4所定义的鞍点的零和博弈问题，需要定义混合战略意义下的鞍点。,西北大学数学系,定义5,对于给定的零和博弈的支付矩阵，如果存在参与人1的某个混合战略 和参与人2某个混合战略 ，使得 那么称战略组合 为支付矩阵U的鞍点。,西北大学数学系,定理3：Von Neumann极小极大定理,在零和博弈中，对于给定的支付矩阵，如果存在混合战略 和 以及一个常数v，使得对任意j有 ，对任意i有 ，那么战略组合 为该博弈的Nash均衡。其中，v为参与人1在均衡中所得到的期望支付，亦称该博弈的值。,西北大学数学系,定理4,对于