复杂网络上的演化博弈

复杂网络上的演化博弈

王　龙,伏　锋,陈小杰,王　靖,李卓政,谢广明,楚天广

(北京大学工学院,北京100871)

摘　要:主要介绍了近年来复杂网络上的演化博弈研究现状和研究方向.复杂网络理论的发展为描述博弈关系提供了系统且方便的框架,网络上的节点表示博弈个体,边代表与其邻居的博弈关系.介绍了经典演化博弈论中的演化稳定策略概念和复制动力学方程,以及二者的相互联系.介绍了混合均匀有限人口中随机演化动力学问题,并给出了与确定复制方程的相互转化关系.介绍了小世界、无标度等复杂网络上演化博弈的研究结论,给出了复杂网络上演化博弈论的未来发展方向.

关键词:演化博弈论;复制动力学;演化稳定策略;复杂网络;有限人口;合作中图分类号:N949　文献标识码:A　文章编号:167324785(2007)0220001210

Evolutionarygamesoncomplexnetworks

WANGLong,FUFeng,CHENXiao2jie,WANGJing,LIZhuo2zheng,

XIEGuang2ming,CHUTian2guang

(CollegeofEngineering,PekingUniversity,Beijing100871,China)

Abstract:Inthissurvey,recentdevelopmentsandfuturedirectionsofevolutionarygamesoncomplexnet2worksarepresented.Thedevelopmentofcomplexnetworktheoryprovidesasystematicandconvenientframeworkfordescriptionofthedynamicalinteractionsofgames.Theverticesrepresentplayers,whiletheedgesdenotethelinksbetweenplayersintermsofgamedynamicalinteraction.First,someimportantconceptsofevolutionarilystablestrategyandreplicatordynamicsareintroduced,andtheconnectionbe2tweentheevolutionarilystablestrategyandreplicatordynamicsisestablished.Then,thestochasticevolu2tionarydynamicsoffinitewell2mixedpopulationsandtheirrelationshiptothedeterministicreplicatordy2namicsarepresented.Someresultsonfixedprobabilityandtimearealsogiven.Furthermore,somerecentresultsofevolutionarygamesoncomplexnetworkssuchassmall2worldandscale2freenetworksareintro2duced.Finally,unresolvedopenproblems,futureresearchdirections,andpossibleapplicationareasforevolutionarygamesoncomplexnetworksarepointedout.

Keywords:evolutionarygame;replicatordynamics;evolutionarilystablestrategy;complexnetworks;fi2nitepopulations;cooperation

　　博弈论是研究依据其他参与者的效用(utility)情况,理性参与者策略之间相互作用的一门科学[1].博弈论的要素有两点:参与博弈者的目标或利益相互冲突,且他们都是理性的.现代博弈论已成为一门横跨数学、生物、心理学、计算机科学、运筹学、经济、

收稿日期:2006212218.

基金项目:国家自然科学基金资助项目(60674050,60528007);973

国家重点基础研究发展计划资助项目(2002CB312200);863国家高技术研究发展计划资助项目(2006AA04Z258);“十一五”规划资助项目(A2120061303).

哲学、政治、军事战略等领域的交叉学科.公认的现

代博弈论起源于数学家VonNeumann和经济学家Morgenstern的合著:博弈理论和经济行为[2].尽管当时这本著作中的博弈论的理论框架只适用于一些有限的特例,如只讨论了零和非合作博弈问题等,但它第一次用数学语言描述和解决了博弈问题.此后,经过许多学者的努力,特别是Nash在非合作博弈理论中创造性地引入策略均衡的概念,博弈论日渐成为非常重要且有用的分析工具[3].近十多年来,诺

・2・智　能　系　统　学　报　　　　　　　　　　　　　　　　　第2卷

贝尔经济学奖先后授予研究博弈论的科学家Nash、Selten、Harsanyi、Aumann、Schelling等人,说明博

(scale2freenetworks),并给出了一个偏好连接(preferentialattachment)的模型,简单探讨了这一

弈论越来越得到更多人的重视,博弈论的威力也得到越来越广泛的承认.

现象的内在机制.自20世纪60年代以来,随着匈牙利数学家Erdos和Renyi的关于随机图论的论文的发表,人们对真实世界网络的认识停留在随机网络的认识水平上.Barabasi和Albert的发现,改变了以往人们对现实网络的认识,从而成为复杂网络研究的催化剂.很多有关复杂网络的重要性质、组织规律及其复杂网络上的动力学的研究论文相继发表,特别是无标度网络上传染病的阈值问题、复杂网络的层次性、结构性、自相似性等方面重要的结果[7-10].有关复杂网络研究的现状,读者可参考文献[11-15],这里不再赘述.

复杂网络理论为描述博弈个体之间的博弈关系提供了方便的系统框架.网络上的节点表示博弈个体,边代表与其邻居的博弈关系.这样一来,就可以利用复杂网络拓扑关系,来研究一些复杂的博弈关系下的博弈.比如,以前的博弈理论中的混合均匀

(well2mixed)假设就可以看成是在全连通图上进行的博弈.在空间二维格子(lattice)或一维格子(ring)上博弈即可转化为规则网络上的博弈.然而,真实世界的网络是异质的(heterogeneous),大部分节点的邻居数目存在差异,甚至成幂率分布.因此,研究接触网络(networkofcontacts)的异质性对其上的博弈动力学的影响是非常有意义的.

在演化博弈研究中,一个重要的方向就是研究理性的博弈者之间如何涌现出合作行为.比如,在囚徒困境博弈(Prisoner’sDilemma)中,每个纯策略的个体都有2种选择:合作(cooperation,C)与作弊(defection,D).D策略个体利用C策略个体,获得

T收益,而C获得S.双方都合作获得R,都作弊获

1　博弈论和复杂网络

