《工程科学学报》：演化博弈与资源配置综述

工程科学学报 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主 0 同样为了放松假设L,Allen等针对特定规则网 体在群体中的比例，l代表策略主体和策略主体 络，利用血缘一致性方法推导合作占优条件相 交互数目，<>0代表中性选择（所有主体具有相同 应结果可在大群体的前提下给出σ近似解析表达 收益)下的期望.这个形式表达式给出了σ的简单 式.血缘一致性在生物学上描述两个主体继承共 算法：在所有主体具有相同适应度的结构群体演 同祖先的基因，如果两个主体自从共同祖先的那 化过程中，记录群体在每一时刻的x2山1和212，将 一代到当前，在整个演化过程中都没有发生变异，称 所有时刻的这两个值进行平均，再取比值即可获 这两个主体具有血缘一致性关系.而获得合作占 得σ，该算法可由大数定律保障收敛性 优条件的核心在于，推导中性选择时，位于n步溯 针对满足假设1的具体模型一基于表现型 祖随机游走两端的个体拥有血缘一致性的概率. 和基于集合的结构群体，Antal等在大群体的前提 最近，Allen等利用图上的溯祖随机游走理论， 下给出了σ近似解析表达式，其具体思路是， 将上述结果拓展到任意网络群体阿和任意更新过 o和转化为中性选择时，计算随机 程阿此时，获取合作占优条件的关键在于，推导 选择的多主体具有相同策略或相同位置的概率. 中性选择下从任意两个位置开始的溯祖随机游走

σ− σ σ σ σ 果莫过于 占优条件的推导[70] . 具体而言，两策略 竞争中策略占优条件线性依赖收益矩阵和结构系 数 (Structure coefficient， )，其中参数 与收益矩阵 无关，它可以量化交互网络和更新过程对于策略 选择影响的大小. 这里的策略占优指的是一种策 略的稳态频率高于另一种策略，在小变异情形下， 等价于一种策略的固定概率高于另一种策略. 相 应地，网络群体中两策略竞争的理论研究转化为 结构系数 的计算. 群体的策略演化可由一个马尔 科夫决策过程刻画，然而在一般复杂网络群体中， 群体状态应该包含所有主体的策略和位置，无法 一一列举出来，相应的状态转移矩阵无法刻画，群 体的稳态频率无法由直接方法计算出来，因此计 算 往往极具挑战性. σ σ = 0 0 x2 Ii j i j <>0 σ x2I11 x2I12 σ 当群体演化过程满足假设 I：全局更新（即所 有主体共同竞争产生后代），学者推导出 的形式 表达式[70] ，即 ，其中 代表策略 2 主 体在群体中的比例， 代表策略 主体和策略 主体 交互数目， 代表中性选择（所有主体具有相同 收益）下的期望. 这个形式表达式给出了 的简单 算法：在所有主体具有相同适应度的结构群体演 化过程中，记录群体在每一时刻的 和 ，将 所有时刻的这两个值进行平均，再取比值即可获 得 ，该算法可由大数定律保障收敛性. σ 0 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) small￾world network; (c) scale-free network; (d) group-structed network 张艳玲等： 演化博弈与资源配置综述 · 405 ·

406 工程科学学报，第44卷.第3期 首次相遇的时间.同时由于σ不依赖收益矩阵，可 提议量；个体作为响应者可接受的最低提议量，即 将上述合作占优条件与σ-占优条件对比，从而获 响应量.同时，它也是最受欢迎的实验研究对象之 取任意网络群体中σ的计算方法.这是复杂网络上 一. 自从复杂网络上演化博弈受到广泛关注，网络 演化博弈理论分析方法的突破性进展，为网络群 结构就成为促进合作演化的最重要机制.一个自 体中两策略竞争提供一个完整的理论分析框架 然问题是，网络结构如何影响最后通牒博弈中公 上述理论方法适用研究离散策略的演化动力 平的演化？早在2000年，Page等就发现环和方格 学，同时Allen等的最新工作在弱选择下可获得一 网络本身并不能促进公平的演化：当模仿过程的 般复杂网络群体中σ的解析表达式-阿但在强选 噪声较高，即模仿的准确率较低时，群体的平均提 择条件下，至今仍然缺少分析一般复杂网络群体 议量和响应量最终稳定在相对公平的范围叫类 演化动力学的理论分析方法 似的结论也在小世界及随机网络中发现2-8到，且 适应动力学是研究连续策略的经典方法，从 对各种初始条件和更新过程鲁棒7事实上，噪 两个时间尺度，描述小变异情形下连续策略的演 声是促进公平涌现的机制之一.即使在混合均匀 化过程.从长期演化角度看，群体近似视为时时刻 群体中，一定程度的噪声也会促进公平的演化，所 刻采用一种策略，群体策略的演化转化为一系列 诱导的群体资源配置行为与实验所发现的分配行 策略迭代事件的发生.从短期时间尺度看，两种策 为相符合⑧这主要是由于噪声引入一些并不适 略共存于群体，且其中之一迅速占据群体或在群 应环境的策略，特别是当高需求的响应者进人群 体中消亡.Zhang等从微观更新过程出发，推导有 体后，提议者相应地提高自身的提议量.除了噪 限群体演化博弈的适应动力学m.具体思路是，利 声，众多学者还提出很多能够促进网络群体中公 用主方程描述群体采用某种策略的概率随时间变 平偏好涌现的机制. 化的动力学.据此发现，群体所采用策略的平均演 目前，最后通牒博弈的行为学实验关注了博 化方向可由变异策略的固定概率所预测.同时利 弈双方的关系因素、博弈决策的情境因素、分配 用固定概率关于变异策略的一阶泰勒展开近似群 物的数量因素等对于决策结果的影响.下面将要 体策略的平均演化路径.该方法的局限是一般网 介绍的五类因素不仅在行为学实验而且在演化博 络群体的固定概率难以获得具体表达式 弈框架下均被广泛关注 3基于演化博弈的资源配置 其一是角色分配.Killingback和Studer在方格 网络中研究角色分配由博弈双方固有等级的相对 公平偏好是在资源配置过程中自发涌现出来 高低来决定的模型.当适应度线性依赖收益时， 的集群行为.为了刻画资源配置行为，博弈论构建 群体平均提议量和响应量稳定在相对公平的范 了简单易行、操作性强的最后通牒博弈：两个参与 围；而在适应度与收益的依赖关系中融入递减回 者配置一笔资源，提议者向响应者提出分配方案， 报效应时，二者明显降低.Wu等的研究在无标度 如果响应者接受该方案，二者按照该方案获得相 网络中对比了基于度的角色分配方式和自适应角 应资源，否则，二者分文未得.在忽略个体为资源 色更替方式，其中自适应角色更替方式更能促 产生所付出的成本及个体间需求的差异性前提 进公平偏好的涌现，此时一旦提议者的分配方案 下，以均等原则度量公平偏好：绝对公平指的是提 被接受，博弈双方在下一轮博弈中以较大概率担 议者均等分配资源且响应者只接受均等分配方 当相同角色：否则二者以较大概率改变角色进行 案，与绝对公平较为接近的行为展现较高的公平 博弈 偏好.该博弈的行为学实验证实了公平偏好的存 其二是声望.Yang等在方格和随机网络中研 在性：提议者通常提供给对方30%~50%的份额， 究由声望确定博弈对象和角色分配的模型则.具 而响应者往往接受20%~35%的份额.公平是各 体而言，个体收益作为声望信息，邻居以此选择是 种系统稳定运行的关键.对财富不公平的分配往 否与其博弈，提议者成功分配资源的次数作为声 往住会造成社会不平等.而社会不平等在皮尤研究 望信息，博弈对象据此确定其再次成为提议者的 中心的报告中被认为是世界上最大的挑战，击败 概率.当个体更愿意与高收益个体进行博弈，且声 宗教仇恨、污染和核武器等 望较好的个体往往担当提议者时，公平偏好被显 最后通牒博弈允许关注资源配置的两个重要 著提高.此时，个体为了获取更多博弈机会和提议 方面-聊：个体作为提议者给予对方的资源量，即 者的角色分配，不得不提高自身提议量，与此同时

