复杂网络上的演化博弈

第2卷第2期 2007年4月 智 能 CAAITransactions 系 统学报 onIntelligentSystems V01．2№．2 Apr．2007 王 复杂网络上的演化博弈 龙，伏 锋，陈小杰，王 靖，李卓政，谢广明，楚天广 (北京大学工学院，北京100871) 摘要：主要介绍了近年来复杂网络上的演化博弈研究现状和研究方向．复杂网络理论的发展为描述博弈关系提供 了系统且方便的框架，网络上的节点表示博弈个体，边代表与其邻居的博弈关系．介绍了经典演化博弈论中的演化 稳定策略概念和复制动力学方程，以及二者的相互联系．介绍了混合均匀有限人口中随机演化动力学问，并给出 了与确定复制方程的相互转化关系．介绍了小世界、无标度等复杂网络上演化博弈的研究结论，给出了复杂网络上 演化博弈论的未来发展方向． 关键词：演化博弈论；复制动力学；演化稳定策略；复杂网络；有限人口；合作 中图分类号：N949文献标识码：A文章编号：1673—4785(2007)02—0001—10 Evolutionarygamesoncomplexnetworks WANGLong，FUFeng，CHENXiao—jie，WANGJing，LIZhuo～zheng， XIEGuang—ming。CHUTian～guang (CollegeofEngineering，PekingUniversity，Beijing100871，China) Abstract：Inthissurvey，recentdevelopmentsandfuturedirectionsofevolutionarygamesoncomplexnet— worksarepresented．Thedevelopmentofcomplexnetworktheoryprovidesasystematicandconvenient frameworkfordescriptionofthedynamicalinteractionsofgames．Theverticesrepresentplayers，while theedgesdenotethelinksbetweenplayersintermsofgamedynamicalinteraction．First，someimportant conceptsofevolutionarilystablestrategyandreplicatordynamicsareintroduced，andtheconnectionbe— tweentheev01utionar订ystablestrategyandreplicatordynamicsisestablished．Then，thestochasticevolu— tionarydynamicsoffinitewell——mixedpopulationsandtheirrelationshiptothedeterministicreplicatordy—— namicsarepresented．Someresultsonfixedprobabilityandtimearealsogiven．Furthermore，somerecent resultsofevolutionarygamesoncomplexnetworkssuchassmall—·worldandscale—·freenetworksareintro—— duced．Finally，unresolvedopenproblems，futureresearchdirections，andpossibleapplicationareasfor evolutionarygamesoncomplexnetworksarepointedout． Keywords：evolutionarygame；replicatordynamics；evolutionarilystablestrategy；complexnetworks；fi— nitepopulations；cooperation 博弈论是研究依据其他参与者的效用(utility) 情况，理性参与者策略之问相互作用的一门科学Ⅲ． 博弈论的要素有两点：参与博弈者的目标或利益相 互冲突，且他们都是理性的．现代博弈论已成为一门 横跨数学、生物、心理学、计算机科学、运筹学、经济、 收稿日期：2006—12-18． 基金项目：国家自然科学基金资助项目(60674050，60528007)；973 国家重点基础研究发展资助项目(2002CB312200)； 863国家高技术研究发展计划资助项目(2006AA042258)； “十一五”规划资助项目(A2120061303)． 哲学、政治、军事战略等领域的交叉学科．公认的现 代博弈论起源于数学家VonNeumann和经济学家 Morgenstern的合著：博弈理论和经济行为[2]．尽管 当时这本著作中的博弈论的理论框架只适用于一些 有限的特例，如只讨论了零和非合作博弈问题等，但 它第一次用数学语言描述和解决了博弈问题．此后， 经过许多学者的努力，特别是Nash在非合作博弈 理论中创造性地引入策略均衡的概念，博弈论日渐 成为非常重要且有用的工具[3]．近十多年来，诺 万方数据 智能系统学报 第2卷 贝尔经济学奖先后授予研究博弈论的科学家Nash、 Selten、Harsanyi、Aumann、Schelling等人，说明博 弈论越来越得到更多人的重视，博弈论的威力也得 到越来越广泛的承认． 1 博弈论和复杂网络 所谓Nash均衡(Nashequilibrium)是指给定博 弈中其他个体(player)的策略时，任何一个个体都 不能单方面改变自己的策略来增加自己的收益 (payoff)的情形．换言之，在Nash均衡中，相对其他 个体，个体的所选策略已经是最佳的反应，此时 Nash均衡成为一致解的概念．但是，作为博弈一致 解的概念，在有些情况下Nash均衡并不是必要条 件而是充分条件．因此，博弈论的后Nash均衡时代 主要是针对博弈的假设和前提的重新修改和扩展． 其中最主要的2个分支：动态博弈和非完全信息博 弈．非完全信息(incompleteinformation)和非完美 信息(imperfectinformation)的区别在于：前者表示 博弈中的个体不精确地知道博弈收益的大小或其他 博弈个体的类型(type)；后者表示博弈过程的信息 集合的元素个数超过一(即不知道博弈中其他个体 的行动(actions))．通过Harsanyi转换(Harsanyi transformation)，可将“非完全信息博弈”转换成“完 全但非完美信息博弈”．在动态博弈中，个体决策的 时间(即行动的先后次序)将对博弈结果起作用．田 忌赛马就是动态博弈的例子之一．本文将介绍完全 信息下非合作博弈的基本概念和演化博弈理论．演 化博弈这一概念最初是由MaynardSmith和Price 在研究对称人口博弈时提出的[4]，他们成功地把博 弈论应用到生物背景中去．其主要思想就是采用依 赖于接触频率的适应度(frequency-dependentfit— ness，对应于博弈论中的效用或收益)的策略更新方 法．近些年，演化博弈论不仅在理论生物学中得到充 分的发展，也在其他学科，如经济学、社会学、心理学 等得到广泛的应用． 近年来，由于复杂网络研究的兴起与发展，使得 人们对各种现实网络的结构演化、复杂性有了比较 清晰的认识．特别是1998年Cornell大学的Watts 和其导师Strogatz在Nature杂志上撰文给出了小 世界网络模型r5]，复杂网络研究迅速引起了诸多领 域中科研工作者的兴趣，特别是物理学界、生物学 界，复杂网络理论得到了充分的探索和发展．1999 年美国NotreDame大学的Barabasi和其学生A卜 bert在Science杂志撰文指出[6]，很多复杂网络的 度分布近似服从幂率分布，也就是常说的无标度网 络(scale—freenetworks)，并给出了一个偏好连接 (preferentialattachment)的模型，简单探讨了这一 现象的内在机制．自20世纪60年代以来，随着匈牙 利数学家Erdos和Renyi的关于随机图论的论文的 发表，人们对真实世界网络的认识停留在随机网络 的认识水平上．Barabasi和AIbert的发现，改变了 以往人们对现实网络的认识，从而成为复杂网络研 究的催化剂．很多有关复杂网络的重要性质、组织规 律及其复杂网络上的动力学的研究论文相继发表， 特别是无标度网络上传染病的阈值问题、复杂网络 的层次性、结构性、自相似性等方面重要的结 果[7-1⋯．有关复杂网络研究的现状，读者可参考文 献[11—15]，这里不再赘述． 复杂网络理论为描述博弈个体之间的博弈关系 提供了方便的系统框架．网络上的节点表示博弈个 体，边代表与其邻居的博弈关系．这样一来，就可以 利用复杂网络拓扑关系，来研究一些复杂的博弈关 系下的博弈．比如，以前的博弈理论中的混合均匀 (well—mixed)假设就可以看成是在全连通图上进行 的博弈．在空间二维格子(1attice)或一维格子(ring) 上博弈即可转化为规则网络上的博弈．然而，真实世 界的网络是异质的(heterogeneous)，大部分节点的 邻居数目存在差异，甚至成幂率分布．因此，研究接 触网络(networkofcontacts)的异质性对其上的博 弈动力学的影响是非常有意义的． 在演化博弈研究中，一个重要的方向就是研究 理性的博弈者之间如何涌现出合作行为．比如，在囚 徒困境博弈(Prisoner'sDilemma)中，每个纯策略的 个体都有2种选择：合作(cooperation，C)与作弊 (defection，D)．D策略个体利用C策略个体，获得 丁收益，而c获得s．双方都合作获得R，都作弊获 得P，其中T>R>P>S，2R>T4-S．在单轮博弈情 况下，无论对手采取何种策略，个体的最佳策略总是 作弊(defect)．然而，在双方都采取合作(cooperate) 策略的情况下，二者总的收益才是最大的．这一现象 说明了社会两难(socialdilemma)问题的实质．当囚 徒困境博弈在2个个体之间进行多次时，每个个体 都可以根据上次博弈的结果选择进行下次博弈的策 略(即迭代囚徒困境博弈)(iteratedprisoner’Sdi— lemmagame)．在20世纪70年代末的Axelrod锦 标赛(Axelrodtournament)中，英国数学家、生物学 家Rapoport提出的Tit—for～Tat(TFT)策略脱颖而 出，打败了其他策略．所谓TFT是一个偏向合作的 策略，第一步采取合作，然后重复其对手上一步的策 略．但是TFT在有环境干扰时表现并不好，此时 万方数据 第2期 王龙，等：复杂网络上的演化博弈 Pavlov策略就能打败TFT．Parlor策略是属于更一 般的Win—Stay—Lose—Shift(WSLS)策略类型． WSLS策略是指个体如果现在的策略获得的收益大 于某个期望水平(aspirationlevel)，那么下一步就保 持这个策略不变，否则就切换到另外一个策略．在演 化博弈中使用较多的另外一个范例是雪堆博弈 (snowdriftgame)．假设合作的收益为b，成本为 c(6>c)，两个个体都选择合作则得到收益6一c／2， 如果都作弊则收益为0．合作者遇到作弊者，则收益 为6一c，作弊者则得到收益b．由于在雪堆博弈中， 选择合作总比选择作弊要好，Nash均衡为混合策略 (合作的频率为X+一(6一c)／(b—c／2)．因此雪堆博 弈被广泛地用于研究生物之间的合作行为．TFT策 略和WSLS策略是建立合作和作弊策略基础上的 宏策略(meta—strategy)．一般在博弈中只考虑最简 单的策略(合作或作弊)，如果囚徒困境博弈在相同 的多个个体之间进行多次，其中个体可以通过记忆 或学习、或者对作弊者进行惩罚，那么在合适的内在 机制之下，合作行为将会涌现并逐渐占据优势．对合 作机制的研究，特别是在复杂网络上的演化博弈背 景中，是目前演化博弈研究的一个热点． ． 2 演化稳定策略与复制动力学 演化稳定策略(evolutionarilystablestrategy， ESS)相关概念最早由英国学者MaynardSmith提 出[16]．策略，是ESS，必须满足条件：如果几乎所有 的个体(population)都采取策略I，那么这些J策略 的个体的适应度要比任何可能的变异策略要大．否 则变异策略可以入侵种群并且_『将不稳定． 有了ESS的概念，就可以判断策略的稳定性。 由于经典博弈中最重要的概念是收益矩阵(payoff matrix)和收益，因此可以把经典博弈中的想法应用 到ESS中来．假设生物的适应度跟收益成正比(或 是收益的函数)，或就等于收益，并且经典博弈中参 与者理性(rationality)选择的策略就对应于ESS．与 传统的Nash均衡相比，ESS这个概念要更加严格 一些，因此可用于平衡点选择．因为所有的ESS必 定是Nash均衡，但只有严格对称Nash均衡才是 ESS．值得一提的是，这里的ESS是一个“静态”的概 念，其假设只要求表现更好的策略具有更快的复制 (增长)速率，并不涉及具体的博弈动力学． 复制动力学(replicatordynamics)在1978年由 Taylor和Jonker引进[1“．其主要假设为给定的策 略类型的单位复制率丝正比于适应度之差： P_L—fitnessoftypei—averagefitness．(1) pi 复制动力学是关于博弈动力学(策略更新)的连 续确定性方程，从而可以赋予前面介绍的ESS这一 静态的概念以动力学含义．复制方程在不动点附近 的稳定性将对应于策略的稳定性(ESS)．复制动力 学与演化稳定性的关系可以总结如下m1引： 1)ESS对应于吸引子； ’ 2)内部ESS对应于全局吸引子； 3)对势博弈(potentialgame)而言，某个不动点 是ESS当且仅当它是吸引子； 4)对2×2矩阵博弈而言，某个不动点是ESS 当且仅当它是吸引子． 3 有限人口上的演化博弈动力学 以往复制动力学及ESS的概念均假设人口为 无限且混合均匀．但更实际一点，往往需要考虑人口 非无限情形，此时演化动力学将受到有限人口因素 的影响而满足随机动力学基本性质(Markov过 程)． 2004年Nowak等人在Nature上发表文章指 出在有限人口的情形下，采用依赖于频率的Moran 过程(birth—deathprocess)，经典的ESS的判据需要 做修改，并提出了在弱选择下的“1／3规则”E20]．假设 种群由N个混合均匀的策略为A或B的个体组 成，收益矩阵为 A B A 口 b B C d 假设有i个A策略的个体，那么策略A和B的适应 度分别为 ^一1～叫+叫[盘(i一1)+b(N—i)]／[N一1]， g。一1～W+叫[d+d(N—i一1)]／[N一1]． (2) 这里适应度由个体原有的基线(baseline)1加 上通过博弈获得的收益经过加权得到．训∈E0，1]， 表示自然选择的强度，即博弈收益对适应度贡献的 大小．在每一时间步长，按照正比于适应度的概率选 择一个个体进行复制，并替代一个随机选取的种群 中个体．A类型的个体可能增加一个，减少一个或保 持不变．因此Markov过程的转移矩阵为三对角矩 阵(tri—diagonalmatrix)，矩阵元素为‰一再‰等，％一藉畿寿， ㈤^一1一万了可矿j。压Ⅳ’ ¨’ 万方数据 智能系统学报 第2卷 P。一l—Pi，升1一P。，l， 其他元素为零．这个随机过程具有2个吸收态(ab— sorbingstate)i一0和i—N．如果种群达到这2个吸 收态之一的话，系统将永远保持状态不变．以z：表 示种群从i个A个体开始演化到i—N终态的概 率，即固定概率(fixationprobability)，那么有以下 关于5C：的递归方程(recursiveequation)嘞_2引： z。一P：，汁1z。+1+P。z。+P。一1zr_1，(4) 边界条件为z。一0和zN一1．方程的解由Karlin和 Taylor在1975年给出[2“： }1 i 1+∑Ⅱ笋 1—1k一1J k (5) 1+∑Ⅱ笋 j一1^一1J女 考虑单个A个体能入侵并占据所有的B个体的概 率： NI| pA—z，一1／(1+∑Ⅱ譬)，(6) 、 ，一l^=1J々7 对于中立博弈(neutralgame)来说，此时w=0，zI一 1／N．若m>1／N，那么自然选择偏向于A取代B． 在有限人口N的情况下，B策略是ESS，记作 ESSN，如果以下条件满足[2⋯： 1)选择不利于A入侵B，这意味着B种群中的 一个变异A具有较低的适应度； 2)选择不利于A取代B，这意味着固定概率 pA标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载