基于Agent的演化博弈下的合作行为研究

王 健 赵 凯

(华侨大学，厦门 361000)



基于Agent的演化博弈下的合作行为研究

王 健 赵 凯

(华侨大学，厦门 361000)

文章在演化博弈的视角下，利用重复囚徒困境博弈(IPD)对合作的演化进行分析。在平均场假设下，合作策略无法在竞争中生存。而在基于Agent的演化博弈中，合作策略有可能获得成功。其原因在于通过限制合作行为的范围，可以使合作者聚集成簇状，从而防止合作的红利被背叛者占有。通过理论推导与计算机仿真，文章证明了利他策略获得成功的条件是c/b/1/m，并对此结果做出了解释。

合作 演化博弈 IPD Agent 种群博弈模型

引 言

合作行为意味着合作者付出一定的成本以期获得共赢的局面，但机会主义者却可以逃避付出并享受别人的合作行为带来的好处。在达尔文主义的视角下，自然选择并不会垂青于合作者。人类文明的产生和发展都依赖于大规模的合作，因此合作行为如何得以产生并持续发展壮大就成为了自然科学和社会科学领域的一个重大问题，不少学者也对此进行了研究。其中Trivers(1971)的互惠理论认为合作行为类似于投资，目的是为了在可预见的将来得到相应的回报[1]；Boyd和Richerson(1982)从文化传播的角度对合作的产生和演化进行了解释[2]；Zahavi(1975)的昂贵信号理论表明，合作行为可以被看作一种信号，让发送者表明自己的类型以提高自己的社会地位[3]；除此之外，Alexander(1987)的间接互惠(Indirect Reciprocity)[4]以及Nowak和Sigmund(1998)基于声誉(Image Scoring)机制的模型[5]等都从不同的视角对合作行为的产生和维持进行了有益的探索。

合作产生于人与人之间的互动，因此博弈论便成为了研究合作行为的强大工具。其中囚徒困境博弈(PD)经常被用来研究合作的产生和演化。在经典博弈论①下对囚徒困境博弈进行分析可知。双方都选择背叛是唯一的纳什均衡，这个结果对有限次IPD也是适用的。在无限次IPD中，根据无名氏定理(Folk Theorem)，合作可以构成一个SPNE的结果。Kreps等(1982)通过把不完全信息引入动态博弈，论证了当参与人的理性不是共同知识的情况下，合作可以在有限次IPD中出现[6]。

演化博弈论(Maynard Smith，1982)的发展也为合作行为提供了新的视角[7]。演化博弈论不再将人模型化为超级理性的博弈方，认为人类通常是通过试错的方法达到博弈均衡的。依赖于平均场(Mean-field)假设的演化博弈也称为种群博弈(Population Game)。种群博弈认为种群中的个体总是以相同概率与其他个体进行博弈，因此不同策略的收益完全取决于种群中不同类型个体的比例。种群博弈的核心概念是策略的演化稳定性。Maynard Smith和Price(1973)提出的演化稳定策略(ESS)的概念认为种群中的ESS可以抵挡小部分突变策略的入侵，因而具有演化稳定性[8]。Taylor和Jonker(1978)把个体的繁殖率与其在博弈中的收益联系在一起，通过复制者动态方程来研究模型的动态演变过程[9]。Foster和Young(1990)提出了随机稳定性(Stochastic Stability)的概念[10]，Cabrales(2000)采用了随机微分方程来建立随机复制者动态模型[11]。

与种群博弈不同的是，有些时候个体之间的相互作用与它们之间的距离存在密切关系，此时种群的微观结构就会对博弈的结果产生影响，这种模型通常被称为基于Agent的演化博弈模型②，这个概念最早由诺瓦克等人(Nowak和May，1992；Nowak等，1994)提出[12，13]。在基于Agent的演化博弈模型中，博弈参与者被置于网络中的节点上，并与临近的个体(Neighborhood)进行博弈，在每轮博弈结束后，每个参与人根据一定的更新规则来改变自身的状态，大量参与人通过简单的相互作用构成动态系统的演化。

