lecture8(博弈論講義(Carnegie-Mellon-University))匯總課件

1、Static (or Simultaneous-Move) Games of Complete InformationMixed Strategy Nash EquilibriumMay 29, 2003173-347 Game Theory-Lecture 8Static (or Simultaneous-Move) Outline of Static Games of Complete Information Introduction to gamesNormal-form (or strategic-form) representation Iterated elimination of

2、 strictly dominated strategies Nash equilibriumReview of concave functions, optimizationApplications of Nash equilibrium Mixed strategy Nash equilibrium May 29, 2003273-347 Game Theory-Lecture 8Outline of Static Games of ComTodays AgendaReview of previous classMixed strategy Nash equilibrium in Batt

3、le of sexesUse indifference to find mixed strategy Nash equilibriaMay 29, 2003373-347 Game Theory-Lecture 8Todays AgendaReview of previoMixed strategy equilibriumMixed Strategy:A mixed strategy of a player is a probability distribution over the players strategies.Mixed strategy equilibriumA probabil

4、ity distribution for each playerThe distributions are mutual best responses to one another in the sense of expected payoffsMay 29, 2003473-347 Game Theory-Lecture 8Mixed strategy equilibriumMixeChris expected payoff of playing Opera: 2qChris expected payoff of playing Prize Fight: 1-qChris best resp

5、onse B1(q):Prize Fight (r=0) if q1/3 Any mixed strategy (0r1) if q=1/3Battle of sexesPatOpera (q)Prize Fight (1-q)ChrisOpera ( r )2 , 10 , 0Prize Fight (1-r)0 , 01 , 2May 29, 2003573-347 Game Theory-Lecture 8Chris expected payoff of playPats expected payoff of playing Opera: rPats expected payoff of

6、 playing Prize Fight: 2(1-r)Pats best response B2(r):Prize Fight (q=0) if r2/3Any mixed strategy (0q1) if r=2/3, Battle of sexesPatOpera (q)Prize Fight (1-q)ChrisOpera ( r )2 , 10 , 0Prize Fight (1-r)0 , 01 , 2May 29, 2003673-347 Game Theory-Lecture 8Pats expected payoff of playi1qr1Chris best respo

7、nse B1(q):Prize Fight (r=0) if q1/3 Any mixed strategy (0r1) if q=1/3Pats best response B2(r):Prize Fight (q=0) if r2/3 Any mixed strategy (0q1) if r=2/3Battle of sexes2/3Three Nash equilibria:(1, 0), (1, 0)(0, 1), (0, 1)(2/3, 1/3), (1/3, 2/3)1/3May 29, 2003773-347 Game Theory-Lecture 81qr1Chris bes

