Faculty of Social and Political Sciences, Institute of Applied Mathematics, University of Lausanne, Lausanne, Switzerland.
PLoS One. 2012;7(9):e44514. doi: 10.1371/journal.pone.0044514. Epub 2012 Sep 10.
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.
通过结合进化博弈论和图论，“图上博弈”研究了频率依赖选择在基于地理或社交网络的群体结构中的进化动态。网络通常通过单分图表示，而社交互动则通过两人游戏（如著名的囚徒困境）表示。单分图也被用于描述超越两人互动的互动。在本文中，我们认为二分图是描述进化多人游戏中群体结构的更好选择。为了说明这一点，我们使用二分图通过计算机模拟研究了传统和分布式 N 人囚徒困境下合作的进化。我们表明，基于单分图的标准方法所产生的几个隐含假设（例如替换邻域的定义、个体多样性和群体多样性的交织以及交互邻域的大量重叠）可能会对产生的进化动态产生重大影响。我们的工作提供了一个清晰的例子，说明了图上博弈中构造过程的重要性，双图和超图在计算建模中的适用性，以及来自社交网络分析的概念（如中心性、集中化和二分聚类）对于理解发生在网络群体结构上的动态过程的重要性。