在一个典型的基于Agent的演化博弈模型中，网络中每个节点表示一个参与人，所有的参与人都是同质的。每个参与人与其邻居③分别进行二人矩阵博弈(Matrix Game)，博弈的收益矩阵为A。位于节点x的参与人可以使用Q种纯策略中的一种，每种纯策略都可表示为一个Q维向量。

x与其邻居分别进行二人博弈，并累计每次博弈的收益，构成x的收益函数Ux。

其中Ωx表示x的邻居构成的集合。

在博弈结束之后，参与人会通过一定的更新规则选择性地改变自己的策略。如果每个参与人都同时进行策略更新，这种更新过程就称之为同步更新(SynchronousUpdate)，反之就称为异步更新(AsynchronousUpdate)。常用的更新规则包括变异(Mutation)、模仿(Imitation)、WSLS(Win-Stay-Lose-Shift)等。以下仅简要介绍本文将使用的更新规则——模仿。

模仿的更新规则可被看作是一种Moran过程，在这个规则下，在每轮博弈结束之后，参与人x将从其邻居Ωx中随机选出参与人y。x把策略sx改变为sy当且仅当y的收益大于x。

如果我们用w(sx→sx′)表示单位时间内x的策略的变化率，则有下式成立：

在基于Agent的演化博弈模型中，计算机仿真是经常被使用的。本文在演化博弈的框架下，通过囚徒困境博弈研究合作的演化：(1)在平均场假设下，建立一个种群博弈模型，用复制者动态方程研究模型的均衡解。(2)在二维网络建立一个基于Agent的演化博弈模型，并使用Netlogo软件进行计算机仿真。(3)对两个模型的结果进行比较，得出相应的结论。

1 模 型

我们通过一个囚徒困境博弈来阐述合作行为的演化问题。在演化博弈中存在两种参与人，合作者C与背叛者D。合作者付出c的成本，并给对方带来b的收益(在本文中我们始终假设b>c，即合作的收益大于成本，否则合作就没有意义了)。而背叛者不付出任何成本，也不给对方带来任何收益。博弈的收益矩阵如下表所示：

CDCDb-c,b-c-c,bb,-c0,0

下面我们分别建立种群博弈模型与基于Agent的演化博弈模型，并对二者进行理论推导和计算机仿真。

1.1 种群博弈模型(Population Game)

在种群博弈模型中，我们只需要考虑不同类型的个体在群体中的比例。以下使用复制者动态方程的方法分析模型的动态演变。

UC=Pt*(b-c)+(1-Pt)*(-c)=bPt-c

UD=Pt*b+(1-Pt)*0=bPt

在演化博弈中，我们假设每个参与人的繁殖率等于它在博弈中的收益，且后代的类型与亲代相同。经过dt的时间，合作者在群体中所占的比例Pt+dt可由下式算出：

1.2 基于Agent的演化博弈模型

我们在一个二维规则网络中建立演化博弈模型。每位参与人占有一个网格，在每轮博弈中，它与上下左右的四位邻居(Von Neumann Neighborhood)进行囚徒困境博弈，并累计博弈的收益。

为了反映博弈的动态演化，在每轮的阶段博弈结束后，每位参与人可以对自己与邻居们的收益进行比较，如果邻居的收益高于自己的收益，则把自己的策略改变为四位邻居中收益最高的策略，否则就保持原有的策略不变。

我们研究的重点是：合作者是否可以入侵由背叛者占据的群体，或是反过来背叛者是否可以入侵合作者的群体。由于合作者与背叛者的分布可能出现的不同情况非常之多，很难用解析方法进行求解(Nowak，2006)[14]。以下我们分别分析这两个问题。

1.2.1 合作者入侵背叛者

