Game Theory – Tutorial 3 answers PDF

Preview

Summary

This set of exercises are based on material from Lecture 4...

Description

Game Theory 5QQMN213: Exercise Sheet 3 Niall Hughes 1. In the 3x3 game below (in which “- ” indicates irrelevant payoffs), show that the strategies (σ1 (T ), σ1 (M ), σ1 (B)) = (43, 0, 14 ) and (σ2 (L), σ2 (C), σ2 (R)) = (0, 31, 23 ) constitute a mixed strategy Nash equilibrium. Explain why this is so. Player 2 L

C

R

T

(−, 2)

(3, 3)

(1, 1)

Player 1 M

(−, −)

(0, −)

(2, −)

B

(−, 4)

(5, 1)

(0, 7)

To see whether this is a mixed strategy Nash equilibrium, we need to check the expected payoffs of each player. First for player 1 we have 1 v1 (T, σ2 ) = (3) + 3 1 v1 (M, σ2 ) = (0) + 3 1 v1 (B, σ2 ) = (5) + 3

2 (1) = 3 2 (2) = 3 2 (0) = 3

5 3 4 3 5 3

We see that player 1 gets the same payoff from playing T or B, but a lower payoff from playing M. Her mixed strategy assigns positive probability to playing T and B but zero probability to playing M. Therefore, the conditions for Player 1 to be playing a best response are satisfied.

1

For player 2 we have 3 1 v2 (σ1 , L) = (2) + (4) = 4 4 3 1 v2 (σ1 , C) = (3) + (1) = 4 4 3 1 v2 (σ1 , R) = (1) + (7) = 4 4

5 2 5 2 5 2

Player 2’s strategy puts positive probability on C and R and zero probability on L. We see that C and R both have the same expected payoff of 25. In fact L also has a payoff of 25 but this does not violate our conditions for a mixed strategy to be best responding. Only if the expected payoff of L was above 25, would the proposed mixed strategy not be a best response. 2. Solve for all the mixed strategy Nash equilibria in the 3x3 game below Player 2 L

C

R

T

(2, 0)

(1, 1)

(4, 2)

Player 1 M

(3, 4)

(1, 2)

(2, 3)

B

(1, 3)

(0, 2)

(3, 0)

First, we observe that for player 1 the strategy B is strictly dominated by T. By IESDS, once row B is eliminated we see that for player 2 the strategy C is dominated by the strategy R. We have now reduced to game to a 2x2 game. Let p be the probability that player 1 plays T, and (1 − p) be the probability that he plays M. Similarly, let q be the probability that player 2 plays L and (1 − q ) be the probability that he plays R. We know that each player is willing to mix when their expected payoff from the pure strategies in their mixed strategy are equal. That is v1 (T, σ2 ) = v1 (M, σ2 ) q (2) + (1 − q)4 = q (3) + (1 − q)(2) 2 q = 3

Page 2

v2 (σ1 , L) = v2 (σ1 , R) p(0) + (1 − p)(4) = p(2) + (1 − p)(3) 1 p = 3 We have found a mixed strategy Nash Equilibrium (σ1 , σ2 ) = ((31, 23 , 0), ( 32 , 0, 13 )). Looking at the matrix we see that there are also 2 pure strategy Nash equilibria: (M, L) and (T, R). We can write these as mixed strategies: (σ1 , σ2 ) = ((0, 1, 0), (1, 0, 0)) and (σ1 , σ2 ) = ((1, 0, 0), (0, 0, 1)). 3. Player 1 is a police officer who must decide whether to patrol the streets or to hang out at the coffee shop. His payoff from hanging out at the coffee shop is 10, while his payoff from patrolling the streets depends on whether he catches a robber, who is player 2. If the robber prowls the streets then the police officer will catch him and obtain a payoff of 20. If the robber stays in his hideaway then the officers payoff is 0. The robber must choose between staying hidden or prowling the street. If he stays hidden then his payoff is 0, while if he walks the street his payoff is -10 if the officer is patrolling the streets, and it is 10 if the officer is at the coffee shop. i Write down the matrix form of this game. ii Draw the best response functions for each player iii Find the Nash equilibrium. What kind of game does this remind you of?

i Let P denote Patrol and C denote Coffee shop for player 1. Let S be a choice of Street, and H be a choice of hiding for player 2. The matrix is therefore: Player 2 S H P (20, −10) (0, 0) Player 1 C (10, 10) (10, 0) ii Let p be the probability that player 1 chooses P and q the probability that player 2 chooses S. It follows that v1 (P, σ2 ) > v1 (C, σ2 ) if and

Page 3

