复杂网络上的演化博弈动力学
——一个计算视角的综述

谭少林，吕金虎

(1.湖南大学电气与信息工程学院，长沙 410082；2.中国科学院数学与系统科学研究院系统科学研究所，北京 100190)

0 引言

博弈论是研究多个自主性个体在利益相关情形下的决策行为的理论。现实中下面这种情形常常会碰到：若干个称为决策者或者玩家的个体，他们具备独立决策的自主性，然而他们彼此之间的利益却相互关联或冲突。博弈论即是通过建立适当的数学模型和工具，来分析、预测和干预自主个体在利益相关情形下决策行为的一门学科[1]。通常，在经典博弈论中，玩家个体被假设具有完全理性和完全信息，即能够依据对邻居策略以及博弈的分析或预判，选择最大化自身收益的策略[2]。

演化动力学则是用于刻画群体演化过程的一个理论工具，它基于群体演化过程中的复制、选择和变异等3个基本原则，来建立描述群体组成在给定适应度景观下的演化数学模型[3]。最初，演化动力学用于描述不同适应度的表现型或行为在生物群体中的扩散过程。后来，鉴于演化动力学中隐含的自然选择和随机漂移机制的普适性，演化动力学也常常用于探索经济、社会和工业系统中的各种不同的演化行为。

传统博弈论与演化动力学理论的结合形成了演化博弈理论[4]。演化博弈以参与博弈的群体作为研究对象，通过分析群体中不同策略的个体组成在复制、选择和突变的演化机制作用下的动态行为过程，来分析、解释和预测个体在交互决策情境下的博弈行为。与经典博弈论不同，演化博弈论摈弃了关于个体的完全理性和完全信息假设，从动态的系统的视角探讨个体决策到群体决策的形成机制，为研究群体决策的形成和演化提供了新的理论工具和方法论支持[5]。

长期以来，在演化博弈理论中，个体之间的交互通常被假定以均匀混合的方式进行的，即任意两个个体之间都存在交互或者以同样的概率发生交互。这种假设能够极大地简化描述群体演化过程的动力学方程，有助于后续的分析处理，但与实际中的个体间的交互模式不相符。事实上，在实际生物、社会、经济和工业复杂系统中，个体之间的交互往往比均匀混合的形式更复杂，呈现出若干特定的拓扑特征，例如小世界特性、无标度特征、社团结构、层级特征等等[6-9]。为了刻画生物、社会和工业系统中的错综复杂的连接结构，复杂网络这一概念被抽象出来，它由节点和节点之间的连边构成，节点代表系统的基础组成单元，而连边代表系统中各单元之间的交互关系。

复杂网络上的演化博弈即是由复杂网络和演化博弈的两者结合而形成的新型交叉研究领域[10]。它以复杂网络和演化博弈动力学分别刻画个体间的交互关联结构以及决策范式，通过网络群体上策略的形成和演化来探讨生物、社会等群体中的策略演化行为。复杂网络上的演化博弈与传统演化博弈的区别在于：前者采用了自下而上的科学范式，它通过对个体之间的交互方式和结构、以及个体的行为规则等进行建模，来探讨由此衍生的群体行为的形成和演化机制[11]。复杂网络上的演化博弈为理解和分析复杂交互环境下群体的决策行为提供了一个新的研究模式，对其展开深入的研究可以为理解集群行为的形成和演化模式，洞察文化变迁、社会规范、以及公共意见的形式和发展过程，提供新的帮助。同时其演化动力学中相关的原理对于分布式协同控制的设计也能提供有益参考。这些因素推动了国内外对于复杂网络上演化博弈研究的热潮[12-14]。

目前，从研究内容上看，复杂网络上的演化博弈研究可以从两方面出发：一方面以个体层面的视角，探讨群体层面的策略演化机制，即通过对个体间的交互关系和策略更新规则进行分析和建模，来分析集群决策的动力学机制与演化行为[15]。另一方面以群体层面的需求的视角，来探讨关于个体层面的策略更新方式的设计和干预。具体地说，依据对群体整体策略所需要达成的目标，来设计个体间的交互结构或者个体的决策方式以及调整干预方法，使得最终由个体组成的群体行为能够达成预先设定的目标[16]。

而从研究形式上看，目前对于复杂网络上演化博弈的研究可以分为模拟仿真研究、理论分析研究和实证研究3类。模拟仿真研究通过利用计算机程序，对复杂网络上的演化博弈动力学进行仿真，来获取对于网络上演化博弈的理解。这种研究方式能够适用于大规模结构复杂的网络，同时对各种复杂的博弈或者更新规则都能适用，是研究复杂网络上演化博弈的最常用的方式。国内外学者利用这种方式对复杂网络上的演化博弈行为展开了大量的研究。各种不同类型的因素，如个体异质性、决策多样性；个体的学习行为以及迁徙行为、收益的遗传以及分配的不均匀性；策略信息的局限性以及网络交互结构的动态特征等，对群体在演化博弈中决策行为的影响都得到了广泛的探讨。目前，已有多篇文章对这一研究方式及其取得的结果进行了综述，感兴趣的读者可以参考文献[17-20]。

