Saturday, July 21, 2012

A Twist in the Prisoner's Dilemma

Prisoner's dilemma is a famous model in game theory, which in a basic form can be asserted as:
Two men are arrested, but the police do not possess enough information for a conviction. Following the separation of the two men, the police offer both a similar deal—if one testifies against his partner (defects/betrays), and the other remains silent (cooperates/assists), the betrayer goes free and the one that remains silent receives the full one-year sentence. If both remain silent, both are sentenced to only one month in jail for a minor charge. If each 'rats out' the other, each receives a three-month sentence. Each prisoner must choose either to betray or remain silent; the decision of each is kept quiet. What should they do?
Despite its apparent simplicity, it is used as a model in places you probably wouldn't imagine it to be.

The solution to this one-off game is quite simple (if depressing). You should not cooperate.

A more interesting version is the iterated prisoners dilemma, where the game is played over and over again. For the longest time (since I took a course in game theory about 10 years ago), it was always assumed that, empirically, a simple strategy like "tit-for-tat" offered a decent balance between simplicity and effectiveness.

Turns out that there is a new twist in the plot.

William Press (of Numerical Recipes fame) and Freeman Dyson ("the") recently published a paper in PNAS (open access) that seems to be getting a lot of attention.

There is a nice commentary (pdf) that is easy to follow for those of us, who have an undergrad-level understanding of the problem.

No comments: