Perturbation theory for evolution of cooperation on networks

Abstract

Network structure is a mechanism for promoting cooperation in social dilemma games. In the present study, we explore graph surgery, i.e., to slightly perturb the given network, towards a network that better fosters cooperation. To this end, we develop a perturbation theory to assess the change in the propensity of cooperation when we add or remove a single edge to/from the given network. Our perturbation theory is for a previously proposed random-walk-based theory that provides the threshold benefit-to-cost ratio, $(b/c{)}^{\ast }$, which is the value of the benefit-to-cost ratio in the donation game above which the cooperator is more likely to fixate than in a control case, for any finite networks. We find that $(b/c{)}^{\ast }$ decreases when we remove a single edge in a majority of cases and that our perturbation theory captures at a reasonable accuracy which edge removal makes $(b/c{)}^{\ast }$ small to facilitate cooperation. In contrast, $(b/c{)}^{\ast }$ tends to increase when we add an edge, and the perturbation theory is not good at predicting the edge addition that changes $(b/c{)}^{\ast }$ by a large amount. Our perturbation theory significantly reduces the computational complexity for calculating the outcome of graph surgery.

arXiv comment31 pages, 6 figures

References in corpus (10)

• Emergence of scaling in random networks
• Community detection in graphs
• Finding community structure in very large networks
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Evolutionary games on graphs
• Evolutionary prisoner's dilemma game on a square lattice
• Random walks and diffusion on networks
• Stochastic Dynamics of Invasion and Fixation
• Evolutionary dynamics on any population structure

Cited by in corpus (1)

• Constant-selection evolutionary dynamics on weighted networks