The folk theorem

The previous lesson showed that patience turns mutual cooperation into an equilibrium of the repeated prisoner's dilemma, and the same construction turns almost every other outcome into one as well.

What repetition can support

Start by drawing the target. In the repeated game a player's payoff is the discounted average of a stream, so it is natural to normalise: multiply the discounted sum by $(1-\delta )$ so that a player who earns 4 every period has a repeated-game payoff of 4 rather than $4/(1-\delta )$. On that scale, repeated-game payoffs are directly comparable with stage payoffs.

The set of pairs that could conceivably be achieved is the feasible set: the convex hull of the stage payoff vectors. For the running prisoner's dilemma, with $T=6$, $R=4$, $P=2$ and $S=1$, the four stage outcomes are $(4,4)$, $(6,1)$, $(1,6)$ and $(2,2)$, and the hull is the quadrilateral they span. Points inside it that are not corners are reached by mixing over time: alternating between $(6,1)$ and $(1,6)$ gives an average of $(3.5,3.5)$, and a rota of three cooperative periods to one exploitative one gives $(4.5,3.25)$. Any point of the hull can be approached this way, and with a publicly observed randomising device, a coin both players see, it can be hit exactly.

Feasibility is not enough to make a point an equilibrium. A player who is being held below what they could get by simply refusing to participate will refuse. So the second ingredient is the floor.

What a player can be held to

The floor is the minmax value: the lowest payoff the other players can force on you when you respond as well as you can to whatever they do.

Read it in that order. The others pick their punishment first; you then best respond; they choose the punishment that leaves your best response worth as little as possible. No equilibrium of the repeated game can ever pay you less than this, because you can always guarantee $\mathrm{underline}\{v{\}}_i$ in every single period by best responding. A payoff vector giving every player strictly more than their minmax is called individually rational.

Two subtleties matter and both are commonly missed. First, minmax is not maximin. Maximin, from the zero-sum lesson, is what you can guarantee when you must move first in the dark; minmax is what others can hold you to when they move first. In a zero-sum game the minimax theorem makes them equal, and in general games they differ.

Second, the minimising side must be allowed to randomise, and this genuinely lowers the floor. Take a game in which player 1 earns 4 from T against L and 0 against R, and 0 from B against L and 3 against R. If player 2 must choose a pure column, player 1 replies with the matching row and earns at least 3, so the pure-strategy floor is 3. If player 2 mixes, playing L with probability $q$, player 1's best reply is worth $\max \{4q,3(1-q)\}$, and player 2 minimises that by equalising the two: $4q=3(1-q)$ gives $q=3/7$ and a value of $12/7=1.71$. Unpredictability is itself a punishment.

In the prisoner's dilemma the minmax is easy. If the opponent cooperates with probability $q$, your best reply is always to defect, worth $2+4q$, which the opponent minimises by never cooperating: $\mathrm{underline}\{v{\}}_i=2=P$. Mutual defection is exactly the punishment level here, which is why grim trigger was the natural construction.

Example. Find player 1's minmax value in the game where T pays 5 against L and 1 against R, and B pays 0 against L and 4 against R.

Let player 2 play L with probability $q$. Player 1's best reply is worth $\max \{5q+1(1-q),0q+4(1-q)\}=\max \{1+4q,4-4q\}$. Player 2 minimises the larger of the two by setting them equal: $1+4q=4-4q$ gives $q=0.375$ and a value of $1+1.5=2.5$. Against a pure column player 1 could guarantee 4, so mixing costs player 1 a further 1.5.

Now you. In the same game, what would player 1's minmax be if player 2 were restricted to pure strategies, and which column would player 2 use?

The theorem

Put the two ingredients together and the result is the folk theorem, so called because versions of it circulated among game theorists through the 1950s and 1960s with no agreed author.

Take a finite stage game with minmax values $\mathrm{underline}\{v{\}}_i$. For any feasible payoff vector $v$ with $v_i>\mathrm{underline}\{v{\}}_i$ for every player, there is a discount factor $\bar{\delta }<1$ such that for every $\delta >\bar{\delta }$, $v$ is the payoff of a subgame perfect equilibrium of the infinitely repeated game.

