Generalizing the $b/c > k$ network-reciprocity rule for the evolution of cooperation on graphs beyond weak selection and large population size

On a graph whose individuals each have $k$ neighbors, death–birth evolutionary updating favors unconditional cooperators over defectors in the donation game if the benefit-to-cost ratio satisfies $b/c > k$ (Ohtsuki, Hauert, Lieberman and Nowak, Nature 2006) — but the rule is derived only in the weak-selection limit ($w \ll 1$) and for population size $N$ much larger than $k$. The paper itself flagged the open regime question (strong selection, $N$ not large compared to $k$), together with weighted edges, conditional reciprocity strategies, better predictors for high-degree-variance networks, and empirical tests. That agenda has since been substantially executed at weak selection: dynamics on any finite heterogeneous population structure were solved via coalescence times (Allen et al. 2017), the isothermal weighted-graph rule $b/c >$ effective degree was derived (Allen, Lippner and Nowak 2019), degree-mean-and-variance replicator approximations exist (Li et al. 2025), and the envisaged human experiment — varying $b/c$ and $k$ on fixed networks — confirmed the rule (Rand et al. 2014). Exact results beyond weak selection exist only for the cycle, weak-selection rankings provably need not survive higher selection intensity, and fixation questions at arbitrary intensity on general input graphs are already known to be computationally intractable under birth–death-type conventions (Ibsen-Jensen, Chatterjee and Nowak 2015). The surviving open core: a criterion for when network structure favors cooperation under arbitrary selection intensity, without the $N \gg k$ assumption, on general heterogeneous and weighted graphs.

Background

Evolutionary game theory studies how strategic behavior changes when reproductive success is driven by payoffs. Its central puzzle is cooperation: a cooperator pays a cost $c$ so that another individual receives a benefit $b$, while a defector pays nothing and gives nothing. In this donation-game form of the Prisoner's Dilemma, defectors always out-earn cooperators, so in a well-mixed population — where everyone interacts with everyone — natural selection eliminates cooperation. Network reciprocity is one of the classic mechanisms that can rescue cooperation: individuals occupy the vertices of a graph (a network whose edges specify both who plays with whom and who competes with whom for reproduction), so cooperators can cluster and mostly help other cooperators. Ohtsuki, Hauert, Lieberman and Nowak (2006) analyzed this setting for the simplest strategy pair, unconditional cooperators versus unconditional defectors, on $k$-regular graphs where every individual has exactly $k$ neighbors. Under death–birth updating — each time step a randomly chosen individual dies, and its neighbors compete in proportion to their fitness to colonize the empty site — with success measured by the fixation probability $\rho_C$ (the chance that a single cooperator placed at a random vertex eventually takes over the population; $1/N$ is the neutral-drift benchmark), they derived the rule that selection favors cooperation if $b/c > k$: cooperation is favored when the benefit-to-cost ratio exceeds the average number of neighbors. For imitation updating (a randomly chosen individual copies the strategy of one of its neighbors, with fitter neighbors more likely to be chosen) the rule becomes $b/c > k + 2$, and for birth–death updating (an individual is chosen to reproduce in proportion to fitness, and its offspring replaces a random neighbor) cooperation is never favored. The derivation uses pair approximation (a closure scheme tracking only the frequencies of neighboring strategy pairs) plus a diffusion approximation (a continuum approximation of the discrete stochastic process), and is valid in two limits: weak selection — the selection intensity $w \in [0,1]$, which interpolates fitness between a constant baseline ($w=0$, neutral drift) and pure game payoff ($w=1$, strong selection), satisfies $w \ll 1$ — and population size $N$ much larger than the degree $k$. The rule's resemblance to Hamilton's rule $b/c > 1/r$ from kin selection (Hamilton 1964) made it a centerpiece of cooperation theory. Much of the paper's own forward agenda has since been executed at weak selection. Companion papers derived the replicator-equation analogue (Ohtsuki and Nowak 2006a), exact conditions on cycles (Ohtsuki and Nowak 2006b), separated interaction from replacement graphs (Ohtsuki, Nowak and Pacheco 2007), generalized to arbitrary two-strategy games via the structure coefficient $\sigma$ — a single number depending only on population structure and update rule, such that one strategy is favored over the other exactly when $\sigma a_{11} + a_{12} > a_{21} + \sigma a_{22}$ in the game's payoff matrix $(a_{ij})$ (Tarnita, Ohtsuki, Antal, Fu and Nowak 2009) — and gave evolutionary-stability conditions on regular graphs (Ohtsuki and Nowak 2008). Chen (2013) proved rigorously that the death–birth rule $b/c > k$ and the imitation rule $b/c > k+2$ are valid and sharp on regular graphs. Allen, Lippner, Chen, Fotouhi, Momeni, Yau and Nowak (2017) solved weak-selection dynamics on any population structure — arbitrary, finite, degree-heterogeneous graphs — in terms of coalescence times of random walks (the expected time for random walks traced backward from two individuals through the population's ancestry to reach a common ancestor); for arbitrary selection intensity they cite the proved complexity theorem of Ibsen-Jensen, Chatterjee and Nowak (2015) — deciding whether an invader fixes, and computing its fixation probability, are NP-hard/#P-hard for evolutionary games on general input graphs under birth–death-type updating with linear or exponential fecundity maps — conventions different from the death–birth process with fitness $1 - w + w\pi$, so this general-graph hardness neither covers the pinned process nor precludes compact criteria on restricted classes such as nearly regular graphs. For weighted edges specifically, Allen, Lippner and Nowak (2019) showed that on isothermal weighted graphs (equal total edge weight at every vertex) the rule generalizes cleanly: cooperation is favored if $b/c$ exceeds the graph's effective degree, a weighted analogue of $k$. Li, Wang, Li and Zhang (2025) derived replicator approximations whose transformed payoff matrix depends on the mean and variance of the degree distribution, addressing the source's observation that the average-degree rule deteriorates on high-degree-variance (scale-free) networks. In experiments, Rand, Nowak, Fowler and Christakis (2014) varied $b/c$ and $k$ on fixed human networks and found cooperation stable exactly when $b/c > k$. What remains almost untouched is the original regime question: no compact criterion is known for when network structure favors cooperation under strong selection ($w$ not small) or when $N$ is not large compared to $k$. Exact strong-selection results exist only for the cycle (Altrock, Traulsen and Nowak 2017), the island-model analysis of Mullon and Lehmann (2014) — a population split into groups connected by migration, a different structure class — shows weak selection gives the ideal condition there, and Wu, García, Hauert and Traulsen (2013) proved that rankings derived under weak selection need not extrapolate to higher intensity in general evolutionary games — so the strong-selection answer is not simply 'the same rule'.