对复杂网络上演化博弈的实证研究，通常通过召集一些志愿参与实验的个体，来参与所设计的博弈实验，并根据参与博弈的个体在不同情境下的策略选择，来获取关于网络演化博弈的理解。由于参与博弈的个体决策方式是不可控的，这种实证研究通常仅能获取若干可观可控因素对于网络演化博弈的影响。例如，通过博弈实验，Rand等[21]发现个体切断和重建交互关系的能力有助于提高社交网络中合作水平。在另一个博弈实验中，他们发现，相比于惩罚背叛行为，奖励合作行为更加有益于促进合作行为的涌现和保持[22]。

而对复杂网络上演化博弈的理论分析研究则是利用数学工具，对网络演化博弈的动力学展开分析，来得到关于复杂网络上演化博弈动力学的一些基本性质。由于在复杂网络上的演化博弈动力学中，每个个体的状态通过网络博弈以及网络演化动力学耦合起来，这使得整个动力学所诱导的状态空间的维度十分庞大且状态之间的转移十分复杂。因此，虽然对复杂网络上的演化博弈动力学展开理论分析是深刻理解网络演化博弈中交互、演化与决策之间关联关系的必要，但却由于其复杂性常常十分困难。不管怎样，目前对于复杂网络上演化博弈的理论研究虽然相对来说较为稀少，但一直在不断推进。

本文主要是对目前复杂网络上演化博弈动力学的理论分析方面获得的主要结果进行一个综述。主要内容包括：给出复杂网络上演化博弈动力学基本模型的数学描述；分析网络上演化博弈动力学的计算复杂性；概述复杂网络上演化博弈动力学的若干主要解析结果等。鉴于目前对复杂网络上演化博弈方面已有大量的仿真模拟研究，国内已有一些学者对这些研究进行了综述，本文从计算的角度对复杂网络上演化博弈动力学的综述将是对目前仿真研究的一个有效补充。

1 复杂网络上演化博弈动力学的数学描述

尽管复杂网络上的演化博弈模型可以多种多样，但其基本模型都由3个基本要素组成：1)一个给定的网络；2)节点的状态集合及其适应度；3)节点状态的更新规则。接下来，我们分别介绍这些基本元素及其工作机理。

1.1 群体结构

具有复杂交互结构的群体常常可以通过一个网络来表示。其中网络中的节点和连边分别代表玩家个体和个体之间的邻居关系。此外，每条连边可以赋予一个权重来描述个体之间的相互作用强度。一般地，一个网络G=(V,E,W)被用来表示博弈群体，其中V=(v1,v2,…,vn)表示节点集、E⊂V×V为边集，W=(wij)n×n表示个体间交互的权重矩阵。

一些常用于刻画演化博弈中个体交互结构的网络包括完全图、环状、星状图、二分图等对称性较高的规则图，也有Erdos-Renyi随机图[23]、Watt-Strogatz小世界网络[24]、Barabasi-Albert无标度网络[25]、随机几何图[26]等局部交互比较复杂，具有一定典型拓扑特征的随机图。图1展示这些图的拓扑结构示意图，其具体定义和生成算法可参考对应的文献。

图1 常见网络的典型拓扑结构示意图[1]

1.2 节点状态集合及其适应度

网络博弈是一类特殊的博弈形式。在网络博弈中，玩家个体的博弈关系构成了一个网络拓扑结构，而每个个体的收益与不相邻的个体行动无关。而且在网络上的演化博弈中，一般采用两类基本的网络博弈：对交互博弈和群组交互博弈。

群组交互网络博弈是另一类常见的网络博弈模型。相比于对交互网络博弈，群组交互博弈中的每个个体与它所有相邻个体形成一个局部多人博弈。也就是说，个体不再与每个邻居进行单独的两人博弈，而是与它邻居集合构成一个整体进行多人博弈[27]。图2分别给出了网络中的对交互和群组交互两种博弈模型的示意图。

图2 博弈交互示意图[28]Fig.2 Illustration of game

在网络上的演化博弈动力学中，常常通过适当的映射方式，将个体的行动集合表示为一个合适的状态集合，而个体通过博弈所获取的收益则被转化为个体的适应度[28]。一般地，个体适应度与收益之间的关系由式(1)转化

fitness=exp(w×payoff)

(1)

