Fixation Probabilities for Any Configuration of Two Strategies on Regular Graphs

Abstract

Population structure and spatial heterogeneity are integral components of evolutionary dynamics, in general, and of evolution of cooperation, in particular. Structure can promote the emergence of cooperation in some populations and suppress it in others. Here, we provide results for weak selection to favor cooperation on regular graphs for any configuration, meaning any arrangement of cooperators and defectors. Our results extend previous work on fixation probabilities of rare mutants. We find that for any configuration cooperation is never favored for birth-death (BD) updating. In contrast, for death-birth (DB) updating, we derive a simple, computationally tractable formula for weak selection to favor cooperation when starting from any configuration containing any number of cooperators. This formula elucidates two important features: (i) the takeover of cooperation can be enhanced by the strategic placement of cooperators and (ii) adding more cooperators to a configuration can sometimes suppress the evolution of cooperation. These findings give a formal account for how selection acts on all transient states that appear in evolutionary trajectories. They also inform the strategic design of initial states in social networks to maximally promote cooperation. We also derive general results that characterize the interaction of any two strategies, not only cooperation and defection.

Figure 1. Calculation of the local frequencies of Eqs (3),(4),(5),(6), f₁(x, ξ), f₀(x, ξ), and f₁₀(x, ξ), where ξ is the configuration consisting of a defector at vertex y and cooperators elsewhere.

Among the three neighbors of the player at vertex x, two are cooperators (u and v) and one is a defector (y); thus, f₁(x, ξ) = 2/3 and f₀(x, ξ) = 1/3. Furthermore, of the nine paths of length two that begin at vertex x, only two (x → u → y and x → v → y) consist of a cooperator followed by a defector, and it follows that f₁₀(x, ξ) = 2/9.

Figure 2. Two graphs showing configurations of cooperators (blue) and defectors (red).

(a) Cooperation can be favored for the initial condition that is shown since the critical benefit-to-cost ratio is 42 and, in particular, finite. However, the fixation of cooperation cannot be favored for any initial configuration with a single cooperator on this graph. (b) Cooperation cannot be favored for the initial condition that is shown since the critical benefit-to-cost ratio is infinite. However, any initial configuration with a single cooperator has a critical benefit-to-cost ratio of 28. Therefore, the addition of cooperators to the initial configuration can either favor cooperation, (a), or suppress it, (b). The critical benefit-to-cost ratio can also be expressed in terms of a well-known quantity known as a “structure coefficient”, σ, which satisfies (b/c)^* = (σ + 1)/(σ − 1).

Figure 3. Configurations of cooperators and defectors on the Frucht graph, a 3-regular graph with 12 vertices and no non-trivial symmetries; see ref. .

Panels (a–f) show the effects on the critical benefit-to-cost ratio of adding additional cooperators to the initial state. Panel (e) shows the global minimum of , which is achieved by just (e) and its conjugate; adding additional cooperators to the configuration in (e) only increases . The configuration of (e) is ‘optimal’ for cooperation in the sense that if selection increases the fixation probability of cooperators in some state, then it does so in state (e) as well. Relative to all possible initial states, selection can increase the fixation probability of cooperators in (e) under the smallest b/c ratio. Panels (g–i) show that when cooperators are added in a different order (starting with just a single cooperator), the critical benefit-to-cost ratio can actually be increased. Each of these three configurations has isolated cooperators, and (i) gives the global maximum of , which is achieved by just (i) and its conjugate. Since N₀ = 3, (i) is a maximal isolated configuration. The initial state in (i) is least conducive to cooperation in the sense that, relative to all other initial configurations, (i) requires the largest b/c ratio for selection to increase the fixation probability of cooperators. If selection increases this fixation probability when starting from state (i), then it does so when starting from any other mixed initial configuration.

Figure 4. Cooperator-defector configurations on a 4-regular graph with 8 vertices and diameter 2.

Starting from one cooperator in (a), a single cooperator is added in each subsequent panel. Although cooperation can never be favored by selection when starting from a state with a single mutant (a) or a single defector (g), it can be favored in the other states, (b–f), since the critical benefit-to-cost ratios are all finite in those panels.

Figure 5. The effects of adding cooperators to the initial condition on a cycle with 10 vertices.

In panels (a–i), cooperators are added sequentially, with each new cooperator neighboring a cooperator in the previous configuration. These panels clearly demonstrate that a configuration and its conjugate have the same critical ratio and structure coefficient. Panels (j–l) show that when cooperators are added in a different order, the critical ratios can increase rather than decrease. The configurations of (j–l) each have isolated cooperators.