我们用不同颜色网格表示不同的参与人：其中灰色表示合作者，白色表示背叛者。下图展现的是一个由背叛者构成的群体中出现了一小部分的合作者，其中合作者占据了群体中3*3的网格。根据分析的需要，我们只画出了合作者与部分背叛者，并写出它们在博弈中的收益。

(1)当b>4b-4c时，0.75

(2)当3b-4c

(3)当b=3b-4c时，c/b=0.5，合作者的数量保持在9个不变。

(5)当b<2b-4c时，c/b<0.25，合作者的数量将在下期扩张为21个，并持续扩张。

由此可见，合作者入侵背叛者，并最终在群体中占据主导地位的条件是c/b<0.25。

1.2.2 背叛者入侵合作者

采用类似的方法，我们画出被合作者包围的背叛者在博弈中的收益。

4b-4c3b-4c3b-4c3b-4c4b-4c3b-4c2bb2b3b-4c3b-4cb0b3b-4c3b-4c2bb2b3b-4c4b-4c3b-4c3b-4c3b-4c4b-4c

(1)当3b-4c>2b时，c/b<0.25，背叛者的数量将在下期缩减为1个，并最终保持在4个。

(2)当3b-4c≤2b≤4b-4c时，0.25≤c/b≤0.5，背叛者的数量保持不变。

(3)当b<4b-4c≤2b时，0.5

(4)4b-4c0.75，合作者的数量将在下期扩张为21个，并持续扩张。

我的画：有位画家说过，“好的绘画在你面前是往后退的。”多年的绘画实践更明白了其中的道理。优秀的绘画呈现的是一种整体的氛围，吸引你去感受画面背后的一种精神性的东西，而不是停留在表面的技法、色彩等物质性上。精神性的呈现，需要你对物的持续关注和体验，才能在最为熟悉的物上得到灵感。因此我画身边的人与物，通过和谐的色调，细腻的手法，书写的笔意，努力营造画面的氛围，给物以升华，如同打开一扇窗。

由此可见，背叛者入侵合作者，并最终在群体中占据主导地位的条件是c/b>0.5。

1.2.3 对基于Agent的演化博弈的仿真

以下考虑合作者和背叛者在二维网格中分布的一般情况，我们使用Netlogo软件进行计算机仿真。首先在100*100的网格中随机生成合作者与背叛者，网格的边缘被设为回环(Torus)以避免出现边界问题。博弈的收益矩阵和其他设定都与前文一致。仿真的结果印证了我们在此之前的分析：

(1)当c/b>0.5时，演化的均衡结果是群体完全由背叛者构成。

(2)当0.25≤c/b≤0.5，演化的均衡结果是群体中合作者与背叛者并存，且背叛者占大多数。

(3)当c/b<0.25时，演化的均衡结果是群体中合作者与背叛者并存，且合作者占大多数。

图1展现了c/b分别为0.2与0.4时的情况。

图1表明，网络中囚徒困境博弈的动态演化可以很快达到均衡，在适当的参数下，合作者与背叛者共同存在。图1的左半部分和右半部分分别表示在0.25≤c/b≤0.5(以c/b=0.4为例)和c/b<0.25(以c/b=0.2为例)的条件下，博弈达到均衡状态下合作者与背叛者的情况。在图1a和图1b中，黑色的点表示合作者，白色的点表示背叛者。当c/b=0.4时，合作的成本较高，此时合作者通过结成簇状以避免被淘汰。而当c/b=0.2时，合作者可以迅速扩张，并在总体中占据较大的比例。图1c与图1d显示了在两种情况下，博弈的均衡状态中合作者(虚线)和背叛者(实线)所占的比例。

图1 网格上囚徒困境博弈的仿真

2 结 论