σ σ− σ 首次相遇的时间. 同时由于 不依赖收益矩阵，可 将上述合作占优条件与 占优条件对比，从而获 取任意网络群体中 的计算方法. 这是复杂网络上 演化博弈理论分析方法的突破性进展，为网络群 体中两策略竞争提供一个完整的理论分析框架. σ 上述理论方法适用研究离散策略的演化动力 学，同时 Allen 等的最新工作在弱选择下可获得一 般复杂网络群体中 的解析表达式[75−76] . 但在强选 择条件下，至今仍然缺少分析一般复杂网络群体 演化动力学的理论分析方法. 适应动力学是研究连续策略的经典方法，从 两个时间尺度，描述小变异情形下连续策略的演 化过程. 从长期演化角度看，群体近似视为时时刻 刻采用一种策略，群体策略的演化转化为一系列 策略迭代事件的发生. 从短期时间尺度看，两种策 略共存于群体，且其中之一迅速占据群体或在群 体中消亡. Zhang 等从微观更新过程出发，推导有 限群体演化博弈的适应动力学[77] . 具体思路是，利 用主方程描述群体采用某种策略的概率随时间变 化的动力学. 据此发现，群体所采用策略的平均演 化方向可由变异策略的固定概率所预测. 同时利 用固定概率关于变异策略的一阶泰勒展开近似群 体策略的平均演化路径. 该方法的局限是一般网 络群体的固定概率难以获得具体表达式. 3    基于演化博弈的资源配置 公平偏好是在资源配置过程中自发涌现出来 的集群行为. 为了刻画资源配置行为，博弈论构建 了简单易行、操作性强的最后通牒博弈：两个参与 者配置一笔资源，提议者向响应者提出分配方案， 如果响应者接受该方案，二者按照该方案获得相 应资源，否则，二者分文未得. 在忽略个体为资源 产生所付出的成本及个体间需求的差异性前提 下，以均等原则度量公平偏好：绝对公平指的是提 议者均等分配资源且响应者只接受均等分配方 案，与绝对公平较为接近的行为展现较高的公平 偏好. 该博弈的行为学实验证实了公平偏好的存 在性：提议者通常提供给对方 30%～50% 的份额， 而响应者往往接受 20%～35% 的份额. 公平是各 种系统稳定运行的关键. 对财富不公平的分配往 往会造成社会不平等. 而社会不平等在皮尤研究 中心的报告中被认为是世界上最大的挑战，击败 宗教仇恨、污染和核武器等. 最后通牒博弈允许关注资源配置的两个重要 方面[78−80] ：个体作为提议者给予对方的资源量，即 2000 提议量；个体作为响应者可接受的最低提议量，即 响应量. 同时，它也是最受欢迎的实验研究对象之 一. 自从复杂网络上演化博弈受到广泛关注，网络 结构就成为促进合作演化的最重要机制. 一个自 然问题是，网络结构如何影响最后通牒博弈中公 平的演化？早在 年 ，Page 等就发现环和方格 网络本身并不能促进公平的演化：当模仿过程的 噪声较高，即模仿的准确率较低时，群体的平均提 议量和响应量最终稳定在相对公平的范围[81] . 类 似的结论也在小世界及随机网络中发现[82−83] ，且 对各种初始条件和更新过程鲁棒[84−87] . 事实上，噪 声是促进公平涌现的机制之一. 即使在混合均匀 群体中，一定程度的噪声也会促进公平的演化，所 诱导的群体资源配置行为与实验所发现的分配行 为相符合[88] . 这主要是由于噪声引入一些并不适 应环境的策略，特别是当高需求的响应者进入群 体后，提议者相应地提高自身的提议量. 除了噪 声，众多学者还提出很多能够促进网络群体中公 平偏好涌现的机制. 目前，最后通牒博弈的行为学实验关注了博 弈双方的关系因素、博弈决策的情境因素、分配 物的数量因素等对于决策结果的影响. 下面将要 介绍的五类因素不仅在行为学实验而且在演化博 弈框架下均被广泛关注. 其一是角色分配. Killingback 和 Studer 在方格 网络中研究角色分配由博弈双方固有等级的相对 高低来决定的模型[89] . 当适应度线性依赖收益时， 群体平均提议量和响应量稳定在相对公平的范 围；而在适应度与收益的依赖关系中融入递减回 报效应时，二者明显降低. Wu 等的研究在无标度 网络中对比了基于度的角色分配方式和自适应角 色更替方式[90] . 其中自适应角色更替方式更能促 进公平偏好的涌现，此时一旦提议者的分配方案 被接受，博弈双方在下一轮博弈中以较大概率担 当相同角色；否则二者以较大概率改变角色进行 博弈. 其二是声望. Yang 等在方格和随机网络中研 究由声望确定博弈对象和角色分配的模型[91] . 具 体而言，个体收益作为声望信息，邻居以此选择是 否与其博弈，提议者成功分配资源的次数作为声 望信息，博弈对象据此确定其再次成为提议者的 概率. 当个体更愿意与高收益个体进行博弈，且声 望较好的个体往往担当提议者时，公平偏好被显 著提高. 此时，个体为了获取更多博弈机会和提议 者的角色分配，不得不提高自身提议量，与此同时 · 406 · 工程科学学报，第 44 卷，第 3 期

