3

## Prisoner's Dilemma

Published on Sunday, May 27, 2007 in , , , , ,

Imagine you and another person are arrested by the police. The police don't have sufficient evidence for a conviction, so the police split you and this other person up into different rooms. They offer you and the other person the same deal. If both you and the other person stay silent, both of you will wind up spending 6 months in jail (the police have enough evidence for a lesser charge). If both you and the other person agree to testify against each other, you will both spend the next 2 years in jail. If one agrees to testify for the prosecution, and the other person remains silent, the one who testifies will go free, while the one who remains silent will go to jail for 10 years.

Considering that you can't know what choice the other person is going to make, what is the best choice you can make to minimize your jail time?

This is a classic puzzle known as the Prisoner's Dilemma. The version stated as above has a very simple solution. If you stay silent, you'll either serve 6 months or 10 years. If you testify against the other person, you'll either serve 2 years or go free. Obviously, the better choice is to testify against the other person.

This seems fairly obvious, and doesn't seem like much of a puzzle. Perhaps it needs one more aspect to make it more interesting.

Imagine this is done not just once, but repeated numerous times (perhaps both you and the other person have been charged with numerous crimes). Only after you have made your choice each time, and before the next round, are you told the other person's choice. Now, what is your best strategy?

This makes it a bit more difficult, doesn't it? This variation is known as the iterated prisoner's dilemma. Before we discuss the best strategy for this version, try some online simulations to see if you can work it out for yourself. You can try out a version using the reward of gold coins. If this doesn't help, and you have Java installed, try another version that allows you to control the other person's strategy.

If the Monte Carlo method gives you trouble, perhaps applying the Nash equilibrium might help. True, the article might be a bit long, but here is the basic idea of the Nash equilibrium, from the movie A Beautiful Mind.

Have you figured it out yet? If not, I'll let Charlie Eppes (David Krumholtz) explain the optimum strategy, from the The Art of Reckoning episode of Numb3rs, with a great rock-climbing analogy:

Yes, Tit For Tat is the best overall strategy. However, there is one strategy that beat it out in the Prisoner's Dilemma competition. A team from Southampton University created the programs that did just that.

How is this possible? The Southampton strategy was to submit 60 programs. Each of the programs was able to recognize the others by the sequence of the first 5-10 choices made. If a Southampton program recognized another Southampton program, one of the programs would always choose to cooperate with the police, while the other one would always choose to remain silent. If a Southampton program realized it was playing a non-Southampton program, it would always choose to cooperate with the police, thereby minimizing the score of the competing program. This strategy took the top three places in the competition when it was applied, not to mention numerous places at the bottom for the programs that would consistently stay silent.

So why do people still claim Tit For Tat is the best? In the classic iterated problem, it is assumed that you only have control of your own actions, and have not pre-arranged a code with the other person (as you were separated before the offer was first made).

To wind up this post, I'd like to point you to Bill Whittle's site, in which he discusses the philosophical implications of the prisoner's dilemma. If you haven't visited this site before, I also suggest you explore the previous entries, too. His essays and even his simple posts are always clear and thought-provoking.

### 3 Response to Prisoner's Dilemma

Anonymous
8:40 AM

the prisoner's dilemma is an amazing source of fascination, i agree, and thanks for the article.

i do disagree a little, though, with your statement that the one-time iteration of the situation is uninteresting because the answer (cooperate with the police) is obvious.

it's obvious for the individual, but raymond smullyan (in a lecture i saw) notes that this does not produce the best overall possible result for you and your partner, and that axiomatically, this is something of a contradiction, since we have been making the assumption that you will strive for the best possible result, which you now haven't acheived!

11:36 AM

I also like Friend or Foe on the Game Show Network. Similar rules: A team of two players earns some money by answering some questions, then they are brought up an dbot have to select (secretly) friend or foe. If they both do friend, they split the money. If they both do foe, no one gets any money. Finally if one does friend and the other foe, then the one who does foe gets all of the money.

Polymath's point is a bit more dramatic here, if everyone did the best strategy, then no one would get any money at all!

2:49 PM

Prisoner's Dilemmas are everywhere, if you know how to recognize them. I witnessed one while being on vacation:
Prisoner's Dilemma at the swimming pool
Luckily in many PDs in daily life, people tend to cooperate. But if everybody defects, you can only play the game the same way...