这里，fitness和payoff分别指代个体的适应度和收益，参数0w称为选择强度，用于调节个体博弈收益对其适应度的影响。当w=0时，个体的适应度与其收益无关，在这种情形下，所有个体的适应度相等，其状态演化过程与博弈无关，完全由更新规则中的随机性决定，因此，称这种情形下的演化动力学为随机漂移。当w→0时，个体通过网络博弈获取的收益仅占其适应度的极小部分，此时，所有个体具有几乎相同的适应度。这种情形称为弱选择。此时，其适应度与收益之间的关系也可简化为：

fitness=1+w×payoff

(2)

在上述收益与适应度之间的关系中，隐含假设了每个状态(策略)给予个体的基准适应度是相同的。即当w=0时，不管个体采取何种状态，其适应度都相同。一种更一般的假定是不同状态给予个体的基准适应度不相同，即当w=0时，个体采取不同的状态，其适应度各不相同。此时，个体的适应度仅取决于自身的状态，与其他个体的状态无关，这种情形被称为常数选择。

1.3 状态更新规则

状态更新规则描述了每个个体根据其周围邻居的状态和适应度来更新自己的状态的过程，是刻画复杂网络上演化博弈动力学的关键要素。仿照自然或社会个体实际决策过程，各种不同类型的更新规则被提出来，如生灭过程、死生过程、模仿过程及其不同情形下的变化形式等。生灭过程和死生过程是生物数学中描述种群演化的两类最基本的动力学模型，大量新的状态更新规则也是在这两类更新规则的基础上进行调整变化的，因此，本文主要考察这两类更新规则下的演化博弈过程，其相关分析方法和结果也可以推广到其他类似演化过程中。

在经典生灭过程中，每一步，以正比于个体适应度的概率，一个个体从群体中被选择出来；随后，这个个体产生一个复制体，并随机替代群体中剩余个体中的某一个，从而导致群体组成的变化。当考虑具有交互结构的群体时，这一经典生灭过程被推广到网络群体中[29]。此时同样以正比于个体适应度的概率，个体从网络群体中被选择出来产生复制体，但此时复制体随机替代其某一个邻居，如图3a所示。显然，在网络上的死生过程中，状态的传播扩散是通过个体间的交互进行的。特别地，对于加权网络，选择被替代邻居节点的概率将与其连边的权重成正比。例如，如果节点vi∈V被选择出来产生复制，那么选择邻居节点vj∈Ni进行替代的概率正比两点连边的权重wij。

同样地，在经典死生过程中，每一步，一个个体被随机地从群体中淘汰，然后以正比于个体适应度的概率，从群体中剩余的个体中选择出一个个体，这个个体产生一个复制体并替代被淘汰个体的位置。而在网络上的死生过程中[30]，每一步，一个个体被随机地从群体中淘汰，然后以正比于个体适应度的概率，从这个淘汰个体的邻居中选择出一个个体，这个个体产生一个复制体并替代被淘汰个体的位置，如图3b所示。而当网络是加权网络时，如果节点vi∈V为淘汰节点，那么选择其邻居节点vj∈Ni产生复制的概率大小正比于fjwji，这里，fj指节点vj的适应度，而wji是连边(vj,vi)∈E的权重值。

图3 复杂网络上的生灭过程以及死生过程示意图Fig.3 Illustration of birth-death process and death-birth process on complex networks

1.4 演化过程的数学描述

一个网络上的演化动力学过程完全可以由个体间的交互关系网络、个体的状态集及其适应度景观、以及个体状态的更新规则等3个元素确定。如图4所示，给定上述3个要素确定了一个典型的网络的演化博弈过程。在这个演化博弈过程中，初始时刻，所有节点都为B策略个体。某一时刻，由于个体的自由探索或者新策略的入侵，一个A策略个体占据了网络中的某个节点，从而导致两种策略的交互与竞争过程。在状态更新规则的不断作用下，网络上的策略分布从一个状态转移到另一状态，形成群体博弈策略的演化过程。

令M0={vi∈V|si(0)=1}为初始时刻网络中的A策略节点集合，令ρM0=P(limt→Mt=V)为网络中所有节点的策略在演化动力学的作用下最终收敛于A策略的概率。这一被称为固定概率的变量，是反映演化博弈动力学行为的关键值。简便起见，通常令ρi=ρ{vi}，表示单个A策略个体在入侵节点vi∈V后，最终占据了网络中全部节点的概率。

图4 网络上两策略博弈的演化过程[1]

求解网络上演化博弈动力学中的固定概率是一个非常困难的问题。一般地，在具有n个节点的网络上两策略演化博弈过程中，由于每个节点具有两个状态可以选择，那么整个网络可能的状态数目为2n。因此利用对应马尔科夫链的吸收概率的计算方法，需要求解一个2n阶次的方程组，其一般形式如下

ρX=∑Y∈2nP(Y|X)ρY

(3)

这里，X∈2n为网络状态，P(Y|X)指网络状态X到状态Y的转移概率。