The construction is the one already seen. Put the players on a path that yields $v$, and specify that any deviation triggers a punishment phase in which the deviator is held to their minmax. Deviating gains at most a bounded amount in the period it happens and costs a stream, so once $\delta$ is high enough the stream wins.

Two versions are worth separating. James Friedman proved in 1971 that any feasible payoff strictly better for everyone than a Nash equilibrium of the stage game can be sustained by reversion to that equilibrium. This is the easy and completely credible version, since the punishment is a Nash equilibrium and nobody has to be persuaded to carry it out. Drew Fudenberg and Eric Maskin proved in 1986 that the stronger statement, with the punishment level pushed all the way down to the minmax, also gives subgame perfect equilibria, provided the feasible set has full dimension. The extra work in their proof is entirely about making the punishers willing to punish, since minmaxing someone can be costly for the punisher, and they solve it by rewarding the punishers afterwards.

Building one, and finding it is not cooperation

Take the running prisoner's dilemma and aim at $(3.5,3.5)$, achieved by taking turns at exploitation: in even periods player 1 defects while player 2 cooperates, in odd periods the reverse. Any departure from this rota triggers mutual defection forever.

The binding constraint belongs to whoever is due to be the victim this period, because they are the one asked to accept 1 now in exchange for 6 next time. Following the rota is worth

Deviating means defecting now and facing permanent mutual defection, worth $2/(1-\delta )$. Setting the first at least equal to the second, and cancelling a factor of $1-\delta$, gives $1+6\delta \ge 2(1+\delta )$, so $\delta \ge 0.25$.

That is a strikingly low bar, and the outcome it supports pays each player 3.5 per period, less than the 4 they would get from plain cooperation and more than the 2 of the stage equilibrium. So for any $\delta$ above 0.25 the repeated game has an equilibrium in which the players systematically take turns at exploiting each other, wasting half a point each, and neither can improve by deviating. Nothing marks it as worse than mutual cooperation from inside the model, because equilibrium is a statement about deviations, not about efficiency.

Example. Suppose mutual defection paid 3 instead of 2, leaving everything else unchanged. What happens to the threshold for the alternating scheme?

The victim's condition becomes $1+6\delta \ge 3(1+\delta )$, so $3\delta \ge 2$ and $\delta \ge 0.667$. A punishment worth 3 rather than 2 is a weaker punishment, so more patience is needed to make the same arrangement stick. Both numbers are still below the minmax check, since 3.5 exceeds the new floor of 3, so the arrangement remains individually rational, but only just.

Now you. In the original game, does the rota still work if the punishment is not permanent but lasts a single period of mutual defection, after which the rota resumes where it left off?

A theory that predicts everything

The folk theorem is usually presented as the triumphant explanation of cooperation, and it is more accurate to call it the moment the theory stops predicting.

Count what has been established. The repeated prisoner's dilemma has equilibria at mutual cooperation, at mutual defection, at alternating exploitation, at a ninety-ten division of the gains, at deliberately wasteful arrangements that nobody likes, and at every other individually rational point of a two-dimensional region. There are uncountably many equilibrium payoff vectors, and any observed pattern of long-run behaviour between two parties can be presented as one of them.

That is not a prediction. Contrast it with the zero-sum lesson, where the theory named a single number, said kickers should go left 38.5 per cent of the time, and could have been wrong. Here nothing could be observed that would embarrass the model, and a claim that cannot fail is doing no work. The multiplicity problem raised in the coordination lesson has not merely persisted, it has gone from three equilibria to a continuum.

Three responses exist and none of them is fully satisfying. One is to add a selection criterion from outside, as with focal points and risk dominance. One is to charge for complexity: Dilip Abreu and Ariel Rubinstein showed in 1988 that if strategies must be implemented by finite automata and simpler machines are cheaper, the set of equilibria shrinks sharply. The third is to stop deriving and start measuring, which is where the subject actually went.

