Previous Up Next

This HTML version of Think Complexity, 2nd Edition is provided for convenience, but it is not the best format of the book. In particular, some of the symbols are not rendered correctly.

You might prefer to read the PDF version.

Chapter 12  Game Theory


12.1  The El Farol Problem

12.2  Prisoner’s Dilemma

The Prisoner’s Dilemma is a topic of study in game theory, but it’s not the fun kind of game. Instead, it is the kind of game that sheds light on human motivation and behavior.

Here is the presentation of the dilemma from's_dilemma.

Two suspects [Alice and Bob] are arrested by the police. The police have insufficient evidence for a conviction, and, having separated the prisoners, visit each of them to offer the same deal. If one testifies against the other (defects) and the other remains silent (cooperates), the defector goes free and the silent accomplice receives the full one-year sentence. If both remain silent, both prisoners are sentenced to only one month in jail for a minor charge. If each betrays the other, each receives a three-month sentence. Each prisoner must choose to betray the other or to remain silent. Each one is assured that the other would not know about the betrayal before the end of the investigation. How should the prisoners act?

Notice that in this context, “cooperate” means to keep silent, not to cooperate with police.

It is tempting to say that the players should cooperate with each other, since they would both be better off. But neither player knows what the other will do. Looking at it from Bob’s point of view:

  • If Alice remains silent, Bob is better off defecting.
  • If Alice defects, Bob is better off defecting.

Either way, Bob is better off defecting. And from her point of view, Alice reaches the same conclusion. So if both players do the math, and no other factors come into play, we expect them to defect and be worse off for it.

This result is saddening because it is an example of how good intentions can lead to bad outcomes, and, unfortunately, it applies to other scenarios in real life, not just hypothetical prisoners.

But in real scenarios, the game is often iterated; that is, the same players face each other over and over, so they have the opportunity to learn, react, and communicate, at least implicitly.

The iterated version of the game is not as easy to analyze; it is not obvious what the optimal strategy is or even whether one exists.

So in the late 1970s Robert Axelrod organized a tournament to compare strategies. He invited participants to submit strategies in the form of computer programs, then played the programs against each other and kept score.

I won’t tell you the outcome, and if you don’t know you should resist the temptation to look it up. Instead, I encourage you to run your own tournament.

12.3  Game Theory


You have reached the end of the book. Congratulations! When you first read Chapter ??, some of the topics might not have made sense. You might find it helpful to read that chapter again now. Then get to work on your case study!

12.4  Exercises

Exercise 1  

Download, which runs the tournament, and, which implements a simple player strategy.

Here is the code from

def move(history): mine, theirs = history if len(mine) % 2 == 0: return 'C' else: return 'D'

Any file that matches the pattern Player*.py is recognized as a player. The file should contain a definition for move, which takes the history of the match so far and returns a string: 'D' for defect and 'C' for cooperate.

history is a pair of lists: the first list contains the player’s previous responses in order; the second contains the opponent’s responses.

PlayerFlipper checks whether the number of previous rounds is even or odd and returns 'C' or 'D' respectively.

Write a move function in a file like, but replace “Flipper” with a name that summarizes your strategy.

Run and see how your strategy does.

After you run your own tournament, you can read about the results of Axelrod’s tournament in his book, The Evolution of Cooperation.

Are you using one of our books in a class?

We'd like to know about it. Please consider filling out this short survey.

Think DSP

Think Java

Think Bayes

Think Python 2e

Think Stats 2e

Think Complexity

Previous Up Next