Repeated & Cooperative Games

Chapter 01 left us with a uncomfortable fact: a Nash equilibrium can be jointly terrible. Two players, each best-responding to the other, can lock into an outcome that both would gladly trade away if only they could trust one another. The escape is not a cleverer one-shot argument — there is none. The escape is repetition. When the same players meet again and again, today's defection can be punished tomorrow, and the prospect of that punishment makes cooperation a credible, self-enforcing equilibrium.

A repeated game takes a one-shot game — the stage game — and plays it over and over, the same opponents each round. What changes is that a player's strategy is no longer a single action; it is a plan that can condition on history. "Cooperate, but defect forever the moment you defect on me" is only expressible when there is a future to threaten. The value of that future is governed by a single number, the discount factor \(\delta\): how much a payoff one round from now is worth today.

This is not a vague hope; it is a theorem. The Folk Theorem says that in an infinitely repeated game with players patient enough (\(\delta\) close to 1), any outcome in which every player does at least as well as their guaranteed minimum (their minmax payoff) can be sustained as a subgame-perfect equilibrium. Cooperation is one such outcome — but so are many others, which is both the power and the embarrassment of the result: repetition explains how cooperation can arise, not which equilibrium will be selected. We will be honest about that gap throughout.

The contrast with the one-shot world is stark. In a single play, a strategy is just an action and the only stable thing is mutual defection. In the repeated world, a strategy is a policy over histories and the set of equilibria explodes. The rest of this chapter is about which of those equilibria are robust — to a clever opponent, to mutation, to noise.

The Prisoner's Dilemma is the cleanest specimen of the conflict between individual and collective rationality. Two suspects, held separately, can each cooperate (stay silent) or defect (betray the other). The payoffs are usually written with four letters: Temptation (defect on a cooperator), Reward (mutual cooperation), Punishment (mutual defection), and Sucker (cooperate against a defector).

A game is a Prisoner's Dilemma whenever the payoffs obey two inequalities. The first makes defection dominant; the second makes mutual cooperation the socially better outcome:

In one shot, that is the end of the story. There is no trick of reasoning that recovers cooperation, no "if I cooperate maybe they will too" — the dominance argument is airtight, and the chapter on equilibria proved it. Defection is not a failure of intelligence; it is what intelligence prescribes when the game is played exactly once. The dilemma is real, and it is why the one-shot answer to the headline true/false below is unambiguous.

Now repeat the game. Suppose both players adopt Grim Trigger: cooperate every round, but if the opponent ever defects, defect forever after. Is mutual cooperation stable? A player tempted to defect once gains \(T - R\) this round, then is punished with \(P\) instead of \(R\) for the rest of time. Cooperation is an equilibrium exactly when the one-time gain does not beat the discounted stream of forfeited rewards:

# Grim-Trigger: when is "cooperate forever" worth more than "defect once"?
import numpy as np
T, R, P, S = 5, 3, 1, 0                      # PD payoffs (EQ G2.2)

# value of always cooperating vs deviating once then being punished forever
def coop_value(delta):  return R / (1 - delta)            # R, R, R, ...
def defect_value(delta): return T + delta * P / (1 - delta)  # T now, then P forever

thresh = (T - R) / (T - P)                   # closed-form threshold (EQ G2.3)
print(f"theoretical cooperation threshold: delta >= {thresh:.3f}\n")

print(" delta   coop_value   defect_value   cooperation holds?")
for d in (0.30, 0.49, 0.50, 0.75, 0.95):
    c, x = coop_value(d), defect_value(d)
    print(f" {d:4}    {c:9.2f}    {x:11.2f}      {c >= x}")

print("\ncooperation becomes the better choice exactly at delta = 0.5,")
print("matching (T-R)/(T-P). The shadow of the future has a sharp edge.")
plot_xy([0.3,0.49,0.5,0.75,0.95],
        [coop_value(d)-defect_value(d) for d in (0.3,0.49,0.5,0.75,0.95)])

Theory tells us cooperation can be an equilibrium. It does not tell us which strategy a real population will land on. In 1980 the political scientist Robert Axelrod ran an experiment to find out: he invited game theorists to submit computer strategies for the iterated Prisoner's Dilemma, then played them all against each other in a round-robin and summed each one's score. The winner — submitted by Anatol Rapoport, and the shortest program entered — was Tit-for-Tat (TFT): cooperate on the first move, then on every move after, simply copy what the opponent did last round.

That last point is the deep lesson, and it is genuinely counter-intuitive. In a zero-sum world you win by making the other player lose. The iterated PD is not zero-sum: two cooperators each score \(R\) per round, far more than two defectors' \(P\). TFT racks up its total not by exploiting anyone but by spending most of its rounds in the lucrative \((R,R)\) groove with other nice strategies. Strategies that tried to be clever — probing for weakness, defecting "just once" — poisoned their own relationships and scored worse. Greed was self-defeating in a way that only repetition makes visible.

