lecture10Mixed Strategy Nash Equilibrium(博弈论,Carnegie Mellon University)

lecture10Mixed Strategy Nash Equilibrium(博弈论,Carnegie Mellon University) Static (or Simultaneous-Move) Games of Complete Information Mixed Strategy Nash Equilibrium 73-347 Game Theory--Lecture 10 Outline of Static Games of Complete Information Introduction to games Normal-form (or strategic-form) representation Iterated elimination of strictly dominated strategies Nash equilibrium Review of concave functions, optimization Applications of Nash equilibrium Mixed strategy Nash equilibrium 73-347 Game Theory--Lecture 10 Today’s Agenda Review of previous class Example: Rock, paper and scissors (Exercise 1391>.1 of Osborne) How to find mixed strategy Nash equilibria in a 2-player game each with a finite number of strategies 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Each of two players simultaneously announces either Rock, or Paper, or Scissors. Paper beats (wraps) rock Rock beats (blunts) scissors Scissors beats (cuts) paper The player who names the winning object receives $1 from her opponent If both players name the same choice then no payment is made 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Can you guess a mixed strategy Nash equilibrium? Player 2 0 , 0 -1 , 1 1 , -1 Scissors Paper 1 , -1 -1 , 1 Scissors 0 , 0 1 , -1 Paper Player 1 -1 , 1 0 , 0 Rock Rock 73-347 Game Theory--Lecture 10 Mixed strategy Nash equilibrium: 2-player each with two pure strategies Mixed strategy Nash equilibrium: A pair of mixed strategies ((r*, 1-r*), (q*, 1-q*)) is a Nash equilibrium if (r*,1-r*) is a best response to (q*, 1-q*), and (q*, 1-q*) is a best response to (r*,1-r*). That is, v1((r*, 1-r*), (q*, 1-q*)) ?? v1((r, 1-r), (q*, 1-q*)), for all 0?? r ??1 v2((r*, 1-r*), (q*, 1-q*)) ?? v2((r*, 1-r*), (q, 1-q)), for all 0?? q ??1 Player 2 s22 ( 1- q ) u1(s12, s22), u2(s12, s22) u1(s12, s21), u2(s12, s21) s12 (1- r ) Player 1 u1(s11, s22), u2(s11, s22) u1(s11, s21), u2(s11, s21) s11 ( r ) s21 ( q ) 73-347 Game Theory--Lecture 10 2-player each with two strategies Theorem 1 (property of mixed Nash equilibrium) pair of mixed strategies ((r*, 1-r*), (q*, 1-q*)) is a Nash A equilibrium if and only if v1((r*, 1-r*), (q*, 1-q*)) ?? EU1(s11, (q*, 1-q*)) v1((r*, 1-r*), (q*, 1-q*)) ?? EU1(s12, (q*, 1-q*)) v2((r*, 1-r*), (q*, 1-q*)) ?? EU2(s21, (r*, 1-r*)) v2((r*, 1-r*), (q*, 1-q*)) ?? EU2(s22, (r*, 1-r*)) Player 2 s22 ( 1- q ) u1(s12, s22), u2(s12, s22) u1(s12, s21), u2(s12, s21) s12 (1- r ) Player 1 u1(s11, s22), u2(s11, s22) u1(s11, s21), u2(s11, s21) s11 ( r ) s21 ( q ) 73-347 Game Theory--Lecture 10 Mixed strategy equilibrium: 2-player each with two strategies Theorem 2 Let ((r*, 1-r*), (q*, 1-q*)) be a pair of mixed strategies, where 0 <r*<1, 0<q*<1. Then ((r*, 1-r*), (q*, 1-q*)) is a mixed strategy Nash equilibrium if and only if EU1(s11, (q*, 1-q*)) = EU1(s12, (q*, 1-q*)) EU2(s21, (r*, 1-r*)) = -r*))EU2(s22, (r*, 1 That is, each player is indifferent between her two pure strategies given the mixed strategy chosen by the other player. Player 2 s22 ( 1- q ) u1(s12, s22), u2(s12, s22) u1(s12, s21), u2(s12, s21) s12 (1- r ) Player 1 u1(s11, s22), u2(s11, s22) u1(s11, s21), u2(s11, s21) s11 ( r ) s21 ( q ) 73-347 Game Theory--Lecture 10 -player each with a finite number of pure strategies 2 Set of players: {Player 1, Player 2} Sets of strategies: player 1: S1= { s11, s12, ..., s1J } player 2: S2= { s21, s22, ..., s2K } Payoff functions: player 1: u1(s1j, s2k) player 2: u2(s1j, s2k) for j = 1, 2, ..., J and k = 1, 2, ..., K 73-347 Game Theory--Lecture 10 2-player each with a finite number of pure strategies Player 1’s mixed strategy: p1=(p11, p12, ..., p1J ) Player 2’s mixed strategy: p2=(p21, p22, ..., p2K ) Player 2 u2(s1J, s22) u1(s1J, s22) ....... u2(s12, s22) u1(s12, s22) u2(s11, s22) u1(s11, s22) s22 (p22) u2(s1J, s21) u1(s1J, s21) ...... u2(s12, s21) u1(s12, s21) u2(s11, s21) u1(s11, s21) s21 (p21) ...... ....... .... u2(s12, s2K) u1(s12, s2K) ....... s12 (p12) s2K (p2K) u2(s1J, s2K) u1(s1J, s2K) ...... s1J (p1J) u2(s11, s2K) u1(s11, s2K) ....... s11 (p11) ....... Player 1 73-347 Game Theory--Lecture 10 Expected payoffs: 2-player each with a finite number of pure strategies Player 1’s expected payoff of pure strategy s11: EU1(s11, p2)=p21×u1(s11, s21)+p22×u1(s11, s22)+...+p2k×u1(s11, s2k)+...+p2K×u1(s11, s2K) Player 1’s expected payoff of pure strategy s12: EU1(s12, p2)=p21×u1(s12, s21)+p22×u1(s12, s22)+...+p2k×u1(s12, s2k)+...+p2K×u1(s12, s2K) ......... Player 1’s expected payoff of pure strategy s1J: EU1(s1J, p2)=p21×u1(s1J, s21)+p22×u1(s1J, s22)+...+p2k×u1(s1J, s2k)+...+p2K×u1(s1J, s2K) Player 1’s expected payoff from her mixed strategy p1: v1(p1, p2)=p11??EU1(s11, p2)+p12??EU1(s12, p2)+...+p1j??EU1(s1j, p2)+... +p1J??EU1(s1J, p2) 73-347 Game Theory--Lecture 10 Expected payoffs: 2-player each with a finite number of pure strategies Player 2’s expected payoff of pure strategy s21: EU2(s21, p1)=p11×u2(s11, s21)+p12×u2(s12, s21)+...+p1j×u2(s1j, s21)+...+p1J×u2(s1J, s21) Player 2’s expected payoff of pure strategy s22: EU2(s22, p1)=p11×u2(s11, s22)+p12×u2(s12, s22)+...+p1j×u2(s1j, s22)+...+p1J×u2(s1J, s22) ........... Player 2’s expected payoff of pure strategy s2K: EU2(s2K, p1)=p11×u2(s11, s2K)+p12×u2(s12, s2K)+...+p1j×u2(s1j, s2K)+...+p1J×u2(s1J, s2K) Player 2’s expected payoff from her mixed strategy p2: v2(p1, p2)=p21??EU2(s21, p1)+p22??EU2(s22, p1) +...+p2k??EU2(s2k, p1)+.... +p2K??EU2(s2K, p1) 73-347 Game Theory--Lecture 10 Mixed strategy Nash equilibrium: 2-player each with a finite number of pure strategies A pair of mixed strategies (p1*, p2*), where p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) is a mixed strategy Nash equilibrium if player 1’s mixed strategy p1* is a best response to player 2’s mixed strategy p2*, and p2* is a best response to p1*. Or, v1(p1*, p2*)?? v1(p1, p2*), for all player 1’s mixed strategy p1, and v2(p1*, p2*) ?? v2(p1*, p2), for all player 2’s mixed strategy p2. That is, given player 2’s mixed strategy p2*, player 1 cannot be better off if she deviates from p1*. Given player 1’s mixed strategy p1*, player 2 cannot be better off if she deviates from p2*. 73-347 Game Theory--Lecture 10 2-player each with a finite number of pure strategies Theorem 3 (property of mixed Nash equilibrium) A pair of mixed strategies (p1*, p2*), where p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) is a mixed strategy Nash equilibrium if and only if v1(p1*, p2*) ?? EU1(s1j, p2*), for j = 1, 2, ..., J and v2(p1*, p2*) ?? EU2(s2k, p1*), for k= 1, 2, ..., K 73-347 Game Theory--Lecture 10 2-player each with a finite number of pure strategies Theorem 4 A pair of mixed strategies (p1*, p2*), where p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) is a mixed strategy Nash equilibrium if and only if they satisfies the following conditions: player 1: for any m and n, if p1m*>0 and p1n*>0 then EU1(s1m, p2*) = EU1(s1n, p2*); if p1m*>0 and p1n*=0 then EU1(s1m, p2*) ?? EU1(s1n, p2*) player 2: for any i and k, if p2i*>0 and p2k*>0 then EU2(s2i, p1*) = EU2(s2k, p1*); if p2i*>0 and p2k*=0 then EU2(s2i, p1*) ?? EU2(s2k, p1*) 73-347 Game Theory--Lecture 10 2-player each with a finite number of pure strategies What does Theorem 4 tell us? A pair of mixed strategies (p1*, p2*), where p1*=(p11*, p12*, ..., p1J* ), p2*=(p21*, p22*, ..., p2K* ) is a mixed strategy Nash equilibrium if and only if they satisfies the following conditions: Given player 2’s p2*, player 1’s expected payoff of every pure strategy to which she assigns positive probability is the same, and player 1’s expected payoff of any pure strategy to which she assigns positive probability is not less than the expected payoff of any pure strategy to which she assigns zero probability. Given player 1’s p1*, player 2’s expected payoff of every pure strategy to which she assigns positive probability is the same, and player 2’s expected payoff of any pure strategy to which she assigns positive probability is not less than the expected payoff of any pure strategy to which she assigns zero probability. 73-347 Game Theory--Lecture 10 2-player each with a finite number of pure strategies Theorem 4 implies that we have a mixed strategy Nash equilibrium in the following situation Given player 2’s mixed strategy, Player 1 is indifferent among the pure strategies to which she assigns positive probabilities. The expected payoff of any pure strategy she assigns positive probability is not less than the expected payoff of any pure strategy she assigns zero probability. Given player 1’s mixed strategy, Player 2 is indifferent among the pure strategies to which she assigns positive probabilities. The expected payoff of any pure strategy she assigns positive probability is not less than the expected payoff of any pure strategy she assigns zero probability. 73-347 Game Theory--Lecture 10 Theorem 4: illustration Check whether ((3/4, 0, 1/4), (0, 1/3, 2/3)) is a mixed strategy Nash equilibrium Player 1: EU1(T, p2) = 0??0+3??(1/3)+1??(2/3)=5/3, EU1(M, p2) = 4??0+0??(1/3)+2??(2/3)=4/3 EU1(B, p2) = 3??0+5??(1/3)+0??(2/3)=5/3. Hence, EU1(T, p2) = EU1(B, p2) > EU1(M, p2) Player 2 0 , 7 2 , 3 1 , 1 R (2/3) C (1/3) 5 , 1 3 , 4 B (1/4) 0 , 4 4 , 0 M (0) Player 1 3 , 3 0 , 2 T (3/4) L (0) 73-347 Game Theory--Lecture 10 Theorem 4: illustration Player 2: EU2(L, p1)=2??(3/4) + 0??0 + 4??(1/4)=5/2, EU2(C, p1)=3??(3/4) + 4??0 + 1??(1/4)=5/2, EU2(R, p1)=1??(3/4) + 3??0 + 7??(1/4)=5/2. Hence, EU2(C, p1)=EU2(R, p1)??EU2(L, p1) Therefore, ((3/4, 0, 1/4), (0, 1/3, 2/3)) is a mixed strategy Nash equilibrium by Theorem 4. Player 2 0 , 7 2 , 3 1 , 1 R (2/3) C (1/3) 5 , 1 3 , 4 B (1/4) 0 , 4 4 , 0 M (0) Player 1 3 , 3 0 , 2 T (3/4) L (0) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Check whether there is a mixed strategy Nash equilibrium in which p11>0, p12>0, p13>0, p21>0, p22>0, p23>0. Player 2 0 , 0 -1 , 1 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors If each player assigns positive probability to every of her pure strategy, then by Theorem 4, each player is indifferent among her three pure strategies. Player 2 0 , 0 1 , 1 - 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Player 1 is indifferent among her three pure strategies: EU1(Rock, p2) = 0??p21+(-1)?? p22+1?? p23 EU1(Paper, p2) = 1?? p21+0?? p22+(-1)?? p23 EU1(Scissors, p2) = (-1)?? p21+1?? p22+0?? p23 EU1(Rock, p2)= EU1(Paper, p2)= EU1(Scissors, p2) Together with p21+ p22+ p23=1, we have three equations and three unknowns. Player 2 0 , 0 1 , 1 - 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors 0??p21+(-1)?? p22+1?? p23= 1?? p21+0?? p22+(-1)?? p23 0??p21+(-1)?? p22+1?? p23 = (-1)?? p21+1?? p22+0?? p23 p21+ p22+ p23=1 The solution is p21= p22= p23=1/3 Player 2 0 , 0 -1 , 1 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Player 2 is indifferent among her three pure strategies: EU2(Rock, p1)=0??p11+(-1)?? p12+1?? p13 EU2(Paper, p1)=1?? p11+0?? p12+(-1)?? p13 EU2(Scissors, p1)=(-1)?? p11+1?? p12+0?? p13 EU2(Rock, p1)= EU2(Paper, p1)=EU2(Scissors, p1) Together with p11+ p12+ p13=1, we have three equations and three unknowns. Player 2 0 , 0 -1 , 1 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors 0??p11+(-1)?? p12+1?? p13=1?? p11+0?? p12+(-1)?? p13 0??p11+(-1)?? p12+1?? p13=(-1)?? p11+1?? p12+0?? p13 p11+ p12+ p13=1 The solution is p11= p12= p13=1/3 Player 2 0 , 0 -1 , 1 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Player 1: EU1(Rock, p2) = 0??(1/3)+(-1)??(1/3)+1??(1/3)=0 EU1(Paper, p2) = 1??(1/3)+0??(1/3)+(-1)??(1/3)=0 EU1(Scissors, p2) = (-1)??(1/3)+1??(1/3)+0??(1/3)=0 Player 2: EU2(Rock, p1)=0??(1/3)+(-1)??(1/3)+1??(1/3)=0 EU2(Paper, p1)=1??(1/3)+0??(1/3)+(-1)??(1/3)=0 EU2(Scissors, p1)=(-1)??(1/3)+1??(1/3)+0??(1/3)=0 Therefore, (p1=(1/3, 1/3, 1/3), p2=(1/3, 1/3, 1/3)) is a mixed strategy Nash equilibrium by Theorem 4. Player 2 0 , 0 -1 , 1 1 , -1 Scissors (1/3) Paper (1/3) 1 , -1 -1 , 1 Scissors (1/3) 0 , 0 1 , -1 Paper (1/3) Player 1 -1 , 1 0 , 0 Rock (1/3) Rock (1/3) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Check whether there is a mixed strategy Nash equilibrium in which one of p11, p12, p13 is positive, and at least two of p21, p22, p23 are positive. The answer is No. Player 2 0 , 0 -1 , 1 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Check whether there is a mixed strategy Nash equilibrium in which two of p11, p12, p13 is positive, and at least two of p21, p22, p23 are positive. The answer is No. Player 2 0 , 0 -1 , 1 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 -1 , 1 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Example: Rock, paper and scissors Therefore, (p1=(1/3, 1/3, 1/3), p2=(1/3, 1/3, 1/3)) is the unique mixed strategy Nash equilibrium by Theorem 4. Player 2 0 , 0 -1 , 1 1 , -1 Scissors (p23) Paper (p22) 1 , -1 -1 , 1 Scissors (p13) 0 , 0 1 , -1 Paper (p12) Player 1 1 , 1 - 0 , 0 Rock (p11) Rock (p21) 73-347 Game Theory--Lecture 10 Summary Find mixed strategy Nash equilibrium in a 2-player game each with a finite number of pure strategies Next time Review HW1 Reading lists Cha 4.10 of Osborne Solutions to HW1 73-347 Game Theory--Lecture 10 Lecture 10