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.