At the forefront of Artificial Intelligence

Iterated Prisoner's Dilemma

The Prisoner's Dilemma (PD) and Iterated Prisoner's Dilemma (IPD) are classic examples of interesting cases of game theory. This essay should introduce you to the basics of the (I)PD and why it is interesting in Artificial Intelligence.

Go To Jail...

You and your friend have just been arrested and thrown into separate cells, so you cannot communicate with each other. Now, the prosecutor comes to you and puts the following deal on the table. If you both plead innocent to the crime, you will be placed in jail for 1 year. If you both plead guilty, you will be jailed for 5 years. Yet, if you defect and testify against your partner, we will set you free, but give your partner 25 years in jail. You are then told your partner has been offered the exact same deal. The table below shows how many years you will get for the four different outcomes:

Partner pleads innocent Partner pleads guilty

You plead innocent 1 years 25 years

You plead guilty 0 years 5 years

This is called the Prisoners' Dilemma. You can see the dilemma comes in because you really should make your decision based upon what your partner does. Defecting is probably the best route to take since you will get a maximum of 5 years, compared to cooperating which could lead to 25. Nevertheless, this isn't very interesting - but what happens when we iterate this process?

Let us disgard "Go to jail" analogy, since it will lead to confusion. Instead, we have the same basic setup: you can cooperate and defect, as can your partner, and the point is to score as few points as possible. Now that we are repeating this process for x number of iterations, what is the best course of action to take? This is called the Iterated Prisoners' Dilemma.

Iterated Prisoners' Dilemma

The problem is now that choices in one move might affect the future choices of your partner. For example, if you defect against him, he will most likely defect against you in the next round. So, is this alternating method the best?

This all depends on whether you are playing the same partner, and depends on how crafty your partner is. If you partner can predict what you are going to do, he can always counter it. So now we have to look at Iterated PD strategies.

Common IPD Strategies

Here are some common strategies:

All C: Always cooperates.
All D: Always defects.
Tit for Tat: Start by cooperating, then play what partner played in his/her last move.
Spiteful: Cooperate until partner defects, subsequently always defect.
Pavlov: Cooperates if and only if both players choose the same option in the previous move.
TF2T: (Tit-for-Two-Tats) Cooperates except if opponent has defected twice consecutively.
Random: Randomly plays.

Note that this list is by no means comprehensive. We can then pit these strategies against one another to see how they fare. The first official tournament was arranged by Rovert Axelrod, and some rather interesting results came from it. It seemed that the Tit-For-Tat strategy was the strongest (although, TF2T would have beaten it, if it had been entered). It was also shown that strategies that were "nice" (cooperated first) would also come out on top.

A second tournament was organized which TFT also won, and finally a third more "ecologically" inspired tournament was bested by TFT again! It was found that TFT didn't work as well in "noisy" conditions (random or probabilistic), but other strategies such as "Pavlov" did.

Expansions on the IPD

Spatial IPD: taken from VIPD (used with permission)

There has been a lot of research into expansions on the IPD, most of which involve some form of Artificial Intelligence to predict or mimick the opponent.

The most interesting variation of the IPD though is the spatial IPD. Basically, this involves populating a grid with IPD strategies and making them compete against each other. Strategies that win multiply and take over the competitors' places. If a form of visualization is used, spatialized IPDs are great for looking at how the IPD interact "socially". The screenshot at the right was taken from VIPD, a Java applet that allows you to set up and run a spatial IPD.

We can now see ties starting to appear between the IPD and Artificial Intelligence and Artificial Life. The spatial IPD is basically a 2-dimensional cellular automata. There has also been a significant amount of research into genetically evolving IPD opponents.

Uses of the IPD

Not only is the IPD interesting from a mathematical and theoritical perspective, using a spatial IPD the problem can be seen as a cellular automata and used to abstract concepts such as cooperation in nature.

Actually, the spatial IPD has been used to show that non-kin cooperation¹ is not as paradoxical as it might initially seem. As long as there is some form of repeated encounters between strategies and they exhibit some form of flexible behaviour and recognition of previous opponents, it can be seen why cooperation is favoured.

Using this, the ideas and theories derived from IPD research have increased into the evolution of intelligence, social interaction and much more. While this may be taking a simple analogy too far, it is easy to see how useful the IPD analogy is.

¹ What this refers to is the fact that nature exhibits a lot of instances whereby an individual does some good for something else at it's own cost (i.e., maternal instinct to save children). Given the individualistic nature of evolutionary competition, it seems paradoxical that beyond the idea of protecting one's kin, individuals are still willing to sacrifice.

• IPD Home Page - Has some excellent software for competing IPD strategies.
• Genetic Algorithm for Iterated Prisoners Dilemma - Very interesting Java applet
• Complexity Central - Has a cool Java applet for visualizing a spatial IPD.

Submitted: 09/03/2001

Article Toolbar

BibTeX entry