Subgame-Perfect Nash Equilibrium

Chapter 11 Subgame-Perfect Nash Equilibrium Backward induction is a powerful solution concept with some intuitive appeal. Unfortunately, it can be applied only to perfect information games with a finite horizon. Its intuition, however, can be extended beyond these games through subgame perfection. This chapter defines the concept of subgame-perfect equilibrium and illustrates how one can check whether a strategy profile is a subgame perfect equilibrium. 11.1 Definition and Examples An extensive-form game can contain a part that could be considered a smaller game in itself; such a smaller game that is embedded in a larger game is called a subgame. A main property of backward induction is that, when restricted to a subgame of the game, the equilibrium computed using backward induction remains an equilibrium (computed again via backward induction) of the subgame. Subgame perfection generalizes this notion to general dynamic games: Definition 11.1 A Nash equilibrium is said to be subgame perfect if an only if it is a Nash equilibrium in every subgame of the game. A subgame must be a well-defined game when it is considered separately. That is, • it must contain an initial node, and • all the moves and information sets from that node on must remain in the subgame. 173 174 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM 1 • 2 •  1 •      (1,1) (0,4) (3,3) (2,5) Figure 11.1: A Centipede Game Consider, for instance, the centipede game in Figure 11.1, where the equilibrium is drawn in thick lines. This game has three subgames. One of them is: 1 •  (2,5)  (3,3) Here is another subgame: 2 • 1 •    (0,4) (3,3)  (2,5) The third subgame is the game itself. Note that, in each subgame, the equilibrium computed via backward induction remains to be an equilibrium of the subgame. Any subgame other than the entire game itself is called proper. 11.1. DEFINITION AND EXAMPLES 175 Now consider the matching penny game with perfect information in Figure 3.4. This game has three subgames: one after Player 1 chooses Head, one after Player 1 chooses Tail, and the game itself. Again, the equilibrium computed through backward induction is a Nash equilibrium at each subgame. 1 E X 1 (2,6) T B 2 L R (0,1) (3,2) L (-1,3) R (1,5) Figure 11.2: An imperfect-information game Now consider the game in Figure 11.2. One cannot apply backward induction in this game because it is not a perfect information game. One can compute the subgameperfect equilibrium, however. This game has two subgames: one starts after Player 1 plays ; the second one is the game itself. The subgame perfect equilibria are computed as follows. First compute a Nash equilibrium of the subgame, then fixing the equilibrium actions as they are (in this subgame), and taking the equilibrium payoffs in this subgame as the payoffs for entering the subgame, compute a Nash equilibrium in the remaining game. The subgame has only one Nash equilibrium, as  dominates , and  dominates . In the unique Nash equilibrium, Player 1 plays  and Player 2 plays , yielding the 176 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM 1 T B 2 L R (0,1) (3,2) L R (-1,3) (1,5) Figure 11.3: Equilibrium in the subgame. The strategies are in thicker arrows. payoff vector (3,2), as illustrated in Figure 11.3. Given this, the game reduces to 1 E X (3,2) (2,6) Player 1 chooses  in this reduced game. Therefore, the subgame-perfect equilibrium is as in Figure 11.4. First, Player 1 chooses  and then they play ( ) simultaneously. 1 E X 1 (2,6) T B 2 L R (0,1) (3,2) L (-1,3) R (1,5) Figure 11.4: Subgame-perfect Nash equilibrium The above example illustrates a technique to compute the subgame-perfect equilibria in finite games: 11.1. DEFINITION AND EXAMPLES 177 1 E X 1 (2,6) T B 2 L R (0,1) (3,2) L (-1,3) R (1,5) Figure 11.5: A non-subgame-perfect Nash equilibrium • Pick a subgame that does not contain any other subgame. • Compute a Nash equilibrium of this game. • Assign the payoff vector associated with this equilibrium to the starting node, and eliminate the subgame. • Iterate this procedure until a move is assigned at every contingency, when there remains no subgame to eliminate. As in backward induction, when there are multiple equilibria in the picked subgame, one can choose any of the Nash equilibrium, including one in a mixed strategy. Every choice of equilibrium leads to a different subgame-perfect Nash equilibrium in the original game. By varying the Nash equilibrium for the subgames at hand, one can compute all subgame perfect Nash equilibria. A subgame-perfect Nash equilibrium is a Nash equilibrium because the entire game is also a subgame. The converse is not true. There can be a Nash Equilibrium that is not subgame-perfect. For example, the above game has the following equilibrium: Player 1 plays  in the beginning, and they would have played ( ) in the proper subgame, as illustrated in Figure 11.5. You should be able to check that this is a Nash equilibrium. But it is not subgame perfect: Player 2 plays a strictly dominated strategy in the proper subgame. 178 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM X 1 (2,6) T B 2 L R (0,1) (3,2) L (-1,3) R (1,5) Figure 11.6: A subgame-perfect Nash equilibrium Sometimes subgame-perfect equilibrium can be highly sensitive to the way we model the situation. For example, consider the game in Figure 11.6. This is essentially the same game as above. The only difference is that Player 1 makes his choices here at once. One would have thought that such a modeling choice should not make a difference in the solution of the game. It does make a huge difference for subgame-perfect Nash equilibrium nonetheless. In the new game, the only subgame of this game is itself, hence any Nash equilibrium is subgame perfect. In particular, the non-subgame-perfect Nash equilibrium of the game above is subgame perfect. In the new game, it is formally written as the strategy profile ( ) and takes the form that is indicated by the thicker arrows in Figure 11.6. Clearly, one could have used the idea of sequential rationality to solve this game. That is, by sequential rationality of Player 2 at her information set, she must choose . Knowing this, Player 1 must choose  . Therefore, subgameperfect equilibrium does not fully formalize the idea of sequential rationality. It does yield reasonable solutions in many games, and it is widely used in game theory. It will also be used in this course frequently. We will later consider some other more refined solution concepts that seem more reasonable. 11.2 Single-deviation Principle It may be difficult to check whether a strategy profile is a subgame-perfect equilibrium in infinite-horizon games, where some paths in the game can go forever without ending 11.2. SINGLE-DEVIATION PRINCIPLE 179 the game. There is however a simple technique that can be used to check whether a strategy profile is subgame-perfect in most games. The technique is called singledeviation principle. I will first describe the class of games for which it applies. In a game there may be histories where all the previous actions are known but the players may move simultaneously. Such histories are called stages. For example, suppose that every day players play the battle of the sexes, knowing what each player has played in each previous day. In that case, at each day, after any history of play in the previous days, we have a stage at which players move simultaneously, and a new subgame starts. Likewise, in Figure 11.2, there are two stages. The first stage is where Player 1 chooses between  and , and the second stage is when they simultaneously play the 2x2 game. It is not a coincidence that there are two subgames because each stage is the beginning of a subgame. For another example, consider alternating-offer bargaining. At each round, at the beginning of the round, the proposer knows all the previous offers, which have all been rejected, and makes an offer. Hence, at the beginning we have a stage, where only the proposer moves. Then, after the offer is made, the responder knows all the previous offers, which have all been rejected, and the current offer that has just been made. This is another stage, where only the responder moves. Therefore, in this game, each round has two stages. Such games are called multi-stage games. In a multistage game, if two strategies prescribe the same behavior at all stages, then they are identical strategies and yield the same payoff vector. Suppose that two strategies are different, but they prescribe the same behavior for very, very long successive stages, e.g., in bargaining they differ only after a billion rounds. Then, we would expect that the two strategies yield very similar payoffs. If this is indeed the case, then we call such games "continuous at infinity". (In this course, we will only consider games that are continuous at infinity. For an example of a game that is not continuous at infinity see Example 9.1.) The single-deviation principle applies to multistage games that are continuous at infinity. Single-deviation test Consider a strategy profile ∗ . Pick any stage (after any history of moves). Assume that we are at that stage. Pick also a player  who moves at that stage. Fix all the other players’ moves as prescribed by the strategy profile ∗ at 180 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM the current stage as well as in the following game. Fix also the moves of player  at all the future dates, but let his moves at the current stage vary. Can we find a move at the current stage that gives a higher payoff than ∗ , given all the moves that we have fixed? If the answer is Yes, then ∗ fails the single-deviation test at that stage for player . Clearly, if ∗ fails the single-deviation test at any stage for any player , then ∗ cannot be a subgame-perfect equilibrium. This is because ∗ does not lead to a Nash equilibrium at the subgame that starts at that stage, as player  has an incentive to deviate to the strategy according to which  plays the better move at the current stage but follows ∗ in the remainder of the subgame. It turns out that in a multistage game that is continuous at infinity, the converse is also true. If ∗ passes the single deviation principle at every stage (after every history of previous moves) for every player, then it is a subgame-perfect equilibrium. Theorem 11.1 (Single-deviation Principle) In a multistage game that is continuous at infinity, a strategy profile is a subgame-perfect Nash equilibrium if and only if it passes the single-deviation test at every stage for every player. This is a generalization of the fact that backward induction results in a Nash equilibrium, as established in Proposition 9.1. For an illustration of the proof, see the proof of Proposition 9.1. The proof in general case considered in the theorem here is similar. Example 9.1 illustrates that the single-deviation principle need not apply when the game is not continuous at infinity. Since all the games considered in this game are continuous at infinity, you do not need to worry about that possibility. 11.3 Application: Infinite-Horizon Bargaining This section illustrates how to apply single-deviation principle on the infinite-horizon bargaining game with alternating offers. The game is the same as the one analyzed in Section 10.3, except that there is no end date. That is, if an offer is rejected, then we always proceed to the next date at which the other player makes an offer. Note that the game is continuous at infinity, for if two strategies describe the same behavior at the first  periods, the payoff difference under the two strategies cannot exceed  , which goes to zero, as  goes to ∞. 11.3. APPLICATION: INFINITE-HORIZON BARGAINING 181 Recall that, when the game automatically ends after 2 periods, at any , the proposer offers to take 1 − (−)2−+1 1+ for himself and leave the remaining,  + (−)2−+1  1+ to the other player, and the other player accepts an offer if his share is at least as in this offer. When  → ∞, the behavior is as follows: ∗ : at each history where  makes an offer, offer to take 1 (1 + ) and leave  (1 + ) to the other player, and at each history where  responds to an offer, accept the offer if and only if the offer gives  at least  (1 + ). We will now use the single-deviation principle to check that ∗ is a subgame-perfect equilibrium. There are two kinds of stages: (i) a player  makes an offer, (ii) a player  responds to an offer. First consider a stage as in (ii) for some  [for an arbitrary history of previous offers], where the current offer gives  ≥  (1 + ) to player . Fix the strategy of player  from this stage on as in ∗ , i.e., from  + 1 and on player  accepts an offer iff his share is at least as  (1 − ), and he offers  (1 + ) to the other player whenever he is to make an offer. Similarly, fix the strategy of player  from date  + 1 as in ∗ , so that at  + 1 and thereafter  offers  (1 + ) to  and accepts an offer if and only if  gets at least  (1 + ). According to the fixed behavior, at  + 1,  offers to take 1 (1 + ) for himself, leaving  (1 + ) to , and the offer is accepted; the payoff of  associated with this outcome is  +1 · 1 (1 − ) =  +1  (1 − )  Now according to ∗ , at the current stage,  is to accept the offer. This gives  the payoff of    ≥  +1  (1 + )  If  deviates and rejects the offer, then according to the fixed behavior he gets only  +1  (1 + ), and he has no incentive to deviate. Hence, ∗ passes the single deviation test at this stage for player . 182 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM Now, consider a stage as in (ii) for some  [for arbitrary history of previous offers], where the current offer gives    (1 + ) to player . Fix the behavior of the players at  + 1 and onwards as in ∗ , so that, independent of what happened so far, at  + 1, player  offers to take 1 (1 + ), which is accepted by , yielding payoff of  +1  (1 − ) to . According to ∗ , player  is to reject the current offer and hence get this payoff. If he deviates and accepts the offer, he will get      +1  (1 + )  Therefore, he has no incentive to deviate at this stage, and ∗ passes the single-deviation test at this stage. Now consider a stage as in (i) for some  [for arbitrary history of previous offers]. Fix again the moves of  at  and onwards as in ∗ . Fix also the moves of  at  and onwards as in ∗ . Given the fixed moves, if  offers  some  ≥  (1 + ), then the offer will be accepted, and  will obtain the payoff of (1 −  )   . If he offers    (1 + ), then the offer will be rejected, and at  + 1 they will agree to a division in which  gets  (1 + ). In that case, the payoff of  will be  +2  (1 + )  The payoff of  as a function of  is as in Figure 11.7. According to ∗ , at this stage,  offers  (1 + ) to the other player and clearly, any other offer gives a lower payoff to , and he has no incentive to deviate at this stage. Therefore, ∗ passes the single deviation test at this stage. We have covered all possible stages, and ∗ has passed the single deviation principle at every stage. Therefore, ∗ is a subgame-perfect equilibrium. In this game at each stage only one player moves. In the following lectures we will study the repeated games where multiple players may move at a given stage. The single-deviation principle will be very useful in those games as well. 11.4. EXERCISES WITH SOLUTIONS 183 Figure 11.7: The payoff of the proposer as a function of the offered share to the other party 11.4 Exercises with Solutions 1. [Midterm 2, 2001]Compute all subgame-perfect Nash equilibria of the following game: 2 X E 1 5/2 5/2 L R 2 l 3 3 r l 0 2 2 0 r 2 2 Solution: The only proper subgame starts after . This subgame can be written as    3 3 0 2  2 0 2 2 in normal form. It has three Nash equilibria: ( ), ( ), and the mixed strategy Nash equilibrium  with 1 () = 2 () = 23. Since 3  52, ( ) entices Player 184 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM 1 L R M 2 l 2 r a b a x y 0 0 1 1 3 3 1 2 2 1 b 1 x y 2 1 1 2 0 0 Figure 11.8: 1 L R M 2 3/2 3/2 a 0 0 b a 1 1 3 3 b 0 0 Figure 11.9: 2 to play . This results in SPE ( ). Similarly, the second SPE is ( ). If one picks  in the subgame, the expected payoff vector for the subgame is (2 2), and Player 2 plays . In the third SPE, Player 2 plays , and  would have been played in the subgame otherwise. 2. [Homework 2, 2002] Compute two subgame-perfect equilibria in Figure 11.8. Solution: The only proper subgame starts after Player 1 plays . The subgame is a matching penny game. It has a unique Nash equilibrium, in which the each player puts equal weights on his moves. The expected payoff vector in equilibrium is (32 32). After fixing the payoffs of the subgame this way, the game reduces 11.4. EXERCISES WITH SOLUTIONS 185 to the game in Figure 11.9, which can be written as    32 32 32 32  0 0 1 1  3 3 0 0 in normal form. This game does not have a proper subgame. The pure strategy Nash equilibria are ( ) and ( ). These result in subgame-perfect Nash equilib¡ ¢ ¡ ¢ ria 12  + 12  12  + 12  and 12  + 12  12  + 12  in mixed strategies. The reduced game has yet another Nash equilibrium, in which Player 1 puts equal probabilities on  and  and Player 2 puts equal probabilities on  and . This leads to a third subgame-perfect Nash equilibrium. 3. [Final 2002] Ashok and Beatrice would like to go on a date. They have two options: a quick dinner at Wendy’s, or dancing at Pravda. Ashok first chooses where to go, and knowing where Ashok went Beatrice also decide where to go. Ashok prefers Wendy’s, and Beatrice prefers Pravda. A player gets 3 out his/her preferred date, 1 out of his/her unpreferred date, and 0 if they end up at different places. All these are common knowledge. (a) Find a subgame-perfect Nash equilibrium. Find also a non-subgame-perfect Nash equilibrium with a different outcome. ANSWER: SPE : Beatrice goes wherever Ashok goes, and Ashok goes to Wendy’s. The outcome is both go to Wendy’s. Non-subgame-perfect Nash Equilibrium: Beatrice goes to Pravda at any history, so Ashok goes to Pravda. The outcome is each goes to Pravda. This is not subgame-perfect because it is not a Nash equilibrium in the subgame after Ashok goes to Wendy’s. (b) Modify the game a little bit: Beatrice does not automatically know where Ashok went, but she can learn without any cost. (That is, now, without knowing where Ashok went, Beatrice first chooses between Learn and NotLearn; if she chooses Learn, then she knows where Ashok went and then decides where to go; otherwise she chooses where to go without learning where Ashok went. The payoffs depend only on where each player goes –as 186 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM Ashok Wendy’s Pravda Beatrice Learn Beatrice Don’t Beatrice Wendy’s 3,1 Don’t Learn Beatrice Pravda 0,0 Wendy’s 3,1 Beatrice Wendy’s Pravda 0,0 0,0 Wendy’s Pravda 1,3 0,0 Pravda 1,3 Figure 11.10: before.) Find a subgame-perfect equilibrium of this new game in which the outcome is the same as the outcome of the non-subgame-perfect equilibrium in part (a). (That is, for each player, he/she goes to the same place in these two equilibria.) ANSWER: The extensive form game is as in Figure 11.10. Consider the strategy profile plotted in thicker arrows: Ashok plays Pravda, and Alice plays Don’t and goes to Pravda; if she played Learn, then she would have played Wendy’s if Ashok played Wendy’s and Pravda if Ashok played Pravda. As in the non-subgame-perfect equilibrium, they both go to Pravda at the end. This is a subgame-perfect equilibrium in the new game however. The only proper subgames are the two decision nodes where Beatrice moves after learning where Ashok went, and she plays best response at these nodes, yielding a Nash equilibrium in these little subgames. As in the original game, the strategy profile is a Nash equilibrium of the whole game. Therefore, it is a subgameperfect Nash equilibrium. 4. [Midterm 2, 2007] The players in the following game are Alice, who is an MIT senior looking for a job, and Google. She has also received a wage offer  from Yahoo, but we do not consider Yahoo as a player. Alice and Google are negotiating. They use alternating offer bargaining, Alice offering at even dates  = 0 2 4    and Google offering at odd dates  = 1 3   . When Alice makes an offer , Google either 11.4. EXERCISES WITH SOLUTIONS 187 accepts the offer, by hiring Alice at wage  and ending the bargaining, or rejects the offer and the negotiation continues. When Google makes an offer , Alice • either accepts the offer  and starts working for Google for wage , ending the game, • or rejects the offer  and takes Yahoo’s offer , working for Yahoo for wage  and ending the game, • or rejects the offer  and then the negotiation continues. If the game continues to date ̄ ≤ ∞, then the game ends with zero payoffs for both players. If Alice takes Yahoo’s offer at   ̄, then the payoff of Alice is   and the payoff of Google is 0, where  ∈ (0 1). If Alice starts working for Google at   ̄ for wage , then Alice’s payoff is   and Google’s payoff is ( − )   , where 2     (Note that she cannot work for both Yahoo and Google.) (a) Compute the subgame perfect equilibrium for ̄ = 4. (There are four rounds of bargaining.) ANSWER: • Consider  = 3. Alice will get  if she accepts Google,  if she accepts Yahoo, and 0 if she rejects and continues. Thus, she must choose (  if  ≥  3 =   otherwise. Given this, Google gets 0 if    and  −  if  ≥ . Therefore, it must choose 3 =  • Consider  = 2. Google will get  −  if it accepts an offer  by Alice and  − 3 next day if it rejects the offer. Hence Google must Accept iff ( − ) ≥  ( − 3 ) i.e.  ≤  (1 − ) +  188 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM The best reply for Alice is to offer 2 =  (1 − ) +  • [This is the most important step.] Consider  = 1. Consider Alice’s decision. Alice will get  if she accepts Google,  if she accepts Yahoo, and 2 if she rejects and continues. One must check whether she prefers Yahoo’s offer to continuing. Note that   2 =  (1 − ) +  2  ⇐⇒   Since   2   , 1+  (1 − )  =  2 1+ 1− this implies that   2 . That is, Alice prefers Yahoo’s offer to continuing, and hence she will never reject and continue. Therefore, she must choose 1 = 3 = (  if  ≥    otherwise. Google then must offer 1 = . • Consider  = 0. It must be obvious now that it is the same as  = 2. Google Accepts iff  ≤ 2 and Alice offers 0 = 2 =  (1 − ) +  (b) Take ̄ = ∞. Conjecture a subgame-perfect equilibrium and check that the conjectured strategy profile is indeed a subgame-perfect equilibrium. ANSWER: From part (a), it is easy to conjecture that the following is a SPE: ∗ : At an odd date Alice accepts an offer  iff  ≥ , otherwise she takes Yahoo’s offer. Google offers  = . At an even date Alice offers  =  (1 − ) + , and Google accepts an offer  iff  ≤  . Use single-deviation principle to check that ∗ is indeed a SPE. There are 4 major cases two check: • Consider the case Alice is offered . 11.4. EXERCISES WITH SOLUTIONS 189 — Suppose that  ≥  ≡ . Alice is supposed to accept and receive  today. If she deviates by rejecting  and taking Yahoo’s offer, she will get , which is not better that . If she deviates by rejecting and continuing, she will offer  at the next day, which will be accepted. The present value of this is  =  (1 − ) +  2    ≤ , i.e. this deviation yields even a lower payoff. — Suppose that    ≡ . Alice is supposed to reject it and take Yahoo’s offer with payoff . If she deviates accepting , she will get the lower payoff of   . If she deviates by rejecting and continuing, she will get  next day, with a lower present value of  =  (1 − ) +  2   . • Consider a case Google offers . If  ≥ , it will be accepted, yielding a payoff of  −  to Google. If   , then Alice will go to Yahoo, with payoff of 0 to Google. Therefore, the best response is to offer  =   0, as in ∗ . There is no profitable (single) deviation. • Consider the case Google is offered . — Suppose that  ≤  . If Google deviates and rejects, it will pay  tomorrow with payoff  ( − ) = ( −  ), which is not better than  −  . — Suppose that    . If Google deviates and accepts, then it will get only  − , while it would get the present value of  ( − ) = ( −  ) by rejecting the offer. • Consider a node in which Alice offers. Google will accept iff  ≤  . If she offers    she gets  next day, with present value of    . Therefore, the best reply is to offer  =  , and there is no profitable deviation. [In part (b) most important cases are the acceptance/rejection cases, especially that of Alice. Many students skipped those cases, and wrongly concluded that a non-SPE profile is a SPE.] 5. Random Proposer Model: Consider -player version of the game in Section 11.3. They have again one dollar to share and each is risk neutral with discount 190 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM factor  as before. The only difference is that the proposer is selected randomly. At any , each player  is selected as the proposer with probability  , and the other players sequentially accept or reject in the increasing order. The game ends if all the responders accept. Compute the subgame-perfect Nash equilibria that are stationary, in that there exist divisions 1       such that each player  offers  = (1       ) whenever he is the proposer (and the offer is accepted). Solution: Write  for the expected share of player  before the proposer is selected:  = 1 1 + · · · +    At , if a player  offers  = (1       ) and the offer is rejected, the payoff of  is  +1  . His payoff is   if the offer is accepted. Hence, he accepts an offer  iff  ≥  . Hence the proposer  = 6  offers  such that  =  . He keeps P  = 1 −   6=  to himself. Substituting these values in  = 1 1 + · · · +   , one obtains  =   + (1 −  )  Ã ! X =  1 −   + (1 −  )  Ã = 6 =  1 −   X  =1 ! +  =  (1 − ) +   Here, the first equality is because all other players offer the same share to ; the second equality is by substitution of the values; the third equality is by simple algebra, and the last equality is by the fact that all the offers add up to 1. Solving for  , one obtains  =   SPE: Each player  offers  to every  6= , keeping himself 1 −  (1 −  ), and accepts an offer  = (1       ) iff  ≥  . 6. [Final 2007] Three senators, namely Alice, Bob, and Colin, are in a committee that determines the tax rate  ∈ [0 1]. Alice is a libertarian: her utility from setting the tax rate  at date  is   (1 −  2 ). Bob is a moderate: his utility 11.4. EXERCISES WITH SOLUTIONS 191 ¡ ¢ is   1 − ( − ̄ )2 where ̄ ∈ (0 1) is a known constant. Colin is a liberal: his ¡ ¢ utility is   1 − (1 −  )2 . At each date randomly one of them becomes a proposer, each having chance of 1/3. The proposer offers a tax rate  and the other two vote Yes or No in alphabetical order. If at least one of them votes Yes, then the game ends and  is set as the tax rate. If both says No, we continue to the next date. (a) Find a subgame perfect equilibrium of this game. (Hint: There exists a SPE with values   ≤ ̄ ≤   such that Alice always offers   , Bob always offers ̄ , and Colin always offers   .) Answer: Construct an equilibrium as in the hint. Note that when Alice makes an offer, she will need the vote of Bob because whenever Bob rejects Alice’s offer, so will the more liberal Colin. Also, she does not need Colin to vote yes. Hence, she will offer the lowest tax rate accepted by Bob. That offer will make Bob indifferent between Yes and No. Similarly, Colin will make Bob indifferent between Yes and No. Let’s write  for the expected value of Bob at the beginning of a date before we know who the proposer is. If Bob says No, he will get  . Therefore, by indifference, his payoffs from the offers of Alice and Carol are also  . Moreover, when he makes an offer, he offers ̄ , and it is accepted by one of the other two senators, yielding payoff of 1. Therefore, his payoff at the beginning of the period is 2 1  =  + · 1 3 3 and hence, 1   = 3 − 2 But he is indifferent between   ,   , and the payoff  :   1 − (  − ̄ )2 = 1 − (  − ̄ )2 = 3 − 2 i.e., 3 (1 − )  (  − ̄ )2 = (  − ̄ )2 = 3 − 2 Therefore, r 3 (1 − )   = ̄ − 3 − 2 r 3 (1 − )    = ̄ + 3 − 2 192 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM In order to complete the description of the strategy profile, one also needs to find which offers are accepted by each senator. Clearly, Bob accepts an offer if and only if  ∈ [     ]. The expected payoff of Alice at the beginning of a period is ¢ 1¡ 2   + ̄ 2 +  2  3 and she must accept an offer iff  ≤ ̂  , where 1 − ̂ 2 =  , i.e., r  ̂  = 1 −  + ( 2 + ̄ 2 +  2 ) 3  = 1 − Similarly, Colin accepts an offer  iff  ≥ ̂  , where r ¢ ¡ (1 −   )2 + (1 − ̄ )2 + (1 −   )2 ̂  = 1 − 1 −  + 3 (which is obtained by replacing  with 1 −  ). This completes the answer. [It can be checked that ̂  + (1 − ̂  )  1, so that at least one of Alice and Colin accepts ̄ . This and the usual single deviation arguments would be enough for verifying that the above strategy profile is indeed a SPE. Also, the above solution assumes that   ≥ 0 and   ≤ 1. If it turns out that they are out of bounds, one takes them 0 and 1 and computes  accordingly.] (b) What happens as  → 1? Briefly interpret. Answer: As  → 1,   → ̄ ;   → ̄ ; ̂  → ̄ ; ̂  → ̄  That is, in the limit all players offer ̄ and they accept an offer if and only if the offer is at least as good as ̄ . That is, the moderate senator’s preferences dictate the outcome. (This is a version of the "median voter theorem" in political science. The "theorem" states that the preferences of the voter who is in the middle prevail. This emerges formally in models as in the example here.) 11.5 Exercises 1. [Homework 3, 2004] Compute the subgame-perfect Nash equilibria in Figure 11.11. 11.5. EXERCISES 193 1 2 2 2 1 2 2 2 3 3 0 0 0 0 1 1 Figure 11.11: 1 B M 2 2 R L l r 1 1 x 4 1 y 0 0 a x 0 0 y 1 4 2 1 Figure 11.12: b 1 2 a 1 2 b 2 1 194 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM 1 U D 2 L L R R 1 1 A 3/2 0 B 2 3/2 0 a b 2 2 l r x y    2 1 0 0 0 0 1 2 2 1 0 0 0 0  1 2 Figure 11.13: 2. [Homework 3, 2006] Compute the subgame-perfect Nash equilibria in Figure 11.12. 3. [Midterm 1, 2006] Compute all the subgame-perfect equilibria in pure strategies in Figure 11.13. 4. [Midterm 2 Make Up, 2011] Find all the subgame-perfect Nash equilibria of the following game. 1 a b 2 2 L 1 R A 5 5 2 0 B R 1 0 2 A’ r 0 6 B’ 2 2 2 2 l L l r L’ R’ L’ R’ 6 0 1 1 5 1 0 0 0 0 1 5 5. Homework 3, 2004] Find all subgame-perfect equilibria in the following game. Consider an employer and a worker. The employer provides the capital  (in 11.5. EXERCISES 195 terms of investment in technology, etc.) and the worker provides the labor  (in √ terms of the investment in the human capital) to produce  ( ) = , which they share equally. The parties determine their investment level (the employer’s capital  and the worker’s labor ) simultaneously. The worker cannot invest ¯ where  ¯ is a very large number. Both capital and labor are costly, more than , so that the payoffs for the employer and the worker are 1  ( ) −  2 and 1  ( ) − 2  2 respectively. So far the problem is same as in Exercise 1 in Section 8.5. The present problem differs as follows. Before the worker joins the firm (in which they simultaneously choose  and  ), the worker is to choose between working for this employer or working for another employer q who pays the worker a constant ̃ ˜ = wage  ˜  0 makes him work as much as  . (If he works for the other 2 employer, the current employer gets 0.) Everything described up to here is common knowledge. 6. [Homework 3, 2006] Alice and Bob are competing to play a game against Casey. Alice and Bob simultaneously bid  and  , respectively. The one who bids higher wins; if  =  , the winner is determined by a coin toss. The winner pays his/her bid to Casey and play the following game with Casey: Winner\Casey L R T 3,1 0,0 B 0,0 1,3 Find two pure strategy subgame-perfect equilibria of this game. Which of the equilibria makes more sense to you? 7. [Midterm 1 Make Up, 2002] Consider the following game of coalition formation in a parliamentary system. There are three parties , , and  who just won 41, 35, and 25 seats, respectively, in a 101-seats parliament. In order to form a government, a coalition (a subset of {  }) needs 51 seats in total. The 196 CHAPTER 11. SUBGAME-PERFECT NASH EQUILIBRIUM parties in the government enjoy a total 1 unit of perks, which they can share in any way they want. The parties outside the government get 0 units of perks, and each party tries to maximize the expected value of its own perks. The process of coalition formation is as follows. First  is given right to form a government. If it fails, then  is given right to form a government, and if  also fails then  is given to form a government. If  also fails, then the game ends and each gets 0. The party who is given right to form a government, say , approaches one of the other two parties, say , and offers some  ∈ [0 1]. If  accepts, then they form the government and  gets 1 −  and  gets  units of perks. If  rejects the offer, then  fails to form a government (in which case, as described above, either another party is given right to form a government or game will and with 0 payoff). Applying backward induction, find a Nash equilibrium of this game. 8. [A variation of Final Make Up, 2002] Consider the following game between two firms. Firm 1 either stays out, in which case Firm 1 gets 2 and Firm 2 gets 3, or enters the market where Firm 2 operates. If it enters, then the firms simultaneously choose between two strategies: Hawk (an aggressive strategy) and Dove (a peaceful strategy). In this subgame, if a firm plays Hawk and the other plays Dove, then Hawk gets 3 Dove gets 0; if both choose Hawk, then each gets -1, and if both play Dove, then each gets 1. (a) Compute the set of subgame-perfect Nash equilibria. (b) Which of the above equilibria is consistent with the assumption that Firm 2 remains to believe that Firm 1 is rational in the information set of Firm 2. 9. [Homework 3, 2004] Consider a two-player bargaining game with alternating offers, where the players try to divide a dollar (as in the class). Assume that the discount rate of player  is  ∈ (0 1), where 1 = 6  2 . Using the single-deviation principle, check that the following is a subgame perfect equilibrium: at any given history where  makes an offer, he offers (1 −   )  (1 −  1  2 ) to himself, leaving the rest to the other player (), and at any history where he responds to an offer, he accepts the offer if and only if his share is at least   (1 −   )  (1 −  1  2 ), where  6= . 10. Verify that the equilibrium identified in the random-proposer model of the previous 11.5. EXERCISES 197 section is indeed a subgame-perfect equilibrium. 11. Can you find a different subgame-perfect equilibrium in the random-proposer model above? 12. [Final 2006] Alice and Bob own a dollar, which they need to share in order to consume. Alice makes an offer  ∈  = {001 002     098 099}; and observing the offer, Bob accepts it or rejects it. If Bob accepts the offer, Alice gets 1 −  and Bob gets . If he reject, then each gets 0. (a) Compute all the subgame-perfect equilibria in pure strategies. (b) Now suppose that their cousin Carol sells a contract for $0.01. The contract requires that Bob is to pay 1 dollar to Carol if Bob accepts an offer  that is less than ̄, where ̄ ∈  is chosen by Bob at the time of purchase of the contract. In particular, consider the following time-line: • Bob decides whether to buy a contract from Carol and determines ̄ if he chooses to buy; • Alice observes Bob’s decision (i.e. whether he buys the contract and ̄ if he buys); • Then, they play the bargaining game above, where Bob pays Carol 1 dollar if he accepts an offer   ̄. Find all the subgame-perfect equilibria in pure strategies. (c) In part (b) assume that Alice cannot observe whether Bob buys a contract (and in particular the value of ̄ if he buys). Find all the subgame-perfect equilibria in pure strategies. (d) In part (b) assume that Alice observes whether Bob buys a contract but does not observe the value of ̄ if he buys. Find all the subgame-perfect equilibria in pure strategies.