Econ 502 Game Theory 2 - Practice Problems with solutions PDF

Preview

Summary

Practice Problems with solutions...

Description

4

Game Theory Part II: Repeated Games, Bayesian Games, Dynamic Games with Incomplete Information

Problem 4.1. Two herders, i = 1, 2, choose the number of sheep, q1 , q2 , to graze on village commons. Their payoffs are u1 (q1 , q2 ) = q1 (120 − q1 − q2 ), u2 (q1 , q2 ) = q2 (120 − q1 − q2 ). The Nash equilibrium of the game is q1 = q2 = 40 and the quantities that maximize joint payoff is q1 = q2 = 30. (This is solved in the lecture.) Now repeat the game infinitely many times. The herders’ discount factor is δ. Describe a grim-trigger strategy and find the minimum δ above which playing q1 = q2 = 30 is an SPNE outcome. (Hint: if a player were to deviate, (s)he would try to maximize the profit he can get by deviating.) Answer: The Grim trigger strategy is as follows: each player plays qi = 30 to begin with. In all future periods, if the past history is q1 = q2 = 30, continue to play qi = 30. Otherwise, play qi = 40. The NE payoff is ui (40, 40) = 40 ∗ 40 = 1600. The payoff of q1 = q2 = 30 is ui (30, 30) = 1800. If player 2 is following Grim-Trigger and player 1 is considering deviating from the ”equilibrium path” of (30, 30), player 1 would choose q1 that is a best-response to q2 . That is, max q1 (120 − q1 − 30) q1

This gives q1 = 45 and a stage payoff of u(45, 30) = 45 ∗ 45 = 2025. Therefore, following the Grim-Trigger forever gives a player the payoff 1800 + δ 1800 + ... =

1800 1−δ

Deviating in the optimal way gives the player the payoff 2025 + δ 1600 + δ 2 1600 + ... = 2025 + To make sure a player doesn’t want to deviate ever, we need δ1600 1800 ≥ 2025 + 1−δ 1−δ Hence 1800 − δ1600 ≥ 2025 − 2025δ

14

δ1600 1−δ

So 425δ ≥ 225 This gives δ≥

225 9 = . 17 425

Problem 4.2. Use the Grim-Trigger strategy and find conditions on the discount factor δ under which cooperation, i.e. playing the strategy profile (U, L) forever, is played as an SPNE outcome in the infinitely repeated games with the following stage games. P2

P1

P2

L

R

U

(2, 2)

(0, 4)

D

(4, 0)

(1, 1)

P1

P2

L

R

U

(3, 4)

(0, 7)

D

(5, 0)

(1, 2)

P1

L

R

U

(3, 2)

(0, 1)

D

(7, 0)

(2, 1)

Answer: For each of the game, consider the following strategy profile. Player 1: Player 1 plays U first, in all future rounds, if in the past only (U, L) has been played, play U in this round. Otherwise, play D. Player 2 Player 2 plays L first, in all future rounds, if in the past only (U, L) has been played, play L in this round. Otherwise, play R. Note that the strategy profile (D, R) is a Nash equilibrium in the stage game. In any history where a deviation has happened, D is a best-response to R and vice versa. We only need to check that players do not want to deviate from (U, L). The Left Game Since the first game is symmetric, we only need to consider the incentive of player 1. For each player, following the strategy profile results in a sequence of payoff of 2, 2, 2, ... Deviating results in a sequence of payoff of 4, 1, 1, 1, ... 15

(If player 1 deviates, he gets 4 in the current period ((D, L) is the outcome). In the future, player 2, who follows Grim-Trigger strategy, will play R forever. And Player 1’s best response to player 2 playing R forever is to play D forever. This results in the outcome (D, R), and a payoff sequence 1, 1, 1, ... forever.) Player evaluates sequence of payoffs by discounting using δ. Player does not want to deviate from the grim-trigger strategy if and only if 2 + δ 2 + δ 2 2 + ... ≥ 4 + 1 · δ + 1 · δ 2 + ... That is,

1 2 ≥4+δ 1−δ 1−δ

This solves to δ ≥ 2/3. The Middle Game We need to separately check that player 1 and 2 do not want to deviate from (U, L). For player 1, following the strategy profile results in a payoff sequence of 3, 3, 3, .... Deviating results in a payoff of 5, 1, 1, 1, .... Therefore, player 1 doesn’t want to deviate if 3 + 3δ + 3δ 2 + ... ≥ 5 + 1 · δ + 1 · δ 2 + ... That is,

