《第3章混合战略Nash均衡.ppt》由会员分享，可在线阅读，更多相关《第3章混合战略Nash均衡.ppt（102页珍藏版）》请在三一办公上搜索。
1、第一部分：完全信息静态博弈,第三章混合战略Nash均衡,主要内容：一、混合战略；二、混合战略Nash均衡；三、混合战略Nash均衡的求解。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,主要内容：一、混合战略；二、混合战略Nash均衡；三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,一、混合战略,“猜硬币”博弈 两个参与人各握有一枚硬
2、币，双方同时选择是正面向上(记作O)还是背面向上(记作R)，即他们的战略空间都是O,R。若两枚硬币是一致的(即全部背面向上或者全部正面向上)，参与人2赢得参与人1的硬币；若两枚硬币不一致，则参与人1赢得参与人2的硬币。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,猜硬币博弈的特征：每位参与人都想猜透对方的战略，而每位参与人又都不能让对方猜透自己的
3、战略。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,在“猜硬币”游戏中，我们会以50%的概率选择正面(O)，以50%的概率选择反面(R)。像这种以一定的概率分布来选择自己战略的行为，在博弈论中称之为混合战略(mixed strategy)。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,纯战略：参与人在给定信息下只选择一种特定战略(或行动)。,Control Science and Engi
4、neering,HUST All Rights Reserved,2007,Luo Yunfeng,混合战略：参与人给定信息下以某种概率分布随机地选择不同的行动。它可以定义为战略空间(集)上概率分布。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定义1：混合战略,在博弈 中，对任一参与人i，设，则参与人i的一个混合战略为定义在战略集 上的一个概率分布 其中 表示参与人i选择战略 的概率，即 满足：,Control Science and Engineering,HUST All Rights
5、 Reserved,2007,Luo Yunfeng,混合战略解释了一个参与人对其他参与人所采取的行动的不确定性，它描述了参与人在给定信息下以某种概率分布随机地选择不同的行动或战略。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,200
6、7,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,支付,1)纯战略时,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2)混合战略时：其中，为参与人j采取中 的概率，表示 发生的概率。,Control Science and
7、Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,其中，,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and
8、Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,看下面的例子：,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,参与人1 的混合战略 参与人2 的混合战略；在混合战略组合 下，战略组合、和 出现的概率就分别为。,Control Science and Engineering,HUST All
9、 Rights Reserved,2007,Luo Yunfeng,参与人1采用纯战略a1和a2的期望效用分别为参与人1在混合战略组合=(1,2)下的期望效用为,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,参与人2采用纯战略b1和b2的期望效用分别为参与人2在混合战略组合=(1,2)下的期望效用为,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,主要内容：一、混合战略；二、混合战略Nash均衡
10、；三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,二、混合战略Nash均衡,提一个问题：在“猜硬币”游戏中，我们往往会以50%的概率选择正面(O)，以50%的概率选择反面(R)，即选择混合战略=(0.5，0.5)。那么有没有参与人会偏离混合战略i=(0.5，0.5)呢？,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,在“猜硬币”博弈中
11、，当双方都选择混合战略 i=(0.5，0.5)时，双方的期望收益都为0。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,如果参与人1保持混合战略1=(0.5，0.5)，那么无论参与人2选择其它什么样的混合战略，只要参与人1保持混合战略1=(0.5，0.5)不变，参与人2的期望收益都为0，不会增大。也就是说，偏离并不能给参与人2带来好处。同理，偏离也不能给参与人1带来好处。,Control Science and Engineering,HUST All Rights Reserved,2007
12、,Luo Yunfeng,因此，在“猜硬币”博弈中，双方都不会偏离混合战略组合=(0.5，0.5),(0.5，0.5)。像这样的混合战略组合我们称之为混合战略Nash均衡。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定义2：混合战略Nash均衡,在博弈 中，混合战略组合 为一个Nash均衡，当且仅当。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and E
13、ngineering,HUST All Rights Reserved,2007,Luo Yunfeng,对简单的博弈问题，容易根据定义判断出Nash均衡。但对于一些复杂的博弈问题，要找到Nash均衡尤其是混合战略Nash均衡是非常不容易的。为了求解混合战略Nash均衡，必须了解在选择混合战略的情况下，参与人如何剔除劣战略以及参与人最优混合战略的特性。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,参与人i的最优混合战略的构成：给定其他参与人的选择-i，假设 为参与人i的最优混合战略，那么 有
14、,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,命题1,在参与人的最优混合战略 中，对，有,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,无论参与人1的选择1=(p，1-p)如何，参与人2选择2=(0.5，0.5，0)的所得为2.5，大于选择的所得2。所以，2=(0.5，0.5，0)相对于b3占优，也就是说，在参与人可以选择混合战略的情况下，b3成为劣战略。,Control Science a
15、nd Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,在“猜硬币”游戏中，设参与人1的战略 为，参与人2的战略为 参与人1选择正面(O)的期望收益为参与人1选择反面(R)的期望收益为,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,由于当且仅当 时，因此，当 时，参与人l的最优纯战略为选择正面(O)；当 时选择反面(R)。而当 时，参与人1无论选择正面(O)还是反面(R)都是无差异的。不仅如此，参与人1此时无论以什么样的概率分布选择正面
16、(O)和反面(R)都是无差异的。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,给定参与人2的战略 的情况下，参与人1的最优反应 参与人1的期望收益在2-4q0时随p递增；在2-4q0时随p递减，因此，当 时，参与人1的最优反应(即选择正面)；当，参与人1的最优反应(即选择反面)。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,H
17、UST All Rights Reserved,2007,Luo Yunfeng,可得参与人1的最优反应 为：为参与人1的最优反应响应(best correspondence)，而不是最优反应函数。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,支集：对于给定的参与人的混合战略i，称i中所有大于0的分量所对应的纯战略的集合为i的支集(记为)，即,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定
18、理1：最优反应的引理,在有限n人战略式博弈 中，混合战略组合 为一个Nash均衡，当且仅当，的支集 中每一个纯战略都是给定 下的最优反应。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,可以根据最优反应引理求解两人两战略的战略式博弈的Nash均衡等值法。例如：,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,根据最优战略的性质，有即,Control Science and Engineering
19、,HUST All Rights Reserved,2007,Luo Yunfeng,求解上式可得其中，。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,通过划线法可知下图所示博弈不存在纯战略Nash均衡。假设参与人1的混合战略为(p,1-p)参与人2的混合战略为(q,1-q)。利用式(1)可得利用等值法同样可以得到 的结果,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,根据等值法得,即,求解
20、上式可得,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,通过划线法可知下图所示博弈存在纯战略Nash均衡(U,L)，(D,R)。假设参与人1的混合战略为(p,1-p)参与人2的混合战略为(q,1-q)。利用式(1)可得利用等值法同样可以得到 的结果,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,根据等值法得,即,求解上式可得,Control Science and Engineering,HU
21、ST All Rights Reserved,2007,Luo Yunfeng,Wilson奇数定理(oddness theorem),Wilson奇数定理：几乎所有的有限战略式博弈都有有限奇数个Nash均衡。注意，Wilson奇数定理并没有肯定在任何情况下都有有限奇数个Nash均衡，在某些情况下仍有可能存在偶数个Nash均衡。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,主要内容：一、混合战略；二、混合战略Nash均衡；三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,Cont
22、rol Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,三、混合战略Nash均衡的求解,支撑求解法；规划求解法；,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,1.支撑求解法,对于给定的有限n人战略式博弈 假设混合战略组合 为Nash均衡，考察 的支撑，对，设，不失一般性，设，则参与人关于混合战略组合 的支集,Control Science and Engineering,HUST All Rights Res
23、erved,2007,Luo Yunfeng,1.支撑求解法,由最优反应的引理可得其中，为参与人i在混合战略Nash均衡下 的期望效用。,(1),Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,1.支撑求解法,由概率分布的规范性条件，可得,(2),Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,1.支撑求解法,给定的有限n人战略式博弈 支撑法求解Nash均衡的基本思路就是：1)构造出所有的混合战略
24、均衡的支撑；2)对于每个给定的支撑，求解由(1)式和(2)式所确定的方程组。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,1.支撑求解法,对于构造出来的支撑，在求解方程组的过程中，可能会出现以下问题：1)方程组的解不存在,原因在于所构造的支撑有问题，需要构造新的支撑。2)解不满足非负性条件，即方程组的解虽然存在，但在解中存在小于0的情形。3)方程组的解存在，并且解都大于0，但对于给定的解，与Nash均衡矛盾，即存在支撑战略期望效用小于非支撑战略期望效用的情况。,Control Science
25、 and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,1.支撑求解法,例子：,不存在纯战略Nash均衡,不存在其支撑中只包含参与人一个战略的Nash均衡,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,可能的支撑包括,一个24战略组合：四个23战略组合：六个22战略组合：,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,假设支撑是24
26、战略组合,各等式之间相互矛盾，因此不存在满足(1)式的解,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,假设支撑是23战略组合,各等式之间相互矛盾，因此不存在满足(1)式的解,基于同样的原因，、和 都不可能为博弈的均衡支撑。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,假设支撑是22战略组合,联立求解上述方程组，可得,给定，参与人2选择纯战略C和D的所得大于在均衡中的所得。,Control
27、Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,假设支撑是22战略组合,联立求解上述方程组，可得,给定，参与人2选择纯战略C和D的所得大于在均衡中的所得。基于同样的原因 不是支撑。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,假设支撑是22战略组合,联立求解上述方程组，可得,不满足非负性条件,基于同样的原因，不可能为博弈的均衡支撑。,Control Science and Engineering,HUST A
28、ll Rights Reserved,2007,Luo Yunfeng,假设支撑是22战略组合,联立求解上述方程组，可得,给定，参与人2选择纯战略A和C的所得小于在均衡中的所得。,混合战略Nash均衡,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,1.支撑求解法,如果无法事前确定博弈的均衡支撑，那么就只能对所有可能的支撑逐一进行计算，从而使得计算量十分巨大。如果能够在求解Nash均衡之前，就确定博弈的均衡支撑，那么就可以使计算量大大减少。事实上，对于给定的支撑，在计算之前进行简单的分析，就有可
29、能判断出给定的支撑是否合理，从而排除不合理的支撑，减少计算量。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,支撑求解法存在的问题,由于目前尚未找到有效的判断博弈问题均衡支撑的简捷方法，随着博弈问题中参与人人数的增加以及战略空间的增大，判断均衡支撑的工作就会变得十分繁冗，因此，支撑求解法的运算量一般都会很大，即使对于我们经常讨论的两人有限博弈问题也是如此。因此，在利用支撑求解法的过程中，存在计算复杂性问题。,Control Science and Engineering,HUST All Ri
30、ghts Reserved,2007,Luo Yunfeng,2.规划求解法,所谓规划求解法就是将求解博弈的混合战略Nash均衡，转换为一个规划问题进行求解。相对于支撑求解法，规划求解法对两人有限博弈问题的Nash均衡求解尤为有效。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,在一个两人有限战略式博弈中：设，。用矩阵 表示参与人1的支付，其中 表示参与人1在战略组合 下的支付，即 用矩阵 表示参与人2的支付，其中 表示参与人2在战略组合 下的支付，即。设参与人1和2的混合战略
31、分别为 和，则，。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,一个两人有限战略式博弈的Nash均衡可以通过求解以下规划问题得到：,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,Em和En分别表示矩阵(1,1)1m和(1,1)1n，和 分别表示参与人1和2在Nash均衡下的期望支付。,Control Science and Engineering,HUST A
32、ll Rights Reserved,2007,Luo Yunfeng,2.规划求解法,其中，表示在均衡下，参与人1采用任一纯战略得到的期望收益不大于均衡收益 即 表示在均衡下，参与人2采用任一纯战略得到的期望收益不大于均衡收益，即在目标函数中，和 意味着如果参与人1和2的选择不是均衡战略的话，目标函数就永远无法达到最优。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划法求解混合战略Nash均衡,Control Science and Engineering,HUST All Righ
33、ts Reserved,2007,Luo Yunfeng,2.规划求解法,参与人1的支付矩阵为 参与人2的支付矩阵为,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,参与人1和参与人2的混合战略分别是 和，和 分别表示参与人1和2在Nash均衡下的期望支付。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,利用规划求解方法求解该战略式博弈，构造规划问题如下,Control Scie
34、nce and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,求解上述规划问题，可得博弈的三个Nash均衡，其中一个纯战略Nash均衡 和两个混合战略Nash均衡 和,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,有限人战略式博弈。对，设，。求解下列规划问题即可得到博弈的解：其中，为参与人在Nash均衡下的期望支付。,Control Science and Engineering,HUST All R
35、ights Reserved,2007,Luo Yunfeng,规划法求解多人战略式博弈的混合战略Nash均衡,参与人1的混合战略为，参与人2的混合战略为，参与人3的混合战略为。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,，,，,，,Control Science and Engineering,HUST All
36、 Rights Reserved,2007,Luo Yunfeng,2.规划求解法,其中，和 分别表示参与人1，2和3在Nash均衡下的期望支付。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2.规划求解法,求解上述规划问题，可得博弈的六个纯战略Nash均衡 和一个混合战略Nash均衡。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,零和博弈中参与人的极大极小化行为,给定参与人1的任一选择a
37、i，参与人2选择战略使自己支付最大化的行为(即)，就是选择战略使参与人1的支付最小化的行为(即)由于在任一情况下，参与人2都选择使参与人1的支付最小化的战略，因此，参与人1就会在使自己支付最小化的战略中，选择使自己的支付达到最大化所对应的战略。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,零和博弈中参与人的极大极小化行为,给定参与人2的任一选择bj，参与人1选择战略，与此同时，参与人2在使自己支付最小化(即参与人1支付最大化)的战略中，选择使自己的支付达到最大化(即损失降到最小)所对应的战略
38、。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,规划求解法,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定义4：鞍点,对于给定的零和博弈的支付矩阵，如果存在某个i*和j*，使得 那么我们称i*行j*列所对应的点为支付矩阵U的鞍点(saddle point)。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo
39、Yunfeng,定理2,在零和博弈中，如果支付矩阵存在鞍点，那么鞍点所对应的战略组合就是博弈的Nash均衡。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,规划求解法,不存在定义3.4所定义的鞍点的零和博弈问题，需要定义混合战略意义下的鞍点。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定义5,对于给定的零和博弈的支付矩阵，如果存在参与人1的某个混合战略 和参与人2某个混合战略，使得 那么称
40、战略组合 为支付矩阵U的鞍点。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定理3：Von Neumann极小极大定理,在零和博弈中，对于给定的支付矩阵，如果存在混合战略 和 以及一个常数v，使得对任意j有，对任意i有，那么战略组合 为该博弈的Nash均衡。其中，v为参与人1在均衡中所得到的期望支付，亦称该博弈的值。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定理4,对于给定的零和博弈，
41、如果博弈的值大于0，则博弈的Nash均衡为以下对偶线性规划问题的解 其中，Nash均衡支付，Nash均衡战略,和,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,规划求解法,命题2：如果支付矩阵的每个元素都大于0，即aij 0，那么博弈的值大于0，即v0。命题3：如果支付矩阵 是由 的每个元素都加上一个常数c得到，即 那么支付矩阵U和U所对应的零和博弈的Nash均衡战略相同，博弈的值相差c。,Control Science and Engineering,HUST All Rights Rese
42、rved,2007,Luo Yunfeng,规划求解法,根据上述命题，我们可以得到求解一般零和博弈Nash均衡的方法：(1)使支付矩阵中的所有元素都大于0。如果支付矩阵中有小于0的元素，可以通过加上一个常数使它们都大于0；(2)求解定理3.4中的两个对偶线性规划问题。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,规划求解法,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,规划求解法,设参与人1
43、和参与人2的混合战略分别是 和，利用对偶线性规划求解方法求解该战略式博弈的Nash均衡，构造规划问题如下：,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,规划求解法,设参与人1和参与人2的混合战略分别是和，利用对偶线性规划求解方法求解该战略式博弈的Nash均衡，构造规划问题如下。,和,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,得到，参与人1的支付v=2，参与人1的混合战略。对对偶问题求解，
44、得到 参与人2的损失v=2，因此，参与人2的混合战略 所以，该博弈存在一个混合战略Nash均衡,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,规划求解法,从理论上来讲，这两种方法对有限战略式博弈都是适用的，但从以上例子的求解过程来看，都存在着计算过程复杂，计算量大等问题，尤其是对多人(即参与人人数大于2)博弈问题。当参与人人数大于2时，使用支撑法，就必须求解非线性方程组；而使用规划法，就必须求解一个无论是目标函数还是约束条件都是非线性的规划问题。总而言之，博弈均衡的计算问题是目前博弈论研究中没有得到很好解决的问题。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,本章结束,