TFT is not a flawless oracle, and honesty requires the caveats. First, it is fragile to noise: if a single move is misimplemented — a cooperate flips to a defect by error — two TFT players fall into an endless echo of mutual recrimination, each punishing the other's punishment. Variants like Tit-for-Two-Tats (retaliate only after two defections) and Generous TFT (forgive a defection with some probability) were designed to break that echo. Second, TFT's victory is tournament-dependent: change the population of opponents and a different strategy can top the table. Against a field with no exploitable cooperators, the relentless defector ALLD can win; Axelrod's result holds because his fields were rich in nice, retaliatory strategies. The instrument below lets you feel exactly this — and the one after it shows what happens when strategies must survive, not just score.

# A mini Axelrod tournament: round-robin, sum each strategy's total score
import numpy as np
T, R, P, S = 5, 3, 1, 0
rng = np.random.default_rng(0)

def TFT(me, opp):   return 'C' if not opp else opp[-1]          # copy last move
def ALLD(me, opp):  return 'D'                                  # always defect
def ALLC(me, opp):  return 'C'                                  # always cooperate
def GRIM(me, opp):  return 'D' if 'D' in opp else 'C'           # never forgive
def RAND(me, opp):  return 'C' if rng.random() < 0.5 else 'D'

def match(a, b, rounds=200):
    ha, hb, sa, sb = [], [], 0, 0
    pay = {('C','C'):(R,R), ('C','D'):(S,T), ('D','C'):(T,S), ('D','D'):(P,P)}
    for _ in range(rounds):
        x, y = a(ha, hb), b(hb, ha)
        pa, pb = pay[(x, y)]; sa += pa; sb += pb; ha.append(x); hb.append(y)
    return sa, sb

strats = {'TFT':TFT, 'ALLD':ALLD, 'ALLC':ALLC, 'GRIM':GRIM, 'RAND':RAND}
score = {n: 0 for n in strats}
for i in strats:
    for j in strats:                      # round-robin, includes self-play
        score[i] += match(strats[i], strats[j])[0]

for n in sorted(score, key=lambda k: -score[k]):
    print(f"{n:5s} total score {score[n]:5d}")
print("\nTFT and GRIM win the lucrative (R,R) groove with nice strategies;")
print("ALLC is exploited, ALLD poisons its own matches. Niceness pays.")

Axelrod's tournament scored strategies once. But in biology — and in any population of learning agents — a successful strategy does more than score: it reproduces. Strategies that earn more payoff become more common; strategies that earn less die out. This shift in perspective, from a rational chooser to a population under selection, is evolutionary game theory, introduced by John Maynard Smith and George Price in 1973. It needs no assumption that players are rational — only that fitter strategies spread.

The central solution concept is the Evolutionarily Stable Strategy (ESS): a strategy that, if adopted by the whole population, cannot be invaded by a small group of mutants playing anything else. Formally, an incumbent strategy \(x\) is an ESS if, against itself, it does at least as well as any mutant \(y\) — and, in the knife-edge case where they tie against the incumbent, \(x\) beats \(y\) when the mutant has to play against other mutants.

How a population gets to an ESS is described by the replicator dynamics: the share of each strategy grows in proportion to how much its fitness beats the population average. Strategies above average expand; strategies below average shrink. The rest points of this flow are the Nash equilibria, and its stable rest points are the ESSs.

The canonical illustration is Hawk–Dove, Maynard Smith's own example. Animals contest a resource of value \(V\). Hawks escalate and risk injury of cost \(C\); Doves display and retreat. Two Hawks split the resource minus the expected injury, \((V-C)/2\); a Hawk meeting a Dove takes the whole \(V\); two Doves share it, \(V/2\). When \(C > V\), neither pure strategy is stable — a population of all Hawks is invadable by Doves (who avoid the ruinous fights) and vice versa. The unique ESS is a mixed population with a Hawk fraction \(p^{*} = V/C\), and the replicator dynamics converges there from almost any start.

# Replicator dynamics on Hawk-Dove: converge to the mixed ESS p* = V/C
import numpy as np
V, C = 2.0, 4.0                              # resource value, injury cost (C > V)
# rows/cols: 0 = Hawk, 1 = Dove ; A[i,j] = payoff to i against j  (EQ G2.6)
A = np.array([[(V - C) / 2,  V   ],
              [ 0.0,         V / 2]])
p_star = V / C                              # predicted ESS Hawk fraction
print(f"predicted mixed ESS: Hawk fraction p* = V/C = {p_star:.3f}\n")