张艳玲等：演化博弈与资源配置综述 407 响应者为了获得较高收益而提高自身响应量.但 的声望；“恶意”和“同理心”属于分配意图方面的 提议量也没有必要高于50%，一旦超过50%，个体 博弈决策情境因素，“恶意”指的是厌恶对方的情 更愿意担当响应者 绪，“同理心“指的是以自己的标准要求别人；“配 其三是恶意四和非单调拒绝.恶意指的是所 置资源总量”属于分配物的数量因素.除了上述因 采取的行为令对手获得较少收益或遭受更多损 素外，Deng等提出每个主体同时位于两个物理网 失，具体表现为个体作为提议者提供给对方较低 络的模型0，发现耦合的两个网络相比于单个网 分配额，而作为响应者拒绝较低提议量.非单调拒 络更加促进公平偏好的演化稳定，双向通信要比 绝指的是个体不仅拒绝较低的还拒绝较高的提议 单向通信更加高效，Zhao等发现内群偏私能有效 量.这两种行为的存在性已被行为学实验所证实， 提升群体平均提议量和响应量)，内群偏私意味 同时也激发了大量行为学实验调查它们对于公平 给予相似个体更多分配额，同时接受对方较低提 演化的影响.鉴于此，Zhang与Fu在任意网络群体 议量 中，从理论上对融入这两种行为的离散策略最后 4总结及未来发展趋势 通牒博弈模型进行了分析9)以策略干预的研究 思路，即在原本旗鼓相当的公平和自私的竞争中， 复杂网络上演化博弈理论不断发展和完善， 通过依次加入利他策略、恶意策略、非单调拒绝 尤其在两策略竞争理论分析方法上获得了里程碑 行为，发现利他抑制公平的演化，恶意和非单调拒 式进步.本文首先介绍了在演化博弈框架下合作 绝促进公平的演化 演化机制的相关研究，详细给出了近年来被广泛 其四是同理心侧-同理心指的是个体提议 关注的个体异质性和环境反馈对于合作演化的影 量等于其响应量，意味个体期待对方给予自身的 响：其次阐述了五种复杂网络上演化博弈的理论 份额不低于自身给予他人的份额.大量研究通常 分析方法，包括适用于任意网络结构和更新规则 将同理心的存在作为前提假设，发现其在众多网 的潮祖随机游走理论：再次总结了在演化博弈框 络群体中能够促进公平的涌现.Zhang等在社团结 架下的资源配置问题，所采用的博弈模型是最后 构群体中假设同理心可随时间演化，研究同理心 通牒博弈.然而最后通牒博弈是典型的连续策略 与噪声如何共同影响公平的演化适量的初始 博弈，连续策略在复杂网络中传播所诱导的群体 同理心和噪声所诱导的群体资源配置行为与行为 状态维度比两策略庞大很多，因此相应理论分析 学实验所展现的分配行为相符合.当噪声较低时， 更具挑战性，相关研究还未形成较为成熟的理论 初始同理心越强，越有利于群体决策行为接近绝 分析框架.结合目前研究现状，我们发现： 对公平；而当噪声较高时，初始同理心越强反而不 利用最后通牒博弈研究公平偏好涌现问题大 利于公平的涌现 多采用计算机仿真，而理论分析是深刻理解网络 其五是配置资源总量7]你可以轻易地拒 群体中策略竞争的必要条件.目前关于最后通牒 绝100元的1%，但你会拒绝100亿元的1%吗？ 博弈的理论分析往往只是针对特定网络群体，故 实验者为证实配置资源对于公平的影响进行了大 亟待寻找新工具、新方法来处理一般网络群体的 量实验，但仍缺乏一致性结论.Zhang等理论分析 最后通牒博弈 了最后通牒博弈中配置资源如何影响资源配置行 对于个体交互网络，大多数文献只是关注给 为四.推导了社团结构群体中平均提议量和响应 定交互异质性的网络群体如何影响公平偏好的涌 量，发现二者所占比例反比于配置资源，即随着配 现.而不同社会网络所对应的交互异质性往往不 置资源量的增加，群体所展现的决策行为越来越 同，目前还没有相应成果系统对比异质性不同所 接近于子博弈完美纳什均衡.而群体平均提议量 诱导的公平行为的差异性 和响应量本身的大小二次依赖于配置资源，其中 对于个体资源，往往假定所有个体都是相同 配置资源越大，提议量越大，而适中的配置资源诱 的.鉴于普遍存在的贫富分化现象和收入不均现 导最大的响应量 象，个体资源通常因人而异，所有个体具有相同资 “角色分配”和“声望”属于博弈双方的关系因 源是一种理想化的假设，无法描述个体的差异性 素，“角色分配”指的是博弈中的身份，并非随机指 属性，由此限制相应理论结果的应用范围，例如无 定，而是通过一定手段获得提议者的身份，“声望” 法展现穷人和富人在资源配置过程中决策行为的 指的是提议者做决策时会考虑提议方案影响自身 差异性

50% 50% 响应者为了获得较高收益而提高自身响应量. 但 提议量也没有必要高于 ，一旦超过 ，个体 更愿意担当响应者. 其三是恶意[92] 和非单调拒绝. 恶意指的是所 采取的行为令对手获得较少收益或遭受更多损 失，具体表现为个体作为提议者提供给对方较低 分配额，而作为响应者拒绝较低提议量. 非单调拒 绝指的是个体不仅拒绝较低的还拒绝较高的提议 量. 这两种行为的存在性已被行为学实验所证实， 同时也激发了大量行为学实验调查它们对于公平 演化的影响. 鉴于此，Zhang 与 Fu 在任意网络群体 中，从理论上对融入这两种行为的离散策略最后 通牒博弈模型进行了分析[93] . 以策略干预的研究 思路，即在原本旗鼓相当的公平和自私的竞争中， 通过依次加入利他策略、恶意策略、非单调拒绝 行为，发现利他抑制公平的演化，恶意和非单调拒 绝促进公平的演化. 其四是同理心[94−95] . 同理心指的是个体提议 量等于其响应量，意味个体期待对方给予自身的 份额不低于自身给予他人的份额. 大量研究通常 将同理心的存在作为前提假设，发现其在众多网 络群体中能够促进公平的涌现. Zhang 等在社团结 构群体中假设同理心可随时间演化，研究同理心 与噪声如何共同影响公平的演化[96] . 适量的初始 同理心和噪声所诱导的群体资源配置行为与行为 学实验所展现的分配行为相符合. 当噪声较低时， 初始同理心越强，越有利于群体决策行为接近绝 对公平；而当噪声较高时，初始同理心越强反而不 利于公平的涌现. 其五是配置资源总量[97−98] . 你可以轻易地拒 绝 100 元的 1%，但你会拒绝 100 亿元的 1% 吗？ 实验者为证实配置资源对于公平的影响进行了大 量实验，但仍缺乏一致性结论. Zhang 等理论分析 了最后通牒博弈中配置资源如何影响资源配置行 为[99] . 推导了社团结构群体中平均提议量和响应 量，发现二者所占比例反比于配置资源，即随着配 置资源量的增加，群体所展现的决策行为越来越 接近于子博弈完美纳什均衡. 而群体平均提议量 和响应量本身的大小二次依赖于配置资源，其中 配置资源越大，提议量越大，而适中的配置资源诱 导最大的响应量. “角色分配”和“声望”属于博弈双方的关系因 素，“角色分配”指的是博弈中的身份，并非随机指 定，而是通过一定手段获得提议者的身份，“声望” 指的是提议者做决策时会考虑提议方案影响自身 的声望；“恶意”和“同理心”属于分配意图方面的 博弈决策情境因素，“恶意”指的是厌恶对方的情 绪，“同理心“指的是以自己的标准要求别人；“配 置资源总量”属于分配物的数量因素. 除了上述因 素外，Deng 等提出每个主体同时位于两个物理网 络的模型[100] ，发现耦合的两个网络相比于单个网 络更加促进公平偏好的演化稳定，双向通信要比 单向通信更加高效. Zhao 等发现内群偏私能有效 提升群体平均提议量和响应量[101] ，内群偏私意味 给予相似个体更多分配额，同时接受对方较低提 议量. 4    总结及未来发展趋势 复杂网络上演化博弈理论不断发展和完善， 尤其在两策略竞争理论分析方法上获得了里程碑 式进步. 本文首先介绍了在演化博弈框架下合作 演化机制的相关研究，详细给出了近年来被广泛 关注的个体异质性和环境反馈对于合作演化的影 响；其次阐述了五种复杂网络上演化博弈的理论 分析方法，包括适用于任意网络结构和更新规则 的溯祖随机游走理论；再次总结了在演化博弈框 架下的资源配置问题，所采用的博弈模型是最后 通牒博弈. 然而最后通牒博弈是典型的连续策略 博弈，连续策略在复杂网络中传播所诱导的群体 状态维度比两策略庞大很多，因此相应理论分析 更具挑战性，相关研究还未形成较为成熟的理论 分析框架. 结合目前研究现状，我们发现： 利用最后通牒博弈研究公平偏好涌现问题大 多采用计算机仿真，而理论分析是深刻理解网络 群体中策略竞争的必要条件. 目前关于最后通牒 博弈的理论分析往往只是针对特定网络群体，故 亟待寻找新工具、新方法来处理一般网络群体的 最后通牒博弈. 对于个体交互网络，大多数文献只是关注给 定交互异质性的网络群体如何影响公平偏好的涌 现. 而不同社会网络所对应的交互异质性往往不 同，目前还没有相应成果系统对比异质性不同所 诱导的公平行为的差异性. 对于个体资源，往往假定所有个体都是相同 的. 鉴于普遍存在的贫富分化现象和收入不均现 象，个体资源通常因人而异，所有个体具有相同资 源是一种理想化的假设，无法描述个体的差异性 属性，由此限制相应理论结果的应用范围，例如无 法展现穷人和富人在资源配置过程中决策行为的 差异性. 张艳玲等： 演化博弈与资源配置综述 · 407 ·