值得注意的是，在生灭过程和死生过程中，每一步最多只有一个节点的状态可能发生改变。因此，对应马尔科夫链的转移概率P(Y|X)不等于0，当且仅当1)Y=X，即网络群体的状态未发生改变；2)存在某一vi∈V且vi∉X，使得Y=X∪{vi}，即网络中节点vi从B策略变为A策略；以及3)存在某一vi∈V且vi∈X，使得Y=X-{vi}，即网络中节点vi从A策略变为B策略。在这种情形下，上述方程组可以简化为

(4)

其边界条件为：ρØ=0以及ρV=1。

2 复杂网络上的随机漂移过程

复杂网络上的随机漂移过程是群体演化中一类特殊而基本的演化过程。在随机漂移过程中，所有个体的适应度完全相等，此时策略在网络上的竞争扩散过程完全与策略之间的博弈无关，而是由状态更新过程本身的随机性决定。随机漂移是促使群体行为演化的一种基本作用力，也为一般的演化博弈动力学过程提供了一个对比参照标准[31]。特别地，虽然对于一般演化博弈动力学过程，求解其固定概率是一件计算复杂度非常高的难题，然而对于网络上的随机漂移过程，其固定概率可以通过解析的方式得到，下面简述关于复杂网络上随机漂移过程的主要结果，其详细讨论详见文献[32-34]。

2.1 无向无权图

在无向无权图上的随机漂移过程中，一个策略的固定概率完全有这个策略所在节点的度以及整个网络的度分布决定。具体地，对于网络上的生灭过程，一个策略入侵节点vi∈V后的固定概率为

(5)

而对于网络上的死生过程，对应的固定概率为

(6)

这里，di是指节点vi∈V的度。由式(5)和(6)可知，在生灭过程中，邻居数目较少的节点，其策略扩散至整个网络的概率更大；相反地，在死生过程中，邻居数目较多的节点，其策略扩散至整个网络的概率更大。

2.2 一类特殊的加权图

上述解析结果可以推广到一类特殊的加权图中。令c=(c1,c2,…cn)和z=(z1,z2,…zn)为两列正向量。考虑一类加权网络，对所有vi,vj∈V，其权重为wij=ciaijzj，这里假设aij=aij。显然，如果c和z是单位向量，那么由上述方法生成的加权网络即为无向无权图。

对于这一类加权图，在生灭过程作用下，一个策略入侵节点vi∈V后的固定概率为

(7)

而在死生过程作用下，对应概率为

(8)

2.3 一般加权图

对于一般加权图上的演化过程，求解其固定概率的方法稍微复杂一些。谭少林等[33]提出来一个一般性的计算方法来求解不同更新动力学作用下的固定概率。具体地，考虑一个强连通的图G=(V,E,W)，其中W=(wij)n×n为权重矩阵。他们证明了，在网络上的随机漂移过程作用下，一个策略入侵节点vi∈V后的固定概率对应于某一随机矩阵平稳分布的第i个元素，即ρi=π(i)，这里π为某一随机矩阵的平稳分布。

对于生灭过程，这个随机矩阵为MBD=(mij)n×n，其中

(9)

而对于死生过程，这个随机矩阵为MDB=(mij)n×n，其中

(10)

因此，对于一般加权网络上的随机漂移过程，虽然无法直接给出其固定概率的表达式，但是可以通过求解对应随机矩阵的平稳分布来求得其固定概率。注意到，求解随机矩阵的平稳分布的计算复杂度是线性时间的，因此与直接求解2n阶的方程组相比，上述方法极大地简化了求解固定概率的复杂度。

2.4 时序图

具体地，令Mt=(mij(t))n×n为一个动态的随机矩阵。对于时序图上的生灭过程，这个矩阵中元素为

(11)

而对于死生过程，矩阵元素为

(12)

其中，aij(t)以及di(t)是t时刻个体交互网络Git中节点vi与vj的邻接关系以及节点vi的节点度。那么在网络上的随机漂移过程作用下，一个策略入侵节点vi∈V后的固定概率对应于某一平稳分布的第i个元素，即ρi=π(i)，这里平稳分布π由式(13)可得。

(13)

由上述计算方法可知，对于动态时序网络上的随机漂移过程，在计算固定概率的过程中，虽然增加了矩阵连乘的部分，但当动态时序网络存在一定的周期性时，其固定概率仍然能够在线性时间内由上述计算方法得到。

上面给出了不同类型网络上随机漂移作用下单个策略入侵某一节点后，最后占据整个网络的概率的计算方法。值得注意的是，在随机漂移这一特殊情形下，某个策略同时入侵多个节点后，其最后占据整个网络的固定概率等于这一策略入侵各单个节点的固定概率之和。因此，通过上述方法，可以计算各种情形下两策略随机漂移过程中的固定概率。

