Game Theory · Chapter 2
Dominance and the Prisoner’s Dilemma
Some choices are bad no matter what anyone else does. Spot them, cross them out, and assume your opponent does the same; often the game solves itself. Here you’ll cross out dominated actions in bigger and bigger games, first by yourself and then watching it done step by step. Then you’ll play the most famous game in the subject, the prisoner’s dilemma, where each player has an action that is always better, and yet both players end up worse off for choosing it.
Mode
Missions
What you’re seeing
The puzzle. Each cell holds two payoffs: the row player’s in gold, the column player’s in blue. Click the name of an action you think no rational player would choose. If some other action of the same player pays more in every remaining cell, it is strictly dominated: gold or blue arrows show each comparison, and a red line crosses it out. If it isn’t, the cells that prove it light up and the explanation says why.
Iterating. Crossing out one player’s action can make another player’s action dominated, because there are fewer cases left to compare. Keep going until nothing is dominated. In the 3×3 and 4×4 puzzles exactly one cell survives; in Random games you may get stuck with several. “Watch it solve” does the same thing, one step every two seconds, with the reason for each step.
The prisoner’s dilemma. You are the row player against a bot with a fixed personality, for ten rounds. After each round a gold arrow points from Quiet to Fink in the column the bot chose, with the extra payoff finking brings: always +1. Bars and chips below keep score.
The text. The explanation under the matrix is also read out to screen readers. Everything you click can be done with the keyboard.
Dominated actions
Here is the prisoner’s dilemma as Osborne writes it. Two suspects are held in separate cells. If both stay quiet, each is convicted of a minor offense; if one finks, the other gets a long sentence and the fink goes free; if both fink, both get a medium sentence. The payoffs rank the outcomes for each suspect: 3 is best, 0 is worst.
| Suspect 2 | ||
|---|---|---|
| Suspect 1 | Quiet | Fink |
| Quiet | 2, 2 | 0, 3 |
| Fink | 3, 0 | 1, 1 |
Look at Suspect 1’s payoffs. If Suspect 2 stays quiet, finking gives 3 instead of 2. If Suspect 2 finks, finking gives 1 instead of 0. Whatever the other does, Fink is better. We say Fink strictly dominates Quiet.
A rational player never chooses a strictly dominated action: there is another action that does better in every case, so no belief about the others can make the dominated one the best choice. If one action strictly dominates all of a player’s other actions, it is a strictly dominant action, and if every player has one, the profile of dominant actions is a dominant-strategy equilibrium. In the prisoner’s dilemma that is (Fink, Fink).
Weak dominance relaxes the inequality: a″i weakly dominates a′i if it is never worse, ui(a″i, a−i) ≥ ui(a′i, a−i) for every a−i, and strictly better in at least one case. Playing a weakly dominated action is not always a mistake, since the cases where it is just as good might be exactly the ones that happen, but it is risky.
Iterated elimination
If you know your opponent is rational, you know they won’t play their dominated actions, so you can cross those out too and look again. If they know you know, they can go one step further. With rationality as common knowledge (Chapter 1), you can repeat the process until nothing more can be removed. This is iterated elimination of strictly dominated actions. When strict dominance is used, the order in which you remove things never changes what survives.
| Column | |||
|---|---|---|---|
| Row | L | C | R |
| T | 4, 1 | 3, 3 | 1, 2 |
| M | 3, 0 | 2, 1 | 0, 5 |
| B | 2, 2 | 1, 4 | 6, 3 |
- Row’s M is dominated by T: 4 > 3, 3 > 2, 1 > 0. Cross out M. (You could instead start with Column’s L, which C beats in every row: 3 > 1, 1 > 0, 4 > 2. The order doesn’t matter.)
- Column’s L is dominated by C (3 > 1 against T, 4 > 2 against B). Cross out L.
- With M gone, Column’s R is dominated by C: 3 > 2 against T and 4 > 3 against B. Before, R was safe, because against M it paid 5. Cross out R.
- Only C is left for Column, and against C, Row’s B (1) is worse than T (3). Cross out B.
| Column | |||
|---|---|---|---|
| Row | L | C | R |
| T | 4, 1 | 3, 3 | 1, 2 |
| M | 3, 0 | 2, 1 | 0, 5 |
| B | 2, 2 | 1, 4 | 6, 3 |
| Column | ||
|---|---|---|
| Row | L | R |
| T | 1, 1 | 0, 0 |
| M | 1, 1 | 2, 1 |
| B | 0, 0 | 2, 1 |
- Remove T first (M is never worse: 1 = 1 and 2 > 0). Then, for Column, R weakly dominates L (1 = 1 against M, 1 > 0 against B). Remove L, and the payoffs left are (2, 1).
- Remove B first instead (M: 1 > 0 and 2 = 2). Now L weakly dominates R for Column (1 > 0 against T, 1 = 1 against M). Remove R, and the payoffs left are (1, 1).
Two orders, two different answers. That is why iterated elimination is usually done with strict dominance, where the order never matters.
Dominated by a mixture, and rationalizability
An action can be beaten by a combination of other actions without being beaten by any single one. Suppose Row’s payoffs are T: (3, 0), M: (1, 1) and B: (0, 3) against Left and Right. Neither T nor B dominates M, but flipping a fair coin between T and B pays 1.5 against either column, more than M’s 1. M is strictly dominated by a mixed strategy (Chapter 4 defines mixed strategies). Removing everything that is dominated this way, again and again, leaves the rationalizable actions, defined by Douglas Bernheim and David Pearce in 1984: the actions a player could choose if everyone is rational and that is common knowledge, but nothing more is assumed about beliefs. In two-player games the two procedures give the same answer.
Why rational players end up worse off
In the prisoner’s dilemma both suspects follow their dominant action and get 1 each, though both would get 2 if both stayed quiet. The outcome is Pareto inefficient: another outcome is better for everyone. Nothing went wrong in anyone’s reasoning. The problem is that each player’s gain from finking (+1) comes partly at the other’s expense (−2), and no one accounts for the harm they do to the other.
Any game with payoffs ranked T > R > P > S has this structure, where T is the temptation to defect, R the reward for mutual cooperation, P the punishment for mutual defection and S the sucker’s payoff. In Osborne’s version, T = 3, R = 2, P = 1, S = 0.
Trust isn’t the problem in a one-shot prisoner’s dilemma. Even if Suspect 1 knew for certain that Suspect 2 would stay quiet, finking would still pay more (3 instead of 2). A promise to stay quiet doesn’t help either, because keeping it is never in the promiser’s interest. What can help is changing the game: a contract with penalties, a repeated relationship (Chapter 7), or caring about the other player, which changes the payoffs themselves.
Real dilemmas
- Arms races. Each of two rival countries is safer if it arms, whatever the other does, yet both are poorer, and no safer, when both arm. Arms-control treaties with inspections try to change the payoffs.
- Advertising. When two firms mostly steal customers from each other, each does better advertising whatever the rival does, and both pay for campaigns that cancel out. Some economists have argued that the 1971 U.S. ban on cigarette advertising on television and radio helped the tobacco companies by ending a race none could quit alone (see R. Eckard, Economic Inquiry, 1991).
- Overfishing. Each boat catches more by fishing harder, whatever the others do; together they empty the sea. The northern cod off Newfoundland collapsed, and Canada closed the fishery in 1992. Garrett Hardin called this pattern “the tragedy of the commons” (Science, 1968).
- Price wars. Each firm gains by undercutting a rival that holds its price, and both lose margin when both cut. The coffee-shop example in Chapter 1 had exactly this structure. In the 1980s, falling memory-chip prices squeezed every maker; Intel’s answer was to leave the business (see the case Intel Walks Out the Door and Comes Back In).
Two firms each decide whether to run an advertising campaign. Profits in millions of dollars (invented for the example): if neither advertises, each earns 5. If one advertises, it earns 6 and the other 2. If both advertise, the campaigns cancel out and each earns 3 after paying for its ads.
| Firm 2 | ||
|---|---|---|
| Firm 1 | Advertise | Don’t |
| Advertise | 3, 3 | 6, 2 |
| Don’t | 2, 6 | 5, 5 |
- For Firm 1: against Advertise, 3 > 2; against Don’t, 6 > 5. Advertising strictly dominates.
- The same holds for Firm 2, so both advertise and earn 3 each.
- Both would earn 5 if neither advertised: together they lose 4 million to campaigns that cancel out. The ranking 6 > 5 > 3 > 2 is T > R > P > S: a prisoner’s dilemma.
A dilemma with many players: the public-goods game
The prisoner’s dilemma has a many-player cousin used in hundreds of laboratory experiments. Four people each get 20 tokens. Each decides how many to put into a group project. Everything in the project is multiplied by 1.6 and shared equally among all four, whoever gave it. Ernst Fehr and Simon Gächter used these numbers in a famous study (American Economic Review, 2000).
Each token you give returns 0.4 tokens to you, so it costs you 0.6 net: giving nothing strictly dominates giving anything. But each token also returns 0.4 to each of the other three, so it creates 1.6 tokens in total. If everyone gives 20, everyone earns 0.4 × 80 = 32 tokens; if everyone gives 0, everyone keeps 20. Play it below with three simulated group members.
Your move
The group
The simulated members follow the types found by Urs Fischbacher, Simon Gächter and Ernst Fehr (Economics Letters, 2001), who asked people how much they would give for each possible average of the others: about half were conditional cooperators, who give more when others give more, and about a third were free riders, who give nothing. Our conditional cooperators give a bit less than the others gave last round, so a single free rider drags the whole group down, round after round. That decay is the most reliable result of public-goods experiments: contributions often start at 40 to 60 percent of the endowment and fall steadily over ten rounds.
Fehr and Gächter then added a stage where, after seeing the contributions, members could pay to punish each other. Punishing costs the punisher, so a purely selfish player never punishes, and knowing that, no one should fear punishment. Yet many people did punish free riders, and contributions rose instead of falling. Turn on the punishment stage to see the same effect in the simulation. The dashed lines show a simulated laboratory session of 40 such players, with and without punishment.
A short history
In early 1950, Merrill Flood and Melvin Dresher at the RAND Corporation persuaded two colleagues to play a game of this structure over and over, an informal experiment. Albert W. Tucker of Princeton, wanting to explain it to an audience of Stanford psychologists, made up the story of the two prisoners, and the name stuck.
The ecologist Garrett Hardin’s 1968 essay “The Tragedy of the Commons” described the many-player version with herders on a shared pasture; Elinor Ostrom later documented how real communities manage commons without either privatization or central control, work that earned her a share of the 2009 Nobel prize in economics. Douglas Bernheim and David Pearce independently defined rationalizability in 1984 (Econometrica). Ernst Fehr and Simon Gächter’s punishment experiments (2000, 2002) changed how economists think about cooperation among strangers.
Where you see it
- Business: price wars, advertising wars, bonus races for talent, and suppliers each tempted to cut quality slightly. A firm that sees a prisoner’s dilemma coming can try to change the game: long-term contracts, loyalty programs that reduce stealing customers, or industry standards.
- Policy: fisheries quotas, climate agreements and arms-control treaties are attempts to escape many-player dilemmas by adding rules, monitoring and penalties. Taxes on pollution change the payoffs directly.
- Sports: doping is often described as a prisoner’s dilemma: each athlete gains an edge by doping whatever the others do, and all of them bear the health risks for no relative gain. Testing is the outside enforcement.
- Daily life: standing up at a concert to see better, everyone driving to avoid a crowded bus, group projects where one member coasts. The public-goods game is any shared fridge, shared kitchen or shared spreadsheet.
Practice
Spot the dominant action. In the advertising game above, change the payoff when neither advertises from (5, 5) to (7, 7). Is advertising still dominant? Is it still a prisoner’s dilemma?
Show the answer
Against Don’t, Firm 1 now compares 6 (advertise) with 7 (don’t): not advertising is better. Against Advertise, it compares 3 with 2: advertising is better. Neither action dominates, so there is no dominant-strategy equilibrium. The ranking is now 7 > 6 > 3 > 2, that is R > T, so it is no longer a prisoner’s dilemma; it is a coordination game (Chapter 3).
Solve by elimination. Use iterated elimination of strictly dominated actions:
Column Row L C R T 5, 3 2, 1 4, 0 M 3, 2 1, 4 6, 1 B 4, 5 0, 3 2, 2 Show the answer
- Row’s B is dominated by T: 5 > 4, 2 > 0, 4 > 2.
- With B gone, Column’s R is dominated by L: 3 > 0 against T, 2 > 1 against M.
- With R gone, Row’s M is dominated by T: 5 > 3, 2 > 1.
- Against T alone, Column’s C (1) is worse than L (3).
What survives is (T, L), with payoffs (5, 3).
Stuck. Is any action strictly dominated in this game? What does that tell you?
Column Row L C R T 2, 0 1, 3 4, 1 M 3, 2 0, 1 1, 0 B 1, 1 2, 0 3, 2 Show the answer
No. For Row, T beats B in column L but loses in column C; M is best in column L but worst in column C; and so on. For Column, L, C and R each are best against some row (L against M, C against T, R against B). Nothing can be crossed out, so dominance says nothing here. The game still has a Nash equilibrium, (M, L), which you’ll learn to find in Chapter 3.
Weak, not strict. In the roommates game of Chapter 1 (Clean or Skip, payoffs (30, 30), (0, 60), (60, 0), (0, 0)), show that Skip weakly but not strictly dominates Clean for Ana.
Show the answer
If Ben cleans, Skip gives Ana 60 and Clean 30: Skip is better. If Ben skips, both give Ana 0: a tie. Skip is never worse and sometimes better, so it weakly dominates Clean; because of the tie it does not strictly dominate it.
When does the public good stop being a dilemma? In the public-goods game with n players, each token in the project returns m to every player (above, n = 4 and m = 0.4). For which m is giving nothing dominant? For which m does the group gain from every token given?
Show the answer
A token you give changes your own earnings by −1 + m. If m < 1, giving nothing strictly dominates. A token changes the group’s total by −1 + nm, which is positive when m > 1/n. So the game is a social dilemma exactly when 1/n < m < 1. With n = 4: 0.25 < m < 1, and 0.4 is in that range.
Beaten by a mixture. Row’s payoffs against (Left, Right) are T: (3, 0), M: (1, 1), B: (0, 3). For which probabilities p of playing T (and 1 − p of playing B) does the mixture strictly dominate M?
Show the answer
Against Left the mixture pays 3p, against Right 3(1 − p). We need 3p > 1 and 3(1 − p) > 1, so 1/3 < p < 2/3. Any mixture in that range beats M in both columns, although neither T nor B does on its own.
Elimination never removes an equilibrium. Show that if (a*1, a*2) is a Nash equilibrium (each action is a best response to the other), then neither a*1 nor a*2 is ever removed by iterated elimination of strictly dominated actions.
Show the answer
Suppose not, and look at the first step at which an equilibrium action is removed, say a*1, dominated by some b1. Before that step a*2 is still present, so domination means u1(b1, a*2) > u1(a*1, a*2). But then a*1 is not a best response to a*2, contradicting equilibrium. So equilibrium actions always survive, and if elimination leaves a single profile, that profile is the only Nash equilibrium.
How the interactive works
Puzzles. The 3×3 and 4×4 puzzles are built backward. Starting from the cell that will survive, the generator adds one action at a time, alternating between the players in random order. Each new action is made strictly dominated, against the opponent’s actions present at that moment, by an action already there. Removing the actions in the opposite order is then a valid elimination path ending at one cell, and since strict elimination gives the same result in any order, every path ends there. Rows and columns are shuffled for display, and payoffs stay between 0 and 9. Random games draw every payoff from 0 to 9. Dominance is checked against pure actions only; the lesson explains dominance by mixtures.
Bots. Saint always stays quiet, Shark always finks, Mirror plays tit for tat, Grudger stays quiet until you fink once, and Coin is a fair coin. The public-goods members are simplified versions of the experimental types, described in the comments of model.js: conditional cooperators give 85% of the others’ last average, free riders give nothing, altruists give 16 to 20; with punishment, cooperators punish anyone who gave at least 4 less than they did, and being punished makes members give more later.
Checks (node). 2,000 generated 3×3 puzzles and 2,000 4×4 puzzles were all solved by elimination in exactly 4 and 6 steps, with the survivor equal to the game’s unique pure Nash equilibrium and every payoff between 0 and 9. In 500 4×4 puzzles, eliminating in a random order always gave the same survivor. Of 5,000 random 3×3 games, 24.2% could be solved by pure-strategy elimination. The public-goods earnings match the formula (32 each when all give 20, 44 for a lone free rider, 20 when nobody gives). Averaged over 200 simulated sessions of 40 players with 30% free riders, contributions fell from 9.1 to 4.5 tokens over ten rounds without punishment and rose from 9.1 to 12.7 with it, the same direction as in the experiments, though the simulated numbers are not meant to match any one study.
Check yourself
Action X strictly dominates action Y for a player when …
Show the answer
Strict dominance is a comparison case by case: X must beat Y whatever the others do.
In the prisoner’s dilemma, suppose Suspect 1 knows for certain that Suspect 2 will stay quiet. What should a Suspect 1 who cares only about their own payoff do?
Show the answer
Fink is dominant, so it is the best reply to Quiet too. The dilemma doesn’t come from distrust.
Why does the order of elimination not matter for strict dominance, but can matter for weak dominance?
Show the answer
Removing opponent actions only removes comparisons, so strict dominance survives. With weak dominance, removing the one case where an action was strictly better can turn it into a tie, as in the T, M, B example.
In the public-goods game (4 players, each token returns 0.4 to everyone), what does a selfish player who expects others to give 20 each do?
Show the answer
Giving nothing is strictly dominant: whatever the others give, every token you give lowers your earnings by 0.6.
Iterated elimination of strictly dominated actions leaves exactly one action profile. What can you conclude?
Show the answer
Equilibrium actions are never eliminated (Practice problem 7), so a unique survivor must be the unique equilibrium. It need not be good for anyone: in the prisoner’s dilemma it is (Fink, Fink).
Sources
- M. J. Osborne, An Introduction to Game Theory (Oxford University Press, 2004), chapter 2 (the prisoner’s dilemma, dominated actions) and chapter 12 (rationalizability).
- R. Gibbons, Game Theory for Applied Economists (Princeton University Press, 1992), section 1.1.B (iterated elimination of strictly dominated strategies).
- Steven Kuhn, “Prisoner’s Dilemma”, Stanford Encyclopedia of Philosophy (Flood, Dresher and Tucker).
- E. Fehr and S. Gächter, “Cooperation and punishment in public goods experiments”, American Economic Review 90(4), 2000, 980–994; E. Fehr and S. Gächter, “Altruistic punishment in humans”, Nature 415, 2002, 137–140.
- U. Fischbacher, S. Gächter and E. Fehr, “Are people conditionally cooperative? Evidence from a public goods experiment”, Economics Letters 71(3), 2001, 397–404.
- Public goods game (Wikipedia).
- B. D. Bernheim, “Rationalizable strategic behavior”, Econometrica 52(4), 1984, 1007–1028; D. G. Pearce, “Rationalizable strategic behavior and the problem of perfection”, Econometrica 52(4), 1984, 1029–1050.
- G. Hardin, “The tragedy of the commons”, Science 162, 1968, 1243–1248. R. L. Eckard Jr., “Competition and the cigarette TV advertising ban”, Economic Inquiry 29(1), 1991.
- Yale Open Courses, ECON 159: Game Theory (Ben Polak), the first lectures on dominance.