.Game Theory for Economists以下考试题目与答案来自:卡内基美隆大学Carnegie Mellon University(题目与答案都是完整的)Final Exam•This exam is open-book and open-notes.•The exam consists of four parts.•You have 120 minutes to do your work.•Justify your answers. No explanation = No credit.Name: SOLUTIONPart 1 Part 2 Part 3 Part 4 TotalPart 1: (12 points) This part contains three questions.1) (3 points) For each of the following statements, provide a proof if it is true or a counter-example if it is not.a) In a static game of complete information, a pure strategy Nash equilibrium doesnot contain any weakly dominated strategy.Answer:False. The following game from lecture 2 is a counter-example.Player 2L RU 1 , 1 2 , 0Player 1B 0 , 2 2 , 2This game has two pure strategy Nash equilibria: (U, L) and (B, R ).B is weakly dominated by U. R is weakly dominated by L.b) In a game tree representing a finite dynamic game of complete and perfectinformation, the number of subgames (including the dynamic game) is equal to thenumber of nonterminal nodes.Answer: True.In a game tree representing a finite dynamic game of complete and perfectinformation, every information set contains a single node. A subgame can begin atany nonterminal node. So the number of subgames is equal to the number of thenonterminal nodes.2) (6 points) Consider the following game.Player 2L (p 21) C (p 22) R (p 23) T (p 11)4 , 40 , 0 0 , 0 M (p 12)0 , 01 , 20 , 1 Player 1B (p 13)0 , 0 0 , 2 3 , 3a) (1 point) Find all the pure strategy Nash equilibria.Answer: (T , L ), (M , C ) and (B , R )b) (2 point) Find ONE mixed strategy Nash equilibrium (that is not a pure strategy Nash equilibrium) Answer:One possible solution: , 0 ,0 ,0131211>>=p p p 0 ,0 ,0232221>>=p p p . By Theorem 4, we should have)) , ,( ,()) , ,( ,()) , ,( ,(232221123222112322211p p p B EU p p p M EU p p p T EU =≤ and)) , ,( ,()) , ,( ,()) , ,( ,(312111231211123121112p p p R EU p p p C EU p p p L EU =≤.0)) , ,( ,(2322211=p p p T EU2322232221123222113)) , ,( ,()) , ,( ,(p p p p p B EU p p p M EU =⇒= (1) Note that 12322232221=+=++p p p p p (2)Solving equations (1) and (2) gives us 41,432322==p p . It is easy to verify that 43)) , ,( ,()) , ,( ,(0)) , ,( ,(232221123222112322211==≤=p p p B EU p p p M EU p p p T EU .0)) , ,( ,(3121112=p p p L EU13121312131231211123121112322)) , ,( ,()) , ,( ,(p p p p p p p p p R EU p p p C EU =⇒+=+⇒=Note that 11312131211=+=++p p p p pSolving these two equations gives us 211312==p p . It is easy to verify that 2)) , ,( ,()) , ,( ,(0)) , ,( ,(312111231211123121112==≤=p p p R EU p p p C EU p p p L EUSo we have one mixed strategy: ⎟⎟⎠⎞⎜⎜⎝⎛⎟⎠⎞⎜⎝⎛⎟⎠⎞⎜⎝⎛41 ,43 ,0 ,21 ,21 ,0.Another possible solution: , . 0 ,0 ,0131211>>>p p p 0 ,0 ,0232221>>>p p p By Theorem 4, we should have 23222134p p p ==, 13121312113224p p p p p +=+=.Note that and 1232221=++p p p 1131211=++p p p . Solving these equations gives us amixed strategy: 194,1912 ,193( ),31 ,31 ,31((.c) (1 point) Consider a two-stage repeated game in which the above simultaneous-move game is played twice. The outcome of the first play is observed before the next play begins. The payoff for the entire game is simply the sum of the payoffs from the two stages. That is, the discount factor 1=δ. Find one subgame perfect Nash equilibrium of the repeated game in which the outcome of the first stage is (B , C ). Answer:This repeated game has a huge number of subgame perfect Nash equilibria. We usebackward induction to solve the nine smallest subgames. Because each smallest subgame has three Nash equilibria, we can select any of them. One subgame perfect Nashequilibrium of the repeated game in which the outcome of the first stage is (B , C ) can be obtained as follows.At the second stage, we select one of the three Nash equilibria according to the following rule.• (T , L ) in the smallest subgame following (B , C ) of the first stage, • (M , C ) in any other smallest subgame.Then we replace the smallest subgames by corresponding payoffs and get the following normal-form. (B , C ) is a Nash equilibrium in this normal-form.Player 2L C R T 4+1 , 4+2 0+1 , 0+2 0+1 , 0+2 M 0+1 , 0+2 1+1 , 2+2 0+1 , 1+2 Player 1B0+1 , 0+20+4 , 2+43+1 , 3+2d) (2 points) Now suppose that both players discount the payoffs from stage 2 by the discount factor δ, where 10<<δ. Determine the range of δ such that the subgame perfect Nash equilibrium you found in c) is still a subgame perfect Nash equilibrium. Answer: If both players discount the payoffs from the second stage, then we have the following normal-form.Player 2L C RT4+1δ , 4+2δ 0+1δ , 0+2δ 0+1δ , 0+2δM 0+1δ , 0+2δ 1+1δ , 2+2δ 0+1δ , 1+2δPlayer 1B0+1δ , 0+2δ 0+4δ , 2+4δ 3+1δ , 3+2δIn this normal-form, (B , C ) is still a Nash equilibrium if and only if ,14δδ+≥ ,4δδ≥ δδ2342+≥+ and δδ242≥+.Solving these gives us 121<≤δ.3) (3 points) Consider an infinitely repeated game in which the following simultaneous move game is repeated infinitely.Player 2L 2R 2L 10 , 0 4 , -1 Player 1R 1-1 , 4 3 , 3 a) (2 points) Determine the range of the discount factor δ such that the infinitelyrepeated game has a Nash equilibrium in which player i plays the following trigger strategy:• At stage 1, player i plays R i• At stage t , if the outcome of every of all t –1 previous stages is (R 1, R 2) then player i plays R i ; otherwise, player i plays L i .Answer:This question is similar to the example in the lecture notes. Following the same procedure, we have an infinite sequence of payoffs, 3, 3, 3, .... with the presentvalue δ−13, and an infinite sequence of payoffs, 4, 0, 0, .... with the presentvalue 4. In order to have a Nash equilibrium in which both players play the triggerstrategies, 141443413≤≤⇒−≥⇒≥−δδδ.b) (1 point) Argue that the Nash equilibrium in a) is subgame prefect.Answer: similar to the argument in the lecture notes.Part 2: (8 points)Consider the following dynamic game. This is a complicated game tree. Note that there are three players in this game. Player 1's payoff is the first number in each triple. Player 2's payoff is the second number in each triple. Player 3's payoff is third number in each triple.Player 11a) (1 point) Write down all the strategies for player 1.Answer: AS, AT, BS, BTb) (1 point) How many information sets does player 3 have?Answer: 4c) (2 points) Construct the normal-form for the subgame following D as indicated in the tree.Note that this subgame is played by player 2 and 3. You can ignore player 1's payoffs. Find all pure strategy Nash equilibria in your normal-form.Answer:Player 3E'P E'Q F'P F'QJ 2 , 1 0 , 2 4 , 2 4 , 2 Player 2K 1 , 2 2 , 3 4 , 2 4 , 2d) (4 points) Use backward induction to find all the subgame perfect Nash equilibria. Write down clearly the subgame perfect Nash equilibria you found.Answer: This is a complicated game. But it is not difficult to find all subgame perfect Nash equilibria by backward induction.I.Start with smallest subgames.II.Find the Nash equilibria in these smallest subgames.III.Replace these smallest subgames by the corresponding payoffs and obtain a new game tree.IV.Repeat I, II and III in the new game tree until the root is reached.There are two subgame perfect Nash equilibria.One is shown in the game tree on previous page. It can be written as (BS, CC'KXY', FE'HQ). Another one is shown in the following game tree. It can be written as (AS, DC'KXY', FE'HQ).Player 11Part 3: (10 points) This part contains one question.Only four firms, 1, 2, 3 and 4, produce a homogeneous product in a market. Let denote the quantity produced by firm i , for i =1, 2, 3, 4. The market price isi q 4321 where ,)(q q q q Q Q a Q P +++=−=Each firm has a constant marginal cost of production, c , and no fixed cost. That is, firm i 's cost function is . The timing is as follows.i i i cq q C =)(• Firm 1 and firm 2 simultaneously chooses and , respectively.1q 2q • After observing and , then firm 3 and firm 4 simultaneously chooses and , respectively.1q 2q 3q 4q Find the subgame perfect Nash equilibrium. What is the outcome? You may use the property of symmetry when you solve equations.Answer:We use backward induction to solve this problem.Step 1: We first solve the smallest subgame following any pair of . That is, we first solve the simultaneous move game played by firm 3 and firm 4 for any given . Note that we consider as constants when we solve the game played by firm 3 and 4. ) ,(21q q ) ,(21q q 21 ,q q Firm 3 and 4's problems:0 ..])([ 343213≥−+++−q t s c q q q q a q Max 0..])([ 443214≥−+++−q t s c q q q q a q MaxWe can solve the simultaneous move game step by step. There is a simple way as follows. Let 21q q a a −−=. Then firm 3 and 4's problems become0 ..])([ 3433≥−+−q t s c q q a q Max 0..])([ 4434≥−+−q t s c q q a q MaxNow the game played by firm 3 and 4 becomes Cournot model with a instead of a . We canappeal to the result of Cournot model. The Nash equilibrium is , where) ,(*4*3q q 3321*4*3cq q a c a q q −−−=−== They are functions of . We can also write then as21 and q q 3),(21213c q q a q q R −−−= 3),(21214cq q a q q R −−−=They are firm 3 and 4's best response to , respectively. ) ,(21q qStep 2: Now we move to the root to solve the simultaneous move game played by firm 1 and 2. Note that firm 1 and 2 knows that if they choose then firm 3 and 4 will choose and , respectively. So Firm 1 and 2's problems are ) ,(21q q ),(2133q q R q =),(2144q q R q =..])),(),(([ 1214213211≥−+++−q t s c q q R q q R q q a q Max0 ..])),(),(([ 2214213212≥−+++−q t s c q q R q q R q q a q MaxPlugging 3),(21213c q q a q q R −−−=, 3),(21214cq q a q q R −−−= into firm 1 and 2's problemsgives us..][31])(32[ 121121211≥−−−=−−−−−−−q t s c q q a q c c q q a q q a q Max 0..][31])(32[ 221221212≥−−−=−−−−−−−q t s c q q a q c c q q a q q a q Max So firm 1 and 2's problems become0 ..])([31 1211≥−+−q t s c q q a q Max 0..])([31 2212≥−+−q t s c q q a q Max They have the same solution (but different objective values) as0 ..])([ 1211≥−+−q t s c q q a q Max 0..])([ 2212≥−+−q t s c q q a q MaxWhy? Now the game played by firm 1 and 2 becomes Cournot model. We can appeal to the result of Cournot model again. So the Nash equilibrium is⎟⎠⎞⎜⎝⎛−=−=3 ,3*2*1c a q c a q Is it surprising? Hence, the subgame Nash equilibrium is⎟⎠⎞⎜⎝⎛−−−=−−−=−=−=3),( ,3),( ,3 ,32121421213*2*1c q q a q q R c q q a q q R ca q c a q The actual outcome is⎟⎠⎞⎜⎝⎛−=−=−=−=9 ,9 ,3 ,3*4*3*2*1c a q c a q c a q c a qPart 4: (10 points) Bayesian Nash equilibrium. This part contains two questions.1) (3 points) Battle of sexes with incomplete information (version one)Consider the battle of sexes with incomplete information. This static game of incomplete information has a Bayesian Nash equilibrium: (Opera, (Opera if happy, Prize Fight if unhappy)) if Chris believes that Pat is happy with probability 0.5, and unhappy with probability 0.5 (Why? Surely it needs computing carefully). Now we check whathappens if Chris' belief changes. Let's assume that Chris believes that Pat is happy with probability p , and unhappy with probability 1–p .Determine the range of p such that (Opera, (Opera if happy, Prize Fight if unhappy)) is a Bayesian Nash equilibrium.Pat Payoffs if Pat is happywith probability p Opera Prize FightOpera 2 , 1 0 , 0 ChrisPrize Fight0 , 01 , 2PatPayoffs if Pat is unhappy with probability 1–p Opera Prize Fight Opera 2 , 0 0 , 2 ChrisPrize Fight0 , 11 , 0Answer:Obviously, "Opera" is Pat's best response to Chris' "Opera" if Pat is happy, and "Prize Fight" is Pat's best response to Chris' "Opera" if Pat is unhappy. Now we need to check whether "Opera" is Chris' best response to Pat's (Opera if happy, Prize Fight if unhappy).• If Chris chooses "Opera" then she get a payoff 2 if Pat is happy, and 0 if Pat is unhappy. Her expected payoff is 2p .• If Chris chooses "Prize Fight" then she get a payoff 0 if Pat is happy, and 1 if Pat is unhappy. Her expected payoff is p −1.• "Opera" is her best response if and only if p p −≥12. That is, 131≤≤p .(7 points) Fighting an opponent of unknown strengthTwo people, Bruce and Pat, are involved in a dispute. Bruce does not know whether Pat is strong or weak. But Bruce believes that Pat is strong with probability p , and weak with probability 1–p . Pat is fully informed. Each person can either fight or yield. The payoffs are shown as follows.Pat Payoffs if Pat is strongwith probability p Fight YieldFight -1 , 1 1 , 0 BruceYield 0 , 1 0 , 0Pat Payoffs if Pat is weakwith probability 1–pFight Yield Fight 1 , -1 1 , 0 BruceYield 0 , 1 0 , 0a) (3 points) Show that there is a unique pure strategy Bayesian Nash equilibrium if21<p . Write down the unique pure strategy Bayesian Nash equilibrium.Answer:If Bruce chooses "Fight" then Pat's best response is ("Fight" if strong, "Yield" if weak). If Bruce chooses "Yield" then Pat's best response is ("Fight" if strong, "Fight" if weak). By the definition of Bayesian Nash equilibrium, we only need to consider the following two cases.• Check whether ("Fight", ("Fight" if strong, "Yield" if weak)) is a Bayesian Nash equilibrium. Since ("Fight" if strong, "Yield" if weak) is Pat's best response to Bruce's "Fight", we need to check whether "Fight" is Bruce's best response to Pat's ("Fight" if strong, "Yield" if weak). If yes, then ("Fight", ("Fight" if strong, "Yield" if weak)) is a Bayesian Nash equilibrium.o If Bruce chooses "Fight" then he get a payoff -1 if Pat is strong, and 1 ifPat is weak. His expected payoff is p p p 21)1(−=−+−.o If Bruce chooses "Yield" then he get a payoff 0 if Pat is strong, and 0 ifPat is weak. His expected payoff is 0.o "Fight" is Bruce's best response if and only if 021≥−p . That is, 21≤p . • Check whether ("Yield", ("Fight" if strong, "Fight" if weak)) is a Bayesian Nash equilibrium. Since ("Fight" if strong, "Fight" if weak) is Pat's best response to Bruce's "Yield", we need to check whether "Yield" is Bruce's best response to Pat's ("Fight" if strong, "Fight" if weak). If yes, then ("Yield", ("Fight" if strong, "Fight" if weak)) is a Bayesian Nash equilibrium.o If Bruce chooses "Fight" then he get a payoff -1 if Pat is strong, and 1 if Pat is weak. His expected payoff is p p p 21)1(−=−+−.o If Bruce chooses "Yield" then he get a payoff 0 if Pat is strong, and 0 if Pat is weak. His expected payoff is 0.o "Yield" is Bruce's best response if and only if 021≤−p . That is, 21≥p . Now it is clear that there is a unique pure strategy Bayesian Nash equilibrium if 21<p . The Bayesian Nash equilibrium is ("Fight", ("Fight" if strong, "Yield" if weak)). This completes the answer to a).b) (3 points) Show that there is a unique pure strategy Bayesian Nash equilibrium if21>p . Write down the unique pure strategy Bayesian Nash equilibrium.Answer: By the answer in a), there is also a unique pure strategy Bayesian Nash equilibrium if21>p . The Bayesian Nash equilibrium is ("Yield", ("Fight" if strong, "Fight" if weak)). This completes the answer to b).c) (1 point) What happens if 21=p ?Answer:By the answer in a), there are two Bayesian Nash equilibria if 21=p . They are ("Fight", ("Fight" if strong, "Yield" if weak))("Yield", ("Fight" if strong, "Fight" if weak))。