lecture8(博弈论讲义(Carnegie-Mellon-University))汇总课件.ppt

《lecture8(博弈论讲义(Carnegie-Mellon-University))汇总课件.ppt》由会员分享，可在线阅读，更多相关《lecture8(博弈论讲义(Carnegie-Mellon-University))汇总课件.ppt（26页珍藏版）》请在三一办公上搜索。

1、Static (or Simultaneous-Move) Games of Complete Information,Mixed Strategy Nash Equilibrium,May 29, 2003,1,73-347 Game Theory-Lecture 8,Static (or Simultaneous-Move),Outline of Static Games of Complete Information,Introduction to gamesNormal-form (or strategic-form) representation Iterated eliminati

2、on of strictly dominated strategies Nash equilibriumReview of concave functions, optimizationApplications of Nash equilibrium Mixed strategy Nash equilibrium,May 29, 2003,2,73-347 Game Theory-Lecture 8,Outline of Static Games of Com,Todays Agenda,Review of previous classMixed strategy Nash equilibri

3、um in Battle of sexesUse indifference to find mixed strategy Nash equilibria,May 29, 2003,3,73-347 Game Theory-Lecture 8,Todays AgendaReview of previo,Mixed strategy equilibrium,Mixed Strategy:A mixed strategy of a player is a probability distribution over the players strategies.Mixed strategy equil

4、ibriumA probability distribution for each playerThe distributions are mutual best responses to one another in the sense of expected payoffs,May 29, 2003,4,73-347 Game Theory-Lecture 8,Mixed strategy equilibriumMixe,Chris expected payoff of playing Opera: 2qChris expected payoff of playing Prize Figh

5、t: 1-qChris best response B1(q):Prize Fight (r=0) if q1/3 Any mixed strategy (0r1) if q=1/3,Battle of sexes,May 29, 2003,5,73-347 Game Theory-Lecture 8,Chris expected payoff of play,Pats expected payoff of playing Opera: rPats expected payoff of playing Prize Fight: 2(1-r)Pats best response B2(r):Pr

6、ize Fight (q=0) if r2/3Any mixed strategy (0q1) if r=2/3,Battle of sexes,May 29, 2003,6,73-347 Game Theory-Lecture 8,Pats expected payoff of playi,Chris best response 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 strateg

7、y (0q1) if r=2/3,Battle of sexes,2/3,Three Nash equilibria:(1, 0), (1, 0)(0, 1), (0, 1)(2/3, 1/3), (1/3, 2/3),1/3,May 29, 2003,7,73-347 Game Theory-Lecture 8,1qr1Chris best response B1(q),Expected payoffs: 2 players each with two pure strategies,Player 1 plays a mixed strategy (r, 1- r ). Player 2 p

8、lays 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(s12, (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

9、, 1-q)+(1-r)EU1(s12, (q, 1-q),May 29, 2003,8,73-347 Game Theory-Lecture 8,Expected payoffs: 2 players ea,Expected payoffs: 2 players each with two pure strategies,Player 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

10、, (r, 1-r)=ru2(s11, 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),May 29, 2003,9,73-347 Game Theory-Lecture 8,Expected p

11、ayoffs: 2 players ea,Mixed strategy 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*,

12、 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 1,May 29, 2003,10,73-347 Game Theory-Lecture 8,Mixed strategy equilibrium: 2-,2-player each with two strategies,Theorem 1 (property of mixed Nash equilibrium)A pair of mixed strategie

13、s (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*),May 29, 2003,11,73-347 Game Theory-Lecture 8,2-player each w

14、ith two strateg,Theorem 1: illustration,Player 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.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=0,May 29, 2003,12,73-347 Gam

15、e Theory-Lecture 8,Theorem 1: illustrationPlayer,Theorem 1: illustration,Player 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

16、strategy Nash equilibrium by Theorem 1.,May 29, 2003,13,73-347 Game Theory-Lecture 8,Theorem 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=50Employees expected

17、 payoff of her mixed strategy v1(0.9, 0.1), (0.5, 0.5)=0.950+0.150=50,Theorem 1: illustration,May 29, 2003,14,73-347 Game Theory-Lecture 8,Employees expected payoff of,Managers expected payoff of playing “Monitor”EU2(Monitor, (0.9, 0.1) = 0.990+0.1(-10) =80Managers expected payoff of playing “Not”EU

18、2(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=80,Theorem 1: illustration,May 29, 2003,15,73-347 Game Theory-Lecture 8,Managers expected payoff of p,Employeev1(0.9, 0.1), (0.5, 0.5) EU1(Work, (0.5, 0.5)v1(0.9, 0.1), (0.5,

19、0.5) EU1(Shirk, (0.5, 0.5)Managerv2(0.9, 0.1), (0.5, 0.5) EU2(Monitor, (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: illustration,May 29, 2003,16,73-347 Game Theory-Lecture 8,EmployeeTheorem 1: illus

20、tratio,Use Theorem 1 to check whether (2/3, 1/3), (1/3, 2/3) is a mixed strategy Nash equilibrium.,Theorem 1: illustration,May 29, 2003,17,73-347 Game Theory-Lecture 8,Use Theorem 1 to check whether,Mixed strategy equilibrium: 2-player each with two strategies,Theorem 2 Let (r*, 1-r*), (q*, 1-q*) be

21、 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 strategies.,May 29, 2003,18,73-347 Ga

22、me Theory-Lecture 8,Mixed 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, 2003,19,73-3

23、47 Game Theory-Lecture 8,Use indifference to find mixed,Use Theorem 2 to find mixed strategy Nash equilibrium: illustration,Player 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

24、 give us q = 1/2,May 29, 2003,20,73-347 Game Theory-Lecture 8,Use Theorem 2 to find mixed st,Use Theorem 2 to find mixed strategy Nash equilibrium: illustration,Player 2 is indifferent between playing Head and Tail.EU2(H, (r, 1r) = r 1+(1r)(-1) =2r 1EU2(T, (r, 1r) = r(-1)+(1r)1 = 1 2rEU2(H, (r, 1r)

25、= 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.,May 29, 2003,21,73-347 Game Theory-Lecture 8,Use Theorem 2 to find mixed st,Employees expected payoff of playing “work”EU1(Work, (q, 1q) = q50 + (1q)50=50 Employees

26、 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/2,Use Theorem 2 to find mixed strategy Nash equilibrium: illustration,May 29, 2003,22,73-347 Game Theory-Lecture 8,Employees expected payoff of,Managers e

27、xpected 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 mixed strate

28、gy Nash equilibrium by Theorem 2.,Use Theorem 2 to find mixed strategy Nash equilibrium: illustration,May 29, 2003,23,73-347 Game Theory-Lecture 8,Managers expected payoff of p,Use Theorem 2 to find a mixed Nash equilibrium,Use Theorem 2 to find mixed strategy Nash equilibrium: illustration,May 29,

29、2003,24,73-347 Game Theory-Lecture 8,Use Theorem 2 to find a mixed,Use Theorem 2 to find a mixed Nash equilibrium,Use Theorem 2 to find mixed strategy Nash equilibrium: illustration,May 29, 2003,25,73-347 Game Theory-Lecture 8,Use Theorem 2 to find a mixed,Summary,Mixed strategiesMixed Nash equilibriumFind mixed Nash equilibriumNext time2-player game each with a finite number of strategiesReading listsChapter 1.3 of Gibbons and Cha 4.3 of Osborne,May 29, 2003,26,73-347 Game Theory-Lecture 8,SummaryMixed strategiesMay 29,