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

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 elimination 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 equilibrium 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 equilibriumA 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 Fight: 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):Prize 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 strategy (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 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(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, 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, (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 payoffs: 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*, 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 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*),May 29, 2003,11,73-347 Game Theory-Lecture 8,2-player each with 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 Game 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 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 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”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=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, 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: illustratio,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 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 Game 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-347 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 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) = 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 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 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 mixed strategy 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, 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,