Problem Statement

The problem is the regime question Ohtsuki, Hauert, Lieberman and Nowak (2006) left open in their own terms: how does the criterion for the evolution of cooperation on graphs generalize beyond the weak-selection, large-population approximation in which $b/c > k$ was derived? In the standard setting — unconditional cooperators and defectors playing the donation game on a finite graph $G$ with $N$ vertices, fitness $= 1 - w + w \cdot \text{payoff}$, success benchmarked by the fixation probability $\rho_C$ of a single randomly placed cooperator against $1/N$, with death–birth updating (and imitation updating for the $b/c > k+2$ rule) — determine the criterion for selection to favor cooperation ($\rho_C > 1/N$) at arbitrary selection intensity $w \in (0, 1]$ (strong selection included) and without assuming $N \gg k$, on the parameter range where the pinned process is well defined: since a cooperator whose neighbors are all defectors earns payoff $-kc$, fitness-proportional competition requires $1 - w + w\pi > 0$ for every attainable payoff $\pi$ (the binding case being a vertex of maximal degree whose neighbors are all defectors; on $k$-regular graphs, $w(1 + kc) < 1$), and results at intensities where this bound fails must state the convention used to keep fitness positive (for example, an exponential fitness map $e^{w\pi}$) and apply it consistently. The components jointly answer one question — when does population structure promote cooperation once the weak-selection closure is dropped. Each component has independent standing: resolving any one of them leaves the others open. (1) on $k$-regular graphs with death–birth updating, establish, for each such graph $G$, the exact condition on $(b, c, k, w, N, G)$ under which $\rho_C > 1/N$ in closed form — that is, determine whether, and for which classes of $k$-regular graphs, it reduces to a compact benefit-to-cost inequality depending only on $(b, c, k, w, N)$ and generalizing $b/c > k$ (analogously $b/c > k+2$ for imitation updating), or whether graph-specific quantities genuinely enter; merely restating the defining inequality $\rho_C > 1/N$ is not an answer; (2) give the corresponding condition or finite-size correction in the regime where $N$ is not large compared to $k$, where the diffusion approximation fails; (3) extend the criterion beyond regular graphs to degree-heterogeneous graphs (where the average-degree rule deteriorates with degree variance) and to weighted graphs outside the isothermal class, generalizing the effective-degree rule of Allen, Lippner and Nowak (2019), at non-weak selection.