x = np.array([0.90, 0.10])                  # start: mostly Hawks
dt = 0.05
traj = []
for step in range(600):
    f = A @ x                              # fitness of each strategy
    phi = x @ f                            # mean fitness  x^T A x
    x = x + dt * x * (f - phi)             # replicator update
    x = x / x.sum()                        # renormalize onto the simplex
    if step % 120 == 0:
        print(f"step {step:3d}: Hawk={x[0]:.3f}  Dove={x[1]:.3f}")
    traj.append(x[0])

print(f"\nconverged Hawk fraction: {x[0]:.3f}  (matches V/C = {p_star:.3f})")
print("neither pure strategy survives: the population settles at the mix.")
plot_xy(list(range(len(traj))), traj)

Everything so far has been non-cooperative game theory: players choose actions independently and we ask what they will do. Cooperative (or coalitional) game theory asks a different question. Suppose the players can form binding agreements and pool their efforts — the only question is how to divide the joint payoff fairly. The primitive is no longer a payoff matrix but a characteristic function \(v(S)\): for every possible coalition \(S\) of players, the total value that coalition can guarantee on its own.

The most celebrated answer to "what is each player's fair share?" is the Shapley value, introduced by Lloyd Shapley in 1953. Its idea is disarmingly simple: a player's worth is their average marginal contribution across every order in which the coalition could have been assembled. Imagine the players walking into a room one at a time in a random order; each player is credited with how much they add to the value of those already present. Average that credit over all \(n!\) orders, and you have the Shapley value.

The Shapley value is the unique allocation satisfying four axioms that any reasonable notion of fairness should demand. Efficiency: the shares sum to the total value \(v(N)\). Symmetry: two players who contribute identically to every coalition get equal shares. Null player: a player who adds nothing to any coalition gets zero. Additivity: the value of two games played together is the sum of the values played separately. That a single formula is forced by these four innocuous requirements is the result's quiet power — and it is why the Shapley value reaches far beyond economics.

That reach is the bridge to the next chapter. In machine learning, SHAP (SHapley Additive exPlanations) treats a model's input features as "players" cooperating to produce a prediction, and uses the Shapley value to attribute the prediction fairly among them — the dominant method for feature attribution in 2026, and the rare interpretability tool with an axiomatic guarantee. The same idea credits data points for a model's accuracy (data valuation) and apportions cost in shared infrastructure. Fair division, it turns out, is a computational problem the field cannot stop needing.

# Shapley value of a 3-player game, by averaging over all arrival orders
import numpy as np
from itertools import permutations

# characteristic function v(S): value each coalition can secure (EQ G2.7)
v = {(): 0, (0,): 10, (1,): 20, (2,): 30,
     (0,1): 50, (0,2): 60, (1,2): 70, (0,1,2): 100}
def val(S): return v[tuple(sorted(S))]

n = 3
phi = np.zeros(n)
orders = list(permutations(range(n)))         # all n! = 6 arrival orders
for order in orders:
    present = set()
    for p in order:
        before = val(present)                 # value without player p
        present.add(p)
        phi[p] += val(present) - before       # p's marginal contribution
phi /= len(orders)                            # average over orderings

for i in range(n):
    print(f"player {i}: Shapley value phi = {phi[i]:.3f}")
print(f"\nsum of shares      = {phi.sum():.3f}")
print(f"grand-coalition v(N) = {val(range(n))}   <- efficiency: they match exactly")

1. Axelrod, R. (1984). The Evolution of Cooperation. Basic Books — the round-robin tournaments and the four properties of tit-for-tat (EQ G2.4, §2.3); the founding popular text on repeated cooperation.
2. Axelrod, R. & Hamilton, W. D. (1981). The Evolution of Cooperation. Science 211(4489) — the peer-reviewed account of the iterated-PD tournaments and the evolutionary stability of tit-for-tat.
3. Maynard Smith, J. & Price, G. R. (1973). The Logic of Animal Conflict. Nature 246 — introduces the Evolutionarily Stable Strategy (EQ G2.5) and the Hawk–Dove game (§2.4).
4. Shapley, L. S. (1953). A Value for n-Person Games. In Contributions to the Theory of Games II, Princeton University Press — defines the Shapley value (EQ G2.7) and its axiomatic characterization (§2.5).
5. Maynard Smith, J. (1982). Evolution and the Theory of Games. Cambridge University Press — the book-length development of ESS and the replicator perspective (EQ G2.6).
6. Friedman, J. W. (1971). A Non-cooperative Equilibrium for Supergames. Review of Economic Studies 38(1) — Grim-Trigger equilibria and an early form of the Folk Theorem behind EQ G2.3 (§2.1).
7. Lundberg, S. M. & Lee, S.-I. (2017). A Unified Approach to Interpreting Model Predictions. NeurIPS 30 (SHAP) — the Shapley value applied to machine-learning feature attribution, the §2.5 bridge into Chapter 03.