Game Theory · Chapter 6

Sequential Games and Backward Induction

“If you enter my market, I’ll start a price war.” Should a newcomer believe that? Not if, once it has entered, a price war would hurt the incumbent more than sharing the market. In games played in turns, the way to think is to look ahead to the end and reason back. Here you’ll build game trees and watch them solved from the leaves up, find the equilibria that rest on empty threats, see how a commitment can make a threat believable, test the theory against how people play the ultimatum and centipede games, and find out when moving first pays.

Tree

Edit the selected node

Strategic form

Missions

What you’re seeing

The tree. The game starts at the top. Each circle is a decision: the number says whose (gold 1 or blue 2). Each line below it is an action, and the boxes at the bottom are the outcomes, with player 1’s payoff first. Everyone sees every earlier move: these are games of perfect information.

Solving. Press Solve and the program starts at the decisions closest to the end. At each one it compares the payoffs the mover would get from each action, using the values already worked out below, keeps the best action (a thick colored line) and writes the resulting payoffs next to the node in green. Then it moves up a level. When it reaches the top, the thick lines show what every player would do at every point, and the green boxes show the path that is actually played.

You solve. The same procedure, by hand: the highlighted node is the next one to decide. A wrong pick tells you what that action would have given the mover.

Editing. Click any node or payoff box to change who moves, rename an action, change payoffs, add an action or turn an end into a new decision. The strategic form in the panel updates for small trees: click its cells to test which Nash equilibria survive backward induction.

Game trees and strategies

A game in which players move in turns is called an extensive game. With perfect information, Osborne describes it by its players, the possible sequences of actions (histories), which ones end the game (terminal histories), who moves after each non-terminal history (the player function), and each player’s preferences over terminal histories. The tree draws all of that.

A strategy in an extensive game is a complete plan: it specifies an action at every node where the player moves, including nodes that the plan itself makes sure are never reached. That sounds pedantic, but it is exactly what lets us ask whether a threat is believable: the plan “fight if you enter” has to say what happens at the node after entry, even if, because of the threat, entry never happens.

Worked example: the entry game

A potential entrant decides whether to enter a market (In) or not (Out). If it enters, the incumbent can fight with a price war or accommodate. Payoffs in millions of dollars of profit (invented): Out gives the entrant 0 and the incumbent 4; In followed by Fight gives −1 and 1; In followed by Accommodate gives 1 and 2.

Backward induction. After entry, the incumbent compares Fight (1) with Accommodate (2) and accommodates. The entrant, foreseeing that, compares Out (0) with In (1) and enters. Outcome: (In, Accommodate), payoffs (1, 2).
The strategic form. The entrant has two strategies, the incumbent two (Fight or Accommodate, “if entry happens”):

Entrant	Fight	Accommodate
	Incumbent
Out	0, 4	0, 4
In	−1, 1	1, 2

Two Nash equilibria. (In, Accommodate), and also (Out, Fight): if the incumbent’s plan is to fight, staying out is the entrant’s best response, and given that the entrant stays out, the incumbent loses nothing by planning to fight, since the plan is never tested.
Only one is believable. (Out, Fight) rests on a threat the incumbent would not carry out: at the node after entry, fighting gives it 1 instead of 2. Backward induction throws that equilibrium away.

Subgame perfect equilibrium

Every node of a perfect-information tree starts a smaller game, a subgame: the part of the tree below it. Reinhard Selten’s idea (1965) was to require equilibrium play not only in the whole game but in every subgame.

a strategy profile is a subgame perfect equilibrium if it is a Nash equilibrium of every subgamein a finite game of perfect information, backward induction finds the subgame perfect equilibria; if no player is ever indifferent, there is exactly one

The result that a finite game of perfect information can always be solved this way goes back to Ernst Zermelo’s 1913 paper on chess and was stated in general by Harold Kuhn (1953). It is why chess has a definite value, a win for White, a win for Black or a draw, even though nobody knows which.

Try this: In the entry game, click the incumbent’s Fight payoff box and change its 1 to 3. Solve again: now fighting is what the incumbent would really do, the threat is credible, and the entrant stays out.

Try this: Load the centipede game and solve it. Each player would rather take the pot now than pass it to an opponent who will take it next, so the game ends at the first move with (1, 0), though both could have had more by passing to the end.

Credible threats and commitment

