网络结构与效应原理：第7章 进化博弈论基本概念简介

进化博弈论基本概念简介（对应教材第7章）回顾上一讲（博弈论基础）博弈参与者（player）策略（strategy）收益，回报（payoff）收益矩阵－－形象地描述一个博弈的结构在博弈论的分析中（决定很可能会采取的策略）从每个人的角度，不是要考虑如何战胜对方，而是基于对对方行为的预测，自己如何收益尽可能大。双方都如此态度。纯策略、混合策略（在可选纯策略集合上的一个概率分布）立刻可能想到的(例)p\q0.10.20.30.4…0.12.74,??,??,??,?0.2?,??,??,??,?0.3?,??,??,??,?0.4?,??,??,??,?乙L(q)R(1-q)甲U(p)4，40，3D(1-p)3，03，3P1(p,q)=?P2(p,q)=?均衡（纳什均衡）－博弈的趋势均衡：互为最佳应对的策略组纳什均衡定理：在考虑混合策略条件下，任何有限参与人、有限纯策略的博弈都存在均衡一般来讲，找到均衡是很困难的，但在某些限定条件下可能有系统化方法例如，双人双（纯）策略检查四个策略组合是否为纯策略均衡利用无差异原理试求混合策略均衡若（1）为空，则（2）一定有；若（1）不空，（2）也可能有囚徒困境（协调）博弈的特征模式双人双策略对称均衡出现在双方采用某一种相同的策略对应社会最优的策略组不是均衡，因为参与人之一有动机改变策略鹰鸽博弈的特征模式双人双策略对称均衡出现在双方采用不同的策略双人双策略对称博弈均衡的一般条件若（S,S）是均衡，a,b,c,d之间的关系？若（S,T）是均衡，…？若（T,S）是均衡，…？若（T,T）是均衡，…？a≥cc≥a,b≥d经常会用到“期望”的概念一个随机的行为，会有多种（以两种为例）可能的结果（r1,r2），分别对应一个概率（p1,p2），p1+p2=1则这个行为的结果期望就是p1r1+p2r2概率常常用“比率”和“占比”来近似混合策略的收益：在纯策略集合上按概率分布选择的收益期望进化博弈论：

用博弈论语言讨论生物进化现象人们发现某些生物进化的过程（物竞天择，适者生存）也体现出博弈的某些关键特征（纳什均衡不一定是社会最优）博弈与进化博弈若干概念的一种对比理解博弈，纯策略确定性策略，直接对应的收益博弈，混合策略概率性策略，收益期望进化博弈，纯策略对于个体：确定性策略，直接收益对于群体（策略）：适应性－其中个体与其他个体随机相遇的收益期望进化博弈，混合策略对于个体：概率性策略，收益期望对于群体（策略）：适应性－其中个体与其他个体随机相遇的收益期望均衡稳定性进化博弈的由来进化论的主要观点生物体的遗传基因在很大程度上决定了它的外部特征（行为方式等），因而决定了它是否能够适应给定的环境。生物体对环境适应性的基本表征是其繁殖能力，较强的生物体往往会繁衍较多的后代，于是该物种在生物总体中的占比增加。一个物种的成功进化取决于它其中的个体和其他个体（同种或者不同种）的互动（竞争）结果。进化博弈的由来1960s，从博弈论视角来解释生物进化论由基因决定的生物特征及行为可类比为博弈中的策略（尽管一般情况下不能选择）；将生物的适应性（的提高）类比为它的收益。J.M.Smith和G.R.Price，提出“进化稳定”的概念，标志着进化博弈论的诞生。JohnM.Smith.OnEvolution.EdinburghUniversityPress,1972J.M.SmithandG.R.Price,TheLogicofAnimalConflict,Nature,246,15-18,1973.生物适应性与种群变异例子：体态大小的进化博弈考虑一种甲虫种群假设每只甲虫对给定环境的适应能力取决于它是否可以发现食物从获得的食物中有多少能转换为生物适应性设想一个特定的突变基因出现，使得有该基因的甲虫体型变大（或变小）。因此，甲虫便分成两个不同的种群——小甲虫和大甲虫。问：在竞争中代代繁衍，其中一种甲虫会灭绝吗？生物适应性与新陈代谢对于大甲虫，维持基本的新陈代谢实际上要比较困难些需要吃较多的食物才能维持较大的体态；即同样数量的食物，小甲虫从中可获得较多的收益（适应性）。直观结论是：大体态变异基因使适应性减弱，会繁衍得越来越少，最后灭绝（被淘汰）。然而事实真的是这样吗？互动（竞争）与生物适应性当两只甲虫为食物争夺时，可能的情形有：如果它们大小相同，它们会平分同样的食物当一只大甲虫和一只小甲虫争夺食物，则大甲虫会得到大多数的食物对于同样的食物量，大甲虫在适应性上得到的益处要少，因为所得到的食物中有一部分要转化用来维持它们消耗较高的新陈代谢食物争夺随机相遇适应性收益矩阵每只甲虫从争夺到的一定量食物中获得的生物适应性（不是食物量），可看成是双人博弈中的收益。随机碰到的一只甲虫有两种可能：大或小。将这可能性看成“策略”，假设有：甲虫2小的大的甲虫1小的5,51,8大的8,13,3与经典的博弈比较每只甲虫的策略都是由遗传基因硬性决定的“策略选择”的概念在此是缺失的因此以策略选择为基础的纳什均衡思想在此没有直接的对应但人们发展出一个平行的概念