408 工程科学学报，第44卷.第3期 目前最后通牒博弈的研究均是在恒定环境下 [16]Debarre F.Fidelity of parent-offspring transmission and the 进行.而策略演化动力学与环境相互影响而形成 evolution of social behavior in structured populations.J Theor 的反馈在生物和社会系统中普遍存在，同时环境 Biol,2017,420:26 [17]McAvoy A,Fraiman N,Hauert C,et al.Public goods games in 反馈已被证实可以促进合作的演化.则环境反馈 populations with fluctuating size.Theor Popul Biol,2018,121: 如何影响公平行为的涌现是一个值得深入探讨和 72 研究的科学问题 [18] Szabo G,Borsos I.Evolutionary potential games on lattices.Phys Rep,2016,624:1 参考文献 [19]Lessard S,Soares C D.Frequency-dependent growth in class- [1] Barabasi A L,Albert R.Emergence of scaling in random structured populations:Continuous dynamics in the limit of weak networks.Science,1999,286(5439):509 selection.J Math Biol,2018,77(1):229 [2] Wang L.Wu T,Zhang Y L.Feedback mechanism in [20]Smith J M,Price G R.The logic of animal conflict.Nature,1973, coevolutionary games.Control Theory Appl,2014,31(7):823 246(5427):15 (王龙，吴特，张艳玲.共演化博弈中的反馈机制.控制理论与 [21]Khoo T,Fu F,Pauls S.Spillover modes in multiplex games: 应用，2014,31(7)：823) Double-edged effects on cooperation and their coevolution.Sci [3] Gallo E,Yan C.The effects of reputational and social knowledge Rep,2018,8:6922 on cooperation.Proc Natl Acad Sci USA,2015,112(12):3647 [22]Wang Q,He N R,Chen X J.Replicator dynamics for public [4] Li X,Cao L.Largest Laplacian eigenvalue predicts the goods game with resource allocation in large populations.Appl emergence of costly punishment in the evolutionary ultimatum Math Comput,2018,328:162 game on networks.Plys Rev E,2009,80(6):066101 [23]Perc M,Jordan J J,Rand D G,et al.Statistical physics of human [5] Doebeli M,Ispolatov Y,Simon B.Point of view:Towards a cooperation.Phys Rep,2017,687:1 mechanistic foundation of evolutionary theory.Elife,2019,6: [24]Hilbe C,Martinez-Vaquero L A,Chatterjee K,et al.Memory-n e23804 strategies of direct reciprocity.Proc Natl Acad Sci USA.2017. [6] Goswami A,Gupta R,Parashari G S.Reputation-based resource 114(18):4715 allocation in P2P systems:A game theoretic perspective./EEE [25] Cheng D Z,Liu Z Q.Application of semi-tensor product of Commmn Lett,2017,21(6):1273 matrices to finite games.Control Theory Appl,2019,36(11): [7] Hilbe C,Wu B,Traulsen A,et al.Cooperation and control in 1812 multiplayer social dilemmas.Proc Natl Acad Sci USA,2014, (程代展，刘泽群.有限博弈的矩阵半张量积方法.控制理论与 111(46):16425 应用.2019,36(11)：1812) [8] Tan S L,Wang Y N.Graphical Nash equilibria and replicator [26] Deng Z H,Nian X H.Distributed generalized Nash equilibrium dynamics on complex networks.IEEE Trans Neural Networks seeking algorithm design for aggregative games over weight- Learn Syst,2020,31(6:1831 balanced digraphs.IEEE Trans Neural Networks Learn Syst, [9] Julou T,Mora T,Guillon L,et al.Cell-cell contacts confine 2019.30(3):695 public goods diffusion inside pseudomonas aeruginosa clonal [27]Zhang R,Zhu Q Y.A game-theoretic approach to design secure microcolonies.Proc Natl Acad Sci USA,2013,110(31):12577 and resilient distributed support vector machines.IEEE Trans [10]Qi S,Footer O,Camerer C F,et al.A collaborator's reputation Neural Networks Learn Syst,2018,29(11):5512 can bias decisions and anxiety under uncertainty.J Neurosci, [28]Chotibut T,Nelson D R.Population genetics with fluctuating 2018,38(9:2262 population sizes.J Stat Phys,2017,167(3-4):777 [11]Feng C,Luo Y J,Krueger F.Neural signatures of fairness-related [29]Constable G W,Rogers T,McKane A J,et al.Demographic noise normative decision making in the ultimatum game:A coordinate- can reverse the direction of deterministic selection.Proc Narl based meta-analysis.Humn Brain Mapp,2015,36(2):591 Acad Sci US4,2016,113(32):4745 [12]Duradoni M,Paolucci M,Bagnoli F,et al.Faimess and trust in [30]Liu Y,Zhang J.An B.et al.A simulation framework for virtual environments:The effects of reputation.Future Internet, measuring robustness of incentive mechanisms and its 2018,10(6:50 implementation in reputation systems.Auton Agents Multi Agent [13]Jeong HC,Oh S Y,Allen B,et al.Optional games on cycles and S31,2016,30(4):581 complete graphs.J Theor Biol,2014,356:98 [31]Zhang Y L,Liu A Z,Sun C Y.Development of several studies on [14]Melamed D,Harrell A,Simpson B.Cooperation,clustering,and indirect reciprocity and the evolution of cooperation.Acta Autom assortative mixing in dynamic networks.Proc Natl Acad Sci Sim,2018,44(1):1 S4,2018,115(5):951 (张艳玲，刘爱志，孙长银.间接互惠与合作演化的若干问题研 [15]Adami C,Schossau J,Hintze A.Evolutionary game theory using 究进展.自动化学报，2018,44(1)：1) agent-based methods.Phys Life Rev,2016,19:1 [32]Rong Z H,Xu X R,Wu Z X.Experiment research on the

目前最后通牒博弈的研究均是在恒定环境下 进行. 而策略演化动力学与环境相互影响而形成 的反馈在生物和社会系统中普遍存在，同时环境 反馈已被证实可以促进合作的演化. 则环境反馈 如何影响公平行为的涌现是一个值得深入探讨和 研究的科学问题. 参    考    文    献 Barabási  A  L,  Albert  R.  Emergence  of  scaling  in  random networks. Science, 1999, 286（5439）: 509 [1] Wang  L,  Wu  T,  Zhang  Y  L.  Feedback  mechanism  in coevolutionary games. Control Theory Appl, 2014, 31（7）: 823 （王龙, 吴特, 张艳玲. 共演化博弈中的反馈机制. 控制理论与 应用, 2014, 31（7）：823） [2] Gallo E, Yan C. The effects of reputational and social knowledge on cooperation. Proc Natl Acad Sci USA, 2015, 112（12）: 3647 [3] Li  X,  Cao  L.  Largest  Laplacian  eigenvalue  predicts  the emergence  of  costly  punishment  in  the  evolutionary  ultimatum game on networks. Phys Rev E, 2009, 80（6）: 066101 [4] Doebeli  M,  Ispolatov  Y,  Simon  B.  Point  of  view:  Towards  a mechanistic  foundation  of  evolutionary  theory. Elife,  2019,  6: e23804 [5] Goswami A, Gupta R, Parashari G S. Reputation-based resource allocation  in  P2P  systems:  A  game  theoretic  perspective. IEEE Commun Lett, 2017, 21（6）: 1273 [6] Hilbe  C,  Wu  B,  Traulsen  A,  et  al.  Cooperation  and  control  in multiplayer  social  dilemmas. Proc Natl Acad Sci USA,  2014, 111（46）: 16425 [7] Tan  S  L,  Wang  Y  N.  Graphical  Nash  equilibria  and  replicator dynamics  on  complex  networks. IEEE Trans Neural Networks Learn Syst, 2020, 31（6）: 1831 [8] Julou  T,  Mora  T,  Guillon  L,  et  al.  Cell-cell  contacts  confine public  goods  diffusion  inside  pseudomonas  aeruginosa  clonal microcolonies. Proc Natl Acad Sci USA, 2013, 110（31）: 12577 [9] Qi  S,  Footer  O,  Camerer  C  F,  et  al.  A  collaborator's  reputation can  bias  decisions  and  anxiety  under  uncertainty. J Neurosci, 2018, 38（9）: 2262 [10] Feng C, Luo Y J, Krueger F. Neural signatures of fairness-related normative decision making in the ultimatum game: A coordinate￾based meta-analysis. Hum Brain Mapp, 2015, 36（2）: 591 [11] Duradoni M, Paolucci M, Bagnoli F, et al. Fairness and trust in virtual  environments:  The  effects  of  reputation. Future Internet, 2018, 10（6）: 50 [12] Jeong H C, Oh S Y, Allen B, et al. Optional games on cycles and complete graphs. J Theor Biol, 2014, 356: 98 [13] Melamed D, Harrell A, Simpson B. Cooperation, clustering, and assortative  mixing  in  dynamic  networks. Proc Natl Acad Sci USA, 2018, 115（5）: 951 [14] Adami C, Schossau J, Hintze A. Evolutionary game theory using agent-based methods. Phys Life Rev, 2016, 19: 1 [15] Débarre  F.  Fidelity  of  parent-offspring  transmission  and  the evolution  of  social  behavior  in  structured  populations. J Theor Biol, 2017, 420: 26 [16] McAvoy A, Fraiman N, Hauert C, et al. Public goods games in populations  with  fluctuating  size. Theor Popul Biol,  2018,  121: 72 [17] Szabó G, Borsos I. Evolutionary potential games on lattices. Phys Rep, 2016, 624: 1 [18] Lessard  S,  Soares  C  D.  Frequency-dependent  growth  in  class￾structured populations: Continuous dynamics in the limit of weak selection. J Math Biol, 2018, 77（1）: 229 [19] Smith J M, Price G R. The logic of animal conflict. Nature, 1973, 246（5427）: 15 [20] Khoo  T,  Fu  F,  Pauls  S.  Spillover  modes  in  multiplex  games: Double-edged  effects  on  cooperation  and  their  coevolution. Sci Rep, 2018, 8: 6922 [21] Wang  Q,  He  N  R,  Chen  X  J.  Replicator  dynamics  for  public goods  game  with  resource  allocation  in  large  populations. Appl Math Comput, 2018, 328: 162 [22] Perc M, Jordan J J, Rand D G, et al. Statistical physics of human cooperation. Phys Rep, 2017, 687: 1 [23] Hilbe C, Martinez-Vaquero L A, Chatterjee K, et al. Memory-n strategies  of  direct  reciprocity. Proc Natl Acad Sci USA,  2017, 114（18）: 4715 [24] Cheng  D  Z,  Liu  Z  Q.  Application  of  semi-tensor  product  of matrices  to  finite  games. Control Theory Appl,  2019,  36（11）: 1812 （程代展, 刘泽群. 有限博弈的矩阵半张量积方法. 控制理论与 应用, 2019, 36（11）：1812） [25] Deng Z H, Nian X H. Distributed generalized Nash equilibrium seeking  algorithm  design  for  aggregative  games  over  weight￾balanced  digraphs. IEEE Trans Neural Networks Learn Syst, 2019, 30（3）: 695 [26] Zhang R, Zhu Q Y. A game-theoretic approach to design secure and  resilient  distributed  support  vector  machines. IEEE Trans Neural Networks Learn Syst, 2018, 29（11）: 5512 [27] Chotibut  T,  Nelson  D  R.  Population  genetics  with  fluctuating population sizes. J Stat Phys, 2017, 167（3-4）: 777 [28] Constable G W, Rogers T, McKane A J, et al. Demographic noise can  reverse  the  direction  of  deterministic  selection. Proc Natl Acad Sci USA, 2016, 113（32）: 4745 [29] Liu  Y,  Zhang  J,  An  B,  et  al.  A  simulation  framework  for measuring  robustness  of  incentive  mechanisms  and  its implementation in reputation systems. Auton Agents Multi Agent Syst, 2016, 30（4）: 581 [30] Zhang Y L, Liu A Z, Sun C Y. Development of several studies on indirect reciprocity and the evolution of cooperation. Acta Autom Sin, 2018, 44（1）: 1 （张艳玲, 刘爱志, 孙长银. 间接互惠与合作演化的若干问题研 究进展. 自动化学报, 2018, 44（1）：1） [31] [32] Rong  Z  H,  Xu  X  R,  Wu  Z  X.  Experiment  research  on  the · 408 · 工程科学学报，第 44 卷，第 3 期

张艳玲等：演化博弈与资源配置综述 409. evolution of cooperation and network game theory.Sci Sin Phys games.Proc Natl Acad Sci USA,2014,111(49):17558 Mech Astron,.2020,50(1):118 [53]Hilbe C.Simsa S,Chatteriee K,et al.Evolution of cooperation in (荣智海，许雄锐，吴枝喜.合作演化与网络博弈实验研究进展 stochastic games.Nature,2018,559(7713):246 中国科学：物理学力学天文学，2020,50(1)：118) [54]Su Q,MeAvoy A,Wang L,et al.Evolutionary dynamics with [33]Perc M,Gomez-Gardenes J,Szolnoki A,et al.Evolutionary game transitions.Proc Natl Acad Sci USA,2019,116(51):25398 dynamics of group interactions on structured populations:A [55] WeitzJS,Eksin C,Paarporn K,et al.An oscillating tragedy of review.J R Soc Interface,2013,10(80):20120997 the commons in replicator dynamics with game-environment [34]Nowak M A.Five rules for the evolution of cooperation.Science, feedback.Proc Natl Acad Sci USA,2016,113(47):E7518 2006.314(5805):1560 [56] Chen P,Li Q,Zhang D Z,et al.A survey of multimodal machine [35]Van Cleve J.Building a synthetic basis for kin selection and learning.Chin Eng,2020,42(5):557 evolutionary game theory using population genetics.Theor Popul (陈鹏，李擎，张德政，等.多模态学习方法综述.工程科学学报 Biol,2020,133:65 202042(5):557) [36]Allen B,Nowak M A.There is no inclusive fitness at the level of [57]Lin Y H,Weitz J S.Spatial interactions and oscillatory tragedies the individual.Curr Opin Behay Sci,2016,12:122 of the commons.Phys Rev Lett,2019,122(14):148102 [37]Hilbe C,Chatterjee K,Nowak M A.Partners and rivals in direct [58]Chen X,Szolnoki A.Punishment and inspection for governing reciprocity.Nat Hum Behay,2018,2(7):469 the commons in a feedback-evolving game.PLoS Comput Biol, [38]Donahue K,Hauser O P,Nowak M A,et al.Evolving 2018,14(7):e1006347 cooperation in multichannel games.Nat Commm,2020,11:3885 [59]Nowak M A,May R M.Evolutionary games and spatial chaos. [39]Hilbe C,Schmid L,Tkadlec J,et al.Indirect reciprocity with Nature,1992,359(6398):826 private,noisy,and incomplete information.Proc Natl Acad Sci [60]Barabasi A L.Scale-free networks:A decade and beyond. US4,2018,115(48):12241 Science,.2009,325(5939):412 [40]Clark D,Fudenberg D,Wolitzky A.Indirect reciprocity with [61] McAvoy A,Adlam B,Allen B,et al.Stationary frequencies and simple records.Proc Natl Acad Sci USA,2020,117(21):11344 mixing times for neutral drift processes with spatial structure. [41] Hauert C,Saade C,McAvoy A.Asymmetric evolutionary games Pr0 c R Soc A,2018,474(2218):20180238 with environmental feedback./Theor Biol,2019,462:347 [62] Liu J Z,Meng H R,Wang W,et al.Evolution of cooperation on [42] Szolnoki A,Perc M.Second-order free-riding on antisocial independent networks:The influence of asymmetric information punishment restores the effectiveness of prosocial punishment. sharing updating mechanism.App/Math Comput,2019,340:234 Phy3RevX,2017,7(4):041027 [63]Deng Z H,Huang Y J,Gu Z Y,et al.Multi-games on [43]Cooney D B.Analysis of multilevel replicator dynamics for interdependent networks and the evolution of cooperation.Phys general two-strategy social dilemma.Bull Math Biol,2020. 4,2018,510:83 82(6):66 [64] Zhao J Q,Luo C,Zheng Y J.Evolutionary dynamics of the [44]McAvoy A,Allen B,Nowak M A.Social goods dilemmas in cooperation clusters on interdependent networks.Phys 4,2019, heterogeneous societies.Nat Hum Behav,2020,4(8):819 517:132 [45]Su Q,Li A,Wang L.Evolutionary dynamics under interactive [65]Chu C.Hu X.Shen C.et al.Self-organized interdependence diversity.New Phys,2017,19:103023 among populations promotes cooperation by means of [46]Su Q,Zhou L,Wang L.Evolutionary multiplayer games on coevolution.Chaos,2019,29(1):013139 graphs with edge diversity.PLoS Comput Biol,2019,15(4): [66] Szolnoki A,Perc M.Information sharing promotes prosocial e1006947 behaviour.New Phys,2013,15(5):053010 [47]Zhou L,Li A M,Wang L.Evolution of cooperation on complex [67]Szolnoki A.Chen X.Reciprocity-based cooperative phalanx networks with synergistic and discounted group interactions maintained by overconfident players.Phys Rev E,2018,98(2-1): EPL,2015,110(6):60006 022309 [48]Su Q,Li A,Wang L.Evolution of cooperation with interactive [68]Xia C Y,Li X P.Wang Z,et al.Doubly effects of information identity and diversity.J Theor Biol,2018,442:149 sharing on interdependent network reciprocity.New /Phys,2018, [49]Hauser O P,Hilbe C,Chatterjee K,et al.Social dilemmas among 20(7):075005 unequals.Nature,2019,572(7770):524 [69] Ibsen-Jensen R,Chatterjee K,Nowak M A.Computational [50]Szolnoki A,Chen X J.Environmental feedback drives complexity of ecological and evolutionary spatial dynamics.Proc cooperation in spatial social dilemmas.EPL,2017,120(5): Natl Acad Sci USA,2015,112(51):15636 58001 [70]Tarnita C E,Wage N,Nowak M A.Multiple strategies in [51]Akeay E.Collapse and rescue of cooperation in evolving structured populations.Proc Natl Acad Sci US4,2011,108(6): dynamic networks.Nat Commun,2018,9:2692 2334 [52]Stewart A J,Plotkin J B.Collapse of cooperation in evolving [71]Antal T,Ohtsuki H,Wakeley J,et al.Evolution of cooperation by

evolution of cooperation and network game theory. Sci Sin Phys Mech Astron, 2020, 50（1）: 118 （荣智海, 许雄锐, 吴枝喜. 合作演化与网络博弈实验研究进展. 中国科学:物理学 力学 天文学, 2020, 50（1）：118） Perc  M,  Gómez-Gardeñes  J,  Szolnoki  A,  et  al.  Evolutionary dynamics  of  group  interactions  on  structured  populations:  A review. J R Soc Interface, 2013, 10（80）: 20120997 [33] Nowak M A. Five rules for the evolution of cooperation. Science, 2006, 314（5805）: 1560 [34] Van  Cleve  J.  Building  a  synthetic  basis  for  kin  selection  and evolutionary game theory using population genetics. Theor Popul Biol, 2020, 133: 65 [35] Allen B, Nowak M A. There is no inclusive fitness at the level of the individual. Curr Opin Behav Sci, 2016, 12: 122 [36] Hilbe C, Chatterjee K, Nowak M A. Partners and rivals in direct reciprocity. Nat Hum Behav, 2018, 2（7）: 469 [37] Donahue  K,  Hauser  O  P,  Nowak  M  A,  et  al.  Evolving cooperation in multichannel games. Nat Commun, 2020, 11: 3885 [38] Hilbe  C,  Schmid  L,  Tkadlec  J,  et  al.  Indirect  reciprocity  with private,  noisy,  and  incomplete  information. Proc Natl Acad Sci USA, 2018, 115（48）: 12241 [39] Clark  D,  Fudenberg  D,  Wolitzky  A.  Indirect  reciprocity  with simple records. Proc Natl Acad Sci USA, 2020, 117（21）: 11344 [40] Hauert C, Saade C, McAvoy A. Asymmetric evolutionary games with environmental feedback. J Theor Biol, 2019, 462: 347 [41] Szolnoki  A,  Perc  M.  Second-order  free-riding  on  antisocial punishment  restores  the  effectiveness  of  prosocial  punishment. Phys Rev X, 2017, 7（4）: 041027 [42] Cooney  D  B.  Analysis  of  multilevel  replicator  dynamics  for general  two-strategy  social  dilemma. Bull Math Biol,  2020, 82（6）: 66 [43] McAvoy  A,  Allen  B,  Nowak  M  A.  Social  goods  dilemmas  in heterogeneous societies. Nat Hum Behav, 2020, 4（8）: 819 [44] Su  Q,  Li  A,  Wang  L.  Evolutionary  dynamics  under  interactive diversity. New J Phys, 2017, 19: 103023 [45] Su  Q,  Zhou  L,  Wang  L.  Evolutionary  multiplayer  games  on graphs  with  edge  diversity. PLoS Comput Biol,  2019,  15（4）: e1006947 [46] Zhou L, Li A M, Wang L. Evolution of cooperation on complex networks  with  synergistic  and  discounted  group  interactions. EPL, 2015, 110（6）: 60006 [47] Su  Q,  Li  A,  Wang  L.  Evolution  of  cooperation  with  interactive identity and diversity. J Theor Biol, 2018, 442: 149 [48] Hauser O P, Hilbe C, Chatterjee K, et al. Social dilemmas among unequals. Nature, 2019, 572（7770）: 524 [49] Szolnoki  A,  Chen  X  J.  Environmental  feedback  drives cooperation  in  spatial  social  dilemmas. EPL,  2017,  120（5）: 58001 [50] Akçay  E.  Collapse  and  rescue  of  cooperation  in  evolving dynamic networks. Nat Commun, 2018, 9: 2692 [51] [52] Stewart  A  J,  Plotkin  J  B.  Collapse  of  cooperation  in  evolving games. Proc Natl Acad Sci USA, 2014, 111（49）: 17558 Hilbe C, Šimsa Š, Chatterjee K, et al. Evolution of cooperation in stochastic games. Nature, 2018, 559（7713）: 246 [53] Su  Q,  McAvoy  A,  Wang  L,  et  al.  Evolutionary  dynamics  with game transitions. Proc Natl Acad Sci USA, 2019, 116（51）: 25398 [54] Weitz J S, Eksin C, Paarporn K, et al. An oscillating tragedy of the  commons  in  replicator  dynamics  with  game-environment feedback. Proc Natl Acad Sci USA, 2016, 113（47）: E7518 [55] Chen P, Li Q, Zhang D Z, et al. A survey of multimodal machine learning. Chin J Eng, 2020, 42（5）: 557 （陈鹏, 李擎, 张德政, 等. 多模态学习方法综述. 工程科学学报, 2020, 42（5）：557） [56] Lin Y H, Weitz J S. Spatial interactions and oscillatory tragedies of the commons. Phys Rev Lett, 2019, 122（14）: 148102 [57] Chen  X,  Szolnoki  A.  Punishment  and  inspection  for  governing the  commons  in  a  feedback-evolving  game. PLoS Comput Biol, 2018, 14（7）: e1006347 [58] Nowak M A, May R M. Evolutionary games and spatial chaos. Nature, 1992, 359（6398）: 826 [59] Barabási  A  L.  Scale-free  networks:  A  decade  and  beyond. Science, 2009, 325（5939）: 412 [60] McAvoy A, Adlam B, Allen B, et al. Stationary frequencies and mixing  times  for  neutral  drift  processes  with  spatial  structure. Proc R Soc A, 2018, 474（2218）: 20180238 [61] Liu J Z, Meng H R, Wang W, et al. Evolution of cooperation on independent networks: The influence of asymmetric information sharing updating mechanism. Appl Math Comput, 2019, 340: 234 [62] Deng  Z  H,  Huang  Y  J,  Gu  Z  Y,  et  al.  Multi-games  on interdependent  networks  and  the  evolution  of  cooperation. Phys A, 2018, 510: 83 [63] Zhao  J  Q,  Luo  C,  Zheng  Y  J.  Evolutionary  dynamics  of  the cooperation  clusters  on  interdependent  networks. Phys A,  2019, 517: 132 [64] Chu  C,  Hu  X,  Shen  C,  et  al.  Self-organized  interdependence among  populations  promotes  cooperation  by  means  of coevolution. Chaos, 2019, 29（1）: 013139 [65] Szolnoki  A,  Perc  M.  Information  sharing  promotes  prosocial behaviour. New J Phys, 2013, 15（5）: 053010 [66] Szolnoki  A,  Chen  X.  Reciprocity-based  cooperative  phalanx maintained by overconfident players. Phys Rev E, 2018, 98（2-1）: 022309 [67] Xia C Y, Li X P, Wang Z, et al. Doubly effects of information sharing on interdependent network reciprocity. New J Phys, 2018, 20（7）: 075005 [68] Ibsen-Jensen  R,  Chatterjee  K,  Nowak  M  A.  Computational complexity of ecological and evolutionary spatial dynamics. Proc Natl Acad Sci USA, 2015, 112（51）: 15636 [69] Tarnita  C  E,  Wage  N,  Nowak  M  A.  Multiple  strategies  in structured  populations. Proc Natl Acad Sci USA,  2011,  108（6）: 2334 [70] [71] Antal T, Ohtsuki H, Wakeley J, et al. Evolution of cooperation by 张艳玲等： 演化博弈与资源配置综述 · 409 ·

410 工程科学学报，第44卷，第3期 phenotypic similarity.Proc Natl Acad Sci USA,2009,106(21): promotes rational sharing.Sci Rep,2018,8(1):1222 8597 [88]Rand D G,Tarnita C E.Ohtsuki H,et al.Evolution of fairness in [72]Zhang Y,Liu A,Sun C.Impact of migration on the multi-strategy the one-shot anonymous Ultimatum Game.Proc Natl Acad Sci selection in finite group-structured populations.Sci Rep,2016,6: US4,2013,110(7):2581 35114 [89]Killingback T,Studer E.Spatial Ultimatum Games, [73]Ohtsuki H.Hauert C.Lieberman E,et al.A simple rule for the collaborations and the evolution of fairness.Proc Biol Sci,2001, evolution of cooperation on graphs and social networks.Nature, 268(1478):1797 2006,441(7092):502 [90]Wu T,Fu F,Zhang Y,et al.Adaptive role switching promotes [74]Allen B,Lippner G.Chen Y T,et al.Evolutionary dynamics on fairness in networked ultimatum game.Sci Rep,2013,3:1550 any population structure.Narre,2017,544(7649):227 [91]Yang Z H,Li Z.Wu T,et al.Effects of partner choice and role [75]Allen B,McAvoy A.A mathematical formalism for natural assignation in the spatial ultimatum game.EPL,2015,109(4): selection with arbitrary spatial and genetic structure.Math Biol, 40013 2019,78(4):1147 [92] Forber P,Smead R.The evolution of fairness through spite.Proc [76]Allen B,Nowak M.Games on graphs.EMS Surv Math Sci,2014, Biol Sci,2014,281(1780):20132439 1(1):113 [93] Zhang YL.Fu F.Strategy intervention for the evolution of [77]Zhang Y L,Fu F,Wu T,et al.A tale of two contribution fairess.PLoS One,2018,13(5):e0196524 mechanisms for nonlinear public goods.Sci Rep,2013,3:2021 [94] Szolnoki A,Perc M,Szabo G.Defense mechanisms of [78]Debove S,Baumard N.Andre J B.Models of the evolution of empathetic players in the spatial ultimatum game.Phys Rey Lett, fairness in the ultimatum game:A review and classification.Evol 2012,109(7):078701 Hum Behav,2016,37(3):245 [95]Page K M,Nowak M A.Empathy leads to fairness.Bull Math [79] Santos F P,Santos F C,Paiva A,et al.Evolutionary dynamics of BioL,2002,64(6):1101 group fairness.Theor Biol,2015,378:96 [96]Zhang Y L,Liu J,Li A M.Effects of empathy on the [80] Takesue H,Ozawa A,Morikawa S.Evolution of favoritism and evolutionary dynamics of fairness in group-structured systems. group fairness in a co-evolving three-person ultimatum game. EPL,2017,118(4):48002 Complexi0,2019,2019:2915020 [81] Page K M,Nowak M A,Sigmund K.The spatial ultimatum [97]Wang X,Chen X,Wang L.Random allocation of pies promotes game.Proc R Soc Lond B,2000,267(1458):2177 the evolution of fairess in the Ultimatum Game.Sci Rep,2014, [82] Alexander J M K.The Structural Evolution of Morality. 4:4534 Cambridge University Press,2007 [98]Chen W,Wu T,Li Z W,et al.Heterogenous allocation of chips [83] Iranzo J,Roman J,Sanchez A.The spatial Ultimatum game promotes faimess in the Ultimatum Game.EPL,2015,109(6): revisited.J Theor Biol,2011,278(1):1 68006 [84]Gao J,Li Z,Wu T,et al.The coevolutionary ultimatum game. [99]Zhang Y L,Chen X J,Liu A Z,et al.The effect of the stake size EPL,2011,93(4:48003 on the evolution of faimess.Appl Math Comput,2018,321:641 [85]Wang X F,Chen X J,Wang L.Evolutionary dynamics of fairness [100]Deng LL,Lin Y,Wang C,et al.Effects of coupling strength and on graphs with migration.J Theor Biol,2015,380:103 coupling schemes between interdependent lattices on the [86]Szolnoki A,Perc M,Szabo G.Accuracy in strategy imitations evolutionary ultimatum game.Phys,2020,540:123173 promotes the evolution of fairness in the spatial ultimatum game. [101]Zhao Y K,Xiong T,Zheng L,et al.The effect of similarity on the EPL,2012,100(2):28005 evolution of faimess in the ultimatum game.Chaos Soliton Fract, [87]Han X,Cao S,Bao J Z,et al.Equal status in Ultimatum Games 2020,131:109494

phenotypic similarity. Proc Natl Acad Sci USA, 2009, 106（21）: 8597 Zhang Y, Liu A, Sun C. Impact of migration on the multi-strategy selection in finite group-structured populations. Sci Rep, 2016, 6: 35114 [72] Ohtsuki H, Hauert C, Lieberman E, et al. A simple rule for the evolution of cooperation on graphs and social networks. Nature, 2006, 441（7092）: 502 [73] Allen B, Lippner G, Chen Y T, et al. Evolutionary dynamics on any population structure. Nature, 2017, 544（7649）: 227 [74] Allen  B,  McAvoy  A.  A  mathematical  formalism  for  natural selection with arbitrary spatial and genetic structure. J Math Biol, 2019, 78（4）: 1147 [75] Allen B, Nowak M. Games on graphs. EMS Surv Math Sci, 2014, 1（1）: 113 [76] Zhang  Y  L,  Fu  F,  Wu  T,  et  al.  A  tale  of  two  contribution mechanisms for nonlinear public goods. Sci Rep, 2013, 3: 2021 [77] Debove  S,  Baumard  N,  André  J  B.  Models  of  the  evolution  of fairness in the ultimatum game: A review and classification. Evol Hum Behav, 2016, 37（3）: 245 [78] Santos F P, Santos F C, Paiva A, et al. Evolutionary dynamics of group fairness. J Theor Biol, 2015, 378: 96 [79] Takesue H, Ozawa A, Morikawa S. Evolution of favoritism and group  fairness  in  a  co-evolving  three-person  ultimatum  game. EPL, 2017, 118（4）: 48002 [80] Page  K  M,  Nowak  M  A,  Sigmund  K.  The  spatial  ultimatum game. Proc R Soc Lond B, 2000, 267（1458）: 2177 [81] Alexander  J  M  K. The Structural Evolution of Morality. Cambridge University Press, 2007 [82] Iranzo  J,  Román  J,  Sánchez  A.  The  spatial  Ultimatum  game revisited. J Theor Biol, 2011, 278（1）: 1 [83] Gao  J,  Li  Z,  Wu  T,  et  al.  The  coevolutionary  ultimatum  game. EPL, 2011, 93（4）: 48003 [84] Wang X F, Chen X J, Wang L. Evolutionary dynamics of fairness on graphs with migration. J Theor Biol, 2015, 380: 103 [85] Szolnoki  A,  Perc  M,  Szabó  G.  Accuracy  in  strategy  imitations promotes the evolution of fairness in the spatial ultimatum game. EPL, 2012, 100（2）: 28005 [86] [87] Han X, Cao S, Bao J Z, et al. Equal status in Ultimatum Games promotes rational sharing. Sci Rep, 2018, 8（1）: 1222 Rand D G, Tarnita C E, Ohtsuki H, et al. Evolution of fairness in the  one-shot  anonymous  Ultimatum  Game. Proc Natl Acad Sci USA, 2013, 110（7）: 2581 [88] Killingback  T,  Studer  E.  Spatial  Ultimatum  Games, collaborations and the evolution of fairness. Proc Biol Sci, 2001, 268（1478）: 1797 [89] Wu  T,  Fu  F,  Zhang  Y,  et  al.  Adaptive  role  switching  promotes fairness in networked ultimatum game. Sci Rep, 2013, 3: 1550 [90] Yang Z H, Li Z, Wu T, et al. Effects of partner choice and role assignation  in  the  spatial  ultimatum  game. EPL,  2015,  109（4）: 40013 [91] Forber P, Smead R. The evolution of fairness through spite. Proc Biol Sci, 2014, 281（1780）: 20132439 [92] Zhang  Y  L,  Fu  F.  Strategy  intervention  for  the  evolution  of fairness. PLoS One, 2018, 13（5）: e0196524 [93] Szolnoki  A,  Perc  M,  Szabó  G.  Defense  mechanisms  of empathetic players in the spatial ultimatum game. Phys Rev Lett, 2012, 109（7）: 078701 [94] Page  K  M,  Nowak  M  A.  Empathy  leads  to  fairness. Bull Math Biol, 2002, 64（6）: 1101 [95] Zhang  Y  L,  Liu  J,  Li  A  M.  Effects  of  empathy  on  the evolutionary  dynamics  of  fairness  in  group-structured  systems. Complexity, 2019, 2019: 2915020 [96] Wang X, Chen X, Wang L. Random allocation of pies promotes the evolution of fairness in the Ultimatum Game. Sci Rep, 2014, 4: 4534 [97] Chen W, Wu T, Li Z W, et al. Heterogenous allocation of chips promotes  fairness  in  the  Ultimatum  Game. EPL,  2015,  109（6）: 68006 [98] Zhang Y L, Chen X J, Liu A Z, et al. The effect of the stake size on the evolution of fairness. Appl Math Comput, 2018, 321: 641 [99] Deng L L, Lin Y, Wang C, et al. Effects of coupling strength and coupling  schemes  between  interdependent  lattices  on  the evolutionary ultimatum game. Phys A, 2020, 540: 123173 [100] Zhao Y K, Xiong T, Zheng L, et al. The effect of similarity on the evolution of fairness in the ultimatum game. Chaos Soliton Fract, 2020, 131: 109494 [101] · 410 · 工程科学学报，第 44 卷，第 3 期