155 Spring 21 (5) soln - homework solutions for stat 155 homework 5 PDF

Preview

Summary

homework solutions for stat 155 homework 5...

Description

Game Theory (STAT 155) Homework #5, 03/13/2021 All the problems are worth 4 points each and will be graded on a 0/1/2/3/4 scale. Due on Wednesay 03/24/2021 before 11:59 pm to be uploaded via Gradescope. 1. There are k NBA teams, and each of them must decide in which city to locate. Let vj be the profit potential, i.e., number of basketball fans, of city j. If l teams select city j, they each obtain a utility of vj /l. Let c = (c1 , . . . , ck ) denote a strategy profile where ci is the city selected by team i, and let nj (c) be the number of teams that select city j in this profile. Show that the market sharing game is a potential game. Solution. It suffices to show that this is a congestion game, since we already know that all congestion games are potential games. To do this, we make the following observations: • Each NBA team is a player. • Each player is allowed to choose an element of the set {{1}, {2}, {3} . . .}. That is, each player chooses one “facility” in which to produce their good. • The cost function is cj (l) = −vj /l. Therefore, this is a congestion game, hence a potential game. We even know from the general theory of congestion games that the potential function can be written down explicitly as (c) = − Φ

j (c) ∞ nX X vj

j=1 l=1

l

2. Show that the following games are not potential   (4, 4) (2, 3) (5, 3) (1, 5)  (6, 7) (9, 4) (1, 1) (2, 3) (3, 1) (4, 2) (6, 2) (4, 0) (1, 1) 

Solution. For the first game, note that there is no pure Nash equilibrium: the top left is not a Nash equilibrium, since Player I will defect; the top right is not a Nash equilibrium, since Player II will defect; the bottom left is not a Nash equilibrium, since Player II will defect; and the bottom right is not a Nash equilibrium, since Player I will defect. Therefore, this cannot be a potential game, since we know that every potential game admits a pure Nash equilibrium. For the second game, consider the following cycle of strategies: (e1 , e1 ) → (e2 , e1 ) → (e2 , e2 ) → (e1 , e2 ) → (e1 , e1 ) We know that, if this is a potential game, then the sum of the costs incurred by each player along the transitions should be zero. So we calculate them as follows: • In the transition (e1 , e1 ) → (e2 , e1 ), Player I is the one who changes strategies, and her payoff changes from 6 to 2, so the change in cost is −4. • In the transition (e2 , e1 ) → (e2 , e2 ), Player II is the one who changes strategies, and his payoff changes from 3 to 1, so the change in cost is −2. • In the transition (e2 , e2 ) → (e1 , e2 ), Player I changes strategies and increases her payoff by 6. • In the transition (e1 , e2 ) → (e1 , e1 ), Player II changes strategies and increases his payoff by 3. The sum of these changes in costs is (−4) + (−2) + 6 + 3 = 3 6= 0. Since this value is non-zero, this game cannot be a potential game. 3. Find all Nash equilibria and determine which of the symmetric equilibria are evolutionarily stable in the following games:   (4, 4) (2, 5) (5, 2) (3, 3)   (4, 4) (3, 2) . (2, 3) (5, 5)

Solution. First we focus on the top game, and we first find all the Nash equilibria. By inspection, we see that the only pure Nash equilibrium, is (e2 , e2 ). Then, if Player I plays the top row with probability x and the bottom row with probability 1 − x, where 0 < x < 1, then we must have the equalization equation 4x + 2(1 − x) = 5x + 3(1 − x). Rearranging this yields 2 = 3, which is impossible, so there is no Nash equilibrium where Player I has a non-pure strategy. By symmetry, there is also no Nash equilibrium where Player II has a non-pure strategy. Thus, the only Nash equilibrium is (e2 , e2 ). Next let us check whether this pure symmetric Nash equilibrium (e2 , e2 ) is evolutionarily stable. Write A for the payoff matrix to Player I. Note that there is no pure strategy z such that z T Ae2 = eT2 Ae2 = 5, so the second condition of evolutionary stability does not need to be checked. Therefore, the only Nash equilibrium is (e2 , e2 ), and it is evolutionarily stable. For the bottom game, let’s first find all of the Nash equilibria. By inspection we see that both (e1 , e1 ) and (e2 , e2 ) are pure Nash equilibria. Next we see that, if Player I plays the top row with probability x and the bottom row with probability 1 − x, where 0 < x < 1, then we must have the equalization equation 4x + 3(1 − x) = 2x + 5(1 − x), and this has as its only solution x = 12 . Moreover, we see by inspection that there is no equalizing pure strategy. Thus, the only Nash equilibria are (e1 , e1 ), (e2 , e2 ), and (( 21 , 12 )T , ( 21 , 12 )T ). Now we check which of these are evolutionarily stable. Both pure strategies x are evolutionarily stable since, as above, the condition z T Ax = xT Ax is never satisfied. Next we note that the mixed strategy x = ( 12 , 12 )T is equalizing, so we have z T Ax = xT Ax for all pure strategies z. However, z = e1 has z T Ax = 4 and xT Ax = 3, so the second property of evolutionary stability is not satisfied. Therefore, this game has two Nash equilibria, (e1 , e1 ) and (e2 , e2 ), which are evolutionarily stable, and one Nash equilibrium (( 12 , 12 )T , ( 12 , 21 )T ) which is evolutiomarily unstable. 4. Argue that in a symmetric game, if ai,i > bi,j (= aj,i ) for all j 6= i, then pure strategy i is an evolutionarily stable strategy. Solution. In order to prove that x = ei is evolutionarily stable, we must show that the two conditions of the definition are satisfied. For the first condition of evolutionary stability, we need (ei , ei ) to be a Nash equilibrium. This is of course true since for any j 6= i we have eTj Aei = aj,i < ai,i = eiTAei by assumption. For the second condition, we note that, in the above, we showed that strict inequality holds, so there is nothing to check. Therefore, each strategy ei is evolutionatily stable. 5. A simultaneous congestion game: There are two drivers, one who will travel from A to C, the other from B to D. Assume each road AB, AD, CD, BC is un-oriented and can be used in any direction. Moreover each road is labeled (x, y), where x is the cost to any driver who travels the road alone, and y is the cost to each driver if both drivers use this road. Write the game in matrix form, and find all of the pure Nash equilibria. A (13, 16) B

