Prisoner's Dilemma

https://arbital.com/p/prisoners_dilemma

by Eliezer Yudkowsky Aug 1 2016

You and an accomplice have been arrested. Both of you must decide, in isolation, whether to testify against the other prisoner--which subtracts one year from your sentence, and adds two to theirs.


[summary: In the original Prisoner's Dilemma, you and a confederate have been arrested for a crime. You are each facing one year in prison. Each of you, in isolation, is offered the chance to testify against the other. If you testify, it will subtract one year from your sentence and add two years to the others' sentence.

You can't communicate and have no means of enforcing an agreement. What do you do?

The Prisoner's Dilemma is a central example in game theory, economics, and decision theory.

For somewhat more realistic scenarios that evade common objections, see True Prisoner's Dilemma.]

[summary(Technical): The Prisoner's Dilemma is a game played by two agents in which no [nash_equilibrium] is [pareto_optimum Pareto optimal]. The two moves are standardly denoted Defect ($~$D$~$) and Cooperate ($~$C$~$). The payoffs $~$(p_1, p_2)$~$ for Player 1 and Player 2 respectively are:

$$~$\begin{array}{r|c|c} & D_2 & C_2 \\ \hline D_1 & (\$1, \$1) & (\$3, \$0) \\ \hline C_1 & (\$0, \$3) & (\$2, \$2) \end{array}$~$$

Each agent is better off playing Defect than Cooperate, regardless of the other agent's move. But both agents prefer the outcome of mutual Cooperation to the outcome of mutual Defection.

The Prisoner's Dilemma is an archetypal example of a [commons_problem] or [coordination_problem]. The conclusion that two rational agents must Defect against each other, even knowing that the other agent is also rational and hence will probably come to the same decision, was challenged by Hofstadter's 'superrationality' and later by logical decision theory.

An important variant is the [iterated_prisoners_dilemma].]

Setup and payoffs

In the classic presentation of the Prisoner's Dilemma, you and your fellow bank robber have been arrested and imprisoned. You cannot communicate with each other. You are facing a prison sentence of one year each. Both of you have been offered a chance to betray the other (Defect); someone who Defects gets one year off their own prison sentence, but adds two years onto the other person's prison sentence. Alternatively, you can Cooperate with the other prisoner by remaining silent.

So:

Or in the form of an outcome matrix where $~$(o_1, o_2)$~$ is the outcome for Player 1 and Player 2 respectively:

$$~$\begin{array}{r|c|c} & \text{ Player 2 Defects: } & \text{ Player 2 Cooperates: }\\ \hline \text{ Player 1 Defects: }& \text{ (2 years, 2 years) } & \text{ (0 years, 3 years) } \\ \hline \text{ Player 1 Cooperates: } & \text{ (3 years, 0 years) } & \text{ (1 year, 1 year) } \end{array}$~$$

As usual, we assume:

(For scenarios that would reproduce the resulting ideal structure with more realistic human motives and situations, see True Prisoner's Dilemma.)

Then we can rewrite the Prisoner's Dilemma as a game with moves $~$D$~$ and $~$C,$~$ and positive payoffs where \$X denotes "X utility":

$$~$\begin{array}{r|c|c} & D_2 & C_2 \\ \hline D_1 & (\$1, \$1) & (\$3, \$0) \\ \hline C_1 & (\$0, \$3) & (\$2, \$2) \end{array}$~$$

Significance

In the Prisoner's Dilemma, each player is individually better off Defecting, regardless of what the other player does. However, both players prefer the outcome of mutual Cooperation to the outcome from mutual Defection; that is, the game's only [nash_equilibrium Nash equilibrium] is not [pareto_optimum Pareto optimal]. The Prisoner's Dilemma is therefore an archetypal example of a [coordination_problem coordination problem].

The Prisoner's Dilemma provoked an enormous amount of debate, mainly due to the tension between those who accepted that it was reasonable or 'rational' to Defect in the Prisoner's Dilemma, and those who found it hard to believe that two reasonable or 'rational' agents would have no choice except to helplessly Defect against each other.

The iterated_prisoners_dilemma Iterated Prisoner's Dilemma was another important development in the debate--instead of two agents playing the Prisoner's Dilemma once, we can suppose that they play the PD against each other 100 times in a row. Another development was 'tournaments', run on a computer, in which many programmed strategies play the Prisoner's Dilemma against every other program. Combined, these yield an IPD tournament, and almost every IPD tournament--whatever the variations--has been won by some variant or another of Tit for Tat, a strategy which Cooperates on the first round and on each successive round just plays whatever the opponent played previously.

Examining such tournaments has yielded the conclusion that strategies should be 'nice' (not be the first to Defect, i.e., not play Defect for the opponent has played Defect), 'retaliatory' (Cooperate less when the opponent Defects) and 'forgiving' (not go on Defecting forever after the opponent Defects once).

The strategy in Tit for Tat stands in contrast to the conclusion that it is reasonable to Defect in the oneshot Prisoner's Dilemma. Indeed, it stands in contrast to the supposedly 'rational' (on some views) strategy in the Iterated Prisoner's Dilemma. If the game is to be played 100 times, then clearly it is 'rational' to play Defect on the last and 100th round. But if both players are 'rational' and know that the other is 'rational', they both know the other player will reason this way and Defect on the 100th round. Then since play in the 100th round is insensitive to play on the 99th round, both agents reason that they should Defect on the 99th round, and so by induction they both Defect on the 1st and every successive round.

This conclusion has been challenged from many directions, on both the oneshot and iterated Prisoner's Dilemma. Douglas Hofstadter observed that two rational agents should both realize that there is only one 'rational' conclusion, whatever that conclusion is; Hofstadter proposed 'superrationality' as rationality taking into account that superrational agents facing similar problems must arrive at similar conclusions. Logical decision theory, which says that the principle of rational choice is to decide as if choosing the logical output of your decision algorithm, can be seen as generalizing this viewpoint. Logical decision theorists have also shown that if the agents in the Prisoner's Dilemma have common knowledge of each other's algorithms, they can end up cooperating (and this works even if the two agents are not identical).