«Contents. 1 Nash Equilibrium in Extensive Form Games 2 1.1 Selten’s Game......... 1.2 The Little Horsey....... 1.3 Giving Gifts.. ...»
We were a little vague in the preceding paragraph. Before we formally deﬁne what a subgame perfect equilibrium is, we must deﬁne what constitutes a “proper subgame.” It really isn’t hard: a proper subgame is any part of a game that can be analyzed as a game itself.
Definition 4. A proper subgame G of an extensive-form game Γ consists of a single decision node and all its successors in Γ with the property that if x ∈ G and x ∈ h(x ), then x ∈ G as well. The payoﬀs are inherited from the original game.
If the game has multiple Nash equilibria, then players must agree on which of them would occur. We shall examine this weakness in the following section.
That is, x and x are in the same information set in the subgame if and only if they are in the same information set in the original game. The payoﬀs in the subgame are the same as the payoﬀs in the original game only restricted to the terminal nodes of the subgame. Note that the word “proper” does not mean strict inclusion as in the term “proper subset.” Any game is always a proper subgame of itself.6 Proper subgames are quite easy to identify in a broad class of extensive form games. For example, in games of complete and perfect information, every information set (a singleton) begins a proper subgame (which then extends all the way to the end of the tree of the original game). Each of these subgames represents a situation that can occur in the original game.
On the other hand, splitting information sets in games of imperfect information produces subgames that are not proper because they represent situations that cannot occur in the original game. Consider, for example, the game Fig. 15 (p. 22) and two candidate subgames.
The two subgames to the right of the original game are not proper. The ﬁrst one fails the requirement that a proper subgame begin with a single decision node. The second one fails the requirement that if two decision nodes are in the same information set in the original game, they must also be in the same information set in the proper subgame.
The reasons for these restrictions are intuitive. In the ﬁrst case, player 2 needs to know the relative probabilities for the decision nodes x and x but the “game” speciﬁcation does not provide these probabilities. Therefore, we cannot analyze this situation as a separate game.
In the second case, player 2 knows that player 1 did not play D, and so has more information than in the original game, where he did not know that.
To make things a little easier, here are some guidelines for identifying subgames. A subgame (a) always starts with a single decision node, (b) contains all successors to that node, and (c) if it contains a node in an information set, then it contains all nodes in that information set. (Never split information sets.) Now, given these restrictions, the payoﬀs conditional on reaching a proper subgame are well deﬁned. We can therefore test whether strategies are a Nash equilibrium in the proper subgame as we normally do. This allows us to state the new solution concept.
Definition 5. A behavior strategy proﬁle σ of an extensive form game is a subgame perfect equilibrium if the restriction of σ to G is a Nash equilibrium for every proper subgame G.
You should now see why it was necessary to deﬁne the behavior strategies: some proper subgames (e.g. the one in F&T’s Game from Fig. 14 (p. 21)) have subgames where the Nash Rasmusen departs from the convention in his book Games and Information, where he deﬁnes a proper subgame to mean strict inclusion, and so he excludes the entire game from the set. We shall follow the convention.
equilibrium is in mixed strategies, which requires that players be able to mix at each information set. (You should at this point go over the diﬀerence between mixed and behavior strategies in extensive-form games.) This now allows us to solve games like the one in Fig. 14 (p. 21). There are three proper subgames: the entire game, the subgame beginning with player 2’s information set, and the subgame that includes the simultaneous moves game. We shall work, as we did with backward induction, our way up the tree. The smallest proper subgame has a unique Nash equilibrium in mixed strategies, where each player chooses one of the two available actions with the same probability of.5. Given these strategies, each player’s expected payoﬀ from the subgame is 0. This now means that player 2 will choose L at her information set because doing so nets her a payoﬀs strictly larger than choosing R and receiving the expected payoﬀ of the simultaneous-moves subgame. Given that player 2 chooses L at her information set, player 1’s optimal course of action is to go D at the initial node. So, the subgame perfect equilibrium of this game is (D, 1/2), (L, 1/2).
Let’s compare this to the normal and reduced normal forms of this extensive-form game;
both of which are shown in Fig. 16 (p. 23).
(0, 1/2, 1/2), (1, 0, 0) which is precisely the subgame-perfect equilibrium we already found.
At this point you should make sure you can ﬁnd this mixed strategy Nash equilibrium.
Suppose player 2 chooses RC for sure, then DB is strictly dominated, so player 1 will not use it. However, this now means RD strictly dominates RC for player 2, a contradiction. Suppose now that she chooses RD for sure. Then DA is strictly dominated, so player 1 will not use it. But now RC strictly dominates RD, a contradiction. Therefore, there is no equilibrium in which player 2 chooses either RC or RD for sure. Suppose player 2 puts positive weight on L and RC only. Then, DA is strictly dominant for player 1. However, 2’s best response to DA is RD, a contradiction with supposition that she does not play it. Hence, no MSNE in which she plays only L and RC. Suppose now that she plays L and RD only. Then DB is strictly dominant, but player 2’s best response to this is RC, a contradiction. Hence, no MSNE in which she plays only L and RD either. Suppose next that she plays RC and RD only. Then U is strictly dominant, and since player 2’s payoﬀ is the same against U regardless of the strategy she uses, we have a continuum of MSNE: U, σ2 (RC) ∈ (0, 1), σ2 (RD) = 1 − σ2 (RC).
Suppose next she plays L for sure. Then player 1 is indiﬀerent between DA and DB, each of which strictly dominates U, so he can mix with σ1 (DA) ∈ (0, 1) and σ1 (DB) = 1 − σ1 (DA).
Since player 2 must not be willing to use any of her other pure strategies, it follows that U2 (σ1 (DA), RC) ≤ 1 σ1 (DA) ≥ 1/4, and U2 (σ1 (DA), RD) ≤ 1 σ1 (DA) ≤ 3/4. Therefore, σ1 (DA) ∈ [ 4 4 1/, 3/ ] are all admissible mixtures, and we have a continuum of MSNE. The subgame-perfect MSNE is among these: the one with σ1 (DA) = 1/2.7 As you can see, we found a lot of MSNE but only one of them is subgame-perfect. This reiterates the point that all SPE are Nash, while not all Nash equilibria are subgame-perfect.
Note the diﬀerent way of specifying the equilibrium in the extensive form and in the reduced normal form.
We can now state a very important result that guarantees that we can ﬁnd subgame perfect equilibria for a great many games.
Theorem 5. Every ﬁnite extensive game with perfect information has a subgame perfect Nash equilibrium.
To prove this theorem, simply apply backward induction to deﬁne the optimal strategies for each subgame in the game. The resulting strategy proﬁle is subgame perfect.
Let’s revisit our basic escalation game from Fig. 10 (p. 19). It has three subgames, shown in Fig. 17 (p. 24) and labeled I, II, and III. What are the pure-strategy Nash equilibria in all these subgames? We have already found the three equilibria of subgame I: (∼e, a), r, (∼e, ∼a), r, and (e, a), ∼r. The Nash equilibrium of subgame III is trivial: ∼a. You should verify (e.g. by writing the normal form) that the Nash equilibria of subgame II are: a, ∼r and ∼a, r.
Of the three equilibria in subgame I (the original game), which ones are subgame perfect?
That is, in which of these do the strategies constitute Nash equilibria in all subgames? The restriction of the strategies to subgame II shows that no strategy proﬁle that involves anything other than the combinations a, ∼r and ∼a, r would be subgame perfect. This eliminates the Nash equilibrium proﬁle (∼e, a), r of the original game. Further, the restriction of the strategies to game III demonstrates that no proﬁle that involves player 1 choosing anything other than ∼a would be subgame perfect either. This eliminates the Nash equilibrium proﬁle (e, a), ∼r of the original game. There are no more subgames to check, and therefore all remaining Nash equilibria are subgame perfect.
There is only one remaining Nash equilibrium:
I leave the ﬁnal possibility as an exercise: what happens if player 2 puts positive weight on all three of her strategies?
(∼e, ∼a), r and this is the unique subgame perfect equilibrium. Of course, it is the one we got from our backward induction method as well.
Subgame perfection (and backward induction) eliminates equilibria based upon non-credible threats and/or promises. This is accomplished by requiring that players are rational at every point in the game where they must take action. That is, their strategies must be optimal at every information set, which is is a much stronger requirement than the one for Nash equilibrium, which only demands rationality at the ﬁrst information set. This property is, of course, sequential rationality, just as we deﬁned it above.
4 Practice with Subgame Perfection
3,0 1,0 1,1 2,1 2,2 1,3 Consider player 2’s information set after history R. Playing f is strictly better than e, so any equilibrium strategy for player 2 will involve choosing f at that information set. However, in the information sets following histories L and C, player 2 is indiﬀerent between her two
actions, so she can pick either one from each pair. This yields four strategies for player 2:
(acf ), (adf ), (bcf ), and (bdf ). Player 1’s best response to any strategy for player 2 that prescribes a as the ﬁrst action is to player L. Therefore, L, acf and L, adf are subgame perfect equilibria. Also, if player 2 is choosing b and d at the ﬁrst two of her information sets, then player 1’s best response is to player C. Therefore, C, bdf is another SPE. If player 2’s strategy is (bcf ), then player 1 is indiﬀerent between L, C, and R. Therefore, L, bcf, C, bcf, and R, bcf are SPE. The game thus has six SPE in pure strategies. It has more in mixed strategies.
4.1 Burning a Bridge The Red Army, having retreated to Stalingrad is facing the advancing Wehrmacht troops. If the Red Army stays, then it must decide whether to defend Stalingrad in the case of an attack or retreat across Volga using the single available bridge for the purpose. Each army prefers to occupy Stalingrad but ﬁghting is the worst outcome for both. However, before the enemy can attack, the Red Army can choose to blow up the bridge (at no cost to it), cutting oﬀ its own retreat. Model this as an extensive form game and ﬁnd all SPE.
−1, −1 0, 1 Since this is a ﬁnite game of complete and perfect information, let’s solve it by backward induction. Starting with the longest terminal history, (B, A), Red Army’s optimal action is to retreat across the bridge, or F. Given this action, the Wehrmacht strategy following history (B) would be to attack, or A. Its strategy after history (B) is not to attack, or A. Thus, the Germans’ optimal strategy is (A, A). Given this strategy, the Red Army strictly prefers to burn the bridge. So, the unique SPE is (B, F ), (A, A). The outcome is that the Red Army burns the bridge and the Germans don’t attack.
This is an easy example that demonstrates a rather profound result of strategic interaction:
if you limit your choices and do so in a way that is observable by the opponent, then you may obtain better outcomes. This is because unless the Red Army burns the bridge, it cannot credibly commit to ﬁghting in order to induce the Germans not to attack. (Their threat to ﬁght if attacked is not credible, and so deterrence fails.) However, by burning the bridge, they leave themselves no choice but ﬁght if attack, even though they don’t like it. This makes the threat to ﬁght credible, and so the Germans are deterred.
You will see credible commitment problems in a wide variety of contexts in political science. Generally, a commitment is not credible if it will not be in the interest of the committing party to carry out its promises should it have to do so. (In our language, its threats/promises are not subgame perfect.) Limiting one’s choices in an observable way may help in such situations.8
4.2 The Dollar Auction
Let’s now play the following game. I have $1 that I want to auction oﬀ using the following procedure. Each student can bid at any time, in 10 cent increments. When no one wants to bid further, the auction ends and the dollar goes to the highest bidder. Both the highest bidder and the second highest bidder pay their bids to me. Each of you has $3.00 to bid with and you cannot bid more than that.
[ What happened? ] This is probably obvious by now but sometimes people get it completely wrong. Take the Trojans who tried to burn the Greeks’ ships! Had they succeeded in doing so, this would have only made the Greeks ﬁght so much harder. (They failed and so the Greeks sailed in apparent defeat, enabling them to carry out the wooden horse ruse.) William the Conqueror and Cortez got it right when the formed burned and the latter scuttled their own ships, forcing the soldiers to ﬁght to the end and compelling some of the opposition to surrender.
Let’s analyze this situation by applying backward induction. We shall assume that it is not worth spending a dollar in order to win a dollar. Suppose there are only two players, 1 and