Games on Networks
How population structure shapes the evolution of cooperation and competition
A Brief History
Why Population Structure Matters
The well-mixed population assumption—that every individual interacts with every other with equal probability—is a mathematical convenience that rarely describes real biological systems. In nature, interactions are constrained by space, social networks, or contact networks. Bacteria compete with neighbours in biofilms; animals interact within territories; diseases spread through contact networks; genes correlate through kinship. Understanding how who interacts with whom shapes evolutionary dynamics is essential for predicting the evolution of cooperation, virulence, investment patterns, and strategy frequencies.
A landmark discovery showed that spatial structure can fundamentally alter evolutionary outcomes. Nowak and May (1992) investigated the Prisoner's Dilemma on a two-dimensional lattice: individuals occupy grid positions and play with spatial neighbours only. They found that cooperation can evolve and persist indefinitely on spatial grids, even when it dies out in a well-mixed population. The mechanism: cooperators form clusters, and clusters are robust because their internal cooperation yields high fitness, while defectors at the boundaries gain little by exploiting cooperators.
Nowak & May (1992), Nature 359, 826–829: spatial structure allows cooperators to cluster, creating islands of mutualism that resist invasion by defectors. In a well-mixed population, cooperation is typically suppressed; on lattices, cooperation can be an ESS.
This observation sparked decades of research into structured populations. The general principle is straightforward: kin selection, reciprocal altruism, and indirect reciprocity all operate more powerfully when interactions are local rather than global. Population structure is not a nuisance to be averaged away; it is a fundamental force shaping evolution.
Evolutionary Graph Theory
To formalize the role of population structure, Lieberman, Hauert, and Nowak (2005) developed evolutionary graph theory, a unified framework for analyzing evolution on arbitrary structures.
Graphs and Moran Processes
In this framework:
Vertices represent individuals in the population.
Edges represent reproductive interactions: an edge from $i$ to $j$ means that $i$ can replace $j$ upon reproduction.
The graph structure encodes the population topology.
Evolution proceeds via a Moran process on graphs:
1. Select a birth vertex with probability proportional to fitness.
2. The newborn replaces a death vertex chosen uniformly at random from the birth vertex's neighbours (outgoing edges).
3. Repeat until fixation or mutation.
A key quantity in finite populations is the fixation probability $\rho_r$ of a mutant with relative fitness advantage $r$ (fitness $r$ vs. fitness 1). In a well-mixed population of size $N$:
$$ \rho_r^{\text{well-mixed}} = \frac{1 - r^{-1}}{1 - r^{-N}} \approx \frac{1}{N} \text{ for } r \text{ close to } 1 $$On a graph, fixation probability depends on the graph structure. A central result is:
On an isothermal graph (a graph where all vertices have the same "weighted temperature"), the fixation probability of a mutant equals that of a well-mixed population. Temperature is defined in terms of the degree and structure; isothermal graphs include regular graphs (all vertices same degree) under birth-death updating.
For other graph structures, fixation probabilities differ from the well-mixed case, allowing selection to be either amplified or suppressed.
Lieberman, Hauert & Nowak (2005), Nature 433, 312–316.
Amplifiers and Suppressors of Selection
Different graphs exert different selective pressures on an invading mutant.
Star Graph: an Amplifier of Selection
In a star graph with $N$ vertices: one central "hub" is connected to $N-1$ "leaf" nodes, and each leaf is connected only to the hub. Under birth-death updating, every replacement event must pass through the hub—it is the sole bottleneck. A beneficial mutant at the hub spreads efficiently to the leaves, while a beneficial mutant at a leaf must first capture the hub before it can spread further. This bottleneck amplifies fitness differences: beneficial mutants fix more often than in a well-mixed population, and deleterious mutants fix less often. Analysis shows:
$$ \rho_r^{\text{star}} \approx 1 - \frac{1}{r^2} \text{ for large } N $$For a mutant with $r = 1.1$, this gives $\rho_r^{\text{star}} \approx 0.173$ (star) vs. $\rho_r^{\text{well-mixed}} \approx 0.09$ (well-mixed): selection is amplified by the star topology.
Complete Graph: Recovery of Well-Mixed Limit
A complete graph $K_N$ (every vertex connected to every other) recovers the well-mixed result, since the graph has no bottlenecks and is highly symmetric.
Suppressors of Selection
Some structures suppress selection, reducing fixation probability below the well-mixed value. Long chains or trees with poorly-connected components can isolate mutants, making spread difficult. Suppressors are important for stability: they reduce the invasion rate of deleterious mutations.
The Circulation Theorem
A unifying principle connects graph structure to fixation: the circulation theorem relates fixation probabilities to the symmetry and connectivity of the graph. Intuitively, graphs that favour the spread of a type (many outgoing edges, high fitness of neighbours) amplify selection; graphs that trap or isolate types suppress selection.
Evolutionary Games on Graphs
Combining graph structure with frequency-dependent games yields evolutionary games on graphs. Individuals occupy vertices, play games with neighbours, and the outcome affects reproduction.
The b/c > k Rule
A major result by Ohtsuki, Hauert, Lieberman, and Nowak (2006) gives a simple condition for the evolution of cooperation on graphs:
In the Prisoner's Dilemma on a graph where cooperation costs $c$ and benefits the partner by $b$, cooperation evolves if:
$$\frac{b}{c} > k$$
where $k$ is the average number of neighbours per individual (average degree).
Intuition: on a regular graph of degree $k$, each individual competes for reproduction with $k$ neighbours. A cooperator pays cost $c$ once but disperses benefit $b$ among $k$ neighbours. Selection favours cooperation when the per-neighbour benefit $b/k$ outweighs the cost, i.e. $b/c > k$. Sparser networks (smaller $k$) therefore make cooperation easier to sustain.
This rule is robust across graph types and provides a clear, testable prediction: denser networks (larger $k$) require stronger benefits relative to costs to sustain cooperation. Sparse networks favour cooperation.
Ohtsuki, Hauert, Lieberman & Nowak (2006), Nature 441, 502–505.
Related work by Traulsen, Claussen, and Hauert (2005) studied how stochastic evolutionary dynamics in finite populations connect to deterministic replicator equations. They showed that the coevolutionary dynamics of finite populations on structured graphs converge to the replicator equation in appropriate limits, providing a bridge between the microscopic (graph-based) and macroscopic (ODE-based) descriptions of evolution.
Explore: Evolution on a Graph
Update Rules
The dynamics of evolution on graphs depend on how birth and death are coupled. Different update rules produce different dynamics and can lead to qualitatively different outcomes.
Birth-Death (BD): Fitness-Proportional Birth
A vertex is chosen for birth proportional to fitness, and the newborn replaces a random neighbour:
- Select vertex $i$ with probability proportional to fitness $f_i$.
- Replace a uniformly random neighbour of $i$.
This rule amplifies the effect of fitness differences, since the fittest individuals reproduce more often.
Death-Birth (DB): Random Death, Fitness-Proportional Replacement
- Select a vertex $i$ uniformly at random for death.
- A neighbour $j$ of $i$ (chosen proportional to fitness) reproduces and fills the vacancy.
This rule can suppress selection compared to birth-death, since death is unbiased but replacement is fitness-biased.
Imitation (IM): Copying Without Replacement
A vertex $i$ is chosen uniformly at random and then adopts the strategy of a neighbour $j$ with probability proportional to $j$'s fitness:
- Select vertex $i$ uniformly at random.
- $i$ copies the strategy of a neighbour $j$ with probability $\propto f_j$.
This is applicable in contexts where strategies spread by imitation rather than reproduction (cultural evolution, learning).
Ohtsuki & Nowak (2006) showed that the choice of update rule affects evolutionary outcomes even under weak selection. Under death-birth (DB) updating, cooperation is favoured on regular graphs when $b/c > k$—this is the setting in which the celebrated rule was derived. Under birth-death (BD) updating, the condition is more stringent because the fitness-weighted birth step creates stronger local competition that works against cooperators. Under imitation updating, the threshold differs again. These differences arise because the update rule determines how local competition and dispersal interact with population structure.
Ohtsuki & Nowak (2006), "The replicator equation on graphs", J. Theor. Biol.
Fixation Probabilities on Structured Populations
For finite structured populations, the fixation probability can be computed or approximated. Under weak selection (fitness differences small), analytical results are available.
Regular Graphs Under Weak Selection
For a regular graph (all vertices degree $k$) and weak selection ($s$ small, relative fitness $1 + s$), the fixation probability is:
$$ \rho_{1+s} \approx \frac{1 + s \cdot \sigma(G)}{N} $$where $\sigma(G)$ is a graph-dependent coefficient related to the number of edges and structure. For a complete graph, $\sigma = 1$. For a star, $\sigma > 1$ (amplification). For a long chain, $\sigma < 1$ (suppression).
Numerical Computation
For arbitrary graphs and finite selection strength, the most reliable approach is numerical simulation of the Moran process. By running many replicates and counting fixations, one can estimate $\rho_r$ to arbitrary accuracy.
Recent Work: Meta-Populations and Complex Networks
Modern extensions of this theory include fixation on heterogeneous networks (scale-free networks, small-world networks) and meta-population models with migration. A comprehensive recent treatment is:
Yagoobi and Traulsen (2021) showed that fixation probabilities in meta-populations (connected communities with migration) depend sensitively on the connectivity between communities and the balance of local vs. global competition.
Yagoobi, S. & Traulsen, A. (2021). Fixation probabilities in network structured meta-populations. Scientific Reports, 11, 17979.
Exercises
Conceptual Questions
- Explain how network structure affects the evolution of cooperation compared to well-mixed populations. Why do "assortative" interactions (like with like) promote cooperation?
- What is the difference between a random regular network and a scale-free network? How does degree distribution affect evolutionary dynamics?
- Describe Ohtsuki's "simple rule" for cooperation on graphs. Why does the average degree $k$ appear as a threshold? Explain the condition $b/c > k$ and why sparser networks favour cooperation.
- How does network reciprocity differ from the spatial games discussed in earlier chapters? Can indirect reciprocity and network structure work together to maintain cooperation?
- In meta-populations (subdivided populations with migration), how does the level of migration between patches affect the evolution of local cooperation and global polymorphisms?
Computer Problems
- Cooperation on Different Network Topologies. Implement the Prisoner's Dilemma on: (a) random regular (each node has degree $k$), (b) small-world (Watts-Strogatz), and (c) scale-free (Barabási-Albert) networks with $N = 100$ nodes. Use Moran process: play with neighbours, reproduce proportional to fitness. Show how network structure affects fixation probability of cooperators versus defectors.
- Ohtsuki's Rule Verification. Implement the Prisoner's Dilemma (benefit $b$, cost $c$) on a regular network of degree $k$ and measure the fixation probability $\rho$ of cooperators as a function of $b/c$. Verify that cooperation is favoured when $b/c > k$ (Ohtsuki's rule). Show the transition from defection dominance to cooperation dominance as the benefit-to-cost ratio increases past the critical threshold.
- Clustering Coefficient and Cooperation. Generate networks with the same degree distribution but varying clustering coefficient (e.g., random, lattice, small-world). Simulate games and show how clustering affects cooperation levels. Explain why tight clustering can both help (assortment) and hurt (mutual punishment) cooperation.
- Meta-Population Dynamics with Migration. Implement multiple patches (subpopulations), each with independent dynamics, connected by migration. Use Moran process within patches and allow occasional movement between patches (migration probability $m$). Show how migration rate affects global cooperation frequency and whether local polymorphisms are maintained.
- Adaptive Network Rewiring. Implement a network where individuals update not only strategy but also network connections. Allow breaking ties to defectors and forming ties to cooperators. Use threshold-based or preferential rules. Show how adaptation creates community structure (clusters of cooperators) and stabilises cooperation.
References
- Yagoobi, S. & Traulsen, A. (2021). Fixation probabilities in network structured meta-populations. Scientific Reports, 11, 17979.
- Lieberman, E., Hauert, C. & Nowak, M. A. (2005). Evolutionary dynamics on graphs. Nature, 433, 312–316.
- Nowak, M. A. & May, R. M. (1992). Evolutionary games and spatial chaos. Nature, 359, 826–829.
- Ohtsuki, H., Hauert, C., Lieberman, E. & Nowak, M. A. (2006). A simple rule for the evolution of cooperation on graphs and social networks. Nature, 441, 502–505.
- Ohtsuki, H. & Nowak, M. A. (2006). The replicator equation on graphs. Journal of Theoretical Biology, 243, 86–97.
- Santos, F. C. & Pacheco, J. M. (2005). Scale-free networks provide a unifying framework for the emergence of cooperation. Phys. Rev. Lett., 95, 098104.
- Traulsen, A., Claussen, J. C. & Hauert, C. (2005). Coevolutionary dynamics: from finite to infinite populations. Phys. Rev. Lett., 95, 238701.
- Allen, B., Lippner, G., Chen, Y.-T., Fotouhi, B., Momeni, N., Yau, S.-T. & Nowak, M. A. (2017). Evolutionary dynamics on any population structure. Nature, 544, 227–230.