PREFERENCE RANKINGS FOR THE LORD OF THE RINGS
Person First Second Third Fourth Fifth
Boromir Boromir Frodo No one Legolas Gimli
Gimli Gimli Frodo No one Boromir Legolas
Legolas Legolas Frodo No one Gimli Boromir
Frodo Legolas Gimli Boromir Frodo No one
Exercises 113
3. Return to the team project game in Chapter 3, and suppose that a frat boy is partnered with a sorority girl. The payoff matrix is shown in FIGURE PR4.3. Find all Nash equilibria.
4. Consider the two-player game illustrated in FIGURE PR4.4. a. For each player, derive those strategies which survive the iterative
deletion of strictly dominated strategies. b. Derive all strategy pairs that are Nash equilibria.
5. Consider the two-player game depicted in FIGURE PR4.5. a. Derive those strategies which survive the iterative deletion of strictly
dominated strategies. b. Derive all strategy pairs that are Nash equilibria.
1,1
0,0
0,0
0,0
0,0
�1,�1 1,1
0,0
�1,�1Drive left
Drive right
Zigzag
Drive rightDrive left Zigzag
FIGURE PR 4.2 Modified Driving Conventions Game
FIGURE PR4.3 Team Project
0,0 2,1
1,2
2,6 3,5
4,4Frat boy
Sorority girl
Low
Moderate
High
Low Moderate High
6,2
3,4
5,3
FIGURE PR4.4
4,0 2,1
2,3
2,2
1,2
3,4Player 1
Player 2
a
b
c
3,2
0,3
0,1
x y z
FIGURE PR4.5
1,2 1,2
4,0
0,2
3,1
0,1
2,1
1,3 Player 1
Player 2
a
b
c
d
0,3
2,4
1,2
0,2
x y z
114 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
6. Return to the “white flight” game in Chapter 3. Now suppose that four of the eight homes are owned by one landlord, Donald Trump, and the other four are owned by a second landlord, John Jacob Astor. A strategy is the number of black families to whom to rent. Construct the payoff matrix and find the set of Nash equilibria. (Although you’re surely familiar with Donald Trump, John Jacob Astor has the noteworthy property of possibly being the first millionaire in U.S. history. Centuries before The Donald ar- rived on the real-estate scene in New York, Astor was wealthy beyond be- lief due to his New York City landholdings.)
7. Return to the kidnapping game, whose strategic form is shown in FIGURE PR4.7. Find all of the Nash equilibria.
FIGURE PR4.7 Kidnapping
3,5 3,5
3,5 3,5Guy (kidnapper)
Vivica (kin of victim)
Pay ransom Do not pay ransom
4,1 2,2
5,3 1,4
Do not kidnap/Kill
Do not kidnap/Release
Kidnap/Kill
Kidnap/Release
8. Queen Elizabeth has decided to auction off the crown jewels, and there are two bidders: Sultan Hassanal Bolkiah of Brunei and Sheikh Zayed Bin Sultan Al Nahyan of Abu Dhabi. The auction format is as follows: The Sultan and the Sheikh simultaneously submit a written bid. Exhibiting her well-known quirkiness, the Queen specifies that the Sultan’s bid must be an odd number (in hundreds of millions of English pounds) between 1 and 9 (that is, it must be 1, 3, 5, 7, or 9) and the Sultan’s bid must be an even number between 2 and 10. The bidder who submits the highest bid wins the jewels and pays a price equal to his bid. (If you recall from Chapter 3, this is a first-price auction.) The winning bidder’s payoff equals his valuation of the item less the price he pays, while the losing bidder’s payoff is zero. Assume that the Sultan has a valuation of 8 (hundred mil- lion pounds) and the Sheikh has a valuation of 7. a. In matrix form, write down the strategic form of this game. b. Derive all Nash equilibria.
9. Find all of the Nash equilibria for the three-player game in FIGURE PR4.9.
10. Return to the game of promotion and sabotage in Section 4.4. a. Determine whether the following strategy profile is a Nash equilib-
rium; (i) player 1 is negative against player 2, (ii) player 2 is negative against player 3, and (iii) player 3 is negative against player 1.
b. Find a Nash equilibrium in which player 2 wins the promotion with certainty (probability 1).
11. When there are multiple Nash equilibria, one approach to selecting among them is to eliminate all those equilibria which involve one or more players using a weakly dominated strategy. For the voting game in Figure 4.17, find all of the Nash equilibria that do not have players using a weakly dominated strategy.
12. Recall the example of Galileo Galilei and the Inquisition in Chapter 2. The strategic form of the game is reproduced in FIGURE PR4.12. Find all of the Nash equilibria.
Exercises 115
FIGURE PR4.9
Player 3 : A
Player 1
Player 2
a
b
c
yx z
1,1,0
3,2,1
2,0,0
1,2,3
2,0,0
0,2,3
0,1,2
2,0,0
3,1,1
Player 3 : B
Player 1
Player 2
a
b
c
yx z
2,0,0
1,2,0
0,1,2
1,2,1
0,0,1
2,2,1
1,2,1
2,1,2
2,1,0
Player 3 : C
Player 1
Player 2
a
b
c
yx z
2,0,0
0,1,1
3,1,2
1,2,1
0,1,2
0,1,2
0,1,2
0,1,2
1,1,2
FIGURE PR4.12
Pope Urban VIII : Refer
3,4,5 3,4,5
3,4,5 3,4,5
1,5,4 4,2,2
2,1,1 4,2,2
Galileo
Inquisitor
C/C
C/DNC
DNC/C
DNC/DNC
Torture Do not torture
Pope Urban VIII: Do Not Refer
5,3,3
5,3,3
5,3,3
5,3,3
5,3,3
5,3,3
5,3,3
5,3,3
Galileo
Inquisitor
C/C
C/DNC
DNC/C
DNC/DNC
Torture Do not torture
116 CHAPTER 4: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE GAMES WITH TWO OR THREE PLAYERS
13. Find all of the Nash equilibria for the three-player game shown in FIGURE PR4.13.
FIGURE PR4.13
Player 3: A
Player 1
Player 2
a
b
c
yx z
2,0,4
3,2,3
1,0,2
0,1,0
1,1,1
0,0,3
2,1,0
1,2,3
3,1,1
Player 3: B
Player 1
Player 2
a
b
c
yx z
2,0,3
1,3,2
0,0,0
2,2,2
4,1,2
3,0,3
0,4,3
1,1,2
2,1,0
4.6 Appendix: Formal Definition of Nash Equilibrium CONSIDER A GAME WITH n players: 1, 2, . . . , n. Let Si denote player i’s strategy set, and read as “strategy is a member of Si.” Let S�i be composed of all (n � 1)-tuples of strategies for the n � 1 players other than player i, and let Vi(s�i, s��i) be the payoff of player i when his strategy is and the other play- ers use s��i � (s�1, . . ., s�i�1, s�i�1, . . ., s�n). Then for all i � 1, 2, . . ., n, a strategy profile (s*1, . . ., s
* n) is a Nash equilibrium if s
* i maximizes player i’s payoff, given
that the other players use strategies (s*1, . . ., s * i�1, s
* i�1, . . ., s
* n). More formally,
(s*1, . . ., s * n) is a Nash equilibrium if and only if for all i � 1, 2, . . ., n,
Vi(s * 1, . . ., s
* n) Vi(s
* 1, . . ., s
* i�1, si, s
* i�1, . . ., s
* n) for all si Si.
REFERENCES 1. “Disney Out-‘Sharks’ DreamWorks,” by Marcus Errico (Aug. 18, 2003)
<www.eonline.com>. Sharkslayer later had its title changed to Shark Tale.
2. A transcript of this conversation was reportedly released by the U.S. Chief of Naval Operations <www.unwind.com/jokes-funnies/militaryjokes/ gamechicken.shtml>.
3. <www.brianlucas.ca/roadside/>.
4. Carol Vogel, “Rock, Paper, Payoff: Child’s Play Wins Auction House an Art Sale,” New York Times, Apr. 29, 2005.
5. This game is based on Kong-Pin Chen, “Sabotage in Promotion Tournaments,” Journal of Law, Economics, and Organization, 19 (2003), 119–40. That paper also provides the anecdote regarding the Chinese Communist Party leadership.
��
s¿i
s¿is¿i � S
5.1 Introduction IN THIS CHAPTER, WE GO beyond two- and three-player games to consider a richer array of settings. This means examining not only games with more than three players, but also games with an unspecified number of players. By the latter, I mean that there are n players, where n could be 2, 3, 10, 50, . . . you name it. But whatever its value, n is fixed and known to the players. In some games, the equilibrium looks the same regardless of the value that n takes, while in other games the number of players drastically alters their behavior.
Before embarking on the next leg of our voyage on the sea of strategic rea- soning, it is helpful to know where our ship is heading. In the games of this chapter, all players have the same strategy sets and thus face the same choices. In Section 5.2, players also have identical payoff functions, which means that the game is symmetric. Then, in Section 5.3, players are allowed to have dif- ferent tastes, as reflected in distinct payoff functions. Whether symmetric or asymmetric, in some games equilibrium behavior may mean that all players act the same. In other games—even symmetric ones—players act differently. In fact, a symmetric game need not have a symmetric equilibrium (i.e., all players choosing the same strategy). Similarly, an asymmetric game need not have an asymmetric equilibrium.
Two important forces, tipping and congestion, can determine whether play- ers make identical or different choices when faced with the same type of de- cision. Tipping reflects the tendency of a player to be increasingly attracted to a strategy when more players choose it. For example, suppose you are a teenager (which shouldn’t be difficult for some of you) who, in deciding what to wear, wants to “fit in.” In comparing clothes from Abercrombie & Fitch and The Gap, the more of your friends who opt for the former, the more appealing that choice becomes to you. In a game, when enough players choose a partic- ular strategy, it can “tip the balance” so that all (or most) players want to choose that same strategy (hence the term “tipping”). At some point in recent years, tipping in the teenage fashion world caused The Gap to lose its position as the leading clothing chain to other retailers, such as Abercrombie & Fitch (which, by the time of the publication of this book, might have lost its appeal). When players’ payoffs have this tipping property, extreme equilibria—whereby a high fraction of all players choose the same strategy—are frequently ob- served. The adage “The more, the merrier” reflects tipping at work.1
Congestion is the opposite of tipping: The more people who use a strategy, the less attractive it becomes. Each workday, commuters engage in a game with congestion when they decide on the route to take to work. The more peo- ple who take a particular route, the slower is traffic on that route, and thus the
5
117
Stable Play: Nash Equilibria in Discrete n-player Games
118 CHAPTER 5: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE n-PLAYER GAMES
less desirable it is to a commuter. Yogi Berra probably said it best when asked about a popular restaurant: “No one goes there anymore; it’s too crowded.” The irony of that statement highlights what equilibrium often looks like in a game with congestion: not everyone makes the same choice—for it would be “too crowded” if they did—and this is true even when the game is symmetric.
You should keep tipping and congestion in mind as we investigate various games. Foreshadowing our analysis, tipping is present in the games of Operating Systems and Civil Unrest; while in the games of Internship, Entry, and The Sneetches (which ought to be required reading in any game theory class), the operative force is congestion. Though not every game has either tip- ping or congestion, recognizing when one of those effects is present can be useful in suggesting what an equilibrium might look like—and that can save you a lot of time in solving a game. All those millions of years of evolution ought to allow us hominids to replace the brute force of exhaustive search with some clever reasoning.
5.2 Symmetric Games A GAME IS SYMMETRIC when (1) all players have the same strategy sets; (2) players receive the same payoff when they choose the same strategy; and (3) if you switch two players’ strategies, then their payoffs switch as well. An ex- ample is provided in FIGURE 5.1. The strategy pair (moderate, low) results in players 1 and 2 having payoffs of 2 and 3, respectively. Now switch their strate- gies so that the pair is (low, moderate). Then the payoffs for players 1 and 2 have similarly switched to 3 and 2, respectively. This is because, for any strat-
egy pair in a symmetric game, swapping strategies means swapping payoffs.
Now change the labels of player 2’s strategies, as shown in FIGURE 5.2. It should be clear that the game is unaltered in any meaningful way; it’s still sym- metric. We just need to recognize that left for player 2 is equivalent to low for player 1 and so forth. What is critical is that players have the same number of strategies and that we can match up their strategies so that they satisfy the two conditions on payoffs mentioned in the previous paragraph.
As we explore various symmetric games, here’s a useful property to keep in mind: Consider an n- player symmetric game, and suppose we find an asymmetric Nash equilibrium, which means that not all players use the same strategy. If we find one asymmetric Nash equilibrium, then there are an- other asymmetric Nash equilibria to be found. For example, (moderate, low) is a Nash equilibrium for the game in Figure 5.1, and so is (low, moder- ate)—a necessary implication of symmetry. The con- dition ensuring that it is optimal for player 1 to use moderate given that player 2 uses low is exactly (and I mean exactly) the same as the condition ensuring that it is optimal for player 2 to use moderate given
n � 1
FIGURE 5.1 A Symmetric Game.
2,1 1,2
Player 1
Player 2
Low
Moderate
High
Low Moderate High
1,1 3,2 1,2
3,3
2,3 2,2 2,1
FIGURE 5.2 The Symmetric Game of Figure 5.1 with Strategies Renamed for Player 2
1,1 3,2
2,3
2,1 1,2
2,2Player 1
Player 2
Left Middle Right
1,2
3,3
2,1
Low
Moderate
High
5.2 Symmetric Games 119
that player 1 uses low. And the condition ensuring that it is optimal for player 2 to use low given that player 1 uses moderate is the same condition ensuring that it is optimal for player 1 to use low given that player 2 uses moderate. Thus, if (low, moderate) is a Nash equilibrium, then so is (moder- ate, low).
In a symmetric game, if a strategy profile is a Nash equilibrium, then so is a strategy profile that has players swap strategies. That is, in a two-player symmetric game, if (s , s ) is a Nash equilibrium, then so is (s , s ). And in a symmetric three-player game, if (s , s , s ) is a Nash equilibrium, then so are (s , s , s ), (s , s , s ), (s , s , s ), ( s , s , s ), and (s , s , s ).
With this piece of insight, the discovery of one asymmetric equilibrium in a symmetric game tells you that there are other asymmetric equilibria and even tells you what they look like. Not a bad trick, eh?
� SITUATION: THE SNEETCHES
Now, the Star-Belly Sneetches
Had bellies with stars.
The Plain-Belly Sneetches
Had none upon thars.2
Dr. Seuss’ story “The Sneetches” starts out with some of these fictional creatures having a star on their belly and the others not. The star-bellied sneetches were esteemed— reveling in frankfurter roasts—and those without stars led a morose life. Though perhaps unfair, the sneetches’ world was stable: neither the haves nor the have-nots sought to upset the status quo. But stability turned to turmoil when Sylvester McMonkey McBean rolled into town with his machine that could put stars on and take them off. Do you recall what happened? How McBean’s machine changed the equilibrium in the land of sneetches?
To explore this Seussian world, let us suppose that there are n sneetches and n is odd. Suppose also that initially less than half of the sneetches have stars. With the arrival of Sylvester McMonkey McBean and his Star- Off and Star-On machines, each sneetch must decide what to do with his or her belly.* Each of the sneetches who were born with stars must decide whether to retain the star or have it taken off. Likewise, each of the sneetches with “none upon thars” must decide whether to have a star put on or remain starless.
The story is unclear as to why a star bestows esteem upon its wearer—indeed, the point of the story is that what determines status can be quite arbitrary—but
¿–‡–¿‡¿‡–‡¿––‡¿ ‡–¿
¿––¿
*The gender pronoun issue here is particularly dicey, as I don’t even know if sneetches have different gen- ders and, if so, how many. Perhaps sneetches are hermaphrodites or asexual, or, like some amphibians, they change their gender during their lifetime. Or perhaps I should stop trying to be so politically correct and just get on with the story.
FR O
M T
H E
SN EE
TC H
ES A
N D
O TH
ER S
TO R IE
S B Y
D R . S
EU SS
, C O
PY R IG
H T
TM &
C O
PY R IG
H T
© B
Y D
R . S
EU SS
E N
TE R PR
IS ES
, L .P . 1
9 5 3 , 1
9 5 4 ,
1 9 6 1 , R
EN EW
ED 1
9 8 9 . U
SE D
B Y
PE R M
IS SI
O N
O F
R A
N D
O M
H O
U SE
C H
IL D
R EN
’S B
O O
K S,
A D
IV IS
IO N
O F
R A
N D
O M
H O
U SE
, I N
C .
Star-Bellied Sneetches Show Off Their Stars
120 CHAPTER 5: STABLE PLAY: NASH EQUILIBRIA IN DISCRETE n-PLAYER GAMES
we’ll assume that whatever is rarer is prized. Let m denote the number of sneetches with stars on their bellies at the end of the day. If then hav- ing a star is esteemed (since fewer sneetches have stars than don’t), and in that case, each sneetch with a star gets a payoff of 1 and each lacking a star gets a payoff of 0. If, instead, then not having a star is esteemed, so each sneetch with a star gets a payoff of 0 and each without one gets a payoff of 1. Contrary to the story, suppose Sylvester McMonkey McBean provides his serv- ices for free.*
Note that a sneetch’s payoff depends only on whether or not she has a star and how many sneetches altogether have stars. Also since the use of the Star- On and Star-Off machines is free, it actually doesn’t matter whether a sneetch was born with a star. The payoffs are summarized in TABLE 5.1.
n/2 6 m,
m 6 n/2,
*In the story, McBean initially charged the sneetches without a star $3 to have a star put on and then charged the original star-bellied sneetches $10 to have a star removed. After that, I suspect the price con- tinued to rise. An exercise at the end of the chapter has you derive equilibrium when a price is charged.
TABLE 5.1 PAYOFF TO A SNEETCH
What’s on the Sneetch’s Total Number of Sneetches Belly? with Stars (m) Payoff
Star 1
Star 0
Nothing 0
Nothing 1n2 6 m
m 6 n2
n 2 6 m
m 6 n2