A game without prisoners
Merrill Flood and Melvin Dresher at the RAND Corporation devised the game as a mathematical problem. Albert Tucker later invented the story of two suspects under questioning, and that story gave the game its name.
Two players choose at the same time: cooperate or defect. If both cooperate, each gets 3 points. A defector against a cooperator takes 5, and the cooperator gets 0. If both defect, each gets 1. The political scientist Robert Axelrod ran a tournament: programs played this game for 200 rounds, each against each. Which strategy scored the most points?
Tit for Tat, by the mathematician Anatol Rapoport: cooperate on the first move, then repeat the other player's last move. It never outscored its opponent in a single match, because it never defects first. But in total it collected the most: 504 points per match on average. Then it won the second tournament too, with 62 entrants.
Let's start with a single game, then repeat it many times.
Two players choose one of two moves at the same time and independently: cooperate or defect. The table on the right gives the points. The name comes from a story about two suspects questioned separately: each is offered a shorter sentence for testifying against the other.
If the other player cooperates, you do better by defecting: 5 beats 3. If the other defects, defecting is still better: 1 beats 0. So in a single round defecting is better whatever the other does. But when both reason this way, each gets 1 when they could have had 3.
The same two play 200 rounds in a row. Before each round both see how everyone moved so far. Points from all rounds add up. Two players who always cooperate get 600 points each; two who always defect get 200 each.
The entrants are programs, each with its own strategy. Each plays a match against every other, and against a copy of itself. The winner is not whoever won the most matches but whoever scored the most points in total.
Which strategy scores the most points in such a tournament?
"A clever strategy that knows how to cheat will win"
There were clever programs in the tournament, and they lost. Tit for Tat won, the simplest of the programs entered: it never defects first, answers defection with defection and cooperation with cooperation.
A round robin, every match 200 rounds, many different entrants. Lock in your answer before reading on.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
Work out what two players get in a 200-round match if they always cooperate, and what two get if they always defect. How big is the gap?
A tournament counts your points, not whether you beat your opponent. Does winning a match matter if both of you scored little in it?
Picture an opponent who answers a defection with a defection on the next move. What does defecting against it get you two rounds later? And what does defecting get you against someone who never strikes back?
You play a match against a bot: each round you choose to cooperate or defect, and the bot moves at the same time. You don't know how many rounds the match has: 8 to 12. After the match, guess which strategy the bot had. The list of strategies is alongside.
Each chosen strategy plays every other one and its own copy for 200 rounds. The bar is the exact average points per match: the page works out the probabilities of all moves round by round. The tick is the simulation: 50 tournaments played with random moves. Noise means each move is flipped by accident with that probability: meant to cooperate, defected instead, and vice versa.
The same entrants, but now they are shares of a population. Each generation a strategy's share grows in proportion to how many points it scores against the current mix. This is how Axelrod checked who survives once the losers gradually die out.
A tournament counts your points, not your margin over the other player. So what pays is not beating the other but letting both of you score a lot.
“In plain words” is hidden on all puzzles.
Let's start with a simple, if incomplete, explanation. The defector never loses a match: against Tit for Tat it takes 204 points to 199. But 204 is a pittance: two cooperators get 600 each. Tit for Tat loses a few points to every defector but earns the most with everyone willing to cooperate.
Clever programs in Axelrod's tournaments often failed on the third and fourth traits: their attempts to defect "just a little" set off long chains of mutual retaliation.
“Rigorous” is hidden on all puzzles.
The row is a strategy, the column its opponent, and each cell holds the row's average points per 200-round match. Green marks matches where the row scored more than its opponent, red where it scored less. Tit for Tat's row has no green cell at all: it beats nobody. But against half of its opponents it scores 599 or 600, and its worst cell is 199, while the Dove's is 0 and Tit for Two Tats' is 198.
In a single round defecting dominates: whatever the other does, it gives 2 points more (5 versus 3) or 1 more (1 versus 0). But in a repeated game your move changes the other's next moves. Defecting against Tit for Tat gives +2 now and costs you in the next round when it answers with a defection: you get 0 instead of 3 if you go back to cooperating, or 1 instead of 3 if you keep defecting.
That is why it matters who else is in the tournament. If many strategies around you retaliate, defecting only pays in the last round. If everyone around is a pushover, always defecting pays: in round 3 you can see this by switching on "Naive field".
Let the game go on after each round with probability w. You play against Tit for Tat. The expected points of three plans:
Cooperating is no worse than both other plans when
Here T = 5 (temptation), R = 3 (reward), P = 1 (punishment), S = 0 (sucker). Axelrod called this condition the shadow of the future: cooperation is stable when the next meeting is likely enough. If the last game is known in advance, the shadow is gone: defecting pays in the last round, then in the one before, and so on back to the first.
“Deeper” is hidden on all puzzles.
The game was devised by Merrill Flood and Melvin Dresher at the RAND Corporation in 1950, and the mathematician Albert Tucker added the story about prisoners. For the first tournament Axelrod gathered 14 programs from scientists who studied the game and added a fifteenth, random one. Tit for Tat averaged 504 points per match and came first, although by matches won it was last: it won none.
Before the second tournament the entrants already knew the results and the analysis. 62 programs came in, plus the random one, and the number of rounds was not announced in advance. Rapoport sent Tit for Tat again, and it won again. Axelrod described both tournaments in the Journal of Conflict Resolution in 1980, and in 1984 he published the book The Evolution of Cooperation.
In Axelrod's tournaments moves were carried out without mistakes. If a move flips by accident even rarely, two copies of Tit for Tat punish each other in turn after one slip. In 1992 Martin Nowak and Karl Sigmund showed in Nature, in a model with a mixed population, that Tit for Tat helps cooperation emerge but is then displaced by a more generous strategy that sometimes cooperates even after the other defected. For the points 3, 0, 5, 1 that generosity is usually taken as 1 in 3. In 1993 the same authors described the strategy "win-stay, lose-shift", often called Pavlov: it also recovers quickly from mistakes.
There is no best strategy for the repeated prisoner's dilemma: everything depends on who else plays. Against nothing but Defectors it is better to defect, and against nothing but Doves too. In 2015 the psychologists Amnon Rapoport, Darryl Seale and Andrew Colman replayed Axelrod's first tournament under other rules and showed that Tit for Tat's win depends on the format, the criterion of success and the numbers in the payoff table. We checked this on our own field of 10 strategies without noise: of the 502 possible line-ups with Tit for Tat and at least three entrants, it is first or shares first in 244.
In 2012 the physicists William Press and Freeman Dyson found "zero-determinant strategies" in this game. Some of them are extortion: they force any opponent who adapts to them to hand over the larger share of the payoff. Tit for Tat is a special, fair case in this class: it splits the points evenly.
Mathematically we'll see what even a rare mistake does to Tit for Tat. Logically, why a repeated game changes the choice at all. And in practice we'll check when it pays to cheat a partner you deal with every month.
Mathematics
Lines: points per round in a very long game against the noise level; the dashed line is the slider's noise.
Each copy repeats the other's last move. One accidental defection starts an echo: defection, reply, reply to the reply. The next mistake may bring back cooperation or lock in mutual defection. In a very long game all four pairs of moves occur equally often, so the average is (3 + 0 + 5 + 1) / 4 = 2.25 points per round, whatever the rate of mistakes. Rare mistakes only stretch out the road to that average.
Generous Tit for Tat and Pavlov escape the echo within a few rounds and, while mistakes are rare, stay near 3. The Grudger defects forever after the first mistake and slides almost to 1. The table computes this exactly: for 200 rounds and for a very long game.
Logic
You play against Tit for Tat, and after each round the game goes on with probability w. Defecting for good pays while w is below 1/4. Between 1/4 and 2/3 it pays to alternate defection and cooperation: Tit for Tat always answers one move late, and you take 5 whenever it cooperates. From 2/3 up, cooperating all the time is best. The idea goes beyond this game: two people who are sure to meet again behave differently from strangers meeting once.
Practice
The model is simple: while you are honest, your partner is honest; after you cheat, they never trust you again. Check it on an example: 10 thousand a month honestly, 25 thousand once for cheating, 2 thousand a month after that, a 90% chance of another month. Honesty gives on average 10 / (1 − 0.9) = 100 thousand, cheating 25 + 0.9 · 2 / 0.1 = 43 thousand. Cheating would pay only if the chance of going on were below (25 − 10) / (25 − 2) ≈ 65%.
Axelrod's best-known example is the trenches of the First World War. Battalions faced the same enemies for months, and in many sectors a "live and let live" system arose: no shelling of kitchens and supply wagons, no firing at certain hours, but answering one shot with several. Axelrod drew on the study by the British sociologist Tony Ashworth. The system broke down when headquarters began ordering raids that could not be quietly faked: every raid was answered, and retaliation escalated.
Merrill Flood and Melvin Dresher at the RAND Corporation devised the game as a mathematical problem. Albert Tucker later invented the story of two suspects under questioning, and that story gave the game its name.
Axelrod invited programs from scientists who had already studied the prisoner's dilemma and added a random one to the 14 entries. Each pair played 200 rounds.
By matches won, Tit for Tat came last in the first tournament. It cannot outscore its opponent: it only defects in reply.
Before the second tournament the entrants knew that Tit for Tat had won the first. Axelrod worked out that Tit for Two Tats, which retaliates only after two defections in a row, would have won the first tournament. It was entered in the second, but Tit for Tat came out ahead again.
In 2004, at a tournament for the 20th anniversary of Axelrod's book, a University of Southampton team entered 60 programs. They recognised each other by a coded sequence of opening moves, and the "slaves" cooperated while the "master" defected. Three of them took top places.
The physicist Freeman Dyson and the astrophysicist William Press showed that a player who remembers only the previous round can tie the opponent's points to its own by a linear rule and so extort the larger share.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
Is “School maths” the right level for this puzzle?
Thank you! This helps set the levels right.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.