References

1. 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(7092), 502–505. DOI 10.1038/nature04605. https://doi.org/10.1038/nature04605
2. Ohtsuki, H., Nowak, M. A. (2006). The replicator equation on graphs. Journal of Theoretical Biology 243(1), 86–97. DOI 10.1016/j.jtbi.2006.06.004. https://doi.org/10.1016/j.jtbi.2006.06.004
3. Ohtsuki, H., Nowak, M. A. (2006). Evolutionary games on cycles. Proceedings of the Royal Society B 273(1598), 2249–2256. DOI 10.1098/rspb.2006.3576. https://doi.org/10.1098/rspb.2006.3576
4. Ohtsuki, H., Nowak, M. A., Pacheco, J. M. (2007). Breaking the symmetry between interaction and replacement in evolutionary dynamics on graphs. Physical Review Letters 98(10), 108106. DOI 10.1103/PhysRevLett.98.108106. https://doi.org/10.1103/PhysRevLett.98.108106
5. Ohtsuki, H., Nowak, M. A. (2007). Direct reciprocity on graphs. Journal of Theoretical Biology 247(3), 462–470. DOI 10.1016/j.jtbi.2007.03.018. https://doi.org/10.1016/j.jtbi.2007.03.018
6. Ohtsuki, H., Nowak, M. A. (2008). Evolutionary stability on graphs. Journal of Theoretical Biology 251(4), 698–707. DOI 10.1016/j.jtbi.2008.01.005. https://doi.org/10.1016/j.jtbi.2008.01.005
7. Tarnita, C. E., Ohtsuki, H., Antal, T., Fu, F., Nowak, M. A. (2009). Strategy selection in structured populations. Journal of Theoretical Biology 259(3), 570–581. DOI 10.1016/j.jtbi.2009.03.035. https://doi.org/10.1016/j.jtbi.2009.03.035
8. Chen, Y.-T. (2013). Sharp benefit-to-cost rules for the evolution of cooperation on regular graphs. Annals of Applied Probability 23(2), 637–664. DOI 10.1214/12-AAP849. https://doi.org/10.1214/12-AAP849
9. 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(7649), 227–230. DOI 10.1038/nature21723. https://doi.org/10.1038/nature21723
10. Ibsen-Jensen, R., Chatterjee, K., Nowak, M. A. (2015). Computational complexity of ecological and evolutionary spatial dynamics. Proceedings of the National Academy of Sciences USA 112(51), 15636–15641. DOI 10.1073/pnas.1511366112. https://doi.org/10.1073/pnas.1511366112
11. Allen, B., Lippner, G., Nowak, M. A. (2019). Evolutionary games on isothermal graphs. Nature Communications 10, 5107. DOI 10.1038/s41467-019-13006-7. https://doi.org/10.1038/s41467-019-13006-7
12. Wang, C., Su, Q. (2026). Public goods games on any population structure. Science Advances 12(10), eaeb1263. DOI 10.1126/sciadv.aeb1263. https://doi.org/10.1126/sciadv.aeb1263
13. Li, J., Wang, X., Li, C., Zhang, B. (2025). Replicator dynamics on heterogeneous networks. Journal of Mathematical Biology 90(2), 16. DOI 10.1007/s00285-024-02177-7. https://doi.org/10.1007/s00285-024-02177-7
14. Altrock, P. M., Traulsen, A., Nowak, M. A. (2017). Evolutionary games on cycles with strong selection. Physical Review E 95(2), 022407. DOI 10.1103/PhysRevE.95.022407. https://doi.org/10.1103/PhysRevE.95.022407
15. Mullon, C., Lehmann, L. (2014). The robustness of the weak selection approximation for the evolution of altruism against strong selection. Journal of Evolutionary Biology 27(10), 2272–2282. DOI 10.1111/jeb.12462. https://doi.org/10.1111/jeb.12462
16. Wu, B., García, J., Hauert, C., Traulsen, A. (2013). Extrapolating weak selection in evolutionary games. PLoS Computational Biology 9(12), e1003381. DOI 10.1371/journal.pcbi.1003381. https://doi.org/10.1371/journal.pcbi.1003381
17. Wang, Z., Durrett, R. (2018). Extrapolating weak selection in evolutionary games. Journal of Mathematical Biology 78(1–2), 135–154. DOI 10.1007/s00285-018-1270-6. https://doi.org/10.1007/s00285-018-1270-6
18. van Veelen, M., García, J., Rand, D. G., Nowak, M. A. (2012). Direct reciprocity in structured populations. Proceedings of the National Academy of Sciences USA 109(25), 9929–9934. DOI 10.1073/pnas.1206694109. https://doi.org/10.1073/pnas.1206694109
19. Murase, Y., Hilbe, C., Baek, S. K. (2022). Evolution of direct reciprocity in group-structured populations. Scientific Reports 12, 18645. DOI 10.1038/s41598-022-23467-4. https://doi.org/10.1038/s41598-022-23467-4
20. Wei, H., Zhang, J., Zhang, C. (2024). Evolutionary dynamics of direct and indirect reciprocity on networked populations. Swarm and Evolutionary Computation 88, 101611. DOI 10.1016/j.swevo.2024.101611. https://doi.org/10.1016/j.swevo.2024.101611
21. Cao, L., Ohtsuki, H., Wang, B., Aihara, K. (2011). Evolution of cooperation on adaptively weighted networks. Journal of Theoretical Biology 272(1), 8–15. DOI 10.1016/j.jtbi.2010.12.008. https://doi.org/10.1016/j.jtbi.2010.12.008
22. Bhaumik, J., Masuda, N. (2024). Constant-selection evolutionary dynamics on weighted networks. Proceedings of the Royal Society A 480(2296), 20240223. DOI 10.1098/rspa.2024.0223. https://doi.org/10.1098/rspa.2024.0223
23. Gracia-Lázaro, C., Ferrer, A., Ruiz, G., Tarancón, A., Cuesta, J. A., Sánchez, Á., Moreno, Y. (2012). Heterogeneous networks do not promote cooperation when humans play a Prisoner's Dilemma. Proceedings of the National Academy of Sciences USA 109(32), 12922–12926. DOI 10.1073/pnas.1206681109. https://doi.org/10.1073/pnas.1206681109
24. Suri, S., Watts, D. J. (2011). Cooperation and contagion in web-based, networked public goods experiments. PLoS ONE 6(3), e16836. DOI 10.1371/journal.pone.0016836. https://doi.org/10.1371/journal.pone.0016836
25. Rand, D. G., Arbesman, S., Christakis, N. A. (2011). Dynamic social networks promote cooperation in experiments with humans. Proceedings of the National Academy of Sciences USA 108(48), 19193–19198. DOI 10.1073/pnas.1108243108. https://doi.org/10.1073/pnas.1108243108
26. Rand, D. G., Nowak, M. A., Fowler, J. H., Christakis, N. A. (2014). Static network structure can stabilize human cooperation. Proceedings of the National Academy of Sciences USA 111(48), 17093–17098. DOI 10.1073/pnas.1400406111. https://doi.org/10.1073/pnas.1400406111
27. Boots, M., Childs, D., Crossmore, J., Tidbury, H., Rudolf, V. (2021). Experimental evidence that local interactions select against selfish behaviour. Ecology Letters 24(6), 1187–1192. DOI 10.1111/ele.13734. https://doi.org/10.1111/ele.13734
28. Gokcekus, S., Cole, E. F., Sheldon, B. C., Firth, J. A. (2021). Exploring the causes and consequences of cooperative behaviour in wild animal populations using a social network approach. Biological Reviews 96(5), 2355–2372. DOI 10.1111/brv.12757. https://doi.org/10.1111/brv.12757
29. Hamilton, W. D. (1964). The genetical evolution of social behaviour. I. Journal of Theoretical Biology 7(1), 1–16. DOI 10.1016/0022-5193(64)90038-4. https://doi.org/10.1016/0022-5193(64)90038-4