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

谭少林; 吕金虎; 谭少林; 吕金虎

doi:10.13306/j.1672-3813.2017.04.001

复杂系统与复杂性科学 >

2017 , Vol. 14 >Issue 4: 1 - 13

DOI: https://doi.org/10.13306/j.1672-3813.2017.04.001

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

谭少林 ,
吕金虎 ,
谭少林 ,
吕金虎

展开

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

谭少林(1986-),男,湖南株洲人,博士,副教授,主要研究方向为复杂网络上的博弈动力学及其学习理论。

收稿日期: 2017-10-25

网络出版日期: 2019-01-16

基金资助

国家自然科学基金(61503130),湖南省自然科学基金(2016JJ3044)

收起

A Computational Survey of Evolutionary Game Dynamics on Complex Networks

TAN Shaolin ,
Lü Jinhu ,
TAN Shaolin ,
Lü Jinhu

Expand

1.College of Electrical and Information Engineering, Hunan University, Changsha 410082;
2.Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190

Received date: 2017-10-25

Online published: 2019-01-16

Fold

摘要

复杂网络上的演化博弈是复杂网络与演化博弈结合而形成的新型交叉研究领域,它以复杂网络和演化博弈动力学分别刻画个体间的交互关联结构以及决策范式,为分析和预测复杂交互环境下群体的决策行为提供了一个系统的研究框架。旨在从一个计算的角度对复杂网络上的演化博弈动力学进行一个简要的综述:介绍复杂网络上演化博弈动力学模型的数学描述;分析网络上演化博弈动力学的计算复杂性;概述复杂网络上演化博弈动力学的若干主要解析结果等。这些结果是对于复杂网络上演化博弈动力学仿真研究的一个有效补充。

关键词： 网络博弈; 演化动力学; 复杂网络; 策略选择

本文引用格式

谭少林 , 吕金虎 , 谭少林 , 吕金虎 . 复杂网络上的演化博弈动力学——一个计算视角的综述[J]. 复杂系统与复杂性科学, 2017 , 14(4) : 1 -13 . DOI: 10.13306/j.1672-3813.2017.04.001

Abstract

Evolutionary games on complex networks is a new interdisciplinary research field at the cross-point of complex networks and evolutionary game. With a complex network and and an evolutionary game dynamics representing the interaction structure among agents and the decision paradigm respectively, evolutionary games on complex networks provides a systematic framework for analyzing and predicting the collective decision-making behaviors of complex interactive populations. This review aims to give a brief survey of evolutionary game dynamics on complex networks from a computational perspective. In detail, we will firstly present a mathematical formulation of the model of evolutionary game dynamics on complex networks, and then analyze the computational complexity of these networked game dynamics, and finally outline some main analytical results about evolutionary game dynamics on complex networks. This computational survey will be a well complement to those simulation results in evolutionary game dynamics on complex networks.

Key words： neworked games; evolutionary dynamics; complex networks; strategy selection

参考文献

[1]吕金虎,谭少林. 复杂网络上的博弈及其演化动力学[M]. 北京: 高等教育出版社, 2018.
[2]Szabo G, Fath G. Evolutionary games on graphs [J]. Phys Rep, 2007, 446: 97216.
[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): 826829.
[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): 3650.
[12] 王龙,伏峰,王靖,等. 复杂网络上的演化博弈[J]. 智能系统学报, 2007, 2(2): 110.
Wang Long, Fu Feng, Wang Jing, et al. Evolutionary games on complex networks [J]. CAAI Transactions on Intelligent Systems, 2007, 2(2): 110.
[13] 吴枝喜,荣智海,王文旭. 复杂网络上的博弈[J]. 力学进展,2008, 389(6): 794804.
Wu Zhixi, RongZhihai, Wang Wenxu. Games on complex networks [J]. Advances In Mechanics, 2008, 389(6): 794804.
[14] 杨阳,荣志海,李翔. 复杂网络演化博弈理论研究综述[J]. 复杂系统与复杂性科学,2008, 5(4):4755.
Yang Yang, RongZhihai, Li Xiang. A research survey of evolutionary game theory on complex networks[J]. Complex Systems and Complex Sciences, 2008, 5(4): 4755.
[15] Antal T, Traulsen A, Ohtsuki H, et al. Mutation-selection equilibrium in games with multiple strategies [J]. J Theor Biol, 2009, 258(4): 614622.
[16] Traulsen A, Nowak M A. Evolution of cooperation by multilevel selection [J]. Proc Natl Acad Sci USA, 2006, 103(29): 1095210955.
[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):109125.
[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: 1919319198.
[22] Rand D G, Dreber A, Ellingsen T, et al. Positive interactions promote public cooperation [J]. Science, 2009, 325: 12721275.
[23] Erdos P, Renyi A. On random graphs I [J]. Publ Math Debrecen, 1959, 6:290297.
[24] Watts D J, Strogatz S H. Collective dynamics of small-world networks [J]. Nature, 1998, 393: 440442.
[25] Barabasi A L, Albert R. Emergence of scaling in random networks [J]. Science, 1999, 286: 509512.
[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): 41184124.
[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(2829): 34913498.
[29] Lieberman E, Hauert C, Nowak M A. Evolutionary dynamics on graphs [J]. Nature, 2005, 433(7023): 312316.
[30] Ohtsuki H, Nowak M A. Evolutionary games on cycles [J]. Proc R Soc B, 2006, 273(1598): 22492256.
[31] Mesoudi A, Lycett S J. Random copying, frequecy-dependent copying and culture change [J]. Evol Hum Behav, 2009, 30(1): 4148.
[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): 27952798.
[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): 576582.
[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): 299303.
[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): 26092627.
[37] Tan S, Lü J, Lin Z. Emerging behavioral consensus of evolutionary dynamics on complex networks [J]. SIAM Journal Contr Optim, 2016, 54(6): 32583272.
[38] Tarnita C E, Ohtsuki H, Antal T, et al. Strategy selection in structured populations [J]. J Theor Biol, 2009, 259(3): 570581.
[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): 502505.
[40] Konno T. A condition for cooperation in a game on complex networks [J]. J Theor Biol, 2011, 269(1): 224233.
[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): 27852805.
[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): 16941705.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献