30 November 2010

Prisoner's Dilemma: Game Theory for Noobs

The Prisoner's Dilemma is a fairly famous scenario in game theory. The dilemma occurs when two alleged criminals are captured by the authorities. Both suspects are handled by some tough customers in their own holding cells, but the police do not have enough evidence to put either of them away for good just yet. In order for either of the suspects to go to jail for a significant time, the other has to deliver testimony. The authorities are stuck between a rock and a hard place, so they come up with a plea bargain.

Should you take the plea bargain?

The plea bargain gives each captured suspect a few options:
  • Deliver testimony while your partner keeps silent, get out of jail free and leave your partner rotting in jail for a full decade.

  • Both keep silent. If your partner doesn't spill the beans, this is the best scenario for both of you as the police wouldn't have enough on you to put either of you away for good, but both of you would spend 6 months in prison.

  • Spill the beans, have your partner spill the beans and share the decade between you. Both of you would thus spend 5 years imprisoned. Time to learn the harmonica and get used to orange jumpsuits.

Should you take the plea bargain, or hope that your partner in crime shuts up too?

Greed is good for you

It turns out that the best course of action is to cooperate with the police and leave your friend to maybe rot in jail. You might think that being selfish and greedy is bad and that you should consider other people's feelings. If you do think so, you are wrong in this case. Wrong because defecting from your partner and cooperating with the police is a dominant strategy. A dominant strategy is a strategy that is a clear winner, regardless of how you feel about it and what else you consider in your equation. Why is this?

To see why, it is often helpful to construct a normal form (or payoff matrix) representation of the strategy. This is the normal form of our prisoner's dilemma:

prisoners dilemma game theory payoff matrix normal form

I found the normal form of the prisoner's dilemma confusing, because it seems unnatural to me to label cooperation with the authorities as cooperation from the viewpoint of allegedly hardened criminals. Surely, cooperation should refer to honour amongst thieves and defection to cooperation with the authorities? Regardless, cooperation here means defaulting on your accomplice's friendship and signing whatever the police put in front of you. To defect means to keep your mouth shut least you sleep with the fishes.

To see why cooperation with the police is clearly dominant strategy, count the numbers for each player in each column. I have colour coded them for your benefit. Since most people would like to spend the least amount of time possible in prison, the column with the lowest number is the dominant strategy.

Danica McKellar model mathematics hot and smart

Unless of course you are lucky enough to get locked up with Danica McKellar and she could explain mathematics to you.

27 November 2010

Game Theory for Noobs

Game theory is not so much about Playstation as it is a science about strategy. The purpose of game theory is to determine the most rational course of action. Rational in this sense means the course of action that results in the highest amount of possible gain, or in the lowest amount of possible loss.

Christina Aguilera Christina Aquilera Hollywood Star
Christina Aguilera. She recently received her own Hollywood star. Not sure why, but it must mean she knows a thing or two about strategy.

John Nash is frequently associated with game theory. His tragic bout of schizophrenia is often abused to ridicule game theorists and to discredit the science of game theory, as is the case in the BBC documentary The Trap. However, John Nash was a fairly latecomer to the field as John von Neumann established the science in collaboration with Oskar Morgenstern with their book, Theory of Games and Economic Behaviour. This book reported a means to quantify the qualitative notions of expected utility, so in a way von Neumann and Morgenstern gave us mathematics for hope just like Bayes gave us the mathematics for faith with Bayesian analysis.

Nash Bridges
Nash Bridges. Not really relevant here.

The Nash equilibrium

Nash's contribution is the Nash equilibrium. Nash equilibrium results when all players involved know the strategies available to themselves and the other players, but no player has anything to gain by switching strategies. This appears superficially similar to the African philosophy of Ubuntu, which is an ethical concept based on the premise that “I am what I am because of who we all are”.

Thus, my strategies are limited by your strategies and your strategies are limited by my strategic choices, but neither of us have anything to gain by changing our current courses of action. If a Nash equilibrium is available, the most rational course of action is to cooperate and not to change your strategy. A Nash equilibrium is however not possible in all kinds of games. In these games, one can maximise gains by not cooperating (that is, by “cheating” or defaulting).

“Seven deadly sins, seven ways to win”

Strangely scientific lyrics from Iron Maiden in Moonchild. Seven of the games in which cheating or defaulting may be beneficial to you and detrimental - fatal, even - to other players as identified in Len Fisher's excellent book Rock, Paper, Scissors are:

  1. The Prisoner's Dilemma

  2. The Tragedy of the Commons

  3. The Free Rider Problem

  4. Chicken

  5. The Volunteer's Dilemma

  6. Battle of the Sexes

  7. Stag Hunt

In the next couple of posts, I shall deal with each of these and elaborate in my usual sombre tone.

Creative Commons License