合作是人类社会存在和发展的必要条件。在演化博弈的平均场假设下，每个参与人等概率与其他参与人进行博弈，此时合作行为无法抵御背叛者的剥削，只能在竞争中被淘汰。而在基于Agent的演化博弈中，我们限制了合作的范围(让每个参与人仅和其邻居进行博弈)，这样可以防止合作红利的外溢，从而使合作行为有机会得到发展。

通过理论推导和计算机仿真，我们证明了在二维规则网络中合作策略获得成功的条件：c/b<0.25。从表面上看，这个结果缺乏直观含义。但如果我们将博弈中邻居的数量从4改成8(Moore Neighborhood)，并对这种情况进行仿真，我们可以发现合作策略获得成功的条件变成了c/b<1/8。不仅如此，当我们改变邻居的数量m，让每个参与人与不同数量的邻居进行博弈，并分别进行仿真。我们可以证明二维规则网络中合作策略获得成功的条件是c/b<1/m，且这个结果对于任意数量的m都是适用的。这个式子的含义是：当合作者的合作成本c可以由足够多合作者的合作收益b来补偿的话，合作者在群体中的频率就将上升。在网络博弈中，这也就意味着合作者必须“扎堆”，保证自己的邻居中有足够多的合作者，才能保证合作策略的成功。在我们的仿真中，均衡状态下总可以看到合作者结成块状或是簇状区域，就是对此的最好证明。

以下我们用一个例子表明c/b<1/m这个公式的应用，假设二人囚徒困境博弈的收益矩阵如下：

CDCD16,160,1919,03,3

在这个博弈中，b与c的数值分别为16和3，此时1/8

值得指出的是，以上结论并不是孤立的。我们暂时借用生物学的思维：汉密尔顿(1964)在研究动物行为时发现，个体之间合作的原因之一在于双方存在亲缘关系，进而提出了汉密尔顿法则：即个体之间达成合作的条件是c/b

本研究在现实生活中也有广泛的应用。c/b<1/m这个式子清晰地表明了网络结构对于合作产生和维持的重要性。根据费孝通(2013)[16]，传统社会很大程度上依赖于血亲和熟人之间自发产生的合作，而在现代社会中人与人之间的关系却日益淡漠，邻里之间“老死不相往来”的情况并不少见。这种情况并不难通过本文得到的理论来进行解释，因为m可以表示人与社会互动的程度，在传统社会中较小的人口流动率导致人们的交际面较窄，此时人们更容易和有限的几个朋友达成合作。而现代社会发达的通讯技术降低了人们的通讯成本，随着人们社交网络的日益发达，单个的朋友对人们而言却变得越来越不重要，人们之间的关系就越疏远，从而要达成合作就更难④。

对基于Agent的演化博弈的研究在学术界方兴未艾，例如Chiong和Kirley(2011)对均匀小世界网络和随机均匀网络下N人重复博弈的研究[17]，Ichinose等人(2014)对无标度网络中合作涌现的分析[18]等。然而目前大部分工作都集中在囚徒困境博弈或雪堆博弈(Snow-drift Game)研究上，其它类型的博弈还缺乏系统地研究。对基于Agent的演化博弈在多人领域和其他类型博弈上的扩展的研究是很有前景的。

注释：

①本文所说的经典博弈论依赖于两个假设：(1)参与人具有“超级理性”(Hyper-rational)；(2)参与人的理性是共同知识。

②这事实上就是上世纪50年代冯诺依曼提出的元胞自动机(Cellular Automata)的概念。

③如果网络中两个节点之间的距离为1，则它们互为邻居。在二维规则网络中，常用的概念包括Moore Neighborhood和Von Neumann Neighborhood。节点x的Moore Neighborhood包括x周围的8个节点，而其Von Neumann Neighborhood只包括它周围的4个节点。

④现代社会是以大范围的合作为标志的，这似乎与本文的结论不符合。但事实上现代社会中的合作依赖于法律、道德的外在约束，以及由间接利他作为保障的声誉机制。而由于篇幅的原因，这并不在本文的研究范围内。但如果一旦剥离这些外在约束，我们会发现现代社会中人们之间的合作链条是很脆弱的。

