Chapter 14: Static Games with Incomplete Information

Chapter 14 Static Games with Incomplete Information So far we have focused on games in which any piece of information that is known by any player is known by all the players (and indeed common knowledge). Such games are called the games of complete information. Informational concerns do not play any role in such games. In real life, players always have some private information that is not known by other parties. For example, we can hardly know other players’ preferences and beliefs as well as they do. Informational concerns play a central role in players’ decision making in such strategic environments. In the rest of the course, we will focus on such informational issues. We will consider cases in which a party may have some information that is not known by some other party. Such games are called games of incomplete information or asymmetric information. The informational asymmetries are modeled by Nature’s moves. Some players can distinguish certain moves of nature while some others cannot. Consider the following simple example, where a firm is contemplating the hiring of a worker, without knowing how able the worker is. Example 14.1 Consider the game in Figure 14.1. There are a Firm and a Worker. Worker can be of High ability, in which case he would like to Work when he is hired, or of Low ability, in which case he would rather Shirk. Firm would want to Hire the worker that will work but not the worker that will shirk. Worker knows his ability level. Firm does not know whether the worker is of high ability or low ability. Firm believes that the worker is of high ability with probability  and low ability with probability 1 − . Most 265 266 CHAPTER 14. STATIC GAMES WITH INCOMPLETE INFORMATION importantly, the firm knows that the worker knows his own ability level. To model this situation, we let Nature choose between High and Low, with probabilities  and 1 − , respectively. We then let the worker observe the choice of Nature, but we do not let the firm observe Nature’s choice. Work (1, 2) W Firm Hire Shirk (0, 1) High p Do not (0, 0) hire Nature Low 1-p Hire W Work Shirk Do not hire (1, 1) (-1, 2) (0, 0) Figure 14.1: A game on employment decisions with incomplete information A player’s private information is called his “type”. For instance, in the above example Worker has two types: High and Low. Since Firm does not have any private information, Firm has only one type. As in the above example, incomplete information is modeled via imperfect-information games where Nature chooses each player’s type and privately informs him. These games are called incomplete-information game or Bayesian game. 14.1 Bayesian Games Formally, a static game with incomplete information is as follows. First, Nature chooses some  = (1  2       ) ∈  , where each  ∈  is selected with probability  (). Here,  ∈  is the type of player  ∈  = {1 2     }. Then, each player observes 14.1. BAYESIAN GAMES 267 his own type, but not the others’. Finally, players simultaneously choose their actions, each player knowing his own type. We write  = (1  2      2 ) ∈  for any list of actions taken by all the players, where  ∈  is the action taken by player . The payoff of a player will now depend on players’ types and actions; we write  :  ×  → R for the utility function of  and  = (1       ). Such a static game with incomplete information is denoted by (    ). Such a game is called a Bayesian Games. One can write the game in the example above as a Bayesian game by setting •  = {  } •  = { }   = { } ; •  (  ) = ,  (  ) = 1 − ; •  = { },  = { }  • and the utility functions  and  are defined by the following tables, where the first entry is the payoff of the firm and the table on the left corresponds to  = (  )  =     =     1,2 0,1  1,1 -1,2  0,0 0,0  0,0 0,0 It is very important to note that players’ types may be “correlated”, meaning that a player “updates” his beliefs about the other players’ type when he learns his own type. Since he knows his type when he takes his action, he maximizes his expected utility with respect to the new beliefs he came to after “updating” his beliefs. We assume that he updates his beliefs using Bayes’ Rule. Bayes’ Rule Let  and  be two events, then probability that  occurs conditional on  occurring is  ( | ) =  ( ∩ )   () where  ( ∩ ) is the probability that  and  occur simultaneously and  (): the (unconditional) probability that  occurs. 268 CHAPTER 14. STATIC GAMES WITH INCOMPLETE INFORMATION In static games of incomplete information, the application of Bayes’ Rule will often be trivial, but a very good understanding of the Bayes’ Rule is necessary to follow the treatment of the dynamic games of incomplete information later. 0 Let  (0− | ) denote ’s belief that the types of all other players is 0− = (01  02   −1  0+1      0 ) given that his type is . [We may need to use Bayes’ Rule if types across players are ‘correlated’. But if they are independent, then life is simpler; players do not update their beliefs.] For example, for a two player Bayesian game, let 1 = 2 = { } and  ( ) =  ( ) =  ( ) = 13 and  ( ) = 0. This distribution is vividly tabulated as     13 13 0 13 Now, 1 (|) = Pr (1 = 2 = )  ( ) 13 = = = 12  ( ) +  ( ) 13 + 13 Pr (1 = ) Similarly, 1 (|) = 12 Pr (1 =  2 = )  ( ) 0 = = =0 1 (|) =  ( ) +  ( ) 0 + 13 Pr (1 = ) Pr (1 =  2 = )  ( ) 13 = = = 1 1 (|) =  ( ) +  ( ) 0 + 13 Pr (1 = ) 14.2 Bayesian Nash Equilibrium As usual, a strategy of a player determines which action he will take at each information set of his. Here, information sets are identified with types  ∈  . Hence, a strategy of a player  is a function  :  →   mapping his types to his actions. For instance, in the example above, Worker has four strategies: (Work,Work)–meaning that he will work regardless of whether he is of high or low ability, (Work, Shirk)–meaning that he will work if he is of high ability and shirk if he is of low ability, (Shirk, Work), and (Shirk, Shirk). 14.2. BAYESIAN NASH EQUILIBRIUM 269 When the probability of each type is positive according to , any Nash equilibrium of a Bayesian game is called Bayesian Nash equilibrium. In that case, in a Nash equilibrium, for each type  , player  plays a best reply to the others’ strategies given his beliefs about the other players’ types given  . If the probability of Nature choosing some  is zero, then any action at that type is possible according to an equilibrium (as his action at that type does not affect his expected payoff.) In a Bayesian Nash equilibrium, we assume that for each type  , player  plays a best reply to the others’ strategies given his beliefs about the other players’ types given  , regardless of whether the probability of that type is positive. Formally, a strategy profile ∗ = (∗1   ∗ ) is a Bayesian Nash Equilibrium in an -person static game of incomplete information if and only if for each player  and type  ∈   ∗ (1 ) ∈ arg max  X  (∗ ( )     ∗ ( )) ×  (0− | ) where  is the utility of player  and  denotes action. That is, for each player  each possible type, the action chosen is optimal given the conditional beliefs of that type against the optimal strategies of all other players. Notice that the utility function  of player  depends both players’ actions and types.1 Notice also that a Bayesian Nash equilibrium is a Nash equilibrium of a Bayesian game with the additional property that each type plays a best reply.2 For example, for  = 34, consider the Nash equilibrium of the game between the firm and the worker in which the firm hires and worker works if and only if Nature chooses high. We can formally write this strategy profile as ∗ = (∗  ∗ ) with ∗ ( ) =  ∗ () =  ∗ () =  We check that this is a Bayesian Nash equilibrium as follows. First consider the firm. 1 Utility function  does not depend the whole of strategies 1 ,. . . ,  , but the expected value of  possibly does. 2 This property is necessarily satisfied in any Nash equilibrium if all types occur with positive probability. 270 CHAPTER 14. STATIC GAMES WITH INCOMPLETE INFORMATION At his only type  , his beliefs about the other types are  (| ) = 34 and  (| ) = 14 His expected utility from the action "hire" is  [ ( ∗ ) | ] =  ( ∗ ()  )  (| ) +  ( ∗ ()  )  (| ) =  (  )  (| ) +  (  )  (| ) 3 1 1 = 1 · + (−1) · =  4 4 2 His expected payoff from action "dont" is ∗ ()  )  (| ) +  ( ∗ ()  )  (| )  [ ( ∗ ) | ] =  (  =  (  )  (| ) +  (  )  (| ) 3 1 = 0 · + 0 · = 0 4 4 ∗ ) | ],  is a best response. Now consider, Since  [ ( ∗ ) | ] ≥  [ (  the worker. He has two types. We need to check whether he play a best response for each of these types. Consider  =  type. Of course,  ( |) = 1. Hence, his utility from "work" is  [ (∗  ) |] =  (  ) = 2 His utility from "shirk" is  [ (∗  ) |] =  (  ) = 1 Clearly, 2  1, and "work" is the best response to ∗ for type . For type  = , we check that his utility from "shirk",  [ (∗  ) |] =  (  ) = 2 is greater than his utility from "work",  [ (∗  ) |] =  (  ) = 1 Hence, the type  =  also plays a best response. Therefore, we have checked that ∗ is a Bayesian Nash equilibrium. Exercise 14.1 Formally, check that firm not hiring and worker shirking for each type is also a Bayesian Nash equilibrium. 14.3. EXAMPLE 14.3 271 Example Suppose that the payoffs are given by the table      1 2  −1   0 where  ∈ {0 2} is known by Player 1,  ∈ {1 3} is known by Player 2, and all pairs of ( ) have probability of 14. Formally, the Bayesian game is defined as •  = {1 2} • 1 = {0 2}, 2 = {1 3} •  (0 1) =  (0 3) =  (2 1) =  (2 3) = 14 • 1 = {  }, 2 = { }, and • 1 and 2 are defined by the table above, e.g., 1 (   ) = 1 (   ) = , 1 (   ) = 1, and 1 (   ) = −1. I next compute a Bayesian Nash equilibrium ∗ of this game. To do that, one needs to determine ∗1 (0) ∈ {  }, 1∗ (2) ∈ {  }, 2∗ (1) ∈ { }, and 2∗ (3) ∈ { }– four actions in total. First observe that when  = 0, action  strictly dominates action  , i.e., 1 ( 2   = 0 )  1 ( 2   = 0 ) for all actions 2 ∈ 2 and types  ∈ {1 3} of Player 2. Hence, it must be that ∗1 (0) =  Similarly, when  = 3, action  strictly dominates action , and hence ∗2 (3) =  Now consider the type  = 2 of Player 1. Since his payoff does not depend on , observe that his payoff from  is 1 +  , where  is the probability that Player 2 plays 272 CHAPTER 14. STATIC GAMES WITH INCOMPLETE INFORMATION . His payoff from  is 2 (1 −  ) −  , which is equal to 2 − 3 . Hence, for  = 2,  is a best response if 1 +  ≥ 2 − 3  i.e.,  ≥ 14 When   14,  is the only best response. Note however that type  must play , and the probability of that type is 1/2. Therefore,  ≥ 12  14 Since ∗1 (2) is a best response for  = 2, it follows that ∗1 (2) =  Now consider  = 1. Given ∗1 , Player 2 knows that Player 1 plays  (regardless of his type). Hence, the payoff of  = 1 is  = 1 when he plays  and 2 when he plays . Therefore, ∗2 (1) =  To check that ∗ is indeed a Bayesian Nash equilibrium, one checks that each type plays a best response. Exercise 14.2 Verify that ∗ is indeed a Bayesian Nash equilibrium. Following the analysis above, show that there is no other Bayesian Nash equilibrium. 14.4 Exercises with Solutions 1. [Final, 2006] Consider a two-player game in which the payoffs, which depend on , and actions are as in the following table: =0   =1   1 −1 −1 1 −1 1 1 −1    1 1  −1 1 −1 −1 1 −1 where Pr ( = 0) = Pr ( = 1) = 12. Only Player 2 knows whether  = 0 or  = 1. 14.4. EXERCISES WITH SOLUTIONS 273 (a) Write this as a Bayesian game. Answer: A Bayesian game can be written as a list  = ( 1        1         1       ) In this problem, • the set of players:  = {1 2}; • the set of actions for each player: 1 = { } and 2 = { }; • the set of types for each player: 1 = {1 } (it is a singleton), 2 = {0 1} (possible values of ); • beliefs are given by  (1  0) =  (1  1) = 12; (one can alternatively defined the conditional beliefs of types, which does not make a difference in this problem); • utility functions 1 (1  2  1  2 ) and 2 (1  2  1  2 ) are given by the matrices above. (b) Find a Bayesian Nash equilibrium of this game. Answer: I will find a BNE in pure strategies. Note that a pure strategy for Player 1 is an action 1 (1 ) ∈ 1 , and a pure strategy for Player 2 is a pair (2 (0)  2 (1)) ∈ 2 × 2 , assigning an action for each type of that player. To find an equilibrium, I guess and eventually verify that there exists a BNE in which Player 1’s strategy is 1 (1 ) = . Player 2’s best response to this strategy is 2 (0) =  and 2 (1) = . Now we need to verify that 1 (1 ) =  is a best response to the strategy of Player 2 that 2 (0) =  and 2 (1) = . To do that, compute that the expected payoff of Player 1 from  is 1 () = 1 ( 2 (0)  2 = 0)  (2 = 0) + 1 ( 2 (1)  2 = 1)  (2 = 1) 1 1 = 1 (  2 = 0) · + 1 (  2 = 1) · 2 2 1 1 = −1 · + 1 · = 0 2 2 and the expected utility from  is 1 () = 1 (  2 = 0) · 1 1 + 1 (  2 = 1) · = 0 2 2 274 CHAPTER 14. STATIC GAMES WITH INCOMPLETE INFORMATION Hence, 1 ( ) ≥ 1 (), showing that  is a best response. Therefore, the strategy profile (1 (1 ) = ; 2 (0) =  2 (1) = ) is a Bayesian Nash equilibrium. 2. [Midterm 2, 2001] This question is about a thief and a policeman. The thief has stolen an object. He can either hide the object INSIDE his car on in the TRUNK. The policeman stops the thief. He can either check INSIDE the car or the TRUNK, but not both. (He cannot let the thief go without checking, either.) If the policeman checks the place where the thief hides the object, he catches the thief, in which case the thief gets −1 and the police gets 1; otherwise, he cannot catch the thief, and the thief gets 1, the police gets −1. (a) Compute all the Nash equilibria. Solution: This is a matching-pennies game. There is a unique Nash equilibrium, in which Thief hides the object INSIDE or the TRUNK with equal probabilities, and the Policeman checks INSIDE or the TRUNK with equal probabilities. (b) Now imagine that there are 100 thieves and 100 policemen, indexed by  = 1     100, and  = 1     100. In addition to their payoffs above, each thief  gets extra payoff  form hiding the object in the TRUNK, and each policeman  gets extra payoff  from checking the TRUNK where 1  2  · · ·  50  0  51  · · ·  100  1  2  · · ·  50  0  51  · · ·  100  Policemen cannot distinguish the thieves from each other, nor can the thieves distinguish the policemen from each other. Each thief has stolen an object, hiding it either in the TRUNK or INSIDE the car. Then, each of them is randomly matched to a policeman. Each matching is equally likely. Again, a policeman can either check INSIDE the car or the TRUNK, but not both. Write this game as a Bayesian game with two players, a thief and a policemen. Compute a pure-strategy Bayesian Nash equilibrium of this game. Solution: The type space is {1     100} × {1     100} where each pair ( ) is equally likely. The payoff of thief is his payoff from part (a) plus  , 14.4. EXERCISES WITH SOLUTIONS 275 depending on his own type. The payoff of policeman is his payoff from part (a) plus  , depending on his type. A Bayesian Nash equilibrium: A thief of type  hides the object in INSIDE if   0 TRUNK if   0; a policeman of type  checks INSIDE if   0 TRUNK if   0 This is a Bayesian Nash equilibrium, because, from the thief’s point of view the policeman is equally likely to check TRUNK or INSIDE the car, hence it is the best response for him to hide in the trunk iff the extra benefit from hiding in the trunk is positive. Similar for the policemen. Remark 14.1 Note that from the point of view of an outside observer, the mixed strategy equilibrium of complete information game in part (a) and the pure strategy Bayesian Nash equilibrium of the Bayesian game in part (b) are equivalent: in both cases, the thief hides either inside the car or in trunk and policeman checks inside or trunk, where the probability of each pair is 14. Moreover, in both games, the players face the same uncertainty about the action of the other player, assigning equal probabilities on both actions. The rationale for those beliefs are somewhat different however. In the complete information game, a player thinks that the actions of the other player are equally likely because he does not know the strategy of the other player, assigning equal probabilities on those strategies. In the Bayesian game, however, he does know what the other player’s strategy is–as a function of his type. Yet, he does not know which action the other player takes as he does not know the other player’s type. Therefore, the uncertainty about the strategies in complete information game is replaced with uncertainty about the others’ types. One can always convert a mixed strategy Nash equilibrium to a pure strategy Bayesian Nash equilibrium by introducing very small uncertainty about the players’ payoffs. (This fact is known as Harsanyi’s Purification Theorem.) Hence, a mixed strategy Nash equilibrium can be interpreted as coming from slight variations in players’ payoffs. 276 CHAPTER 14. STATIC GAMES WITH INCOMPLETE INFORMATION 14.5 Exercises 1. [Midterm 2, 2011] Consider a two-player game with the payoff matrix    1    0 − 0 1  where  ∈ {−2 2} is privately known by Player 1, and Pr ( = −2) = 08. (There is no other private information.) (a) Write this formally as a Bayesian game. (b) Find a Bayesian Nash equilibrium of this game. Verify that the strategy profile you identified is indeed a Bayesian Nash equilibrium. 2. [Final 2010] Consider a two player Bayesian game with the following payoff matrix    (1 )   (2 )   (1 ) − 10  (2 ) + 10     (1 ) + 10  (2 ) − 10  (1 ) − 10  (2 ) + 10  (1 )   (2 )  (1 ) + 10  (2 ) − 10  (1 ) − 10  (2 ) + 10  (1 ) + 10  (2 ) − 10  (1 )   (2 ) where  ∈ {0 1 2} is privately known by player  and  (0) = 1,  (1) =  (2) = 0,  (1) = 1,  (0) =  (2) = 0,  (2) = 1, and  (0) =  (1) = 0. The functions , , and  are known and each pair (1  2 ) has probability 1/9. (a) Write this as a Bayesian game. (b) Find a Bayesian Nash equilibrium of this game. Verify that the strategy profile you identified is indeed a Bayesian Nash equilibrium. 3. [Midterm 2 Make up, 2002] Consider the incomplete information game with payoff matrix O O 2 + 1  1 B 0 0 B 1  2 1 2 + 2 where 1 and 2 are the private information of players 1 and 2, respectively, and are identically and independently distributed with uniform distribution on [−13 23]. 14.5. EXERCISES 277 (Here  is the type of player .) Find a Bayesian Nash equilibrium of this game in which for each action (O or B) there is a realization of  at which player  plays that action. 4. [Homework 4, 2004] Consider a two player game with payoff matrix    2 2 0    0 1 1 where  ∈ {0 3} is a parameter known by Player 1. Player 2 believes that  = 0 with probability 1/2 and  = 3 with probability 1/2. Everything above is common knowledge. (a) Write this game formally as a Bayesian game. (b) Compute two Bayesian Nash equilibria of this game.