Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games
Open Access
- 10 September 2012
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 7 (9) , e44514
Abstract
By combining evolutionary game theory and graph theory, “games on graphs” study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of unipartite graphs, and social interactions by two-person games such as the famous prisoner’s dilemma. Unipartite graphs have also been used for modeling interactions going beyond pairwise interactions. In this paper, we argue that bipartite graphs are a better alternative to unipartite graphs for describing population structures in evolutionary multiplayer games. To illustrate this point, we make use of bipartite graphs to investigate, by means of computer simulations, the evolution of cooperation under the conventional and the distributed N-person prisoner’s dilemma. We show that several implicit assumptions arising from the standard approach based on unipartite graphs (such as the definition of replacement neighborhoods, the intertwining of individual and group diversity, and the large overlap of interaction neighborhoods) can have a large impact on the resulting evolutionary dynamics. Our work provides a clear example of the importance of construction procedures in games on graphs, of the suitability of bigraphs and hypergraphs for computational modeling, and of the importance of concepts from social network analysis such as centrality, centralization and bipartite clustering for the understanding of dynamical processes occurring on networked population structures.Keywords
This publication has 69 references indexed in Scilit:
- Population Structure Induces a Symmetry Breaking Favoring the Emergence of CooperationPLOS Computational Biology, 2009
- Snowdrift game dynamics and facultative cheating in yeastNature, 2009
- Natural selection of altruism in inelastic viscous homogeneous populationsJournal of Theoretical Biology, 2008
- Mesoscopic Structure Conditions the Emergence of Cooperation on Social NetworksPLOS ONE, 2008
- TRANSFORMING THE DILEMMAEvolution, 2007
- Evolutionary graph theory: Breaking the symmetry between interaction and replacementJournal of Theoretical Biology, 2007
- Participation costs dismiss the advantage of heterogeneous networks in evolution of cooperationProceedings Of The Royal Society B-Biological Sciences, 2007
- Five Rules for the Evolution of CooperationScience, 2006
- A simple rule for the evolution of cooperation on graphs and social networksNature, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005