Dynamic Games with Incomplete Information

Chapter 16 Dynamic Games with Incomplete Information This chapter is devoted to the basic concepts in dynamic games with incomplete in­ formation. As in the case of complete information, Bayesian Nash equilibrium allows players to take suboptimal actions in information sets that are not reached in equilib­ rium. This problem addressed by sequential equilibrium, which explicitly requires that the players play a best reply at every information set (sequential rationality) and that the players’ beliefs are "consistent" with the other players’ strategies. Here, I will define sequential equilibrium and apply it to some important games. Remark 16.1 Sequential equilibrium is closely related to another solution concept, called perfect Bayesian Nash equilibrium. Sequential equilibrium is a better defined solution concept, and easier to understand. The two solution concepts are equiva­ lent in the games considered here. Hence, you should apply sequential equilibrium in past exam questions regarding perfect Bayesian Nash equilibrium. 16.1 Sequential Equilibrium Consider the game in Figure 16.1. This game is meant to describe a situation in which a firm does not know whether a worker is hard working, in the sense of preferring to work rather than shirk, or lazy, in the sense of wanting to shirk. The worker is likely to be hard working. However, there is a Bayesian Nash equilibrium, plotted in bold lines, in which 311 312 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION Work (1, 2) W Firm Hire Shirk (0, 1) High .7 Do not hire Nature Low .3 Hire (0, 0) W Work Shirk Do not hire (1, 1) (-1, 2) (0, 0) Figure 16.1: A Bayesian Nash equilibrium in which player W plays a suboptimal action. worker would shirk if he were hired, independent of whether he is hard working or lazy, and anticipating this, the firm does not hire. Clearly, hard working worker’s shirking is against his preferences (which were meant to model a worker who would rather work). This is however consistent with Bayesian Nash equilibrium because every strategy of the worker is a best reply to the "do not hire" strategy of the firm. (Worker gets 0 no matter what strategy he plays.) In order to solve this problem, assume that players are sequentially rational, i.e., they play a best reply at every information set, maximizing their expected payoff conditional on that they are at the information set. That is, when he is to move, the hard working worker would know that Nature has chosen "High" and the firm has chosen "Hire", and he must play Work as the only best reply under that knowledge. This would lead to the other equilibrium, in which firm hires and worker works if he is hard working and shirks otherwise. Notice that the latter equilibrium is the only subgame-perfect equilibrium in that game. Since subgame perfection has been introduced as a remedy to the problem exhib­ ited in the former equilibrium, it is tempting to think that subgame perfection solves the problem. As we have seen in the earlier lectures, it does not. For example, consider the strategy profile in bold in Figure 16.2. This is a subgame-perfect equilibrium because there is no proper subgame, and it clearly a Nash equilibrium. Strategy L is a best reply only to X. However, at the information Player 2 moves, she knows that player one has played either T or B. Given this knowledge, L could not be a best reply. In order to formalize the idea of sequential rationality for general games, we need to 16.1. SEQUENTIAL EQUILIBRIUM 313 X 1 (2,6) T B 2 L R (0,1) (3,2) L (-1,3) R (1,5) Figure 16.2: A SPE in which player 2 plays a sequentially irrational strategy. define beliefs: Definition 16.1 A belief assessment is a list b of probability distributions on informa­ tion sets; for each information set I, b gives a probability distribution b(·|I) on I. For any information set I, the player who moves at I believes that he is at node n ∈ I with probability b (n|I). For example, for the game in Figure 16.2, in order to define a belief assessment, we need to assign a probability μ on the node after T and a probability 1 − μ on the node after B. (In information sets with single nodes, the probability distribution is trivial, putting 1 on the sole node.) When Player 2 moves, she believes that Player 1 played T with probability μ and B with probability 1 − μ. We are now ready to define sequential rationality for a strategy profile: Definition 16.2 For a given pair (s, b) of strategy profile s and belief assessment b, strategy profile s is said to be sequentially rational iff, at each information set I, the player who is to move at I maximizes his expected utility 1. given his beliefs b(·|I) at the information set (which imply that he is at information set I), and 2. given that the players will play according to s in the continuation game. For example, in Figure 16.2, for Player 2, given any belief μ, L yields U2 (L; μ) = 1 · μ + 3 · (1 − μ) 314 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 1 T 2 L B .9 .1 R (0,10) (3,2) L (-1,3) R (1,5) Figure 16.3: An inconsistent belief assessment while R yields U2 (R; μ) = 2 · μ + 5 · (1 − μ) . Hence, sequential rationality requires that Player 2 plays R. Given Player 2 plays R, the only best reply for Player 1 is T . Therefore, for any belief assessment b, the only sequentially rational strategy profile is (T, R). In order to have an equilibrium, b must also be consistent with σ. Roughly speaking, consistency requires that players know which (possibly mixed) strategies are played by the other players. For a motivation, consider Figure 16.3 and call the node on the left nT and the node on the right nB . Given the beliefs b (nT |I2 ) = 0.1 and b (nB |I2 ) = 0.9, strategy profile (T, R) is sequentially rational. Strategy T is a best response to R. To check the sequential rationality for R, it suffices to note that, given the beliefs, L yields (.1) (10) + (.9) (3) = 3.7 while R yields (.1) (2) + (.9) (5) = 4.7. (Note that there is no continuation game.) But (T, R) is not even a Nash equilibrium in this game. This is because in a Nash equilibrium player knows the other player’s strategy. She would know that Player 1 plays T , and hence she would assign probability 1 on nT . In contrast, according to b, she assigns only probability 0.1 on nT . In order to define consistency formally, we need to think more carefully about the information sets are reached positive probability (the information sets that are "on the 16.1. SEQUENTIAL EQUILIBRIUM 315 path") and the ones that are not supposed to be reached ("off the path") according to the strategy profile. Definition 16.3 Given any (possibly mixed) strategy profile s, belief assessment b, and any information set I that is reached with positive probability according to s, the beliefs b (·|I) at I is said to be consistent with s iff b (·|I) is derived using the Bayes rule and s. That is, for each node n in I, Pr (n|s) , ' nl ∈I Pr (n |s) b (n|I) = L where Pr (n|s) is the probability that we reach node n according to s. For example, in order a belief assessment b to be consistent with (T, R), we need μ = b (nT |I) = Pr (nT | (T, R)) 1 = = 1. 1+0 Pr (nT | (T, R)) + Pr (nB | (T, R)) In general, there can be information sets that are not supposed to be reached accord­ L ing to the strategy profile. In that case the number nl ∈I Pr (n' |s) on the denominator would be zero, and we cannot apply the Bayes rule (directly). For such information sets, we perturb the strategy profile slightly, by assuming that players may "tremble", and apply the Bayes rule using the perturbed strategy profile. To see the general idea, consider the game in Figure 16.4. The information set of player 3 is off the path of the strategy profile (X, T, L). Hence, we cannot apply the Bayes rule. But we can still see that the beliefs the figure are inconsistent. Let us perturb the strategies of players 1 and 2 assuming that players 1 and 2 tremble with probabilities ε1 and ε2 , respectively, where ε1 and ε2 are small but positive numbers. That is, we put probability ε1 on E and 1 − ε1 on X (instead of 0 and 1, respectively) and 1 − ε2 on T and ε2 on B (instead of 1 and 0, respectively). Under the perturbed beliefs, Pr (nT |I3 , ε1 , ε2 ) = ε1 (1 − ε2 ) = 1 − ε2 , ε1 (1 − ε2 ) + ε1 ε2 where nT is the node that follows T . As ε2 → 0, Pr (nT |I3 , ε1 , ε2 ) → 1. Therefore, for consistency, we need b (nT |I3 ) = 1. Definition 16.4 Given any (s, b), belief assessment b is consistent with s iff there exist some trembling probabilities that go to zero such that the conditional probabilities derived 316 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 1 E X 2 T 3 B 0.1 L R 1 2 1 2 0 0 0.9 L 3 3 3 R 0 1 2 0 1 1 Figure 16.4: A belief assessment that is inconsistent off the path by Bayes rule with trembles converge to probabilities given by b on all information sets (on and off the path of s). That is, there exists a sequence (σ m , bm ) of assessments such that 1. (σ m , bm ) → (σ, b), 2. σ m is "completely mixed" for every m, and 3. bm is derived from σ m using the Bayes’ rule. Here, note that σ m and σ prescribe probability distributions σ m i (·|I) and σ i (·|I) on the available moves at every information set I of every player i. Likewise, σ m and σ prescribe probability distributions bm (·|I) and b (·|I) on every information set I. The m first condition states that limm→∞ σ m i (a|I) → σ i (a|I) and limm→∞ b (n|I) → b (n|I) for every i, I,and all nodes n ∈ I and all available moves a at I. The second condition requires that σ m i (a|I) > 0 everywhere (i.e. every available move is played with positive probability). Under any such strategy profile, every information set is reached with positive probability, and hence one can apply Bayes rule to obtain the beliefs. Sequential equilibrium is defined as an assessment that is sequentially rational and consistent: 16.2. SEQUENTIAL EQUILIBRIUM IN BEER AND QUICHE GAME 317 Definition 16.5 A pair (s, b) of a strategy profile s and a belief assessment b is said to be a sequential equilibrium if (s, b) is sequentially rational and b is consistent with s. Note that a sequential equilibrium is a pair, not just a strategy profile. Hence, in order to identify a sequential equilibrium, one must identify a strategy profile s, which describes what a player does at every information set, and a belief assessment b, which describes what a player believes at every information set. In order to check that that (s, b) is a sequential equilibrium, one must check that 1. (Sequential Rationality) s is a best response to belief b (·|I) and the belief that the other players will follow s in the continuation games in every information set I, and 2. (Consistency) there exist trembling probabilities that go to zero such that the conditional probabilities derived from Bayes rule under the trembles approach b (·|I) at every information set I. Example 16.1 In the game in Figure 16.4, the unique subgame-perfect equilibrium is s∗ = (E, T, R). Let us check that (s∗ , b∗ ) where b∗ (nT |I3 ) = 1 is a sequential equilibrium. We need to check that 1. s∗ is sequentially rational (at all information sets) under b∗ , and 2. b∗ is consistent with s∗ . At the information set of player 3, given b∗ (nT |I3 ) = 1, action L yields 1 while R yields 3, and hence R is sequentially rational. At the information set of Player 2, given the other strategies, T and B yield 3 and 1, respectively, and hence playing T is sequentially rational. At the information set of Player 1, E and X yield 3 and 2, respectively, and hence playing E is again sequentially rational. Since all the information sets are reached under s∗ , we just need to use the Bayes rule in order to check consistency: Pr (nT |I3 , s∗ ) = 1 = b∗ (nT |I3 ) . 1+0 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 0 1 2 0 3 1 el don {.1} ’t don quiche qui che beer tw ts el du 1 0 du beer {.9} 1 1 el du don ’t du el 318 3 0 0 0 quiche qui che don ’t ’t 2 1 Figure 16.5: Beer & Quiche game 16.2 Sequential equilibrium in Beer and Quiche Game Consider the game in Figure 16.5. Here Player 1 has two types: strong (ts ) and weak (tw ). The strong type likes beer for breakfast, while the weak type likes quiche. Player 1 is ordering his breakfast, while Player 2, who is a bully, is watching and contemplating whether to pick a fight with Player 1. Player 2 would like to pick a fight if Player 1 is weak but not fight if he is strong. His payoffs are such that if he assign probability more than 1/2 to weak, he prefers a fight, and if he assigns probability more than 1/2 to strong, then he prefers not to fight. Player 1 would like to avoid a fight: he gets 1 utile from the preferred breakfast and 2 utiles from avoiding the fight. Before observing the breakfast Player 2 finds it more likely that Player 1 is strong. One sequential equilibrium, denoted by (s∗ , b∗ ), is depicted in Figure 16.6. Both types of Player 1 order beer. If Player 2 sees Beer, he assigns probability 0.9 to strong and does not fight; if he sees Quiche, he assigns probability 1 on weak and fights. Let us check that this is indeed a sequential equilibrium. We start with sequential rationality. Playing Beer is clearly sequentially rational for the strong type because it leads to the highest payoff for ts . For tw , beer yields 2 (beer, don’t) while quiche yields only 1 (quiche, duel). Hence beer is sequentially rational for tw , too. After observing beer, the expected payoff of Player 2 from "duel" is (.9) (0) + (.1) (1) = .1 16.2. SEQUENTIAL EQUILIBRIUM IN BEER AND QUICHE GAME ’ don tw ’ don .9 beer {.9} el 1 d on’ t ts el 3 1 {.1} .1 t du quiche beer du 1 0 el 1 1 el 2 0 du quiche 0 du 0 1 don t 319 3 0 0 0 ’t 2 1 Figure 16.6: A PBE in Beer and Quiche game while his payoff from "don’t" is (.9) (1) + (.1) (0) = .9, and hence "don’t" is indeed sequentially rational. After observing quiche, the expected payoff of Player 2 from duel is 1 (which is (1) (1) + (0) (0)) while his expected payoff from "don’t" is 0. Hence, duel is sequentially rational at this information set. To check consistency, we start the information set after beer. This information set is on the path, and hence we use the Bayes rule. Clearly, Pr (ts ) Pr (beer|ts , s∗ ) Pr (ts ) Pr (beer|ts , s∗ ) + Pr (tw ) Pr (beer|tw , s∗ ) (.9) (1) = = .9 (.9) (1) + (.1) (1) = b∗ (ts |beer) , Pr (ts |beer, s∗ ) = showing that the beliefs are consistent after observing beer. Now consider the informa­ tion set after quiche. This information set is off the path, and we cannot apply the Bayes rule directly. In order to check consistency at this information set, we need to find some trembling probabilities that would lead to probability 1 on weak in the limit. (Notice that we don’t need all the trembles to lead to this probability in the limit. There could CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 2 0 el don ’t {.1} tw don 0 beer {.9} ’t 1 1 el .1 d on’ t ts el 3 1 1 du quiche beer du 1 0 du el 0 1 quiche .9 du 320 don ’t 3 0 0 0 2 1 be some other trembles that would lead to a different limit.) Suppose that weak type trembles with probability ε while the strong type trembles with probability zero. Then, Pr (tw |quiche, ε) = (.1) ε = 1. (.1) ε + (.9) (0) As ε → 0, clearly, Pr (tw |quiche, ε) → 1 = b∗ (tw |quiche), showing that b∗ is consistent with s∗ .1 Above equilibrium is intuitive. Since weak type likes quiche, Player 2 takes ordering quiche as a sign of weakness and fights. Anticipating this, none of the types orders quiche. There is also another sequential equilibrium in which both types order quiche, as depicted in Figure 16.2. Exercise 16.1 Check that the strategy profile and the belief assessments in Figure 16.2 are a sequential equilibrium. Exercise 16.2 Find all sequential equilibria in Beer and Quiche game. (Hint: Note that there may be two different equilibria in which the strategy profiles are same but the beliefs are different.) Beer and Quiche game is a representative of an important class of games, called signaling games. In these games, Player 1 has several types, i.e. he knows something 1 We could also allow both types to tremble. For example, we can take tremble probability ε for weak type and ε2 for the strong type. The conditional probability would be (.1) ε .1 = → 1. 2 .1 + .9ε (.1) ε + (.9) ε 16.2. SEQUENTIAL EQUILIBRIUM IN BEER AND QUICHE GAME 3 1 quiche beer {.1} ’t don el du 1 0 el tw ts beer {.9} 1 1 el du don ’t el 0 0 du du -2 1 321 3 0 0 0 quiche ’t don don ’t 2 1 Figure 16.7: A revised version of Beer and Quiche game relevant. He takes an action (called a message). Player 2 observes Player 1’s action but not his type and takes an action. Players’ payoffs depend both players’ actions and Player 1’s type. Definition 16.6 In a signaling game, a pooling equilibrium is a sequential equilibrium in which all types of Player 1 play the same action. Both of the equilibria in Beer and Quiche game are pooling equilibrium. In a pooling equilibrium, Player 2 does not learn anything from Player 1’s actions on the path of equilibrium (i.e. his beliefs at the information set on the path are just his prior beliefs). In some signaling games, different types may take different actions, and Player 2 may learn Player 1’s information from his actions: Definition 16.7 In a signaling game, a separating equilibrium is a sequential equilib­ rium in which every type of Player 1 play a different action. Notice that if a type t∗ plays action a∗ in a separating equilibrium, then by consistency Player 2 assigns probability 1 to t∗ when he observes a∗ . Therefore, after Player 1 takes his action Player 2 learns his type (putting probability 1 on the correct type). Example 16.2 Consider the game in Figure 16.7, where weak type really dislikes beer. In this game there is a unique sequential equilibrium, depicted in Figure 16.8. Since weak type plays quiche and strong type plays beer, it is a separating equilibrium. Notice that Player 2 assigns probability 1 to ts after beer and to tw after quiche. CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 0 0 el ’ don 0 t ’ don {.1} tw 1 beer {.9} t 1 1 el 1 d on’ t ts el 3 1 du quiche beer du 1 0 du el -2 1 quiche 0 du 322 don ’t 3 0 0 0 2 1 Figure 16.8: A separating equilibrium Exercise 16.3 Check that the strategy profile and the belief assessment form a sequential equilibrium. Show also that this is the only sequential equilibrium. Sequential equilibrium in mixed strategies In some games the only sequential equilibrium is in mixed strategies. For example, in the original Beer and Quiche game (of Figure 16.5), take the probability of the weak type tw as 0.8 instead of 0.1, so that, before the bully observes what Player 1 has for his breakfast, bully finds Player 1 more likely to be weak. In that case neither of the pooling equilibria can remain as a sequential equilibrium. For example, in the one in which both types play beer, Player 2 must assign probability 0.8 to weak type after observing beer, and he must fight by sequential rationality. In that case, tw must play quiche as a best reply. One can also check that there is no separating equilibrium. For example, if strong type has beer and the weak type has quiche, then Player 2 would learn player’s type after the choice of breakfast and would fight only after quiche. In that case, weak type would like to deviate. Therefore in a sequential equilibrium, at least one of the types must be playing a mixed strategy. In order to find the equilibrium, let us write pB and pQ for the probabilities of "don’t" (i.e. "don’t duel") after beer and quiche respectively. Write UB (t) and UQ (t) for the 16.2. SEQUENTIAL EQUILIBRIUM IN BEER AND QUICHE GAME 323 expected payoffs from beer and quiche for type t, respectively. Then,2 UB (ts ) − UQ (ts ) = 1 + 2 (pB − pQ ) and UB (tw ) − UQ (tw ) = −1 + 2 (pB − pQ ) . Hence, UB (ts ) − UQ (ts ) = 2 + UB (tw ) − UQ (tw ) > UB (tw ) − UQ (tw ) . (16.1) Now, if tw plays beer with positive probability, then for sequential rationality we must have UB (tw ) ≥ UQ (tw ). Then (16.1) implies that UB (ts ) > UQ (ts ). In that case, sequential rationality requires that ts must play beer with probability 1. Similarly, one can conclude that if ts plays quiche with positive probability, then tw must play quiche with probability 1. Therefore, in a sequential equilibrium, either (i) ts plays beer and tw mixes, or (ii) ts mixes and tw plays quiche. The case (ii) cannot happen in equilibrium. After beer, Player 2 must assign proba­ bility 1 on ts and not fight, i.e. pB = 0. Moreover, after quiche, he must assign Pr (tw |quiche) = 0.8 ≥ 0.8 0.8 + 0.2 Pr (quiche|ts ) to the weak type and must fight, i.e. pQ = 1. In that case, UB (ts ) = 3 and UB (tw ) = 0, and strong type must fight with probability 1 (not mixing). Therefore, in equilibrium, ts plays beer and tw mixes. By consistency, we must have Pr (tw |quiche) = Pr (quiche|tw ) (0.8) = 1. Pr (quiche|tw ) (0.8) + 0 · 0.2 By sequential rationality, Player 2 must fight after quiche: pQ = 1. Since tw mixes, it must be that 0 = UB (tw ) − UQ (tw ) = −1 + 2 (pB − pQ ). Therefore, pB = 1/2. That is, after observing beer, player two strictly mixes between "duel" and "don’t". For sequential rationality, he must then be indifferent between them. This happens only 2 Notice that UB (ts ) = 1 + 2pB and UQ (ts ) = 2pQ . CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 2 0 ’ don 3/4 1/4 {.8} tw .5 beer {.2} 1 1 el 1 don ’t ts el .5 du quiche beer .5 ’t .5 n o d .5 3 1 el du 1 0 .5 du el 0 1 quiche 0 du 324 don t 3 0 0 0 ’t 2 1 when3 Pr (tw |beer) = 1/2. Finally, for consistency after beer, we must have 1/2 = Pr (tw |beer) = Pr (beer|tw ) (0.8) . Pr (beer|tw ) (0.8) + 1 · 0.2 By solving for Pr (beer|tw ), we obtain Pr (beer|tw ) = 1/4. We have identified a strategy profile and belief assessment, depicted in Figure 16.2. From our derivation, one can check that this is indeed a sequential equilibrium. Exercise 16.4 Check that the strategy profile and the belief assessment in Figure 16.2 form a sequential equilibrium. 16.3 A Simple example of Reputation Formation In a complete information game, it is assumed that the players know exactly what other players’ payoffs are. In real life this assumption almost never holds. What would happen 3 Payoff from duel is Pr (tw |beer) while the payoff from "don’t" is Pr (ts |beer). 16.3. A SIMPLE EXAMPLE OF REPUTATION FORMATION 2 1 325 1 (1,-5) .9 .1 (4,4) (3,3) (5,2) 1 2 1 (0,-5) (-1,4) (0,2) (-1,3) in equilibrium if a player has a small amount of doubt about the other player’s payoffs? It turns out that in dynamic games such small changes may have profound effects on the equilibrium behavior. The next example illustrates this fact. (It also illustrates how one computes a mixed-strategy sequential equilibrium.) Consider the game in Figure 16.3. In this game, Player 2 does not know the payoffs of Player 1. She thinks at the beginning that his payoffs are as in the upper branch with high probability 0.9, but she also assigns the small probability of 0.1 to the possibility that he is averse to play down, exiting the game. Call the first type of Player 1 "normal" type and the second type of Player 1 "crazy" type. If it were common knowledge that Player 1 is "normal", then backward induction would yield the following: Player 1 goes down in the last decision node; Player 2 goes across, and Player 1 goes down in the first node. What happens in the incomplete information game of Figure 16.3 in which the above common knowledge assumption is relaxed? By sequential rationality, the "crazy" type (in the lower branch) will always go across. In the last decision node, the normal type again goes down. Can it be the case that the normal type goes down in his first decision node, as in the complete information case? It turns out that the answer is No. If in a sequential equilibrium "normal" type goes down in the first decision node, in her information set, Player 2 must assign probability 1 to the crazy type. (By Bayes rule, Pr (crazy|across) = 0.1/ (0.1 + (.9) (0)) = 1. This is required for consistency.) Given this belief and the actions that are already determined, she gets −5 from going across and 2 from going down, and she must go down for sequential rationality. But then 326 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION "normal" type should go across as a best reply, which contradicts the assumption that he goes down. Similarly, one can also show that there is no sequential equilibrium in which the normal type goes across with probability 1. If that were the case, then by consistency, Player 2 would assign 0.9 to normal type in her information set. Her best response would be to go across for sure, and in that case the normal type would prefer to go down in the first node. In any sequential equilibrium, normal type must mix in his first decision node. Write α = Pr (across|normal) and β for the probability of going across for Player 2. Write also μ for the probability Player 2 assigns to the upper node (the normal type) in her information set. Since normal type mixes (i.e. 0 < α < 1), he is indifferent. Across yields 3β + 5 (1 − β) while down yields 4. For indifference, the equality 3β + 5 (1 − β) = 4 must therefore hold, yielding β = 1/2. Since 0 < β < 1, Player 2 must be indifferent between going down, which yields 2 for sure, and going across, which yields the expected payoff of 3μ + (−5) (1 − μ) = 8μ − 5. That is, 8μ − 5 = 2, and μ = 7/8. But this belief must be consistent: 7 0.9α =μ= . 8 0.9α + .1 Therefore, α = 7/9. This completes the computation of the unique sequential equilibrium, which is depicted in Figure 16.3. Exercise 16.5 Verify that the pair of mixed strategy profile and the belief assessment is indeed a sequential equilibrium. 16.4. BARGAINING WITH INCOMPLETE INFORMATION 1 α=7/9 2 β=1/2 327 1 (1,-5) μ=7/8 .9 .1 (4,4) (3,3) (5,2) 1 2 1 (0,-5) (-1,4) (0,2) (-1,3) Notice that in sequential equilibrium, after observing that Player 1 goes across, Player 2 increases her probability for Player 1 being a crazy type who will go across, from 0.1 to 0.125. If she assigned 0 probability at the beginning she would not change her beliefs after she observes that he goes across. In the latter case, Player 1 could never convince her that he will go across (no matter how many times he goes across), and he would not try. When that probability is positive (no matter how small it is), she will increase her probability of him being crazy after she sees him going across, and Player 1 would try go across with some probability even he is not crazy. Exercise 16.6 In the above game,compute the sequential equilibrium for any initial probability π ∈ (0, 1) of crazy type (in the figure π = 0.1). 16.4 Bargaining with Incomplete Information We will now analyze a relatively simple bargaining game with incomplete information. A seller has an object, whose value for him is 0. There is also a buyer. The value of the object for the buyer is v, where v is uniformly distributed on [0, 1]. The buyer knows v, but the seller does not. There are two periods, 0 and 1. At period 0, seller sets a price p0 and the buyer decides whether to buy the object at price p0 . If he buys, the payoffs of the seller and the buyer are p0 and v − p0 , respectively. Otherwise, they proceed to the next period. In period 1, the seller set again a price p1 and the buyer decides 328 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION whether to buy. If he buys, the payoffs of the seller and the buyer are δp0 and δ (v − p0 ), respectively, where δ ∈ (0, 1). Otherwise, the game ends with zero payoffs. Consider a sequential equilibrium with the following cutoff strategies.4 For any price p0 and p1 there are cutoffs a (p0 ) and b (p1 ) such that at period 0, buyer buys if and only if v ≥ a (p0 ) and at period 1, the buyer buys if and only if v ≥ b (p1 ). At period 1, given any price p1 , buyer gets δ (v − p1 ) if he buys and 0 otherwise. Hence, by sequential rationality, he should buy if and only if v ≥ p1 .That is, b (p1 ) = p1 . Now, given any p0 , if the buyer does not buy in period 0, then seller knows, from the strategy of the buyer, that v ≤ a (p0 ). That is, after the rejection of p0 , the seller believes that v is uniformly distributed on [0, a (p0 )]. Given that buyer buys iff v ≥ p1 , the expected payoff of the seller is US (p1 |p0 ) = p1 Pr (p1 ≤ v|v ≤ a (p0 )) = p1 (a (p0 ) − p1 ) /a (p0 ) . For sequential rationality, after the rejection of p0 , the price p1 (p0 ) must maximize US (p1 |p0 ). Therefore, p1 (p0 ) = a (p0 ) /2. (16.2) Now consider period 0. Given any price p0 , the types v ≥ a (p0 ) buy at price p0 at period 0; the types v ∈ [a (p0 ) /2, a (p0 )) buy at price a (p0 ) /2 at period 1, and the other types do not buy. For sequential rationality, we must have v − p0 ≥ δ (v − p1 (p0 )) for v ≥ a (p0 ) v − p0 ≤ δ (v − p1 (p0 )) for v ∈ [a (p0 ) /2, a (p0 )). By continuity, this implies that we have equality at v = a (p0 ): a (p0 ) − p0 = δ (a (p0 ) − p1 (p0 )) = δa (p0 ) /2, where the last equality is by (16.2). Therefore, a (p0 ) = p0 . 1 − δ/2 All we need to do is now to find what price buyer sets at period 0. For any price p0 , he gets p0 from types with v ≥ a (p0 ), δp1 (p0 ) = δa (p0 ) /2 from types v ∈ [a (p0 ) /2, a (p0 )) 4 This is actually the only sequential equilibrium. 16.5. EXERCISES WITH SOLUTIONS 329 and zero from the rest. His expected payoff is US (p0 ) = p0 · (1 − a (p0 )) + δ (a (p0 ) /2) · (a (p0 ) − a (p0 ) /2) p0 1− 1 − δ/2 = p0 +δ 2 p0 2−δ . The first period price must maximize US (p0 ). By taking the derivative and setting it equal to zero, we obtain p0 = 16.5 (1 − δ/2)2 . 2 (1 − 3δ/4) Exercises with Solutions 1. [Final 2007, Early exam] Find a sequential equilibrium of the following game: A 1 1/3 B 1/3 1 1 L1 R1 L2 2 2 a C 1/3 b L3 R2 a b 1 1 0 2 R3 -1 0 1 3 1 x y 3 0 0 3 2 2 2 l r 2 10 1 -1 l -1 1 l r r 1 w z 3 0 1 2 2 0 1 2 330 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION Answer: The following is the unique sequential equilibrium: A 1 1/3 R1 1/3 1 L2 2 0 1 b a C 1 L1 2 1/3 B L3 R2 a b 1 1 0 2 R3 -1 0 1 3 1 x y 2 3 0 0 3 l r 2 10 1 -1 1/2 2 1/2 l r l -1 1 2 r 1 w z 3 0 1 2 2 0 1 2 2. [Final 2007, Early exam] This question is about a game, called "Deal or No Deal". The monetary unit is M$, which means million dollars. The players are a Banker and a Contestant. There are 3 cases: 0,1, and 2. One of the cases contains 1M$ and all the other cases contain zero M$. All cases are equally likely to contain the 1M$ prize (with probability 1/3). Contestant owns Case 0. Banker offers a price p0 , and Contestant accepts or rejects the offer. If she accepts, then Banker buys the content of Case 0 for price p0 , ending the game. (Contestant gets p0 M$ and Banker gets the content of the case, minus p0 M$.) If she rejects the offer, then we open Case 1, revealing the content to both players. Banker again offers a price p1 , and Contestant accepts or rejects the offer. If she accepts, then Banker buys the content of Case 0 for price p1 ; otherwise we open Case 2, and the game ends with Contestant owning the content of Case 0 and Banker owning zero. The utility of owning x M$ is x for the Banker and x1/α for the Contestant, where α > 1. (a) (10 points) Assuming α is commonly known, apply backward induction to 16.5. EXERCISES WITH SOLUTIONS 331 find a subgame-perfect equilibrium. Answer: If Case 1 contains 1M$, then in period 1 players know that Case 0 contains 0, and hence Contestant accepts any offer, and Banker offers 0. If Case 1 contains 0M$, then players know that Case 0 contains 0 with proba­ bility 1/2 and 1M$ with probability 1/2. The expected payoff of Contestant from rejecting an offer p1 is 1/2. Hence, she accepts the offer iff 1/α p1 ≥ 1/2, i.e., p1 ≥ 1/2α . Therefore, Banker offers p1 = 1/2α . Notice that, since α > 1, the value of the case for the banker is 1/2 > p1 , and he is happy to make that offer. Now consider period 0. If the offer p0 is rejected, then with probability 1/3 it will be revealed that Case 1 contains 1M$, and players will get (0,0), and with probability 2/3 it will be revealed that Case 1 contains 0M$, and Banker will get payoff of 1/2 − 1/2α in expectation and Contestant will get payoff 1/α of 1/2 (which is p1 ). The expected value of these payoffs for Banker and Contestant are 1/3 − 2/ (2α 3) and 1/3, respectively. Therefore, Contestant will accept p0 iff 1/α p0 ≥ 1/3, i.e., p0 ≥ 1/3α . Therefore, Banker will offer p0 = 1/3α . Notice that, since α > 1, 2/ (2α 3) > 1/3α , and hence Banker would rather offer p0 and get 1/3 − 1/3α ; as opposed to making a rejected offer and getting 1/3 − 2/ (2α 3) as a result. (b) Now assume that Banker does not know α, i.e., α is private information of Contestant, and Pr (1/2α ≤ x) = 2x for any x ≤ 1/2. Consider a strategy of the Contestant with cutoffs α̂0 (p0 ) and α̂1 (p1 ) such that Contestant accepts the first price p0 iff α ≥ α̂0 (p0 ) and, in the case the game proceeds to the next stage, she accepts the second price p1 iff α ≥ α̂1 (p1 ). Find the necessary and sufficient conditions on α̂0 (p0 ) and α̂1 (p1 ) under which the above strategy is 332 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION played by the contestant in a sequential equilibrium. (You need to find two equations, one contains only α̂0 (p0 ) and p0 and the other contains only α̂ (p1 ) and p1 as variables.) [Hint: Some of the following equalities may be useful: for any x ≥ y, Pr (1/2α ≤ x|1/2α > y) = 2 (x − y) / (1 − 2y); for any a ≥ 1, Pr (α ≤ a) = ( ) 1−(1/2)a−1 , and for any a ≥ b ≥ 1, Pr (α ≥ b|α ≤ a) = 1/2b−1 − 1/2a−1 / (1 − 1/2a−1 ).] Answer: As in part (a), if Case 1 contains 1M$, then Contestant accepts any offer and Banker offers 0, each getting 0. If Case 1 contains 0M$, then again Contestant accepts p1 iff p1 ≥ 1/2α , i.e. iff α ≥ α̂1 (p1 ) where p1 = 1/2αˆ 1 (p1 ) . (Of course, α̂1 (p1 ) = − log (p1 ) / log (2), but you do not need to obtain this explicit solution.) Towards finding the equation for α0 , we need to find the price p1 (p0 ) that will be offered in a sequential equilibrium. Given that p0 is rejected, Banker knows that α < α̂0 (p0 ), or 1/2α > 1/2α̂0 (p0 ) . Write y = 1/2α̂0 (p0 ) . His expected utility from offering p1 is UB (p1 |p0 ) = Pr (1/2α ≤ p1 |1/2α > y) (1/2 − p1 ) 2 (p1 − y) = (1/2 − p1 ) , 1 − 2y which is maximized at p1 (p0 ) = 1/4 + y/2 = 1/4 + 1/2αˆ 0 (p0 )+1 . Given p0 , the types α ≥ α̂0 (p0 ) prefer to trade at p0 rather than waiting for p1 (p0 ) the next period, and the types α ∈ (α̂1 (p1 (p0 )) , α̂0 (p0 )) wait for p1 (p0 ) (and trade at that price) rather than trading at p0 . As explained in the class, this implies that the type α̂0 (p0 ) is indifferent between these two options: 1/α̂0 (p0 ) p0 = (2/3) (p1 (p0 ))1/α̂0 (p0 ) , 16.5. EXERCISES WITH SOLUTIONS 333 where the left-hand side is the payoff from accepting p0 and the right-hand side is the expected payoff from rejecting p0 and accepting p1 (p0 ) if Case 1 contains 0. By taking the powers on both sides and substituting the value of p1 (p0 ), we obtain p0 = (2/3)α̂0 (p0 ) p1 (p0 ) ( ) = (2/3)α̂0 (p0 ) 1/4 + 1/2αˆ 0 (p0 )+1 . (You can simplify this equation a bit more if you want, but you are not asked to do so. Also, note that we specified all the actions and beliefs except for the value of the initial price, which will be the price that maximizes the expected payoff of the banker given what we described so far.) 3. [Midterm 2, 2004] Consider two pharmaceutical companies, who are competing to develop a new drug, called Xenodyne. Simultaneously, each firm i invests xi amount of money in R&D. The firm that invests more develops the drug first; if they invest equal amounts, then each firm is equally likely to develop the drug first. (The probability that they develop the drug at the same time is zero.) The firm that develops the drug first obtains a patent for the drug and becomes a monopolist in the market for Xenodyne. The other firm ceases to exist, obtaining the payoff of zero, minus its investment in R&D. The monopolist then produces Q ≥ 0 units of Xenodyne at marginal cost ci and sells it at price P = max {1 − Q, 0}, obtaining payoff of (P − ci ) Q, minus its investment in R&D, where Q is chosen by the monopolist. Here, ci is privately known by firm i, and c1 and c2 are independently and identically distributed by uniform distribution on [0, 1]. (a) (10) Write this game formally as a static Bayesian game. ANSWER: • Type space: T1 = T2 = [0, 1]. • Action space: A1 = A2 = [0, ∞) × [0, ∞)[0,∞)×[0,∞) , where an action is a pair (xi , Qi ), where Qi is a function of x1 and x2 . 334 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION • ⎧ ⎪ if xi > xj ⎪ ⎨ P (Qi (x1 , x2 )) Qi (x1 , x2 ) − xi ui (x1 , Q1 , x2 , Q2 ) = P (Qi (x1 , x2 )) Qi (x1 , x2 ) /2 − xi if xi = xj ⎪ ⎪ ⎩ −xi otherwise. • pcj |ci is uniform distribution on [0, 1]. (b) (15) Find a symmetric Bayesian Nash equilibrium of the above game in which each player’s investment is of the form xi = a (1 − ci )3 +b for some parameters a and b. [If you can, you may want to solve part (c) first.] ANSWER: See part (c). (c) (10) Show that the equilibrium in part (b) is the only Bayesian Nash equi­ librium in which both firms act sequentially rationally and in which xi is an increasing, differentiable function of (1 − ci ) . ANSWER: By sequential rationality, a monopolist produces Qi = 1 − ci /2 in order to maximize its profit, obtaining payoff of (1 − ci )2 /4, minus the investment in R&D. Define new variable θ i = 1 − ci which is also independently and identically distributed with uniform distrib­ ution on [0, 1]. Let x be the strategy played in a symmetric equilibrium, so that x1 = x (θ1 ) and x2 = x (θ2 ). Now, the expected payoff of firm i is E [ui ] = θ2i Pr (xi > xj ) − xi . 4 This is because with probability Pr (xi > xj ) the firm will become monopolist and get the monopoly profit θ2i /4 and will pay the investment cost xi with probability 1. Since x is increasing, Pr (xi = xj ) = 0. Now, ( ) Pr (xi > xj ) = Pr (xi > x (θj )) = Pr θj < x−1 (xi ) = x−1 (xi ) . 16.5. EXERCISES WITH SOLUTIONS 335 Hence, θ2i −1 E [ui ] = x (xi ) − xi . 4 Therefore, the first-order condition for maximization is 0= ∂E [ui ] θ2 1 = i ' − 1, 4 x (θi ) ∂xi showing that x' (θi ) = θ2i , 4 and therefore θ3i + const, 12 where the const = 0, so that x (0) = 0. x (θi ) = 4. [Final 2002] Find a sequential equilibrium in the following game. .5 .1 .4 1 2,1,0 2 3 2 0,1,0 0,0,1 1 0,0,1 2 0,0,1 0,2,0 1,0,0 0,2,2 2 0,0,0 1,1,3 3,3,3 Solution: There is a unique sequential equilibrium in this game. Clearly, 1 must exit at the beginning and 2 has to go in on the right branch as he does not have any choice. The behavior at the nodes in the bottom layer is given by sequential rationality as in the figure below. Write α for the probability that 2 goes in in the center branch, β for the probability that 3 goes right, and μ for the probability 3 assigns to the center branch. In equilibrium, 3 must mix (i.e., β ∈ (0, 1)). [Because if 3 goes left, then 2 must exit at the center branch, hence 3 must assign probability 1 to the node at the right (i.e., μ = 0), and hence she should play 336 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION right –a contradiction. Similarly, if 3 plays right, then 2 must go in at the center branch. Given his prior beliefs (.4 and .1), μ = 4/5, hence 3 must play left – a contradiction again.] In order 3 to mix, she must be indifferent, i.e., 1 = 0μ + 3 (1 − μ) , hence μ = 2/3. By the Bayes’ rule, we must have μ= .4α = 2/3, .4α + .1 i.e., α = 1/2. That is player 2 must mix on the center branch, and hence she must be indifferent, i.e., 1 = 2β. That is, β = 1/2. The equilibrium is depicted in the following figure. .5 .1 .4 1 2 2 α = 1/2 2,1,0 3 0,1,0 μ =2/3 0 0,0,1 1−μ β = 1/2 1 0,0,1 2 0,0,1 0,2,0 1,0,0 0,2,2 2 0,0,0 1,1,3 3,3,3 16.5. EXERCISES WITH SOLUTIONS 337 5. [Final 2002] We have a Judge and a Plaintiff. The Plaintiff has been injured. Sever­ ity of the injury, denoted by v, is the Plaintiff’s private information. The Judge does not know v and believes that v is uniformly distributed on {0, 1, 2, . . . , 99} (so that the probability that v = i is 1/100 for any i ∈ {0, 1, . . . , 99}). The Plaintiff can verifiably reveal v to the Judge without any cost, in which case the Judge will know v. The order of the events is as follows. First, the Plaintiff decides whether to reveal v or not. Then, the Judge rewards a compensation R. The payoff of the Plaintiff is R − v, and the payoff of the Judge is − (v − R)2 . Everything described so far is common knowledge. Find a sequential equilibrium. Solution: Consider a sequential equilibrium with strategy profile (s∗ , R∗ ), where s∗ (v) ∈ {v, N R} determines whether the Plaintiff of type v reveals v or does Not Reveal, and R∗ determines the reward, which is a function from {N R, 0, 1, . . . , 99}. Given the Judge’s preferences, if the Plaintiff reveals her type v, the Judge will choose the reward as R∗ (v) = v and R∗ (N R) = E [v|N R] . In equilibrium, the Plaintiff gives her best response to R∗ at each v. Hence, she must reveal her type whenever v > R∗ (N R), and she must not reveal her type whenever v < R∗ (N R). Suppose that R∗ (N R) > 0. Then, s∗ (0) = N R, and hence N R is reached with positive probability. Thus, R∗ (N R) = E [v|s∗ (v) = N R] ≤ E [v|v ≤ R∗ (N R)] ≤ R∗ (N R) /2, which could be true only when R∗ (N R) = 0, a contradiction. Therefore, we must have R∗ (N R) = 0, and thus s∗ (v) = v at each v > 0. There are two equilibria (more or less equivalent). 338 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION • s∗ (v) = v for all v; R∗ (v) = v; R∗ (N R) = 0, and the Judge puts probability 1 to v = 0 whenever the Plaintiff does not reveal her type. • s∗ (0) = N R; s∗ (v) = v for all v > 0; R∗ (v) = v; R∗ (N R) = 0, and the Judge puts probability 1 to v = 0 whenever the Plaintiff does not reveal her type. 6. [Final 2001, Make Up] This question is about a game between a possible appli­ cant (henceforth student) to a Ph.D. program in Economics and the Admission Committee. Ex-ante, Admission Committee believes that with probability .9 the student hates economics and with probability .1 he loves economics. After Nature decides whether student loves or hates economics with the above probabilities and reveals it to the student, the student decides whether or not to apply to the Ph.D. program. If the student does not apply, both the student and the committee get 0. If student applies, then the committee is to decide whether to accept or reject the student. If the committee rejects, then committee gets 0, and student gets -1. If the committee accepts the student, the payoffs depend on whether the student loves or hates economics. If the student loves economics, he will be successful and the payoffs will be 20 for each player. If he hates economics, the payoffs for both the committee and the student will be -10. Find a separating equilibrium and a pooling equilibrium of this game. Solution: A separating equilibrium: 16.5. EXERCISES WITH SOLUTIONS 339 (-10,-10) Accept Apply {0} Reject Don’t .9 (-1,0) Hate (0,0) Love .1 Apply (20,20) {1} Accept Reject Don’t (-1,0) (0,0) A pooling equilibrium: (-10,-10) Apply {.9} Accept Reject Don’t .9 (-1,0) Hate (0,0) Love .1 Apply {.1} (20,20) Accept Reject Don’t (-1,0) (0,0) 7. [Final 2001] We have an employer and a worker, who will work as a salesman. The worker may be a good salesman or a bad one. In expectation, if he is a good salesman, he will make $200,000 worth of sales, and if he is bad, he will make only $100,000. The employer gets 10% of the sales as profit. The employer offers a wage 340 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION w. Then, the worker accepts or rejects the offer. If he accepts, he will be hired at wage w. If he rejects the offer, he will not be hired. In that case, the employer will get 0, the worker will get his outside option, which will pay $15,000 if he is good, $8,000 if he is bad. Assume that all players are risk-neutral. (a) Assume that the worker’s type is common knowledge, and compute the subgame­ perfect equilibrium. Solution: A worker will accept a wage iff it is at least as high as his outside option, and the employer will offer the outside option – as he still makes profit. That is, 15,000 for the good worker 8,000 for the bad. (b) Assume that the worker knows his type, but the employer does not. Employer believes that the worker is good with probability 1/4. Find the sequential equilibrium. Solution: Again a worker will accepts an offer iff his wage at least as high as his outside option. Hence if w ≥ 15, 000 the offer will be accepted by both types, yielding U (w) = (1/4) (.1) 200, 000 + (3/4) (.1) 100, 000 − w = 12, 500 − w < 0 as the profit for the employer. If 8, 000 ≤ w < 15, 000, then only the bad worker will accept the offer, yielding U (w) = (3/4) [(.1) 100, 000 − w] = (3/4) [10, 000 − w] as profit. If w < 0, no worker will accept the offer, and the employer will get 0. In that case, the employer will offer w = 8, 000, hiring the bad worker at his outside option. (c) Under the information structure in part (b), now consider the case that the employer offers a share s in the sales rather than the fixed wage w. Compute the sequential equilibrium. Solution: Again a worker will accept the share s iff his income is at least as high as his outside option. That is, a bad worker will accept s iff 100, 000s ≥ 8, 000 16.5. EXERCISES WITH SOLUTIONS 341 i.e., s ≥ sB = 8, 000 = 8%. 100, 000 A good worker will accept s iff s ≥ sG = 15, 000 = 7.5%. 200, 000 In that case, if s < sG no one will accept the offer, and the employer will get 0; if sG ≤ s < sB , the good worker will accept the offer and the employer will get (1/4) (10% − s) 200, 000 = 50, 000 (10% − s) , and if s ≥ sB , each type will accept the offer and the employer will get (10% − s) [(1/4) 200, 000 + (3/4) 100, 000] = 125, 000 (10% − s) . Since 125, 000 (10% − sB ) = 2%125, 000 = 2, 500 is larger than 50, 000 (10% − sG ) = 2.5%50, 000 = 1, 250, he will offer s = sB , hiring both types. 8. [Final 2001, Make Up] As in the previous question, we have an employer and a worker, who will work as a salesman. Now the market might be good or bad. In expectation, if the market is good, the worker will make $200,000 worth of sales, and if the market is bad, he will make only $100,000 worth of sales. The employer gets 10% of the sales as profit. The employer offers a wage w. Then, the worker accepts or rejects the offer. If he accepts, he will be hired at wage w. If he rejects the offer, he will not be hired. In that case, the employer will get 0, the worker will get his outside option, which will pay $12,000. Assume that all players are risk-neutral. (a) Assume that whether the market is good or bad is common knowledge, and compute the subgame-perfect equilibrium. ANSWER: A worker will accept a wage iff it is at least as high as his outside option 12,000. If the market is good, the employer will offer the outside option w = 12, 000, and make 20, 000 − 12, 000 = 8, 000 profit. If the market is bad, the return 10,000 is lower than the worker’s outside option, and the worker will not be hired. 342 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION (b) Assume that the employer knows whether the market is good or bad, but the worker does not. The worker believes that the market is good with probability 1/4. Find the sequential equilibrium. ANSWER: As in part (a). [We will have a separating equilibrium.] (c) Under the information structure in part (b), now consider the case that the employer offers a share s in the sales rather than the fixed wage w. Compute a sequential equilibrium. ANSWER: Note that, since the return is 10% independent of whether the market is good or bad, the employer will make positive profit iff s < 10%. Hence, except for s = 10%, we must have a pooling equilibrium. Hence, at any s, the worker’s income is [(1/4) 200, 000 + (3/4) 100, 000] s = 125, 000s. This will be at least as high as his outside option iff s ≥ s∗ = 12, 000 = 9.6% < 10%. 125, 000 Hence an equilibrium: the worker will accept an offer s iff s ≥ s∗ , and the employer will offer s∗ . The worker’s beliefs at any offer s is that the market is good with probability 1/4. [Note that this is an inefficient equilibrium. When the market is bad, the gains from trade is less than the outside option.] There are other inefficient equilibria where there is no trade (i.e., worker is never hired). In any such equilibrium, worker take any high offer as a sign that the market is bad, and does not accept an offer s unless s ≥ 12, 000/100, 000 = 12%, and the employer offers less than 12%. When the market is good, in any such pure strategy equilibrium, he must in fact be offering less than s∗ . (why?) For instance, employer offers s = 0 independent of the market, and the worker accept s iff s > 12%. 9. [Final 2001] A risk-neutral entrepreneur has a project that requires $100,000 as an investment, and will yield $300,000 with probability 1/2, $0 with probability 1/2. There are two types of entrepreneurs: rich who has a wealth of $1,000,000, and 16.5. EXERCISES WITH SOLUTIONS 343 poor who has $0. For some reason, the wealthy entrepreneur cannot use his wealth as an investment towards this project. There is also a bank that can lend money with interest rate π. That is, if the entrepreneur borrows $100,000 to invest, after the project is completed he will pay back $100, 000 (1 + π) – if he has that much money. If his wealth is less than this amount at the end of the project, he will pay all he has. The order of the events is as follows: • First, bank posts π. • Then, entrepreneur decides whether to borrow ($100,000) and invest. • Then, uncertainty is resolved. (a) Compute the subgame perfect equilibrium for the case when the wealth is common knowledge. ANSWER: The rich entrepreneur is always going to pay back the loan in full amount, hence his expected payoff from investing (as a change from not investing) is (0.5)(300, 000) − 100, 000 (1 + π) . Hence, he will invest iff this amount is non-negative, i.e., π ≤ 1/2. Thus, the bank will set the interest rate at π R = 1/2. The poor entrepreneur is going to pay back the loan only when the project succeeds. Hence, his expected payoff from investing is (0.5)(300, 000 − 100, 000 (1 + π)). He will invest iff this amount is non-negative, i.e., π ≤ 2. Thus, the bank will set the interest rate at π P = 2. CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 344 (b) Now assume that the bank does not know the wealth of the entrepreneur. The probability that the entrepreneur is rich is 1/4. Compute the sequential equilibrium. ANSWER: As in part (a), the rich type will invest iff π ≤ π R = .5, and the poor type will invest iff π ≤ π P = 2. Now, if π ≤ π R , the bank’s payoff is 1 3 1 1 100, 000 (1 + π) + 100, 000 (1 + π) + 0 − 100, 000 4 4 2 2 5 = 100, 000 (1 + π) − 100, 000 8 5 ≤ 100, 000 (1 + π R ) − 100, 000 8 5 1 = 100, 000 (1 + 1/2) − 100, 000 = − 100, 000 < 0. 8 16 U (π) = If π R < π ≤ π P , the bank’s payoff is 3 1 1 100, 000 (1 + π) + 0 − 100, 000 4 2 2 3 = 100, 000 (π − 1) , 8 U (π) = which is maximized at π P , yielding 38 100, 000. If π > π P , U (π) = 0. Hence, the bank will choose π = π P . 16.6 Exercises 1. [Homework 5, 2011] In the following game, for each action of player 2, find a sequential equilibrium in which player 2 plays that action: 1 1/4 1 out 2 0 y x 3/4 in L 3 10 in out R 0 1 2 R 1 0 L 3 0 1 1 16.6. EXERCISES 345 2. [Final 2011] Find a sequential equilibrium of the following game. Verify that you have indeed a sequential equilibrium. (1,1) b 1/3 1/3 a y 1 1 (0,0) x 2 a x y b 1/3 (-1,-1) a b (2,-2) (0,0) (1,1) (0,0) x y (1,1) (2,2) 3. [Final 2011] Consider the following version of Yankee Swap Game, played by Alice, Bob, and Caroline. There are 3 boxes, namely A, B, and C, and three prizes x, y, and z. The prizes are put in the boxes randomly, so that any combination of prizes is equally likely, and the boxes are closed without showing their contents to the players. First, Alice is to open box A, revealing its content observable. Then, in the alphabetical order, Bob and Caroline are to open the box with their own initial, making its content observable, and either keep the content as is or swap its content with the content of a box that has been opened already. Finally, Alice is given the option of swapping the content of her box with the content of any other box, ending the game when each player gets the prize in their own box. (a) Assume that it is commonly known that, for each player, the payoff from x, y, and z are 3, 2, and 0, respectively. Find a subgame-perfect Nash equilibrium. (b) Now assume that it is commonly known that the preferences of Bob and Caroline are as in part (a), but the preferences of Alice are privately known by herself. With probability 1/2, her utility function is as above, but with probability 1/2 she gets payoffs of 2, 3, and 0 from x, y, and z, respectively. Find a sequential equilibrium of this game. 346 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 4. [Final 2006] Consider the following game 1 2 E 1 A 1−π π a X D d (0,0) (-1,1) (1,0) 1 2 E A (0,2) 1 a (0,2) D (-1,1) where π is the probability that Nature selects the lower branch. (a) (10 pts) Find a sequential equilibrium for π = 3/4. (b) (15 pts) Find a sequential equilibrium for π = 1/4. 5. [Final 2005] The following game describes a situation in which Player 2 is not sure that she is playing a game with Player 1, i.e., she is not sure that Player 1 exists. 1 A 2 D .8 d a 2 1 F -1,3 P 0 2 1 0 .2 a 3 1 -1,3 d 0 2 (a) (20 points) Compute a perfect Bayesian Nash equilibrium of this game. (b) (5 points) Breifly discuss the equilibrium in (a) from Player 2’s point of view. 16.6. EXERCISES 347 6. [Final 2005] We have two players, Host and Contestant. There are three doors, L, M, and R. • Nature puts a car behind one of these doors, and goats behind the others. The probability of having the car is same for all doors. Host knows which door, but Contestant does not. • Then, Contestant selects a door. • Then, Host must open one of the two doors that are not selected by Contestant and show Contestant what Nature put behind that door. • Then, Contestant chooses any of the three doors, and receives whatever is behind that door. Payoffs for Contestant and Host are (1,-1) if Contestant receives a car, and (0,0) if he receives a goat. Compute a perfect Bayesian Nash equilibrium of this game. Verify that this is indeed a PBE. [Hint: Any strategy for Host in which he never shows the car is part of some PBE.] 7. [Final 2004] Find a sequential equilibrium of the following game. 1 .4 2 A α 1 0 δ D 2 1 0 0 .6 1 2 a α 1 2 δ d 2 2 3 1 8. [Final 2004] A soda company, XC, introduces a new soda and wants to sell it to a representative consumer. The soda may be either Good or Bad. The prior probability that it is Good is 0.6. Knowing whether the soda is Good or Bad, 348 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION the soda company chooses an advertisement level for the product, which can be either an Ad Blitz, which costs the company c, or No Advertisement, which does not cost anything. Observing how strongly the company advertises the soda, but without knowing whether the soda is Good or Bad, the representative consumer decides whether or not to buy the product. After subtracting the price, the payoff of representative consumer from buying the soda is 1 if it is Good and −1 if it is Bad. His payoff is 0 if he does not buy the soda. If the soda is Good and representative consumer buys it (and therefore learns that the soda is Good), then the company sells the soda to other future consumers, enjoying a high revenue of R. If the soda is Bad and the representative consumer buys it, the company will have only a small revenue r. If the representative consumer does not buy the soda, the revenue of the company is 0. Assume that 0 < r < c < R. (a) Write this game as a signaling game. (Draw the game tree.) (b) Find a separating equilibrium. (Verify that it is a sequential equilibrium.) (c) Find a pooling equilibrium. (Verify that it is a sequential equilibrium.) (d) Find a sequential equilibrium for the case that the prior probability of Good is 0.4. (e) Find a sequential equilibrium for the case that 0 < c < r < R (and the prior probability of Good is 0.6). 9. [Final 2004] In this question, you are asked to help me to determine the letter grades! We have a professor and a potential student. There are two types of students, H and L. The student knows his type, but the professor does not. The prior probability of type H is π ∈ [0, 1]. The events take place in the following order. • First, the professor determines a cutoff value γ ∈ [0, 100]. • Observing γ and his type, the student decides whether to take the class. • If the student does not take the class, the game ends; the professor gets 0, and the student gets Wt , where t ∈ {H, L} is his type and 0 < WL < WH < 100. 16.6. EXERCISES 349 • If the student takes the class, then he chooses an effort level e and takes an exam. His score in the exam is s = e if t = L and s = 2e if t = H; i.e., a high type student scores higher for any effort level. • The student gets a letter grade g= A if s ≥ γ B otherwise. • The student’s payoff is 100 − e/2 if he gets g = A, and −e/2 if he gets B. The professor’s payoff is s. (a) Consider a prestigious institution with high standards, where π is high, and WH is not too high. In particular, π > .5 (100 − WL ) / (100 − WH ) and WH < (100 + WL ) /2. Compute a sequential equilibrium for this game. (b) Consider a prestigious institution with spoiled kids, where both π and WH are high. In particular, WH > (100 + WL ) /2 and π > 1−2 (100 − WH ) / (100 − WL ). Compute a sequential equilibrium for this game. (c) Consider a lower-tier college, where both π and WH are low; π < .5 (100 − WL ) / (100 − WH ) and WH < (100 + WL ) /2. Compute a sequential equilibrium for this game. (d) Assuming that WL is the same at all three institutions, rank the exam scores in (a), (b) and (c). (e) (0 points) What cutoff value would you choose if you were a professor at MIT? 10. [Final 2002 Make Up] Consider the following game. 350 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION (3,1) T L (2,1/2) T B L B B C T L 3 1 R {.1} T T 2 0 1,0 T {.4} (0,1/2) 1 1 3 0 0,0 R B B (1,1) B {.5} A B 0 1 R 2 1 (a) Find a pooling sequential equilibrium. (b) Find a sequential equilibrium in which for each signal there is a type who send that signal. 11. [Final 2002 Make Up] We have a Defendant and a Plaintiff, who injured the Defen­ dant. If they go to court, the Defendant will pay a cost c ∈ (0, 1) to the court and a reward d to the Plaintiff, depending on the severity of the injury. [Here c and d are measured in terms of utiles, where a utile is $1M.] The Plaintiff knows d but the Defendant does not; she believes that d = 1 with probability π > c and d = 2 with probability 1 − π. The Plaintiff ask a settlement s, and the Defendant either accepts, in which case she pays s (utile) to the Plaintiff, or rejects in which case they go to court. Everything described up to here is common knowledge. Find a sequential equilibrium. 12. [Final 2000] Consider the following private-value auction of a single object, whose value for the seller is 0. there are two buyers, say 1 and 2. The value of the object for each buyer i ∈ {1, 2} is vi so that, if i buys the object paying the price p, his payoff is vi − p; if he doesn’t buy the object, his payoff is 0. We assume that v1 and v2 are independently and identically distributed uniformly on [v, 1] where 0 ≤ v < 1. (a) We use sealed-bid first-price auction, where each buyer i simultaneously bids bi , and the one who bids the highest bid buys the object paying his own bid. 16.6. EXERCISES 351 Compute the symmetric Bayesian Nash equilibrium in linear strategies, where bi = a + cvi . Compute the expected utility of a buyer for whom the value of the object is v. (b) Now assume that v1 and v2 are independently and identically distributed uniformly on [0, 1]. Now, in order to enter the auction, a player must pay an entry fee φ ∈ (0, 1). First, each buyer simultaneously decides whether to enter the auction. Then, we run the sealed-bid auction as in part (a); which players entered is now common knowledge. If only one player enters the auction any bid b ≥ 0 is accepted. Compute the symmetric sequential equilibrium where the buyers use the linear strategies in the auction if both buyer enter the auction. Anticipating this equilibrium, which entry fee the seller must choose? [Hint: In the entry stage, there is a cutoff level such that a buyer enters the auction iff his valuation is at least as high as the cutoff level.] 13. [Final 2000] Consider a worker and a firm. Worker can be of two types, High or Low. The worker knows his type, while the firm believes that each type is equally likely. Regardless of his type, a worker is worth 10 for the firm. The worker’s reservation wage (the minimum wage that he is willing to accept) depends on his type. If he is of high type his reservation wage is 5 and if he is of low type his reservation wage is 0. First the worker demands a wage w0 ; if the firm accepts it, then he is hired with wage w0 , when the payoffs of the firm and the worker are 10 − w0 and w0 , respectively. If the firm rejects it, in the next day, the firm offers a new wage w1 . If the worker accept the offer, he is hired with that wage, when the payoffs of the firm and the worker are again 10 − w1 and w1 , respectively. If the worker rejects the offer, the game ends, when the worker gets his reservation wage and the firm gets 0. Find a perfect Bayesian equilibrium of this game. 14. [Homework 5, 2004] Compute all sequential equilibria of the following game. 15. [Homework 5, 2004] Consider the following general Beer-Quiche game, where the value of avoiding a fight is α, and the ex-ante probability of strong type is p. For each case below find a sequential equilibrium. 352 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION 1 2 1 1,-5 .5 4,4 .1 .4 5,2 1 -1,4 tw don beer {p} ’t -2,-5 -1,3 1 1 el du don 1+α 0 ’t el ts el 1+α 1 {1-p} ’t 1 du don quiche beer du 1 0 -1,2 du el 1,-5 -1,3 2 0,4 α 0 1 0,2 1 0 1 3,3 2 0 0 quiche don ’t α 1 (a) p = 0.4, and α = 2. (b) p = 0.8, and α = 2. (c) p = 0.8, and α = 1/2. 16. [Homework 5, 2004] Consider a buyer and a seller. The seller owns an object, whose value for himself is c. The value of the object for the buyer is v. Each player knows his own valuation not the other player’s valuation; v and c are independently and identically distributed with uniform distribution on [0, 1]. We have two dates, t = 0, 1. The players discount the future payoffs with δ = .9. Hence, if they trade at t = 0 with price p, the payoffs of seller and the buyer are p − c and v − p, respectively, while these payoffs would be 0.9 (p − c) and 0.9 (v − p), respectively, if they traded at t = 1. If the do not trade at any of these dates, each gets 0. Find a sequential equilibrium of the game in each of the following cases. 16.6. EXERCISES 353 (a) At t = 0, the seller offers a price p0 . If the buyer accepts, trade occurs at price p0 . If the offer is rejected, the game end without possibility of a trade at t = 1. (b) At t = 0, the seller offers a price p0 . If the buyer accepts, trade occurs at price p0 . If the buyer rejects, at t = 1, the seller sets another price p1 . If the buyer accepts the price, the trade occurs at price p1 ; otherwise they do not trade. [Hint: There is an equilibrium in which there is a threshold a (p0 ) such that a buyers buys at t = 0 if his valuation is above a (p0 ), and the threshold and the sellers strategies are "linear," i.e., a (p0 ) = min {αp0 + β, 1} and p0 = Ac + B for some parameters α, β, A, and B.] 17. [Final 2000, Make Up] Two players (say A and B) own a company, each of them owning a half of the Company. They want to dissolve the partnership in the following way. Player A sets a price p. Then, player B decides whether to buy A’s share or to sell his own share to A,in each case at price p. The value of the Company for players A and B are vA and vB , respectively. (a) Assume that the values vA and vB are commonly known. What would be the price in the subgame-perfect equilibrium? (b) Assume that the value of the Company for each player is his own private information, and that these values are independently drawn from a uniform distribution on [0,1]. Compute the sequential equilibrium. 18. Final 2000, Make Up] Consider the following game. 354 CHAPTER 16. DYNAMIC GAMES WITH INCOMPLETE INFORMATION (2,1) (3,1) L R 1 {0.6} (0,0) (1,0) 2 2 (0,0) (2,0) {0.4} L (1,1) 1 R (a) Find a separating equilibrium. (b) Find a pooling equilibrium. (c) Find an equilibrium in which a type of player 1 plays a (completely) mixed strategy. (3,1)