3 δ ≥5+ 1−δ 1−δ

This solves to

1 δ≥ . 2 For player 2, following Grim-Trigger gives 4 forever. Deviating results in the payoff

sequence 7, 2, 2, 2, .... Therefore, player 2 does not want to deviate if 4 + 4δ + 4δ 2 + ... ≥ 7 + 2δ + 2δ 2 + ... That is,

4 2 ≥7+δ 1−δ 1−δ

which solves to

3 δ≥ . 5 For both players to cooperate, we need δ ≥ max{1/2, 3/5}. 16

The Right Game Observe that player cannon gain by deviating. We only need to discuss player 1. Player 1 doesn’t want to deviate whenever 3 + 3δ + 3δ 2 + ... ≥ 7 + 2δ + 2δ 2 + ... That is,

3 2 ≥7+δ 1−δ 1−δ

This solves to δ ≥ 4/5. Lemma 4.1. For any number 0 < δ < 1 and any number a, we have a + δa + δ 2 a + ... =

a 1−δ

Proof. Let S = a + δa + δ 2 a + ... Then δS = δa + δ 2 a + ... We have S − δS = a Hence (1 − δ)S = a. Hence S = a/(1 − δ).

Problem 4.3. Two neighboring homeowners, i = 1, 2 simultaneously choose how many hours li to sepnd maintaining a beautiful lawn. Player i’s average benefit per hour of work on landscaping is

lj . 2 Player 2’s opportunity cost of an hour of landscaping work is 4. Suppose that player 1’s 10 − li +

hourly opportunity cost is either 3 or 5 and that this cost is player 1’s private information. Player 2 thinks that with probability 50% player 1’s hourly opportunity cost is 3. a. Write down the best-response function of each player-type. (3pts) b. Solve for the Bayesian-Nash equilibrium. (3pts) 17

c. Which type of player 1 would like to send a truthful signal to player 2 if it could? Which type would like to hide his his or her private information? (3pts) Solution a. The low type player 1 solves max(10 − lLC − l2 /2)lLC − 3lLC lLC

FOC gives 10 − 2lLC − l2 /2 − 3 = 0 Therefore, the best-response function is lLC = 3.5 + l2 /4 for the low-cost type of player 1. Similarly, the best-response function is lHC = 2.5 + l2 /4 for the high-cost type, and l2 = 3 + l1 /4 for Player 2, where l1 = 0.5lLC + 0.5lHC is the average for Player 1. ∗ ∗ b. Solving these equations yields lLC = 4.5, lHC = 3.5 and l2∗ = 4.

c. If the low-cost type signals his type, then the corresponding best responses will be l1 = 3.5 + l2 /4 l2 = 3 + l1 /4 This solves to l1 = 68/15 and l2 = 62/15. Therefore, the equilibrium payoff for player 1 when his type is known is u1 = (10 − (68/15) + (62/15)/2) ∗ (68/15) − 3 ∗ (68/15) = 20.55 The low-cost type of player 1 earns 20.25 in the BayesianNash equilibrium and 20.55 in the full-information game, so would prefer to signal its type if it could. Similar calculations show that the high-cost player would like to hide its type.

Problem 4.4. In Blind Texan Poker, player 2 draws a card from a standard deck and places it against her forehead without looking at it but so player 1 can see it. Player 1 moves first, deciding whether to stay or fold. If player 1 folds, he must pay player 2 $50, and the game ends. If player 1 stays, the action goes to player 2. Player 2 can fold or call. If player 2 folds, she must pay player 1 $50. If player 2 calls, the card is examined. If it is a low card (2-8), player 2 pays player 1 $x. If it is a high card (9,10,J,Q,K,A), player 1 pays player 2 $x. 18

1. Draw the extensive form of the game. 2. Are there value(s) of x such that there is an equilibrium in which player 1 always stays regardless of the types? If so, find such an equilibrium (please specify both players’ strategies and player 2’s beliefs), if not, explain why not. Solution: If player 1 always stays, player 2’s belief that he draws a high card will be 6/13. Player 2’s expected payoff for staying is then E[U2 (stay)|P1 stays] = 6/13x + 7/13(−x) = −x/13. Player 2’s expected payoff for folding is −50. If −x/13 > −50, then it’s best for player 2 to stay. However, this makes it non-optimal for Low type player 1 to stay. So x < 650 wouldn’t support ”player 1 always stays” as an equilibrium. If −x/13 ≤ −50, then it’s best for player 2 to fold. Given player 2 folds with probability 1, both types of player 1 would optimally stay. Hence when x ≥ 650, the following is a pooling PBE: Player 1 always stays. Player 2 always folds. P (High|stay) = 6/13. Problem 4.5. Consider the following situation: There are 2 firms, an incumbent, player 1, and a potential entrant, player 2. The incumbent can choose to build a new factory B or not D, while the potential entrant can enter, E, or remain passive, D. The incumbents construction costs, c, of building the new factory can either be high, cH , or low, cL , i.e. cH > cL . If the construction costs are high the payoff will be as follows: while low construction Player 2