Axelrod's tournaments

Robert Axelrod's move in 1980 was to treat the question as empirical rather than deductive. He invited people to submit computer programs to play the repeated prisoner's dilemma, ran a round robin, and asked which did well against the field that had actually turned up.

The first tournament had fourteen entries plus a random player, each pairing lasting 200 rounds, with the scoring $T=5$, $R=3$, $P=1$, $S=0$. The second, publicised on the results of the first, drew sixty-two entries from six countries, and to remove the end-game problem the length was made probabilistic, with a continuation probability of 0.99654 giving a median match of 200 moves.

Tit for tat won both. It was submitted by the psychologist Anatol Rapoport and was the shortest program entered, four lines of BASIC. Axelrod's summary of why is worth quoting in his own categories. It was nice, never the first to defect. It was provocable, retaliating immediately. It was forgiving, returning to cooperation as soon as the opponent did. And it was clear, simple enough for an opponent to work out what it was doing and therefore to see that cooperation paid.

He then ran an ecological version of the second tournament, repeating it over generations with each strategy's population share growing in proportion to its score. Tit for tat's share rose steadily. Strategies that exploited the naive did well in the first generations and then starved as their prey died out, which is a genuinely interesting mechanism and not one that any equilibrium argument had suggested.

Example. In the tournament scoring, what do tit for tat and unconditional defection score against each other over 200 rounds?

Round one, tit for tat cooperates and is defected on: 0 against 5. From then on tit for tat defects too, so both take 1 for the remaining 199 rounds. Tit for tat scores 199 and the defector scores 204. This is the fact most often left out of the popular retelling: tit for tat never beat any opponent head to head in either tournament. It won by never losing badly, while its rivals ruined each other.

Now you. Two tit for tat players meet over 200 rounds, but in round 100 one player's intended cooperation comes out as a defection. What does each score, against the 600 they would have scored without the error?

What the tournaments do and do not show

A tournament result is not a theorem, and the qualifications are substantial.

The winner depends on the field. Tit for tat won against the strategies people submitted; a field stuffed with unconditional defectors would have been won by unconditional defection, since tit for tat's advantage comes entirely from meeting other cooperative strategies. Axelrod was clear about this, and later work made it sharper: Robert Boyd and Jeffrey Lorberbaum showed in 1987 that no strategy at all is evolutionarily stable in the repeated prisoner's dilemma, so there is no final winner to be found.

Noise is worse for tit for tat than the tournaments suggested, as the exercise above shows. Two repairs do better under noise. Generous tit for tat forgives a proportion of defections at random, breaking the echo. Win-stay lose-shift, called Pavlov, repeats its last move if the outcome was good and switches if it was bad, which lets it recover from errors and also lets it exploit an unconditional cooperator, something tit for tat never does. Martin Nowak and Karl Sigmund's 1993 simulations found Pavlov displacing tit for tat once errors are allowed.

And there are strategies nobody had thought of. William Press and Freeman Dyson showed in 2012 that a class of memory-one strategies, which they called zero-determinant, can unilaterally fix a linear relationship between the two players' scores, allowing an extortionate player to guarantee themselves a fixed multiple of the opponent's surplus. Against an opponent who adapts, extortion works. Against another extortionist, both do badly. That result appeared thirty-two years after the tournaments and shows how far from closed the question was.

Where this leaves us

Repetition explains cooperation and rather too much else besides. The honest summary is that the shadow of the future makes cooperation possible without making it necessary, that which arrangement a particular pair settles into is not determined by the payoffs, and that the empirical work points to simple, retaliatory, forgiving rules rather than to anything the equilibrium arithmetic singled out.

That leaves an obvious gap. If a long relationship can support any division of the gains, what actually decides the division? The question is sharpest when the division is the whole point: two parties with a surplus of £100 to share and no way to create it except by agreeing. Equilibrium accepts every split from 0 to 100, so it says nothing at all. The next lesson takes the opposite approach and asks what properties a fair and sensible split ought to have, then shows that four modest-sounding properties pin down exactly one answer.