Solutions PS 6 PDF

Preview

Summary

Problem set 6 questions w/solutions....

Description

1

Game Theory, Econ 159 01 Problem Set 6

This problem will be graded and is due on October 12 at the latest. Please, write clearly and use the notation of the lectures whenever possible.

Please, answer each problem in separated sheets of paper and do not forget your name in each of them. Problem 1 Consider the following game tree played by two rational players. The tree and the players’ rationality are common knowledge. 1

c

2

s

1 1

1

c

s

2

c

c

s

0 3

3 3

s

2 2

1 2

(a) Write the normal form and find all Nash equilibria in pure strategies. Each player has 2 information sets and 2 actions per set. Hence each has four pure strategies: S1 = S2 = {ss, sc, cs, ss}. This leads to a 4 × 4 matrix ss

sc

ss 1

1

1 0 0

1 1

2 2

3 0

1

1

0

1

1

3

3

cc

1

1 3

cs

cc 1

1

1

sc

cs 1

1

2 2

2 1

3 3

NE = {(ss, ss), (ss, sc), (sc, ss), (sc, sc), (cc, cc)} (b) Which equilibria of those you found survive backward induction? Motivate your answer. {(sc, sc), (cc, cc)} In the last node 2 will always choose c and so will 1 in his last node. At his first node, given that both will play c afterwards, 2 is indifferent between c

2

Game Theory, Econ 159 01 Problem Set 6

and s. In the first case 1’s optimal choice at the beginning of the games is c, in the second case s is the optimal choice. (That is why we get 2 eq by the backward induction method: there are some ties.) (c) Which equilibria of those you found are not reasonable? Motivate your answer for each of them. (ss, ss), (ss, sc), (sc, ss) do not survive backward induction. (ss, ss): 2 should play c at his last node. (ss, sc): 1 should play c at his last node. (sc, ss): 2 should play c at his last node. Problem 2 Suppose that a single play of a prisoners’ dilemma (PD) has the following payoffs. C C D

D 4

3 3

1 1

4

2 2

Imagine a large population in which each member’s behavior is genetically determined. In each time period, all the members of the population are randomly matched in pairs to play n > 3 prisoner’s dilemmas. The opponent is different each time the players are matched but is the same in each match. (In the example in the lectures n = 1 and each player played “only” one PD per period, now each player plays n > 3 PDs per period). There are two types of players: 1. A share x of them are “defectors” and always play D. 2. A share 1 − x of players are “Tit-for-Tat.” In multiple rounds of the PD with the same opponent, a “Tit-for-Tat” plays C in the first round, and on any subsequent round she does whatever her opponent did on the preceding round. “Tit-for-Tat” always starts with C in a newly formed match, i.e in the first of the n rounds. The payoff to each player, her Darwinian fitness, is the sum of her payoffs in the n rounds.

3

Game Theory, Econ 159 01 Problem Set 6

(a) Draw the payoff matrix for the n-times-repeated prisoners’ dilemma. Namely, write a 2 × 2 table with the payoffs to a player of each type (“defector” and “Tit-for-Tat”) when the player meets an opponent of each of the two types and they play the PD n times. D 2n

D

2n

TFT 1+2(n-1) 4+2(n-1)

4+2(n-1) 1+2(n-1) 3n

TFT

3n

(b) For which values of x do the defectors have a greater fitness? D has greater fitness when x · 2n + (1 − x)(4 + 2(n − 1)) > x(1 + 2(n − 1)) + (1 − x)3n x2n + 4 + 2(n − 1) − 4x − 2nx + 2x > x + 2nx − 2x + 3n − 3nx 2 + 2n − 2x > −x − nx + 3n −x + nx > n − 2 n−2 x> n−1 (c) If evolution leads to a gradual increase in the proportion of the fitter type in the population, what are the possible steady states for the population described? Plot the phase diagram for the replicator dynamics to illustrate your answer. all TFT

all D