A threat works only if it would be in the threatener’s interest to carry it out when the time comes. The cleverest strategic moves therefore change your own future payoffs. Thomas Schelling called this the paradox of commitment: by limiting your options, or making some of them costly, you can be better off, because others then believe what you say. Generals have burned bridges behind their armies so that retreat was impossible.

Worked example: investing to deter entry

Before the entrant decides, the incumbent can invest in extra capacity. The investment costs it 1 (million dollars) but makes a price war cheaper to fight: after investing, fighting an entrant gives the incumbent 1.5 and accommodating, with expensive capacity standing idle, only 1. Load “Commitment” to see the tree.

Without the investment, the game is the entry game above: the entrant enters, the incumbent accommodates, and the incumbent gets 2.
With the investment, the incumbent would fight (1.5 > 1), so the entrant, expecting −1 from entering, stays out. The incumbent gets 4 − 1 = 3.
3 > 2, so the incumbent invests. The investment pays not because the extra capacity is used, but because it changes what the incumbent would do, and the entrant knows it.

Business is full of commitments: capacity built ahead of demand, contracts that promise customers the lowest price, long-term supply agreements, public announcements that would be embarrassing to reverse. Tata Motors publicly committed to a price of 100,000 rupees for the Nano; the case Tata Nano: The Car Nobody Wanted to Be Seen In asks whether that commitment helped or hurt. Commitments are also costly: they take away flexibility when circumstances change.

Common mistake: “Moving first is always an advantage”

Moving first lets you commit, and that helps when your commitment pushes the other player in a direction you like, as with the Stackelberg leader below. But moving first also reveals your choice. In matching pennies played in turns, the second player simply matches (or mismatches) and always wins. In price competition with differentiated products, the follower can undercut a leader’s announced price. Whether the first or the second mover has the advantage depends on the game.

What people actually do: ultimatums and centipedes

Backward induction makes sharp predictions, and two famous games test them. In the ultimatum game, a proposer offers a split of $10 and a responder accepts or rejects; rejecting leaves both with nothing. A responder who cares only about money accepts any positive offer, so the proposer should offer the smallest possible amount. In the centipede game, players alternately choose between taking a growing pot and passing it on; backward induction says the first player takes at once.

In the experiment that started this literature, Werner Güth, Rolf Schmittberger and Bernd Schwarze (1982) found that proposers offered far more than the minimum and that low offers were often rejected. Hundreds of studies since agree: the most common offers are 40 to 50 percent of the pie, a review of 37 studies by Hessel Oosterbeek, Randolph Sloof and Gijs van de Kuilen (2004) found an average offer of about 40 percent, and offers below about 20 percent are rejected roughly half the time (Colin Camerer, Behavioral Game Theory, 2003). The simulated “typical” responder above has a curve with that shape; it isn’t fitted to any one study.

Does that refute backward induction? Not exactly. Backward induction is a statement about players whose payoffs are the dollar amounts. Rejecting an insulting offer says that the responder’s payoff includes something else, such as fairness or the satisfaction of punishing a greedy proposer, and a proposer who knows that is right to offer more. In the centipede game, Richard McKelvey and Thomas Palfrey (1992) found that very few players took at the first opportunity; most passed at least once. A small chance that the other player is an altruist who always passes can make passing rational, which is the same logic of reputation that Chapter 7 develops.

Stackelberg: the value of moving first

Take the Cournot market of Chapter 5 (price = 100 − total output, cost $10), but let firm 1 choose its output first and firm 2 see it before choosing. Heinrich von Stackelberg studied this in 1934. Backward induction: the follower best responds to whatever it sees, q₂ = (90 − q₁)/2, so the leader chooses the point on the follower’s best-response line that is best for itself.

The leader’s choice

Leader’s output q₁

Worked example: leader and follower

The leader’s profit, given the follower’s reply, is (100 − q₁ − (90 − q₁)/2 − 10)q₁ = (45 − q₁/2)q₁.
Setting the derivative to zero: 45 − q₁ = 0, so q₁ = 45, and the follower replies q₂ = 22.5.
Price 100 − 67.5 = $32.50. Profits: leader 22.5 × 45 = 1,012.5, follower 22.5 × 22.5 = 506.25, against 900 each in Cournot.

The leader commits to producing a lot, and because quantities are strategic substitutes the follower backs off. Total output (67.5) is higher than under Cournot (60), so customers gain too. Note that the leader’s 45 is not a best response to 22.5 (that would be 33.75): the leader gains precisely because it can’t revise its choice. Without commitment, its lead would be worthless.

A short history

