lecture7Mixed Strategy Nash Equilibrium(博弈论,Carnegie Mellon University)课件

1、May 28, 200373-347 Game Theory-Lecture 71Static (or Simultaneous-Move) Games of Complete InformationMixed Strategy Nash EquilibriumMay 28, 200373-347 Game Theory-Lecture 72Outline of Static Games of Complete Information nIntroduction to gamesnNormal-form (or strategic-form) representation nIterated

2、elimination of strictly dominated strategies nNash equilibriumnReview of concave functions, optimizationnApplications of Nash equilibrium nMixed strategy Nash equilibrium May 28, 200373-347 Game Theory-Lecture 73Todays AgendanReview of previous classnMixed strategiesnMixed strategy Nash equilibriumn

3、Use best response to find mixed strategy Nash equilibriumMay 28, 200373-347 Game Theory-Lecture 74Matching penniesnHead is Player 1s best response to Player 2s strategy TailnTail is Player 2s best response to Player 1s strategy TailnTail is Player 1s best response to Player 2s strategy HeadnHead is

4、Player 2s best response to Player 1s strategy HeadHence, NO Nash equilibriumPlayer 2HeadTailPlayer 1Head-1 , 1 1 , -1Tail 1 , -1-1 , 1May 28, 200373-347 Game Theory-Lecture 75Solving matching penniesnRandomize your strategies to surprise the rivalPlayer 1 chooses Head and Tail with probabilities r a

5、nd 1-r, respectively. Player 2 chooses Head and Tail with probabilities q and 1-q, respectively.nMixed Strategy:Specifies that an actual move be chosen randomly from the set of pure strategies with some specific probabilities.Player 2HeadTailPlayer 1Head-1 , 1 1 , -1Tail 1 , -1-1 , 1q1-qr1-rMay 28,

6、200373-347 Game Theory-Lecture 761qr11/21/2Solving matching penniesnPlayer 1s best responseB1(q):Head (r=1) if q0.5 Any mixed strategy (0r1) if q=0.5Player 2HeadTailPlayer 1Head-1 , 1 1 , -1Tail 1 , -1-1 , 1q1-q1-2q2q-1Expected payoffsr1-rMay 28, 200373-347 Game Theory-Lecture 77Solving matching pen

7、niesnPlayer 2s best responseB2(r):Tail (q=0) if r0.5Any mixed strategy (0q1) if r=0.5 Player 2HeadTailPlayer 1Head-1 , 1 1 , -1Tail 1 , -1-1 , 1q1-q1-2q2q-1Expected payoffsr1-rExpected payoffs2r-11-2r1qr11/21/2May 28, 200373-347 Game Theory-Lecture 781qr11/21/2Solving matching penniesnPlayer 1s best

8、 responseB1(q):Head (r=1) if q0.5 Any mixed strategy (0r1) if q=0.5nPlayer 2s best responseB2(r):Tail (q=0) if r0.5Any mixed strategy (0q1) if r=0.5Check r = 0.5 is best response to q=0.5q = 0.5 is best response to r=0.5Player 2HeadTailPlayer 1Head-1 , 1 1 , -1Tail 1 , -1-1 , 1r1-rq1-qMixed strategy

9、 Nash equilibriumMay 28, 200373-347 Game Theory-Lecture 79Mixed strategynMixed Strategy:A mixed strategy of a player is a probability distribution over players (pure) strategies.May 28, 200373-347 Game Theory-Lecture 710Mixed strategy: examplenMatching penniesnPlayer 1 has two pure strategies: H and

10、 T( 1(H)=0.5, 1(T)=0.5 ) is a Mixed strategy. That is, player 1 plays H and T with probabilities 0.5 and 0.5, respectively.( 1(H)=0.3, 1(T)=0.7 ) is another Mixed strategy. That is, player 1 plays H and T with probabilities 0.3 and 0.7, respectively.May 28, 200373-347 Game Theory-Lecture 711Mixed st

11、rategy: examplenPlayer 1: (3/4, 0, ) is a mixed strategy. That is, 1(T)=3/4, 1(M)=0 and 1(B)=1/4.nPlayer 2: (0, 1/3, 2/3) is a mixed strategy. That is, 2(L)=0, 2(C)=1/3 and 2(R)=2/3.Player 2L (0)C (1/3)R (2/3)Player 1T (3/4)0 , 23 , 31 , 1M (0)4 , 00 , 42 , 3B (1/4)3 , 45 , 10 , 7May 28, 200373-347