Player 1

E

D

B

0, −1

2, 0

D

2, 1

3, 0

costs will imply that the payoffs are as follows: Player 2

Player 1

E

D

B

3, −1

5, 0

D

2, 1

3, 0

19

a. What is the Nash equilibrium if c = cH ? b. What is the Nash equilibrium if c = cL ? Assume that only the incumbent knows his construction costs. The potential entrant believes that with probability p1 the construction cost is high, c = cH . c. Find the Bayesian Nash equilibrium for p1 < 1/2. d. Find the Bayesian Nash equilibrium for p1 > 1/2 Solution: a. It is easy to see that, B is a strictly dominated strategy of player 1 and given that firm 1 plays D it is optimal for firm 2 to play E. Hence the unique Nash equilibrium of the game of c = cH is for firm 1 not to build and firm 2 to enter. b. Again, it is easy to see that, D is a strictly dominated strategy of player 1 and given that firm 1 plays B it is optimal for firm 2 to play D. Hence the unique Nash equilibrium of the game of c = cL is for firm 1 to build and firm 2 to remain passive. c. A strategy for player 1 must specify what the high type player 1 would do and what the low type player 1 would do. So we represent the set of player 1’s strategy as {BB, BD, DB, DD} where BD means the High type player 1 plays B and the low type player 1 plays D, etc. Since it is a dominant strategy for High type to play D and a dominant strategy for the low type to play B, player 1’s strategy that can possibly be in an equilibrium is simply DB. Player 2’s expected utility to play E given player 1 plays DB is then 2p1 − 1 while his expected utility to play D is zero. Hence player 2 will play E when 2p1 −1 > 0 or p1 > 1/2. The BNE when p1 > 1/2 is (DB, E) d. On the other hand, when p1 < 1/2 we have 0 > 2p1 − 1, hence player 2 will play D. The BNE in this case is (DB, D). 20

Problem 4.6. Consider the following game depicted in Figure 2: You want to buy a used-car which may be either good or bad (a lemon). A good car is worth H and a bad one L dollars. You cannot tell a good car from a bad one but believe a proportion q of cars are good. The car you are interested in has a sticker price p The dealer knows quality but you dont. The bad car needs additional work that costs c to make it look like good. The dealer decides whether to put a given car on sale or not You decide whether to buy or not Assume H >p>L

page.5

Signaling Games: Used-Car Market Yes 0, 0

Hold

D

good

Offer

No

(q)

Nature

0, 0

Y

(1 − q)

bad

p, H − p

Yes

p − c, L − p

0, 0 Hold

D

Offer No

−c, 0

Figure 2: Market for Used-Cars

a. Find the pooling equilibria of the game and the range of parameters under which such equilibria exist. (Good and Bad car dealers play the same strategy) b. Find the separating equilibria of the game and the range of parameters under which such equilibria exist. (Good and Bad car dealers play differently) c. Find the hybrid equilibria in which the good dealer always offers when H = 3000, L = 0, q = 0.5, p = 2000, c = 1000. Answer

21

a. There are two types of pooling equilibria. One is that the dealer always offers regardless of whether the car is good. If the dealer always offers, the Bayes law implies that the buyer would believe an offered car is good with probability P (good|offer) P (offer|good)P (good) = P (offer|good)P (good) + P (offer|bad)P (bad) 1×q = q. = 1 × q + 1 × (1 − q) The expected payoff to buy the car with this belief is V = q(H − p) + (1 − q)(L − p) Therefore the buyer buys whenever V ≥ 0. The dealer would be willing to offer a bad car as long as p ≥ c. Therefore, whenever p ≥ c and V ≥ 0, the following is a PBE: ((Good: Offer, Bad: Offer), Buy), P (good|offer) = q. The second kind of PBE is where dealer does not offer the car regardless of whether the car is good. This is consistent with dealer utility maximization only if the buyer never buys. (else the good car dealer will offer). When will the buyer choose not to buy? It is optimal for the buyer not to buy if P (good|offer)(H − p) + (1 − P (good|offer))(L − p) ≤ 0 which rearranges to P (good|offer) ≤