Ernst Zermelo (1913) analyzed chess as a finite game of perfect information. John von Neumann and Oskar Morgenstern (1944) introduced the extensive form, and Harold Kuhn (1953) gave the general definition of extensive games and proved that games of perfect information have equilibria in pure strategies, found by backward induction. Heinrich von Stackelberg’s Marktform und Gleichgewicht (1934) studied leadership in markets. Thomas Schelling’s The Strategy of Conflict (1960) made commitment and credibility central. Reinhard Selten defined subgame perfection in 1965, in a paper on an oligopoly with demand inertia, and in 1978 posed the “chain-store paradox”: an incumbent facing a long series of entrants should, by backward induction, accommodate every one, though intuition says it should fight early to build a reputation. Robert Rosenthal introduced the centipede game in 1981 in the same spirit. Explaining the paradoxes led to the theory of reputation (Chapter 7) and of incomplete information (Chapter 8).

Where you see it

Business: entry deterrence, capacity races, price-matching promises, exclusive contracts. Early movers can lock in customers and scale, as Amazon did when it began selling the computing infrastructure it had built for itself (Amazon Web Services); Henry Ford’s five-dollar day was a first move in the labor market that rivals then had to match (Henry Ford’s Five-Dollar Day).
Negotiation: “final offers” that aren’t final, deadlines, and the ultimatum game’s lesson that a lowball offer can be refused even when refusing costs the responder.
Politics: veto threats, brinkmanship, and constitutional rules that commit future governments.
Games and sports: chess and checkers endgames are solved by backward induction; computers solved checkers completely in 2007 (it is a draw with perfect play).
Daily life: a parent’s threat to cancel a vacation if the kids don’t behave is credible only if the parent would really cancel it. Kids are good at backward induction.

Practice

Solve a tree. Player 1 chooses L or R. After L, player 2 chooses a, giving (3, 1), or b, giving (0, 2). After R, player 2 chooses c, giving (2, 2), or d, giving (1, 3). Find the subgame perfect equilibrium.
Show the answer
After L, player 2 picks b (2 > 1), so L leads to (0, 2). After R, player 2 picks d (3 > 2), so R leads to (1, 3). Player 1 compares 0 and 1 and picks R. Equilibrium: player 1 plays R; player 2 plays b after L and d after R. Outcome (1, 3).
Counting strategies. In the problem above, how many strategies does player 2 have? Write them all.
Show the answer
Player 2 moves at two nodes with two actions each: 2 × 2 = 4 strategies: (a, c), (a, d), (b, c), (b, d), each meaning “this after L, that after R.”
When is the threat credible? In the entry game, the incumbent gets x from fighting an entrant (and 2 from accommodating, 4 if the entrant stays out). For which x does the entrant stay out in the subgame perfect equilibrium?
Show the answer
The incumbent fights if x > 2. Then the entrant compares −1 (enter and be fought) with 0 (stay out) and stays out. So the entrant stays out exactly when x > 2. (At x = 2 the incumbent is indifferent and there are two subgame perfect equilibria.)
Stackelberg with other numbers. Demand is P = 120 − Q and cost is $20. Find the Stackelberg outputs and profits and compare them with Cournot.
Show the answer
Follower: q₂ = (100 − q₁)/2. Leader maximizes (50 − q₁/2)q₁: q₁ = 50, q₂ = 25, price $45, profits 1,250 and 625. Cournot: 33.3 each, price $53.33, profit about 1,111 each. The leader gains 139, the follower loses 486, consumers gain from the lower price.
The ultimatum game on a grid. The proposer must offer a whole number of dollars from $0 to $10, and the responder cares only about money. Find all subgame perfect equilibria.
Show the answer
The responder accepts any offer of $1 or more (something beats nothing). At $0 the responder is indifferent, so either reply is a best response. If the responder accepts $0, the proposer offers $0 and keeps $10. If the responder rejects $0, the proposer offers $1 and keeps $9. Both are subgame perfect.
Why pass in the centipede? In the centipede tree of the interactive, suppose player 1 thinks player 2 will pass at the second node with probability π (and take otherwise), and that player 1 would then take at the third node, getting 3. For which π does player 1 prefer to pass at the first node?
Show the answer
Taking at once gives 1. Passing gives 3 with probability π (player 2 passes, then player 1 takes) and 0 with probability 1 − π. Pass if 3π > 1, that is π > 1/3. A modest doubt about the other player’s rationality, or a belief that they are kind, is enough to make passing sensible.
A second-mover advantage. In matching pennies, player 1 wins (+1) if the coins match and player 2 wins if they differ. Suppose player 1 must show her coin before player 2 chooses. Solve the game and compare with the simultaneous version.
Show the answer
Whatever player 1 shows, player 2 picks the other side and wins. Backward induction: player 1 gets −1 whatever she does. In the simultaneous game each wins with probability 1/2 (expected payoff 0, Chapter 4). Moving first is a disadvantage when it reveals information that the other player can exploit.

