Graph topology and the evolution of cooperation

Li, Menglin
It has been shown that the graph topology can influence the level of cooperation in evolutionary games. Previous research showed that graphs like scale-free networks and small-world networks are more useful in maintaining cooperation. Many researchers believe that the emergence of a high level of cooperation on scale-free networks is due to its power-law degree distribution and the existence of hubs. The main motivation of this work is to examine the influence of the structure of the graph in maintaining cooperation. Apart from the graph topology, we have also examined the influence of the game's payoff and the player's strategies on the emergence of cooperation. We analysed the payoff matrix of the two-player pure-strategy social dilemma on a lattice grid first, followed by a study of iterated strategies in the prisoner's dilemma game on a lattice grid, from which, we have understood the influence of the game's payoff and the player's strategy. The analysis of the game's payoffs and the player's strategy helped us to select suitable values of those attributes during the subsequent research on complex graphs, through which, we could understand the influence of the graph topology more clearly, and identify more features that influence the outcome of the evolutionary games. With selected payoff matrices and strategy sets and have run experiments on graphs generated by our new graph generation algorithms; we analysed the influence of the average degree and transitivity of the graphs on the robustness of the cooperation. The results of these experiments show that the robustness of cooperation is actually related to the presence of certain combinations of sub-communities. This finding lead us to the research on individual nodes in graphs. By analysing the graph centralities of each individual node, we found that the graph centrality is related to the ability of certain strategies to invade the population. This gives us a prospective vision that predictions can be made to understand the invasion of the defectors through examining the node centralities. This may help us to predict the level of cooperation on complex graphs. The unique contributions of this work include: The understanding of the influence of game's payoff on the emergence of cooperation and a prediction formula that can predict the level of cooperation on lattice grids. An analysis of the performance of N-player TFT strategies against the pure strategy players (pure C and pure D): N-player TFT strategies can not be guaranteed to outperform pure D strategies, but the N-player TFT strategies with a lower level of tolerance usually perform much better than others. A new approaches to generating graphs with predefined degree and clustering coefficient. An analysis of the influence of average degree and transitivity of graphs on the robustness of cooperation: in lower average degree graphs, higher transitivity means increased robustness of cooperation. Research of how an individual node's graph centrality can affect the level of cooperation, which gives us an approach to making prediction of the level of cooperation through analysing the centralities of the nodes with a defector, in order to helps us to understand the invasion of defection on complex graphs. This could be an alternative approach to understand the evolution on complex graphs. Development of an open source graph simulator.
Publisher DOI
Attribution-NonCommercial-NoDerivs 3.0 Ireland