(10, 15) (7, 23)

D (21, 14) C

Solution. The first driver has two possible choices of the path, ABC and ADC. Similarly, the second driver has possible choices BCD and BAD. Let’s denote the price of the road P when it’s used by n players as P (n). Then we can write out the cost matrix as follows:

ABC ADC

BCD BAD     AB (1) + BC (2), BC(2) + CD (1) AB (2) + BC (1), BA(2) + AD(1)    AD(1) + DC (2), BC(1) + CD(2) AD(2) + DC (1), BA(1) + AD(2)

= ABC ADC

BCD BAD     13 + 23, 23 + 21  16 + 7, 16 + 10  = ABC ADC 10 + 14, 7 + 14 15 + 21, 13 + 15

In other words, the payoff matrix is

BCD BAD  36, 44 23, 26 24, 21 36, 28

  (−36, −44) (−23, −26) . (−24, −21) (−36, −28) By inspection, we see that this game has two pure Nash equilibria (ADC, BCD) and (ABC, BAD).

6. A B C

A B C (0, 0) (6, 2) (−1, −1) (2, 6) (0, 0) (6, 9) (−1, −1) (9, 6) (0, 0)

Find two mixed Nash equilibria, one supported on A, B (only A and B have positive probabilities), the other supported on B, C. Show that they are both ESS, but the A,B equilibrium is not stable when invaded by an arbitrarily small population composed of half B’s and half C’s. Solution. Let A denote the matrix of payoffs to Player I, and observe of course that this game is symmetric. First, we find the mixed Nash equilibrium supported on A, B. Suppose Player II’s strategy is y = (p, 1 − p, 0)T for 0 ≤ p ≤ 1. This is a best response to some strategy of Player I supported on A, B if and only if we have eT1 Ay = eT2 Ay ≥ eT3 Ay. The first equality is 2p = 6(1 − p), so p = 34 is the only option. Then, the last inequality is 2p ≥ 9(1 − p) − p, and this holds (with equality) when p = 34 . Therefore, x = y = (43 , 14 , 0)T is a symmetric Nash equilibrium supported on A, B, and it is in fact fully equalizing. Let’s check that this strategy x is evolutionarily stable. Since it is fully equalizing, we know that xT Ax = z T Ax holds for all strategies z, so we just need to check that z T Az < xT Az holds for all pure strategies z. This is indeed the case, since we have z T Az = 0 for any pure z (just by inspecting the diagonal of the matrix), and xT Ae1 =

1 > 0, 2

xT Ae2 =

9 > 0, 2

xT Ae3 =

3 > 0. 4

Therefore, the strategy ( 43 , 14 , 0)T is evolutionarily stable. Next, let’s show that this strategy is not stable against mixed strategies. That is, consider z = (0, 12 , 21 )T . Since x is fully equalizing, we of course have xT Ax = z T Ax. But we also have xT Az =

21 15 < = z T Az, 8 4

so we see that ( 34 , 41 , 0)T is not stable when invaded by (0, 12 , 12 )T . Next we we find the mixed Nash equilibrium supported on B, C; analogously to the previous part, we find that x = y = (0, 25 , 35 )T is a symmetric Nash equilibrium with the desired support. Note in particular that we have )T , so this strategy is a Nash equilibrim, although it is not fully equalizing. To see that it is stable, we Ax = ( 95 , 18 , 18 5 5 need to verify the strict inequality xT Ax > zT Ax for z equal to e1 and e2 . Indeed, this is easy since z T Az = 0 for all pure z like we observed before. So we just check: xT Ae1 = Therefore, (0, 52 , 35 )T is evolutionarily stable.

18 > 0, 5

xT Ae1 =

216 > 0. 5...