Chapter 4: Dominance

Chapter 4 Dominance The previous lectures focused on how to formally describe a strategic situation. We now start analyzing strategic situations in order to find which outcomes are more reasonable and likely to realize. In order to do that, we consider certain sets of assumptions about the players’ beliefs and discover their implications on what they would play. Such analyses will lead to solution concepts, which yield a set of strategy profiles1 . These are the strategy profiles deemed to be possible by the solution concept. This lecture is devoted to two solution concepts: dominant strategy equilibrium and rationalizability. These solution concepts are based on the idea that a rational player does not play a strategy that is dominated by another strategy. 4.1 Rationality and Dominance A player is said to be rational if and only if he maximizes the expected value of his payoffs (given his beliefs about the other players’ strategies). For example, consider the following game. 1\2  1   2 0  0 10  −1 −6 −1 1 0 0 2 0 A strategy profile is a list of strategies, prescribing a strategy for each player. 51 (4.1) 52 CHAPTER 4. DOMINANCE Consider Player 1. He is contemplating about whether to play  , or , or . A quick inspection of his payoffs reveals that his best play depends on what he thinks the other player does. Let’s then write  for the probability he assigns to  (as Player 2’s play). Then, his expected payoffs from playing  , , and  are  = 2 − (1 − ) = 3 − 1  = 0  = − + 2(1 − ) = 2 − 3 respectively. These values as a function of  are plotted in Figure 4.1. As it is clear from the graph,  is the largest when   12, and  is the largest when   12. At  = 12,  =   0. Hence, if player 1 is rational, then he plays  when   12,  when   12, and  or  when  = 12. Notice that, if Player 1 is rational, then he never plays –no matter what he believes about the strategy of Player 2. Therefore, if we assume that Player 1 is rational (and that the game is as it is described above), then we can conclude that Player 1 does not play . This is because  is a strictly dominated strategy, a concept that we define now. U 2 UT UB UM 0 -1 0 p 1 Figure 4.1: Expected payoffs in (4.1) as a function of probability of . Towards describing this idea more generally and formally, let us use the notation − 4.1. RATIONALITY AND DOMINANCE 53 to mean the list of strategies  played by all the players  other than , i.e., − = (1  −1  +1   ) Definition 4.1 A strategy ∗ strictly dominates  if and only if  (∗  − )   (  − ) ∀− ∈ −  That is, no matter what the other players play, playing ∗ is strictly better than playing  for player . In that case, if  is rational, he would never play the strictly dominated strategy  . That is, there is no belief under which he would play  , for ∗ would always yield a higher expected payoff than  no matter what player  believes about the other players.2 A mixed strategy  dominates a strategy  in a similar way:  strictly dominates  if and only if  (1 ) (1  − ) +   (2 ) (2  − ) + · · ·   ( ) (  − )   (  − ) ∀− ∈ −  Notice that neither of the pure strategies  , , and  dominates any strategy. Nevertheless,  is dominated by the mixed strategy that  1 that puts probability 1/2 on each of  and . For each , the payoff from 1 is 1 1 1 1 = (3 − 1) + (2 − 3) =  2 2 2 which is larger than 0, the payoff from . Recall that  is a best response to any . This is indeed a general result. Towards stating the result, I introduce a couple of basic concepts. Write − = Y  6= for the set of other players’ strategies, and define a belief of player  as a probability distribution  − on − . Definition 4.2 For any player , a strategy  is a best response to − if and only if  (  − ) ≥  (0  − ) 2 As a simple exercise, prove this statement. ∀0 ∈  54 CHAPTER 4. DOMINANCE A strategy  is said to be a best response to a belief  − if and only if playing  yields the highest expected payoff under  − , i.e., X − ∈−  (  − )  − (− ) ≥ X − ∈−  (0  − )  − (− )  ∀0 ∈   The concept of a best response is one of the main concepts in game theory, used throughout the course. It is important to understand the definition well and be able to compute the best response in relatively simple games, as those covered in this class. A rational player can play a strategy under a belief only if it is a best response to that belief. Theorem 4.1 A strategy  is a best response to some belief if and only if  is not dominated.3 Therefore, playing strategy  is never rational if and only if  is dominated by a (mixed or pure) strategy. To sum up: if one assumes that players are rational (and that the game is as described), then one can conclude that no player plays a strategy that is strictly dominated (by some mixed or pure strategy), and this is all one can conclude. Although there are few strictly dominated strategies–and thus one can conclude little from the assumption that players are rational–in general, there are interesting games in which this weak assumption can lead to counterintuitive conclusions. For example, consider the well-known Prisoners’ Dilemma game, introduced in Chapter 1: 1 \2 Cooperate Defect Cooperate 5 5 0 6 Defect 6 0 1 1 Clearly, Cooperate is strictly dominated by Defect, and hence we expect each player to play Defect, assuming that the game is as described and players are rational. Some found the conclusion counterintuitive because if both players play Cooperate, the outcome would be much better for both players. 3 If you like mathematical challenges try to prove this statement. 4.2. DOMINANT-STRATEGY EQUILIBRIUM 4.2 55 Dominant-strategy equilibrium This section introduces two concepts of dominance, one is stronger than the other. It the uses the weak dominance to define dominant-strategy equilibrium. Definition 4.3 A strategy ∗ is a strictly dominant strategy for player  if and only if ∗ strictly dominates all the other strategies of player . For example, in the prisoners’ dilemma game, Defect strictly dominates the only other strategy of Cooperate. Hence, Defect is a strictly dominant strategy. If  is rational and has a strictly dominant strategy ∗ , then he will not play any other strategy. In that case, it is reasonable to expect that he will play ∗ . The problem is that there are only few interesting strategic situations in which players have a strictly dominant strategies. Such situations can be analyzed as individual decision problems. A slightly weaker form of dominance is more common, especially in dynamic games (which we will analyze in the future) and in situation that arise in structured environments, such as under suitably designed trading mechanisms as in auctions. This weaker form is called weak dominance: Definition 4.4 A strategy ∗ weakly dominates  if and only if  (∗  − ) ≥  (  − ) ∀− ∈ − and  (∗  − )   (  − ) for some − ∈ − . That is, no matter what the other players play, playing ∗ is at least as good as playing  , and there are some contingencies in which playing ∗ is strictly better than  . In that case, if rational,  would play  only if he believes that these contingencies will never occur. If he is cautious in the sense that he assigns some positive probability for each contingency, then he will not play  . This weak dominance is used in the definition of a dominant strategy: Definition 4.5 A strategy ∗ of a player  is a (weakly) dominant strategy if and only if ∗ weakly dominates all the other strategies of player . When there is a weakly dominant strategy, if the player is rational and cautious, then he will play the dominant strategy. 56 CHAPTER 4. DOMINANCE Example: 1\2 work hard shirk hire 2 2 1 3 don’t hire 0 0 0 0 (4.2) In this game, player 1 (firm) has a strictly dominant strategy: “hire.” Player 2 has only a weakly dominated strategy. If players are rational, and in addition Player 2 is cautious, then Player 1 hires and Player 2 shirks. When every player has a dominant strategy, one can make a strong prediction about the outcome. This case yields the first solution concept in the course. Definition 4.6 A strategy profile ∗ = (∗1  ∗2  ∗ ) is a dominant strategy equilibrium, if and only if for each player , ∗ is a weakly dominant strategy. As an example consider the Prisoner’s Dilemma. 1 \2 Cooperate Defect Cooperate 5 5 0 6 Defect 6 0 1 1 Defect is a strictly dominant strategy for both players, therefore (Defect, Defect) is a dominant strategy equilibrium. Note that dominant strategy equilibrium only requires weak dominance. For example, (hire, shirk) is a dominant strategy equilibrium in game (4.2). When it exists, the dominant strategy equilibrium has an obvious attraction. In that case, rational cautious players will play the dominant strategy equilibrium. Unfortunately, it does not exist in general. For example, consider the Battle of the Sexes game: opera football opera 3 1 0 0 football 0 0 1 3 Clearly, no player has a dominant strategy: opera is a strict best reply to opera and football is a strict best reply to football. Therefore, there is no dominant strategy equilibrium. 4.3. EXAMPLE: SECOND-PRICE AUCTION 4.3 57 Example: second-price auction As already mentioned, under suitably designed trading mechanisms, it is possible to have a dominant strategy equilibrium. Such mechanisms are desirable for they give the economic agents strong incentive to play a particular strategy (which is presumably preferred by the market designer) and eliminate the agents’ uncertainty about what the other players play, as it becomes irrelevant for the agent what the other players are doing. The most famous trading mechanism with dominant-strategy equilibrium is the second-price auction. There is an object to be sold through an auction. There are two buyers. The value of the object for any buyer  is  , which is known by the buyer . Each buyer  submits a bid  in a sealed envelope, simultaneously. Then, the envelopes are opened, and the buyer ∗ who submits the highest bid ∗ = max {1  2 } gets the object and pays the second highest bid (which is  with  6= ∗ ). (If two or more buyers submit the highest bid, one of them is selected by a coin toss.) Formally the game is defined by the player set  = {1 2}, the strategies  , and the payoffs where  = 6 . ⎧ ⎪ if    ⎪ ⎨  −   (1  2 ) = ( −  ) 2 if  =  ⎪ ⎪ ⎩ 0 if    In this game, bidding his true valuation  is a dominant strategy for each player . To see this, consider the strategy of bidding some other value 0 6=  . We want to show that 0 is weakly dominated by bidding  . Consider the case 0   . If the other player bids some   0 , player  would get  −  under both strategies 0 and  . If the other player bids some  ≥  , player  would get 0 under both strategies 0 and  . But if  = 0 , bidding  yields  −   0, while 0 yields only ( −  ) 2. Likewise, if 0     , bidding  yields  −   0, while 0 yields only 0. Therefore, bidding  weakly dominates 0 . The case 0   is similar, except for when 0     , bidding  yields 0, while 0 yields negative payoff  −   0. Therefore, bidding  is dominant strategy. Since this is true for each player , (1  2 ) is a dominant-strategy equilibrium. 58 CHAPTER 4. DOMINANCE Exercise 4.1 Extend this to the -buyer case. 4.4 Exercises with Solutions 1. [Homework 1, 2011] There are  students in a class. Simultaneously, each student  chooses an effort level  incurring cost 2 for some   0. The student  receives an increase  in his grade from his own effort, but this also raises the curve and decreases the grade of every other student by  for some   0. The resulting utility of player  is  (1       ) =  −  X 6=  − 2  All of the above is common knowledge. (a) Write this game in normal form. Solution: The set of players is  = {1     }. For each  ∈ ,  = R, and  : R → R is given in the question. (b) Is there a dominant strategy equilibrium? If so, compute the dominant strategy equilibrium. Solution: For any − = (1      −1  +1       ), the best response can be found by  = 1 − 2 = 0  The solution to this equation is the unique best response: ∗ = 1 2 Since ∗ is best response to every strategy, ∗ dominates any other strategy  :  (∗  − )   (  − ) (∀− )  ¡1 ¢ 1      2 is the dominant-strategy equilibrium. Therefore, 2 (c) Compute the (1       ) vector that maximizes the sum 1 (1       ) + · · ·+ (1       ) of grades. Comparing your answers to (b) and (c), briefly discuss your findings. 4.4. EXERCISES WITH SOLUTIONS 59 Solution: The total utility is à ! X X X X =  −   −  − 2 = (1 − ( − 1) ) 2   6=   The first order condition is  = 1 − ( − 1)  − 2 = 0  Therefore,  is maximized at µ ¶ 1 − ( − 1)  1 − ( − 1)    2 2 Note that the the dominant-strategy equilibrium corresponds to the case  = 0, ignoring the negative impact on the other students’ grades. The dominant strategy equilibrium always yield a higher effort than the socially optimal level that maximizes . This is a version of the commons problem, a generalization of the Prisoners’ Dilemma game. In commons problem, the players’ efforts have positive impact on the others payoffs, as they produce some public good. In that problem, equilibrium effort is lower than the optimal one. Here, the impact is negative, and students work harder than socially optimal. (Professors want them to work even harder!) 2. [Homework 1, 2010] Consider an auction in which  identical objects are sold to    bidders. Each bidder  needs only one object and has a valuation  for the object. In the auction, simultaneously, every bidder  bids  . The highest  bidders win. Each winner gets one object and pays the  + 1 highest bidder (i.e., the price  is the highest bid among the bidders who do not get an object). (The ties are broken by a coin toss.) Each of the losing bidders gets a gift of value  for their participation. (The winners do not get a gift.) Show that the game has a dominant strategy equilibrium, and compute the equilibrium. Solution: The dominant strategy equilibrium is (1 −  2 −       − ). To show that ∗ =  −  is dominant strategy, consider any  6= ∗ . Consider the case,   ∗ . Towards showing that ∗ weakly dominates  , take any bid − by the others. Relabeling the players, one can take  =  and 1 ≥ 2 ≥ · · · ≥ −1 . 60 CHAPTER 4. DOMINANCE If    , then under both bids  and ∗ ,  wins the object and pays price  =  , enjoying the payoff level of  − . If    , then under both bids  and ∗ ,  loses the object and gets . Consider the case,     ∗ . In that case, under ∗ ,  wins and gets  −  . Under  , he gets . But, since   ∗ =  − , bid ∗ yields a higher payoff:  −   . The cases of ties and   ∗ are dealt similarly. 3. For the following strategy space and utility pairs, check if best response exists for player 1, and compute it when it exists. Note: In general a best response exists if 1 is compact (i.e. closed and bounded for all practical purposes) and  is continuous in  . In particular, it exists whenever 1 is finite. Fortunately it may exists even if the above conditions fail. (a) 1 = [0 1]; 1 (1 ) = 1 if 1  1 and 1 (1) = 0. Solution: Clearly, there is no best response. Plot a graph for illustration. (Continuity fails here.) (b) 1 = 2 = [0 ∞); 1 (1 ) = 1 2 . Solution: Everything is a best response when 2 = 0, and nothing is a best response when 2 6= 0. Compactness fails. This also shows that there can be more than one best response. (c) Partnership Game: 1 = 2 = [0 ∞); 1 (1 ) = 1 2 − 21 where   0. Solution: Best response exists although 1 is not compact. Take the partial derivative with respect to 1 and set it equal to zero in order to obtain the "first-order condition" for maximum: 1 = 2 − 21 = 0 1 That is, the best response is 1 = 2 2 One does not need to check the second order condition because 1 is concave. (d) First-Price Auction: 1 = 2 = [0 ∞); ⎧ ⎪ if 1  2 ⎪ ⎨  − 1 1 (1  2 ) = ( − 1 ) 2 if 1 = 2 ⎪ ⎪ ⎩ 0 otherwise 4.5. EXERCISES 61 where   0. Solution: Everything is a best response when 2 = ; any 1  2 is a best response when 2  , and nothing is a best response when 2  . Continuity fails. (e) Price Competition: 1 = 2 = [0 ∞); ⎧ ⎪ if 1  2 ⎪ ⎨ (1 − 1 ) 1 1 (1  2 ) = (1 − 1 ) 1 2 if 1 = 2 ⎪ ⎪ ⎩ 0 otherwise. Solution: Everything is a best response when 2 = 0, and nothing is a best response when 2 = 6 0. Continuity fails. (f) Quantity Competition: 1 = 2 = [0 ∞); 1 (1  2 ) = (1 − 1 − 2 ) 1 − 1 . Solution: There is a unique best response. As in part (c), the first-order condition is 1 = 1 − 21 − 2 −  = 0 1 yielding 1 = 4.5 1 − 2 −   2 Exercises 1. Show that there cannot be a dominant strategy in mixed strategies. 2. [Homework 1, 2007] The Federal Government is to decide whether to construct a road between the towns Arlington and Belmont. The values of the road for Arlington and Belmont are  ≥ 0 and  ≥ 0, respectively. The cost of constructing the road is   0. The Federal Government wants to construct the road if and only if  +  ≥ . The values  and  are known by the towns, but not by the government;  is known by everybody. To learn these values, the government asks each town to submit the value of the road for the town. Given the submitted valuations  and  , which need to be non-negative, the government constructs the bridge if and only if  +  ≥  and tax Arlington and Belmont  (   ) 62 CHAPTER 4. DOMINANCE and  (   ), respectively, where  (   ) =  (   ) = ( (  −  if  +  ≥  and    0 otherwise  −  if  +  ≥  and    0 otherwise. Find the dominant strategy equilibrium; show that the strategies that you identify are indeed dominant. 3. [Homework 1, 2006] There are  players and an object. The game is as follows: • First, for each player , Nature chooses a number  from {0 1 2     99}, where each number is equally likely, and reveals  to player  and nobody else. ( is the value of the object for player .) • Then, each player  simultaneously bids a number  . • The player who bids the highest number wins the object and pays  where  is the highest number bid by a player other than the winner. (If two or more players bid the highest bid, the winner is determined by a coin toss among the highest bidders.) The payoff of player  is ( −  ) if he is the winner and 0 otherwise. (a) Write this game in normal form. That is, determine the set of strategies for each player, and the payoff of each player for each strategy profile. (b) Show that there is a dominant strategy equilibrium. State the equilibrium. 4. [Homework 1, 2010] Alice, Bob, and Caroline are moving into a 3-bedroom apartment (with rooms, named 1, 2, and 3). In this problem we want to help them to select their rooms. Each roommate has a strict preference over the rooms. The roommates simultaneously submit their preferences in an envelope, and then the rooms are allocated according to one of the following mechanisms. For each mechanism, check whether submitting the true preferences is a dominant strategy for each roommate. 4.5. EXERCISES 63 Mechanism 1 First, Alice gets her top ranked room. Then, Bob gets his top ranked room among the remaining two rooms. Finally, Caroline gets the remaining room. Mechanism 2 Alice, Bob, and Caroline have priority scores 03, 0, and −03, respectively; the priority score of a roommate  is denoted by  . For each roommate  and room , let rank  be 3 if  ranks  highest, 2 if  ranks  second highest, and 1 if  ranks  lowest. Write  =  +  for the aggregate score. In the mechanism, Room 1 is given to the roommate  with the highest aggregate score 1 . Then, among the remaining two, the one with the highest aggregate score 0 2 gets Room 2, and the other gets Room 3.