26 February 1997

Building on my previous foray into paradoxical situations, I choose to focus this week on one of the most interesting, applicable, and insoluble problems of all; the Prisoner's Dilemma. Credited to Melvin Dresher and Merrill Flood, the Prisoner's Dilemma is a classic example from the research field of Game Theory. Game Theory has officially existed for quite some time; John von Neumann proved the basic minimax theorem¹ in 1928. The Prisoner's Dilemma, while a trivial example in many respects, is a fascinating study in logic and a useful stepping-stone to more complex discussions on Game Theory. The principles behind it are relevant to many fields, including sociology, philosophy and political science. Consider, then, the following situation:

You (also known as P1²) and your friend (P2³) are trapped in a dank, gloomy dungeon awaiting sentencing for committing a most heinous crime. Amidst the clanking chains, scampering rodentia, and endlessly dripping water, a welcome light shines upon your forehead. The only door to the dungeon cell swings open, and a guard peers through the cobwebs spanning the door frame. He clambers inside and drags you out after him, mercilessly scraping your shins on the stones in his haste.

The guard wishes to determine whether you and your friend committed the crime in question. He leers evilly, snickering as he describes the punishment to be doled out:

In this table, called a Payoff Matrix, "Cooperate" means the prisoner chooses to remain silent when queried about the crime. "Defect" means the prisoner confesses guilt, implicating the other prisoner in the crime as well. The "Payoff" represents the number of years the prisoners will be forced to spend in jail as a result of their actions. Payoffs are negative here as they represent a loss, rather than a gain.

You should first note that the punishment depends on both your response and that of your friend. The punishments seem oddly biased, do they not? In the interest of minimizing the prison time for both you and your friend, you would like to cooperate with him, staying silent and hoping he remains silent as well. However, if your friend were to take advantage of your silence and proclaim guilt, he would suffer no prison time while you would find yourself incarcerated for the maximum prison sentence. This situation is easily reversed; should you, then, take advantage of your friend's possible trust and declare guilt in an attempt to avoid any prison time? Worst of all, if you both attempt to take advantage of each other's expected trust, you will both be jailed⁴ for a substantial, non-minimal period of time. A quandary, indeed!

The crucial realization is that each prisoner can gain by double-crossing the other. You have no opportunity to speak with your friend, and so you cannot come to any agreement in advance. As you puzzle and weigh the decisions, a glittering whirlwind of electrons forms about you and your computer. You suddenly find yourself swimming in Java as you live and breathe the Iterated Prisoner's Dilemma!.

In this first instance of the Prisoner's Dilemma, your friend randomly chooses whether to cooperate or defect. You should quickly discover that you're generally best off if you always defect⁵ so as to limit your potential prison time to either 0 or 2 years. Isn't it naturally desirable, though, for you and your friend to help each other out? Were you both to cooperate, you would each spend only 1 year in jail⁶. The crux of the dilemma revolves around the lack of trust between the two prisoners. Unfortunately, it is this distrust which often leads to non-optimal actions and results for all those involved.

Preventive Measures in the Face of Perpetual Punishment

The Tit-For-Tat strategy is one well-known way to deal with the Prisoner's Dilemma. In this technique the player initially cooperates, but as soon as the other prisoner defects the first prisoner retaliates in kind. In essence, the player using this strategy simply cooperates initially, and thereafter duplicates the other prisoner's action from the previous round. Despite the apparent simplicity, this will always remove any disparity between the prisoners' "total punishment amount," beating out many far more complex strategies. However, it will never allow the player to surpass his opponent. The ever-nifty Java programming language allows us to once again demonstrate the Prisoner's Dilemma, but this time the player is confronted with a wily Tit-For-Tat opponent. Egads!

We demonstrate other simple strategies for the Prisoner's Dilemma here; the Golden Rule, in which the player always cooperates, and the Iron Rule, in which the player always defects. After trying the Java demonstrations of each, it should be clear that a perpetually-cooperating P2 is easily taken advantage of; P1 may forever defect, earning no prison time while the "sucker" prisoner P2 accumulates prison time rapidly. Similarly, a hard-nosed P2 bent on always defecting leaves P1 with no better choice than to resign himself to sharing an equal, non-minimal amount of prison time with P2.

The intriguing point here is to note that most, or even all, of the preceding discussion of choices and decisions map directly onto innumerable real-world situations. This includes almost any scenario in which the "payoff" with respect to certain actions is in favor of one person over another. Specific examples include such surprises⁷ as business, love, and software development.

Pandora's Box of Dilemmas

The interested reader should be sure to utilize go2search, as there is a wealth of information available on the web regarding Game Theory and various well-known dilemmas. There are also a great many books available in your local bookstore or library ; one which comes highly recommended is Robert Axelrod's The Evolution of Cooperation.

Some of the more relevant and engaging web sites include:

* B. Brembs discusses Chaos, Cheating and Cooperation: Potential Solutions to the Prisoner's Dilemma. This is a must-read for those interested in a multitude of real-world examples of the Iterated Prisoner's Dilemma.

* The Ethical Spectacle is home to a range of interesting articles pertaining to the Prisoner's Dilemma, related problems, applications, and studies. Some are linked to in this article; all are worth reading.

* Patrick Grim's "Undecidability in the Spatialized Prisoner's Dilemma" research utilizes a cellular automata (the topic of a previous Deep Magic article) to generate graphical displays in support of his findings.

* Xerox PARC's Dynamics of Computation Area has information on detailed computer modeling of issues relating to cooperation, along with many related research papers and links.

In conclusion, I might argue⁸ that there is at least one pure solution to the class of dilemmas presented in this article. Indeed, in The Princess Bride, the Dread Pirate Roberts uses careful planning and forethought to triumph in one particular scene. We would do well to take the Pirate's lesson to heart; learn to overcome even utter defeat, and the world is truly your oyster.

-- Walter <shaper@cerf.net> has, thus far, always cooperated, but soon expects to defect.

Source code to the applet written for this article as a gzipped tar file.