－－“进化稳定策略”一个生物种群，能够抵御外来入侵（入侵者会在进化过程中消亡）甲虫2小的大的甲虫1小的5,51,8大的8,13,3进化稳定策略一个策略（基因）称为是进化稳定的，若当整个群体都采取这个策略时，其他采用不同策略的小规模

“入侵”群体经过多代遗传后最终会消亡。这里的基本思想也可用于讨论人们的社会行为形式化定义一种生物体的适应性是指它与一个随机遇到的生物体互动（竞争）得到的收益期望称“策略T在x程度上（以x水平）入侵策略S”，指的是在总体中有x占比的生物体采用策略T，1-x占比采用策略S；其中0<x<1。若存在一个小正数y，当任何其他策略T以任何x<y水平入侵策略S时，采用策略S的个体的适应性严格高于采取策略T的个体，则称策略S是进化稳定的，evolutionarilystable。考察小体态是否进化稳定策略考虑一个小正数x<1，总体中有x占比的个体使用策略“大体态”，有1-x占比的个体使用策略“小体态”。（甲虫们随机相遇争夺食物）一只小甲虫的收益期望是5(1-x)+1

x=5-4x一只大甲虫的收益期望是8(1-x)+3

x=8-5x可见，不存在y，使得x<y时小甲虫的期望收益超过大甲虫。因此，策略“小体态”不是进化稳定的。甲虫2小的大的甲虫1小的5,51,8大的8,13,3(1-x)x体态博弈中的进化稳定策略：考察大体态考虑一个很小的正数x<1，总体中有x占比为小体态，1-x占比甲虫为大体态。大甲虫收益期望是8x+3(1-x)=3+5x小甲虫收益期望是5x+(1-x)=1+4x大甲虫的收益期望总是超过小甲虫的，所以，“大体态”是一个进化稳定策略。甲虫2小的大的甲虫1小的5,51,8大的8,13,3(1-x)x进化博弈中的“军备竞赛”生物学家认为在自然界中存在具有囚徒困境结构的进化博弈现象例如：树木高矮的竞争；植物根系的竞争例子：病毒之间的进化博弈（Nature，1999）噬菌体Φ6病毒。这种病毒感染细胞，而且产生自我复制（繁殖）所需的化学产物。它的一种基因变异体称为噬菌体ΦH2，自身繁殖能力较弱，但能够利用Φ6的化学产物，于是当和病毒噬菌体Φ6同时存在时，噬菌体ΦH2在适应性方面便有明显优势。具有类似囚徒困境博弈的结构：病毒有两种：Φ6和ΦH2（对应两个进化策略）在一个纯Φ6种群中，病毒行为收益（自我复制的能力）会优于纯ΦH2种群的病毒；但是，当病毒ΦH2与Φ6同时存在时，ΦH2的收益会比较高，甚至高于纯Φ6种群情形。因此，ΦH2是进化稳定的，Φ6不是。结果就是，一旦Φ6种群中出现了少量变异ΦH2，则ΦH2病毒会越来越多，Φ6越来越少换句话说，ΦH2成功入侵了Φ6病毒进化博弈的收益矩阵生物学家测量了两种病毒在不同条件下复制行为的相对速率（体现适应性）病毒2Φ6ΦH2病毒1Φ61.00,1.000.65,1.99ΦH21.99,0.650.83,0.83理性的选择与进化的力量有相似的取向！进化稳定策略的一般描述如何用a，b，c，d写出S是进化稳定的条件？设对于一个很小的正数x<1，总体中有1-x部分使用策略S，有x部分使用策略T采取S策略的期望收益：a(1-x)+bx采取T策略的期望收益：c(1-x)+dx应满足a(1-x)+bx>c(1-x)+dx结论：在双人双策略的对称博弈中，若(i)a>c或(ii)a=c且b>d，则S是进化稳定的。（注意“x很小”在其中的作用）生物体2ST生物体1Sa,ab,cTc,bd,d(x)(1-x)考虑双人对称博弈形态在双人双策略的对称博弈中，若(i)a>c，或(ii)a=c且b>d，则S是进化稳定的。这意味着：为了使S成为一个进化稳定策略，用策略S应对策略S的回报不能小于用策略T来应对策略S取得的回报。若策略S和T在应对策略S时的收益相等。为了保证S是一个进化稳定策略，采取策略S应对策略T的收益要严格大于采取策略T应对策略T的收益。生物体2ST生物体1Sa,ab,cTc,bd,d进化稳定策略与纳什均衡？博弈

