Chapter 6: Nash Equilibrium

Chapter 6 Nash Equilibrium 6.1 Introduction and Definition Both dominant-strategy equilibrium and rationalizability are well-founded solution concepts. If players are rational and they are cautious in the sense that they assign positive probability to each of the other players’ strategies, then we would expect that the players to play according to the dominant-strategy equilibrium whenever such an equilibrium exists. On the other hand, rationalizability describes exactly what is implied by the definition of the game (aka common knowledge of rationality). If it is common knowledge that the players are rational (i.e. they maximize the expected value of their utility function), then each player must be playing a rationalizable strategy. Moreover, every rationalizable strategy can be rationalizable in the sense that a player can play that strategy and still believe that it is common knowledge that players are rational. Unfortunately, these solution concepts are not useful in most situations in economics. Except for the games that are specifically designed, as in the second-price auction, there is often no dominant-strategy equilibrium. The set of rationalizable strategies tends to be large in games analyzed in economics (and in this course). In that case, one can make only weak predictions about the outcome using rationalizability. This lecture introduces a new solution concept: Nash Equilibrium. It assumes that the players correctly guess the other players’ strategies. This assumption may be reasonable when there is a long prior interaction that leads players to form opinion about how the other players play. It may also be reasonable when there is a social convention, 83 84 CHAPTER 6. NASH EQUILIBRIUM adhered by the other players. Towards defining Nash equilibrium, consider the Battle of the Sexes game Alice\Bob opera football opera 4 1 0 0 football 0 0 1 4 (6.1) In this game, there is no dominant strategy, and everything is rationalizable. Suppose Alice plays opera. Then, the best thing Bob can do is to play opera, too. Thus opera is a best response for Bob against Alice playing opera. Similarly, opera is a best response for Alice against opera. Thus, at (opera, opera), neither party wants to take a different action. This is a Nash Equilibrium. Towards formalizing this idea for general games, recall that, for any player , a strategy  is a best response to − if and only if   (   − ) ≥  (  − ) ∀ ∈   Recall also that the definition of a best response differs from that of a dominant strategy by requiring the above inequality only for a specific strategy − instead of requiring it for all − ∈ − . If the inequality were true for all − , then  would also be a dominant strategy, which is a stronger requirement than being a best response against some strategy − . Definition 6.1 A strategy profile ∗ = (∗1  ∗ ) is a Nash Equilibrium if and only if ∗ ∗ is a best response to ∗− = (∗1  ∗−1  ∗+1   ) for each . That is, for all , ∗ ∗ ) ≥  (  − )  (∗  − ∀ ∈   In other words, no player would have an incentive to deviate, if he correctly guesses the other players’ strategies. If one views a strategy profile as a social convention, then being a Nash equilibrium is tied to being self-enforcing, that is, nobody wants to deviate when they think that the others will follow the convention. For example, in the battle of sexes game (6.1), (opera, opera) is a Nash equilibrium because  ( ) = 4  0 =  ( ) 6.2. RELATION TO EARLIER SOLUTION CONCEPTS 85 and  ( ) = 1  0 =  ( )  Likewise, (football, football) is also a Nash equilibrium. On the other hand, (opera, football) is not a Nash equilibrium because Bob would like to go to opera instead:  ( ) = 1  0 =  ( )  6.2 Relation to Earlier Solution Concepts Nash Equilibrium v. Dominant-strategy Equilibrium Every dominant strategy equilibrium is also a Nash equilibrium, but the reverse is not true. Theorem 6.1 If ∗ is a dominant strategy equilibrium, then ∗ is a Nash equilibrium. Proof. Let ∗ be a dominant strategy equilibrium. Take any player . Since ∗ is a dominant strategy for , for any given  ,  (∗  − ) ≥  (  − ) ∀− ∈ −  In particular, ∗  (∗  ∗− ) ≥  (  − ) Since  and  are arbitrary, this shows that ∗ is a Nash equilibrium. To see that the converse is not true, consider the Battle of the Sexes. In this game, both (Opera, Opera) and (Football, Football) are Nash equilibria, but neither are dominant strategy equilibria. Furthermore, there can be at most one dominant strategy equilibrium, but as the Battle of the Sexes shows, Nash equilibrium is not unique in general. There can also be a other Nash equilibria when there is a dominant strategy equilibrium. For an example, consider the game    1 1 0 0  0 0 0 0 In this game, ( ) is a dominant strategy equilibrium, but ( ) is also a Nash equilibrium. 86 CHAPTER 6. NASH EQUILIBRIUM This example also illustrates that a Nash equilibrium can be in weakly dominated strategies. In that case, one can rule out some Nash equilibria by eliminating weakly dominated strategies. While may find such equilibria unreasonable and be willing to rule out such equilibria, the next example shows that all Nash equilibria may need to be in dominated strategies in some games. (One then ends up ruling out all Nash equilibria.) Example 6.1 Consider a two-player game in which each player  selects a natural number  ∈ N = {0 1 2   }, and the payoff of each player is 1 2 . It is easy to check that (0 0) is a Nash equilibrium, and there is no other Nash equilibrium. Nevertheless, all strategies, including 0, are weakly dominated. Nash Equilibrium v. Rationalizability If a strategy is played in a Nash equilibrium, then it is rationalizable, but there may be rationalizable strategies that are not played in any Nash equilibrium. Theorem 6.2 If ∗ is a Nash equilibrium, then ∗ is rationalizable for every player . Proof. It suffices to show that none of the strategies ∗1  ∗2   ∗ is eliminated at any round of the iterated elimination of strictly dominated strategies. Since these strategies are all available at the beginning of the procedure, it suffices to show if the strategies ∗1  ∗2  ∗ are all available at round , then they will remain available at round  + 1. ∗ Indeed, since ∗ is a Nash equilibrium, for each , ∗ is a best response to − which are available at round . Hence, ∗ is not strictly dominated at round , and remains available at round  + 1. The converse is not true. That is, there can be a rationalizable strategy that is not played in any Nash equilibrium, as the next example illustrates. Example 6.2 Consider the following game:     1 −2 −2 1 0 0   −1 2 1 −2 0 0 0 0 0 0 0 0 (This game can be thought as a matching penny game with an outside option, which is represented by strategy .) Note that ( ) is the only Nash equilibrium. In contrast, no 6.3. MIXED-STRATEGY NASH EQUILIBRIUM 87 strategy is strictly dominated (check that each strategy is a best response to some strategy of the other player), and hence all strategies are rationalizable. 6.3 Mixed-strategy Nash equilibrium The definition above covers only the pure strategies. We can define the Nash equilibrium for mixed strategies by changing the pure strategies with the mixed strategies. Again given the mixed strategy of the others, each agent maximizes his expected payoff over his own (mixed) strategies. Definition 6.2 A mixed-strategy profile  ∗ = ( ∗1      ∗ ) is a Nash equilibrium if and only if for every player ,  ∗ is a best response to  ∗− . The condition for checking whether ∗ is mouthful.1 Fortunately, there is a simpler ∗ condition to check: for every , if ∗ ( )  0, then  is a best response to  − . That is, X −  (  − )  ∗− (− ) ≥ X − ∗  (0  − )  − (− ) ∀ with ∗ ( )  0,∀0  ∗ ∗ ∗ (−1 ) · +1 (+1 ) · · · · · +1 (+1 ). where  ∗− (− ) = 1∗ (1 ) · · · · · −1 Example –Battle of the Sexes Consider the Battle of the Sexes again. Alice\Bob opera football 1 opera 4 1 0 0 football 0 0 1 4 The condition is X  (1       )  ∗ ( ) Y 6= (1  )  ∗ ( ) ≥ X  (1       )   ( ) Y  ∗ ( ) 6= (1  ) for every mixed strategy   . It can be simplified because one does not need to check for all mixed strategies  . It suffices to check against the pure strategy deviations. That is,  ∗ is a Nash equilibrium if and only if X  (1       )  ∗ ( ) (1  ) for every pure strategy 0 . Y 6=  ∗ ( ) ≥ X −  (0  − ) Y = 6  ∗ ( ) 88 CHAPTER 6. NASH EQUILIBRIUM We have identified two pure strategy equilibria, already. In addition, there is a mixed strategy equilibrium. To compute the equilibrium, write  for the probability that Alice goes to opera; with probability 1 −  she goes to football game. Write also  for the probability that Bob goes to opera. For Alice, the expected payoff from opera is  (opera,) =  (opera,opera) + (1 − )  (opera,football) = 4 and the expected payoff from football is  (football,) =  (football,opera) + (1 − )  (football,football) = 1 −  Her expected payoff from the mixed strategy is  (; ) =  (opera,) + (1 − )  (football,) = [4] + (1 − ) [1 − ]  The payoff function  (; ) is strictly increasing with  when  (opera,)   (football ). This is the case when 4  1 −  or equivalently when   15. In that case, the unique best response for Alice is  = 1, and she goes to opera for sure. Likewise, when   15,  (opera,)   (football ), and her expected payoff  (; ) is strictly decreasing with . In that case, Alice’s best response is  = 0, i.e., going to football game for sure. Finally, when  = 15, her expected payoff  (; ) does not depend on , and any  ∈ [0 1] is a best response. In other words, Alice would choose opera if her expected utility from opera is higher, football if her expected utility from football is higher, and can choose either opera or football or any randomization between them if she is indifferent between the two. Similarly, one can compute that  = 1 is best response if   45;  = 0 is best response if   45; and any  can be best response if  = 45. The best responses are plotted in Figure 6.1. The Nash equilibria are where these best responses intersect. There is one at (0 0), when they both go to football, one at (1 1), when they both go to opera, and there is one at (45 15), when Alice goes to opera with probability 45, and Bob goes to opera with probability 15. Remark 6.1 The above example illustrates a way to compute the mixed strategy equilibrium (for 2x2 games). Choose the mixed strategy of Player 1 in order to make Player 6.3. MIXED-STRATEGY NASH EQUILIBRIUM 89 q 1/5 p 4/5 Figure 6.1: The best-responses in the Battle of Sexes 2 indifferent between her strategies, and choose the mixed strategy of Player 2 in order to make Player 1 indifferent. This is a valid technique to compute a mixed strategy equilibrium, provided that it is known which strategies are played with positive probabilities in equilibrium. (Note that one must be indifferent between two strategies if he plays both of them with positive probabilities.) Exercise 6.1 Show that if ∗ is a mixed strategy Nash equilibrium and  ∗ ( )  0, then  is rationalizable. One can use the above fact in searching for a mixed strategy Nash equilibrium. One can compute the rationalizable strategies first and search for a mixed strategy equilibrium within the set of rationalizable strategies, which may be smaller than the original set of strategies. Games with unique rationalizable strategy profile are called dominance solvable. Exercise 6.2 Show that in a dominance-solvable game, the unique rationalizable strategy is the only Nash equilibrium. 90 CHAPTER 6. NASH EQUILIBRIUM 6.4 Evolution of Hawks and Doves Consider the game     ¡  −  − ¢  2  0 2 0   2  2 (played by the genes). Assume that   , so that the payoffs are negative when two hawks meet. One can easily check that there are two Nash equilibria in pure strategies: (hawk, dove) and (dove, hawk). There is also a mixed strategy equilibrium where both strategies are played with positive probability. Let  be the probability of Player 2 playing hawk, and  = 1 −  be the probability that he plays dove. Since Player 1 plays both strategies with positive probability, he must be indifferent between them:  −  ·  +  ·  = ·  2 2 where the left hand side is the expected payoff from hawk and the right hand side is the expected payoff from dove. The solution to this equation is  =   Similarly, in order for Player 2 play both hawk and dove with positive probabilities (which are played with positive probabilities   and 1 −  , respectively), it must be that Player 1 plays hawk with probability  . Therefore, in the mixed-strategy Nash equilibrium, each player plays hawk with probability   and dove with probability 1 −  . Now imagine an island where hawks and doves live together. Let there be 0 hawks and 0 doves at the beginning where both 0 and 0 are very large. Suppose that each season, the birds are randomly matched and the number of offsprings of a bird is given by the payoff matrix above. That is, if a dove is matched to a dove as the neighbor, then it will have  2 offsprings, and the next generation, we will have 1 +  2 doves in its family. If a dove is matched with a hawk, then it will have zero offsprings and its family will have only 1 member, itself in the next season. If two hawks are matched, then each will have ( − ) 2 offsprings, which is negative reflecting the situation that the number of hawks from such matches will decrease when we go to next season. Finally, if a hawk meets dove, it will have  offsprings, and there will 1 +  hawks in its family in the 6.4. EVOLUTION OF HAWKS AND DOVES 91 next season. We want to know the ratio of hawks and doves in this island millions of seasons later. Let  and  be the number of hawks and doves, respectively, at season . Define  =   and  =  +   +  as the ratios of hawks and doves at . In accordance with the strong law of large numbers, assume that the number of hawks that are matched to hawks is   , and number of hawks that are matched to doves is   .2 Each hawk in the first group multiplies to 1 + ( − ) 2, and each hawk in the second group multiplies to 1 +  2. The number of hawks in the next season will be then +1 = (1 + ( − ) 2)   + (1 +  )   (6.2) = (1 + ( − )  2 +   )  Number of doves who are matched to hawks is   , and number of doves that are matched to doves is   . Each dove in the first and the second group multiplies to 1 and 1 +  2, respectively. Hence, the number of doves in the next season will be then +1 = (1 + 0)   + (1 +  2)   = (1 +   2)   (6.3) It is easy to find the steady states of the ratio  (and  ), defined by +1 =  and +1 =   From (6.2) and (6.3) it is clear that  = 0 and  = 1 is a stationary state, which can be reached if we start with all doves. In that case, by (6.2), it will continue as "doves only." Similarly, another steady state is  = 1 and  = 0 which can be reached if we start with all hawks. Since we have started with both hawks and doves, both  and +1 are positive. Hence, we can compute the steady states by +1  1 + ( − )  2 +    = =  +1  1 +   2  2 The probabilities of matching to a hawk and dove are  and  , respectively. And there are  hawks. 92 CHAPTER 6. NASH EQUILIBRIUM where the last equality is due to (6.2) and (6.3). The equality holds if and only if ( − )  2 +   =   2 or equivalently  =   This is the only steady state reached from a distribution with hawks and doves. Notice that it is the mixed strategy Nash equilibrium of the underlying game. This is a general fact: if a population dynamic is as described in this section, then the steady states reachable from a completely mixed distribution are symmetric Nash equilibria. We will now see that when we start with both hawks and doves present, we will necessarily approach to the last steady state, which is the mixed strategy Nash equilibrium. Now +1   whenever +1    +1  which holds whenever 1 + ( − )  2 +   1 1 +   2 as one can see from (6.2) and (6.3). The latter inequality is equivalent to     That is, if  exceeds the equilibrium value, then it decreases towards the equilibrium value. Similarly, if    , then +1   , and  will increase towards the equilibrium. 6.5 Exercises with Solutions 1. [Homework 2, 2011] Compute the set of Nash equilibria in Exercise 1 of Section 5.3. Solution: Since Nash equilibrium strategies put positive probability only on rationalizable strategies, it suffices to consider rationalizable set. But there is only one rationalizable strategy profile ( ). Therefore, ( ) is the only Nash equilibrium. 2. [Midterm 1, 2011] Compute the set of Nash equilibria in Exercise 2 of Section 5.3. Solution: Recall that the set of Nash equilibria is invariant to the elimination of non-rationalizable strategies. Hence, it suffices to compute the Nash equilibria 6.5. EXERCISES WITH SOLUTIONS 93 in the reduced game. Recall also from Section 5.3 that, after the elimination of non-rationalizable strategies, the game reduces to   ∗  0 3  ∗ 3 0 3∗  0 2 4∗ Here, the best responses (to the pure strategies) are indicated with asterisk. Since the best responses do not intersect, there is no Nash equilibrium in pure strategies. There is a unique mixed strategy Nash equilibrium ∗ . In order for Player 1 to play a mixed strategy, he must be indifferent between  and  against  ∗2 : 3∗2 () = 2 + (1 −  ∗2 ())  Here the left-hand side is the expected payoff from , and the right-hand side is the expected payoff from . The indifference condition yields  ∗2 () = 34 Of course, ∗2 () = 14. Since Player 2 is playing a mixed strategy, he must be indifferent between playing  and  against ∗1 : 3∗1 () = 4 (1 −  ∗1 ())  Here the left-hand side is the expected payoff from , and the right-hand side is the expected payoff from . The indifference condition yields  ∗1 () = 47 and ∗1 () = 37 3. [Midterm 1, 2001] Find all the Nash equilibria in the following game: 1\2     1 0 0 1 5 0  0 2 2 1 1 0 Solution: By inspection, there is no pure-strategy equilibrium in this game. There is one mixed strategy equilibrium. Since  is strictly dominated, Player 2 assigns 0 probability to . Let  and  be the equilibrium probabilities for strategies  94 CHAPTER 6. NASH EQUILIBRIUM and , respectively; the probabilities for  and  are 1 −  and 1 − , respectively. If Player 1 plays  , his expected payoff is 1 + (1 − ) 0 = . If he plays , his expected payoff is 2 (1 − ). Since he assigns positive probabilities to both  and , he must be indifferent between  and . Hence,  = 2 (1 − ), i.e.,  = 23. Similarly, for Player 2, the expected payoffs from playing  and  are 2 (1 − ) and 1, respectively. Hence, 2 (1 − ) = 1, i.e.,  = 12. 4. [Make up for Midterm 1, 2007] Consider the game in Exercise 4 of Section 3.4. (a) Assuming   12, find a Nash equilibrium. Solution: It is easier to compute a Nash equilibrium from the normal-form representation. Recall from the solution to Exercise 4 of Section 3.4 that the normal-form representation of the game is Student\Prof same new  1 0 1 0  3 12  2 −1 32 (1 − ) 2  4 −12 12 −(1 + )2 1 − When   12, strategy "same" weakly dominates "new", with equality only against . Since  is not a best response to "new", there cannot be a Nash equilibrium in which "new" is played with positive probability. (Why?) Hence, in any Nash equilibrium Prof plays "same". The best response is . This yields ( same) as the unique Nash equilibrium. (b) Assuming  ∈ (0 12), find a Nash equilibrium. In order to find all Nash equilibria for   12, it is useful to find the rationalizable strategies: Student\Prof same ∗  3 12  4∗  −12 new ∗ 32  (1 − ) 2 1 −∗ where the best responses are indicated by asterisk. Clearly, there is no pure strategy Nash equilibrium. The only Nash equilibrium  ∗ is in mixed strategies. Towards computing  ∗ , the indifference condition for Student yields 32 + (32) ∗2 (same) = 1 + 3 ∗2 (same)  6.6. EXERCISES 95 where the payoffs from the strategies "same" and "new" are on the left and right hand sides of the equation, respectively. Therefore,  ∗2 (same) = 13 and ∗2 (new) = 23 The indifference condition for Prof yields ∗1 () − 12 = (1 + ) 2∗1 () −  yielding ∗1 () = 1 − 2  and ∗1 () =  1− 1− Note that, in equilibrium, Student takes the regular exam when he is healthy and mixes between regular exam and make up when he is sick. 6.6 Exercises 1. [Homework 2, 2007] Consider the following game: L M N R A (4 2) (0 0) (5 0) (0 0) B (1 4) (1 4) (0 5) (−1 0) C (0 0) (2 4) (1 2) (0 0) D (0 0) (0 0) (0 −1) (0 0) (a) Compute the set of rationalizable strategies. (b) Find all Nash equilibria (including those in mixed strategies). 2. [Midterm 1, 2007] Consider the game in Exercise 3 in Section 3.5 and Exercise 3 in Section 5.4. (a) Find all pure strategy Nash Equilibria. (b) Compute a mixed strategy Nash equilibrium. 96 CHAPTER 6. NASH EQUILIBRIUM 3. [Midterm 1, 2005] Find all the Nash equilibria in the following game. (Don’t forget the mixed strategy equilibrium.) 1\2     1 0 4 1 1 0  2 1 3 2 0 1 3 −1 2 0 2 2  4. [Midterm 1, 2004] Consider the following game: 1\2     3 0 0 3 0   0 3 3 0 0    0  0   (a) Compute two Nash equilibria for  = 1. (b) For each equilibrium in part a, check if it remains a Nash equilibrium when  = 2. 5. [Homework 2, 2001] Compute all the Nash equilibria of the following game. L M R A (3 1) (0 0) (1 0) B (0 0) (1 3) (1 1) C (1 1) (0 1) (0 10) 6. [Homework 2, 2002] Compute all the Nash equilibria of the following game. L M R A (4 3) (0 0) (1 1) B (0 1) (1 0) (10 0) C (0 0) (3 4) (1 1) D (−1 0) (3 1) (5 0) 6.6. EXERCISES 97 7. [Homework 1, 2001] Consider the following game in normal form.    1 2 2 3 0 4 0 2 3 3 2 0 1 0 3 1 3 5 5 0 2 4 1 1 1 1 2 3 (a) Iteratively eliminate all strictly dominated strategies; state the assumptions necessary for each elimination. (b) What are the rationalizable strategies? (c) What are the pure-strategy Nash equilibria? 8. [Homework 1, 2004] Consider the game in Exercise 1 of Section 5.4. What are the Nash equilibria in pure strategies? 9. [Midterm 1, 2003] Find all the Nash equilibria in Exercise 3 of Section 5.4. (Don’t forget the mixed-strategy equilibrium!) 10. [Homework 1, 2002] Consider the game in Exercise 10 of Section 5.4. What are the Nash equilibria in pure strategies? 11. [Midterm 1 Make up, 2001]Compute all the Nash equilibria in the following game.     3 2 4 0 0 0  2 0 3 3 0 0  0 0 0 0 3 3 12. [Homework 2, 2004] Compute all the Nash equilibria of the following games. (a) L M T (2 1) (0 2) B (0 1) (3 0) 98 CHAPTER 6. NASH EQUILIBRIUM (b) L M R A (4 2) (0 0) (1 1) B (1 1) (3 4) (2 1) C (0 0) (3 1) (1 0) 13. [Homework 2, 2001] A group of  students go to a restaurant. It is common knowledge that each student will simultaneously choose his own meal, but all students will share the total bill equally. If a student gets a meal of price  and √ contributes  towards paying the bill, his payoff will be −. Compute the Nash equilibrium. Discuss the limiting cases  = 1 and  → ∞. 14. [Midterm 1, 2010] Compute a Nash equilibrium of the following game. (This is a version of Rock-Scissors-Paper with preference for Paper.) 1\2   0 0  −2 2    2 −2 −2 3 0 0 3 −2 −1 2 2 −1 1 1 15. [Homework 2, 2006] There are  players, 1 2     , who bid for a painting in a second-price auction. Each player  bids  , and the bidder who bids highest buys the painting at the highest price bid by the players other than himself. (If two ore more players bid the highest bid, the winner is decided by a coin toss.) The value of the art is  for each player  where 1  2  · · ·    0. Find a Nash equilibrium of this game in which player , who values the painting least, buys the object for free (at price zero). Briefly discuss this result and compare it to the answer of Exercise 4 in Section 4.5. 16. [Homework 2, 2006] Compute all the Nash equilibria of the following game. L M R A (4 2) (0 0) (2 1) B (0 1) (3 4) (0 1) C (1 5) (2 1) (1 4) 6.6. EXERCISES 99 17. Assume that each strategy set  is convex and each utility function  is strictly concave in own strategy  .3 Show that all Nash equilibria are in pure strategies. 3 A set  is convex if  + (1 − )  ∈  for all   ∈  and all  ∈ [0 1]. A function  :  →  is strictly concave if  ( + (1 − ) )   () + (1 − )  () for all   ∈  and  ∈ (0 1).