x1 : 0

n-2/n-1

1

The possible equilibrium outcomes are: – the whole population playing D, – the whole population playing TFT , – or

n−2 n−1

share of the population playing D and

1 n−1

share of the population

playing TFT. (d) Is “Tit-for-Tat” and evolutionarily stable strategy? What about ”always defect”? Why? Both are ESS since both are strict NE. An alternative answer is that both are asymptotically stable under the replicator dynamics and hence ESS. One could also use the definition of ESS and show that TFT does better than always defect when the share of the latter in the population is

Game Theory, Econ 159 01 Problem Set 6

4

sufficiently small. Similarly with all defect, it does better than TFT when the share of TFT in the population is sufficiently small. (e) Which monomorphic population is more robust to “large” invasions by the other type, a population of all ““Tit-for-Tat”s or a population of all “defectors”? Does your answer depend on n? If so, in what way? TFT is more robust since its basin of attraction is larger (the set of initial states for which the system converges to a population of all TFT) whenever n > 3. At n = 3, both basins of attraction are equally large since (n − 2)/(n − 1) = 1/2 when n=3. The basin of attraction of TFT is larger for larger n’s since (n − 2)/(n − 1) goes to 1 as n goes to infinity (f) In what sense does greater repetition facilitate the evolution of cooperation? gets to 1. Therefore the more rounds are The higher n, the closer n−2 n−1 played the smaller the share of the population playing TFT needs to be initially for the population to converge to an all TFT population. It becomes more and more difficult to invade a population of all TFT since you of the whole population. need the defectors to be more than a share n−2 n−1

Game Theory, Econ 159 01 Problem Set 6

5

Problem 3 We say that a player has a winning strategy if, whatever the other player does, he has a strategy that guarantees that he wins. In the following game one of the players has a winning strategy, namely if he follows it he will always win. Two players alternate in taking turns to remove some sticks from a set of 4. Each time it’s a player’s turn, (s)he chooses to remove 1, 2, or 3 sticks. The player who removes the last stick is the winner. (a) Draw the game tree indicating clearly which node is the root, which ones are decision nodes and which ones are final nodes. Call the players P1 and P2 (to avoid confusion with the number of sticks taken). Give payoff 1 to the winner and 0 to the loser. (Note that in some decision nodes the player with the move will have only one choice. Plot it anyway.) This was done on the blackboard. It is a game of perfect information with Player 1 moving first. (b) What does a strategy for player 1 look like? and for player 2? A strategy for 1 should specify what he does at any of his info sets. Namely, how many sticks to take at the beginning (1,2 or 3) and how many in the other two nodes he could be at (after he has taken 1 and player 2 has taken 1 (he can take 1 or 2 in this case ) or P2 has taken 2 and after he has taken 2 and player 2 has taken 1 (in both cases player 1 can only take 1)). A strategy for 2 should specify what to do after each first action of 1 and at any other info set belonging to 2 (if he takes 1 after 1 takes 1 and then 1 only takes 1). (c) Solve the game using backward induction. This is easy once you have the tree, just mark the optimal branches moving upwards in the three. (d) Which player has a winning strategy? What should (s)he do? Player 2 has a winning strategy: take all what is left after player 1’s first move. Assume now that the game starts with a set of 5 sticks instead. (e) Who has now a winning strategy? Explain. (Hint: To answer this question you do not really need to plot the tree). Now player 1 has a winning strategy: to leave four sticks on the table. The game at that moment is a game with four sticks and player 1 will be the second mover. (f) Now generalize. Who has a winning strategy when starting with 4n sticks? Who when the number of sticks is not a multiple of 4? Explain With multiple of 4 the second player has a winning strategy because he can always arrive as second mover to the game with only four sticks. When it

Game Theory, Econ 159 01 Problem Set 6

6

is not multiple of 4, player 1 has a winning strategy for the same reason. He can always arrive as second mover to the game with only four sticks....