工程科学学报 Chinese Journal of Engineering 演化博奔与资源配置综述 张艳玲莫廷钰李松涛张妍李擎 A survey of evolutionary game and resource allocation ZHANG Yan-ling.MO Ting-yu,LI Song-tao,ZHANG Yan,LI Qing 引用本文： 张艳玲，莫廷钰，李松涛，张妍，李擎.演化博弈与资源配置综述[J.工程科学学报，2022,44(3)：402-410.doi: 10.13374j.issn2095-9389.2020.10.26.002 ZHANG Yan-ling.MO Ting-yu,LI Song-tao,ZHANG Yan,LI Qing.A survey of evolutionary game and resource allocation[J]. Chinese Journal of Engineering,.2022,443:402-410.doi:10.13374j.issn2095-9389.2020.10.26.002 在线阅读View online::https://doi..org/10.13374.issn2095-9389.2020.10.26.002 您可能感兴趣的其他文章 Articles you may be interested in 5G超密集网络的能量效率研究综述 Survey of energy efficiency for 5G ultra-dense networks 工程科学学报.2019,41(8：968 https:doi.org10.13374.issn2095-9389.2019.08.002 C-RAN回传网络中下行资源调度策略 A downlink resource scheduling strategy for C-RAN backhaul network 工程科学学报.2018.40(5：629htps:/doi.org10.13374.issn2095-9389.2018.05.014 领域Q$与资源感知的物流服务动态优化组合方法 Domain QoS and resource-aware logistics web service dynamic optimal composition 工程科学学报.2018,40(7)：882 https::/1doi.org/10.13374.issn2095-9389.2018.07.015 复杂应力路径下裂隙泥岩渗透演化规律试验研究 Experimental study of the permeability evolution of fractured mudstone under complex stress paths 工程科学学报.2021,43(7)：903 https:ldoi.org10.13374j.issn2095-9389.2020.05.27.005 深度神经网络模型压缩综述 A survey of model compression for deep neural networks 工程科学学报.2019.41(10：1229 https:oi.org10.13374j.issn2095-9389.2019.03.27.002 微生物技术在稀土资源利用中的研究进展 Overview of microbial technology in the utilization of rare earth resources 工程科学学报.2020,42(1：60 https:/1doi.org10.13374j.issn2095-9389.2019.09.12.003
演化博弈与资源配置综述 张艳玲 莫廷钰 李松涛 张妍 李擎 A survey of evolutionary game and resource allocation ZHANG Yan-ling, MO Ting-yu, LI Song-tao, ZHANG Yan, LI Qing 引用本文: 张艳玲, 莫廷钰, 李松涛, 张妍, 李擎. 演化博弈与资源配置综述[J]. 工程科学学报, 2022, 44(3): 402-410. doi: 10.13374/j.issn2095-9389.2020.10.26.002 ZHANG Yan-ling, MO Ting-yu, LI Song-tao, ZHANG Yan, LI Qing. A survey of evolutionary game and resource allocation[J]. Chinese Journal of Engineering, 2022, 44(3): 402-410. doi: 10.13374/j.issn2095-9389.2020.10.26.002 在线阅读 View online: https://doi.org/10.13374/j.issn2095-9389.2020.10.26.002 您可能感兴趣的其他文章 Articles you may be interested in 5G超密集网络的能量效率研究综述 Survey of energy efficiency for 5G ultra-dense networks 工程科学学报. 2019, 41(8): 968 https://doi.org/10.13374/j.issn2095-9389.2019.08.002 C-RAN回传网络中下行资源调度策略 A downlink resource scheduling strategy for C-RAN backhaul network 工程科学学报. 2018, 40(5): 629 https://doi.org/10.13374/j.issn2095-9389.2018.05.014 领域QoS与资源感知的物流服务动态优化组合方法 Domain QoS and resource-aware logistics web service dynamic optimal composition 工程科学学报. 2018, 40(7): 882 https://doi.org/10.13374/j.issn2095-9389.2018.07.015 复杂应力路径下裂隙泥岩渗透演化规律试验研究 Experimental study of the permeability evolution of fractured mudstone under complex stress paths 工程科学学报. 2021, 43(7): 903 https://doi.org/10.13374/j.issn2095-9389.2020.05.27.005 深度神经网络模型压缩综述 A survey of model compression for deep neural networks 工程科学学报. 2019, 41(10): 1229 https://doi.org/10.13374/j.issn2095-9389.2019.03.27.002 微生物技术在稀土资源利用中的研究进展 Overview of microbial technology in the utilization of rare earth resources 工程科学学报. 2020, 42(1): 60 https://doi.org/10.13374/j.issn2095-9389.2019.09.12.003
工程科学学报.第44卷.第3期：402-410.2022年3月 Chinese Journal of Engineering,Vol.44,No.3:402-410,March 2022 https://doi.org/10.13374/j.issn2095-9389.2020.10.26.002;http://cje.ustb.edu.cn 演化博弈与资源配置综述 张艳玲2)，莫廷钰，李松涛)，张妍，李擎，2四 1)北京科技大学自动化学院.北京1000832)工业过程知识自动化教育部重点实验室，北京100083 ☒通信作者，E-mail:liqing@ies.ustb.edu.cn 摘要复杂网络上集群行为的研究是多学科交叉的热点，行为学实验不仅证实了集群行为的普遍存在性，而且证实了利用 演化论解释集群行为涌现的合理性.复杂网络上演化博弈理论已取得长足发展，特别是在两策略竞争理论分析方法上取得 突破性进展.首先介绍了演化博弈框架下合作演化机制的相关研究，详细总结了近年来被广泛关注的个体异质性和环境反 馈对于合作演化的影响研究：其次阐述了五种复杂网络上演化博弈的理论分析方法，包括最近提出的适用于任意网络结构和 更新规则的溯祖随机游走理论：再次给出了基于最后通牒博弈模型的资源配置问题研究：最后总结了复杂网络最后通牒博弈 所面临的挑战及未来发展趋势 关键词复杂网络；演化；合作；最后通牒博弈；资源配置 分类号TG142.71 A survey of evolutionary game and resource allocation ZHANG Yan-ling2,MO Ting-yu,LI Song-tao,ZHANG Yan,LI Qing 1)School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Key Laboratory of Knowledge Automation for Industrial Processes,Ministry of Education,Beijing 100083,China Corresponding author,E-mail:liging@ies.ustb.edu.cn ABSTRACT Evolutionary game theory involves multiple disciplinary sciences and has enormous scientific value and promising applicability.Collective behavior is an important topic of interdisciplinary study.Ethology has shown the ubiquity of collective behavior and has proven the rationality of evolutionary theory in explaining the emergence of collective behavior.The recent development of complex network theory offers a convenient framework for describing game interactions and competition relationships among individuals.The combination of evolutionary games and complex networks,particularly,evolutionary game theory in a complex network,has been attracting growing interest from different fields.It has undergone substantial development,especially in quantitative analysis of two-strategy competition.Under this framework,the complex network represents the population structure,and the game describes interactions between individuals.On the basis of the methodology from network science,stochastic process,and statistical physics,the framework mainly focuses on how population structures,individual behavior patterns,and interacting environments influence the emergence of collective behavior.In this paper,the mechanisms for the evolution of cooperation were given under the framework of evolutionary game,including kin selection,direct reciprocity,indirect reciprocity,network reciprocity,and group selection.Recently,the effects of individual heterogeneity and environmental feedback on cooperation had attracted growing interest. Next,five main theoretical methods were addressed for analyzing the evolutionary game in complex networks,including the- dominance rule,the coalescing theory,the pairwise approximation,the coalescing random walk theory,and the adaptive dynamics. Particularly,the recently proposed coalescing random walk theory is suitable for analyzing the dynamics of any network structure and any update rule.Then,the studies on the evolution of fairness in ultimatum games were presented,and reasonable resource allocation is 收稿日期：2020-10-26 基金项目：国家自然科学基金青年基金资助项目(61603036)
演化博弈与资源配置综述 张艳玲1,2)，莫廷钰1)，李松涛1)，张 妍1)，李 擎1,2) 苣 1) 北京科技大学自动化学院，北京 100083 2) 工业过程知识自动化教育部重点实验室，北京 100083 苣通信作者， E-mail: liqing@ies.ustb.edu.cn 摘 要 复杂网络上集群行为的研究是多学科交叉的热点，行为学实验不仅证实了集群行为的普遍存在性，而且证实了利用 演化论解释集群行为涌现的合理性. 复杂网络上演化博弈理论已取得长足发展，特别是在两策略竞争理论分析方法上取得 突破性进展. 首先介绍了演化博弈框架下合作演化机制的相关研究，详细总结了近年来被广泛关注的个体异质性和环境反 馈对于合作演化的影响研究；其次阐述了五种复杂网络上演化博弈的理论分析方法，包括最近提出的适用于任意网络结构和 更新规则的溯祖随机游走理论；再次给出了基于最后通牒博弈模型的资源配置问题研究；最后总结了复杂网络最后通牒博弈 所面临的挑战及未来发展趋势. 关键词 复杂网络；演化；合作；最后通牒博弈；资源配置 分类号 TG142.71 A survey of evolutionary game and resource allocation ZHANG Yan-ling1,2) ，MO Ting-yu1) ，LI Song-tao1) ，ZHANG Yan1) ，LI Qing1,2) 苣 1) School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China 2) Key Laboratory of Knowledge Automation for Industrial Processes, Ministry of Education, Beijing 100083, China 苣 Corresponding author, E-mail: liqing@ies.ustb.edu.cn σ ABSTRACT Evolutionary game theory involves multiple disciplinary sciences and has enormous scientific value and promising applicability. Collective behavior is an important topic of interdisciplinary study. Ethology has shown the ubiquity of collective behavior and has proven the rationality of evolutionary theory in explaining the emergence of collective behavior. The recent development of complex network theory offers a convenient framework for describing game interactions and competition relationships among individuals. The combination of evolutionary games and complex networks, particularly, evolutionary game theory in a complex network, has been attracting growing interest from different fields. It has undergone substantial development, especially in quantitative analysis of two-strategy competition. Under this framework, the complex network represents the population structure, and the game describes interactions between individuals. On the basis of the methodology from network science, stochastic process, and statistical physics, the framework mainly focuses on how population structures, individual behavior patterns, and interacting environments influence the emergence of collective behavior. In this paper, the mechanisms for the evolution of cooperation were given under the framework of evolutionary game, including kin selection, direct reciprocity, indirect reciprocity, network reciprocity, and group selection. Recently, the effects of individual heterogeneity and environmental feedback on cooperation had attracted growing interest. Next, five main theoretical methods were addressed for analyzing the evolutionary game in complex networks, including the - dominance rule, the coalescing theory, the pairwise approximation, the coalescing random walk theory, and the adaptive dynamics. Particularly, the recently proposed coalescing random walk theory is suitable for analyzing the dynamics of any network structure and any update rule. Then, the studies on the evolution of fairness in ultimatum games were presented, and reasonable resource allocation is 收稿日期: 2020−10−26 基金项目: 国家自然科学基金青年基金资助项目（61603036） 工程科学学报，第 44 卷，第 3 期：402−410，2022 年 3 月 Chinese Journal of Engineering, Vol. 44, No. 3: 402−410, March 2022 https://doi.org/10.13374/j.issn2095-9389.2020.10.26.002; http://cje.ustb.edu.cn
张艳玲等：演化博弈与资源配置综述 403· the key factor for social stability,economic development,and individual health.Finally,the challenges and further directions of studying ultimatum games in a complex network were summarized. KEY WORDS complex networks;evolution;cooperation;ultimatum game;resources allocation 20世纪末，复杂网络研究的兴起在国内外掀 群体行为的统计学规律.最常采用的研究方式是 起一股新的研究复杂性科学的热潮凹，而复杂网络 计算机仿真，即利于计算机程序对动力学进行模 本身也形成了一门新学科一一网络科学.复杂网 拟.另一种重要但十分具有挑战性的研究方式 络能够很好地刻画实际生物、社会和工业系统中 是理论分析，即利用数学工具量化动力学6 所表现的社团结构、小世界特性、无标度特性等 本文组织结构如下：第1部分简要介绍基于演 网络拓扑.集群行为普遍存在于各类真实系统中， 化博弈的合作演化机制研究现状：第2部分阐述 如蚁群互助觅食、蜂群协同建巢、鸽群编队飞行、 复杂网络上演化博弈的理论分析方法；第3部分 鱼群涡旋游动和人类选举投票等.相应地，复杂网 给出基于最后通牒博弈的公平偏好涌现机制的相 络上集群行为的相关研究成为多学科交叉的热点 关研究：第4部分总结本文的主要内容，并归纳了 问题-列，主要聚焦以下三方面：(1)通过对动物和 复杂网络上最后通牒博弈研究现阶段的不足和未 人类进行大量行为学实验，证实集群行为的存在 来的发展方问 性；(2)以集群行为的存在作为前提假设，研究据 1 基于演化博弈的合作演化机制 此所诱导的社会、经济和工程影响，或仿照集群行 为设计控制律和智能算法；(3)将集群行为的存在 演化博弈理论曾相当成功地解释了生物进化 看作是需要证明的结论，即对集群行为如何从个 过程中的某些现象，最为经典的早期工作是 体的简单交互中涌现提供完整解释 1973年Smith和Price将其用来解释物的斗争行 行为学证实了集群行为的普遍存在性，而经 为，同时提出了演化稳定策略20之后，经济学、 济学、社会学和统计物理学发现了集群行为存在 社会学和统计物理学运用演化博弈论分析影响集 的重要性.不仅要“知其然”，也要“知其所以然” 群行为形成的各类因素，获取了丰富且具有启发 一个自然的问题是，集群行为从何而来，为什么能 意义的研究成果1-2.近期，众多学者试图将控制 够长期稳定存在？行为学实验有效支持了利用演 论和演化博弈理论结合，希望借助一定的控制手 化论解释集群行为涌现的合理性.以公平行为为 段令群体行为演化到期望状态，从而实现更加有 例加以阐述四：聚焦公平偏好神经学解释的实 效的工程应用2s-0 验证明，人类的公平偏好具有生理基础：针对儿童 被演化博弈论最为频繁研究的集群行为是合 进行公平行为测试的研究表明，未成年儿童的公 作行为IB1-)2006年，Nowak总结性地提出了五种 平偏好会随着年龄的增长而上升，暗示人类的公 有利于合作演化的机制B(图1)：(1)亲缘选择B5-询， 平偏好在社会学习中不断演化进步：随着社会的 通过具有亲缘和遗传关系的个体之间的关系来促 不断进化，人类不断提升自身的公平偏好 进合作，即个体更愿意与亲缘关系较近的对手合 由行为学可见，复杂网络上演化博弈可被用 作.(2)直接互惠7-3，在重复博弈中，个体当前阶 来研究集群行为的涌现.此类研究往往利用复杂 段的合作诱发对手在后续阶段的合作行为.(3)间 网络对个体间交互方式进行数学建模3：边连 接互惠B90,此时声望起关键作用，合作的个体具 接博弈对象和模仿对象：而边的权重描述个体间 备较高的声望，从而在接下来的博弈阶段更容易 交互强度，量化个体被选为博弈对象或模仿对象 获得他人的帮助.(4)网络互惠1-，复杂网络的 的概率.同时利用经典博弈（例如最后通牒博 连接关系令合作者“抱团取暖”而存活，背叛者无 弈)的演化动力学对个体间决策范式进行数学建 法再利用合作者而消亡.（⑤）群组选择)，自然选 模：策略更新过程刻画自然选择，即个体在与博弈 择作用于群组而非个体，通过群组选择来决定个 对象进行交互后获取收益，收益越高的个体，它的 体策略演化 策略越容易被模仿对象所采用；而在突变的作用 除了上面介绍的演化合作机制外，还有一些 下，个体探索地采取全新策略.最后以整个系统为 机制也能够促进合作，例如个体异质性和环境反 研究对象，分析群体策略的动态演化过程，并获取 馈.个体异质性本质上描述了不同主体间相互比
the key factor for social stability, economic development, and individual health. Finally, the challenges and further directions of studying ultimatum games in a complex network were summarized. KEY WORDS complex networks；evolution；cooperation；ultimatum game；resources allocation 20 世纪末，复杂网络研究的兴起在国内外掀 起一股新的研究复杂性科学的热潮[1] ，而复杂网络 本身也形成了一门新学科——网络科学. 复杂网 络能够很好地刻画实际生物、社会和工业系统中 所表现的社团结构、小世界特性、无标度特性等 网络拓扑. 集群行为普遍存在于各类真实系统中， 如蚁群互助觅食、蜂群协同建巢、鸽群编队飞行、 鱼群涡旋游动和人类选举投票等. 相应地，复杂网 络上集群行为的相关研究成为多学科交叉的热点 问题[2−9] ，主要聚焦以下三方面：(1) 通过对动物和 人类进行大量行为学实验，证实集群行为的存在 性；(2) 以集群行为的存在作为前提假设，研究据 此所诱导的社会、经济和工程影响，或仿照集群行 为设计控制律和智能算法；(3) 将集群行为的存在 看作是需要证明的结论，即对集群行为如何从个 体的简单交互中涌现提供完整解释. 行为学证实了集群行为的普遍存在性，而经 济学、社会学和统计物理学发现了集群行为存在 的重要性. 不仅要“知其然”，也要“知其所以然”. 一个自然的问题是，集群行为从何而来，为什么能 够长期稳定存在？行为学实验有效支持了利用演 化论解释集群行为涌现的合理性. 以公平行为为 例加以阐述[10−12] ：聚焦公平偏好神经学解释的实 验证明，人类的公平偏好具有生理基础；针对儿童 进行公平行为测试的研究表明，未成年儿童的公 平偏好会随着年龄的增长而上升，暗示人类的公 平偏好在社会学习中不断演化进步；随着社会的 不断进化，人类不断提升自身的公平偏好. 由行为学可见，复杂网络上演化博弈可被用 来研究集群行为的涌现. 此类研究往往利用复杂 网络对个体间交互方式进行数学建模[13−14] ：边连 接博弈对象和模仿对象；而边的权重描述个体间 交互强度，量化个体被选为博弈对象或模仿对象 的概率. 同时利用经典博弈 (例如最后通牒博 弈) 的演化动力学对个体间决策范式进行数学建 模：策略更新过程刻画自然选择，即个体在与博弈 对象进行交互后获取收益，收益越高的个体，它的 策略越容易被模仿对象所采用；而在突变的作用 下，个体探索地采取全新策略. 最后以整个系统为 研究对象，分析群体策略的动态演化过程，并获取 群体行为的统计学规律. 最常采用的研究方式是 计算机仿真，即利于计算机程序对动力学进行模 拟[15] . 另一种重要但十分具有挑战性的研究方式 是理论分析，即利用数学工具量化动力学[16−19] . 本文组织结构如下：第 1 部分简要介绍基于演 化博弈的合作演化机制研究现状；第 2 部分阐述 复杂网络上演化博弈的理论分析方法；第 3 部分 给出基于最后通牒博弈的公平偏好涌现机制的相 关研究；第 4 部分总结本文的主要内容，并归纳了 复杂网络上最后通牒博弈研究现阶段的不足和未 来的发展方向. 1 基于演化博弈的合作演化机制 1973 演化博弈理论曾相当成功地解释了生物进化 过程中的某些现象 ，最为经典的早期工作是 年 Smith 和 Price 将其用来解释动物的斗争行 为，同时提出了演化稳定策略[20] . 之后，经济学、 社会学和统计物理学运用演化博弈论分析影响集 群行为形成的各类因素，获取了丰富且具有启发 意义的研究成果[21−24] . 近期，众多学者试图将控制 论和演化博弈理论结合，希望借助一定的控制手 段令群体行为演化到期望状态，从而实现更加有 效的工程应用[25−30] . 被演化博弈论最为频繁研究的集群行为是合 作行为[31−33] . 2006 年，Nowak 总结性地提出了五种 有利于合作演化的机制[34] （图 1）：(1) 亲缘选择[35−36] ， 通过具有亲缘和遗传关系的个体之间的关系来促 进合作，即个体更愿意与亲缘关系较近的对手合 作. (2) 直接互惠[37−38] ，在重复博弈中，个体当前阶 段的合作诱发对手在后续阶段的合作行为. (3) 间 接互惠[39−40] ，此时声望起关键作用，合作的个体具 备较高的声望，从而在接下来的博弈阶段更容易 获得他人的帮助. (4) 网络互惠[41−42] ，复杂网络的 连接关系令合作者“抱团取暖”而存活，背叛者无 法再利用合作者而消亡. (5) 群组选择[43] ，自然选 择作用于群组而非个体，通过群组选择来决定个 体策略演化. 除了上面介绍的演化合作机制外，还有一些 机制也能够促进合作，例如个体异质性和环境反 馈. 个体异质性本质上描述了不同主体间相互比 张艳玲等： 演化博弈与资源配置综述 · 403 ·
404 工程科学学报，第44卷.第3期 (a 致不同的收益矩阵，环境通过收益矩阵的变化直 接反过来影响策略演化动力学.Hilbe等将随机博 弈思想融入重复博弈，具体而言，每一轮的个体行 为及博弈共同决定下一轮的博弈5]此时，环境反 馈和直接互惠可以极大促进合作的演化，远高于 只有环境反馈或直接互惠所诱导的合作水平.类 似地，Su等将随机博弈思想融入规则网络群体54， d 其中博弈转移大大放松合作演化的条件，特别地， 即使在每个备选博弈中合作无法演化，而在备选 博弈间转移却能够促进合作的演化.Weitz等将群 体中博弈的变化由一个类似的复制动力学刻画， 图1五大促进合作涌现的机制(a)亲缘选择：(b)直接互惠：(c)间 发现群体在好环境、坏环境、合作、背叛间不断往 接互惠；(d)群组选择：(e)网络互惠 复震荡啊稍后的研究表明类似的震荡环也出现 Fig.I Five mechanisms for the emergence of cooperation(a)kin 在环境反馈下的非对称两人博弈和网络群体65刃 selection;(b)direct reciprocity;(c)indirect reciprocity;(d)group 同时研究框架被推广到公共品博弈58]，发现资源反 selection;(e)network reciprocity 馈可以有效促进合作的演化 较过程中，展现出来的身心特征上的彼此各不相 2复杂网络上演化博弈的理论分析方法 同的现象，这主要是由于个体的成长过程受遗传 和环境的交互影响.例如，主体间的能力有高低之 自从Nowak和May开创性地研究了方格网络 分，不同主体才能的形成有早有晚，且各有所长 群体中的囚徒困境5网，复杂网络上的演化博弈成 个体异质性在群体竞争中普遍存在，演化博弈研 为研究网络群体中策略竞争的有效工具.常见的网 究的异质个体可归为三类：其一是异质网络中，每 络包括规则网络、小世界网络、无标度网络和社 个主体参与博弈总次数呈现天然异质性，而这种 团结构网络，如图2所示5960.目前，国内外学者 异质性从整体上利于合作的演化.其二是个体 对复杂网络上的两策略竞争进行了系统的研究61-6烈， 间行为模式存在异质性，即个体与不同对手采取 相关研究大多利用计算机仿真进行63-8】而理论 不同策略、不同交互概率和模仿概率，这种差异性 分析是深刻理解网络群体中策略竞争的必要条 可以在一定条件下促进两人博弈啊或多人博弈中 件.在中性选择这种适应度与收益无关的特殊情 合作的演化6其三是公共品博弈的投资、产出和 形下，策略在网络的扩散过程仅仅依赖随机漂移 分配额因人而异.当产出的协同效应和折扣效应 (由状态更新过程本身的随机性所决定).相应固 以概率共存时，高概率的协同效应能够促进合作叨： 定概率具有封闭形式计算公式，这里的固定概率 在分配额越大的博弈中投资越多，越有利于合作 指的是单个变异体传播到整个群体的概率，具体 的演化，在重复博弈中，投资的极端异质性抑制 数值往往与变异体出现的位置相关.然而，复杂网 合作，而当个体间分配额存在差异时，适当的投资 络上一般演化博弈的理论研究较为稀少，且在弱 异质性反而是促进合作的必要条件例 选择情形下进行.弱选择意味适应度对收益依赖 策略演化动力学与环境相互影响而形成的反 程度较小，允许扰动理论的使用，从而获得解析成 馈在生物和社会系统中普遍存在.例如，接种疫苗 果.同时探索弱选择情形的演化博弈具有现实意 的不充分往往导致本可以预防的传染病大规模爆 义，因为每个主体在生活中参与大量博弈，而单一 发；之后，政府通过宣传疫苗接种必要性等反馈措 博弈对适应度的影响往往很小.况且在强选择情 施改善疫苗的接种环境和群体的决策行为.最近， 形下，即适应度依赖收益的程度较大，相应固定概 环境反馈对于合作演化的影响激发了研究人员的 率已被证明没有封闭形式计算公式，也不能被一 浓厚兴趣0-，这里探讨的环境反馈是在随机博 个多项式时间算法所求解69下面，将分别阐述两 弈的研究框架下的定义的，随机博弈通常包括若 类主流的复杂网络上演化博弈理论分析方法：针 干个博弈主体、各主体的策略集合、收益矩阵及 对离散策略，计算σ-占优条件；针对连续策略，分 更新过程.收益矩阵和更新过程令部分主体改变 析适应动力学 自身策略，从而影响环境状态；环境状态的变化导 针对离散策略，弱选择情形下最一般理论结
较过程中，展现出来的身心特征上的彼此各不相 同的现象，这主要是由于个体的成长过程受遗传 和环境的交互影响. 例如，主体间的能力有高低之 分，不同主体才能的形成有早有晚，且各有所长. 个体异质性在群体竞争中普遍存在，演化博弈研 究的异质个体可归为三类：其一是异质网络中，每 个主体参与博弈总次数呈现天然异质性，而这种 异质性从整体上利于合作的演化[44] . 其二是个体 间行为模式存在异质性，即个体与不同对手采取 不同策略、不同交互概率和模仿概率，这种差异性 可以在一定条件下促进两人博弈[45] 或多人博弈中 合作的演化[46] . 其三是公共品博弈的投资、产出和 分配额因人而异. 当产出的协同效应和折扣效应 以概率共存时，高概率的协同效应能够促进合作[47] ； 在分配额越大的博弈中投资越多，越有利于合作 的演化[48] ；在重复博弈中，投资的极端异质性抑制 合作，而当个体间分配额存在差异时，适当的投资 异质性反而是促进合作的必要条件[49] . 策略演化动力学与环境相互影响而形成的反 馈在生物和社会系统中普遍存在. 例如，接种疫苗 的不充分往往导致本可以预防的传染病大规模爆 发；之后，政府通过宣传疫苗接种必要性等反馈措 施改善疫苗的接种环境和群体的决策行为. 最近， 环境反馈对于合作演化的影响激发了研究人员的 浓厚兴趣[50−52] ，这里探讨的环境反馈是在随机博 弈的研究框架下的定义的，随机博弈通常包括若 干个博弈主体、各主体的策略集合、收益矩阵及 更新过程. 收益矩阵和更新过程令部分主体改变 自身策略，从而影响环境状态；环境状态的变化导 致不同的收益矩阵，环境通过收益矩阵的变化直 接反过来影响策略演化动力学. Hilbe 等将随机博 弈思想融入重复博弈，具体而言，每一轮的个体行 为及博弈共同决定下一轮的博弈[53] . 此时，环境反 馈和直接互惠可以极大促进合作的演化，远高于 只有环境反馈或直接互惠所诱导的合作水平. 类 似地，Su 等将随机博弈思想融入规则网络群体[54] ， 其中博弈转移大大放松合作演化的条件，特别地， 即使在每个备选博弈中合作无法演化，而在备选 博弈间转移却能够促进合作的演化. Weitz 等将群 体中博弈的变化由一个类似的复制动力学刻画， 发现群体在好环境、坏环境、合作、背叛间不断往 复震荡[55] . 稍后的研究表明类似的震荡环也出现 在环境反馈下的非对称两人博弈和网络群体[56−57] . 同时研究框架被推广到公共品博弈[58] ,发现资源反 馈可以有效促进合作的演化. 2 复杂网络上演化博弈的理论分析方法 σ− 自从 Nowak 和 May 开创性地研究了方格网络 群体中的囚徒困境[59] ，复杂网络上的演化博弈成 为研究网络群体中策略竞争的有效工具. 常见的网 络包括规则网络、小世界网络、无标度网络和社 团结构网络，如图 2 所示[59−60] . 目前，国内外学者 对复杂网络上的两策略竞争进行了系统的研究[61−62] ， 相关研究大多利用计算机仿真进行[63−68] . 而理论 分析是深刻理解网络群体中策略竞争的必要条 件. 在中性选择这种适应度与收益无关的特殊情 形下，策略在网络的扩散过程仅仅依赖随机漂移 （由状态更新过程本身的随机性所决定）. 相应固 定概率具有封闭形式计算公式，这里的固定概率 指的是单个变异体传播到整个群体的概率，具体 数值往往与变异体出现的位置相关. 然而，复杂网 络上一般演化博弈的理论研究较为稀少，且在弱 选择情形下进行. 弱选择意味适应度对收益依赖 程度较小，允许扰动理论的使用，从而获得解析成 果. 同时探索弱选择情形的演化博弈具有现实意 义，因为每个主体在生活中参与大量博弈，而单一 博弈对适应度的影响往往很小. 况且在强选择情 形下，即适应度依赖收益的程度较大，相应固定概 率已被证明没有封闭形式计算公式，也不能被一 个多项式时间算法所求解[69] . 下面，将分别阐述两 类主流的复杂网络上演化博弈理论分析方法：针 对离散策略，计算 占优条件；针对连续策略，分 析适应动力学. 针对离散策略，弱选择情形下最一般理论结 (a) (b) (c) (e) (d) 图 1 五大促进合作涌现的机制[34] . （a）亲缘选择；（b）直接互惠；（c）间 接互惠；（d）群组选择；（e）网络互惠 Fig.1 Five mechanisms for the emergence of cooperation[34] : (a) kin selection; (b) direct reciprocity; (c) indirect reciprocity; (d) group selection; (e) network reciprocity · 404 · 工程科学学报，第 44 卷，第 3 期
张艳玲等：演化博弈与资源配置综述 405. b 而潮祖理论是适用中性选择的经典方法，核心思 想是，在回顾多主体祖先的过程中，只要回顾时间 足够长，总会找到他们最近的共同祖先.计算合作 占优条件的关键思路是，从当前的多主体回顾到 他们最近共同祖先的过程中，确定每个主体是否 发生变异或更改位置 Antal等推导了全局迁移下c的近似解析表达 式四，Zhang等将溯祖理论和随机游走结合起来计 算任意迁移模式下结构系数σ四此时，从当前的 多主体回潮到他们最近共同祖先的过程中，溯祖 理论不再只是确定其是否变异或迁移，而是更准 确地捕捉到每个主体发生变异或迁移的祖先数 图2常见的网络结构59(a)规则网络：(b)小世界网络：(c)无标度 网路：(d)社团结构网络 目.之后利用多个随机游走追踪从最近共同祖先 Fig.2 Common network structures (a)regular network;(b)small- 到当前期间每个主体祖先的策略变化轨迹和位置 world network;(c)scale-free network;(d)group-structed network 变化轨迹 果莫过于σ-占优条件的推导0具体而言，两策略 上述工作均是在假设1下进行的.为了放松假 设L,即演化过程服从局部更新，不再要求全局更 竞争中策略占优条件线性依赖收益矩阵和结构系 数(Structure coefficient,c),其中参数c与收益矩阵 新，Ohtsuki等针对随机规则网络，利用对估计方法 获得两人博弈中合作占优的条件)相应结果可 无关，它可以量化交互网络和更新过程对于策略 在大群体的前提下给出σ的近似解析表达式.对估 选择影响的大小，这里的策略占优指的是一种策 略的稳态频率高于另一种策略，在小变异情形下， 计方法是一种平均场估计方法，利用六个变量刻 等价于一种策略的固定概率高于另一种策略.相 画群体状态.假设两种策略A和B共存于群体，相 应地，网络群体中两策略竞争的理论研究转化为 应的六个变量为：随机选择的个体采取策略 A(B)的概率为xA(xB);在选中一个A个体后，任意选 结构系数σ的计算.群体的策略演化可由一个马尔 科夫决策过程刻画，然而在一般复杂网络群体中， 择他的一个邻居采取A(B)的条件概率为xAA(xAB片 在选中一个B个体后，任意选择他的一个邻居采取 群体状态应该包含所有主体的策略和位置，无法 A(B)的条件概率为xBA(BB).以上六个变量中的 一一列举出来，相应的状态转移矩阵无法刻画，群 xA和xAA是自由变量，对估计方法的核心是根据策 体的稳态频率无法由直接方法计算出来，因此计 略更新过程对这两个自由变量建立演化方程.该 算σ往往极具挑战性 方法和混合均匀群体的复制动力学相比，多了一 当群体演化过程满足假设1：全局更新（即所 个刻画自由变量xAA的动力学方程，此动力学方程 有主体共同竞争产生后代)，学者推导出σ的形式 可以理解为对个体局部交互信息的量化. 表达式m,即。=≤0，其中代表策略2主 <x2l12>0 同样为了放松假设L,Allen等针对特定规则网 体在群体中的比例，l代表策略主体和策略主体 络，利用血缘一致性方法推导合作占优条件相 交互数目，<>0代表中性选择（所有主体具有相同 应结果可在大群体的前提下给出σ近似解析表达 收益)下的期望.这个形式表达式给出了σ的简单 式.血缘一致性在生物学上描述两个主体继承共 算法：在所有主体具有相同适应度的结构群体演 同祖先的基因，如果两个主体自从共同祖先的那 化过程中，记录群体在每一时刻的x2山1和212，将 一代到当前，在整个演化过程中都没有发生变异，称 所有时刻的这两个值进行平均，再取比值即可获 这两个主体具有血缘一致性关系.而获得合作占 得σ，该算法可由大数定律保障收敛性 优条件的核心在于，推导中性选择时，位于n步溯 针对满足假设1的具体模型一基于表现型 祖随机游走两端的个体拥有血缘一致性的概率. 和基于集合的结构群体，Antal等在大群体的前提 最近，Allen等利用图上的溯祖随机游走理论， 下给出了σ近似解析表达式，其具体思路是， 将上述结果拓展到任意网络群体阿和任意更新过 <x211>o和<x212>转化为中性选择时，计算随机 程阿此时，获取合作占优条件的关键在于，推导 选择的多主体具有相同策略或相同位置的概率. 中性选择下从任意两个位置开始的溯祖随机游走
σ− σ σ σ σ 果莫过于 占优条件的推导[70] . 具体而言，两策略 竞争中策略占优条件线性依赖收益矩阵和结构系 数 (Structure coefficient， )，其中参数 与收益矩阵 无关，它可以量化交互网络和更新过程对于策略 选择影响的大小. 这里的策略占优指的是一种策 略的稳态频率高于另一种策略，在小变异情形下， 等价于一种策略的固定概率高于另一种策略. 相 应地，网络群体中两策略竞争的理论研究转化为 结构系数 的计算. 群体的策略演化可由一个马尔 科夫决策过程刻画，然而在一般复杂网络群体中， 群体状态应该包含所有主体的策略和位置，无法 一一列举出来，相应的状态转移矩阵无法刻画，群 体的稳态频率无法由直接方法计算出来，因此计 算 往往极具挑战性. σ σ = < x2I11 >0 < x2I12 >0 x2 Ii j i j <>0 σ x2I11 x2I12 σ 当群体演化过程满足假设 I：全局更新（即所 有主体共同竞争产生后代），学者推导出 的形式 表达式[70] ，即 ，其中 代表策略 2 主 体在群体中的比例， 代表策略 主体和策略 主体 交互数目， 代表中性选择（所有主体具有相同 收益）下的期望. 这个形式表达式给出了 的简单 算法：在所有主体具有相同适应度的结构群体演 化过程中，记录群体在每一时刻的 和 ，将 所有时刻的这两个值进行平均，再取比值即可获 得 ，该算法可由大数定律保障收敛性. σ < x2I11>0 < x2I12>0 针对满足假设 I 的具体模型——基于表现型 和基于集合的结构群体，Antal 等在大群体的前提 下给出了 近似解析表达式[71] ，其具体思路是 ， 和 转化为中性选择时，计算随机 选择的多主体具有相同策略或相同位置的概率. 而溯祖理论是适用中性选择的经典方法，核心思 想是，在回顾多主体祖先的过程中，只要回顾时间 足够长，总会找到他们最近的共同祖先. 计算合作 占优条件的关键思路是，从当前的多主体回顾到 他们最近共同祖先的过程中，确定每个主体是否 发生变异或更改位置. σ σ Antal 等推导了全局迁移下 的近似解析表达 式[71] ，Zhang 等将溯祖理论和随机游走结合起来计 算任意迁移模式下结构系数 [72] . 此时，从当前的 多主体回溯到他们最近共同祖先的过程中，溯祖 理论不再只是确定其是否变异或迁移，而是更准 确地捕捉到每个主体发生变异或迁移的祖先数 目. 之后利用多个随机游走追踪从最近共同祖先 到当前期间每个主体祖先的策略变化轨迹和位置 变化轨迹. σ A B A(B) xA (xB) A A(B) xAA (xAB) B A(B) xBA (xBB) xA xAA xAA 上述工作均是在假设 I 下进行的. 为了放松假 设 I，即演化过程服从局部更新，不再要求全局更 新，Ohtsuki 等针对随机规则网络，利用对估计方法 获得两人博弈中合作占优的条件[73] . 相应结果可 在大群体的前提下给出 的近似解析表达式. 对估 计方法是一种平均场估计方法，利用六个变量刻 画群体状态. 假设两种策略 和 共存于群体，相 应的六个变量为 ：随机选择的个体采取策略 的概率为 ；在选中一个 个体后，任意选 择他的一个邻居采取 的条件概率为 ； 在选中一个 个体后，任意选择他的一个邻居采取 的条件概率为 . 以上六个变量中的 和 是自由变量，对估计方法的核心是根据策 略更新过程对这两个自由变量建立演化方程. 该 方法和混合均匀群体的复制动力学相比，多了一 个刻画自由变量 的动力学方程，此动力学方程 可以理解为对个体局部交互信息的量化. σ 同样为了放松假设 I，Allen 等针对特定规则网 络，利用血缘一致性方法推导合作占优条件[74] . 相 应结果可在大群体的前提下给出 近似解析表达 式. 血缘一致性在生物学上描述两个主体继承共 同祖先的基因. 如果两个主体自从共同祖先的那 一代到当前，在整个演化过程中都没有发生变异，称 这两个主体具有血缘一致性关系. 而获得合作占 优条件的核心在于，推导中性选择时，位于 n 步溯 祖随机游走两端的个体拥有血缘一致性的概率. 最近，Allen 等利用图上的溯祖随机游走理论， 将上述结果拓展到任意网络群体[75] 和任意更新过 程[76] . 此时，获取合作占优条件的关键在于，推导 中性选择下从任意两个位置开始的溯祖随机游走 (a) (c) (b) (d) 1 m 图 2 常见的网络结构[59-60] . （a）规则网络；（b）小世界网络；（c）无标度 网络；（d）社团结构网络 Fig.2 Common network structures[59-60] : (a) regular network; (b) smallworld network; (c) scale-free network; (d) group-structed network 张艳玲等： 演化博弈与资源配置综述 · 405 ·