混合策略纳什均衡(上)2013.pdf

北京邮电大学北京邮电大学本科选修课程本科选修课程信息经济学信息经济学高丛高丛1HUA1SHIJIE100VIP.SINA.COM混合策略纳什均衡在纳什均衡不存在或者不唯一的情形，2013年10月29日新浪微博：一花一世界economics2前面介绍的纳什均衡的定义和寻找纳什均衡的方法，就不足以帮助我们对博弈的最终结果作出明确的预测，无法给参与博弈的局中人提供明确的决策建议。因此，我们需要拓展纳什均衡的概念，引入新的分析工具，对存在多个纳什均衡的博弈和“不存在”纳什均衡的博弈作进一步的讨论。本章内容：2013年10月29日新浪微博：一花一世界economics3本章首先引入混合策略和期望支付的概念，在此基础上定义混合策略纳什均衡，然后具体介绍求解纳什均衡的反应函数法，并给出混合策略纳什均衡的直观解释。我们讨论多重纳什均衡的问题及其筛选标准。第三章混合策略纳什均衡2013年10月29日新浪微博：一花一世界economics431 混合策略与期望支付32 反应函数法33 高维情形和代数方法34 纳什定理和奇数定理35 多重纳什均衡及其甄别31 混合策略与期望支付2013年10月29日新浪微博：一花一世界economics5我们考虑一个“扑克牌对色游戏”（game of color matching）：两人博弈，每人从自己的扑克牌中抽一张出来，一起翻开。如果颜色一样，甲输给乙一根火柴；如果颜色不一样，甲赢得乙一根火柴。为了确定起见，我们不允许出“大鬼”和“小鬼”。“扑克牌对色游戏”111111112013年10月29日新浪微博：一花一世界economics6甲乙红黑红黑博弈论最重要的问题就是寻求博弈的稳定结果上面这个简单的例子，给我们提出了一个很重要的问题，就是如何解决按照前面两章的定义和方法“不存在”纳什均衡和“找不到”纳什均衡的博弈问题。2013年10月29日新浪微博：一花一世界economics7如何解决“不存在”纳什均衡的博弈的问题？2013年10月29日新浪微博：一花一世界economics8在这类博弈中，要紧的不是局中人应该选择哪个（纯）策略，而是局中人不应该选择哪个（纯）策略。尤其值得注意的是，在这个博弈中，每个局中人的出牌一定要避免规律性。因此，每个局中人最合理的做法，是随机地出红牌或出黑牌，让对手摸不着北，然后看能不能凭运气击败对手。局中人这种随机化自己可选策略的做法，就是“混合策略”的思想。混合策略与纯策略有很大区别在局中人只有两个纯策略可以选择的情形，混合策略是一种按照什么概率选择这个纯策略，按照什么策略选择那种纯策略的策略选择指示。纯策略给每个局中人具体明确了一个非随机性的行动计划。而混合策略则表明，局中人可以按照一定的概率，随机地从纯策略集合中选择一种纯策略作为实际的行动。2013年10月29日新浪微博：一花一世界economics9混合策略包括原来的纯策略2013年10月29日新浪微博：一花一世界economics10混合策略概念是原来纯策略概念的推广。混合策略（mixed strategy）纯策略（pure strategy）不确定性（uncertainty）期望支付（expected payoff）与混合策略相伴随的一个问题是局中人支付的不确定性。为了刻画不确定情形下局中人的支付，我们需要借助期望支付的概念。在博弈论中，当局中人并不清楚其他局中人的实际策略选择时，他的支付便具有不确定性，为此，他只能通过计算期望支付的方式来预测自己的得益情况，确定自己的策略选择。2013年10月29日新浪微博：一花一世界economics11“扑克牌对色游戏”111111112013年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局中人121S22S1mS11S12b11a12anb1na121ana21mb1ma2mb2ma22bnb2mnbmna22a21b二人博弈的数学表达因为行局中人有m种可以选择的纯策略，所以他的混合策略可以紧凑地表示为一个向量要求对每一个纯策略i都有，并且满足。同样，因为列局中人有n种可以选择的纯策略，所以他的混合策略可以紧凑地表示为一个向量要求对每一个纯策略j都有，并且满足。2013年10月29日新浪微博：一花一世界economics16),(21mpppp=0ip=miip11),(21nqqqq=0jq=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日新浪微博：一花一世界economics1912=minjijjiaqpqp111),(=minjijjibqpqp112),(对有n个局中人参与的策略式博弈的混合策略给出如下定义3.1 混合策略在一个有n个局中人参与的策略式博弈中，,;,11nnuuSSG=,iKilissS=2013年10月29日新浪微博：一花一世界economics20假定局中人i有K个纯策略，即则概率分布),(iKilippp=其中,10ikp=11ikkkp称为局中人i的一个混合策略，这里)(ikikspp=ikSKk,1=表示局中人i选择纯策略的概率本课程约定2013年10月29日新浪微博：一花一世界economics21用表示局中人i的混合策略空间Space of mixed strategies于是，就表示博弈的一个混合策略组合Mixed strategy profile其中每一个元素都是一个混合策略向量。这时候，我们用表示局中人i在混合策略组合下的期望支付，它是混合策略组合p的函数。i=iinippppp),(1ip),()(1niiipppp=),(1nipppp=简记局中人的期望支付表示局中人i之外所有其他局中人的混合策略组合。至此，局中人i的期望支付可以具体定义为：2013年10月29日新浪微博：一花一世界economics22),()(iiippp=其中),(111niiippppp+=Ssinjjjisuspp)()()(1其中是我们在纯策略情况熟悉的当所有局中人采取s这个策略组合的时候局中人i之支付，而正是所有局中人各自的策略选择正好组成纯策略组合s的概率。)(sui=njjjsp1)(重新定义纳什均衡2013年10月29日新浪微博：一花一世界economics23从二人同时决策博弈看，混合策略纳什均衡必须是两个局中人的相对最优混合策略的组合，所谓相对最优混合策略，是指在给定对方选择该相对最优混合策略的条件下，能使局中人自身的期望支付达到最大的混合策略。用比较学术化的语言，如果*)*,(*21ppp=*),(*)*,(211211pppp2013年10月29日新浪微博：一花一世界economics2411p)*,(*)*,(211212pppp22p是二人博弈的一个纳什均衡，它必须满足：对于任意的和对于任意的2013年10月29日新浪微博：一花一世界economics25对于一个有n个局中人参与的同时决策博弈，其混合策略纳什均衡Nash equilibrium of mixed strategies的定义可具体表述为：定义3.2更一般地，定义3.2混合策略纳什均衡*),*,*,(*1nipppp=,;,11nnuuSSG=2013年10月29日新浪微博：一花一世界economics26*),(*)*,(,1iiiiiippppni=iip*),*,*,(*1nipppp=是n人策略式博弈的一个混合策略组合。对于每一个都成立，则称混合策略组合是这个博弈的一个纳什均衡。设如果对于所有的则称混合策略组合定义2.4，纯策略纳什均衡Nash equilibrium of pure strategies2013年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日新浪微博：一花一世界economics2932 反应函数法2013年10月29日新浪微博：一花一世界economics30进行博弈分析的目的，还是为了最终能找到博弈的均衡解。下面我们主要讨论如何寻找同时决策有限博弈的混合策略纳什均衡。一般来说有两种比较常用的方法：反应函数法直线交叉法为了使分析具有连续性，我们还是以扑克对色游戏为例作为开始。反应函数法method of reaction functions扑克牌对色游戏中局中人A的期望支付为2013年10月29日新浪微博：一花一世界economics31)12()21(2),(+=qqpqpUA因为B的混合策略已经设定（q,1-q）,所以A的（最佳）反应函数是=,1,1,0,0p如果如果如果2/1q2/1p2/1q4/1p4/3p4/3=pppq23)34(+=)1)(1(3)1(0)1(12),(qpqpqppqqpUz+=pqqppqppq33332+=224+=qppq陈明和钟信的最佳反应函数画在一起，2013年10月29日新浪微博：一花一世界economics44p0q13/41/41一共得到三个交点：)0,0(*)*,(=qp)4/1,4/3(*)*,(=qp)1,1(*)*,(=qp验算如果陈明以3/4的概率选德语，钟信以1/4的概率选法语，那么陈明的期望得益是2013年10月29日新浪微博：一花一世界economics45)4/1,4/3(*)*,(=qp这个纳什均衡2/3)4/3(20)1*(2)1*4(*)*,(=qqpqpUc而钟信的期望得益是2/32/330*23)3*4(*)*,(=+=+=qpqqpUZ都没有)0,0(*)*,(=qp大家一起选德语3*)*,(=qpUc和)1,1(*)*,(=qp大家一起选法语3*)*,(,2*)*,(=qpUqpUzc来得好。帕累托优势可见，纯策略纳什均衡比混合策略纳什均衡具有支付优势，得益优势。在博弈论里面，我们把这种表现为支付的优势叫做帕累托优势。由此可以体会，在这种纯策略纳什均衡和混合策略纳什均衡都存在的情况下，博弈论往往把“优先权”给予纯策略的纳什均衡。2013年10月29日新浪微博：一花一世界economics46情侣博弈的版本之一：陈明和钟信选修第二外语博弈的结局结局不是一起选德语，就是一起选法语，这两个纳什均衡都具有绝对的支付优势、得益优势，绝对优势指的是两人的情况都变好，而不仅是两人的情况加起来变好。陈明和钟信选修第二外语的博弈只进行一次，但是情侣博弈有别的版本，如果真是恋人周末节目选择的博弈，那么这种博弈在许多周末都要进行，这样，情侣博弈就变成重复多次的博弈即重复博弈。2013年10月29日新浪微博：一花一世界economics47