Defining Nash Equilibrium 91
which ensures that a player’s strategy is optimal, given the other players’ strate- gies. Thus, all players are simultaneously doing their best. A violation of one or more of those conditions means that a strategy profile is not a Nash equilib- rium. Unlike the game of horseshoes, you don’t come “close to a Nash equilib- rium” by having all but one of the conditions satisfied; it’s either all or nothing.
An appeal of Nash equilibrium as a solution concept is that it identifies strategy profiles that are stable in the sense that each player is content to do what she is doing, given what everyone else is doing. Consider, for instance, a strategy profile that is not a Nash equilibrium because, say, player 3’s strategy is not best for her, given what the other players are up to. We would then ex- pect player 3 to change her strategy once she discovers that it is not optimal. In contrast, a Nash equilibrium is not subject to such second-guessing, be- cause players are happy with what they are doing.
To be more concrete on this point, imagine that players play the same game over and over. If they are not currently acting according to a Nash equilibrium, then, after one of the game’s interactions, there will be a player who will learn that his strategy is not the best one available, given what others are doing. He will then have an incentive to change his strategy in order to improve his pay- off. In contrast, if players are behaving according to a Nash equilibrium, they are satisfied with their actions after each round of interactions. Behavior gen- erated by a Nash equilibrium is then expected to persist over time, and social scientists are generally interested in understanding persistent behavior (not necessarily because unstable behavior is uninteresting, but rather because it is just much harder to explain).
Hopefully having convinced you that Nash equilibrium is a worthy solution concept (and if not, bear with me), let’s put it to use with the game of Chicken. We begin by considering the four strategy pairs and asking whether each is a Nash equilibrium.
■ (hang tough, hang tough). If driver 2 chooses hang tough, then driver 1’s payoff from swerve is 1 and from hang tough is 0. (See FIGURE 4.2.) Thus, driver 1 prefers to swerve (and live with a few clucking sounds from his friends) than to hang tough (and learn whether or not there is an afterlife). Thus, hang tough is not best for player 1, which means that player 1’s Nash equilibrium condition is not satisfied. Hence, we can conclude that (hang tough, hang tough) is not a Nash equilibrium. (It is also true that driver 2’s strategy of hang tough is not best for her either, but we’ve already shown this strat- egy pair is not a Nash equilibrium.)
■ (swerve, swerve). If driver 1 chooses swerve, then driver 2’s payoff from swerve is 2 and from hang tough is 3. (See FIGURE 4.3.) Driver 2 thus prefers hang tough if driver 1 is going to chicken out. Since swerve is not the best strat- egy for driver 2, (swerve, swerve) is not a Nash equilibrium either.
FIGURE 4.3 Chicken: Highlighting Driver 2’s Payoffs when Driver 1 Chooses Swerve
Driver 1
Driver 2
Swerve
Hang tough
Swerve Hang tough
2, 2 3,1
1, 3
0,0
FIGURE 4.2 Chicken: Highlighting Driver 1’s Payoffs when Driver 2 Chooses Hang Tough
2,2
3,1
1 ,3 0 ,0
Driver 1
Driver 2
Swerve
Hang tough
Swerve Hang tough
92 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
■ (swerve, hang tough). If driver 2 chooses hang tough, swerve is the best strategy for driver 1, as it produces a payoff of 1 compared with 0 from hanging tough. Consequently, the requirement that driver 1’s strategy is best for him is satisfied. Turning to driver 2, we see that hang tough is best for her, because it yields a payoff of 3, rather than 2 from swerve. The con- dition ensuring that driver 2’s strategy is optimal for her is satisfied as well. Because each driver is choosing the best strategy, given what the other driver is expected to do, (swerve, hang tough) is a Nash equilibrium.
■ (hang tough, swerve). By logic similar to that in the preceding case, this strategy pair is a Nash equilibrium, too.
Summing up, there are two Nash equilibria in this game: (swerve, hang tough) and (hang tough, swerve). Both predict that there will be no car crash and, furthermore, that one and only one driver will swerve. However, Nash equilibrium doesn’t tell us which driver will swerve.
Perhaps the best way to play Chicken is to com- mit to not swerving by eliminating swerve from your strategy set and, most importantly, making this known to the other driver. FIGURE 4.4 illustrates what the game would look like if driver 1 were to elimi- nate swerve from his strategy set. The game now has only one Nash equilibrium: driver 1 hangs tough and driver 2 chickens out.
A tactic similar to that illustrated in Figure 4.4 was taken in a naval encounter about 20 years ago.
Let’s listen in on the radio conversation between the two participants.2
1: “Please divert your course 15 degrees to the north to avoid a collision.”
2: “Recommend that you change your course 15 degrees to the south to avoid a collision.”
1: “This is the captain of a U.S. navy ship. I say again, divert your course.”
2: “No, I say again, divert your course.”
1: “This is the aircraft carrier Enterprise; we are a large warship of the U.S. navy. Divert your course now!”
2: “This is a lighthouse. Your call.”
We have several tasks ahead of us in this chapter. Having defined Nash equilib- rium, we want to learn how to solve games for Nash equilibria and begin to ap- preciate how this concept can be used to derive an understanding of human be- havior. Our analysis commences in Section 4.2 with some simple two-player games that embody both the conflict and mutual interest that can arise in strategic situa- tions. To handle more complicated games, the best-reply method for solving for Nash equilibria is introduced in Section 4.3 and is then applied to three-player games in Section 4.4. Finally, Section 4.5 goes a bit deeper into understanding what it means to suppose that players behave as described by a Nash equilibrium.
4.2 Classic Two-Player Games THE MAIN OBJECTIVE OF this chapter is to get you comfortable both with the con- cept of Nash equilibrium and with deriving Nash equilibria. Let’s warm up with a few simple games involving two players, each of whom has at most
FIGURE 4.4 Chicken when Driver 1 Has Eliminated Swerve as a Strategy
3,1 0,0Driver 1
Driver 2
Hang tough
Swerve Hang tough
4.2 Classic Two-Player Games 93
three strategies. As we’ll see, a game can have one Nash equilibrium, several Nash equilibria, or no Nash equilibrium. The first case is ideal in that we pro- vide a definitive statement about behavior. The second is an embarrassment of riches: we cannot be as precise as we’d like, but in some games there may be a way to select among those equilibria. The last case—when there is no Nash equilibrium—gives us little to talk about, at least at this point. Although in this chapter we won’t solve games for which there is no Nash equilibrium, we’ll talk extensively about how to handle that problem in Chapter 7.
You may be wondering whether there is an “easy-to-use” algorithm for solving Nash equilibria. Chapter 3, for example, presented an algorithm for finding strategies consistent with rationality being common knowledge: the iterative deletion of strictly dominated strategies (IDSDS). Unfortunately, there is no such method for solving Nash equilibrium. For finite games—that is, when there is a finite number of players and each player has a finite number of strategies—the only universal algorithm is exhaustive search, which means that one has to check each and every strategy profile and assess whether it is a Nash equilibrium. We will, however, present some shortcuts for engaging in exhaustive searches.
A useful concept in deriving Nash equilibria is a player’s best reply (or best response). For each collection of strategies for the other players, a player’s best reply is a strategy that maximizes her payoff. Thus, a player has not just one best reply, but rather a best reply for each configuration of strategies for the other players. Furthermore, for a given configuration of strategies for the other players, there can be more than one best reply if there is more than one strategy that gives the highest payoff.
✚ DEFINITION 4.2 A best reply for player i to (s1, . . ., si�1, si�1, . . ., sn) is a strategy that maximizes player i’s payoff, given that the other n � 1 players use strategies (s1, . . ., si�1, si�1, . . ., sn).
A Nash equilibrium can be understood as a strategy profile which ensures that a player’s strategy is a best reply to the other players’ strategies, for each and every player. These are the same n conditions invoked by Definition 4.1, but we’re just describing them a bit differently.
� SITUATION: PRISONERS’ DILEMMA
During the time of Stalin, an orchestra conductor was on a train reading a mu- sical score. Thinking that it was a secret code, two KGB officers arrested the conductor, who protested that it was just Tchaikovsky’s Violin Concerto. The next day, the interrogator walks in and says, “You might as well confess, as we’ve caught your accomplice Tchaikovsky, and he’s already talking.”
The Prisoners’ Dilemma, which we previously considered under the guise of the opera Tosca, is the most widely examined game in game theory. Two members of a criminal gang have been arrested and placed in separate rooms for interrogation. Each is told that if one testifies against the other and the other does not testify, the former will go free and the latter will get three years of jail time. If each testifies against the other, they will both be sentenced to two years. If neither testifies against the other, each gets one year. Presuming that each player’s payoff is higher when he receives a shorter jail sentence, the strate- gic form is presented in FIGURE 4.5.
FIGURE 4.5 The Prisoners’ Dilemma
2,2
1,4
4,1
3,3 Criminal 1
Criminal 2
Testify
Silence
Testify Silence
94 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
This game has a unique Nash equilibrium, which is that both players choose testify. Let us first convince ourselves that (testify, testify) is a Nash equilibrium. If criminal 2 testifies, then criminal 1’s payoff from also testifying is 2, while it is only 1 from remaining silent. Thus, the condition ensuring that criminal 1’s strategy is optimal is satisfied. Turning to criminal 2, we see that, given that criminal 1 is to testify, she earns 2 from choosing testify and 1 from choosing silence. So, the condition ensuring that criminal 2’s strategy is optimal is also satisfied. Hence, (testify, testify) is a Nash equilibrium.
Let us make two further points. First, the Prisoners’ Dilemma is an example of a symmetric game. A two-player game is symmetric if players have the same strategy sets, and if you switch players’ strategies, then their payoffs switch. For example, if the strategy pair is (testify, silence), then the payoffs are 4 for criminal 1 and 1 for criminal 2. If we switch their strategies so that the strat- egy pair is (silence, testify), the payoffs switch: now criminal 1’s payoff is 1 while criminal 2’s payoff is 4. A trivial implication of the symmetric condition is that players who choose the same strategy will get the same payoff.
An important aspect of symmetric games is that if a symmetric strategy profile—such as (testify, testify)—is optimal for one player, it is also optimal for the other player. If criminal 1’s strategy is optimal (given what criminal 2 is doing), then it must also be the case that criminal 2’s strategy is optimal (given what criminal 1 is doing). By the symmetry in the game and the consideration of a symmetric strategy profile, the equilibrium conditions for the players are identical. Thus, for a symmetric strategy profile in a symmetric game, either all of the Nash equilibrium conditions hold or none do. Now that we know this property, it is sufficient to show that if testify is optimal for criminal 1 (given that criminal 2 chooses testify), testify must also be optimal for criminal 2.
For a symmetric strategy profile in a symmetric game, if one player’s strategy is a best reply, then all players’ strategies are best replies.
Note also that testify is a dominant strategy. Regardless of what the other criminal does, testify produces a strictly higher payoff than silence. With a little thought, it should be clear that if a player has a dominant strategy, then a Nash equilibrium must have her using it. For a player’s strategy to be part of a Nash equilibrium, the strategy must be optimal, given the strategies used by the other players. Because a dominant strategy is always the uniquely best strategy, then it surely must be used in a Nash equilibrium. It follows that if all players have dominant strategies—as in the Prisoners’ Dilemma—the game has a unique Nash equilibrium in which those dominant strategies are used. Thus, (testify, testify) is the unique Nash equilibrium in the Prisoners’ Dilemma.
© S
C O
TT A
D A
M S/
D IS
T. B
Y U
N IT
ED F
EA TU
R E
SY N
D IC
A TE
, IN
C .
Dilbert/Scott Adams
If a player has a dominant strategy, a Nash equilibrium requires that the player use it. If all players have a dominant strategy, then there is a unique Nash equilibrium in which each player uses his or her dominant strategy.