[1]Trivers R L.The Evolution of Reciprocal Altruism[J].Quarterly Review of Biology,1971:35～57

[2]Boyd R,Richerson P J.Cultural Transmission and the Evolution of Cooperative Behavior[J].Human Ecology,1982,10(3):325～351

[3]Zahavi A.Mate Selection—a Selection for a Handicap[J].Journal of Theoretical Biology,1975,53(1):205～214

[4]Alexander R D.The Biology of Moral Systems[M].Transaction Publishers,1987

[5]Nowak M A,Sigmund K.Evolution of Indirect Reciprocity By Image Scoring[J].Nature,1998,393(6685):573～577

[6]Kreps D M,Milgrom P,Roberts J,et al.Rational Cooperation in the Finitely-Repeated Prisoners’ Dilemma[R].Stanford Univ Ca Inst For Mathematical Studies In The Social Sciences,1982

[7]Smith J M.Evolution and the Theory of Games[M].Cambridge University Press,1982

[8]Smith J M,Price G R.lhe Logic of Animal Conflict[J].Nature,1973,246:15

[9]Taylor P D,Jonker L B.Evolutionary Stable Strategies and Game Dynamics[J].Mathematical Biosciences,1978,40(1):145～156

[10]Foster D,Young P.Stochastic Evolutionary Game Dynamics?[J].Theoretical Population Biology,1990,38(2):219～232

[11]Cabrales A.Stochastic Replicator Dynamics[J].International Economic Review,2000,41(2):451～481

[12]Nowak M A,May R M.Evolutionary Games and Spatial Chaos[J].Nature,1992,359(6398):826～829

[13]Nowak M A,Bonhoeffer S,May R M.Spatial Games and the Maintenance of Cooperation[J].Proceedings of the National Academy of Sciences,1994,91(11):4877～4881

[14]Nowak M A.Evolutionary Dynamics[M].Harvard University Press,2006

[15]丁绒，孙延明．企业竞合行为的演化博弈试验与集群联盟群体行为研究[J]．工业技术经济，2013，(4)：68～77

[16]费孝通.乡土中国[M].北京：外语教学与研究出版社,2013

[17]Chiong R,Kirley M.Iterated N-player Games on Small-world Networks[C].Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation.ACM,2011:1123～1130

[18]Ichinose G,Sayama H.Invasion of Cooperation in Scale-free Networks:Accumulated vs.Average Payoffs[C].ALIFE 14:The Fourteenth Conference on the Synthesis and Simulation of Living Systems，14:398～399

(责任编辑：史 琳)

Cooperation under Agent-based Evolutionary Games

Wang Jian Zhao Kai

(Huaqiao University，Xiamen 361000，China)

This article used IPD to analyze the evolution of cooperative behavior in the field of evolutionary game theory.Under the mean-field assumption,cooperator cannot survive in competition with defectors.However,in agent-based evolutionary game theory,cooperators can thrive.The reason for that is by restricting the scope of cooperation,cooperators can survive by living in clusters,thereby preventing the benefit of cooperation from being exploited by defectors.This article not only compares the difference between spatial evolutionary theory and classical theory,but also analyzes the conditions needed for the emergence and maintenance of cooperation using PD game simulation on a regular network.

cooperation;evolutionary game;IPD;Agent;population game

2016—01—05

中央高校基本科研业务费资助项目·华侨大学哲学社会科学青年学者成长工程“‘承诺’的可信性和宏观经济政策的动态不一致——一个博弈论的视角”(项目编号：12SKGC-QG17)。

王健，华侨大学数量经济研究院助理研究员，经济学博士。研究方向：博弈论、计算经济学。赵凯，华侨大学数量经济研究院讲师，经济学博士。研究方向：博弈论、计量经济学。

10．3969/j．issn．1004-910X．2016．05．002

F224.32；F270

A