Repeated Games and Cooperation

What you’re seeing

Why a known last round unravels everything

Suppose two players know they will play the prisoner’s dilemma exactly 200 times. In round 200 there is no future to protect, so it is a one-shot game and both defect. Knowing that, round 199 has no future worth protecting either, since round 200 is going to be mutual defection anyway, so both defect there too. Backward induction (Chapter 6) unravels the whole game: in the finitely repeated prisoner’s dilemma, the unique subgame perfect equilibrium is to defect in every round, however long the game is.

That conclusion strikes most people as wrong, and real players don’t follow it: in experiments, cooperation usually survives until close to the end. Two things break the argument: an end that is uncertain, and a little doubt about whether the other player is fully rational.

The shadow of the future

If after each round the game continues with probability δ, or players value a payoff one round later at δ times its value today, then a stream of payoffs u₀, u₁, u₂, … is worth u₀ + δu₁ + δ²u₂ + … . The number δ, between 0 and 1, is the discount factor: how much the future counts. Axelrod called it the shadow of the future.

Consider grim trigger: cooperate until the other player defects, then defect forever. If both play it, both cooperate forever and each gets R + δR + δ²R + … = R/(1 − δ). A player who defects today gets T now, but then mutual defection forever: T + δP/(1 − δ). Cooperation is a best response when

Is the punishment itself credible? Yes: once someone has defected, defecting forever is a best response to a partner who defects forever, so grim trigger is subgame perfect, not just a Nash equilibrium.

The folk theorem

Grim trigger is one equilibrium of the repeated game, but far from the only one. The folk theorem, so called because game theorists knew versions of it before anyone published them, says roughly: in an infinitely repeated game with patient enough players, any pattern of average payoffs that is feasible and gives every player more than the least that others could hold them to (their minmax payoff) can be sustained by a subgame perfect equilibrium. James Friedman proved a version with punishments that revert to a Nash equilibrium of the one-shot game (1971); Drew Fudenberg and Eric Maskin gave a general form (1986). Repetition explains how cooperation is possible; it does not say that cooperation will happen, because mutual defection forever remains an equilibrium too.

Axelrod’s tournaments

Around 1980 Robert Axelrod, a political scientist at the University of Michigan, invited game theorists to submit computer programs to play a repeated prisoner’s dilemma. In the first tournament 14 entries and a random strategy played each other, and themselves, in a round robin of 200-move matches. The winner, submitted by the mathematical psychologist Anatol Rapoport, was tit for tat, the simplest program entered. Axelrod published the results and held a second tournament, this time with matches of uncertain length; 62 entries arrived from six countries, many designed to beat tit for tat. Tit for tat won again. In his book The Evolution of Cooperation (1984) Axelrod drew lessons from the successful strategies:

He also ran an “ecological” analysis, letting each strategy’s share of the population grow with its score, the same thing the Evolution view does. Strategies that preyed on naive cooperators shrank once their prey disappeared, and nice, retaliating strategies came to dominate.

The field matters. Which strategy wins depends on who else is in the tournament. In this page’s small field without noise, grim trigger edges out tit for tat because it punishes the Random player harder; take Random out and see what changes. Mistakes matter too. When moves can come out wrong, tit for tat against itself falls into echoes: one accidental defection is answered, the answer is answered, and the pair alternates for a long time. Martin Nowak and Karl Sigmund showed that generous tit for tat (1992) and win-stay, lose-shift (1993) do better in noisy worlds because they recover from errors. In our tests with 5% noise, tit for tat averaged 2.30 points a round against itself, while generous tit for tat averaged 2.86 and win-stay, lose-shift 2.79.

Reputation, and cooperation in business

The unraveling argument for a known last round assumes everyone is sure everyone else is rational. David Kreps, Paul Milgrom, John Roberts and Robert Wilson showed in 1982 that a small doubt changes everything: if there is even a modest chance that your partner is the kind of player who plays tit for tat no matter what, it pays a fully rational player to cooperate too, to keep the partner cooperating, until near the end. A reputation for cooperating is an asset, built slowly and lost quickly.

Long relationships are how most business works. Suppliers deliver quality they could skimp on, customers pay invoices they could delay, and firms keep promises to employees in hard times, because each side values the future of the relationship more than the gain from cheating today. When Southwest Airlines kept its employees after the 2001 attacks, it was honoring a commitment that was costly to keep; the case Southwest Airlines Keeps Its People After 9/11 discusses how that built trust. The same logic holds cartels together, until it doesn’t: the lysine cartel in Chapter 5 held regular meetings to monitor each member’s sales.

