进化博弈论读书心得

进化博弈论读书报告汪波1973年，梅拉德·史密斯和普瑞斯将博弈论的思想引入到生物演化的分析中，二人提出了进化稳定策略（ESS），随着1978年，Taylor和Jonker发现了进化稳定策略和复制动力学之间的关系，标志着进化博弈理论的诞生，因为与复制动力学之间的关系，进化稳定策略也因此成为进化博弈理论最经典的概念。1982年，梅拉德·史密斯出版了《演化与博弈论》，该书揭示动物群体的行为变化的动力学机制，也因此书他被称为进化博弈论之父，1995年，Weibull著作了《EvolutionaryGameTheory》,2009年初，Sandholm出版了《PopulationGameandEvolutionaryDynamics》专著，这篇读书报告是在看了这三本著作的很少的一部分内容之下，理解其中一些浅显的内容后完成的。一、进化稳定策略最初的模型进化博弈理论是将博弈论引入到生物学背景下产生的，当生物的特定表现型的适应度依赖于群体中的频率分布时，进化博弈论就是从这个角度来思考生物演化的问题的一种方法，古典博弈中，参与者根据自利的原则表现出理性行为，但在生物进化的背景下是不合适的，由此，理性原则被群体的动态性和稳定性取代，而自利原则则被达尔文的适应度所取代。在一些重要的假设下，将会得到博弈的一个新形式解：进化稳定策略。它是这样一个策略，如果整个群体的每个成员都采取这个策略，那么在自然选择的作用下，不存在一个具有突变特征的策略能够侵犯这个种群。最初的简化的模型由梅拉德·史密斯和普瑞斯给出，他和普瑞斯也给出了进化稳定策略的数学式的描述定义，这一模型的本质特征是假设该群体有无限大的规模，繁衍以无性生殖的方式进行，竞争只在两个不存在任何差异的对手间展开即是成对的竞争。生物学中价值是指两个动物为了争夺资源而增加的或者减少的达尔文适应度。故我们用适应度作为最后个体的收益的衡量，假想在这个无限的种群中，有两个策略I、J，每一个成员都采取这两个策略之一，且策略的选择是随机的，在有竞争前个体的初始适应度为0w，再假设整个群体中选择I的概率为p，()wI、()wJ分别表示选择相应策略带来的适应度，而(,)EIJ表示个体选择策略I而对手选择J时的收益，其他(,)EII等表示类同的意义。若每一个个体都参与到竞争当中，则有0()=+(1-p)(,)(,)wIwEIIpEIJ（1-1）0()=+(1-p)(,)(,)wJwEJIpEJJ（1-2）稳定的策略具有下列性质：整个种群中几乎所有的个体都采取了这个策略，且这些个体的适应度必将高于竞争对手或者可能出现的突变异种的适应度，否则竞争对手或者产生的突变异种会侵害整个种群，以致种群的削弱或者毁灭等，这时此策略便不可能是稳定的策略。若I是进化稳定策略，则()()wIwJ，且1p，所以当IJ，有(,)(,)EIIEJI（1-3）当(,)(,)EIIEJI时有(,)(,)EIJEJJ（1-4）满足上述条件（1-3）、（1-4）的策略就称为进化稳定策略，而上述的两个条件1-3、1-4也被认为是判别ESS的标准条件。上述的策略是在纯策略情形下考虑的，当策略I是从一个可能策略集合中随机的选择而构成的，此时的策略称为混合策略。此时I若是一个混合进化稳定策略，假设12,,......,ksss等是该群体的纯策略，赋予这些纯策略非零的概率值，那么I必须满足如下条件：12()().....()(,)kEsEsEsEII(1-5)保证所有纯策略的回报是相等的，群体中的个体才不会选择偏离的策略。此时起满足的条件和上述是相同的形式。二、对称博弈1.对称博弈的定义两人对称博弈对于许多进化博弈论内容而言是基础的，而且，许多进化博弈论中的深刻见解都可以从二人对称博弈这种特殊情形中得到，这也是单独列出对称博弈内容的主要原因。一个二人对称博弈(,,)GISu，可假设有两个玩家的位置，每个位置上有相同的纯策略，而任意的策略的支付则依赖于玩家所选的位置，因此有如下的定义：博弈(,,)GISu称为二人对称博弈，如果{1,2}I，12{1,2,......,}SSSn且对于任意的12(,)ssS有112221(,)(,)ussuss成立。该对称博弈要求两个位置上的支付矩阵是互为转置的，即若A为第一人的支付矩阵，B为第二个人的支付矩阵，则TBA，即111212122212.....................nnnnnnaaaaaaAaaa则112121222112.....................nnTnnnnaaaaaaBAaaa也即有若,ijjiaAbB，则ijjiab。例如：囚徒困境情形就是一个非常好的对称博弈的例子。上述是在纯策略下的情形，现在描述混合策略情形：12{1,2,......,}SSSn，用1(,,.....,)nnxxx表示策略集上的一个概率分布，即为该博弈的一个混合策略，用表示其混合策略集，则混合策略组合空间为2，此时任意的纯策略iS在对手选择混合策略x时的支付为(,)()iiiuexeAxAx。2.对称博弈的特点对称博弈是一种很特殊情形，它有自己的特征，一是对称博弈的最优回应对应*和通常的最优回应对应不一样，通常的是策略组合空间到策略组合空间之间的映射，而*是策略集到策略集之间的映射，即*(){:(,)(,),}yxuxyuzyz(1-6)这是对称博弈策略集相同所决定的。二是对称博弈有更特殊的形式：双对称博弈。此时在其他条件满足下当且仅当BA时称为双对称博弈。例如：协调博弈就是一个很好的双对称博弈的例子。三是对称博弈的纳什均衡的形式也有所不同，对称博弈具有不对称的纳什均衡，也具有对称的纳什均衡。策略组合2(,)xy被称为对称博弈的纳什均衡，当且仅当**(),()xyyx，其中*:，这与通常的纳什均衡的定义是一致的，用NE表示纳什均衡集合。当xy时我们称该纳什均衡为对称的，此时纳什均衡可以表示为{:(,)}NENExxx(1-7)对称的情形下，它本质是一个策略空间，不同于往常的策略组合空间，当然，对称博弈的纳什均衡并非都要求是对称的，但也可以证明任意的对称博弈一定能够存在至少一个对称的纳什均衡，即对于任意的二人有限对称博弈，NE。例如：鹰-鸽博弈、石头-剪刀-布等博弈都是具有混合策略均衡的且是对称的。以鹰鸽博弈为例：不是一般地，下面支付矩阵为一方甲的支付矩阵：()202vcvAvTBA其中v表示一定价值的资源适应度，在此表示获得的支付，双方甲、乙都选择鹰策略则各自获得()2vc，c表示双方争斗产生的适应度的下降或者说是损失，若甲选择鹰策略乙选择鸽策略，则甲获得全部资源v而乙获得0，若都选鸽策略则平分资源。当vc时，则鹰策略是纳什均衡，因为此时双方都宁愿冒着受伤的风险获得大于零的资源适应度，而当vc时，则存在对称的混合纳什均衡，假设此混合策略组合为(,1)xpp，则要满足()2(1)2(1)pvcvpvp解得pvc，则知(,1)NExvcvc，故(,)NExx。四是二人对称博弈的分类，根据支付我们可以将对称博弈分为四类.以11122122aaAaa为例。将第一列减去21a，第二列减去12a变形得1121'221200aaAaa再令1112122212,aaaaaa得正规化形式1'200aAa构造如下所示的图：2aIII1aIIIIV用212(,)aaaR表示该图中平面上的点，若当点在图中的北西象限时，我们说此时的对称博弈是第I类的，当若当点在图中的北东象限时，我们说此时的对称博弈是第II类的，当若当点在图中的南西象限时，我们说此时的对称博弈是第III类的，当若当点在图中的南东象限时，我们说此时的对称博弈是第IV类的。很容易发现，当博弈是第I类或者是第IV类的时候，分别有21aa和21aa，两个的支付一正一负，此时博弈都存在严格占优的策略，故都存在纯策略纳什均衡。第I类的解为{2,2}S，纳什均衡集合为22{(,)}NEee和2{}NEe。第IV类的解为{1,1}S，纳什均衡集合为11{(,)}NEee和1{}NEe。当博弈是第II类或者第III类时，支付函数值同号，此时不仅仅存在对称的纯策略的纳什均衡，也存在对称的混合策略纳什均衡。第II类博弈，二者支付都为正数。有两个对称的严格占优的纳什均衡，还有一个对称的混合策略纳什均衡，故它的解为{1,2}S，纳什均衡集合为1122**{(,),(,),(,)}NEeeeexx，12*{,,}NEeex。其中*221121((),())xaaaaaa。这一类博弈常见的例子如调和博弈。第IV类博弈，二者的支付都为负数，没有严格占优的策略。它的解为{1,2}S，纳什均衡集合为1221**{(,),(,),(,)}NEeeeexx，*{}NEx。其中*221121((),())xaaaaaa。这一类常见的博弈如鹰鸽博弈（vc的情形）。三、对称博弈下看进化稳定策略1.进化稳定策略的定义结论仍然集中二人对称博弈上，{1,2}I，纯策略集为{1,2,.....,}Kk，混合策略集为{:1}kiiKxRx，当1选择x而2选择y时，参与者1的支付矩阵为A，则此时支付函数为(,)uxyxAy。在对称博弈的下，进化稳定策略有两种等价的定义。由于对称博弈可以很好的解释单群体博弈，所以此时是在单群体情形下来讨论，假设有一个数量规模很大的群体，里面出现一组规模很小的突变者，他们选择的策略集是相同的且成对竞争，群体主体现在的策略为x，这组小规模的突变者选择策略y，并假设这组小规模突变族所占群体的份额为（0，1）。同时假设群体里每个代理人都参与竞争，每个代理人选择现任策略x的概率为-1，选择突变策略y的概率为，在此时的生物群体下的支付可以看作与其中一个代理人选择策略(-)wyx1时竞争产生的支付。那么相应的,代理人选择现任策略x的支付函数值为(,)=u(x,(-))uxwyx1,同理有(,)=u(y,(-))uywyx1。在这样的生物情形下，直觉告诉我们，群体要能抵抗外来的入侵或者应对突变者的袭击，那么现任策略x所能得到的支付必须高于入侵者或者突变者的策略y的支付。因此，进化稳定策略除了本文第一部分的定义形式外，有另外一种等价的定义形式：若策略x是进化稳定策略（ESS），如果存在实数01，，使得对于所有的0，，都满足下面的不等式条件：(,)=u[x,(-)](,)=u[y,(-)],uxwyxuywyxyx11(3-1)其中(,)TuxwxAw。策略x在任意的策略y下的最优回应集合为*()y。此时若x是该博弈的进化稳定策略，则它必须满足*()xy，即x必须是该博弈的纳什均衡即NEx，但还需要满足另外的条件才能保证x是进化稳定的策略，由此可知，若用ESS表示博弈的进化稳定策略集合，那么有ESSNE，由进化稳定策略的含义可以更详细的表示ESS的形式如下：*{:(,)(,)()y}ESSNExuxyuyyyxx，(3-2)由此我们又回到了进化稳定策略的第一种定义的形式：称x是该博弈的进化稳定策略，若满足如下两个条件：(,)(,),uxxuxyy(3-3)当存在y满足(,)(,)uxxuxy时有(,)(,),uxyuyyyx。(3-4)这两个条件就如我们一开始所说的是判断一个策略是不是进化稳定策略的标准。2.两种等价定义的作用将上述（3-1）式在定义计数函数：:[0,1]fR下可写为(,)fy，且其等于(,)(,(1))fyuxyyx由x是进化稳定的可知当