×

Pure Nash equilibriums and independent dominating sets in evolutionary games on networks. (English) Zbl 07878468

Summary: Recently, a new model was developed in evolutionary game dynamics, extending the standard replicator equation to a finite set of players interacting on some network of connections. Players are modeled as the subpopulations of a multipopulation game, connected on an arbitrary graph, allowed to change their strategies over time and to adopt mixed strategies. A relation between the stability of the mixed equilibrium with the topology of the network was proved to depend on the eigenvalues of the graph’s adjacency matrix multiplied by a scalar. The present paper studies the pure (strict) Nash equilibrium, (S)NE, of these games and their connection to the network. Specifically, we present necessary and sufficient conditions for a pure steady state in a coordination or anti-coordination game to be a (strict) Nash equilibrium. A significant application of the model concerns finding the conditions for the onset of pure cooperative or pure defective behavior of players. In this direction, our main result provides conditions in an anti-coordination game such that a pure steady state of the system is a Nash equilibrium if and only if the set of players that cooperate or the set of players that defect are independent dominating sets.

MSC:

91A22 Evolutionary games
91A43 Games involving graphs
91A10 Noncooperative games
Full Text: DOI

References:

[1] E. Accinelli, J. G. Carrera and E. J. Sánchez Carrera, Imitative behavior in a two-population model, Advances in Dynamic Games, Annals of the International Society of Dynamic Games, Birkhäuser Boston, 11 (2010), 275-289. · Zbl 1218.91022
[2] E. E. J. Accinelli Sánchez Carrera, Corruption driven by imitative behavior, Economics Letter, 117, 84-87, 2012 · Zbl 1254.91068 · doi:10.1016/j.econlet.2012.04.092
[3] R. B. R. Allan Laskar, On domination and independent domination numbers of a graph, Discrete Mathematics, 23, 73-76, 1978 · Zbl 0416.05064 · doi:10.1016/0012-365X(78)90105-X
[4] A. Baronchelli, The emergence of consensus: A primer, R. Soc. Open Sci., 5 (2018), 172189, 13 pp.
[5] C. Berge, The Theory of Graphs and Its Applications, Methuen & Co., Ltd., LondonJohn Wiley & Sons, Inc., New York, 1962. · Zbl 0097.38903
[6] E. J. S. T. Cockayne Hedetniemi, Towards a theory of domination in graphs, Networks, 7, 247-261, 1977 · Zbl 0384.05051 · doi:10.1002/net.3230070305
[7] W. M. A. Goddard Henning, On domination and independent domination numbers of a graph, Discrete Mathematics, 313, 839-854, 2013 · Zbl 1260.05113 · doi:10.1016/j.disc.2012.11.031
[8] M. Jackson and Y. Zenou, Games on networks, Handbook of Game Theory with Economic Applications, Elsevier, Amsterdam, 4 (2015), 95-163.
[9] N. L. Q. Lang Wang Zha, Opinion dynamics in social networks under competition: The role of influencing factors in consensus-reaching, R. Soc. Open Sci., 9, 211732, 2022 · doi:10.1098/rsos.211732
[10] Y. Liu and K. Lee, Probabilistic consensus decision making algorithm for artificial swarm of primitive robots, SN Appl. Sci., 2 (2020), article number 95.
[11] W. F. C. Maciejewski Fu Hauert, Evolutionary game dynamics in populations with heterogenous structure, PLOS Computational Biology, 10, e1003567, 2014 · doi:10.1371/journal.pcbi.1003567
[12] D. C. Madeo Mocenni, Game interactions and dynamics on networked populations, IEEE Trans. Aut. Contr., 60, 1801-1810, 2015 · Zbl 1360.91035 · doi:10.1109/TAC.2014.2384755
[13] D. Madeo and C. Mocenni, Consensus towards partially cooperative strategies in self-regulated evolutionary games on networks, Games, 12 (2021), Paper No. 60, 16 pp. · Zbl 1484.91053
[14] A. D. V. Mare Latora, Opinion formation models based on game theory, International Journal of Modern Physics C, 18, 1377-1395, 2007 · Zbl 1200.91014 · doi:10.1142/S012918310701139X
[15] H. C. E. M. A. Ohtsuki Hauert Lieberman Nowak, A simple rule for the evolution of cooperation on graphs and social networks, Nature, 441, 502-505, 2006 · doi:10.1038/nature04605
[16] O. Ore, Theory of Graphs, American Mathematical Society, Providence, RI, 1962. · Zbl 0105.35401
[17] H. M. Ohtsuki Nowak, The replicator equation on graphs, J Theor Biol., 243, 86-97, 2006 · Zbl 1447.91024 · doi:10.1016/j.jtbi.2006.06.004
[18] J. M. G. R. Smith Price, The logic of animal conflict, Nature, 246, 15-18, 1973 · Zbl 1369.92134 · doi:10.1038/246015a0
[19] J. M. Smith, Evolution and the Theory of Games, 1982 · Zbl 0526.90102
[20] S. H. Strogatz, Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry and Engineering, 2015 · Zbl 1343.37001
[21] P. D. L. B. Taylor Jonker, Evolutionary stable strategies and game dynamics, Mathematical Biosciences, 40, 145-156, 1978 · Zbl 0395.90118 · doi:10.1016/0025-5564(78)90077-9
[22] J. Weibull, Evolutionary Game Theory, 1995 · Zbl 0879.90206
[23] J. Wu, E. Paeng, K. Linder, P. Valdesolo and J. C. Boerkoel Jr., Trust and cooperation in human-robot decision making, The 2016 AAAI Fall Symposium Series: Artificial Intelligence for Human-Robot Interaction, Arlington, United States, 2016, FS-16-01.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.