Axelrod also described the “live and let live” system in the trenches of the First World War, drawing on the historian Tony Ashworth: units facing each other for long periods often held their fire, or fired at predictable times and places, and answered any real attack in kind. Soldiers in opposing armies were in a repeated game, and the high command, which wanted fighting, eventually broke it up, above all by ordering raids on the enemy trenches.

Where you see it

• Business: supplier relationships, repeat customers, online reviews (a public reputation is a repeated game with everyone), price leadership in concentrated markets, and the tacit collusion that competition authorities look for.
• Policy: arms-control treaties with inspections, trade agreements with retaliation clauses, fishing quotas: repeated games with monitoring.
• Biology: Axelrod and the biologist W. D. Hamilton applied the same ideas to cooperation among animals (Science, 1981). Reciprocity needs repeated encounters with individuals who recognize each other.
• Daily life: neighbors, coworkers and roommates cooperate because they will see each other tomorrow. The last week of a job, or a one-time online purchase from a stranger, are where cooperation is most fragile.

Nothing here is financial or investment advice.

Practice

1. A threshold. In a prisoner’s dilemma with T = 7, R = 4, P = 2, S = 0, how patient must players be for grim trigger to sustain cooperation?

   Show the answer

   δ* = (7 − 4)/(7 − 2) = 3/5 = 0.6. With δ = 0.6, cooperating is worth 4/0.4 = 10 and defecting 7 + 0.6 × 2/0.4 = 10: exactly equal.

2. Three rounds. Two players play Osborne’s prisoner’s dilemma exactly three times and both know it. Explain why both defect in round 1.

   Show the answer

   Round 3 is a one-shot game: both defect. In round 2, whatever happens, round 3 will be mutual defection, so round 2 is effectively one-shot too: both defect. The same reasoning applies to round 1. Cooperation can’t be rewarded in a future that is already decided.

3. The cartel’s threshold. Verify that the cartel of Chapter 5 can be held together by grim trigger exactly when δ ≥ 9/17.

   Show the answer

   Collusion: 22.5 each at a price of $55, profit 1,012.5. Cheating: 33.75 against 22.5, price $43.75, profit 33.75 × 33.75 = 1,139.0625. Cournot: 900. δ* = (1,139.0625 − 1,012.5)/(1,139.0625 − 900) = 126.5625/239.0625 = 9/17 ≈ 0.529.

4. How long is uncertain? If after every round there is another with probability w = 0.95, how many rounds does a match last on average?

   Show the answer

   The number of rounds is geometric: the expected length is 1/(1 − w) = 1/0.05 = 20 rounds. (Our simulation checked w = 0.9: 4,000 matches averaged 10.00 rounds.)

5. How many reciprocators to invade? In a population of Always defect and Tit for tat playing 200-round matches with Axelrod’s payoffs, TFT earns 600 against TFT and 199 against ALLD; ALLD earns 204 against TFT and 200 against ALLD. Above what share x of TFT does TFT do better?

   Show the answer

   TFT: 600x + 199(1 − x). ALLD: 204x + 200(1 − x). TFT is better when 401x + 199 > 4x + 200, that is 397x > 1, or x > 1/397 ≈ 0.25%. A tiny cluster of reciprocators who meet each other can invade a world of defectors.

6. The folk theorem at work. With Axelrod’s payoffs, can two patient players sustain average payoffs of (2.5, 2.5) by alternating (C, D) and (D, C)? What is each player’s minmax payoff?

   Show the answer

   Each player can guarantee at least P = 1 by always defecting, and the other can hold them to 1 by always defecting, so the minmax payoff is 1. Alternating gives each an average of (5 + 0)/2 = 2.5 > 1, and it is feasible, so by the folk theorem it can be sustained for δ close enough to 1 (it is worse than mutual cooperation, 3 each, but it is an equilibrium too).

7. Tit for tat never wins a match. Without noise, show that in any match tit for tat’s total is at most its opponent’s.

   Show the answer

   The scores differ only in rounds where one player defects and the other cooperates. Tit for tat defects against a cooperator only in a round right after the opponent defected. Look at the sequence of rounds where the two players’ moves differ: tit for tat copies with a one-round delay, so those rounds alternate, starting with the opponent defecting (tit for tat begins by cooperating). So the opponent is the defector in at least as many of them as tit for tat, and each of those rounds gives the defector 5 and the cooperator 0. Hence the opponent’s total is at least tit for tat’s.

How the interactives work

Matches. Each round, both strategies choose from the history of what was actually played; with noise, each chosen move is flipped with the given probability before it is played. Payoffs are Axelrod’s: 5, 3, 1 and 0. Matches last 200 rounds, or continue with probability w after each round (capped at 3,000 rounds). Your strategy is “memory one”: its move depends only on the last round, unless you tick “never forgive.” The default rule is tit for tat.