12、Game Theory-Lecture 712Expected payoffs: 2 players each with two pure strategiesnPlayer 1 plays a mixed strategy (r, 1- r ). Player 2 plays a mixed strategy ( q, 1- q ).Player 1s expected payoff of playing s11: EU1(s11, (q, 1-q)=qu1(s11, s21)+(1-q)u1(s11, s22)Player 1s expected payoff of playing s12

13、: EU1(s12, (q, 1-q)= qu1(s12, s21)+(1-q)u1(s12, s22)nPlayer 1s expected payoff from her mixed strategy:v1(r, 1-r), (q, 1-q)=r EU1(s11, (q, 1-q)+(1-r) EU1(s12, (q, 1-q)Player 2s21 ( q )s22 ( 1- q )Player 1s11 ( r )u1(s11, s21), u2(s11, s21)u1(s11, s22), u2(s11, s22)s12 (1- r )u1(s12, s21), u2(s12, s2

14、1)u1(s12, s22), u2(s12, s22)May 28, 200373-347 Game Theory-Lecture 713Expected payoffs: 2 players each with two pure strategiesnPlayer 1 plays a mixed strategy (r, 1- r ). Player 2 plays a mixed strategy ( q, 1- q ).Player 2s expected payoff of playing s21: EU2(s21, (r, 1-r)=ru2(s11, s21)+(1-r)u2(s1

15、2, s21)Player 2s expected payoff of playing s22: EU2(s22, (r, 1-r)= ru2(s11, s22)+(1-r)u2(s12, s22)nPlayer 2s expected payoff from her mixed strategy:v2(r, 1-r),(q, 1-q)=q EU2(s21, (r, 1-r)+(1-q) EU2(s22, (r, 1-r)Player 2s21 ( q )s22 ( 1- q )Player 1s11 ( r )u1(s11, s21), u2(s11, s21)u1(s11, s22), u

16、2(s11, s22)s12 (1- r )u1(s12, s21), u2(s12, s21)u1(s12, s22), u2(s12, s22)May 28, 200373-347 Game Theory-Lecture 714Expected payoffs: examplenPlayer 1:EU1(H, (0.3, 0.7) = 0.3(-1) + 0.71=0.4EU1(T, (0.3, 0.7) = 0.31 + 0.7(-1)=-0.4v1(0.4, 0.6), (0.3, 0.7)=0.4 0.4+0.6 (-0.4)=-0.08nPlayer 2:EU2(H, (0.4,

17、0.6) = 0.41+0.6(-1) = -0.2EU2(T, (0.4, 0.6) = 0.4(-1)+0.61 = 0.2v2(0.4, 0.6), (0.3, 0.7)=0.3(-0.2)+0.70.2=0.08Player 2H (0.3)T (0.7)Player 1H (0.4)-1 , 1 1 , -1T (0.6) 1 , -1-1 , 1May 28, 200373-347 Game Theory-Lecture 715Expected payoffs: examplenMixed strategies: p1=( 3/4, 0, ); p2=( 0, 1/3, 2/3 )

18、.nPlayer 1: EU1(T, p2)=3(1/3)+1(2/3)=5/3, EU1(M, p2)=0(1/3)+2(2/3)=4/3EU1(B, p2)=5(1/3)+0(2/3)=5/3. v1(p1, p2) = 5/3nPlayer 2: EU2(L, p1)=2(3/4)+4(1/4)=5/2, EU2(C, p1)=3(3/4)+3(1/4)=5/2,EU2(R, p1)=1(3/4)+7(1/4)=5/2. v1(p1, p2) = 5/2Player 2L (0)C (1/3)R (2/3)Player 1T (3/4)0 , 23 , 31 , 1M (0)4 , 00

19、 , 42 , 3B (1/4)3 , 45 , 10 , 7May 28, 200373-347 Game Theory-Lecture 716Mixed strategy equilibriumnMixed strategy equilibriumA probability distribution for each playerThe distributions are mutual best responses to one another in the sense of expected payoffsMay 28, 200373-347 Game Theory-Lecture 71

20、7Mixed strategy equilibrium: 2-player each with two pure strategiesnMixed strategy Nash equilibrium:nA 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*)

21、v1(r, 1-r), (q*, 1-q*), for all 0 r 1v2(r*, 1-r*), (q*, 1-q*) v2(r*, 1-r*), (q, 1-q), for all 0 q 1Player 2s21 ( q )s22 ( 1- q )Player 1s11 ( r )u1(s11, s21), u2(s11, s21)u1(s11, s22), u2(s11, s22)s12 (1- r )u1(s12, s21), u2(s12, s21)u1(s12, s22), u2(s12, s22)May 28, 200373-347 Game Theory-Lecture 7

22、18Find mixed strategy equilibrium in 2-player each with two pure strategiesnFind the best response correspondence for player 1, given player 2s mixed strategynFind the best response correspondence for player 2, given player 1s mixed strategynUse the best response correspondences to determine mixed s

23、trategy Nash equilibria.May 28, 200373-347 Game Theory-Lecture 719Employee MonitoringnEmployees can work hard or shirknSalary: $100K unless caught shirking nCost of effort: $50KnManagers can monitor or notnValue of employee output: $200KnProfit if employee doesnt work: $0nCost of monitoring: $10KMay

24、 28, 200373-347 Game Theory-Lecture 720nEmployees best response B1(q):Shirk (r=0) if q0.5Any mixed strategy (0 r 1) if q=0.5Employee MonitoringManagerMonitor ( q )Not Monitor (1-q)EmployeeWork ( r )50 , 9050 , 100Shirk (1-r )0 , -10100 , -10050100(1-q)Expected payoffsExpected payoffs100r-10200r-100M

25、ay 28, 200373-347 Game Theory-Lecture 721nManagers best response B2(r):Monitor (q=1) if r0.9 Any mixed strategy (0 q 1) if r=0.9Employee MonitoringManagerMonitor ( q )Not Monitor (1-q)EmployeeWork ( r )50 , 9050 , 100Shirk (1-r )0 , -10100 , -10050100(1-q)Expected payoffsExpected payoffs100r-10200r-100May 28, 200373-347 Game Theory-Lecture 7221qr10.5nEmployees best response B1(q):Shirk (r=0) if q0.5 Any mixed strategy (0 r 1) if q=0.5nManagers best response B2(r):Monitor (q=1) if r0.9 Any mixe