CHECK YOUR UNDERSTANDING
Exercises 79
auction—the presence of a weakly dominant strategy is a good choice for the cautious player.
A procedure known as the iterative deletion of strictly dominated strate- gies (IDSDS) builds on the idea that a rational player does not use a strictly dominated strategy. The key assumption of IDSDS is that it is common knowl- edge that players are rational and thus common knowledge that players avoid using strictly dominated strategies. The IDSDS procedure eliminates each player’s strictly dominated strategies from the game, resulting in a game with fewer strategies (if some strategies are indeed strictly dominated and thus can be deleted). In this smaller game, strictly dominated strategies are again elim- inated. A strategy that may not be strictly dominated in the original game may become strictly dominated in the smaller game after some of the other players’ strategies are eliminated. This procedure continues—eliminating strictly dom- inated strategies and then doing the same for the game that remains—until none of the remaining strategies are strictly dominated. Strategies that survive the IDSDS represent the set of possible solutions.
For some games, such as Tosca, a unique strategy profile can be derived as- suming only that the players are rational. For that to be the case, each player must have a dominant strategy. In other games, like the Existence-of-God game, the derivation of a unique solution requires not only that all players be rational, but also that all players know that all players are rational. Other games, such as the Doping game, require yet more: all players know that all players know that all players are rational. Of course, this procedure of itera- tively eliminating stupid (that is, strictly dominated) strategies has traction only if, in the original game, some strategies are indeed stupid. In fact, there are many games in which no strategies are stupid (we’ll start seeing them in the next chapter), in which case the iterative deletion of strictly dominated strategies is incapable of eliminating any of the possible strategy profiles.
This chapter has delivered some of the subtle insights that game theory of- fers. In the Tosca game, we showed how players acting in their own best in- terests can make everyone worse off. In the Cigarette Advertising game, play- ers having fewer options can make themselves better off. And in the Boxed Pigs game, a weaker player can outperform a stronger one. The ensuing chap- ters will provide many more insightful lessons.
The observant reader will have noticed that we did not solve the game in Figure 3.1 that led off the chapter. Figuring out what happens in the kidnap- ping scenario is not feasible with the methods of this chapter, because no strategies are strictly dominated. Fortunately, game theory has many more tools up its sleeve, and the next chapter will pull another one out. Like the show business adage says, “Always leave them wanting more.”
Sections 3.5 and 3.6 provide additional insight into strict and weak domi- nance and the advanced topic of rationalizability.
1. Derive the strategic form of the Mugging game in Figure 2.8 of Chapter 2 (page 29), and determine whether any strategies are either strictly dominated or weakly dominated.
EXERCISES
80 CHAPTER 3: ELIMINATING THE IMPOSSIBLE: SOLVING A GAME WHEN RATIONALITY IS COMMON KNOWLEDGE
2. In the Dr. Seuss story “The Zax,” there is a North-Going Zax and a South-Going Zax who, on their trek, come to find themselves facing each other. Each Zax must decide whether to continue in their current direction or move to the side so that the other may pass. As the story re- veals, neither of them moves and that stalemate perpetuates for many years. Write down a strategic form game of this situation.
3. For the Team-project game, suppose a jock is matched up with a soror- ity girl as shown in FIGURE PR3.3. a. Assume that both are rational and that the jock knows that the soror-
ity girl is rational. What happens? b. Assume that both are rational and that the sorority girl knows that
the jock is rational. What happens?
3,0 4,1
2,2
1,6 2,5
3,4Jock
Sorority girl
Low
Moderate
High
ModerateLow High
5,2
3,4
4,3
FIGURE PR3.3
4. Consider the strategic form game shown in FIGURE PR3.4. a. Assume that both players are rational. What happens? b. Assume that both players are rational and that each believes that the
other is rational. What happens? c. Find the strategies that survive the iterative deletion of strictly domi-
nated strategies.
FIGURE PR3.4
1,3 1,1
0,2
3,1
1,2
2,2Player 1
Player 2
a
b
c
0,2
3,0
1,0
x y z
5. For the strategic form game shown in FIGURE PR3.5, derive the strategies that survive the iterative deletion of strictly dominated strategies.
FIGURE PR3.5
5,2 3,4
4,4
2,3
3,5
1,5
4,4
3,2 Player 1
Player 2
a
b
c
d
2,1
3,0
0,4
3,3
x y z
Exercises 81
6. Two Celtic clans—the Garbh Clan and the Conchubhair Clan—are set to battle. (Pronounce them as you’d like; I don’t speak Gaelic.) According to tradition, the leader of each clan selects one warrior and the two war- riors chosen engage in a fight to the death, the winner determining which will be the dominant clan. The three top warriors for Garbh are Bevan (which is Gaelic for “youthful warrior”), Cathal (strong in battle), and Duer (heroic). For Conchubhair, it is Fagan (fiery one), Guy (sensible), and Neal (champion). The leaders of the two clans know the following information about their warriors, and each knows that the other leader knows it, and furthermore, each leader knows that the other leader knows that the other leader knows it, and so forth (in other words, the game is common knowledge): Bevan is superior to Cathal against Guy and Neal, but Cathal is superior to Bevan against Fagan. Cathal is supe- rior to Duer against Fagan, Guy, and Neale. Against Bevan, Guy is best. Against Cathal, Neal is best. Against Duer, Fagan is best. Against Bevan, Fagan is better than Neal. Against Cathal, Guy is better than Fagan. Against Duer, Guy and Neal are comparable. Assuming that each leader cares only about winning the battle, what can you say about who will be chosen to fight?
7. Consider the two-player strategic form game depicted in FIGURE PR3.7. a. Derive the strategies that survive the iterative deletion of strictly dom-
inated strategies. b. Derive the strategies that survive the iterative deletion of weakly dom-
inated strategies. (The procedure works the same as the iterative dele- tion of strictly dominated strategies, except that you eliminate all weakly dominated strategies at each stage.)
FIGURE PR3.7
1,2 0,5
1,3
3,4
2,3
2,1
4,0
5,2 Player 1
Player 2
a
b
c
d
2,2
4,0
3,3
5,3
4,0
7,5
6,2
2,0
w x y z
8. Consider the three-player game shown in FIGURE PR3.8. Player 1 selects a row, either a1, b1 or c1. Player 2 selects a column, either a2 or b2. Player 3 selects a matrix, either a3 or b3. The first number in a cell is player 1’s payoff, the second number is player 2’s payoff, and the last number is player 3’s payoff. Derive the strategies that survive the iterative deletion of strictly dominated strategies.
FIGURE PR3.8
0,3,1
1,0,2
3,1,0
1,1,0
1,2,1
2,3,1a1 b1 c1
a3
a2 b2
2,0,2
1,1,1
3,1,1
2,2,1
0,2,0
1,3,2a1 b1 c1
b3
a2 b2
82 CHAPTER 3: ELIMINATING THE IMPOSSIBLE: SOLVING A GAME WHEN RATIONALITY IS COMMON KNOWLEDGE
9. A gang controls the drug trade along North Avenue between Maryland Avenue and Barclay Street. The city grid is shown in FIGURE PR3.9a. The gang leader sets the price of the drug being sold and assigns two gang members to place themselves along North Avenue. He tells each of them that they’ll be paid 20% of the money they collect. The only decision that each of the drug dealers has is whether to locate at the corner of North Avenue and either Maryland Avenue, Charles Street, St. Paul Street, Calvert Street, or Barclay Street. The strategy set of each drug dealer is then composed of the latter five streets. Since the price is fixed by the leader and the gang members care only about money, each member wants to locate so as to maximize the number of units he sells.
Maryland Avenue
Charles Street
St. Paul Street
Calvert Street
Barclay Street
North Avenue
FIGURE PR3.9a
For simplicity, assume that the five streets are equidistant from each other. Drug customers live only along North Avenue and are evenly dis- tributed between Maryland Avenue and Barclay Street (so there are no customers who live to the left of Maryland Avenue or to the right of Barclay Street). Customers know that the two dealers set the same price, so they buy from the dealer that is closest to them. The total number of units sold on North Avenue is fixed. The only issue is whether a customer buys from drug dealer 1 or drug dealer 2. This means that a drug dealer will want to locate so as to maximize his share of customers. We can then think about a drug dealer’s payoff as being his customer share. FIGURE PR3.9b shows the customer shares or payoffs. Let us go through a few so that you understand how they were derived. For example, suppose dealer 1 locates at the corner of Maryland and North and dealer 2 parks his wares at the corner of Charles and North. All customers who live between Maryland and Charles buy from dealer 1, as he is the closest to them, while the customers who live to the right of St. Paul buy from dealer 2. Hence, dealer 1 gets 25% of the market and dealer 2 gets 75%. Thus, we see that ( , ) are the payoffs for strategy pair (Maryland, St. Paul). Now,34
1 4
FIGURE PR3.9b Drug Dealer’s Payoffs Based on Location
Dealer 1’s location
Dealer 2’s location
Maryland
Charles
St. Paul
Calvert
Barclay
Maryland Charles St. Paul Calvert Barclay
1 2
1 2
, 7 8
1 8
, 3 4
1 4
, 5 8
3 8
, 1 2
1 2
,
1 8
7 8
, 1 2
1 2
, 5 8
3 8
, 1 2
1 2
, 3 8
5 8
,
1 4
3 4
, 3 8
5 8
, 1 2
1 2
, 3 8
5 8
, 1 4
3 4
,
3 8
5 8
, 1 2
1 2
, 5 8
3 8
, 1 2
1 2
, 1 8
7 8
,
1 2
1 2
, 5 8
3 8
, 3 4
1 4
, 7 8
1 8
, 1 2
1 2
,
Exercises 83
suppose instead that dealer 2 locates at Charles and dealer 1 at Maryland. The customer who lies exactly between Maryland and Charles will be in- different as to whom to buy from. All those customers to his left will pre- fer the dealer at Maryland, and they make up one-eighth of the street. Thus, the payoffs are ( , ) for the strategy pair (Maryland, Charles). If two dealers locate at the same street corner, we’ll suppose that customers divide themselves equally between the two dealers, so the payoffs are ( , ). Using the iterative deletion of strictly dominated strategies, find where the drug dealers locate.
10. Two students are to take an exam, and the professor has instructed them that the student with the higher score will receive a grade of A and the one with the lower score will receive a B. Student 1’s score equals x1 � 1.5, where x1 is the amount of effort she invests in studying. (That is, I as- sume that the greater the effort, the higher is the score.) Student 2’s score equals x2, where x2 is the amount of effort she exerts. It is implicitly as- sumed that student 1 is the smarter of the two, in that, if the amount of effort is held fixed, student 1 has a higher score by an amount of 1.5. Assume that x1 and x2 can take any value in {0,1,2,3,4,5}. The payoff to student i is 10 � xi if she gets an A and 8 � xi if she gets a B, i � 1, 2. a. Derive the strategies that survive the iterative deletion of strictly dom-
inated strategies. b. Derive the strategies that survive the iterative deletion of weakly dom-
inated strategies. (The procedure works the same as the iterative dele- tion of strictly dominated strategies, except that you eliminate all weakly dominated strategies at each stage.)
11. Groucho Marx once said, “I’ll never join any club that would have me for a member.” Well, Groucho is not interested in joining your investment club, but Julie is. Your club has 10 members, and the procedure for ad- mitting a new member is simple: Each person receives a ballot that has two options: (1) admit Julie and (2) do not admit Julie. Each person can check one of those two options or abstain by not submitting a ballot. For Julie to be admitted, she must receive at least six votes in favor of ad- mittance. Letting m be the number of ballots submitted with option 1 checked, assume that your payoff function is
1 if m � 6, 7, 8, 9, 10
0 if m � 0, 1, 2, 3, 4, 5 .
a. Prove that checking option 1 (admit Julie) is not a dominant strategy. b. Prove that abstaining is a weakly dominated strategy. c. Now suppose you’re tired at the end of the day, so that it is costly for
you to attend the evening’s meeting to vote. By not showing up, you abstain from the vote. This is reflected in your payoff function having the form
1 if m � 6, 7, 8, 9, 10 and you abstained
if m � 6, 7, 8, 9, 10 and you voted
0 if m � 0, 1, 2, 3, 4, 5 and you abstained
if m � 0, 1, 2, 3, 4, 5 and you voted