所谓Nash均衡(Nashequilibrium)是指给定博弈中其他个体(player)的策略时,任何一个个体都不能单方面改变自己的策略来增加自己的收益(payoff)的情形.换言之,在Nash均衡中,相对其他个体,个体的所选策略已经是最佳的反应,此时Nash均衡成为一致解的概念.但是,作为博弈一致解的概念,在有些情况下Nash均衡并不是必要条件而是充分条件.因此,博弈论的后Nash均衡时代主要是针对博弈的假设和前提的重新修改和扩展.其中最主要的2个分支:动态博弈和非完全信息博弈.非完全信息(incompleteinformation)和非完美信息(imperfectinformation)的区别在于:前者表示博弈中的个体不精确地知道博弈收益的大小或其他博弈个体的类型(type);后者表示博弈过程的信息集合的元素个数超过一(即不知道博弈中其他个体的行动(actions)).通过Harsanyi转换(Harsanyitransformation),可将“非完全信息博弈”转换成“完

全但非完美信息博弈”.在动态博弈中,个体决策的时间(即行动的先后次序)将对博弈结果起作用.田忌赛马就是动态博弈的例子之一.本文将介绍完全信息下非合作博弈的基本概念和演化博弈理论.演化博弈这一概念最初是由MaynardSmith和Price在研究对称人口博弈时提出的[4],他们成功地把博弈论应用到生物背景中去.其主要思想就是采用依赖于接触频率的适应度(frequency2dependentfit2ness,对应于博弈论中的效用或收益)的策略更新方

得P,其中T>R>P>S,2R>T+S.在单轮博弈情况下,无论对手采取何种策略,个体的最佳策略总是作弊(defect).然而,在双方都采取合作(cooperate)策略的情况下,二者总的收益才是最大的.这一现象说明了社会两难(socialdilemma)问题的实质.当囚徒困境博弈在2个个体之间进行多次时,每个个体都可以根据上次博弈的结果选择进行下次博弈的策略(即迭代囚徒困境博弈)(iteratedprisoner’sdi2lemmagame).在20世纪70年代末的Axelrod锦

法.近些年,演化博弈论不仅在理论生物学中得到充分的发展,也在其他学科,如经济学、社会学、心理学等得到广泛的应用.

近年来,由于复杂网络研究的兴起与发展,使得人们对各种现实网络的结构演化、复杂性有了比较清晰的认识.特别是1998年Cornell大学的Watts和其导师Strogatz在Nature杂志上撰文给出了小世界网络模型[5],复杂网络研究迅速引起了诸多领域中科研工作者的兴趣,特别是物理学界、生物学界,复杂网络理论得到了充分的探索和发展.1999年美国NotreDame大学的Barabasi和其学生Al2bert在Science杂志撰文指出[6],很多复杂网络的度

标赛(Axelrodtournament)中,英国数学家、生物学

家Rapoport提出的Tit2for2Tat(TFT)策略脱颖而出,打败了其他策略.所谓TFT是一个偏向合作的策略,第一步采取合作,然后重复其对手上一步的策略.但是TFT在有环境干扰时表现并不好,此时

分布近似服从幂率分布,也就是常说的无标度网络

第2期　　　　　　　　　　　　　　　　　王　龙,等:复杂网络上的演化博弈・3・

Pavlov策略就能打败TFT.Pavlov策略是属于更一

般的Win2Stay2Lose2Shift(WSLS)策略类型.WSLS策略是指个体如果现在的策略获得的收益大

ρ󰂻i=fitnessoftypei-averagefitness.(1)ρi

　　复制动力学是关于博弈动力学(策略更新)的连续确定性方程,从而可以赋予前面介绍的ESS这一静态的概念以动力学含义.复制方程在不动点附近的稳定性将对应于策略的稳定性(ESS).复制动力学与演化稳定性的关系可以总结如下[18-19]:

1)ESS对应于吸引子;

2)内部ESS对应于全局吸引子;

3)对势博弈(potentialgame)而言,某个不动点是ESS当且仅当它是吸引子;

4)对2×2矩阵博弈而言,某个不动点是ESS当且仅当它是吸引子.

于某个期望水平(aspirationlevel),那么下一步就保持这个策略不变,否则就切换到另外一个策略.在演化博弈中使用较多的另外一个范例是雪堆博弈(snowdriftgame).假设合作的收益为b,成本为

c(b>c),两个个体都选择合作则得到收益b-c/2,