p−L H −L

Therefore, the following is a pooling eq: ((Good: No Offer, Bad: No Offer), Not Buy), P (good|offer) ≤

p−L . H −L

b. There are two possible types of pooling equilibrium, one involves the dealer offers if and only if the car is good and the other involves the dealer offers if and only if the car is bad. In the first type, Bayes rule implies P (good|offer) = 1. 22

Given such belief, the buyer will always buy. Hence, it’s optimal for the bad car dealer not to offer if and only if p ≤ c. When p ≤ c, the following is a PBE: ((Good: Offer, Bad: No Offer), Buy), P (good|offer) = 1. In the second type, Bayes rule implies P (good|offer) = 0. Given such belief, the buyer will not buy. But then the bad car dealer is just wasting the cost c, so the bad dealer shouldn’t offer instead. We conclude therefore that its impossible to have this kind of equilibrium. c. Let the bad dealer offers with probability b. Then Bayes rule gives P (good|offer) =

0.5 . 0.5 + (1 − 0.5)b

Since p > c, the reason that the bad dealer mixes must be that sometimes the buyer will not buy, and sometimes the buyer will buy. Buyer’s expected payoff of buying is 0.5 0.5 )(0 − 2000) (3000 − 2000) + (1 − 0.5 + (1 − 0.5)b 0.5 + (1 − 0.5)b Buyer’s expected utility for not buying is 0. The buyer would be willing to mix if and only if P (good|offer)(3000 − 2000) + (1 − P (good|offer))(0 − 2000) = 0 which gives

2 3 Hence the bad dealer’s choice of b has to be such that P (good|offer) =

2 0.5 = 0.5 + (1 − 0.5)b 3 This gives b = 0.5. In this case, the buyer is indifferent between buying or not buying, but the probability the buyer buys has to be such that the bad car dealer is willing to mix. Let x be the probability the buyer buys the car. Then x has to be such that x(2000 − 1000) + (1 − x)(−c) = 0 23

This gives x = 0.5. Therefore under the given parameter values, the following is a PBE: ((Good: Offer, Bad: Offer with probability 1/2.), Buy with probability 1/2), P (good|offer) = 2/3.

Problem 4.7. Return to the game with two neighbors in Problem 8.4 (Check HW3). Continue to suppose that player i’s average benefit per hour of work on landscaping is 10 − li +

lj 2

Continue to suppose that player 2’s opportunity cost of an hour of landscaping work is 4. Suppose that player 1’s opportunity cost is either 3 or 5 with equal probability and that this cost is player 1’s private information. a. Write down the best-response function of each player-type. b. Solve for the Bayesian-Nash equilibrium. c. Which type of player 1 would like to send a truthful signal to player 2 if it could? Which type would like to hide his his or her private information? Answer: See Homework 4 Solution.

Problem 4.8. In Blind Texan Poker, player 2 draws a card from a standard deck and places it against her forehead without looking at it but so player 1 can see it. Player 1 moves first, deciding whether to stay or fold. If player 1 folds, he must pay player 2 $50. If player 1 stays, the action goes to player 2. Player 2 can fold or call. If player 2 folds, she must pay player 1 $50. If player 2 calls, the card is examined. If it is a low card (2-8), player 2 pays player 1 $100. If it is a high card (9,10,J,Q,K,A), player 1 pays player 2 $100. a. Draw the extensive form of the game. b. Solve for the hybrid equilibrium. 24

c. Compute the player’s expected payoffs. Answer: See Homework 4 Solution.

Problem 4.9. Recall the job-market signaling game discussed in class (NS Example 8.9). a. Find the conditions under which there is a pooling equilibrium where both types of worker choose not to obtain education (NE) and where the firm offers an uneducated worker a job. Be sure to specify beliefs as well as strategies. b. Find the conditions under which there is a pooling equilibrium where both types of workers choose not ot obtain an education (NE) and where the firm does not offer an uneducated workers a job. What is the lowest posterior belief that the worker is low skilled conditional on obtaining an education consistent with this pooling equilibrium? Why is ti more natural to think that a low-skilled worker would never deviate to E and thus an educated worker must be high-skilled? Answer: See Homework 4 Solution.

25...