SITUATION: A GAME OF COORDINATION AND CONFLICT—TELEPHONE
In the driving conventions game, there were two Nash equilibria and the play- ers were indifferent between them: driving on the right was just as good as driving on the left. Now let us consider a setting that also has two equilibria, but the players rank them differently.
4.2 Classic Two-Player Games 95
FIGURE 4.6 Driving Conventions
1,1
1,1�1,�1
�1,�1 Thelma
Louise
Drive left
Drive right
Drive left Drive right
96 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
Colleen is chatting on the phone with Winnie and suddenly they’re disconnected. Should Colleen call Winnie or should Winnie call Colleen? Colleen and Winnie are the players, and they have a strategy set composed of call and wait. Each is willing to call the other if that is what it takes to continue the conversation, but each would prefer the other to do so. If they both try to call back, then the other’s phone is busy and thus they don’t reconnect. Obviously, if neither calls back, then they don’t reconnect either. The strategic form game is shown in FIGURE 4.7.*
The strategy pair (call, call) is not a Nash equilibrium, since, for example, Colleen earns 0 from call, but a higher payoff of 3 from wait. Thus, Colleen’s strategy of call is not optimal should Winnie choose call. Nor is (wait, wait) a Nash equilibrium, since, for example, Winnie earns 1 from choosing wait and a higher payoff of 2 from choosing call should Colleen choose wait. Thus, Winnie’s strategy is not optimal, given what Colleen is doing.
A strategy pair that is a Nash equilibrium has one player calling back while the other waits. Consider the strategy pair (call, wait), so that Colleen is to call. Given that Winnie is waiting for Colleen’s call, Colleen prefers to call, as it delivers a payoff of 2 while waiting has a payoff of only 1. And if Winnie an- ticipates that Colleen will call her, then Winnie prefers to wait for Colleen’s call. For Winnie, waiting delivers a payoff of 3, whereas should she call, the payoff is 0.
If the telephone game is symmetric (and it is), we can infer by symmetry from (call, wait) being a Nash equilibrium that (wait, call) is also a Nash equilibrium (where now it is Winnie who is to call). To see why, first convince yourself that this is a symmetric game. If the strategy pair is (call, wait), then Colleen gets a payoff of 2 and Winnie gets 3. If we switch the strategies so that the strategy pair is (wait, call), then Colleen now gets a payoff of 3 and Winnie gets 2. Furthermore, they have the same payoff when they choose the same strategy. This symmetry implies that the Nash equilibrium condition for Winnie at strat- egy pair (wait, call) is the same as the Nash equilibrium condition for Colleen at (call, wait), and the Nash equilibrium condition for Colleen at (wait, call) is the same as the Nash equilibrium condition for Winnie at (call, wait). Thus, if, at (call, wait), Colleen finds it optimal to choose call, then Winnie must find it op- timal to choose call at strategy pair (wait, call); the conditions are exactly the same. Either both conditions hold or neither does. Similarly, if, at (call, wait), Winnie finds it optimal to choose wait, then Colleen must find it optimal to choose wait at (wait, call).
In sum, by virtue of the game being symmetric, either both (wait, call ) and (call, wait) are Nash equilibria or neither are. Since we’ve shown that (call, wait) is a Nash equilibrium, then, by symmetry, (wait, call ) is a Nash equilibrium.
If a game is symmetric, but the equilibrium is asymmetric, how do players coordinate? How would you coordinate in the telephone gametelephone game?
0,0
3,2
2,3
1,1 Colleen
Winnie
Call
Wait
Call Wait
FIGURE 4.7 The Telephone Game
*This is the same game as the well-known “Battle of the Sexes,” though recast in a more gender-neutral setting. The original game was one in which the man wants to go to a boxing match and the woman wants to go to the opera. Both would prefer to do something together than to disagree.
4.2 Classic Two-Player Games 97
� SITUATION: AN OUTGUESSING GAME—ROCK–PAPER–SCISSORS
Lisa: Look, there’s only one way to settle this: Rock–Paper–Scissors.
Lisa’s Brain: Poor predictable Bart. Always picks rock.
Bart’s Brain: Good ol’ rock. Nothin’ beats that!
(Bart shows rock, Lisa shows paper)
Bart: Doh! —FROM THE EPISODE “THE FRONT,” OF THE SIMPSONS.
How many times have you settled a disagreement by using Rock–Paper–Scissors? In case you come from a culture that doesn’t use this device, here’s what it’s all about. There are two people, and each person moves his hands up and down four times. On the fourth time, each person comes down with either a closed fist (which signals her choice of rock), an open hand (signaling paper), or the middle finger and forefinger in the shape of scissors (no explanation required). The winner is determined as follows: If one person chooses rock and the other scissors, then rock wins, since scissors break when trying to cut rock. If one person chooses rock and the other paper, then paper wins, as paper can be wrapped around rock. And if one person chooses paper and the other scissors, then scissors wins, since scissors can cut paper. If the two players make identical choices, then it is considered a draw (or, more typ- ically, they play again until there is a winner).
If we assign a payoff of 1 to winning, �1 to losing, and 0 to a draw, then the strategic form game is as described in FIGURE 4.8. Contrary to Bart’s belief, rock is not a dom- inant strategy. While rock is the unique best reply against scissors, it is not the best reply against paper. In fact, there is no dominant strategy. Each strategy is a best reply against some strategy of the other player. Paper is the unique best reply against rock, rock is the unique best reply against scissors, and scissors is the unique best reply against paper.
Without any dominated strategies, the IDSDS won’t get us out of the starting gate; all strategies survive the IDSDS. So, being good game theorists, we now pull Nash equilibrium out of our toolbox and go to work. After much hammering and banging, we chip away some of these strat- egy pairs. We immediately chip off (rock, rock), as Bart ought to choose paper, not rock, if Lisa is choosing rock. Thus, (rock, rock) now lies on the floor, hav- ing been rejected as a solution because it is not a Nash equilibrium. We turn to (paper, rock), and while Bart’s strategy of paper is a best reply, Lisa’s is not, since scissors yields a higher payoff than rock when Bart is choosing paper. Hence, (paper, rock) joins (rock, rock) on the floor. We merrily continue with our work, and before we know it, the floor is a mess as everything lies on it! None of the nine strategy pairs is a Nash equilibrium.
You could check each of these nine strategy pairs and convince yourself that that claim is true, but let me offer a useful shortcut for two-player games. Suppose we ask whether Lisa’s choice of some strategy, call it y, is part of a Nash equilibrium. (I say “part of,” since, to even have a chance at being a Nash equilibrium, there must also be a strategy for Bart.) For y to be part of a Nash equilibrium, Bart must choose a strategy (call it c) that is a best reply to Lisa’s
FIGURE 4.8 Rock–Paper–Scissors
Bart
Lisa
Rock
Paper
Scissors
PaperRock Scissors
0,0
1,�1
�1,1 0,0
1,�1
�1,10,0
1,�1
�1,1
98 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
choosing y. Choosing such a strategy ensures that Bart’s Nash equilibrium con- dition is satisfied. To ensure that Lisa is also acting optimally, we then need to derive her best reply to Bart’s choosing c (which, recall, is his best reply to Lisa’s choosing y). Now suppose that Lisa’s best reply to c is actually y, which is the strategy we started with for Lisa. Then we have shown that y is indeed part of a Nash equilibrium and the equilibrium is, in fact, (c, y). However, if Lisa’s best reply to Bart’s choosing c is not y, then we conclude that y is not part of any Nash equilibrium. In that case, in one fell swoop we’ve eliminated all strategy profiles involving Lisa’s choosing y. Putting it pictorially, this is what we need to happen for Lisa’s playing y to be part of a Nash equilibrium:
Lisa plays y S Bart’s best reply to y is c S Lisa’s best reply to c is y.
To put this algorithm into action, let us ask whether Lisa’s choosing rock is part of a Nash equilibrium. If Bart thinks that Lisa is going to choose rock, then he wants to choose paper. Now, if Bart chooses paper, then Lisa wants to choose scissors. Since this option is different from what we initially assumed that Lisa would choose, which was rock, we conclude that there is no Nash equilibrium in which Lisa chooses rock. Hence, none of the strategy profiles in which Lisa chooses rock—namely, (rock, rock), (paper, rock), and (scissors, rock)—are Nash equilibria. Now let’s do the same trick on the strategy paper for Lisa in order to determine whether her choosing paper is part of an equilibrium. If Lisa chooses paper, Bart’s best reply is scissors, and Lisa’s best reply to Bart’s selection of scis- sors is rock, not paper. Hence, Lisa’s using paper is not part of any Nash equilib- rium, so we can eliminate (rock, paper), (paper, paper), and (scissors, paper) as Nash equilibria. Finally, using the same method, we can show that Lisa’s choos- ing scissors is not part of any Nash equilibrium. In this manner, we’ve proven that there is no Nash equilibrium for the game of Rock–Paper–Scissors.
Rock–Paper–Scissors is an example of an outguessing game. In an out- guessing game, maximizing your payoff requires that you outguess the other player (or players). That is, you want to do what they don’t expect. If the other player thinks that you’re going to play strategy x, and she responds by playing b, then you don’t want to play x in response to her playing b; instead, you want to respond with something else. For example, if Lisa thinks that Bart is going to play rock, then she’ll play paper, in which case Bart doesn’t want to do as Lisa expects. Instead, he should play scissors, not rock. (Unfortunately, Bart isn’t that smart, but you have to blame Matt Groening for that, not game theory.)
As it turns out, outguessing games arise in many situations. Sports and mil- itary conflicts are two prominent examples; we’ll investigate them quite ex- tensively in Chapter 7. However, be forewarned: if you intend to enter the USA Rock–Paper–Scissors League (yes, there is such a thing), game theory really can’t help you design a winning strategy.
That Rock–Paper–Scissors is not just a kid’s game was recently demonstrated by the two leading auction houses: Christie’s and Sotheby’s. The owner of an art collection worth in excess of $20 million decided to determine which auction house would sell his collection—and, consequently, earn millions of dollars in commissions—on the basis of the outcome of a round of Rock–Paper–Scissors.4
Rather than play the game in the traditional way, however, with physical hand movements, an executive for Christie’s and an executive for Sotheby’s each wrote down one of the three strategies on a piece of paper. Christie’s won, choos- ing rock to beat Sotheby’s scissors.