如果都作弊则收益为0.合作者遇到作弊者,则收益为b-c,作弊者则得到收益b.由于在雪堆博弈中,选择合作总比选择作弊要好,Nash均衡为混合策略(合作的频率为x3=(b-c)/(b-c/2).因此雪堆博弈被广泛地用于研究生物之间的合作行为.TFT策略和WSLS策略是建立合作和作弊策略基础上的宏策略(meta2strategy).一般在博弈中只考虑最简单的策略(合作或作弊),如果囚徒困境博弈在相同的多个个体之间进行多次,其中个体可以通过记忆或学习、或者对作弊者进行惩罚,那么在合适的内在机制之下,合作行为将会涌现并逐渐占据优势.对合作机制的研究,特别是在复杂网络上的演化博弈背景中,是目前演化博弈研究的一个热点.

3　有限人口上的演化博弈动力学

以往复制动力学及ESS的概念均假设人口为

无限且混合均匀.但更实际一点,往往需要考虑人口非无限情形,此时演化动力学将受到有限人口因素的影响而满足随机动力学基本性质(Markov过程).

2004年Nowak等人在Nature上发表文章指

2　演化稳定策略与复制动力学

演化稳定策略(evolutionarilystablestrategy,ESS)相关概念最早由英国学者MaynardSmith提出[16].策略I是ESS,必须满足条件:如果几乎所有的个体(population)都采取策略I,那么这些I策略的个体的适应度要比任何可能的变异策略要大.否则变异策略可以入侵种群并且I将不稳定.有了ESS的概念,就可以判断策略的稳定性.由于经典博弈中最重要的概念是收益矩阵(payoffmatrix)和收益,因此可以把经典博弈中的想法应用

出在有限人口的情形下,采用依赖于频率的Moran过程(birth2deathprocess),经典的ESS的判据需要

[20]

做修改,并提出了在弱选择下的“1/3规则”.假设种群由N个混合均匀的策略为A或B的个体组成,收益矩阵为

AAB

ac

Bbd

假设有i个A策略的个体,那么策略A和B的适应度分别为

fi=1-w+w[a(i-1)+b(N-i)]/[N-1],

gi=1-w+w[ci+d(N-i-1)]/[N-1].

(2)

到ESS中来.假设生物的适应度跟收益成正比(或是收益的函数),或就等于收益,并且经典博弈中参与者理性(rationality)选择的策略就对应于ESS.与传统的Nash均衡相比,ESS这个概念要更加严格一些,因此可用于平衡点选择.因为所有的ESS必定是Nash均衡,但只有严格对称Nash均衡才是ESS.值得一提的是,这里的ESS是一个“静态”的概

　　这里适应度由个体原有的基线(baseline)1加上通过博弈获得的收益经过加权得到.w∈[0,1],

表示自然选择的强度,即博弈收益对适应度贡献的大小.在每一时间步长,按照正比于适应度的概率选择一个个体进行复制,并替代一个随机选取的种群中个体.A类型的个体可能增加一个,减少一个或保持不变.因此Markov过程的转移矩阵为三对角矩阵(tri2diagonalmatrix),矩阵元素为

Pi,i+1=

if

i

念,其假设只要求表现更好的策略具有更快的复制(增长)速率,并不涉及具体的博弈动力学.

复制动力学(replicatordynamics)在1978年由Taylor和Jonker引进

[17]

.其主要假设为给定的策

ifiN-i,

+(N-i)giN

(3)

ρ󰂻i略类型的单位复制率ρ正比于适应度之差:

i

Pi,i-1=

(N-i)gii,

ifi+(N-i)giN

・4・智　能　系　统　学　报　　　　　　　　　　　　　　　　　第2卷

Pi,i=1-Pi,i+1-Pi,i-1,

其他元素为零.这个随机过程具有2个吸收态(ab2

sorbingstate)i=0和i=N.如果种群达到这2个吸收态之一的话,系统将永远保持状态不变.以xi表示种群从i个A个体开始演化到i=N终态的概率,即固定概率(fixationprobability),那么有以下关于xi的递归方程(recursiveequation)[20-22]:

xi=Pi,i+1xi+1+Pi,ixi+Pi,i-1xi-1,

(4)

对应于调整复制方程(adjustedreplicatorequation)或MaynardSmith形式的复制方程.如果采用对比较(paircomparison)更新方式,在N→∞时,人口演化的随机动力学形式上将对应于标准复制方程.如果记x=i/N,以ρ(x,t)表示人口在t时刻处于x状态的概率密度,那么ρ(x,t)满足Fokker2Planck方程(FPE)[25-26]:

dρ(d(x,t)]+x,t)=-[a(x)ρdxdx

1d22()ρ([bxx,t)].

2dx2(7)

边界条件为x0=0和xN=1.方程的解由Karlin和Taylor在1975年给出

xi=

[23]

:

i-1

j

j=1k=1N-1j

1+1+

∑∏f∑∏N-1

gkk

式中:,

(5)TT

+j=1k=1

gkfk

(x)=(x)=

fixfxf

i

+(1-x)gi

gi+(1-x)gi

+

x(1-x),x(1-x),

考虑单个A个体能入侵并占据所有的B个体的概率:

j

-

i

ρA=x1=11+

j=1k=1

∑∏gkfk

a(x)=Tb(x)=

(x)-T-(x),

,(6)

(1/N)[T+(x)+T-(x)],

对于中立博弈(neutralgame)来说,此时w=0,x1=1/N.若ρA>1/N,那么自然选择偏向于A取代B.在有限人口N的情况下,B策略是ESS,记作ESSN,如果以下条件满足[20]:

1)选择不利于A入侵B,这意味着B种群中的一个变异A具有较低的适应度;

2)选择不利于A取代B,这意味着固定概率

使用Ito积分,式(7)FPE方程变成Langevin方程:

(8)󰂻x=a(x)+b(x)ξ,

ξ为非相关高斯噪声.在N→∞式中:时,b(x)→0,式(8)方程由随机微分方程变成了确定性的复制方程.文献[26]推广了Nowak的有限人口时弱选择下ESSN的充分条件:当Nwν1时“,1/3规则”是有效

的;对w固定且Nµ1时,传统的ESS判定条件成立.

有限人口因素对人口策略演化的影响是当前研究的一个热点问题.更详细的内容可以参考文献[27-30].

ρA<1/N.

值得一提的是,不像在无限人口中2种策略有可能共存的情况,在有限人口中,某种策略最终会被固定下来(即最终不存在2种策略共存的情况),但达到固定的时间有可能很长,此时讨论固定概率就没有多少意义了.因此固定时间(fixationtime)从另一个方面反映了自然选择如何影响种群进化的速度.一般讨论条件平均固定时间(conditionalmeanfixationtime).在文献[22]、[24]中,发现系统从状态i=1演化到i=N,或从i=N-1到i=0的条件平均固定时间是相等的.进一步地,这一结果跟收益矩阵没有关系,即无论是在A对B是占优的情况下,还是在A和B都是对自己的最好反应等情况下,条件平均固定时间的均值和方差都是相等的.这是一个相当有趣的结果.文献[24]还发现,这一结果对于Wright2Fisher过程或同时有多个变异存在的情况并不成立.

对于有限人口,演化动力学是一个随机过程,那么在人口N趋于无穷大的情况下,二者有没有联系呢?Traulsen等人发现[25],若采用标准的Moran更新过程,在N→∞时,人口演化的随机动力学将

4　复杂网络上的演化博弈

上面所讨论的混合均匀的有限人口中的博弈动力学,相当于在全连通图上的演化博弈问题.复杂网