only if 20q > 10, or q > 12 , and v2 (σ1 , S) > v2 (σ1 , H) if and only if −10p + (10(1 − p) > 0 or p < 21 . It follows that we have   if q < p = 0 BR1 (σ2 ) = p ∈ [0, 1] if q =  p = 1 if q >

1 2 1 2 1 2

(1)

  if p < q = 1 BR2 (σ1 ) = q ∈ [0, 1] if p =   q=0 if p >

1 2 1 2 1 2

(2)

Notice that these are identical to the best response functions for the penalties/matching pennies game. iii From the two best response correspondences the unique Nash equilibrium is (p, q) = (21, 12 ) and the games strategic forces are identical to those in the Penalty Kicks/Matching Pennies game. 4. Two students sign up for an honours thesis with a Professor. Each can invest time in their own project: either no time, one week, or two weeks (these are the only three options). The cost of time is 0 for no time, and each week costs 1 unit of payoff. The more time a student puts in the better their work will be, so that if one student puts in more time than the other there will be a clear “leader”. If they put in the same amount of time then their thesis projects will have the same quality. The professor, however, will give out only one “A” grade. If there is a clear leader then he will get the A, while if they are equally good then the professor will toss a fair coin to decide who gets the A grade. The other student gets a “B”. Since both wish to continue to graduate school, a grade of A is worth 3 while a grade of B is worth zero. i Write down the matrix form of this game. ii Are there any strictly dominated strategies? iii Find the unique mixed strategy Nash equilibrium.

Page 4

i Let N denote No time, O denote One week, and T denote Two weeks. The matrix is therefore: Player 2

Player 1

N

O

T

N

(1.5, 1.5)

(0, 2)

(0, 1)

O

(2, 0)

(0.5, 0.5)

(−1, 1)

T

(1, 0)

(1, −1)

(−0.5, −0.5)

ii No strategy is strictly dominated for either player, so we cannot reduce the game from a 3x3 game. iii Let σi = (σi (N ), σi (O)), 1 − σi (N ) − σi (O)) denote a mixed strategy for player i. Because the game is symmetric it suffices to solve the indifference conditions for one player. For player j to be indifferent between N and O, 1.5σi (N ) = 2σi (N ) + 0.5σi (O) − (1 − σi (N ) − σi (O) and for him to be indifferent between N and T, 1.5σi (N ) = σi (N ) + σi (O) − 0.5(1 − σi (N ) − σi (O) Solving these two equations with two unknowns yields σi (N ) = σi (O) = 31 implying that the unique mixed strategy Nash equilibrium has the players mixing between all three pure strategies with equal probability. 5. Two players find themselves in a legal battle over a patent. The patent is worth 20 for each player, so the winner would receive 20 and the loser 0. Given the norms of the country they are in, it is common to bribe the judge of a case. Each player can offer a bribe secretly, and the one whose bribe is the largest is awarded the patent. If both choose not to bribe, or if the bribes are the same amount, then each has an equal chance of being awarded the patent. If a player does bribe, then bribes can be either a value of 9 or of 20. Any other number is considered to be very unlucky and the judge would surely rule against a party who offers a different number.

Page 5

i Write down the matrix form of this game and find the unique pure-strategy Nash equilibrium of this game. ii If the norm were different so that a bribe of 15 were also acceptable, is there a pure strategy Nash equilibrium? iii Find the symmetric mixed-strategy Nash equilibrium for the game with possible bribes of 0, 9 and 15 only.

i Let Z represent no payment, N represents a bribe of 9, and T a bribe of 20. For example, if both choose 9 then they each have an equal chance of getting 20, so the expected payoff is 21(20) − 9 = 1 Player 2 Z

N

T

(10, 10)

(0, 11)

(0, 0)

Player 1 N

(11, 0)

(1, 1)

(−9, 0)

T

(0, 0)

(0, −9)

(−10, −10)

Z

It is easy to see that the unique pure strategy Nash equilibrium is (N, N ). ii Now the game is as follows, where F denotes a bribe of 15. Player 2

Player 1

Z

N

F

T

Z

(10, 10)

(0, 11)

(0, 5)

(0, 0)

N

(11, 0)

(1, 1)

(−9, 5)

(−9, 0)

F

(5, 0)

(5, −9)

(−5, −5)

(−15, 0)

T

(0, 0)

(0, −9)

(0, −15)

(−10, −10)

Using the best response of each player we can see that there is no pure strategy Nash equilibrium. iii We have the following matrix:

Page 6

Player 2 Z

N

F

Z

(10, 10)

(0, 11)

(0, 5)

Player 1 N

(11, 0)

(1, 1)

(−9, 5)

F

(5, 0)

(5, −9)

(−5, −5)

Let σi = (σi (Z), σi (N ), 1 − σi (Z) − σi (N )) denote a mixed strategy for player i. The game is symmetric so for player j to be indifferent between Z and N it must be that, 10σi (Z) = 11σi (Z) + σi (N ) − 9(1 − σi (Z) − σi (N )) which implies that σi (N ) = 109 − σi (Z). For player j to be indifferent between Z and F it must be that, 10σi (Z) = 5σi (Z) + 5σi (N ) − 5(1 − σi (Z) − σi (N )) which implies that σi (N ) = 21 and thus we have σi (Z) = 52 . Hence, the unique (mixed strategy) Nash equilibrium has each player play σi = 1 ). ( 25 , 21, 10 6. Use the same method we used in the lectures solving the Paper-Scissors-Rock game, to find all the equilibria of the following game. Player 2

Player 1

L

M

R

T

(2, 2)

(0, 3)

(1, 3)

B

(3, 2)

(1, 1)

(0, 2)

• First, we check whether there are any pure strategy Nash equilibria. We see that there are two: (B, L) and (T, R). • Second, we check whether there can be an equilibrium in which one player plays a pure strategy while the other mixes.

Page 7

– Suppose player 2 is playing L for sure, then player 1 will strictly prefer B to T. If player 2 plays M for sure, then player 1 prefers B to T, if player 2 plays R for sure, then player 1 prefers T to B. Because he is not indifferent in any of these cases, it cannot be that player 2 plays a pure strategy while player 1 mixes. – Suppose player 1 plays T for sure - Player 2 will be indifferent between playing M and R. Can this be an equilibrium? It will be an equilibrium if player 1 gets a higher payoff from playing T than B, given player 2’s mixed strategy. Suppose player 2 has the mixed strategy σ2 = (σ2 (L), σ2 (M ), 1 − σ2 (L) − σ2 (M)). The candidate for equilibrium has σ2 (L) = 0. We can check when player 1 prefers T to B: v1 (T, σ2 ) ≥ v1 (B, σ2 ) (0)σ2 (M) + (1)(1 − σ2 (M)) ≥ (1)σ2 (M) + (0)(1 − σ2 (M )) 1 σ2 (M) ≤ 2 That is, we have an equilibrium where player 1 plays T for sure, and player 2 mixes between M and R, but playing R with a probability greater than or equal to 21. – Suppose player 1 plays B for sure - Player 2 will be indifferent between playing L and R. Can this be an equilibrium? It will be an equilibrium if player 1 gets a higher payoff from playing B than T, given player 2’s mixed strategy. Suppose player 2 has the mixed strategy σ2 = (σ2 (L), σ2 (M ), 1 − σ2 (L) − σ2 (M)). The candidate for equilibrium has σ2 (M) = 0. We can check when player 1 prefers B to T: v1 (T, σ2 ) ≤ v1 (B, σ2 ) (2)σ2 (L) + (1)(1 − σ2 (L)) ≤ (3)σ2 (L) + (0)(1 − σ2 (L)) 1 σ2 (L) ≥ 2 That is, we have an equilibrium where player 1 plays B for sure, and player 2 mixes between L and R, but playing L with a probability greater than or equal to 21.

Page 8

• Third, we check whether there are any equilibria in which both players mix over only 2 strategies. We know that if player 2 is mixing then he must be indifferent between playing any of the pure strategies in his mixed strategy. Suppose player 1 plays T with probability p and B with probability (1−p) - where 0 < p < 1 (we suppose he is mixing, so therefore p cannot be equal to 0 or 1). Given Player 1’s mixed strategy, player 2’s expected payoff from his three pure strategies are: v2 (σ1 , L) = (2)p + (2)(1 − p) = 2 v2 (σ1 , M) = (3)p + (1)(1 − p) = 2p + 1 v2 (σ1 , R) = (3)p + (2)(1 − p) = p + 2 From these equations we can see that the pure strategy R strictly dominates any other strategy of player 2, if player 1 is mixing between T and B. Why? Because when 0 < p < 1 it must be that both p + 2 > 2 and p + 2 > 2p + 1 are true. Therefore, Player 2 only willing to play R whenever Player 1 is mixing, so we have no equilibria in which both players are playing mixed strategies. • Finally, we check whether there are any equilibria where player 1 mixes over 2 strategies and player 2 mixes over 3 strategies. It follows directly from the point above that if player 1 is mixing, then player 2 will want to play the pure strategy R. Therefore, there can be no equilibrium where both players mix.

Page 9...