Iterated and evolutionary game theory

October 13, 2016 — January 5, 2024

bounded compute
game theory
incentive mechanisms
Figure 1

Note: The originator of the field (R. M. Axelrod 1984) is very approachable and does not require esoteric mathematical sophistication. It is a good book which you should read. The notebook is a meagre summary for the busy. The internet is full of many lavish introductions to iterated game theory, and I recommend you try some of them out. Game Theory 101, for example, has many animations and a pedagogic structure.

Here we introduce an abstract model for how cooperation might evolve, or not, amongst a population of animals, especially human animals. The basic version is probably a bit too abstract to serve as a model for anything real but minor variants are useful in e.g. understanding inequity, culture wars and evolution.

1 Background: Game theory

See my actual basic game theory post for some more refs.

When people talk about game theory they usually mean the class of mathematically formulated two-player “games”, which are typically not the fun type of games, being much shorter and more brutal than Carcassone or whatever. The most famous one is the Prisoner’s dilemma; You’ve probably run into this one. You and I, co-conspirators, have been arrested by the cops for a crime we did commit, and we are interviewed separately. They offer us each the same choice: “Inform on your buddy and we will let you off lightly”. Obviously we want to have as little time in prison; what should we each do?

There are four possible outcomes:

  1. Both defect — You and I both turn informant: We both go to prison for 10 years
  2. You defect — You inform and I stay stumm: I go to prison for 10 years, you walk free in 1 year
  3. I defect — You stay stumm and I inform: You go to prison for 10 years, I walk free in 1 year
  4. Both cooperate — We both stay stumm: We each go to prison for 2 years on a lesser charge

The Prisoner’s dilemma is a classic. There are other games, but this one will stand in for all of them for now. The first lesson is that even though it would be better in terms of total prison time for us both to cooperate, to remain silent, given that you and I do not know if the other one will defect, it makes sense for each of us individually to defect.

This one is a toy model for the kind of cooperative dilemmas we face all the time, especially dilemmas about trust. Should I take credit for that bit of work at the expense of my colleague? Should I take more donuts from the donut tray rather than leave some for my colleagues? Why should my factory refrain from polluting if all my competitors are doing it and lowering their costs?

A lot of people have written about these kinds of games, there are some nice mathematical insights from making all this precise, theorems that you can prove and so forth. It’s a whole industry.

An important sub-field of this game theory thing is the field of iterated games, especially Iterated Prisoner’s Dilemma (“IPD”). This is the field wherein we extend the model a little to encompass the fact that these isolated one-off prisoner’s dilemmas are not a typical situation. In real life, when we interact in society, we meet with people again and again, and moreover there are a lot of people interacting in diverse situations. These are iterated games. Still a simplified model, but a whole bunch of interesting phenomena arise in the marginally more life-like setup.

2 Iterated Prisoner’s Dilemma: Basics and Strategy

  • Imagine two friends, Alice and Bob, playing a game repeatedly. In each round, they can either cooperate with each other or betray (defect). The twist is they remember what happened in previous rounds.
  • Strategy: This is the plan each player follows in every round. For instance, Alice might adopt the “Always Cooperate” strategy, meaning she decides to cooperate in every round, no matter what Bob does.

3 Population Structure and Interaction Model

  • Now, imagine there’s a whole group of people, not just Alice and Bob, playing this game. They might randomly pair up for each round, or maybe they always play against the same few people.
  • In some versions of this game, players remember not just past actions but also who they were playing against. So, if Alice played against Bob before, she might change her strategy based on what Bob did last time.

4 Competition and Evolution of Strategies

  • In this game, winning isn’t about a single round; it’s about doing well over many rounds. Let’s say Alice’s “Always Cooperate” strategy works well against those who also cooperate, but it might not do well against someone who always defects.
  • Strategy Evolution: Imagine a player, Charlie, who notices that “Always Defect” works well initially but then starts losing out to players using “Tit-for-Tat” (a strategy where a player cooperates in the first round and then replicates the opponent’s previous action). Charlie might switch to “Tit-for-Tat” to improve his overall score.
  • Over time, the most successful strategies become more common. If “Tit-for-Tat” consistently earns higher scores, more players will start using it.

