国外博弈论课件lecture(23).ppt

June 2, 2003,73-347 Game Theory-Lecture 10,1,Static (or Simultaneous-Move) Games of Complete Information,Mixed Strategy Nash Equilibrium,June 2, 2003,73-347 Game Theory-Lecture 10,2,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,June 2, 2003,73-347 Game Theory-Lecture 10,3,Todays Agenda,Review of previous class Example: Rock, paper and scissors (Exercise 139.1 of Osborne) How to find mixed strategy Nash equilibria in a 2-player game each with a finite number of strategies,June 2, 2003,73-347 Game Theory-Lecture 10,4,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,June 2, 2003,73-347 Game Theory-Lecture 10,5,Example: Rock, paper and scissors,Can you guess a mixed strategy Nash equilibrium?,June 2, 2003,73-347 Game Theory-Lecture 10,6,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,June 2, 2003,73-347 Game Theory-Lecture 10,7,2-player each with two strategies,Theorem 1 (property of mixed Nash equilibrium) A pair of mixed strategies (r*, 1-r*), (q*, 1-q*) is a Nash 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*),June 2, 2003,73-347 Game Theory-Lecture 10,8,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, 0q*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*) = EU2(s22, (r*, 1-r*) That is, each player is indifferent between her two pure strategies given the mixed strategy chosen by the other player.,June 2, 2003,73-347 Game Theory-Lecture 10,9,2-player each with a finite number of pure strategies,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,June 2, 2003,73-347 Game Theory-Lecture 10,10,2-player each with a finite number of pure strategies,Player 1s mixed strategy: p1=(p11, p12, ., p1J ) Player 2s mixed strategy: p2=(p21, p22, ., p2K ),Player 1,June 2, 2003,73-347 Game Theory-Lecture 10,11,Expected payoffs: 2-player each with a finite number of pure strategies,Player 1s expected payoff of pure strategy s11: EU1(s11, p2)=p21u1(s11, s21)+p22u1(s11, s22)+.+p2ku1(s11, s2k)+.+p2Ku1(s11, s2K) Player 1s expected payoff of pure strategy s12: EU1(s12, p2)=p21u1(s12, s21)+p22u1(s12, s22)+.+p2ku1(s12, s2k)+.+p2Ku1(s12, s2K) . Player 1s expected payoff of pure strategy s1J: EU1(s1J, p2)=p21u1(s1J, s21)+p22u1(s1J, s22)+.+p2ku1(s1J, s2k)+.+p2Ku1(s1J, s2K) Player 1s expected payoff from her mixed strategy p1: v1(p1, p2)=p11EU1(s11, p2)+p12EU1(s12, p2)+.+p1jEU1(s1j, p2)+. +p1JEU1(s1J, p2),June 2, 2003,73-347 Game Theory-Lecture 10,12,Expected payoffs: 2-player each with a finite number of pure strategies,Player 2s expected payoff of pure strategy s21: EU2(s21, p1)=p11u2(s11, s21)+p12u2(s12, s21)+.+p1ju2(s1j, s21)+.+p1Ju2(s1J, s21) Player 2s expected payoff of pure strategy s22: EU2(s22, p1)=p11u2(s11, s22)+p12u2(s12, s22)+.+p1ju2(s1j, s22)+.+p1Ju2(s1J, s22) . Player 2s expected payoff of pure strategy s2K: EU2(s2K, p1)=p11u2(s11, s2K)+p12u2(s12, s2K)+.+p1ju2(s1j, s2K)+.+p1Ju2(s1J, s2K) Player 2s expected payoff from her mixed strategy p2: v2(p1, p2)=p21EU2(s21, p1)+p22EU2(s22, p1) +.+p2kEU2(s2k, p1)+ +p2KEU2(s2K, p1),June 2, 2003,73-347 Game Theory-Lecture 10,13,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 1s mixed strategy p1* is a best response to player 2s mixed strategy p2*, and p2* is a best response to p1*. Or, v1(p1*, p2*) v1(p1, p2*), for all player 1s mixed strategy p1, and v2(p1*, p2*) v2(p1*, p2), for all player 2s mixed strategy p2. That is, given player 2s mixed strategy p2*, player 1 cannot be better off if she deviates from p1*. Given player 1s mixed strategy p1*, player 2 cannot be better off if she deviates from p2*.,June 2, 2003,73-347 Game Theory-Lecture 10,14,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,June 2, 2003,73-347 Game Theory-Lecture 10,15,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*),June 2, 2003,73-347 Game Theory-Lecture 10,16,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 2s p2*, player 1s expected payoff of every pure strategy to which she assigns positive probability is the same, and player 1s 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 1s p1*, player 2s expected payoff of every pure strategy to which she assigns positive probability is the same, and player 2s 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.,June 2, 2003,73-347 Game Theory-Lecture 10,17,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 2s 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 1s 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.,June 2, 2003,73-347 Game Theory-Lecture 10,18,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) = 00+3(1/3)+1(2/3)=5/3, EU1(M, p2) = 40+0(1/3)+2(2/3)=4/3 EU1(B, p2) = 30+5(1/3)+0(2/3)=5/3. Hence, EU1(T, p2) = EU1(B, p2) EU1(M, p2),June 2, 2003,73-347 Game Theory-Lecture 10,19,Theorem 4: illustration,Player 2: EU2(L, p1)=2(3/4) + 00 + 4(1/4)=5/2, EU2(C, p1)=3(3/4) + 40 + 1(1/4)=5/2, EU2(R, p1)=1(3/4) + 30 + 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.,June 2, 2003,73-347 Game Theory-Lecture 10,20,Example: Rock, paper and scissors,Check whether there is a mixed strategy Nash equilibrium in which p110, p120, p130, p210, p220, p230.,June 2, 2003,73-347 Game Theory-Lecture 10,21,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.,June 2, 2003,73-347 Game Theory-Lecture 10,22,Example: Rock, paper and scissors,Player 1 is indifferent among her three pure strategies: EU1(Rock, p2) = 0p21+(-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.,June 2, 2003,73-347 Game Theory-Lecture 10,23,Example: Rock, paper and scissors,0p21+(-1) p22+1 p23= 1 p21+0 p22+(-1) p23 0p21+(-1) p22+1 p23 = (-1) p21+1 p22+0 p23 p21+ p22+ p23=1 The solution is p21= p22= p23=1/3,June 2, 2003,73-347 Game Theory-Lecture 10,24,Example: Rock, paper and scissors,Player 2 is indifferent among her three pure strategies: EU2(Rock, p1)=0p11+(-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.,June 2, 2003,73-347 Game Theory-Lecture 10,25,Example: Rock, paper and scissors,0p11+(-1) p12+1 p13=1 p11+0 p12+(-1) p13 0p11+(-1) p12+1 p13=(-1) p11+1 p12+0 p13 p11+ p12+ p13=1 The solution is p11= p12= p13=1/3,June 2, 2003,73-347 Game Theory-Lecture 10,26,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