Week 06 · Complete notes
Thinking strategically
How should I act and strategize when outcomes depend on others who also strategize?
This print edition combines all five readings. Interactive definitions become ordinary text when printed.
01
What makes a game
How do we describe a situation in which your best move depends on what someone else does?
Think back to the monopoly setting a uniform price. It faced its customers' demand and no rival, so the only question was which price maximizes profits. That is an individual decision problem. Now suppose a second firm sold the same product. The product is homogeneous, so customers would look for the lowest price in the market. The problem would be quite different. The best price for each firm would depend on the price the other charges, so each would need to figure out the other's move, knowing the other is doing the same.
This reading gives us the language for problems like the second one. First, we separate a decision you make on your own from one whose outcome depends on what others choose. Then we set out the elements we need to describe a game.
1.1
Individual decision problem vs multi-person decision problem
In an individual decision problem, one decision-maker chooses from a set of options to best meet their goals. There are three pieces. First, a set of feasible options: what the person can do, given what is available to them, and the rules they face. Second, a goal: a way to rank the options so each one has value to the person. Third, a choice: the person picks the feasible option they value most. The result is the outcome of that choice.
Take an investor with $10,000 to split among stocks, bonds, and a savings account. The feasible options are all the splits that add up to $10,000. The goal might be the highest expected return, or the best balance between return and risk. The investor compares the splits, picks the best one, and lives with the result. Returns are uncertain, but the uncertainty is chance. Once the investor has weighed the options, the problem is simply to choose the best one.
In a multi-person decision problem, two or more decision-makers each choose from a set of options to best meet their goals, and the outcome depends on everyone's choices. There are the same three pieces as before, one set for each person. First, a set of feasible options: what the person can do, given what is available to them, and the rules they face. Second, a goal: a way to rank the outcomes so each one has value to the person. Third, a choice: the person picks an option. What changes is that the outcome now depends on all the choices together, so you can't find your best option by looking at your own options alone. It depends on what the others choose.
Take two cafés directly across the street from each other. Each sets the price of a cup of coffee. For each café, the feasible options are the prices it is willing to charge, say $4 or $6, and the goal is the highest profit. Whether $6 is a good price for Café A depends on whether Café B charges $6 or $4, and vice versa. Each café must form a view of what the other will do, knowing the other is forming a view of its own. Unlike an investor, a café can't simply compare its options and pick the best one, because each option's value depends on a choice someone else makes.
Multi-person problems are everywhere:
- The success of a group project depends on every member's effort, not just yours.
- Whether you win a pair of loudspeakers on eBay, and what you pay, depends on everyone else's bids.
- A jury's verdict depends on the work of both the defense and the prosecution.
We will call a multi-person decision problem a , and the decision-makers are its players. The word isn't meant to make these problems sound trivial. It reflects what they share with chess or poker: each player has goals, and each has to take the other players' choices into account. In a game, the outcome depends on what all the players do. The study of games is called game theory.
1.2
What we write down
To describe a game we need five elements.
- Players. The decision-makers. A player can be a person, a firm, a government or any other party, as long as its choices have a material effect on the outcome.
- Strategies. The options available to each player. A strategy can be a single action or, as we'll see in Reading 4, a plan of actions over time.
- Outcomes. What happens for each combination of strategies, one for each player.
- Payoffs. How much each player values each outcome. A payoff is a number that represents the player's ranking of the outcomes: a higher payoff means the player prefers that outcome. Profit is the usual payoff for a firm, but a payoff can also capture anything else a player cares about, such as fairness, pride, or a rival's loss.
- Rules. Who moves when, what each player knows when it moves, and how the players' strategies determine the outcome.
Writing these down is useful in itself, because it turns a hunch into a problem you can discuss. Two managers who disagree about a pricing decision often disagree about something they haven't said aloud: what the rival will do. One assumes the rival will match a price cut, the other assumes it won't, and they argue about price when the real dispute is about the rival. Setting out the game puts that assumption on the table, where the team can question it, test it, and agree on it before committing to a price.
1.3
Two cafés
Let's describe this game with the same five elements.
- Players. The two cafés, Café A and Café B.
- Strategies. Each café can charge $4 or $6 a cup. Each chooses one price without knowing what the other chooses, so the choices are simultaneous.
- Outcomes. Two players with two strategies each give four possible outcomes. There are 100 customers a day, each buying one cup, and they are very sensitive to price: they go to the cheaper café, and split evenly if the prices are equal.
- Both charge $6. The prices are equal, so the customers split: 50 go to each café.
- Both charge $4. The prices are equal again, so 50 customers go to each café.
- A charges $4 and B charges $6. Café A is cheaper, so all 100 customers go to A and none go to B.
- A charges $6 and B charges $4. Café B is cheaper, so all 100 customers go to B and none go to A.
- Payoffs. Costs are zero, so each café's payoff is its profit, which equals its revenue: price times customers served.
- Both charge $6. Each earns \(50\times6=300\).
- Both charge $4. Each earns \(50\times4=200\).
- A charges $4, B charges $6. A earns \(100\times4=400\) and B earns \(0\times6=0\).
- A charges $6, B charges $4. A earns \(0\times6=0\) and B earns \(100\times4=400\).
- Rules. Both cafés set their prices at the same time, and the customers' behavior determines how many each café serves.
A with two players and a few strategies each is easiest to read as a payoff matrix:
Read it like this. Café A chooses a row and Café B chooses a column. Each cell is one outcome, and it lists two payoffs: Café A's first, in red, and Café B's second, in blue. If Café A charges $6 and Café B charges $4, we're in the top-right cell: Café A earns 0 and Café B earns 400. The row player's payoff always comes first. It's a convention worth holding onto, because nothing else in the matrix tells you which number is whose.
1.4
Simultaneous and sequential games
The rules include the timing of the moves, and there are two broad kinds of game.
In a , each player chooses without knowing what the others have chosen. The players don't have to move at the same moment. Suppose Café B sets its price at 7 am and Café A sets its price at 8 am. If Café A can't see Café B's price before it decides, the game is still simultaneous. What matters is whether a player knows the others' choices when it makes its own.
Recall the first-price sealed-bid auction from Week 1. Each bidder submits one bid in secret, without seeing anyone else's. The bids are opened together, the highest bidder wins, and the winner pays what they bid. This is a simultaneous game. When you choose your bid, you don't know what the others bid.
In a , players move in turn, and a later player sees the earlier moves before choosing. An English auction, where every bidder sees the current high bid, is a sequential game. So is a market entry decision, where the incumbent reacts after the entrant has moved. We draw sequential games as trees, and Reading 4 treats them.
A matrix can be larger than two by two. In the game below, Alice has four actions, \(w\), \(x\), \(y\) and \(z\), and Bob has five, \(a\) to \(e\). An action profile lists one action for each player, such as \((x,d)\). Its payoffs are written \(\pi_A(x,d)=1\) for Alice and \(\pi_B(x,d)=-2\) for Bob.
Time plays no role here. The players choose once, receive their payoffs and the game is over.
Summary. A game is a situation in which each player's payoff depends on everyone's choices. To describe one, write down the players, their strategies, the outcomes, the payoffs and the rules. In a simultaneous game no player sees the others' moves before choosing, and a payoff matrix lists both players' payoffs for every combination of strategies, the row player's first. In a sequential game later players see earlier moves, and we draw a tree.
02
Dominance
When can you choose without knowing what your rival will do?
Some choices are easy. In the café game, Café A doesn't need to guess Café B's price, because $4 is better against both. Some strategies are like that, and when they exist they settle the game quickly.
This reading defines dominant and dominated strategies and uses them step by step to solve games that look harder at first sight.
2.1
A strategy that wins whatever the rival does
Start with the cafés from Reading 1. You run Café A. Pick a price and submit it before you read on.
Whatever you chose, Café B charged $4. Would you have chosen differently if it had charged $6? Compare the two rows column by column. If Café B charges $6, Café A earns 400 at $4 and 300 at $6. If Café B charges $4, Café A earns 200 at $4 and 0 at $6. Either way $4 is better. So Café A doesn't need a forecast of Café B at all.
A strategy like this is a : it gives a higher payoff than any other strategy, regardless of what strategy the other players choose. $4 is a dominant strategy for Café A, and by the same reasoning it is one for Café B too. We'll come back to the cafés in Reading 3.
Consider another game: two news stories dominate public attention: a heated budget debate in parliament and a new COVID variant. The editors of The Australian and the AFR each choose one for tomorrow's cover. Market research says 30% of potential readers care about the budget story and 70% about the COVID story. The payoffs are the percentage of potential buyers each paper attracts.
Take The Australian's view. Its editor doesn't know which story the AFR will run.
- If the AFR runs COVID, COVID gives The Australian 35 and Budget gives 30. COVID is better.
- If the AFR runs Budget, COVID gives 70 and Budget gives 15. COVID is better again.
Whatever the AFR does, COVID is better for The Australian. The AFR's editor reasons the same way and reaches the same answer. Both run COVID.
COVID is a dominant strategy for each paper. Each editor can say, "I'm doing the best I can whatever you do, and you're doing the best you can whatever I do."
The force of the idea is that it needs no beliefs at all. You don't need a forecast of the rival, a view of its costs or a theory of its psychology. If a strategy is best against every choice the rival might make, play it. So always look for dominance first.
Consider a variant of the game. If both papers run COVID, The Australian now attracts 25% and the AFR 35%. Every other cell stays the same.
Does The Australian still have a dominant strategy? The answer is no. If the AFR runs COVID, The Australian does better with Budget, 30 against 25. If the AFR runs Budget, it does better with COVID, 70 against 15. So The Australian can't decide what to run without working out what the AFR will do.
But the AFR still has a dominant strategy. COVID gives it 35 against 30 if The Australian runs COVID, and 70 against 15 if The Australian runs Budget. So The Australian can reason as follows:
- The AFR has a dominant strategy, so it will run COVID.
- The Australian knows that the AFR plays to maximize its payoff, so it predicts that the AFR runs COVID. Based on that correct prediction, The Australian runs Budget.
So even though The Australian doesn't have a dominant strategy, it can decide what to run by using the rationality of its rival. The outcome is (Budget, COVID).
2.2
Dominated strategies
The Australian's reasoning can be put another way. For the AFR, Budget is a : COVID gives it a higher payoff whatever The Australian runs.
A rational player never plays a dominated strategy. Its rival knows this, the player knows that its rival knows, and so on. In other words, it is . So we can cross a dominated strategy out of the game.
In the variant, cross out the AFR's Budget first. Only the COVID column is left, and in that column The Australian gets 25 from COVID and 30 from Budget. Now COVID is dominated for The Australian, so cross it out too. One cell remains: (Budget, COVID).
A game that can be solved this way is called dominance solvable. Notice that The Australian's COVID isn't dominated in the original game. It becomes dominated only once we've used the fact that the AFR won't run Budget.
2.3
Iterated elimination
Deleting a dominated strategy leaves a smaller game, and in that smaller game another strategy may now be dominated. So we look again. If we find one, we delete it and check once more, and we keep going until nothing else can be removed. This is called .
Neither player has a dominant strategy, and Player 2 has no dominated one either. But Player 1's \(b\) is dominated by \(c\):
- against \(a\), \(c\) gives 20 and \(b\) gives 7;
- against \(b\), \(c\) gives 7 and \(b\) gives 3;
- against \(c\), \(c\) gives 10 and \(b\) gives 5.
Delete row \(b\). In the smaller game, Player 2's \(b\) is now dominated by \(c\): 8 beats 5 against row \(a\), and 10 beats 3 against row \(c\). Delete column \(b\). Now Player 1's \(c\) beats \(a\) in both remaining columns, 20 against 15 and 10 against 2, so delete row \(a\). Player 2 is left choosing between 1 and 10 in row \(c\), and picks \(c\). The game's outcome is \((c,c)\), with payoffs of 10 each.
Two cautions. First, "dominated" means worse against every choice of the rival. A strategy that does worse on average, or worse in the case you think likely, isn't dominated, and crossing it out is a mistake. Second, each round asks more of the players. Deleting Player 2's \(b\) assumes Player 2 knows that Player 1 won't play \(b\). Deleting Player 1's \(a\) assumes Player 1 knows that Player 2 knows it. In a game with many rounds, that chain of reasoning gets long.
Check the definition
In the 3 × 3 game, is Player 2's strategy \(a\) dominated in the original game, before anything is deleted?
A dominated strategy has to do worse against every choice of the rival. Against Player 1's \(a\), Player 2's \(a\) is the best column, 15 against 5 and 8. So it isn't dominated at the start. It becomes dominated only after Player 1's \(a\) and \(b\) have been deleted.
A manager says: "Strategy X earns more than Strategy Y in three of the rival's four possible moves, and the fourth is unlikely. So Y is dominated." Is that right?
Dominance doesn't depend on what's likely. If Y beats X against even one of the rival's moves, a rational player might choose Y, depending on what it expects the rival to do. That case needs the tool of Reading 3, best responses.
Summary. A dominant strategy is best whatever the other players do, so a player who has one needs no forecast of the rival. A dominated strategy does worse than some other strategy against every choice of the rival, so it can be deleted. Deleting dominated strategies round after round can solve a game, as in the newspaper and 3 × 3 examples.
03
Nash equilibrium
What can we predict when nobody has a dominant strategy?
Dominant and dominated strategies don't always exist. In most games, a player's best choice depends on what the other player does.
This reading introduces the tool for those games. We define best responses and Nash equilibrium, find the equilibria of several classic games, and ask what we can predict when a game has more than one equilibrium, or none.
3.1
Best responses
Alice and Bob are deciding where to spend the evening. Alice prefers the ballet and Bob the opera, but both would rather be together than apart. They choose separately, without being able to talk first.
Start with dominance
Does either player have a dominant strategy or a dominated strategy in this game?
Neither. If Bob goes to the ballet, Alice does better at the ballet, 3 against 0. If Bob goes to the opera, she does better at the opera, 1 against 0. Her best choice depends on Bob's, so neither of her strategies is dominant, and neither is dominated. Bob's payoffs are the mirror image.
Neither has a dominant strategy. If Bob goes to the ballet, Alice should too; if Bob goes to the opera, Alice should too. Nothing is dominated either, so dominance can't help.
We need a weaker idea. A is a strategy that gives a player the highest payoff against a particular choice of the others. Ballet is Alice's best response to Bob's Ballet, and Opera is her best response to Bob's Opera. Dominance asks whether a strategy is best against everything the rival might do. A best response only has to be best against one thing.
Best responses are easy to find in a matrix. For the row player, go column by column and underline the highest red payoff in each column. For the column player, go row by row and underline the highest blue payoff in each row.
3.2
Nash equilibrium
A is a combination of strategies, one for each player, in which every player's strategy is a best response to the others'. Given what everyone else is doing, no player can do better by changing its own strategy. Each player can say, "Given what you're doing, I'm doing the best I can."
The idea is named after the mathematician John Nash
John Forbes Nash Jr. (1928–2015) was an American mathematician at Princeton. His 1950 doctoral thesis, 28 pages long, defined the equilibrium that now carries his name. He shared the 1994 Nobel Memorial Prize in Economic Sciences with John Harsanyi and Reinhard Selten for their work on game theory. His life is the subject of the book and film A Beautiful Mind.Photo: Peter Badge / Typos1, Wikimedia Commons, CC BY-SA 3.0, who showed in 1950 that equilibria of this kind exist in a very wide class of games.
There are several ways to read a Nash equilibrium, and each is useful in a different situation.
- No regrets. Once the choices are revealed, no player looks back and wishes it had chosen differently, given what the others actually did.
- A self-enforcing agreement. Think of an equilibrium as an unwritten handshake deal. There's no court or referee to enforce it, so it survives only if keeping it is in each player's own interest. In a Nash equilibrium it is: as long as the others keep the deal, breaking it hurts the player who breaks it.
- A resting point. Players may not know the equilibrium in advance. But suppose they adjust by trial and error, each changing its choice whenever it can do better. They stop changing only at a Nash equilibrium, and once they're there, nothing pushes them away.
- A self-fulfilling convention. If everyone expects everyone else to behave in a certain way, and that behavior is a best response to those expectations, the expectations confirm themselves. Australians drive on the left because they expect everyone else to, and everyone else does.
In a matrix, a Nash equilibrium is a cell in which both payoffs are underlined. In the ballet game there are two: (Ballet, Ballet) and (Opera, Opera). In the cafés' game there is one, ($4, $4).
How does this relate to the tools of Reading 2?
Dominance and Nash equilibrium
Suppose every player has a dominant strategy and plays it. Is the outcome a Nash equilibrium?
Yes. A dominant strategy is a best response to anything the others do, so in particular it is a best response to the others' dominant strategies. Every player is best responding, which is exactly the definition of a Nash equilibrium. In the cafés' game, ($4, $4) is both.
Now the opposite. In a Nash equilibrium, is every player playing a dominant strategy?
Not necessarily. In the ballet game, (Ballet, Ballet) is a Nash equilibrium, but Ballet isn't dominant for Alice: if Bob goes to the opera, she does better at the opera. A Nash equilibrium only asks each strategy to be best against what the others actually do, not against everything they might do.
The same holds for iterated elimination. If it leaves one cell, that cell is the only Nash equilibrium of the game.
Three things a Nash equilibrium doesn't claim are worth spelling out, because each is a common mistake.
It needn't be good for the players. An equilibrium is stable, not desirable. In the cafés' game both cafés earn 200 at ($4, $4). Both would earn 300 at ($6, $6), but that cell isn't an equilibrium: if Café B charges $6, Café A earns 400 by switching to $4. So the outcome both prefer doesn't last on its own, and the outcome that lasts is worse for both. The next section comes back to this.
It needn't be unique. A game can have more than one equilibrium. The ballet game has two, (Ballet, Ballet) and (Opera, Opera), and in each of them neither player wants to switch alone. The definition tells us which outcomes are stable, but not which of them will happen. Section 3.4 asks what decides that.
It doesn't explain how the players got there. The definition is a test we apply to a combination of choices: is each player doing its best, given what the others do? It says nothing about the process that led there. The players may have reasoned their way to it, learned it over time or simply agreed on it. They needn't even know that it's an equilibrium. The definition only says that once they're there, nobody wants to leave.
Compare the competitive equilibrium of Week 3. There, no buyer or seller wanted to change their plans at the market price. Here, no player wants to change its strategy, given the others' strategies. Both are states that nobody wants to leave.
Find the equilibria
Go back to Alice and Bob's 4 × 5 game from Reading 1. Click a payoff to mark it as a best response: Alice's best payoff in each column and Bob's best payoff in each row. Then press Check.
Which cells are Nash equilibria?
Alice's best responses, column by column, are \(y\) against \(a\), \(z\) against \(b\), \(w\) and \(x\) against \(c\) (a tie at 0), \(z\) against \(d\) and \(x\) against \(e\). Bob's best responses, row by row, are \(b\) against \(w\), \(e\) against \(x\), \(c\) against \(y\) and \(d\) against \(z\). Both are underlined in \((x,e)\) and \((z,d)\). The cell \((y,a)\) gives Alice her best response, but Bob would rather switch to \(c\), 6 against 5.
3.3
The cafés: a prisoner's dilemma
Go back to the cafés. In Reading 2 we saw that $4 is a dominant strategy for each café, so the only Nash equilibrium is ($4, $4). Look at where that leaves them: 200 each, when they could have had 300 each by both charging $6. Nobody made a mistake. Each café did what was best for itself, whatever the other did, and the result is worse for both.
A game with this structure is called a . The name comes from the original story. Two suspects are questioned separately. Each is better off confessing, whatever the other does, but if both stay silent they both get a lighter sentence than if both confess.
The game was first designed in 1950 by the mathematicians Merrill FloodMerrill M. Flood (1908–1991) was an American mathematician and one of the pioneers of operations research. At RAND he worked on the traveling salesman problem and, with Melvin Dresher, ran the first experiment with the prisoner's dilemma in January 1950: two RAND researchers played the game 100 times in a row.Reference: M. M. Flood (1958), “Some experimental games,” Management Science 5(1), 5–26. and Melvin DresherMelvin Dresher (1911–1992) was a Polish-born American mathematician at RAND, where he worked on game theory and its military applications. He wrote Games of Strategy: Theory and Applications (1961).Reference: M. Dresher (1961), Games of Strategy: Theory and Applications, Prentice-Hall. at the RAND Corporation. Soon after, the Princeton mathematician Albert W. TuckerAlbert W. Tucker (1905–1995) was a Canadian-born mathematician at Princeton. He supervised John Nash's doctoral thesis, and the Karush–Kuhn–Tucker conditions in optimization carry his name. In 1950 he presented Flood and Dresher's game to a group of psychologists at Stanford and needed a story to explain it, so he invented the two prisoners.Reference: A. W. Tucker (1983), “The mathematics of Tucker: a sampler,” Two-Year College Mathematics Journal 14(3), 228–232, which reprints his 1950 note “A two-person dilemma.” formalized it, told the story of the two prisoners and gave the game its name. The Stanford Encyclopedia of Philosophy has more on its history.
The structure shows up wherever individually sensible moves add up to a collectively bad outcome: fare wars between airlines, rival firms escalating their advertising, and price cuts that each firm makes to win customers from the other.
What can the cafés do about it? Asking the other café to keep its price at $6 doesn't help. Even if Café B promises, Café A knows that B still earns more by charging $4, whatever A does, and a promise that goes against the promiser's interest isn't believed. The way out is to change the payoffs, so that undercutting no longer pays. There are three broad ways to do that.
Repetition. In the game above the cafés meet once. In reality they set prices every day. A café that undercuts today earns 400 instead of 300, a gain of 100. But its rival can respond by charging $4 from tomorrow on, and then the undercutter earns 200 a day instead of 300 for as long as that lasts. If the future matters enough, the gain today isn't worth the loss later, and both cafés can keep charging $6. Reading 5 works out when that happens.
Commitment. A café can change its own payoffs in advance. Suppose Café A promises its customers to match any lower price in the street. Now if Café B cuts to $4, A's price falls to $4 too, so B doesn't take every customer. It only splits them at a lower price, 200 instead of 300, and undercutting stops paying. The weekly challenge, Hats, asks when a price-matching promise like this works and when it doesn't.
Changing the game. The cafés are in a dilemma because their coffee is the same, so the cheaper café takes every customer. If they make their products different, say one focuses on specialty pour-over and the other on quick takeaway, a lower price no longer wins all the customers, and the gain from undercutting shrinks. Week 7 studies competition between firms whose products differ.
3.4
Several equilibria
Three classic games each have two equilibria, for different reasons.
Chicken. Two drivers race toward each other on a narrow road, and each can swerve or stay on course. If one swerves and the other doesn't, the one who swerves is the “chicken” and loses face, with a payoff of \(-1\), while the one who stays wins, with 1. If both swerve, nobody wins or loses, and both get 0. If neither swerves, they crash, the worst outcome for both, at \(-10\) each.
If Alice swerves, Bob's best response is to stay, 1 against 0. If Alice stays, Bob's best response is to swerve, \(-1\) against \(-10\). The same holds for Alice, so there are two equilibria, (Swerve, Stay) and (Stay, Swerve). Each player prefers the one in which the other swerves.
Chicken is a game of nerve. Each driver wants the other to back down, and the worst outcome is that neither does. The same structure appears whenever two parties each hope the other will give way: two firms that each want the other to leave a market too small for both, a union and a management heading for a strike, or two countries in a standoff. In chicken, credibility is everything. A driver who could convince the other that it will never swerve, for example by visibly throwing its steering wheel out of the window, would win.
Pure coordination. Alice and Bob want to meet tonight, either at their usual café or at the cinema in their neighborhood. Their phones are dead, so they can't call each other. Neither cares which place it is. What matters is being at the same place: each gets 2 if they meet and 0 if they don't.
If Bob goes to the café, Alice's best response is the café, and if Bob goes to the cinema, it's the cinema. The same holds for Bob. So both (Café, Café) and (Cinema, Cinema) are equilibria, and both players rank them the same way. This is a : there's no conflict at all, only the need to match. What can go wrong is beliefs. Alice goes to the café because she expects Bob to be there, and Bob goes to the cinema for the same reason. Firms face the same problem when they need to agree on a common file format or a meeting place for a trade fair.
The battle of the sexes. This is the ballet game from the start of this reading. Alice prefers the ballet, Bob prefers the opera, and both prefer being together to being apart. Again there are two equilibria, (Ballet, Ballet) and (Opera, Opera). But unlike in pure coordination, the players rank them differently: Alice gets 3 at the ballet and 1 at the opera, and Bob the reverse. They agree that they want to coordinate, and they disagree about where. Two firms that both gain from a common standard, but each prefer the one built around their own technology, are in this game.
When a game has several equilibria, the model narrows the prediction but can't tell us which equilibrium will happen. What decides it depends on the kind of game, and that matters for a manager. In pure coordination the problem is only beliefs: each needs to expect the other to go to the same place. Anything that makes one equilibrium obvious solves it, such as a habit, a convention or a quick message. In chicken and the battle of the sexes, communication alone isn't enough, because each would like to steer toward its own favorite. There, what decides the outcome is often who can commit first, which is where Reading 4 begins.
So it pays to diagnose which kind of game you're in. Firms often spend on building trust when the real problem is who gets the better deal, and on negotiating when the real problem is that nobody wants to move first.
3.5
No equilibrium in pure strategies
In matching pennies, Alice and Bob each hold a coin. Each secretly turns it to heads or tails, and then both reveal their coins at the same time. If the coins match, both heads or both tails, Alice wins and Bob pays her $1. If they don't match, Bob wins and Alice pays him $1. Whatever one player gains, the other loses, so this is a zero-sum game.
No cell has both payoffs shaded. Start anywhere and follow the best responses. Suppose Alice plays Heads. Bob wants the coins not to match, so he plays Tails. Against Tails, Alice wants a match, so she switches to Tails. Against that, Bob switches to Heads, and then Alice switches back to Heads. We're back where we started. In every cell, one of the two players would rather switch. So the game has no Nash equilibrium in pure strategies, that is, with each player choosing one action for sure.
This is not a curiosity. A penalty taker and a goalkeeper, a tax auditor and a taxpayer, and a store choosing which week to run a promotion are all in games like this, and in all of them being predictable is costly. Players do best by keeping the other side guessing. If we allow players to randomize, choosing each action with some probability, an equilibrium exists again. We won't compute those equilibria in this course, but the lesson is useful on its own: when a rival can exploit any pattern in what you do, don't have one.
Name the game
For each matrix, find the pure-strategy Nash equilibria and decide which kind of game it is.
Two firms each choose a technical standard, Old or New. Both earn 9 if both choose New, 5 if both choose Old and 0 if they choose differently.
Both (New, New) and (Old, Old) are equilibria, and both firms prefer (New, New). That's a coordination game. The danger is getting stuck on Old because each firm expects the other to stay there. A public commitment to New can fix that.
Two firms each choose a high or low advertising budget. Each earns 6 if both choose Low, 2 if both choose High, 8 by choosing High against Low and 1 by choosing Low against High.
High is dominant for both: 8 beats 6 and 2 beats 1. The only equilibrium is (High, High), with 2 each, when both would earn 6 at (Low, Low). That's a prisoner's dilemma.
Two firms consider entering a market that has room for only one. Each earns 5 if it enters alone, 0 if it stays out, and loses 4 if both enter.
There are two equilibria, (Enter, Stay out) and (Stay out, Enter), and each firm prefers the one in which it enters. That's the structure of chicken. Whoever can commit to entering first, for example by building capacity, gets its favorite equilibrium.
An inspector chooses whether to inspect, and a factory whether to comply. The inspector gains 1 from catching a violation or from not wasting an inspection on a compliant factory, and loses 1 otherwise. The factory gains 1 from a violation that goes unchecked or from complying when inspected, and loses 1 otherwise.
Follow the best responses around the matrix: against Violate the inspector inspects, against Inspect the factory complies, against Comply the inspector doesn't inspect, against Don't the factory violates. They never settle, so there is no pure-strategy equilibrium. It's matching pennies in another setting.
Summary. A best response is the best strategy against a particular choice of the others. A Nash equilibrium is a combination of strategies in which each player's strategy is a best response to the others', so nobody wants to change alone. In a matrix, it is a cell with both payoffs underlined. An equilibrium can be bad for everyone, as in the cafés' prisoner's dilemma. Chicken, coordination and the battle of the sexes have two equilibria each, and the model can't say which happens. Matching pennies has none in pure strategies.
04
Sequential games
How should you move when others will observe your choice and respond?
In many business decisions, one party moves and the others react. A launch, a price change or an entry decision is public, and the rivals respond to what they see.
This reading draws such games as trees and shows that a later mover's strategy is a whole plan. That makes room for threats, and we'll see that some threats support a Nash equilibrium even though nobody would carry them out. Backward induction removes them.
4.1
The catwalk game
Spring is coming. Allure Avenue, a prominent US fashion house, is choosing between a Sporty line (S) and a Classical line (C). Its choice will be public. DownUnder Style, an Australian brand breaking into the US market, will see Allure's choice and then introduce either its European line (E) or its Outback collection (O).
A like this is represented as a game tree. Each decision node belongs to one player, each branch is an action, and each node at the end of the tree is an outcome with its payoffs, the first mover's first.
There are four possible outcomes. Allure gets 6 and DownUnder 4 after (S, E); 3 and 3 after (S, O); 2 and 2 after (C, E); and 4 and 6 after (C, O).
4.2
A strategy is a plan
In a simultaneous game, a strategy is just an action. In a sequential game, a strategy is a complete plan: it says what the player will do at every point where it might have to move, including points that the game may never reach.
Allure moves once and has two strategies, S and C. DownUnder moves after seeing Allure's choice, so its strategy has to say what it does after S and what it does after C. That gives four strategies. We write them as two letters: the first is DownUnder's line after S and the second its line after C.
| DownUnder's strategy | After S | After C |
|---|---|---|
| EE | European | European |
| EO | European | Outback |
| OE | Outback | European |
| OO | Outback | Outback |
With strategies defined this way, we can write the sequential game as a matrix and look for its Nash equilibria with the tools of Reading 3:
The matrix has three Nash equilibria: (S, EE), (S, EO) and (C, OO). In each of them, neither firm can do better by changing its plan, given the other's plan.
4.3
A threat that isn't credible
Look at (C, OO). DownUnder's plan says: "Outback, whatever you launch." If Allure believes it, Allure compares 3 from Sporty with 4 from Classical and launches Classical. Given Classical, Outback is DownUnder's best reply, earning 6. Both are best responses, so (C, OO) is a Nash equilibrium, and a good one for DownUnder.
But think about what would happen if Allure launched Sporty anyway. DownUnder would then be choosing between European, worth 4, and Outback, worth 3. It would launch European. The plan "Outback whatever you launch" is a threat DownUnder wouldn't carry out once the moment came. Allure, which can work this out, shouldn't believe it.
A is one that the player making it would actually want to carry out if the moment came. DownUnder's threat isn't credible, and an equilibrium that depends on it isn't a sensible prediction.
The equilibrium (S, EE) has a similar flaw, in a place that never gets reached. It plans European after Classical, where Outback would earn DownUnder 6 rather than 2. Allure launches Sporty, so the plan is never tested, but it isn't a plan DownUnder would follow.
The Nash equilibrium checks only that each strategy is a best response to the other strategy as a whole. It doesn't check whether each part of the plan makes sense at the moment it would be used. For sequential games we need a stricter test.
4.4
Backward induction
The stricter test is to require that every player's strategy be a best response at every decision point, including those that aren't reached. We find such strategies by : start at the end of the tree and work back to the beginning.
- Start with the last moves. These are DownUnder's. After Sporty, European gives DownUnder 4 and Outback 3, so it chooses European. After Classical, European gives 2 and Outback 6, so it chooses Outback.
- Replace each last move with its outcome. Sporty now leads to (6, 4) and Classical to (4, 6).
- Move back one step. Allure anticipates DownUnder's replies. Sporty gives Allure 6 and Classical 4, so Allure launches Sporty.
The result is that Allure plays S and DownUnder plays EO, European after Sporty and Outback after Classical. This is the of the game. Allure launches Sporty, DownUnder answers with European, and the payoffs are 6 and 4.
Of the three Nash equilibria, only (S, EO) survives. It's the only one in which DownUnder's plan is optimal at both of its decision points. A credible Nash equilibrium is always a Nash equilibrium, but not every Nash equilibrium is credible.
Notice who does well here. Moving first lets Allure pick the branch, knowing how DownUnder will answer, and it gets 6. Under the non-credible equilibrium it would have got 4. That isn't true of every game, though. If matching pennies were played in sequence, the player who sees the other's coin first would always win, so there the second mover has the advantage.
Is the threat credible?
An incumbent tells a potential entrant: "If you enter, we'll start a price war." After entry, a price war earns the incumbent 2 and sharing the market earns it 5. Is the threat credible?
Backward induction asks what the incumbent would choose once entry has happened: 5 from sharing against 2 from fighting. So it would share, and an entrant who works that out isn't deterred. Reputation could change this, but only by changing the payoffs, for example if the incumbent faces other potential entrants later. Week 8 returns to this game.
Change one number: after entry, a price war earns the incumbent 6 and sharing earns 5. Is the threat credible now?
Now fighting is the incumbent's best reply to entry, 6 against 5, so it would carry out the threat. Whether a threat is credible depends on the payoff from carrying it out, not on how harsh it is.
4.5
Where sequential games show up
Many strategic situations are best described as sequential games:
- Market entry. An entrant has to anticipate how incumbents will react once it's in.
- English auctions. Bidders see the current high bid and decide whether to raise it.
- Labor negotiations. Employers and unions make offers in turn, each responding to the last.
- Product launches. A firm's timing and design depend on what its rivals have launched and on how they'll respond.
In each case, the question for the first mover is the one Allure asked: what will the others do once they see my move? And the question for anyone hearing a threat or a promise is whether the person making it would want to follow through.
4.6
Centipede and ultimatum: what people actually do
Backward induction gives sharp predictions. Two classic games test them.
The centipede game. Two players take turns. At each turn, the player can stop the game and take the payoffs shown, or continue, which passes the move to the other player and makes the total payoff larger. Here is an eight-move version. If both always continue, the game ends with 8 for Player 1 and 6 for Player 2.
Start at the end. At move 8, Player 2 compares 7 from stopping with 6 from continuing, and stops. At move 7, Player 1 knows this: continuing gives 6, stopping gives 7, so Player 1 stops. The same comparison repeats at every move, all the way back to the first. Backward induction predicts that Player 1 stops immediately, taking 1 and leaving Player 2 with 0, although both could have had far more.
The ultimatum game. A proposer has $100 and offers the responder a share of it. The proposer keeps \(x\) and offers \(100-x\). The responder accepts or rejects. If the responder accepts, both get their shares. If the responder rejects, both get nothing.
Backward induction is quick. A responder who cares only about money accepts any positive offer, because something beats nothing. Knowing that, the proposer offers the smallest positive amount. The credible Nash equilibrium is a tiny offer, accepted.
In experiments, people don't play either game this way. Many players continue in the centipede game for several moves. In the ultimatum game, responders often reject offers they see as unfair, even though rejecting costs them money, and proposers, anticipating this, offer much more than the minimum.
That doesn't mean the logic of backward induction is wrong. It means the payoffs were. Reading 1 said a payoff can include anything a player cares about. A responder who would rather walk away than accept $1 out of $100 has a payoff that includes fairness, and with those payoffs backward induction predicts a larger offer. The ultimatum game is also a stark version of the bargaining you saw in Week 1, where one side makes a take-it-or-leave-it offer.
Summary. In a sequential game, a strategy is a complete plan: an action for every point where the player might move. A Nash equilibrium of a sequential game can rest on a threat that the player wouldn't carry out, such as DownUnder's "Outback whatever you launch". Backward induction solves the game from the end and keeps only plans that are optimal at every decision point. The result is the credible Nash equilibrium: in the catwalk game, Allure launches Sporty and DownUnder answers with European.
05
Playing repeatedly
Can the shadow of the future make rivals cooperate?
The cafés' prisoner's dilemma was played once. But two cafés across the street from each other set prices every day, and they'll be there tomorrow.
This reading asks how that changes players' behavior. Repetition lets each player make today's choice depend on what happened in the past, so a deviation today can be punished tomorrow. Whether that threat sustains cooperation depends on how much the players care about the future.
5.1
The same rivals, every day
In a , the same players play the same game, the , again and again. Each period's payoffs add up, and each player can condition what they do today on what happened in the past.
In this reading the stage game is the prisoner's dilemma below. It has the same structure as the cafés' pricing game. If a café charges $6, we call it cooperating, and if it charges $4, we call it defecting. Defect is a dominant strategy for both Alice and Bob: against Cooperate it pays 5 instead of 3, and against Defect it pays 1 instead of 0. So (Defect, Defect) is the only Nash equilibrium of the stage game, although both would be better off at (Cooperate, Cooperate).
Repetition changes what a strategy can be. In the one-shot game, Alice just picks an action. In the repeated game she can follow a rule such as "I'll cooperate as long as you do" or "if you defect, I'll defect from then on." Rules like these reward cooperation and punish deviation, and they make the future part of today's decision.
We'll suppose the game goes on indefinitely: neither player knows of a last period. The last section of this reading explains why that matters.
5.2
Valuing a stream of payoffs
Payoffs now arrive over time, and a dollar tomorrow is worth less than a dollar today. Today's dollar can be invested to earn interest, prices may rise, and there's always some chance that tomorrow's payment never comes, for example because the relationship ends.
We summarize all of this with a \(\delta\), between 0 and 1: one dollar received one period from now is worth \(\delta\) dollars today.
You may have seen the same idea as a . The discount rate \(r\) is the percentage rate used to bring future payments back to their present value, and it reflects interest, inflation, and risk. One dollar today grows to \(1+r\) dollars next period, so one dollar next period is worth \(1/(1+r)\) today. The two are linked by \(\delta=\dfrac{1}{1+r}\). A discount rate of 10% gives \(\delta=1/1.1\approx0.91\).
A dollar two periods from now is worth \(\delta^2\), and so on. What is an infinite stream of one dollar every period, starting today, worth? Call its value \(V\):
With \(\delta=0.9\), a dollar every period is worth \(1/0.1=10\) today. With \(\delta=0.5\) it's worth 2. The larger \(\delta\) is, the more the future counts.
What if the stream stops after period \(T\)?
Suppose the dollar arrives in periods \(0, 1, \ldots, T\) and then stops. Call its value \(V_T\). It's the infinite stream minus the part that starts in period \(T+1\). That part is itself an infinite stream of one dollar a period, only pushed \(T+1\) periods into the future, so today it's worth \(\delta^{T+1}V\):
With \(\delta=0.9\) and \(T=9\), ten payments are worth \((1-0.9^{10})/0.1\approx6.51\). As \(T\) grows, \(\delta^{T+1}\) shrinks toward 0 and \(V_T\) approaches \(1/(1-\delta)\).
5.3
Grim trigger
Repetition makes cooperation possible, but not automatic. The players need strategies that make cooperating pay. The idea behind all of them is a simple deal: keep cooperating and you'll be rewarded with cooperation tomorrow; deviate and you'll be punished. The question is whether such a deal can be a Nash equilibrium of the repeated game, so that neither player wants to break it. We'll study two strategies that can do this, grim trigger and tit-for-tat. They differ in how hard they punish.
Suppose Alice follows : cooperate as long as both players have always cooperated; after the first period in which anyone defects, defect forever. Should Bob keep cooperating?
Suppose Bob considers deviating in some period \(t\). Up to period \(t-1\) both have cooperated, and nothing Bob does now changes those payoffs. So we compare what he gets from period \(t\) on, valued in period \(t\).
If Bob keeps cooperating, he earns 3 every period:
If Bob deviates in period \(t\), he earns 5, because Alice still cooperates in that period. From period \(t+1\) on, Alice defects forever, and Bob's best reply is to defect too, so he earns 1 a period:
Bob keeps cooperating if cooperating is worth at least as much as deviating:
Valued from period 0 instead, both streams would be multiplied by \(\delta^t\), which doesn't change the comparison. So the condition is the same in every period: if Bob doesn't want to deviate in period 0, he doesn't want to deviate later either.
The same holds for Alice. So if both follow grim trigger and \(\delta\geq\frac{1}{2}\), both cooperate in every period, and neither gains by deviating. The gain from deviating is 2 in period \(t\). The cost is 2 a period forever after, starting in period \(t+1\). With enough patience, the cost wins.
Is the punishment itself believable? After a deviation, grim trigger has both players defect forever. Since (Defect, Defect) is a Nash equilibrium of the stage game, neither player can do better by deviating from the punishment. So the threat behind grim trigger is credible in the sense of Reading 4.
5.4
Tit-for-tat
Grim trigger never forgives. is gentler: cooperate in the first period, then copy whatever the other player did in the previous period. A deviation is punished for one period, and if the deviator returns to cooperating, so does the punisher.
Against tit-for-tat, Bob has two ways to deviate in period \(t\), and cooperating has to beat both.
Deviate forever. Bob earns 5 in period \(t\) and, since Alice then defects every period, 1 a period after that. That's the same stream as under grim trigger, so it needs \(\delta\geq\frac{1}{2}\).
Deviate once, then return. In period \(t\) Bob earns 5. In period \(t+1\) Alice punishes by defecting while Bob is back to cooperating, so Bob earns 0. From period \(t+2\) on, both cooperate again. The two streams are the same from period \(t+2\) on, so compare periods \(t\) and \(t+1\):
Both conditions must hold, so tit-for-tat sustains cooperation when \(\delta\geq\frac{2}{3}\). That's more patience than grim trigger needs.
That's the general pattern. Grim trigger is the harshest punishment available, so it sustains cooperation for the widest range of discount factors. A forgiving strategy like tit-for-tat punishes less, so it never needs less patience than grim trigger and sometimes needs more. What it offers in return is a way back to cooperation after a mistake, which grim trigger never allows.
5.5
What the shadow of the future can and can't do
The result is a general one. In a repeated prisoner's dilemma, cooperation can be sustained when players are patient enough, and how patient they must be depends on the payoffs. A bigger gain from deviating today, or a milder punishment, needs a larger \(\delta\).
What makes \(\delta\) large in practice? Frequent interaction, so that the next period comes soon, and a relationship that is likely to last. Rivals that set prices daily and expect to compete with each other for years are in a good position to cooperate. A business that expects to close next month, or a rival that's about to be bought out, isn't.
Two limits matter.
A known last period unravels cooperation. Suppose both players know that the game ends after exactly 100 periods. In period 100 there's no tomorrow to protect, so the game is a one-shot prisoner's dilemma, and both defect. In period 99, both know that period 100 will be (Defect, Defect) whatever happens, so nothing today can be rewarded or punished tomorrow, and both defect again. Backward induction runs all the way back to period 1. That's why we assumed the game goes on with no known end.
Cooperation is possible, not guaranteed. Even when \(\delta\geq\frac{1}{2}\), both players defecting in every period is still an equilibrium of the repeated game. Repetition adds cooperative equilibria; it doesn't remove the bad one.
5.6
Looking ahead to Week 7
This week's games had two or three strategies per player. In Week 7, firms choose any price or any quantity, and the same tools give us the equilibria of oligopoly markets. The prisoner's dilemma comes back too: a cartel is a group of firms trying to keep prices high when each would gain by cutting its own price, and the repeated game tells us when that can last.
Summary. In a repeated game, today's choice can be rewarded or punished tomorrow. An infinite stream of one dollar a period is worth \(1/(1-\delta)\), where \(\delta\) is the discount factor. Under grim trigger, the players in the prisoner's dilemma keep cooperating if \(3/(1-\delta)\geq5+\delta/(1-\delta)\), that is \(\delta\geq\frac{1}{2}\). Tit-for-tat punishes less and needs \(\delta\geq\frac{2}{3}\). Cooperation needs a future that matters and no known last period, and even then the bad equilibrium remains.