混合策略纳什均衡(上)XXXX

北京邮电大学本科选修课程《信息经济学》高丛[e-mail]混合策略纳什均衡在纳什均衡不存在或者不唯一的情形，2013年10月29日新浪微博：一花一世界economics2前面介绍的纳什均衡的定义和寻找纳什均衡的方法，就不足以帮助我们对博弈的最终结果作出明确的预测，无法给参与博弈的局中人提供明确的决策建议。因此，我们需要拓展纳什均衡的概念，引入新的分析工具，对存在多个纳什均衡的博弈和“不存在”纳什均衡的博弈作进一步的讨论。本章内容：2013年10月29日新浪微博：一花一世界economics3本章首先引入混合策略和期望支付的概念，在此基础上定义混合策略纳什均衡，然后具体介绍求解纳什均衡的反应函数法，并给出混合策略纳什均衡的直观解释。我们讨论多重纳什均衡的问题及其筛选标准。第三章混合策略纳什均衡2013年10月29日新浪微博：一花一世界economics43—1混合策略与期望支付3—2反应函数法3—3高维情形和代数方法3—4纳什定理和奇数定理3—5多重纳什均衡及其甄别3—1混合策略与期望支付2013年10月29日新浪微博：一花一世界economics5我们考虑一个“扑克牌对色游戏”（gameofcolormatching）：两人博弈，每人从自己的扑克牌中抽一张出来，一起翻开。如果颜色一样，甲输给乙一根火柴；如果颜色不一样，甲赢得乙一根火柴。为了确定起见，我们不允许出“大鬼”和“小鬼”。“扑克牌对色游戏”1－1－11－111－12013年10月29日新浪微博：一花一世界economics6甲乙红黑红黑博弈论最重要的问题就是寻求博弈的稳定结果上面这个简单的例子，给我们提出了一个很重要的问题，就是如何解决按照前面两章的定义和方法“不存在”纳什均衡和“找不到”纳什均衡的博弈问题。2013年10月29日新浪微博：一花一世界economics7如何解决“不存在”纳什均衡的博弈的问题？2013年10月29日新浪微博：一花一世界economics8在这类博弈中，要紧的不是局中人应该选择哪个（纯）策略，而是局中人不应该选择哪个（纯）策略。尤其值得注意的是，在这个博弈中，每个局中人的出牌一定要避免规律性。因此，每个局中人最合理的做法，是随机地出红牌或出黑牌，让对手摸不着北，然后看能不能凭运气击败对手。局中人这种随机化自己可选策略的做法，就是“混合策略”的思想。混合策略与纯策略有很大区别在局中人只有两个纯策略可以选择的情形，混合策略是一种按照什么概率选择这个纯策略，按照什么策略选择那种纯策略的策略选择指示。纯策略给每个局中人具体明确了一个非随机性的行动计划。而混合策略则表明，局中人可以按照一定的概率，随机地从纯策略集合中选择一种纯策略作为实际的行动。2013年10月29日新浪微博：一花一世界economics9混合策略包括原来的纯策略2013年10月29日新浪微博：一花一世界economics10混合策略概念是原来纯策略概念的推广。混合策略（mixedstrategy）纯策略（purestrategy）不确定性（uncertainty）期望支付（expectedpayoff）与混合策略相伴随的一个问题是局中人支付的不确定性。为了刻画不确定情形下局中人的支付，我们需要借助期望支付的概念。在博弈论中，当局中人并不清楚其他局中人的实际策略选择时，他的支付便具有不确定性，为此，他只能通过计算期望支付的方式来预测自己的得益情况，确定自己的策略选择。2013年10月29日新浪微博：一花一世界economics11“扑克牌对色游戏”1－1－11－111－12013年10月29日新浪微博：一花一世界economics12甲乙红p黑1-p红q黑1-q记甲的期望支付为UA，记乙的期望支付为UB2013年10月29日新浪微博：一花一世界economics13)1)(1)(1()1(1)1(1)1(),(qpqpqppqqpUA−−−+−+−+−=pqqppqqpqppq−++−−+−+−=11224−++−=qppq)12()21(2−+−=pqp)12()12(2),(−−−=ppqqpUB需要说明的是，期望支付的标准写法是EU，从而甲的期望支付的标准写法是EUA，但是在概率p和q明显出现的时候，我们约定也可以写成UA(p,q)，表达式里面已经有期望的意思。UB(p,q)与EUB的关系也是这样。2013年10月29日新浪微博：一花一世界economics14更一般地，二人博弈矩阵表示…………………11b12S2nS2013年10月29日新浪微博：一花一世界economics15局中人2局中人121S22S1mS11S……12b11a12anb1na121ana21mb1ma2mb2ma22bnb2mnbmna22a21b二人博弈的数学表达因为行局中人有m种可以选择的纯策略，所以他的混合策略可以紧凑地表示为一个向量要求对每一个纯策略i都有，并且满足。同样，因为列局中人有n种可以选择的纯策略，所以他的混合策略可以紧凑地表示为一个向量要求对每一个纯策略j都有，并且满足。2013年10月29日新浪微博：一花一世界economics16),,,(21mpppp=0≥ip∑==miip11),,,(21nqqqq=0≥jq∑==njjq11纯策略的数学表达若对于某个纯策略i,我们有，而对任意都成立，那么混合策略p对于行局中人来说就是i这一纯策略。也就是说，行局中人i相当于行局中人以1的概率选择策略i，以0的概率选择其他任何策略。这时候，行局中人的纯策略可表述为其中1只在i的位置出现一次。这样的向量一共有m个，正好对应局中人的m个纯策略。2013年10月29日新浪微博：一花一世界economics171=ip0=kpik≠)0,,0,1,0.,0,0(=p类似地，任何形式为的混合策略，其中1只出现一次，实际上都是列局中人的一个纯策略。显然，这样的向量一共有n个，也正好对应列局中人的n个纯策略。2013年10月29日新浪微博：一花一世界economics18)0,,0,1,0.,0,0(=q行局中人的期望支付；列局中人的期望支付如果我们用表示行局中人1的期望支付，用表示列局中人2的期望支付：2013年10月29日新浪微博：一花一世界economics191π2π∑∑−==minjijjiaqpqp111),(π∑∑−==minjijjibqpqp112),(π对有n个局中人参与的策略式博弈的混合策略给出如下定义3.1混合策略在一个有n个局中人参与的策略式博弈中，},,;,,{11nnuuSSG=},,{iKilissS=2013年10月29日新浪微博：一花一世界economics20假定局中人i有K个纯策略，即则概率分布),,(iKilippp=其中,10≤≤ikp∑==11ikkkp称为局中人i的一个混合策略，这里)(ikikspp=ikSKk,,1=表示局中人i选择纯策略的概率本课程约定2013年10月29日新浪微博：一花一世界economics21用表示局中人i的混合策略空间Spaceofmixedstrategies于是，就表示博弈的一个混合策略组合Mixedstrategyprofile其中每一个元素都是一个混合策略向量。这时候，我们用表示局中人i在混合策略组合下的期望支付，它是混合策略组合p的函数。∑i∑∈=iinippppp),,,,,(1ip),,,,()(1niiippppππ=),,,,(1nipppp=简记局中人的期望支付表示局中人i之外所有其他局中人的混合策略组合。至此，局中人i的期望支付可以具体定义为：2013年10月29日新浪微博：一花一世界economics22),()(iiippp−=ππ其中),,,,,(111niiippppp+−−=∑∏∈==Ssinjjjisuspp)())(()(1π其中是我们在纯策略情况熟悉的当所有局中人采取s这个策略组合的时候局中人i之支付，而正是所有局中人各自的策略选择正好组成纯策略组合s的概率。)(sui∏=njjjsp1)(重新定义纳什均衡2013年10月29日新浪微博：一花一世界economics23从二人同时决策博弈看，混合策略纳什均衡必须是两个局中人的相对最优混合策略的组合，所谓相对最优混合策略，是指在给定对方选择该相对最优混合策略的条件下，能使局中人自身的期望支付达到最大的混合策略。用比较学术化的语言，如果*)*,(*21ppp=*),(*)*,(211211ppppππ≥2013年10月29日新浪微博：一花一世界economics24∑∈11p)*,(*)*,(211212ppppππ≥∑∈22p是二人博弈的一个纳什均衡，它必须满足：对于任意的和对于任意的2013年10月29日新浪微博：一花一世界economics25对于一个有n个局中人参与的同时决策博弈，其混合策略纳什均衡Nashequilibriumofmixedstrategies的定义可具体表述为：定义3.2更一般地，定义3.2混合策略纳什均衡*),*,,*,(*1nipppp=},,;,,{11nnuuSSG=2013年10月29日新浪微博：一花一世界economics26*),(*)*,(,,,1iiiiiippppni−−≥=ππ∑∈iip*),*,,*,(*1nipppp=是n人策略式博弈的一个混合策略组合。对于每一个都成立，则称混合策略组合是这个博弈的一个纳什均衡。设如果对于所有的则称混合策略组合定义2.4，纯策略纳什均衡Nashequilibriumofpurestrategies2013年10月29日新浪微博：一花一世界economics27从定义3.2可以看出，第二章中定义2.4给出的纳什均衡，是现在给出的混合策略纳什均衡的特例。所以相对于现在定义的比较广泛的混合策略纳什均衡，原来定义2.4定义的纳什均衡，可以特别叫做纯策略纳什均衡。具体来说，2013年10月29日新浪微博：一花一世界economics28如果*),*,,*,(*1nipppp=是一个现在定义的混合策略的纳什均衡，但是对于每个ni,,1=概率分布*),*,(1*iikiippp=的分量中，都只有一个是1，其余都是0，即所有概率分布*),*,(1*iikiippp=都取)0,,0,1(*=ip)0,,0,1,0,,0(*=ip或者)1,0,,0(*=ip的形式，那么这个“混合”策略纳什均衡就是原来定义2.4的（纯策略）纳什均衡。混合策略纳什均衡与纯策略纳什均衡在本质上是相同的即每个局中人的策略选择都是针对其他局中人的策略选择或策略组合的最佳对策，没有局中有单独偏离或改变该策略组合中自己的策略选择。“单独偏离没有好处”或者“懒得单独改变自己的策略选择”，始终是纳什均衡概念的精髓，只不过混合策略纳什均衡的概念概括的范围更广，它包括了纯策略纳什均衡。所以，纯策略情形的纳什均衡可以看作是混合策略纳什均衡的一种特殊情形。2013年10月29日新浪微博：一花一世界economics293—2反应函数法2013年10月29日新浪微博：一花一世界economics30进行博弈分析的目的，还是为了最终能找到博弈的均衡解。下面我们主要讨论如何寻找同时决策有限博弈的混合策略纳什均衡。一般来说有两种比较常用的方法：反应函数法直线交叉法为了使分析具有连续性，我们还是以扑克对色游戏为例作为开始。反应函数法methodofreactionfunctions扑克牌对色游戏中局中人A的期望支付为2013年10月29日新浪微博：一花一世界economics31)12()21(2),(−+−=qqpqpUA因为B的混合策略已经设定（q,1-q）,所以A的（最佳