Evolutionary stable strategies in networked games: the influence of topology

• Autorzy: Kasthurirathna D. , Piraveenan M. , Uddin S.

Identyfikatory

DOI

10.1515/jaiscr-2015-0021

• Języki publikacji: EN

Abstrakty

EN

Evolutionary game theory is used to model the evolution of competing strategies in a population of players. Evolutionary stability of a strategy is a dynamic equilibrium, in which any competing mutated strategy would be wiped out from a population. If a strategy is weak evolutionarily stable, the competing strategy may manage to survive within the network. Understanding the network-related factors that affect the evolutionary stability of a strategy would be critical in making accurate predictions about the behaviour of a strategy in a real-world strategic decision making environment. In this work, we evaluate the effect of network topology on the evolutionary stability of a strategy. We focus on two well-known strategies known as the Zero-determinant strategy and the Pavlov strategy. Zero-determinant strategies have been shown to be evolutionarily unstable in a well-mixed population of players. We identify that the Zero-determinant strategy may survive, and may even dominate in a population of players connected through a non-homogeneous network. We introduce the concept of ‘topological stability’ to denote this phenomenon. We argue that not only the network topology, but also the evolutionary process applied and the initial distribution of strategies are critical in determining the evolutionary stability of strategies. Further, we observe that topological stability could affect other well-known strategies as well, such as the general cooperator strategy and the cooperator strategy. Our observations suggest that the variation of evolutionary stability due to topological stability of strategies may be more prevalent in the social context of strategic evolution, in comparison to the biological context.

Słowa kluczowe

EN

evolutionary game theory; competing strategy; evolutionary stability; network topology; Zero-determinant strategy; Pavlov strategy; players population; topological stability; cooperator strategy

PL

ewolucyjna teoria gier; strategia współzawodnictwa; stabilność ewolucyjna; topologia sieci; strategia Pavlova; populacja graczy; stabilność topologiczna; strategia współpracy

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2015
• Tom: Vol. 5, No. 2
• Strony: 83--95
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Kasthurirathna D.

• Centre for Complex Systems Research, Faculty of Engineering and IT The University of Sydney, NSW 2006, Australia

autor

Piraveenan M.

• Centre for Complex Systems Research, Faculty of Engineering and IT The University of Sydney, NSW 2006, Australia

autor

Uddin S.

• Centre for Complex Systems Research, Faculty of Engineering and IT The University of Sydney, NSW 2006, Australia

Bibliografia