3 复杂网络上的常数选择过程

常数选择过程是一类比随机漂移过程更加一般化的演化过程。在随机漂移过程中，初始策略B与入侵策略A的适应度相同，没有选择性差异，演化过程决定于随机性因素。而在常数选择过程中，初始策略与入侵策略的适应度都是固定不变的常数，但不一定相同。常数选择过程一般用于刻画效用值不同的策略在网络群体中竞争和扩散过程[35]。这类过程也可以视为一类特殊的网络博弈：在这类博弈中，个体的收益是仅依赖自身策略的常数，与其他邻居个体的策略无关。

不失一般性，在常数选择过程中，一般令初始策略B的适应度为单位1，而令入侵策略A的适应度为r。这里，r为一个大于0的常数，用于刻画策略A相对于策略B的选择性差异。当r=1时，这一常数选择过程即为随机漂移过程；当01时，称A策略为优势策略。

(14)

(15)

而对于死生过程，上述转移概率为

(16)

对于复杂网络上的常数选择过程，目前尚没有简单可行的方法来求解其固定概率。实际上，Broom等[36]证明，除了一些高度对称性的网络外，对于一般的网络，n阶的网络上的两策略演化过程可能形成2n阶的策略构型，因此，通过马尔科夫链的方法来求解固定概率，需要求解2n阶的方程组，其计算复杂度是指数时间的。

图5 个体层面的策略更新与群体层面的策略选择关系示意图[1]

虽然无法获得复杂网络上常数选择过程中固定概率的解析形式，但是目前仍然有一些文献得到了其固定概率的一些基本性质，用以阐明网络上常数选择过程的一些基本特性。令ρ(M0,r)表示A策略的固定概率，其中M0是初始时刻网络中A策略节点集合。如图5所示，每个个体vi∈V对于策略的选择由转移概率p(Mt,r,vi)和q(Mt,r,vi)来刻画，而整个网络群体对于策略的选择则由固定概率ρ(M0,r)刻画。谭少林等人在文献[37]中给出了个体层面的策略更新与群体层面的策略选择之间的关联关系。下面综述其主要结果，详细证明与讨论可参考文献[37]。

其次，如果对所有节点vi∈V和r>0，转移概率p(C,r,vi)是关于集合C的单调递增函数；并且对所有Ø⊆C⊆V和vi∈V，转移概率p(C,r,vi)是关于A策略个体适应度r的单调递增函数，那么A策略的固定概率ρ(M0,r)也是关于适应度r的单调递增函数。这一性质说明：在复杂网络上的常数选择过程中，如果每个个体在进行策略选择时倾向于选择适应度更高的策略，那么整个网络最终倾向于选择适应度更高的策略。简言之，如果个体具有择优行为，那么由个体组成的群体也具有择优行为。

最后，如果对所有节点vi∈V，转移概率p(C,r,vi)是关于集合C的单调递增函数，并且对所有节点vi∈V，转移概率p(C,r,vi)是关于集合C的次模或超模函数，那么A策略的固定概率ρ(M0,r)也是关于集合C的次模或超模函数。这一性质刻画了常数选择过程中，初始时刻A策略节点集合中新增一个节点对于其固定概率的边际效应。当A策略的固定概率是关于其初始A策略集合的次模(超模)函数时，那么在初始时刻给A策略集合新增一个A策略节点，对其固定概率的边际效应会随着其初始A策略集合的增大而减小(增大)。