How the interactives work

Trees. Backward induction is computed recursively: each end node’s value is its payoffs; each decision node takes the value of the child that gives the mover the highest payoff (ties go to the first action listed, and the program says so). The strategic form lists every strategy (an action at each of a player’s nodes) and plays the tree out for every pair; pure Nash equilibria are found with the best-response test of Chapter 3, and the subgame perfect profile is the one matching backward induction at every node. Random trees have depth two or three, two or three actions per node, payoffs from 0 to 9, and no ties.

Bots. The “typical” responder accepts an offer that is a share s of the pie with probability 0.02 + 0.97/(1 + e^{−22(s − 0.2)}): about 12% for $1, 51% for $2, 89% for $3, and 98% or more from $4 up. The typical proposer offers $4 or $5 most of the time and $1 or $2 occasionally (mean about $4.03). The centipede bot passes early and takes later. The money-maximizer accepts any positive offer.

Checks (node). The entry game solves to (In, Accommodate) with payoffs (1, 2); its strategic form has exactly two pure equilibria, and only (In, Accommodate) is subgame perfect. The commitment tree solves to Invest, then Out, with the incumbent getting 3. The centipede solves to Take at once with (1, 0); the ultimatum tree to the smallest offer; the discrete Stackelberg tree to the leader choosing 45. In 300 random trees, the backward-induction profile was always a Nash equilibrium of the strategic form. Stackelberg: 45 and 22.5 with profits 1,012.5 and 506.25; a brute-force search over the leader’s output in steps of 0.01 found the maximum at 45.

Check yourself

A strategy in an extensive game is …
Show the answer
Including nodes that are never reached. That is what makes it possible to ask whether a threat would really be carried out.
In the entry game, why isn’t (Out, Fight) subgame perfect?
Show the answer
It is a Nash equilibrium, but in the subgame after entry the incumbent’s planned action is not a best response.
The incumbent in the commitment game is better off investing because …
Show the answer
The investment costs 1, but it turns an empty threat into a credible one, worth 4 − 1 = 3 instead of 2.
In ultimatum-game experiments, offers below about 20 percent of the pie are …
Show the answer
People give up money to reject offers they see as unfair. Their payoffs aren’t just dollars.
In the Stackelberg example, the leader produces 45 and earns more than in Cournot. What makes this possible?
Show the answer
Same costs, rational follower. The advantage comes entirely from commitment plus strategic substitutes.

Sources

M. J. Osborne, An Introduction to Game Theory (Oxford University Press, 2004), chapters 5 and 6 (extensive games with perfect information: theory and illustrations, including the ultimatum game and Stackelberg’s duopoly).
R. Selten, “Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit”, Zeitschrift für die gesamte Staatswissenschaft 121, 1965; “The chain store paradox”, Theory and Decision 9, 1978, 127–159.
H. W. Kuhn, “Extensive games and the problem of information”, in Contributions to the Theory of Games II (Princeton University Press, 1953).
W. Güth, R. Schmittberger and B. Schwarze, “An experimental analysis of ultimatum bargaining”, Journal of Economic Behavior and Organization 3(4), 1982, 367–388; Ultimatum game (Wikipedia, for the review by Oosterbeek, Sloof and van de Kuilen, Experimental Economics, 2004).
C. F. Camerer, Behavioral Game Theory (Princeton University Press, 2003), chapter 2.
R. W. Rosenthal, “Games of perfect information, predatory pricing and the chain-store paradox”, Journal of Economic Theory 25(1), 1981, 92–100; R. D. McKelvey and T. R. Palfrey, “An experimental study of the centipede game”, Econometrica 60(4), 1992, 803–836; Centipede game (Wikipedia).
H. von Stackelberg, Marktform und Gleichgewicht (Springer, 1934). T. C. Schelling, The Strategy of Conflict (Harvard University Press, 1960).
Ben Polak, Yale ECON 159, Lecture 16: Backward Induction: Reputation and Duels.

I finished this chapterSaved on this device only.