纳什均衡（互为最佳应对策略组）进化博弈

进化稳定策略给定一个收益矩阵，我们可以讨论是否存在纳什均衡，也可以讨论哪个策略是进化稳定的--基于各自的定义如果能建立起这两个概念的某种关系，则有可能让我们从对一个的认识直接得到对另一个的认识。进化稳定策略与纳什均衡的关系S是进化稳定的条件：(i)a>c，或(ii)a=c且b>d(S,S)是纳什均衡的条件：a≥c因此，若策略S是进化稳定的，则(S,S)一定是一个纳什均衡。反之不一定成立。生物体2ST生物体1Sa,ab,cTc,bd,d例子：猎鹿博弈猎鹿，猎兔都是进化稳定的因此（猎鹿,猎鹿）和（猎兔,猎兔）也都是纳什均衡猎人2猎鹿猎兔猎人1猎鹿4，40，3猎兔3，03，3猎人2猎兔猎鹿猎人1猎兔3，33，0猎鹿0，34，4例子：另一种猎鹿博弈猎鹿不是进化稳定的，尽管（猎鹿,猎鹿）是纳什均衡。猎兔是进化稳定的，于是（猎兔,猎兔）此时也是纳什均衡。猎人2猎鹿猎兔猎人1猎鹿4，40，4猎兔4，03，3猎人2猎兔猎鹿猎人1猎兔3，34，0猎鹿0，44，4进化稳定策略和严格纳什均衡在一个策略选择中，若每个参与人使用的都是唯一的最佳应对策略（即严格最佳应对），则称这个最佳应对策略组是一个严格纳什均衡。不难看到：如果（S,S）是一个严格纳什均衡（即a>c），则S是进化稳定的。反之不一定成立。生物体2ST生物体1Sa,ab,cTc,bd,d并不是总有进化稳定策略例子：鹰鸽博弈可以从定义验证：D，H都不是进化稳定的。这也可从（D，D）和（H，H）都不是纳什均衡直接推出动物2相让D相争H动物1相让D3，31，5相争H5，10，0在生活中，极端主义是很难长存的怎么办？进化稳定混合策略一种生物个体，由其基因决定，按照概率分布（p,1-p）随机采用两个策略S和T之一。想像有一群这样的个体，在互动中繁衍突然，其中出现了一种变异：概率变为q设变异种群在总体中初始占比x（很小），问：原来的种群是进化稳定的吗？也就是，在互动中，p种群能比q种群更具适应能力，从而能抑制q种群的蔓延吗？若是，则称p是进化稳定混合策略下面，我们先来看两个采用不同混合策略的生物体相遇互动时的收益期望（p,q的函数）然后再看根据在总体中的占比，两种生物体随机相遇所导致的收益期望（x,p,q的函数）讨论最后这两个期望的大小，判断是否进化稳定第二类生物S（q）T（1-q）第一类生物S（p）a,ab,cT（1-p）c,bd,d进化混合策略下的收益第一种（p策略者）遇到第二种V(p,q)=p