5 Implications

  • This game is a simple way to understand complex real-world interactions. It shows how people (or animals, or even computer programs) might change their behavior based on past experiences and the behavior of others around them. It’s not just about winning a game; it’s about how strategies evolve and how cooperation or competition can emerge in a community.

By using these concrete examples, we can see how the Iterated Prisoner’s Dilemma is a powerful tool for understanding the dynamics of strategy, memory, and evolution in both social and biological contexts.

6 Population-Level Behaviors:

  1. Clusters of Cooperation: In a mixed population of different strategies, cooperators can form clusters. If players are more likely to interact with those nearby (like in a spatial IPD), these clusters can protect cooperators from defectors, as they mostly interact with each other.

  2. Cycles of Strategies: Sometimes, you’ll see cycles where different strategies rise and fall in prevalence. For instance, if “Always Defect” becomes common, “Tit-for-Tat” might rise in response, as it can protect itself against defectors. But then, a more forgiving strategy might outcompete “Tit-for-Tat” by not retaliating as harshly, and so on.

7 Dependence on Initial Conditions:

  • The outcome of an IPD tournament can be highly sensitive to initial conditions. For example, if the game starts with a majority of defectors, cooperative strategies might struggle to gain a foothold. Conversely, if the game starts with many cooperators, they might establish a cooperative norm that resists invasion by defectors.
  • The structure of interactions also matters. If players mostly interact with a fixed set of neighbors, it can lead to different dynamics compared to a model where they interact randomly with the entire population.

8 Unintuitive Dynamics:

  1. Emergence of Cooperation: It might seem counterintuitive, but cooperation can emerge and stabilize even in a competitive environment. The success of strategies like “Tit-for-Tat” shows that cooperation can be a robust strategy, even when facing defectors.

  2. The Shadow of the Future: The importance of future interactions in the IPD is often surprising. The longer the shadow of the future (i.e., the more future interactions players expect to have), the greater the incentive to cooperate. This is because the potential future payoffs from cooperation outweigh the immediate gains from defection.

  3. Complexity from Simplicity: The IPD is based on simple rules, yet it can lead to incredibly complex dynamics. This complexity arising from simplicity can be quite unexpected, showing how basic interactions can lead to rich and varied behavioral patterns.

The dynamics of IPD games at the population level can be quite complex and often counterintuitive. The initial setup of the game and the interaction structure play crucial roles in determining the outcome, and the emergence of cooperation in a competitive environment highlights the nuanced interplay between individual strategies and collective behavior.

9 Incoming

10 References

