Tit-for-tat was beaten in the iterated prisoner’s dilemma tournament in 2005 and I only found about this now!

THE example of game theory in a nutshell:

“Two suspects, A and B, are arrested by the police. The police have insufficient evidence for a conviction, and, having separated both prisoners, visit each of them to offer the same deal: if one testifies for the prosecution against the other and the other remains silent, the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both remain silent, both prisoners are sentenced to only six months in jail for a minor charge. If each betrays the other, each receives a five-year sentence. Each prisoner must make the choice of whether to betray the other or to remain silent. However, neither prisoner knows for sure what choice the other prisoner will make. So this dilemma poses the question: How should the prisoners act?”

The dilemma:

1. If you’re one of the prisoner’s it is always “best” (in the sense of a short prison sentence) for you to betray the other person, regardless of how this person behaves.

2. This holds by symmetry for the other person too.

3. If both people act “rationally” they will  both go to jail for 5 years. Quite a lot.

4. If they both act “nicely” (and count on the other’s co-operation) they’ll be free after 6 months. Not a lot.

5. So you’ll think: Ah, so they co-operate! – Not so fast! If person A knows/assumes that person B will be nice, he has no reason to be nice himself. Unless he’s afraid of  person’s B big brother or some other form of retaliation. For a “single round” of “this game” you simply cannot “rationally” justify co-operative behavior.

But this is different, if we “play repeatedly”! Then I need your good will for the future rounds.
Suppose it’s not about serving time in prison, but about getting points, the more points the better.

If both confess, both get only 1 point.  If both co-operate (= shut up), both get 3 points. If one confesses/defects and the other co-operates/shuts up, then the person who confesses will get 5 points, the person who remained silent will get 0 points.

So now we play this game repeatedly. Then I suddenly need your co-operation in several rounds. If I betray you now, I might get 5 points, but then you’ll probably betray me in the next rounds, and I won’t be able to get more than 1 point anymore.

Funny thing: This reasoning only works, if the number of rounds is unknown!

If we know in advance that we’ll play, say, 10 rounds, then I know that in the last round you have no reason to co-operate with me. Hence, I already have no reason to be nice to you in the 9th round, as in the next round you can do what you want anyways (as there is “no tomorrow”). So neither me nor you will co-operate in the 9th round either. But then, why co-operate in the 8th round? Etc…

So this game is only fun to play, if you don’t know the number of rounds in advance, and this is exactly what was done in this tournament (where computer programs were the players/prisoners).

Ok, if you’ve followed so far, just stay with me a bit longer and you’ll get the punchline.

In this tournament, where any super complicated way of choosing to defect or to co-operate could participate, the winning strategy (i.e., the one which accumulated the most points accumulated in a number of “matches”) was a very simple one: tit-for-tat!

You start by co-operating, i.e., by playing nicely. Then you do whatever the other player did in the last move.

This is the Cold War kind of strategy: I start by not dropping by my nukes. If you didn’t drop your nukes last week, then I won’t drop my nukes this week.

Tit-for-tat … unbeaten for 20 years … fascinating … at least for a computer geek!  🙂

Finally, it was beaten 3 years ago!

But, it took a very cleverly choreographed group of 60 players to beat it. These players had some designated “slaves” and “masters”. The slaves would always sacrifice themselves when playing against one of the masters, but the slaves would be always defecting when playing against outsiders, whereas the masters would play a tit-for-tat in those cases. The really clever thing: The rules of the game usually do not leave any room for “communication”, i.e., I can’t simply tell you “Hey, I’m also in your group!”. So the program always sacrificed the first 10 moves to “communicate” through its decisions about defection or co-operation (think ‘handshake‘ if you’re a nerd).

Pretty clever, but ultimately it still seems that as an individual strategy the tit-for-tat performs best.

Advertisements