• [1] J. Von Neumann and O. Morgenstern, “Game theory and economic behavior,” 1944.
• [2] E. Rasmusen and B. Blackwell, Games and information. Cambridge, 1994, vol. 2.
• [3] J. M. Smith and G. Price, “lhe logic of animal conflict,” Nature, vol. 246, p. 15, 1973.
• [4] J. M. Smith, Evolution and the Theory of Games. Springer, 1993.
• [5] J. Bendor and P. Swistak, “Types of evolutionary stability and the problem of cooperation.” Proceedings of the National Academy of Sciences, vol. 92, no. 8, pp. 3596–3600, 1995.
• [6] A.-L. Barab´asi and R. Albert, “Emergence of scaling in random networks,” science, vol. 286, no. 5439, pp. 509–512, 1999.
• [7] R. Albert and A.-L. Barab´asi, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, pp. 47–97, 2002.
• [8] G. Thedchanamoorthy, M. Piraveenan, S. Uddin, and U. Senanayake, “Influence of vaccination strategies and topology on the herd immunity of complex networks,” Social Network Analysis and Mining, vol. 4, no. 1, pp. 1–16, 2014.
• [9] M. Prokopenko, M. Piraveenan, and P. Wang, “On convergence of dynamic cluster formation in multiagent networks,” Advances in Artificial Life, pp. 884–894, 2005.
• [10] M. E. J. Newman, “Mixing patterns in networks,” Physical Review E, vol. 67, no. 2, p. 026126, 2003.
• [11] M. Piraveenan, M. Prokopenko, and A. Y. Zomaya, “Local assortativeness in scale-free networks,” Europhysics Letters, vol. 84, no. 2, p. 28002, 2008.
• [12] —, “Assortative mixing in directed biological networks,” IEEE/ACM Transactions on computational biology and bioinformatics, vol. 9(1), pp. 66–78, 2012.
• [13] R. V. Sol´e and S. Valverde, “Information theory of complex networks: on evolution and architectural constraints,” in Complex Networks, ser. Lecture Notes in Physics, E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai, Eds. Springer, 2004, vol. 650.
• [14] M. Piraveenan, D. Polani, and M. Prokopenko, “Emergence of genetic coding: an informationtheoretic model,” in Advances in Artificial Life. Springer Berlin Heidelberg, 2007, pp. 42–52.
• [15] M. Piraveenan, M. Prokopenko, and L. Hossain, “Percolation centrality: Quantifying graphtheoretic impact of nodes during percolation in networks,” PloS one, vol. 8, no. 1, p. e53095, 2013.
• [16] F. C. Santos and J. M. Pacheco, “Scale-free networks provide a unifying framework for the emergence of cooperation,” Physical Review Letters, vol. 95, no. 9, p. 098104, 2005.
• [17] D. B. Fogel, “Evolving behaviors in the iterated prisoner’s dilemma,” Evolutionary Computation, vol. 1, no. 1, pp. 77–97, 1993.
• [18] C. Adami and A. Hintze, “Evolutionary instability of zero-determinant strategies demonstrates that winning is not everything,” Nature communications, vol. 4, 2013.
• [19] D. Kasthurirathna, M. Piraveenan, and M. Harre, “Influence of topology in the evolution of coordination in complex networks under information diffusion constraints,” The European Physical Journal B, vol. 87, no. 1, pp. 1–15, 2014.
• [20] D. Kasthurirathna, H. Nguyen, M. Piraveenan, S. Uddin, and U. Senanayake, “Optimisation of strategy placements for public good in complex networks,” in Social Computing (SocialCom), 2014 International Conference on. IEEE, 2014, p. in print.
• [21] W. H. Press and F. J. Dyson, “Iterated prisoners dilemma contains strategies that dominate any evolutionary opponent,” Proceedings of the National Academy of Sciences, vol. 109, no. 26, pp. 10 409–10 413, 2012.
• [22] P. A. P. Moran et al., “The statistical processes of evolutionary theory.” The statistical processes of evolutionary theory., 1962.
• [23] F. Santos, J. Rodrigues, and J. Pacheco, “Graphtopology plays a determinant role in the evolution of cooperation,” Proceedings of the Royal Society B: Biological Sciences, vol. 273, no. 1582, pp. 51–55, 2006.
• [24] J. F. Nash et al., “Equilibrium points in n-person games,” Proceedings of the national academy of sciences, vol. 36, no. 1, pp. 48–49, 1950.
• [25] J. Maynard Smith, “The theory of games and the evolution of animal conflicts,” Journal of theoretical biology, vol. 47, no. 1, pp. 209–221, 1974.
• [26] S. Le and R. Boyd, “Evolutionary dynamics of the continuous iterated prisoner’s dilemma,” Journal of theoretical biology, vol. 245, no. 2, pp. 258–267, 2007.
• [27] A. Rapoport, Prisoner’s dilemma: A study in conflict and cooperation. University of Michigan Press, 1965, vol. 165.
• [28] D. P. Kraines and V. Y. Kraines, “Natural selection of memory-one strategies for the iterated prisoner’s dilemma,” Journal of Theoretical Biology, vol. 203, no. 4, pp. 335–355, 2000.
• [29] D. Iliopoulos, A. Hintze, and C. Adami, “Critical dynamics in the evolution of stochastic strategies for the iterated prisoner’s dilemma,” PLoS computational biology, vol. 6, no. 10, p. e1000948, 2010.
• [30] A. J. Stewart and J. B. Plotkin, “Extortion and cooperation in the prisoners dilemma,” Proceedings of the National Academy of Sciences, vol. 109, no. 26, pp. 10 134–10 135, 2012.