q

a+p(1-q)b+(1-p)q

c+(1-p)(1-q)d第二种（q策略者）遇到第一种V(q,p)=qpa+q(1-p)b+(1-q)pc+(1-q)(1-p)d也可以写出同种相遇的收益V(p,p),V(q,q)第二类生物S（q）T（1-q）第一类生物S（p）a,ab,cT（1-p）c,bd,d两个采用不同混合策略者相遇的收益下面看两个群体的个体间互动的情形，设第二种是入侵者，占比x第一种p占比1-x,第二种q占比x第一种与第一种相遇，两者收益都是V(p,p)第一种与第二种相遇，前者收益V(p,q)，后者收益V(q,p)第二种与第二种相遇，两者收益都是V(q,q)此时，个体随机相遇的可能有如何讨论群体？群体占比的设定给出了个体相遇的概率第一种1-x第二种x第一种：V(p,p)V(p,q)第二种：V(q,p)V(q,q)相遇的概率及其所导致的收益期望第一种（初始种群，p）E1(x,p,q)=(1-x)V(p,p)+xV(p,q)第二种（变异种群，q）E2(x,p,q)=(1-x)V(q,p)+xV(q,q)第一种1-x第二种x第一种：V(p,p)V(p,q)第二种：V(q,p)V(q,q)在种群混杂情况下不同种群中一个个体的平均收益p是一个进化稳定混合策略的判据：存在y，对任意x<y及任意q≠p，有E1(x,p,q)>E2(x,p,q)

(1-x)V(p,p)+x

V(p,q)>(1-x)V(q,p)+x

V(q,q)判定进化稳定混合策略的一个要点存在y，对任意x

y，下面这个不等式对任意的混和策略q≠p成立，则称p是进化稳定混合策略：

(1-x)V(p,p)+x

V(p,q)>(1-x)V(q,p)+x

V(q,q)注意，由于p的进化稳定性要求x可以任意小，于是必有V(p,p)≥V(q,p)。这意味着混合策略p是自己的最佳应对，亦即（p,p）是一个混合纳什均衡。结论：p是进化稳定混合策略

（p,p）是混合纳什均衡这对确定p是否进化稳定混合策略的启发：先看（p,p）是否混合纳什均衡例：鹰鸽博弈根据无差异原则，有：3q+1-q=5q；且3p+1-p=5p解得知(1/3,1/3)是混合纳什均衡。特别注意，在这种情况，当一方用1/3，另一方无论用什么都得到同样的收益5/3（由无差异原则）参与者2鸽派D(q)鹰派H(1-q)参与者1鸽派D(p)3，31，5鹰派H(1-p)5，10，0前面，我们已知D和H都不是进化稳定策略下面看是否存在进化稳定混合策略p是进化稳定混合策略的条件：对任意的q（q不等于p），所有小x满足：(1-x)V(p,p)+x