Axelrod, Robert M. 1984. The evolution of cooperation.
Axelrod, Robert. 1985. The Evolution of Cooperation.
Boyd, and Richerson. 1990. Group Selection Among Alternative Evolutionarily Stable Strategies.” Journal of Theoretical Biology.
Bruner, and O’Connor. 2017. Power, Bargaining, and Collaboration.” In Power, Bargaining, and Collaboration.
Cai, Daskalakis, and Weinberg. 2013. Understanding Incentives: Mechanism Design Becomes Algorithm Design.” arXiv:1305.4002 [Cs].
Castellano, Fortunato, and Loreto. 2009. Statistical Physics of Social Dynamics.” Reviews of Modern Physics.
Choi, and Bowles. 2007. The Coevolution of Parochial Altruism and War.” Science.
Chong, and Yao. 2005. Behavioral Diversity, Choices and Noise in the Iterated Prisoner’s Dilemma.” IEEE Transactions on Evolutionary Computation.
Cochran, and O’Connor. 2019. Inequality and Inequity in the Emergence of Conventions.” Politics, Philosophy and Economics.
Dawkins. 1980. “Good Strategy or Evolutionarily Stable Strategy?” In Sociobiology: Beyond Nature/Nurture?
Dowding. 2016. Albert O. Hirschman, Exit, Voice and Loyalty: Responses to Decline in Firms, Organizations, and States.” In Albert O. Hirschman,.
Fosco, and Mengel. 2010. Cooperation Through Imitation and Exclusion in Networks.” Journal of Economic Dynamics and Control.
Harley. 1981. Learning the Evolutionarily Stable Strategy.” Journal of Theoretical Biology.
Hauert, Monte, Hofbauer, et al. 2002. Volunteering as Red Queen Mechanism for Cooperation in Public Goods Games.” Science.
Henrich, and Boyd. 2001. Why People Punish Defectors: Weak Conformist Transmission Can Stabilize Costly Enforcement of Norms in Cooperative Dilemmas.” Journal of Theoretical Biology.
Hetzer, and Sornette. 2013. An Evolutionary Model of Cooperation, Fairness and Altruistic Punishment in Public Good Games.” PLoS ONE.
Hirschman. 1970. Exit, Voice, and Loyalty: Responses to Decline in Firms, Organizations, and States.
Izumi, Yamashita, and Kurumatani. 2005. Analysis of Learning Types in an Artificial Market.” In Multi-Agent and Multi-Agent-Based Simulation.
Jackson. 2008. Social and Economic Networks.
Köster, Hadfield-Menell, Everett, et al. 2022. Spurious Normativity Enhances Learning of Compliance and Enforcement Behavior in Artificial Agents.” Proceedings of the National Academy of Sciences.
Le, and Boyd. 2007. “Evolutionary Dynamics of the Continuous Iterated Prisoner’s Dilemma.” Journal of Theoretical Biology.
McElreath, and Boyd. 2007. Mathematical Models of Social Evolution: A Guide for the Perplexed.
Mohseni, O’Connor, and Rubin. 2019. On the Emergence of Minority Disadvantage: Testing the Cultural Red King Hypothesis.” Synthese.
Nowak. 2006. Five Rules for the Evolution of Cooperation.” Science.
O’Connor. 2017. The Cultural Red King Effect.” The Journal of Mathematical Sociology.
———. 2019. The Origins of Unfairness: Social Categories and Cultural Evolution.
Olson. 2009. The Logic of Collective Action: Public Goods and the Theory of Groups.
Ostrom. 1990. Governing the Commons: The Evolution of Institutions for Collective Action (Political Economy of Institutions and Decisions).
Phelps. 2013. Emergence of Social Networks via Direct and Indirect Reciprocity.” Autonomous Agents and Multi-Agent Systems.
Phelps, Nevarez, and Howes. 2011. The Effect of Group Size and Frequency-of-Encounter on the Evolution of Cooperation.” In Advances in Artificial Life. Darwin Meets von Neumann. Lecture Notes in Computer Science.
Rapoport, Seale, and Colman. 2015. Is Tit-for-Tat the Answer? On the Conclusions Drawn from Axelrod’s Tournaments.” PLOS ONE.
Richards. 2001. Coordination and Shared Mental Models.” American Journal of Political Science.
Rubin, and O’Connor. 2018. Discrimination and Collaboration in Science.” Philosophy of Science.
Sanders, Galla, and Shapiro. 2011. Effects of Noise on Convergent Game Learning Dynamics.” arXiv:1109.4853.
Sato, and Crutchfield. 2003. “Coupled Replicator Equations for the Dynamics of Learning in Multiagent Systems.” Physical Review E.
Selten. 1988. A Note on Evolutionarily Stable Strategies in Asymmetric Animal Conflicts.” In Models of Strategic Rationality. Theory and Decision Library C.
Sethi, and Somanathan. 1996. The Evolution of Social Norms in Common Property Resource Use.” The American Economic Review.
Spence. 2002. Signaling in Retrospect and the Informational Structure of Markets.” American Economic Review.
Taylor, and Jonker. 1978. Evolutionary Stable Strategies and Game Dynamics.” Mathematical Biosciences.
Tooby, Cosmides, and Price. 2006. Cognitive Adaptations Forn-Person Exchange: The Evolutionary Roots of Organizational Behavior.” Managerial and Decision Economics.
Wolpert, Harré, Olbrich, et al. 2010. “Hysteresis Effects of Changing Parameters of Noncooperative Games.” SSRN eLibrary.
Wu, Altrock, Wang, et al. 2010. “Universality of Weak Selection.”
Yang, Lin, Wu, et al. 2011. Topological Conditions of Scale-Free Networks for Cooperation to Evolve.” arXiv:1106.5386.
Young. 1996. The Economics of Convention.” The Journal of Economic Perspectives.
———. 1998a. Individual Strategy and Social Structure : An Evolutionary Theory of Institutions.
———. 1998b. “Social Norms and Economic Welfare.” European Economic Review.
———. 2006. “Social Dynamics: Theory and Applications.” Handbook of Computational Economics.