8、t response B1(q)Expected payoffs: 2 players each with two pure strategiesPlayer 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: EU1(s1

9、2, (q, 1-q)= qu1(s12, s21)+(1-q)u1(s12, s22)Player 1s expected payoff from her mixed strategy:v1(r, 1-r), (q, 1-q)=rEU1(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, s21)u1(s12, s

10、22), u2(s12, s22)May 29, 2003873-347 Game Theory-Lecture 8Expected payoffs: 2 players eaExpected payoffs: 2 players each with two pure strategiesPlayer 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

11、, s21)+(1-r)u2(s12, s21)Player 2s expected payoff of playing s22: EU2(s22, (r, 1-r)= ru2(s11, s22)+(1-r)u2(s12, s22)Player 2s expected payoff from her mixed strategy:v2(r, 1-r),(q, 1-q)=qEU2(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)u

12、1(s11, s22), u2(s11, s22)s12 (1- r )u1(s12, s21), u2(s12, s21)u1(s12, s22), u2(s12, s22)May 29, 2003973-347 Game Theory-Lecture 8Expected payoffs: 2 players eaMixed strategy equilibrium: 2-player each with two pure strategiesMixed strategy Nash equilibrium:A pair of mixed strategies (r*, 1-r*), (q*,

13、 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 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

14、)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 29, 20031073-347 Game Theory-Lecture 8Mixed strategy equilibrium: 2-2-player each with two strategiesTheorem 1 (property of mixed Nash equilibrium)A pair of mixed strategies (r*, 1

15、-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*)Player 2s21 ( q )s22 ( 1- q )Player 1s11 ( r )u1(s11, s21), u2(s11, s

16、21)u1(s11, s22), u2(s11, s22)s12 (1- r )u1(s12, s21), u2(s12, s21)u1(s12, s22), u2(s12, s22)May 29, 20031173-347 Game Theory-Lecture 82-player each with two strategTheorem 1: illustrationPlayer 1:EU1(H, (0.5, 0.5) = 0.5(-1) + 0.51=0EU1(T, (0.5, 0.5) = 0.51 + 0.5(-1)=0v1(0.5, 0.5), (0.5, 0.5)=0.50+0.

17、50=0Player 2:EU2(H, (0.5, 0.5) = 0.51+0.5(-1) =0EU2(T, (0.5, 0.5) = 0.5(-1)+0.51 = 0v2(0.5, 0.5), (0.5, 0.5)=0.50+0.50=0Matching penniesPlayer 2H (0.5)T (0.5)Player 1H (0.5)-1 , 1 1 , -1T (0.5) 1 , -1-1 , 1May 29, 20031273-347 Game Theory-Lecture 8Theorem 1: illustrationPlayer Theorem 1: illustratio

18、nPlayer 1:v1(0.5, 0.5), (0.5, 0.5) EU1(H, (0.5, 0.5)v1(0.5, 0.5), (0.5, 0.5) EU1(T, (0.5, 0.5)Player 2:v2(0.5, 0.5), (0.5, 0.5) EU2(H, (0.5, 0.5)v2(0.5, 0.5), (0.5, 0.5) EU2(T, (0.5, 0.5)Hence, (0.5, 0.5), (0.5, 0.5) is a mixed strategy Nash equilibrium by Theorem 1.Matching penniesPlayer 2H (0.5)T

19、(0.5)Player 1H (0.5)-1 , 1 1 , -1T (0.5) 1 , -1-1 , 1May 29, 20031373-347 Game Theory-Lecture 8Theorem 1: illustrationPlayer Employees expected payoff of playing “work”EU1(Work, (0.5, 0.5) = 0.550 + 0.550=50 Employees expected payoff of playing “shirk”EU1(Shirk, (0.5, 0.5) = 0.50 + 0.5100=50Employee

20、s expected payoff of her mixed strategy v1(0.9, 0.1), (0.5, 0.5)=0.950+0.150=50Theorem 1: illustrationEmployee MonitoringManagerMonitor (0.5)Not Monitor (0.5)EmployeeWork (0.9)50 , 9050 , 100Shirk (0.1)0 , -10100 , -100May 29, 20031473-347 Game Theory-Lecture 8Employees expected payoff of Managers e

21、xpected payoff of playing “Monitor”EU2(Monitor, (0.9, 0.1) = 0.990+0.1(-10) =80Managers expected payoff of playing “Not”EU2(Not, (0.9, 0.1) = 0.9100+0.1(-100) = 80Managers expected payoff of her mixed strategy v2(0.9, 0.1), (0.5, 0.5)=0.580+0.580=80Theorem 1: illustrationEmployee MonitoringManagerMo

22、nitor (0.5)Not Monitor (0.5)EmployeeWork (0.9)50 , 9050 , 100Shirk (0.1)0 , -10100 , -100May 29, 20031573-347 Game Theory-Lecture 8Managers expected payoff of pEmployeev1(0.9, 0.1), (0.5, 0.5) EU1(Work, (0.5, 0.5)v1(0.9, 0.1), (0.5, 0.5) EU1(Shirk, (0.5, 0.5)Managerv2(0.9, 0.1), (0.5, 0.5) EU2(Monit

23、or, (0.9, 0.1)v2(0.9, 0.1), (0.5, 0.5) EU2(Not, (0.9, 0.1) Hence, (0.9, 0.1), (0.5, 0.5) is a mixed strategy Nash equilibrium by Theorem 1.Theorem 1: illustrationEmployee MonitoringManagerMonitor (0.5)No Monitor (0.5)EmployeeWork (0.9)50 , 9050 , 100Shirk (0.1)0 , -10100 , -100May 29, 20031673-347 G

24、ame Theory-Lecture 8EmployeeTheorem 1: illustratioUse Theorem 1 to check whether (2/3, 1/3), (1/3, 2/3) is a mixed strategy Nash equilibrium.Theorem 1: illustrationBattle of sexesPatOpera (1/3)Prize Fight (2/3)ChrisOpera (2/3 )2 , 10 , 0Prize Fight (1/3)0 , 01 , 2May 29, 20031773-347 Game Theory-Lec

25、ture 8Use Theorem 1 to check whetherMixed strategy equilibrium: 2-player each with two strategiesTheorem 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*,

26、1-q*) EU2(s21, (r*, 1-r*) = EU2(s22, (r*, 1-r*)That is, each player is indifferent between her two strategies.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, s21)u1(s12, s22), u2(s12, s22)May 29, 20031873-347 Game The

27、ory-Lecture 8Mixed strategy equilibrium: 2-Use indifference to find mixed Nash equilibrium (2-player each with 2 strategies)Use Theorem 2 to find mixed strategy Nash equilibriaSolve EU1(s11, (q*, 1-q*) = EU1(s12, (q*, 1-q*)Solve EU2(s21, (r*, 1-r*) = EU2(s22, (r*, 1-r*)May 29, 20031973-347 Game Theo

28、ry-Lecture 8Use indifference to find mixedUse Theorem 2 to find mixed strategy Nash equilibrium: illustrationPlayer 1 is indifferent between playing Head and Tail.EU1(H, (q, 1q) = q(-1) + (1q)1=12qEU1(T, (q, 1q) = q1 + (1q) (-1)=2q1EU1(H, (q, 1q) = EU1(T, (q, 1q) 12q = 2q1 4q = 2 This give us q = 1/

29、2Matching penniesPlayer 2H ( q )T ( 1q )Player 1H ( r )-1 , 1 1 , -1T ( 1r ) 1 , -1-1 , 1May 29, 20032073-347 Game Theory-Lecture 8Use Theorem 2 to find mixed stUse Theorem 2 to find mixed strategy Nash equilibrium: illustrationPlayer 2 is indifferent between playing Head and Tail.EU2(H, (r, 1r) = r

30、 1+(1r)(-1) =2r 1EU2(T, (r, 1r) = r(-1)+(1r)1 = 1 2rEU2(H, (r, 1r) = EU2(T, (r, 1r) 2r 1= 1 2r 4r = 2 This give us r = 1/2Hence, (0.5, 0.5), (0.5, 0.5) is a mixed strategy Nash equilibrium by Theorem 2.Matching penniesPlayer 2H ( q )T ( 1q )Player 1H ( r )-1 , 1 1 , -1T ( 1r ) 1 , -1-1 , 1May 29, 20

31、032173-347 Game Theory-Lecture 8Use Theorem 2 to find mixed stEmployees expected payoff of playing “work”EU1(Work, (q, 1q) = q50 + (1q)50=50 Employees expected payoff of playing “shirk”EU1(Shirk, (q, 1q) = q0 + (1q)100=100(1q)Employee is indifferent between playing Work and Shirk. 50=100(1q)q=1/2Use

32、 Theorem 2 to find mixed strategy Nash equilibrium: illustrationEmployee MonitoringManagerMonitor ( q )Not Monitor (1q )EmployeeWork (r)50 , 9050 , 100Shirk (1r)0 , -10100 , -100May 29, 20032273-347 Game Theory-Lecture 8Employees expected payoff of Managers expected payoff of playing “Monitor”EU2(Monitor, (r, 1r) = r90+(1r)(-10) =100r10Managers expected payoff of playing “Not”EU2(Not, (r, 1r) = r100+(1r)(-100) =200r100Manager is indifferent between playing Monitor and Not 100r10 =200r100 implies that r=0.9.Hence, (0.9, 0.1), (0.5, 0.5) is a mix