上述结果的好处在于，在无法得到复杂网络上常数选择过程中固定概率的解析解时，可以由常数选择过程中的个体层面的相关性质，推断出其群体层面的性质。例如，对于在复杂网络上的死生过程中，容易证明其个体层面策略更新的转移概率满足1)-3)三个基本条件，而且是关于A策略个体适应度r的单调递增函数，以及关于集合C的单调递增函数，并且集合C的次模(若r≥1)或超模函数(若0

4 复杂网络上的演化博弈

复杂网络上的演化博弈由复杂网络、博弈以及更新动力学三者组成。与常数选择过程不同，在演化博弈过程中，个体之间会进行博弈并产生收益，这一收益影响了该个体的适应度，进而影响其策略更新过程。因此，在演化博弈过程中，个体间的博弈与个体策略的演化紧密联系在一起，并基于演化过程来研究分析相互连接的个体对于博弈策略的选择。

策略选择是复杂网络上演化博弈中的核心问题。当不考虑个体策略复制过程中的突变概率时，网络上的演化博弈过程对应于吸收型马尔科夫链。此时，为了比较网络群体对于某两个策略的偏好，一般考虑令一种策略随机地入侵另一种策略后的演化情形。具体地，令A、B分别表示两种策略。令ρA表示单个A策略从某个随机的节点入侵到全为B策略节点的网络中，最终占据整个网络的固定概率。同样，令ρB表示单个B策略从某个随机的节点入侵到一个全为A策略节点的网络中，最终占据整个网络的固定概率。假定网络中的节点数目为n。那么当ρA>1/n时，则称选择偏好策略A。这里，1/n是随机漂移过程中一个随机入侵的A策略的固定概率。而如果ρA>ρB，则称与策略B相比，选择更偏好策略A。

值得注意的是，与博弈学习动力学不同，通过上述演化动力学获得的偏好策略不一定是网络博弈的纳什均衡策略。演化博弈动力学的核心魅力在于它基于自然演化的原理来分析群体的博弈行为。特别地，经典博弈理论无法解释生物群体和社会群体中的合作行为，形成著名的合作困境问题。而演化博弈动力学提供了一种新的方式来阐释合作行为的涌现。这也是合作行为的涌现研究成为复杂网络上演化博弈研究的主要内容的原因。

显然，在复杂网络上的演化博弈过程中，个体间的交互结构、博弈以及个体策略的更新动力学都会新规则时，两种典型网络博弈模型下策略选择的主要结果，相关详细讨论可参考对应的文献[38],[39]。

4.1 对交互网络博弈

考虑下面的两人两策略对称博弈

ABAabBcd

其中a,b,c,d分别为策略对(A,A),(A,B),(B,A),(B,B)中第一个个体所能获得的收益。在对交互网络博弈中，每个个体分别与它每个邻居分别进行上述两两博弈，所获得的收益和称为这个个体的总收益。在更新动力学中，每个个体的收益通过式(1)转化为其适应度。如前文所述，w→0的情形称为弱选择。

与复杂网络上的常数选择过程一样，对于一般网络上的演化博弈，很难解得其固定概率，从而无法直接比较固定概率ρA与ρB的大小。但在文献[38]中，Tarnita等人发现，在弱选择的情况下，存在一个非常简单的准则来判定群体对于策略的偏好。具体地，在上述网络演化博弈过程中，选择更偏好策略A而不是B，当且仅当

σa+b>c+σd

(17)

其中，参数σ称为结构常数，仅取决于个体的状态更新规则以及个体间的交互结构，与博弈参数a,b,c,d无关。

根据上述判定准则，现在只需计算一个网络在给定更新规则下的结构常数σ，就能判定这一网络上演化过程对于策略的偏好。例如，对于用来说明合作困境的囚徒博弈，其收益矩阵为

CDCb-c-cDb0

这里，C和D分别代表合作与背叛策略。在这个博弈中，个体采取合作策略需要付出c的代价，但能为对方产生b的收益；而如果个体采取背叛策略，它既不用付出代价也不会带来收益。显然，在上述博弈中，个体的最优选择是背叛策略；而对于整体来说，合作才是最佳策略，这形成了著名的囚徒博弈。在复杂网络上的演化博弈中，在弱选择的情况下，根据上述判定准则，合作策略优于背叛策略的充要条件为

或等价地

将这一系数应用于囚徒博弈中，可得合作策略优于背叛策略的条件为b/c>k，即囚徒博弈中的收益付出比大于网络的平均度。在文献[40]中，konno发现

是死生过程中网络结构系数的一个更好的近似，因此，比较囚徒博弈中的收益付出比与网络平均邻接度的大小关系，是判定合作策略是否被选择所偏好的更好准则。

表1 对交互博弈中一些简单图的结构系数[1]Tab.1 Structural Coefficients of some simple graphs with pairwise interactions

4.2 群组交互网络博弈

群组交互网络博弈中，以每个节点为中心，个体及其所有的邻居组成一个群组进行多人博弈。考虑下面策略为A和B的两策略群体博弈。假设一个群组中有i个A策略个体和j个B策略个体，那么A策略个体和B策略个体获得的收益分别为(ia+jb)/(i+j)和(ic+jd)/(i+j)。对于这种群组交互网络博弈，在弱选择的情况下，式(17)的策略选择条件同样适用，只不过其中的结构系数σ与对交互网络中的结构系数不同。

显然，当a=r-1,b=-1,c=r,d=0，上述群体博弈即为著名的公共物品博弈。这个博弈可以理解如下：每个个体可以选择是否往公共资金中投入单位资金(合作策略)或者不如此(背叛策略)。这笔公共资金乘以系数r>1后，平均分给所有个体。公共物品博弈也是研究群体中合作行为涌现的一类重要博弈。显然，在公共物品博弈中，理性个体的最优选择是背叛策略。而在复杂网络上的演化博弈中，在弱选择的情况下，根据上述判定准则，合作策略优于背叛策略的充要条件为

或等价地

表2给出了生灭过程和死生过程作用下，完全图、环状图、以及星状图的结构系数[41]。显然，当个体间的交互网络为完全图时，在生灭过程和死生过程下，完全图的结构系数都是σ=1，此时合作行为不被偏好。而对于环状图和星状图，只要当公共物品的收益系数r大于一定的值时，合作行为能被演化过程所偏好。

表2 群组交互博弈中一些简单图的结构系数[1]Tab.2 Structural coefficients of some simple graphs with group interactions

5 总结与展望

复杂网络上的演化博弈是研究具有复杂交互结构的群体决策行为，特别是合作行为涌现和演化的重要工具。其研究内容可以从多个方面展开，包括个体间交互结构对于群体决策行为的影响；个体策略的更新规则与群体整体策略演化之间的关系；以及个体间的博弈模型与群体最终策略的偏好之间的关系等。对复杂网络上的演化博弈展开深入的研究对于理解生物和社会群体中集群行为的涌现过程，如公共观点的形成、社会创新的传播等具有重要的意义[42]。

本文对迄今为止复杂网络上演化博弈动力学理论分析方面获得的主要结果进行一个系统的综述。给出了复杂网络上演化博弈动力学基本模型的数学描述；分析了网络上演化博弈动力学的计算复杂性；概述复杂网络上演化博弈动力学的若干主要解析结果，包括复杂网络上随机漂移过程中固定概率的计算、复杂网络上常数选择中局部状态更新与全局状态选择之间的关联性质、以及复杂网络上演化博弈过程中的策略选择等。鉴于目前对复杂网络上演化博弈方面已有大量的仿真模拟研究，这些理论分析方面的结果对于深入理解复杂网络上演化博弈的动力学机制与原理将有所助益。

值得注意的是，为了达到主线简明清晰的目的，本文综述的结果仅针对两种典型的更新过程：生灭过程和死生过程、以及两策略博弈和不具有突变率的演化过程。从这些结果发散开去的更多分析内容可参考相关文献。此外，上文已经提到，对于复杂网络上演化博弈动力学展开理论分析十分困难，很多问题甚至不可能求解。特别是随着复杂网络上的演化博弈研究的深入开展，越来越多更加复杂的网络演化博弈模型被提出来，如共演化博弈，其动力学行为更加复杂。如不进行系统的实验设计，利用仿真模拟的方法对复杂网络上的演化博弈模型展开研究多数仅能获得某一角度甚至片面的结果。理论分析则是获得对网络博弈演化过程深入理解的必要工具。因此，利用新的数学工具，对复杂网络上的演化动力学展开深入的分析讨论，将是研究复杂网络上演化博弈过程的一个重要课题。

[1]吕金虎，谭少林. 复杂网络上的博弈及其演化动力学[M]. 北京: 高等教育出版社, 2018.

[2]Szabo G, Fath G. Evolutionary games on graphs [J]. Phys Rep, 2007, 446: 97-216.

[3]Nowak M. A. Evolutionary Dynamics: Exploring the Equation of Life [M]. Cambridge: Harvard University Press, 2006.

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

[5]Hofbauer J, Sigmund K. Evolutionary Games and Population Dynamics [M]. Cambridge: Cambridge University Press, 1998.

[6]Newman M E J, Barabási A L, Watts D J. The Structure and Dynamics of Networks [M]. Princeton: Princeton University Press, 2006.

[7]汪小帆，李翔，陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006.

[8]何大韧，刘宗华，汪秉宏. 复杂系统与复杂网络[M]. 北京: 高等教育出版社, 2009.

[9]Newman M E J. Networks: An Introduction [M]. New York: Oxford University Press, 2010.

[10] Nowak M A, May R M. Evolutionary games and spatial chaos [J]. Nature, 1992, 359(6398): 826-829.

[11] Tan S, Lü J, Chen G, et al. When structure meets function in evolutionary dynamics on complex networks [J]. IEEE Circ Syst Mag, 2014, 14(4): 36-50.

[12] 王龙，伏峰，王靖，等. 复杂网络上的演化博弈[J]. 智能系统学报, 2007, 2(2): 1-10.

Wang Long, Fu Feng, Wang Jing, et al. Evolutionary games on complex networks [J]. CAAI Transactions on Intelligent Systems, 2007, 2(2): 1-10.

[13] 吴枝喜，荣智海，王文旭. 复杂网络上的博弈[J]. 力学进展，2008, 389(6): 794-804.

Wu Zhixi, RongZhihai, Wang Wenxu. Games on complex networks [J]. Advances In Mechanics, 2008, 389(6): 794-804.

[14] 杨阳，荣志海，李翔. 复杂网络演化博弈理论研究综述[J]. 复杂系统与复杂性科学，2008, 5(4)：47-55.

Yang Yang, RongZhihai, Li Xiang. A research survey of evolutionary game theory on complex networks[J]. Complex Systems and Complex Sciences, 2008, 5(4): 47-55.

[15] Antal T, Traulsen A, Ohtsuki H, et al. Mutation-selection equilibrium in games with multiple strategies [J]. J Theor Biol, 2009, 258(4): 614-622.

[16] Traulsen A, Nowak M A. Evolution of cooperation by multilevel selection [J]. Proc Natl Acad Sci USA, 2006, 103(29): 10952-10955.

[17] Du J, Wu B, Altrock P M, et al. Aspiration dynamics of multi-player games in finite populations [J]. J R Soc Interface, 2014, 11: 20140077.

[18] Pacheco J, Traulsen A, Nowak M A. Coevolution of strategy and structure in complex networks with dynamical linking [J]. Phys Rev Lett, 2006, 97: 258103.

[19] Perc M, Szolnoki A. Coevolutionary games-a mini review [J]. Biosystems, 2010, 99(2):109-125.

[20] Perc M, Gomez-Gardenes J, Szolnoki A, et al. Evolutionary dynamics of group interactions on structured populations: a review [J]. J Royal Soc Interface, 2013, 10(80): 20120997.

[21] Rand D G, Arbesman S, Christakis N A. Dynamic social networks promote cooperation in experiments with humans [J]. Proc Nat Acad Sci, 2011, 108: 19193-19198.

[22] Rand D G, Dreber A, Ellingsen T, et al. Positive interactions promote public cooperation [J]. Science, 2009, 325: 1272-1275.

[23] Erdos P, Renyi A. On random graphs I [J]. Publ Math Debrecen, 1959, 6:290-297.

[24] Watts D J, Strogatz S H. Collective dynamics of small-world networks [J]. Nature, 1998, 393: 440-442.

[25] Barabasi A L, Albert R. Emergence of scaling in random networks [J]. Science, 1999, 286: 509-512.

[26] Penrose M. Random Geometric Graphs [M]. New York: Oxford University Press, 2003

[27] Tan S, Lü J. Analysis and control of networked game dynamics via a microscopic deterministic approach [J]. IEEE Trans Autom Contr, 2016, 61(12): 4118-4124.

[28] Tan S, Lü J, Yu X, et al. Evolution and maintenance of cooperation via inheritance of neighborhood relationship [J]. Chin Sci Bull, 2013, 58(28-29): 3491-3498.

[29] Lieberman E, Hauert C, Nowak M A. Evolutionary dynamics on graphs [J]. Nature, 2005, 433(7023): 312-316.

[30] Ohtsuki H, Nowak M A. Evolutionary games on cycles [J]. Proc R Soc B, 2006, 273(1598): 2249-2256.

[31] Mesoudi A, Lycett S J. Random copying, frequecy-dependent copying and culture change [J]. Evol Hum Behav, 2009, 30(1): 41-48.

[32] Broom M, Hadjichrysanthou C, Rychtár J, et al. Addendum: two results on evolutionary processes on general non-directed graphs [J]. Proc R Soc A, 2010, 466(2121): 2795-2798.

[33] Tan S, Lü J, Hill D. Towards a theoretical framework for analysis and intervention of random drift on general networks [J]. IEEE Trans Automat Contr, 2015, 60(2): 576-582.

[34] Tan S, Wang Y, Chen Y. A unified tractable approach for random drifts on dynamical networks [J]. IEEE Trans Circ Syst II, 2016, 63(3): 299-303.

[35] Tan S, Lü J. Characterizing the effect of population heterogeneity on evolutionary dynamics on complex networks [J]. Sci Rep, 2014, 4: 05034.

[36] Broom M, Rychtár J. An analysis of the fixation probability of a mutant on special classes of non-directed graphs [J]. Proc R Soc A, 2008, 464(2098): 2609-2627.

[37] Tan S, Lü J, Lin Z. Emerging behavioral consensus of evolutionary dynamics on complex networks [J]. SIAM Journal Contr Optim, 2016, 54(6): 3258-3272.

[38] Tarnita C E, Ohtsuki H, Antal T, et al. Strategy selection in structured populations [J]. J Theor Biol, 2009, 259(3): 570-581.

[39] Ohtsuki H, Hauert C, Lieberman E, et al. A simple rule for the evolution of cooperation on graphs and social networks [J]. Nature, 2006, 441(7092): 502-505.

[40] Konno T. A condition for cooperation in a game on complex networks [J]. J Theor Biol, 2011, 269(1): 224-233.

[41] Tan S, Feng S, Wang P, et al. Strategy selection in evolutionary game dynamics on group interaction networks [J]. Bulletin of Mathematical Biology, 2014, 76(11): 2785-2805.

[42] Tan S, Wang Y, Chen Y, et al. Evolutionary dynamics of collective behavior selection and drift: flocking, collapse, and oscillation [J]. IEEE Trans Cy, 2017, 47(7): 1694-1705.