Evolution of cooperation in stochastic games
Abstract
Social dilemmas occur when incentives for individuals are misaligned with group interests 1-7. According to the 'tragedy of the commons', these misalignments can lead to overexploitation and collapse of public resources. The resulting behaviours can be analysed with the tools of game theory 8. The theory of direct reciprocity 9-15 suggests that repeated interactions can alleviate such dilemmas, but previous work has assumed that the public resource remains constant over time. Here we introduce the idea that the public resource is instead changeable and depends on the strategic choices of individuals. An intuitive scenario is that cooperation increases the public resource, whereas defection decreases it. Thus, cooperation allows the possibility of playing a more valuable game with higher payoffs, whereas defection leads to a less valuable game. We analyse this idea using the theory of stochastic games 16-19 and evolutionary game theory. We find that the dependence of the public resource on previous interactions can greatly enhance the propensity for cooperation. For these results, the interaction between reciprocity and payoff feedback is crucial: neither repeated interactions in a constant environment nor single interactions in a changing environment yield similar cooperation rates. Our framework shows which feedbacks between exploitation and environment-either naturally occurring or designed-help to overcome social dilemmas.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Techniques from game theory can be valuable in modeling behavior, e.g., to explore cooperation in the face of a depleting resource.
“In addition to ABMs, techniques from game theory can be valuable in modeling behavior, e.g., to explore cooperation in the face of a depleting resource [344].”
From Tackling climate change with machine learning (2023) · cites this paper as [344]
Cites
Hardin, G. (1968) · Science · doi:10.1126/science.162.3859.1243 · Cited by 25,167 · see citing works
Governing the Commons: The Evolution of Institutions for Collective Action
Ostrom, E. (1990) · doi:10.1017/cbo9780511807763 · Cited by 20,653 · see citing works
Axelrod, R., & Hamilton, W. D. (1981) · Science · doi:10.1126/science.7466396 · Cited by 20,065 · see citing works
Governing the Commons: The Evolution of Institutions for Collective Action
Field, B. C., & Elinor Ostrom, B. (1992) · Land Economics · doi:10.2307/3146384 · Cited by 19,082 · see citing works
The Evolution of Reciprocal Altruism
Trivers, R. L. (1971) · The Quarterly Review of Biology · doi:10.1086/406755 · Cited by 11,010 · see citing works
Nielsen, R. P., & Axelrod, R. (1985) · Academy of Management Review · doi:10.2307/257983 · Cited by 6,517 · see citing works
Five Rules for the Evolution of Cooperation
Nowak, M. A. (2006) · Science · doi:10.1126/science.1133755 · Cited by 5,894 · see citing works
Self-citationEvolutionary Games and Population Dynamics
Hofbauer, J., & Sigmund, K. (1998) · doi:10.1017/cbo9781139173179 · Cited by 5,502 · see citing works
The Handbook of experimental economics
(1995) · Choice Reviews Online · doi:10.5860/choice.33-1645 · Cited by 3,780 · see citing works
Szabó, G., & Fáth, G. (2007) · Physics Reports · doi:10.1016/j.physrep.2007.04.004 · Cited by 2,923 · see citing works
Shapley, L. S. (1953) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.39.10.1095 · Cited by 2,425 · see citing works
A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner's Dilemma game
Nowak, M., & Sigmund, K. (1993) · Nature · doi:10.1038/364056a0 · Cited by 1,797 · see citing works
Self-citationStatistical physics of human cooperation
Perc, M., Jordan, J., Rand, D. G., Wang, Z., Boccaletti, S., & Szolnoki, A. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.05.004 · Cited by 1,601 · see citing works
Evolutionary prisoner's dilemma game on a square lattice
Szabó, G., & Tőke, C. (1997) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.58.69 · Cited by 1,507 · see citing works
Alternating-time temporal logic
Alur, R., Henzinger, T. A., & Kupferman, O. (2002) · Journal of the ACM · doi:10.1145/585265.585270 · Cited by 1,428 · see citing works
Emergence of cooperation and evolutionary stability in finite populations
Nowak, M. A., Sasaki, A., Taylor, C., & Fudenberg, D. (2004) · Nature · doi:10.1038/nature02414 · Cited by 1,403 · see citing works
Self-citationRand, D. G., & Nowak, M. A. (2013) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2013.06.003 · Cited by 1,308 · see citing works
Self-citationStochastic evolutionary game dynamics∗
Foster, D. P., & Young, P. (1990) · Theoretical Population Biology · doi:10.1016/0040-5809(90)90011-j · Cited by 994 · see citing works
Discounted Dynamic Programming
Blackwell, D. (1965) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177700285 · Cited by 953 · see citing works
Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent
Press, W. H., & Dyson, F. J. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1206569109 · Cited by 720 · see citing works
Shapley, L. S. (1953) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.39.10.1953 · Cited by 678 · see citing works
The collective-risk social dilemma and the prevention of simulated dangerous climate change
Milinski, M., Sommerfeld, R. D., Krambeck, H.-J., Reed, F. A., & Marotzke, J. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709546105 · Cited by 613 · see citing works
Stochastic dynamics of invasion and fixation
Traulsen, A., Nowak, M. A., & Pacheco, J. M. (2006) · Physical Review E · doi:10.1103/physreve.74.011909 · Cited by 608 · see citing works
Self-citationSigmund, K. (2010) · doi:10.1515/9781400832255 · Cited by 570 · see citing works
Evolutionary Dynamics and Extensive Form Games
Cressman, R. (2003) · The MIT Press eBooks · doi:10.7551/mitpress/2884.001.0001 · Cited by 564 · see citing works
The leading eight: Social norms that can maintain cooperation by indirect reciprocity
Ohtsuki, H., & Iwasa, Y. (2006) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2005.08.008 · Cited by 491 · see citing works
An oscillating tragedy of the commons in replicator dynamics with game-environment feedback
Weitz, J. S., Eksin, C., Paarporn, K., Brown, S. P., & Ratcliff, W. C. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1604096113 · Cited by 353 · see citing works
Heads-up limit hold’em poker is solved
Bowling, M., BURCH, N. R., Johanson, M., & Tammelin, O. (2015) · Science · doi:10.1126/science.1259433 · Cited by 349 · see citing works
Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma
Neyman, A. (1985) · Economics Letters · doi:10.1016/0165-1765(85)90026-6 · Cited by 346 · see citing works
Imitation processes with small mutations
Fudenberg, D., & Imhof, L. A. (2006) · Journal of Economic Theory · doi:10.1016/j.jet.2005.04.006 · Cited by 335 · see citing works
Mertens, J. F., & Neyman, A. (1981) · International Journal of Game Theory · doi:10.1007/bf01769259 · Cited by 324 · see citing works
Evolutionary games and population dynamics: maintenance of cooperation in public goods games
Hauert, C., Holmes, M., & Doebeli, M. (2006) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.2006.3600 · Cited by 314 · see citing works
Punish or perish? Retaliation and collaboration among humans
Sigmund, K. (2007) · Trends in Ecology & Evolution · doi:10.1016/j.tree.2007.06.012 · Cited by 310 · see citing works
Stochastic Games and Applications
Neyman, A., & Sorin, S. (2003) · Springer eBooks · doi:10.1007/978-94-010-0189-2 · Cited by 302 · see citing works
From extortion to generosity, evolution in the Iterated Prisoner’s Dilemma
Stewart, A. J., & Plotkin, J. B. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1306246110 · Cited by 297 · see citing works
Evolution of extortion in Iterated Prisoner’s Dilemma games
Hilbe, C., Nowak, M. A., & Sigmund, K. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1214834110 · Cited by 296 · see citing works
Self-citationThe evolution of stochastic strategies in the Prisoner's Dilemma
Nowak, M. A., & Sigmund, K. (1990) · Acta Applicandae Mathematicae · doi:10.1007/bf00049570 · Cited by 285 · see citing works
Self-citationDevelopment of cooperative relationships through increasing investment
Roberts, G., & Sherratt, T. N. (1998) · Nature · doi:10.1038/28160 · Cited by 283 · see citing works
Evolutionary games in the multiverse
Gokhale, C. S., & Traulsen, A. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0912214107 · Cited by 281 · see citing works
A Folk Theorem for Stochastic Games
Dutta, P. K. (1995) · Journal of Economic Theory · doi:10.1006/jeth.1995.1030 · Cited by 249 · see citing works
Aumann, R. J. (1981) · Medical Entomology and Zoology · Cited by 244 · see citing works
The Asymptotic Theory of Stochastic Games
Bewley, T. F., & Kohlberg, E. (1976) · Mathematics of Operations Research · doi:10.1287/moor.1.3.197 · Cited by 238 · see citing works
9. STOCHASTIC GAMES WITH ZERO STOP PROBABILITIES
Gillette, D. (1958) · Princeton University Press eBooks · doi:10.1515/9781400882151-011 · Cited by 208 · see citing works
Cooperation and control in multiplayer social dilemmas
Hilbe, C., Wu, B., Traulsen, A., & Nowak, M. A. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1407887111 · Cited by 198 · see citing works
Self-citationPartners and rivals in direct reciprocity
Hilbe, C., Chatterjee, K., & Nowak, M. A. (2018) · Nature Human Behaviour · doi:10.1038/s41562-018-0320-9 · Cited by 187 · see citing works
Self-citationKillingback, T., & Doebeli, M. (2002) · The American Naturalist · doi:10.1086/342070 · Cited by 170 · see citing works
Collapse of cooperation in evolving games
Stewart, A. J., & Plotkin, J. B. (2014) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1408618111 · Cited by 167 · see citing works
Emergence of cooperation in public goods games
Kurokawa, S., & 井原, 泰. (2009) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.2008.1546 · Cited by 164 · see citing works
Hauert, C., & Schuster, H. G. (1997) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.1997.0073 · Cited by 160 · see citing works
Memory- n strategies of direct reciprocity
Hilbe, C., Martínez-Vaquero, L. A., Chatterjee, K., & Nowak, M. A. (2017) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1621239114 · Cited by 149 · see citing works
Self-citationThe survival of the conformist: Social pressure and renewable resource management
Tavoni, A., Schlüter, M., & Levin, S. A. (2011) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2011.07.003 · Cited by 147 · see citing works
The evolution of cooperation by social exclusion
Sasaki, T., & Uchida, S. (2012) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.2012.2498 · Cited by 137 · see citing works
The Continuous Prisoner's Dilemma: I. Linear Reactive Strategies
Wahl, L. M., & Nowak, M. A. (1999) · Journal of Theoretical Biology · doi:10.1006/jtbi.1999.0996 · Cited by 136 · see citing works
Self-citationEmergence of Fairness in Repeated Group Interactions
Segbroeck, S. V., Pacheco, J. M., Lenaerts, T., & Santos, F. C. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.158104 · Cited by 117 · see citing works
Two-player stochastic games II: The case of recursive games
Vieille, N. (2000) · Israel Journal of Mathematics · doi:10.1007/bf02810664 · Cited by 114 · see citing works
Phase diagrams for three-strategy evolutionary prisoner’s dilemma games on regular graphs
Szolnoki, A., Perc, M., & Szabó, G. (2009) · Physical Review E · doi:10.1103/physreve.80.056104 · Cited by 112 · see citing works
Stochastic evolutionary dynamics of direct reciprocity
Imhof, L. A., & Nowak, M. A. (2009) · Proceedings of the Royal Society B Biological Sciences · doi:10.1098/rspb.2009.1171 · Cited by 111 · see citing works
Self-citationTwo-player stochastic games I: A reduction
Vieille, N. (2000) · Israel Journal of Mathematics · doi:10.1007/bf02810663 · Cited by 107 · see citing works
How small are small mutation rates?
Wu, B., Gokhale, C. S., Wang, L., & Traulsen, A. (2011) · Journal of Mathematical Biology · doi:10.1007/s00285-011-0430-8 · Cited by 104 · see citing works
Fixation in finite populations evolving in fluctuating environments
Ashcroft, P., Altrock, P. M., & Galla, T. (2014) · Journal of The Royal Society Interface · doi:10.1098/rsif.2014.0663 · Cited by 89 · see citing works
Social Dilemmas: The Psychology of Human Cooperation
Lange, P. A. M. V., Balliet, D. P., Parks, C. D., & van Vugt, M. (2013) · VU Research Portal · Cited by 85 · see citing works
Eco-evolutionary dynamics of social dilemmas
Gokhale, C. S., & Hauert, C. (2016) · Theoretical Population Biology · doi:10.1016/j.tpb.2016.05.005 · Cited by 84 · see citing works
Autocratic strategies for iterated games with arbitrary action spaces
McAvoy, A., & Hauert, C. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1520163113 · Cited by 83 · see citing works
The iterated Prisoner’s Dilemma: good strategies and their dynamics
Akin, E. (2016) · De Gruyter eBooks · doi:10.1515/9783110461510-004 · Cited by 80 · see citing works
Small Groups and Long Memories Promote Cooperation
Stewart, A. J., & Plotkin, J. B. (2016) · Scientific Reports · doi:10.1038/srep26889 · Cited by 78 · see citing works
Repeated games with stationary bounded recall strategies
Lehrer, E. (1988) · Journal of Economic Theory · doi:10.1016/0022-0531(88)90153-6 · Cited by 77 · see citing works
Comparing reactive and memory-one strategies of direct reciprocity
Baek, S. K., Jeong, H.-C., Hilbe, C., & Nowak, M. A. (2016) · Scientific Reports · doi:10.1038/srep25676 · Cited by 65 · see citing works
Self-citationIn and out of equilibrium I: Evolution of strategies in repeated games with discounting
García, J. A., & van Veelen, M. (2015) · Journal of Economic Theory · doi:10.1016/j.jet.2015.11.007 · Cited by 61 · see citing works
Evolution of All-or-None Strategies in Repeated Public Goods Dilemmas
Pinheiro, F. L., de Vasconcelos, V. V. L., Santos, F. C., & Pacheco, J. M. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003945 · Cited by 57 · see citing works
Evolutionary consequences of behavioral diversity
Stewart, A. J., Parsons, T. L., & Plotkin, J. B. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1608990113 · Cited by 53 · see citing works
Reiter, J. G., Hilbe, C., Rand, D. G., Chatterjee, K., & Nowak, M. A. (2018) · Nature Communications · doi:10.1038/s41467-017-02721-8 · Cited by 50 · see citing works
Self-citationFinite automata play the repeated prisioners dilemmaPreprint
Rubinstein, A. (1997) · RePEc: Research Papers in Economics · Cited by 49 · see citing works
Fixation in finite populations evolving in fluctuating environmentsPreprint
Ashcroft, P., & Galla, T. (2014) · Cited by 48 · see citing works
Generosity Pays in the Presence of Direct Reciprocity: A Comprehensive Study of 2×2 Repeated Games
Martínez-Vaquero, L. A., Cuesta, J. A., & Sánchez, Á. (2012) · PLoS ONE · doi:10.1371/journal.pone.0035135 · Cited by 41 · see citing works
The Control of Synchronous Systems
de Alfaro, L., Henzinger, T. A., & Mang, F. Y. C. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44618-4_33 · Cited by 40 · see citing works
Folk theorems with bounded recall under (almost) perfect monitoring
Mailath, G. J., & Olszewski, W. (2010) · Games and Economic Behavior · doi:10.1016/j.geb.2010.11.002 · Cited by 40 · see citing works
Origin and Structure of Dynamic Cooperative Networks
Wardil, L. L., & Hauert, C. (2014) · Scientific Reports · doi:10.1038/srep05725 · Cited by 33 · see citing works
Continuous-time stochastic games
Neyman, A. (2017) · Games and Economic Behavior · doi:10.1016/j.geb.2017.02.004 · Cited by 33 · see citing works
Mertens, J., & Neyman, A. (1982) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.79.6.2145 · Cited by 31 · see citing works
Grujić, J., Cuesta, J. A., & Sánchez, Á. (2012) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2012.02.003 · Cited by 27 · see citing works
The Control of Synchronous Systems, Part II
de Alfaro, L., Henzinger, T. A., & Mang, F. Y. C. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44685-0_38 · Cited by 26 · see citing works
A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament
Miltersen, P. B., & Sørensen, T. B. (2007) · Adaptive Agents and Multi-Agents Systems · doi:10.1145/1329125.1329357 · Cited by 25 · see citing works
The coevolution of culture and environment.
Safarzynska, K. (2013) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2013.01.004 · Cited by 22 · see citing works
‘Raise the stakes’ evolves into a defector
Killingback, T., & Doebeli, M. (1999) · Nature · doi:10.1038/22913 · Cited by 18 · see citing works
Sobel, M. J. (1973) · Journal of Applied Probability · doi:10.1017/s0021900200118467 · Cited by 17 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Tackling climate change with machine learning
Rolnick, D., Donti, P. L., Kaack, L. H., Kochanski, K., Lacoste, A., Sankaran, K., Ross, A. S., Milojevic-Dupont, N., Jaques, N., Waldman-Brown, A., et al. (2023) · ACM Computing Surveys · doi:10.1145/3485128 · Cited by 336 · see citing works
Barfuss, W., Donges, J. F., Vasconcelos, V. V., Kurths, J., & Levin, S. A. (2020) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1916545117 · Cited by 87 · see citing works
Early exclusion leads to cyclical cooperation in repeated group interactions
Liu, L., Xiao, Z., Chen, X., & Szolnoki, A. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2021.0755 · Cited by 50 · see citing works
Conditional investment strategy in evolutionary trust games with repeated group interactions
Liu, L., & Chen, X. (2022) · Information Sciences · doi:10.1016/j.ins.2022.07.073 · Cited by 45 · see citing works
Stochastic evolutionary dynamics of trust games with asymmetric parameters
Lim, I. S. (2020) · Physical review. E · doi:10.1103/physreve.102.062419 · Cited by 12 · see citing works
- Authors
- Hilbe, C., Šimsa, Š., Chatterjee, K., & Nowak, M. A.
- Affiliations
- Harvard University (US)
- Charles University (CZ)
- Institute of Science and Technology Austria (AT)
- Corresponding author
- Hilbe, Christian
- Chatterjee, Krishnendu
- Nowak, Martin A.
- Venue
- Nature
- Published
- 2018-07
- Volume
- 559
- Issue
- 7713
- Pages
- 246-249
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- OpenAlex
- W2811498230
- Cited by
- 277
- References
- 85
- Citations by year
- 2026: 34 · 2025: 40 · 2024: 42 · 2023: 38 · 2022: 38 · 2021: 31 · 2020: 29 · 2019: 21 · 2018: 4
- FWCI
- 48.26
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Nature (publishedVersion)
- PubMed (publishedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- Topics
- Social Sciences › Sociology and Political Science › Evolutionary Game Theory and Cooperation
- Social Sciences › Safety Research › Experimental Behavioral Economics Studies
- Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
- Keywords
- evolution of cooperation, stochastic games, social dilemmas, public goods, direct reciprocity, repeated interaction, tragedy of the commons, environmental change
- MeSH terms
- Cooperative Behavior, Decision Making, Biological Evolution, Game Theory, Group Processes, Probability, Stochastic Processes, Feedback, Psychological
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