络或图为描述博弈关系提供了方便的框架:顶点表示博弈个体,边表示博弈关系.在每一时间步长,节点与其所有邻居进行博弈,累积博弈获得的收益,然后根据更新规则进行策略更新,如此这样重复迭代下去.近年来,复杂网络上演化博弈问题,尤其是对合作行为产生的机制的探索,引起了学术界广泛的注意和兴趣[31-33].尽管对合作行为提出了一些可行的机制,但合作行为的本质和真正内在机理,仍然是一个尚未解决的问题[34-35].复杂网络上的演化博弈研究主要可分为2种:一种是研究网络拓扑对合作的影响,主要是静态(static)网络的拓扑性质对合作水平的影响;另外一种是网络拓扑和博弈动力学的共演化(co2evolution),主要是自适应(adaptive)网

第2期　　　　　　　　　　　　　　　　　王　龙,等:复杂网络上的演化博弈・5・

络上博弈动力学,即网络拓扑调整受博弈动力学影响.

Nowak等人首先研究了空间二维格子上的囚

wSx←Sy=

11+exp[(Mx-My)/T]

.(9)

徒困境博弈,即每个博弈个体跟邻近的4个或8个邻居进行博弈.在此基础上发现了美妙的空间混沌[36-37],并发现了对于囚徒困境博弈,博弈个体的空间分布会加强合作(spatialcooperation).但是,Hauert等人发现对于雪堆博弈,博弈个体的空间分

布结构往往会削弱合作水平[38].Szabó等人利用平均场(mean2field)、对估计(pair2approximation)等方法,系统地研究了二维平面各种规则格子上的演化博弈问题[39-41].

