A Computational Survey of Evolutionary Game Dynamics on Complex Networks
TAN Shaolin1, Lü Jinhu2
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
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.
谭少林, 吕金虎. 复杂网络上的演化博弈动力学——一个计算视角的综述[J]. 复杂系统与复杂性科学, 2017, 14(4): 1-13.
TAN Shaolin, Lü Jinhu. A Computational Survey of Evolutionary Game Dynamics on Complex Networks. Complex Systems and Complexity Science, 2017, 14(4): 1-13.
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.