Tournament. Every pair plays, including each strategy against itself. Each pair plays several matches (3 without noise, 6 with it, 40 to 200 for uncertain lengths) and the grid shows the average payoff per round. A strategy’s score is the average of its row. Evolution uses the tournament grid: each generation, a strategy’s share is multiplied by its average payoff against the current population and divided by the population average (discrete replicator dynamics), for 200 generations. The discount lab plots R and (1 − δ)T + δP, the average discounted payoffs of cooperating and of defecting once against grim trigger.

Checks (node). Tit for tat against Always defect over 200 rounds scores 199 to 204; against itself, 600. Without noise, tit for tat never outscored its opponent in 50 matches against each strategy. In our classic field without noise the ranking was Grim 2.73, TFT 2.66, TF2T 2.61, WSLS 2.60, GTFT 2.58, ALLC 2.44, Random 2.24, ALLD 2.16; with w = 0.5, Always defect came first (3.28). From equal shares, evolution drove Always defect below 1%; starting with 90% Always defect, after 300 generations the reciprocators (TFT, Grim, TF2T) held almost the whole population. With w = 0.9, 4,000 matches averaged 10.00 rounds, as 1/(1 − w) predicts. The threshold δ* = 1/2 for Axelrod’s payoffs makes both values exactly equal.

Check yourself

1. In a prisoner’s dilemma repeated exactly 100 times, with the end known to both players, the subgame perfect equilibrium is …

   • cooperate until round 100, then defect
   • defect in every round
   • tit for tat
   Show the answer

   Backward induction unravels from the last round. Uncertainty about the end, or about the other player’s type, is what rescues cooperation.

2. With T = 5, R = 3, P = 1, grim trigger sustains cooperation if and only if …

   • δ ≥ 3/5
   • δ ≥ 1/5
   • δ ≥ 1/2
   Show the answer

   (T − R)/(T − P) = 2/4 = 1/2.

3. Why did tit for tat do so well in Axelrod’s tournaments?

   • It was nice, retaliated against defection, forgave quickly and was easy to read, so it got cooperation from many opponents
   • It beat every opponent head to head
   • It defected more often than the others
   Show the answer

   It never beats an opponent in a match. Its total was high because it rarely got into long fights.

4. When moves can come out wrong (noise), tit for tat against itself …

   • keeps cooperating perfectly
   • falls into echoes of alternating retaliation after a mistake
   • switches to always defecting at once
   Show the answer

   Each copies the other’s last move, so a single error bounces back and forth. Generous tit for tat and win-stay, lose-shift recover faster.

5. The folk theorem says that in an infinitely repeated game with patient players …

   • cooperation is the only equilibrium
   • only the one-shot Nash equilibrium can be repeated
   • many outcomes, including full cooperation, can be sustained as equilibria, as long as each player gets more than their minmax payoff
   Show the answer

   Repetition makes cooperation possible but not inevitable: there are many equilibria, including mutual defection forever.

Sources

• M. J. Osborne, An Introduction to Game Theory (Oxford University Press, 2004), chapters 14 and 15 (repeated games: the prisoner’s dilemma; general results and the folk theorem).
• R. Axelrod, “Effective choice in the prisoner’s dilemma” and “More effective choice in the prisoner’s dilemma”, Journal of Conflict Resolution 24, 1980; The Evolution of Cooperation (Basic Books, 1984). R. Axelrod and W. D. Hamilton, “The evolution of cooperation”, Science 211, 1981, 1390–1396.
• R. Axelrod, “The Evolution of Strategies in the Iterated Prisoner’s Dilemma” (University of Michigan; the entries in the two tournaments).
• The Evolution of Cooperation (Wikipedia; the 200-move matches, Rapoport, and the properties of successful strategies).
• M. Nowak and K. Sigmund, “Tit for tat in heterogeneous populations”, Nature 355, 1992, 250–253; “A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner’s Dilemma game”, Nature 364, 1993, 56–58.
• J. W. Friedman, “A non-cooperative equilibrium for supergames”, Review of Economic Studies 38(1), 1971, 1–12. D. Fudenberg and E. Maskin, “The folk theorem in repeated games with discounting or with incomplete information”, Econometrica 54(3), 1986, 533–554.
• D. M. Kreps, P. Milgrom, J. Roberts and R. Wilson, “Rational cooperation in the finitely repeated prisoners’ dilemma”, Journal of Economic Theory 27(2), 1982, 245–252.
• Steven Kuhn, “Prisoner’s Dilemma”, Stanford Encyclopedia of Philosophy (iterated and evolutionary versions).
• MIT OpenCourseWare 14.12, Economic Applications of Game Theory (repeated games and the folk theorem).