由于社会网络具有小世界和无标度等特性,因此研究拓扑特性对合作的影响是十分有意义的.小世界网络上的空间纯策略博弈主要分为2类:一类是基于环的小世界网络;另一类是基于方格的小世界网络.Santos等人研究了同质(homogeneous)和异质(heterogeneous)的小世界网络上的演化博弈问题[42-44].异质小世界网络是由规则网络演化而来:由一个具有N个节点的环开始,环上每一个节点与两侧各有m条边相连.对每条边以概率p随机进行重连(自我连接和重边除外).重连以后,如果保持网络的平均度不变,此时的网络就为异质小世界网络;而同质小世界网络也是由规则网络演化而来:由一个具有N个节点、平均度为z的规则网络开始,其边数为E=N・z/2.以概率p进行交叉换边重连(同样避免重复连边).这样重连以后不改变节点的度的网络就为同质的小世界网络(此时每个节点的度相等,亦称之为规则随机图(regularrandomgraph).对于上述2种小世界网络,当概率p=0时,

相应的网络为规则网络,而当概率p=1时,相应的网络为随机网络.Santos等仿真了环型小世界网络上的“弱”囚徒困境的博弈情形.他们发现平衡态时异质小世界网络上的合作策略比例比同质小世界网络上的要大.在异质小世界网络上,当概率p不断增大时,平衡态时合作策略比例也不断增强[42,45].而在同质小世界网络上,对于囚徒困境博弈,存在一个临界作弊收益值bc,当bbc时,随着概率p不断增大,对应平衡态时合作不断增强[42].Ren[46]等发现在均匀小世界网络上,同时也存在一个临界概率pc,当概率ppc时,平衡态时合作水平反而不断降低.这说明pc为最优概率值,能保证合作最强.大部分工作采取策略演化更新规则:

式中:wSx←Sy表示节点x模仿邻居节点y策略的概率,Mx、My表示节点x、y的累积收益,T表示节点的理性程度.当T=0时,表示完全理性选择;当T→∞时,表示完全随机选择.适当的T也可以加强合作,即存在一个最优的能使博弈合作程度达到最强[46].

Szabó等人也研究了方格小世界网络上的带有loner的囚徒困境博弈问题(即带有志愿者参加(volunteeringparticipation)的囚徒困境博弈),发现重连概率大于一定的阈值时,相图会发生振荡[47].有趣的是,若分别用优先选择邻居和随机选择邻居的演化规则,在方格小世界上会发现优先选择邻居能促进合作[48-49].Tomassini等仿真研究了方格小世界网络上的鹰鸽博弈(hawk2dovegame,数学上等价于前面所提到的雪堆博弈),发现平衡态的合作与演化规则、收益比(gain2to2cost)r以及重连概率

[50]

p相关.

Santos和Pacheco等采用同步更新的策略模仿(strategyimitation)更新方法对无标度网络上的空间纯策略博弈行为进行了较系统的研究[43,51-53],发现与规则网络、随机网络相比,无标度网络更有利于合作行为的产生.因此网络拓扑的异质性(度分布为幂率分布)是提升合作水平的一个重要因素.Ren等采用“优先学习”方法,即优先选择邻居来进行模仿演化,数值仿真显示平衡态时合作水平得到加强[54].类似于亲缘选择中的合作判据Hamilton规则[55],Ohtsuki等人发现在网络上合作行为产生的一个充分性判据:b/c>k,其中b、c分别为合作行为的收益和代价,k为网络的平均度[56].这一合作行为简单判定规则适用于二维格子、随机网络和无标度社会网络.考虑在网络上的入侵和固定动力学(dy2namicsofinvasionandfixation),即一个变异A入侵种群B的固定概率,Antal等人发现在度不相关无标度网络上的一个变异的固定概率跟它发生的节点的度相关,且发现对投票模型(votermodel),固定概率正比于度,对生灭(birth2death)过程,固定概率反比于度[57].除了网络的异质性对合作行为有影响外,网络的平均度也是影响合作涌现的重要因素之一.文献[58]研究了随机图、小世界、无标度3种网络中平均度对合作水平的影响,发现对于每种网络均存在适当的平均度使得合作水平最优.

另一方面,博弈动力学与网络拓扑共演化的问题也得到一些关注和研究.网络拓扑影响博弈结果,而博弈结果反过来作用于网络拓扑,调整网络拓扑

・6・智　能　系　统　学　报　　　　　　　　　　　　　　　　　第2卷

(或社会关系),这种情形更符合实际.Zimmermann

等人认为个体可以依据博弈结果调整与邻居的边来

实现合作者与合作者之间的联合,从而有利于合作行为的涌现和维持[59-60].Santos等人考虑了网络拓扑调整与博弈演化之间的时间尺度的关系,并假设不满意博弈结果的节点以一定概率断开与邻居中作弊者的边,并随机重连到作弊者的邻居,发现存在时间尺度之比的临界值,一旦超过这个临界值,合作将会占上风[61].Pacheco等人考虑了简化的情形,提出了活跃连接(activelinking)的假设,在一定条件下,自然选择将偏向于合作[62].目前文献中关于这方面的结果比较少,但这个问题又为大家所关注,因此这个问题将是今后研究的一个重点.

得到平衡态时合作者的比例.每个数据点对应于40次不同的网络实现和初始分布条件下合作者比例的平均值.图1显示了相同网络规模,但不同平均度m+n及不同社团内外连接数之比m/n时的合作频率对参数b的变化情况.可以发现,在具有社团结构无标度网络上,随着平均度m+n的增加,合作水平也相应地减小.同时,在保持平均度m+n不变,改变内外连接数之比m/n时,合作水平随着m/n减小而降低.另外,在没有外部连接时(对应于n=0),合作水平总是最优的.此时对应于3个Barabasi2Al2bert(BA)无标度网络,而无标度网络是利于合作的涌现的[51],因此此时合作水平最高.随着外部连接数的增加、内部连接的较少,网络结构中的一些hub(网络中度较大的节点)并不直接相连,并且网络中回路(loop)减少了,这些因素影响了合作水平[63].

5　演化囚徒困境博弈中的合作涌现真实社会的网络拓扑除了具有小世界、无标度等性质外,还具有社团结构(communitystructure)这一重要的性质.社团结构是指整个网络是由若干个“群(group)”或“团(cluster)”构成的.每个群内部的节点之间的连接相对比较紧密,但是各个群之间的连接却比较稀疏.因此,研究社团结构对合作水平的影响是很有意义的.笔者研究了具有社团结构的无标度网络上的囚徒困境博弈问题[63].不失囚徒困境博弈的一般特性,博弈矩阵M取为[36]

M=

1

b

00.(10)

式中:1C=

10,D=

01.

图1　对应于不同m+n与m/n时合作频率

对参数的变化情况

Fig.1　Frequencyofcooperatorsvs.bcorrespondingto

differentm+nandm/n

个体x的收益为他跟所有邻居博弈一次的收益的总和:Px=∑sMsy,其中sx、sy表示节点的状态Ω

y∈x

T

x

(策略),Ωx表示x的所有邻居.采用同步更新规则

(synchronousupdaterule),在每一时间步长,节点

x从其邻居中随机选取节点y进行策略更新,若Py>Px,则以概率

Wsx←xy=

Py-Px.bk>

(11)

文献[51-53]指出复杂网络的异质性是影响合作水平的重要因素.但复杂网络的异质程度大小会对合作水平产生什么影响呢?考虑了异质New2man2Watts小世界网络上的演化囚徒困境博弈问

采用节点y所用的策略sy,其中k>为节点x和y的度中的较大值.初始时刻,合作者与作弊者等比例随机分布在网络顶点上.系统演化10000时间步长后,再取1000步时间步长上合作者比例的平均数,

题[65].与Watts2Strogatz小世界模型中断边重连机制不同[5],本文采用改进的Newman2Watts小世界模型,即在低维规则环上添加m条长程边形成小世界网络.首先随机地从N个节点中选出Nh个节点

第2期　　　　　　　　　　　　　　　　　王　龙,等:复杂网络上的演化博弈・7・

图2　对应于不同参数b时合作水平随着

网络异质程度Nh/N的变化情况

Fig.2　Frequencyofcooperatorsvs.Nh/N

correspondingtodifferentb

图3　合作水平在参数空间(b,Nh/N)中的变化情况

Fig.3　Frequencyofcooperatorsasafunction

ofparameterspace

作为hub.然后使添加的长程边至少保证每条边一个端点随机地与选出的Nh个hub中的一个相连,另一个端点则随机地与N个节点中的一个相连(避免自连和重边).可以看出,参数Nh/N可反映拓扑异质性的大小.Nh/N=1时,网络退化到一般均质小世界的情形,而Nh/N=1/N对应网络最异质的情形,即所有的长程边都与唯一的hub相连.博弈矩阵采用式(10),更新规则采用式(11).网络节点规模N=2001,长程边数m=1000.所有的数据点对于100次运行取平均,即10次网络拓扑实现对应于10次不同的初始条件分布.初始时刻,合作者和作弊者等比例随机分布在网络上,在经过10000步演化后,再取2000步结果作平均,作为平衡时合作者的比例.图2给出了对应于不同参数b合作水平随着网络异质程度Nh/N的变化情况.可以发现,对于固定的b,总存在适当的网络异质程度Nh/N,使得合作水平最高.也就是说,合作水平在Nh/N取某个值时达到最大值,此时网络的异质程度既不是最大的也不是最小的.图3显示了合作水平在参数空间(b,Nh/N)中变化情况.合作水平的大小由右边的色带标记.同样地,可以发现,对于固定的b,合作水平在Nh/N≈0.01时达到最优.另外,在更新规则使用节点的平均收益,而不是累积收益时,会削弱网络异质性对合作水平的影响[65].

头-剪刀-布(rock2scissors2paper)博弈.近来一些文献开始关注这些问题,也得到了一些有趣的结果[66-68].

目前很多工作只是一些数值仿真结果,由于数学工具的不足,对复杂网络上的博弈动力学进行解析分析是非常困难的,目前的一些近似方法,如平均场方法、对估计方法在异质程度很大的网络很有可能失效.因此寻求有效的数学工具,探求更好的理论结果,将一些数值结果命题化、严格化,将是十分有意义的.

在演化网络上的博弈动力学还没有得到充分的研究.研究网络拓扑和博弈动力学共演化将是一个非常有前景的方向.另外,还可以对个体的学习、记忆等能力上进行更为合理的描述,使得模型能更好地反应现实,解决一些社会、经济中的公开问题.对合作机制的研究,目前还没有统一的认识,依然是演化博弈研究中的一个重要方向.当前演化博弈主要集中在合作行为的研究上[69],除了考虑可能的内在合作机制外,还可以考虑复杂网络上的其他动力学行为,应用演化博弈的思想,解决一些实际问题,如在“路由问题”“、传染病传播问题”“、生物进化”“、最

[70]

优控制设计”“、市场经济行为规律”等问题上做进一步的探索将是十分有意义的.

近年来有关复杂系统和复杂性科学的研究蓬勃发展[71-76],这对人们原先的还原论的认识带来革命性的新思潮.物理学家Hawking说:21世纪将是复杂性科学的世纪.复杂网络上的演化博弈研究,对当前国际上关注研究的多智能体(multi2agent)协作、群体行为(collectivebehavior)控制等热点问题,也将带来新的视角和方法[77-84].总之,复杂网络上的演化博弈可作为研究复杂系统、复杂性科学一个可行的切入点,并将会在生态演化、神经网络、群体智能、

6　结论与展望

复杂网络上的演化博弈研究是近年来随着复杂

网络研究兴起而逐渐引起关注的一个重要研究课题.目前大部分工作都集中在囚徒困境博弈或雪堆博弈研究上,其他类型的博弈还缺乏系统的研究.因此有必要进一步考虑多人博弈的情形,如公用品博弈(publicgoodsgame)或者多策略的博弈,如石

・8・智　能　系　统　学　报　　　　　　　　　　　　　　　　　第2卷

1978,40:145-156.

[18]HOFBAUERJ,SIGMUNDK.Evolutionarygamesand

populationdynamics[M].Cambridge:CambridgeUni2versityPress,1998.

[19]HOFBAUERJ,SIGMUNDK.Evolutionarygamedy2

namics[J].BullAmMathSoc,2003,10(4):479-519.

[20]NOWAKMA,SASAKIA,TAYLORC,FUDEN2

BERGD.Emergenceofcooperationandevolutionarystabilityinfinitepopulations[J].Nature,2004,428(6983):646-650.[21]TAYLORC,FUDENBERGD,SASAKIAKIRA,

etal.Evolutionarygamedynamicsinfinitepopulations[J].BullMathBio,2004,66:1621-1644.

[22]ANTALT,SCHEURINGI.Fixationofstrategiesfor

anevolutionarygameinfinitepopulations[J].BullMathBio,2006,68(8):1522-1906.

[23]KARLINS,TAYLORHM.Afirstcourseinstochas2

ticprocess:2nded[M].London:AcademicPress,1975.

[24]TAYLORC,IWASAY,NOWAKMA.Asymmetry

offixationtimesinevolutionarydynamics[J].JournalofTheoBio,2006,243:245-251.

[25]TRAULSENA,CLAUSSENJC,HAUERTC.Coev2

olutionarydynamics:fromfinitetoinfinitepopulations[J].PhysRevLett,2005,95(23):238701.

[26]TRAULSENA,PACHECOJM,IMHOFLA.Sto2

chasticityandevolutionarystability[J].PhysRevE,2006,74:021905.

[27]CLAUSSENJC,TRAULSENA.Non2Gaussianfluc2

tuationsarisingfromfinitepopulations:exactresultsfortheevolutionaryMoranprocess[J].PhysRevE,2005,71:025101.

[28]TRAULSENA,CLAUSSENJC,HAUERTC.Coev2

olutionarydynamicsinlarge,butfinitepopulations[J].PhysRevE,2006,74:011901.

[29]TRAUSLENA,NOWAKMA,PACHECOJM.Sto2

chasticdynamicsofinvasionandfixation[J].PhysRevE,2006,74:021905.

[30]FORSTERR,ADAMIC,WILKECO.Selectionfor

mutationalrobustnessinfinitepopulations[J].JournalofTheoBio,2006,243:181-190.

[31]SZABOG,FATHG.Evolutionarygamesongraphs

[EB/OL].arXiv:cond2mat/0607344.

[32]DOEBELIM,HAUERTC.Modelsofcooperation

basedonthePrisoner’sDilemmaandtheSnowdriftgame[J].EcologyLetters,2005(8):748-766.[33]NOWAKMA,SIGMUNDK.Evolutionarydynamics

ofbiologicalgames[J].Science,2004,303:793-799.[34]PENNISIE.Howdidcooperativebehaviorevolve?

Hierarchicalorganizationof

认知科学、自组织涌现行为、网络化系统(networked

systems)、经济动力学等研究中彰显它的作用.

参考文献:

[1]ROSSD.Gametheory[EB/OL].StanfordEncyclopediaofPhilosophy:http://plato.stanford.edu/entries/game2theory/,2006-03-10.

[2]VONNEUMANNJ,MORGENSTERNO.Thetheoryofgamesandeconomicbehavior:2nded[M].Princeton:PrincetonUniversityPress,1947.

[3]NASHJ.Equilibriumpointsinn2persongames[J].Proc

NatlAcadSci(USA),1950,36:48-49.

[4]SMITHJM,PRICEGR.Thelogicofanimalconflict[J].Nature,1973,246(5427):15-18.

[5]WATTSDJ,STROGATZSH.Collectivedynamicsof’

small-world’networks[J].Nature,1998,393(6684):440-442.

[6]BARABASIAL,ALBERTR.Emergenceofscalinginran2domnetworks[J].Science,1999,286(5439):509-512.[7]PASTOR2SATORRASR,VESPIGNANIA.Epidemic

spreadinginscale2freenetworks[J].PhysRevLett,2000,86(14):3200-3203.

[8]RAVASZE,BARABASIAL.Hierarchicalorganizationincomplexnetworks[EB/OL].arXiv:cond-mat/0206130.

[9]RAVASZE,SOMERAAL,MONGRUDA,OLTVAI

ZN,BARABASIAL.(5596):1551-1555.

[10]SONGC,HAVLINS,MAKSEHA.Self2similarityof

complexnetworks[J].Nature,2005,433(7024):392-395.[11]ALBERTR,BARABASIAL.Statisticalmechanicsof

complexnetworks[J].RevModPhys,2002,74(1):47-97.

[12]STROGATZSH.Exploringcomplexnetworks[J].

Nature,2001,410(6825):268-276.

[13]WANGXF,CHENGR.Complexnetworks:small2

world,scale2freeandbeyond[J].IEEECirSysMag,2003,3(1):6-20.

[14]NEWMANMEJ.Thestructureandfunctionofcom2

plexnetworks[J].SIAMReview,2003,45(2):167-256.

[15]BOCCALETTIS,LATORAV,MORENOY,etal.

Complexnetworks:structureanddynamics[J].Phys2icsReports,2006,424:175-308.

[16]SMITHJM.Evolutionandthetheoryofgames[M].

Cambridge:CambridgeUniversityPress,1982.[17]TAYLORPD,JONKERL.Gamedynamicsandevolu2

tionarystablestrategies[J].MathematicalBiosciences,modularityinmetabolicnetworks[J].Science,2002,297

第2期　　　　　　　　　　　　　　　　　王　龙,等:复杂网络上的演化博弈

[J].Science,2005(309):93.

[35]COLMANAM.Thepuzzleofcooperation[J].Nature,

2006,440:744-745.

[36]NOWAKMA,MAYRM.Evolutionarygamesand

spatialchaos[J].Nature,1992,359:826-829.[37]NOWAKMA,MAYRM.Thespatialdilemmasofe2

volution[J].InternationalJournalofBifurcationandChaos,1993,3(1):35-78.

[38]HAUERTC,DOEBELIM.Spatialstructureoftenin2

hibitstheevolutionofcooperationinthesnowdriftgame[J].Nature,2004,428:643-646.

[39]SZABOG,TOKEC.Evolutionaryprisoner’sdilemma

onasquarelattice[J].PhysRevE,1998,58:69-73.[40]VUKOVJ,SZABOG,SZOLNOKIA.Cooperationinthenoisycase:Prisoner’sdilemmagameontwotypesofregularrandomgraphs[J].PhysRevE,2006,73:067103.

[41]SZABOG,HAUERTC.Phasetransitionsandvolun2

teeringinspatialPublicGoodsGames[J].PhysRevLett,2002,89:118101.

[42]SANTOSFC,RODRIGUESJF,PACHECOJM.

Epidemicspreadingandcooperationdynamicsonhomo2geneoussmall2worldnetworks[J].PhysRevE,2005,72:056128.

[43]SANTOSFC,PACHECO.Anewroutetotheevolu2

tionofcooperation[J].JournalofEvolBio,2006,19(3):726-733.

[44]PACHECOJM,SANTOSFC.Networkdependence

ofthedilemmasofcooperation[A].Scienceofcomplexnetworks:frombiologytotheinternetandWWW.AIPConferenceProceedings[C].AIP,2005.

[45]ABRAMSONG,KUPERMANM.Socialgamesina

socialnetwork[J].PhysRevE,2001,63:030901.[46]RENJ,WANGWX,QIF.Randomnessenhancesco2

operation:coherenceresonanceinevolutionarygame[EB/OL].eprintarXiv:physics/0607457.

[47]SZABOG,VUKOVJ.Cooperationforvolunteering

andpartiallyrandompartnerships[J].PhysRevE,2004,69:036107.

[48]WUZX,XUXJ,CHENY,WANGYH.Spatial

prisoner’sdilemmagamewithvolunteeringinNewman-Wattssmall-worldnetworks[J].PhysRevE,2005,71:037103.

[49]WUZX,XUXJ,HUANGZG,WANGSJ,WANG

YH.Evolutionaryprisoner’sdilemmagamewithdy2namicpreferentialselection[J].Phys.Rev.E,2006,74:021107.

[50]TOMASSINIM,LUTHIL,GIACOBINIM.Hawks

anddovesonsmall-worldnetworks[J].PhysRevE,2006,73:016132.

・9・

[51]SANTOSFC,PACHECOJM.Scale2freenetworks

provideaunifyingframeworkfortheemergenceofco2operation[J].PhysRevLett,2005,95:098104.[52]SANTOSFC,RODRIGUESJF,PACHECOJM.

Graphtopologyplaysadeterminantroleintheevolu2tionofcooperation[J].ProcRoyalSoc.LondonB,2006,273:51-55.

[53]SANTOSFC,PACHECOJM,LENAERTST.Evo2

lutionarydynamicsofsocialdilemmasinstructuredhet2erogeneouspopulations[J].ProcNatlAcadSci

(USA),2006,103(9):3490-3494.[54]RENJ,WANGWX,YANG,WANGBH.Emer2

genceofcooperationinducedbypreferentiallearning[EB/OL].Eprint:arXiv:physics/0603007.

[55]HAMILTONWD.Thegeneticalevolutionofsocialbe2

havior[J].JournalofTheorBiol,1964(7):1-16.[56]OHTSUKIH,HAUERTC,LIEBERMANE,

NOWAKMA.Asimplerulefortheevolutionofcoop2erationongraphsandsocialnetworks[J].Nature,2006,441:502-505.

[57]ANTALT,REDNERS,SOODV.Evolutionarydy2

namicsondegree2heterogeneousgraphs[J].PhysRevLett,2006,96:188104.

[58]TANGCL,WANGWX,WUX,WANGBH.Effect

ofaveragedegreeoncooperationinnetworkedevolu2tionarygame[J].EurPhysJB,2006,53:411-415.[59]ZIMMERMANNM,EGUILUZVM,MIGUELMS.

Coevolutionofdynamicalstatesandinteractionsindy2namicnetworks[J].PhysRevE,2004,69:065102.[60]ZIMMERMANNMG,EGUILUZVM.Cooperation,

socialnetworks,andtheemergenceofleadershipinaprisoner’sdilemmawithadaptivelocalinteractions[J].PhysRevE,2005,72:056118.

[61]SANTOSFC,PACHECOJM,LENAERTST.Co2

operationprevailswhenindividualsadjusttheirsocialties[J].PLOSComputationalBiology,2006,2(10):1284-1291.

[62]PACHECOJM,TRAULSENA,NOWAKMA.Ac2

tivelinkinginevolutionarygames[J].JThoerBiol,2006,243:437-443..

[63]CHENXJ,FUF,WANGL.Prisoner’sdilemmaoncom2

munitynetworks[J].PhysicaA,2006(12):24-29.[64]LICG,MAINIPK.Anevolvingnetworkmodelwith

communitystructure[J].JPhysA:MathGen,2005,38:9741-9749.

[65]FUF,LIULH,WANGL.Evolutionaryprisoner’sdi2

lemmagameonsocialnetworks[EB/OL].eprint:arX2iv:math.DS/060926.

[66]HAUERTC,MONTESD,HOFBAUERJ,etal.

Volunteeringasredqueenmechanismforcooperationin

・10・智　能　系　统　学　报　　　　　　　　　　　　　　　　　第2卷

[83]XIAOF,WANGL.Dynamicbehaviorofdiscrete2time

multi2agentsystemswithgeneralcommunicationstruc2tures[J].PhysicaA,2006,370:364-380.

[84]LIUB,CHUTG,WANGL,WANGZ.Collective

motionofaclassofsocialforagingswarms[J].Chaos,Solitions&Fractals,2006(11):21-28.

publicgoodsgames[J].Science,2002,296:1129-1132.

[67]BRANDTH,HAUERTC,SIGMUNDK.Punishing

andabstainingforpublicgoods[J].ProcNatlAcadSci(USA),2006,103(2):495-497.

[68]IMHOFLA,FUDENBERGD,NOWAKMA.Evo2

lutionarycyclesofcooperationanddefection[J].ProcNatlAcadSci(USA),2005,102(31):10797-10800.[69]NOWAKMA.Fiverulesfortheevolutionofcoopera2

tion[J].Science,2006,314:1560-1563.

[70]VINCENTTL,VINCENTTLS.Evolutionandcon2

trolsystemdesign[J].IEEEControlSystemsMaga2zine,2000,20(5):20-35.

[71]BARABASIA2L.Tamingcomplexity[J].NaturePhys2ics,2005(1):68-70.

[72]ANDERSONP,ARROWKJ,PINESD.Theecono2

myasanevolvingcomplexsystem[M].NewYork:Addison2Wesley,1988.[73]AXELORDRM.Thecomplexityofcooperation:a2

gent2basedmodelsofcompetitionandcollaboration[M].NewJersey:PrincetonUniv.Press,1997.[74]WALDROPMM.Complexity:theemergingscienceat

theedgeoforderandchaos[M].NewYork:Youch2stoneBooks,1993.

[75]HOLLANDJH.Hiddenorder:howadaptationbuilds

complexity[M].NewYork:Addison2Wesley,1996.[76]KAUFFMANS.Athomeintheuniverse:thesearch

forlawsofself2organizationandcomplexity[M].Ox2ford,UK:OxfordUniv.Press,1996.

[77]WANGL,SHIH,CHUTG,ZHANGW,ZHANGL.

Aggregationofforgingswarms[A].LectureNotesinAr2tificialIntelligence[C].Berlin,Springer,2004.

[78]CHUTG,WANGL,CHENTW.Self2organizedmo2

tioninanisotropicswarms[J].JournalofControlThe2oryAppl,2003(1):77-81.

[79]CHUTG,WANGL,CHENTW,MUSM.Com2

plexemergentdynamicsofanisotropicswarms:conver2gencevsoscillation[J].ChaosSolitons&Fractals,2006,30(4):875-885.

[80]MUSM,CHUTG,WANGL.Coordinatedcollective

motioninamotileparticlegroupwithaleader[J].PhysicaA,2005,351:211-226.

[81]SHIH,WANGL,CHUTG.Virtualleaderapproachto

coordinatedcontrolofmultiplemobileagentswithasym2metricinteractions[J].PhysicaD,2006,312:51-65.[82]XIAOF,WANGL.Stateconsensusformulti2agent

systemswithswitchingtopologiesandtime2varyingde2lays[J].InternationalJournalofControl,2006,79(10):1277-1284.

作者简介:

王　龙,男,1964年生,教授,博士生导师,长江学者,是国家教委跨世纪人才基金、国家杰出青年科学基金获得者.主要研究方向复杂系统智能控制、多机器人系统的协调与控制、网络化控制系统的分析与综合、集群行为与集群智能、复杂网络上的演化博弈等,获得国家教委霍英东奖(研究类一等奖)、国

家自然科学奖、国家教委科技进步奖(一等奖)、第一届Ho

OutstandingPaperAward、第一届关肇直控制理论奖等多项

奖励.曾应邀赴美国讲学,并在亚太地区国际学术大会上作大会报告.

王龙教授目前担任国际自动控制联合会(international

federationofautomaticcontrol)网络系统技术委员会成员、

《自然科学进展》《、智能系统学报》《、自动化学报》《、控制理论与应用》《、电子科学与工程学报》《、动力学与控制学报》、《系统工程学报》《、控制与决策》《、信息与控制》《、北京大学学报》《、ElsevierJournalofAppliedMathematicsandCom2

putation》、《InternationalJournalofComputerSystems》、

《JournalofControlTheoryandApplications》编委、中国科学院系统复杂性研究中心学术委员会副主任、北京大学系统与控制研究中心主任、智能控制实验室主任、北京大学先进技术研究院空天智能系统研究中心主任、国家湍流与复杂系统重点实验室副主任、中国人工智能学会理事、国家出国留学基金评审专家等.

E2mail:longwang@pku.edu.cn.

伏　锋,男,1981年生,博士研究生,主要研究方向为实证网络分析、网络建模、复杂网络上演化博弈动力学等.

E2mail:fufeng@pku.edu.cn.

陈小杰,男,1982年生,博士研究生,主要研究方向为网络建模、复杂网络上演化博弈动力学等.

E2mail:xjchen@pku.edu.cn.