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:
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' DilemmaThe 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 StrategiesHere are some common strategies:
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 IPDThere 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 IPDNot 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 cooperation1 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.
1 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.
Article content copyright © James Matthews, 2001.
All content copyright © 1998-2007, Generation5 unless otherwise noted.