14.12 Game Theory - Midterm 1 with Solutions

14.12 Game Theory — Midterm I 10/19/2010 Prof. Muhamet Yildiz Instructions. This is an open book exam; you can use any written material. You have one hour and 20 minutes. Each question is 25 points. Good luck! 1. Consider the following game. (a) Using backward induction find an equilibrium. Answer: At the last node, Player 1 chooses ; at the right node, Player 2 then chooses . At the left node, she chooses . Hence, at the beginning, Player 1 chooses . The equilibrium is ( ). (b) Write the game in normal form. Answer: The game in normal form is 1\2      2,1 2,1 2,1 2,1    2,1 1,2 1,2 2,1 1,2 1,2 1,0 2,1 1,0 0,1 2,1 0,1 2. Compute a Nash equilibrium of the following game. (This is a version of Rock-ScissorsPaper with preference for Paper.) R S P R 0 0 2 −2 −2 3 S −2 2 0 0 2 −1 P 3 1 −1 2 1 1 Answer: (Because of a typo, the question became asymmetric, making the answer longer. We gave nearly full credit to the students who thought the game was symmetric.) 1 This game has a unique Nash equilibrium, which is in mixed strategies. Write  ,  , and  for the probabilities with which player  plays strategies R, S, and P, respectively. Of course,  +  +  = 1 (1) Now, (2  2  2 ) must make Player 1 indifferent between his strategies. Indifference between R and S yields 2 (2 − 2 ) = 2 (2 − 2 ), i.e., 22 = 2 + 2  Since 2 + 2 = 1 − 2 by (1), this yields 2 = 13 On the other hand, the indifference between S and P yields 2 (2 − 2 ) = 1+2 (2 − 2 ). Substituting 2 = 13, we obtain 42 − 22 = −13. Together with 2 + 2 = 23, this yields 2 = 16 2 = 12 Similarly, indifference between R and S for player 2 yields 2 (1 − 1 ) = 21 − 1 , i.e., 31 = 2 (1 + 1 ). Since 1 + 1 = 1 − 1 , this yields 1 = 25 The indifference between S and P yields 2 (1 − 1 ) = 1+2 (1 − 1 ), yielding 41 −21 = −15. Together with 1 + 1 = 35, this yields 1 = 16 1 = 1330 3. Ann and Bob own a small business. Ann provides the capital, denoted by  ∈ [0 1] and Bob provides√the labor, denoted by  ∈ [0 1]. They equally share the revenue, which is given by . The cost of capital for Ann is 4, and the √ cost of Labor for Bob is 2 4. In summary, the utility function of Ann and Bob are 12  − 4 and √ 1  − 2 4. Note that Ann can choose any  in [0 1]; Bob can choose any  in 2 [0 1], and everything is common knowledge. (a) Compute the set of Nash equilibria in pure strategies. Answer: The best response function of Ann is   () =  The best response function of Bob is  () = p 3 4 (2) (3) The Nash equilibria are the intersections p pof the best-response functions, i.e.,  =  and  = 3 4. That is,  =  = 3 4. Clearly,  =  = 0 is a solution. The other solution is given by  2 = 14, i.e.,  =  = 12. The Nash equilibria are (0 0) and (12 12). 2 (b) Compute the set of rationalizable strategies. Answer: Graph of the best response functions will be useful: Let’s apply iterated dominance. Round 1 : Since   = , each  ∈ [0 1] is a best response to some p = ∈ 3  [0 1], and no  is eliminated. On the other hand, every    (1) = √ 14 is p 3 ≡ 12  − strictly dominated ³ p by´ 14. Indeed, for any  ∈ [0 1],  ( ) p 2 4    3 14 because  ( 0 ) is decreasing in 0 on [ 3 4 ∞) and p    (1) ≥ 3 4. Hence, all such strategies are eliminated for Bob. All the other strategies are a best response to some  as in the figure, hence they are not eliminated. The resulting set is [0 1 ] for Ann and [0 1 ] for Bob where p 1 = 1 and 1 = 3 14 Round 2 : In this round nothing is eliminated for Bob (because nothing was eliminated for Ann in the previous round). For Ann all the strategies   1 are eliminated because they are now strictly dominated by 1 as in the previous round. The resulting set is [0 2 ] for Ann and [0 2 ] for Bob where 2 = 1 and 2 = 1  Towards a mathematical induction, assume that at the end of Round 2, the resulting set is [0 2 ] for Ann and [0 2 ] for Bob where 2 = 2 . Now, Round 2 + 1: Since   =  and 2 = 2 , each  ∈ [0 2 ] is a best response to some  = p ∈ [0 2 ], and no  is eliminated. p On the other hand, every    (2 ) = 3 2 4 is strictly dominated by 3 2 4, as in Round 1. All the other strategies are a best response to some , hence they are not eliminated. The resulting set is [0 2+1 ] for Ann and [0 2+1 ] for Bob where p 2+1 = 2 and 2+1 = 3 2 4 Round 2 + 2: In this round nothing is eliminated for Bob (because nothing was eliminated for Ann in the previous round). For Ann all the strategies   2+1 3 are eliminated because they are now strictly dominated by 2+1 . The resulting set is [0 2+2 ] for Ann and [0 2+2 ] for Bob where p 2+2 = 2+1 and 2+2 = 2+1 = 3 2 4 Combining the two equations we obtain 2+2 = 2+2 = p 3 2 4 With the initial condition 0 = 0 = 1, this decreasing sequence converges to (∞  ∞ ) where ∞ = ∞ is the largest solution to p ∞ = 3 ∞ 4 That is, ∞ = ∞ = 12 The rationalizable strategies are [0 12] and [0 12] for Ann and Bob, respectively. 4. In a family, there are 3 sisters, named Alice, Beatrice, and Caroline. They have a big piece of cake, whose size we normalize to 1. Alice divides the cake into 3 pieces, which can be of different sizes. Next, Beatrice picks one of the pieces for herself. Next, Caroline picks one of the remaining two pieces. Alice picks the last piece. Each sister’s payoff is the size of the cake she gets. (a) Using backward induction, compute an equilibrium of this game. Answer: Given the remaining two pieces, Caroline chooses the larger one, leaving the smaller one to Alice. When Beatrice’s turn, she chooses the largest of the three pieces. Therefore, given any division (1  2  3 ), Beatrice gets the largest, Caroline gets the middle one, and Alice gets the smallest i.e. min (1  2  3 ). Therefore, in dividing the cake Alice must max (1 2 3 ) 1 +2 +3 =1 min (1  2  3 )  The unique solution is (13 13 13). (b) Repeat (a) assuming instead that Beatrice picks a piece for Alice; Caroline picks a piece for Beatrice, and the remaining piece is given to Caroline. Answer: There are multiple solutions. The first solution is as follows. Given the remaining two pieces, Caroline gives the smaller to Beatrice, keeping the larger one for herself. Given the three pieces, Beatrice will get the smaller of the remaining two. Hence, it is a best response to Beatrice to give Alice the smallest of the three. Therefore, once again Alice receives the smallest of the three pieces, and therefore she divides the cake equally (13 13 13). There is also a continuum of other equilibria. To see this, note that when 1  2 = 3 , Beatrice has multiple best responses. She can give 3 to Alice and end up receiving 2 or give 3 to Alice and end up receiving 2 again. Hence, for any  ∈ [0 13], the following is also an outcome of backward induction. If 1  2 = 3 and 2  , she gives 3 =  to Alice and if 1  2 = 3 and 2 ≥ , she gives 1 to Alice. Alice picks 1 = 1 − 2 and 2 = 3 = . 4