What will happen in the second round?
\What will happen in the second round? Although some of player 2’s and player 3’s strategies may have been eliminated in the first round, y and z were not, and that ensures that x is not strictly dominated. The same argument ex- plains why y is still not strictly dominated for player 2 in the second round and why z is still not strictly dominated for player 3. Thus, x, y, and z survive two rounds. Like the Energizer Bunny, this argument keeps going and going . . . it works for every round! Thus, if (x, y, z) is a Nash equilibrium, then those strategies survive the IDSDS. Although we have demonstrated this property for a three-player game, the argument is general and applies to all games.
While every Nash equilibrium is consistent with IDSDS, can a strategy sur- vive the IDSDS, but not be part of a Nash equilibrium? Absolutely, and in fact, this chapter is loaded with examples. In the American Idol fandom game, all of the strategies survive the IDSDS, since none are strictly dominated. Thus, the IDSDS says that any of the eight feasible strategy profiles could occur. In con- trast, only two strategy profiles—(A, C, E) and (Bebe, Bebe, Bebe) (try saying that real fast!)—are Nash equilibria. Another example is Rock–Paper–Scissors, in which all strategy profiles are consistent with IDSDS, but none are Nash equilibria. Nash equilibrium is a more stringent criterion than IDSDS, since fewer strategy profiles satisfy the conditions of Nash equilibrium.
All Nash equilibria satisfy the iterative deletion of strictly dominated strategies and thereby are consistent with rationality’s being common knowledge. However, a strategy profile that survives the IDSDS need not be a Nash equilibrium.
FIGURE 4.20 depicts how Nash equilibria are a subset of the strategy profiles that survive the IDSDS, which are themselves a subset of all strategy profiles. However, for any particular game, these sets could coincide, so that, for example, the set of Nash equilibria might be the same as those strategy profiles which survive the IDSDS, or the strategies that survive the IDSDS might coincide with the set of all strategy profiles.
4.5.2 The Definition of a Strategy, Revisited To better understand the role of a strategy in the context of Nash equilibrium, think about specifying both a strat- egy for player i—denoted si and intended to be his deci- sion rule—and a conjecture that player i holds regarding the strategy selected by player j—denoted sj(i)—which rep- resents what i believes that j is going to play. A strategy profile ( , . . ., ) is then a Nash equilibrium if, for all i,
1. maximizes player i’s payoff, given that he believes that player j will use sj(i), for all j i.
2. sj(i) � , for all j i.
is then playing a dual role in a Nash equilibrium. As specified in condition 1, it is player i’s decision rule. In addition, as described in condition 2, is player j’s (accurate) conjecture as to what player i will do.
s¿i s¿i
s¿j
si¿
sn¿s1¿
110 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
FIGURE 4.20 Relationship Between Nash Equilibria and the Strategies That Survive the IDSDS
Nash equilibria
All strategy profiles
IDSDS strategy profiles
Summary 111
Recall from Section 2.3 that we required that a strategy specify what a player should do at every possible information set; that is, a strategy must specify behavior even at an information set that cannot be reached, given the prescribed behavior for some preceding information set. For example, in the kidnapping game, the kidnapper’s strategy had to specify whether to release or kill the victim, even if at the initial node that strategy prescribed that he not perform the kidnapping. A strategy must meet this requirement because of the dual role of an equilibrium strategy. A player will have a conjecture as to how another player is going to behave, even if that player did not behave as pre- dicted. For example, the victim’s kin will have a conjecture as to whether the kidnapper will release or kill the victim, even if the kin originally predicted that the kidnapper would not perform the kidnapping. Just because a player did not behave as you expected doesn’t mean that you don’t have beliefs as to what will happen in the future.
At a Nash equilibrium, a strategy has two roles—decision rule and conjec- ture—in which case it’s important that the strategy be fully specified; it must specify behavior at every information set for a player. A Nash equilibrium strategy both prescribes—being a player’s decision rule—and describes—being another player’s conjecture about that player’s decision rule.
Summary A rational player chooses a strategy that maximizes her payoff, given her be- liefs about what other players are doing. Such an optimal strategy is referred to as a best reply to the conjectured strategies of the other players. If we fur- thermore suppose that these conjectures are accurate—that each player is cor- rectly anticipating the strategy choices of the other players—then we have a Nash equilibrium. The appeal of Nash equilibrium is that it identifies a point of “mutual contentment” for all players. Each player is choosing a strategy that is best, given the strategies being chosen by the other players.
In many games, the iterative deletion of strictly dominated strategies (IDSDS) has no traction, because few, if any, strategies are strictly dominated. Nash equilibrium is a more selective criterion; thus, some games might have only a few Nash equilibria while having many more strategy profiles that sur- vive the IDSDS. Generally, Nash equilibrium is a more useful solution concept, for that very reason. Nevertheless, as we found out by way of example, a game can have many Nash equilibria, a unique Nash equilibrium, or none at all.
In deriving the Nash equilibria for a game, one can approach the problem algorithmically, but also intuitively. The best-reply method was put forth as a procedure for deriving Nash equilibria, even though it can be cumbersome when players have many strategies to choose from. Intuition about the play- ers’ incentives can be useful in narrowing down the set of likely candidates for Nash equilibrium.
Games can range from pure conflict to ones where players have a mutual interest. Constant-sum games involve pure conflict, because something that makes one player better off must make other players worse off. An example is the children’s game Rock–Paper–Scissors, which is also an example of an out- guessing game whereby each player is trying to do what the other players don’t expect. At the other end of the spectrum are games in which the interests of the players coincide perfectly, so that what makes one player better off makes the others better off as well. This property describes driving conventions,
a coordination game in which players simply want to choose the same ac- tion. Then there are games that combine conflict and mutual interest, such as the telephone game, Chicken, and American Idol fandom. In these games, un- derstanding the incentives of a player—how best a player should react to what another player is going to do—can provide insight into what strategy profiles are apt to be Nash equilibria.
112 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
1. One of the critical moments early on in the The Lord of the Rings trilogy is the meeting in Rivendale to decide who should take the ring to Mordor. Gimli the dwarf won’t hear of an elf doing it, while Legolas (who is an elf) feels similarly about Gimli. Boromir (who is a man) is opposed to either of them taking charge of the ring. He is also held in contempt, for it was his ancestor who, when given the opportunity to destroy the ring millennia ago, chose to keep it instead. And then there is Frodo the hobbit, who has the weakest desire to take the ring, but knows that someone must throw it into the fires of Mordor. In modeling this scenario as a game, assume there are four players: Boromir, Frodo, Gimli, and Legolas. (There were more, of course, including Aragorn and Elrond, but let’s keep it simple.) Each of them has a preference ordering, shown in the following table, as to who should take on the task of carrying the ring.
EXERCISES
Of the three nonhobbits, each prefers to have himself take on the task. Other than themselves and Frodo, each would prefer that no one take the ring. As for Frodo, he doesn’t really want to do it and prefers to do so only if no one else will. The game is one in which all players simulta- neously make a choice among the four people. Only if they all agree—a unanimity voting rule is put in place—is someone selected; otherwise, no one takes on this epic task. Find all symmetric Nash equilibria.
2. Consider a modification of driving conventions, shown in FIGURE PR4.2, in which each player has a third strategy: to zigzag on the road. Suppose, if a player chooses zigzag, the chances of an accident are the same whether the other player drives on the left, drives on the right, or zigzags as well. Let that payoff be 0, so that it lies between �1, the payoff when a collision oc- curs for sure, and 1, the payoff when a collision does not occur. Find all Nash equilibria.