V(p,q)>(1-x)V(q,p)+x

V(q,q)因为若p是进化稳定混合策略，则(p,p)是混合纳什均衡，于是就要有，对任意的q，V(p,p)=V(q,p)V(p,q)－V(q,q)=(4q+1/3)－(6q-3q2)=

1/3*(3q—1)2>0因此，p=1/3就是进化稳定混合策略！再看1/3是否进化稳定混合策略动物2鸽派D(q)鹰派H(1-q)动物1鸽派D(p)3，31，5鹰派H(1-p)5，10，0进化博弈思想的应用虽然进化过程的博弈分析方法起源于生物学，但它也可以应用在许多其他情境中，包括社会行为。比如，假设一大群人被成对安排来重复进行普通的对称博弈，每次博弈可以看到先前的结果。收益被解释为反应参与人得到的福利情况。模仿周围成功的人从个人经验中学习在这两种情况下，在过去取得好成绩的策略将会倾向于更多的被人们在将来的策略选择上使用。这种经验学习过程会导致进化稳定策略。进化博弈论简要小结群体中，个体采用不同的（基因决定的）策略谋求生存相遇互动个体之间按照策略的应对关系产生各自的收益一个群体（对应一种策略）的适应性：定义为其中的个体与随机相遇个体互动的收益期望进化稳定（非形式化）种群：能够抵御一小群采用不同策略的个体的入侵（它们延续不下去）。具体体现就是在个体间的互动中能获得较高的收益期望（即较强的适应性）进化稳定策略（形式化）：S，在对称收益矩阵（a,b,c,d）的适当条件下，对所有x<y，优于T。进化稳定混合策略：在S和T中进行选择的概率p，在对称收益矩阵（a,b,c,d）的条件下，对所有x<y，优于任何q≠p。进化稳定策略与纳什均衡的关系下面几张PPT的信息来源于刘永军（2012年夏季培训班学员）进化博弈思想的发展与应用斯密斯与普瑞斯在20世纪70年代初期提出了演化博弈的基本概念：演化稳定策略，为博弈论的研究提供了一个新方向。

20世纪80年代，许多经济学家将演化博弈引入到经济学领域，用于分析社会制度变迁、产业演化以及股票市场等等，同时也开始由对称博弈向非对称博弈深入(Selten,1980；1983)。

20世纪90年代以来，温布尔（Weibull，1995）比较系统完整地总结了演化博弈理论，演化博弈理论的发展进入了一个新的阶段。21世纪以来，演化博弈的发展出现了一些新的思路：如关注演化博弈的稳定性问题（AnaB.Ania，2006）；有一方模仿情况下的合作演化博弈问题（DavidK.Levine，2007）JosefHofbauera和WilliamH.Sandholmb（2007）讨论了具有随机扰动得益的演化博弈问题。

90年代末21世纪初，张维迎谢识予等开始介绍演化博弈理论的一些基本概念和相关内容。孙庆文，陆柳等（2003）对不完全信息条件下演化博弈均衡的稳定性进行了分析。吴昊，杨梅英等（2004）对合作竞争博弈中的复杂性与演化均衡的稳定性进行了分析。易余胤等（2005）对经济活动中的演化博弈理论的研究做了综述。

进化博弈思想的应用举例（国外）公民规范和演化之间的关系（规范的长期存活依赖于演化过程和自然选择）—巴苏(Basu,1995)日美无贸易和有贸易情形下企业组织模式的演化

—弗里德曼和方(Friedman&Fung,1996)人类在经济活动中利他行为的存在性及其演化稳定性

—拜斯特和古斯(Bester&Guth,1998)在双寡头垄断竞争的情形下两种经济制度比较及在怎样的市场环境中会导致相似的市场结果

—登弗伯格和古斯(Dufwenberg&Guth,1999)互惠主义在有机会主义存在的群体中是否能够存活

—戈特曼(Guttman,2000)在具有网络外部性的条件下免费软件的最优价格和质量的研究—哈如威和普拉赛