Playing again and again

Here is the Cookie Game from Chapter 2 again, the one grown-ups call the Prisoner's Dilemma. Two players each secretly choose Share or Grab. Both share: 3 cookies each. One grabs while the other shares: the grabber gets 5, the sharer gets 0. Both grab: 1 each. Grab is the dominant strategy, because whatever the other player does, grabbing gets you 2 more cookies. So both players grab, both get 1, and both stare at the 3 they could have had. Both grabbing is the only Nash equilibrium, and it is a bad one.

Now change one thing. You play the same opponent twenty times in a row, and you both remember every round. Game theorists call this a repeated game, and the memory changes everything. A grab in round 4 is not free anymore, because the other player can answer it in round 5, and 6, and 7. What might happen later changes what is smart now. There is a lovely name for this: the shadow of the future.

Robo cannot play "perfectly" here, because there is no single best way to play a repeated Cookie Game: how good a move is depends on who you are playing. So Robo follows a strategy, a fixed rule that decides every move, and you pick which one. Play a few. Then choose Mystery Robo, which picks a strategy in secret, and work out which one it is from the way it answers you. A well-placed grab tells you a lot.

Tit for Tat is this: share in round 1, and after that do whatever the other player did in the round before. That is the whole strategy. In 1980 a political scientist named Robert Axelrod ran a computer tournament in which strategies played the repeated Cookie Game against each other. Tit for Tat, the shortest program anyone sent in, won. Axelrod published the results, ran a second and bigger tournament, and it won again.

He looked at what the strategies near the top had in common and found four things.

• Nice. Never grab first. In the first tournament the top eight strategies were all nice, and none of the others were.
• Retaliating (say: ri-TAL-ee-ay-ting). If the other player grabs, grab right back. Always Share never punishes, and gets eaten.
• Forgiving. When they go back to sharing, go back to sharing. Grudger never forgives, and loses the rest of the game over one bad round.
• Clear. Be easy to figure out. If the other player can work out your rule in a few rounds, they can also work out that sharing with you is their best plan.

Tit for Tat has all four, and one strange property besides: you can never beat it by much. Here is the proof.

So Tit for Tat never beats anybody: head to head, it ties or loses by 5. It wins tournaments because a tournament is not scored by who beats whom. It is scored by your total. Tit for Tat collects 3 a round from every opponent willing to share, is never a sucker for more than one round, and goes straight back to 3 a round when the other player does. The strategies that "beat" it by 5 spend the rest of the tournament collecting 1s from each other. That is the lesson of this chapter: do not try to beat the other player. Try to score well.

Here is your own version of Axelrod's tournament. Every strategy you tick plays every other one, and a copy of itself, for a set number of rounds. Highest total wins. The default is 200 rounds because that is what Axelrod used in his first tournament, and Random is in the field because he put one in his.

Look closely at the result. In this field Grudger usually finishes a little ahead of Tit for Tat, and the whole gap comes from Random: after Random's first grab, Grudger grabs forever and collects 5 or 1 from every coin flip, 3 a round on average, while Tit for Tat, copying a coin, gets only 2.25. Untick Random and the two tie exactly, because against everyone else here they make identical moves. Who wins depends on who is in the field. Axelrod's was full of clever programs trying to take advantage of each other, and in that crowd Tit for Tat came out on top.

Then there is the noise slider. In real life hands slip and signals get misread: you meant to share and the other player saw a grab. Noise gives every move a small chance of being flipped by mistake. Set it to 5% and watch the "vs itself" column. Tit for Tat playing its own copy drops from 3 a round to about 2.3: one mistaken grab gets answered, the answer gets answered, and the two copies take turns punishing each other for a mistake nobody meant. Tit for Two Tats ignores a single mistake and stays near 2.95. Pavlov wobbles for two rounds, finds its way back to sharing, and stays near 2.8. Untick Random, set the noise to 2 or 3 percent, and run it several times: Pavlov and Tit for Two Tats each finish above Tit for Tat about three runs out of four. Push the noise to 10% and Grudger and Always Grab climb to the top instead: when mistakes are everywhere, most matches collapse into mutual grabbing sooner or later, and the strategies that were grabbing anyway lose the least.

You can also build a strategy of your own: its first move, what it does after the other player shared, and what it does after they grabbed. That covers every strategy that remembers exactly one round back, 2 × 2 × 2 = 8 of them, and some are ones you already know. Change any of the three choices and your creation enters as Yours.

Now a puzzle that has bothered game theorists for a long time. Suppose both players know for certain that the game ends after round 20. Think backwards, the way you did in Chapter 5. In round 20 there is no tomorrow, nothing to punish and nothing to reward: Grab is dominant, so both players grab. But then round 19 has no future either, because round 20 is already settled as a grab whatever you do. So grab in 19. And in 18. It unravels all the way back to round 1. With an ending everybody knows about, backward induction says grab every round, and the shadow of the future is gone.

Real people do not do this. In experiments, people who play a fixed number of rounds mostly share, and start grabbing near the end if at all. The unraveling needs both players to be certain about the ending, and certain that the other is certain, and so on (Chapter 18 is about that). The fix game theorists use is simpler: make the ending uncertain. After every round, roll for whether there is another one: the game continues with probability p and ends with probability 1 - p. Now no round is ever known to be the last, and the shadow of the future never goes away.