MS&E246:Lecture3PurestrategyNashequilibriumRamesh JohariJanuary 16, 2007Outline• Best response and pure strategyNash equilibrium• Relation to other equilibrium notions• Examples• Bertrand competitionBestresponsesetBest response set for player n to s-n:Rn(s-n) = arg maxsn∈ SnΠn(sn, s-n)[ Note: arg maxx ∈ Xf(x) is theset of x that maximize f(x) ]NashequilibriumGiven: N-player gameA vector s = (s1, …, sN) is a (pure strategy) Nash equilibrium if:si∈ Ri(s-i)for all players i.Each individual plays a best response to the others.NashequilibriumPure strategy Nash equilibrium is robust to unilateral deviationsOne of the hardest questions ingame theory:How do players know to play a Nash equilibrium?Example:Prisoner’sdilemmaRecall the routing game:(-2,-2)(-5,-1)far(-1,-5)(-4,-4)nearfarnearAT&TMCIExample:Prisoner’sdilemmaHere (near,near) is the unique (pure strategy) NE:(-2,-2)(-5,-1)far(-1,-5)(-4,-4)nearfarnearAT&TMCISummaryofrelationshipsGiven a game:• Any DSE also survives ISD, and is a NE.(DSE = dominant strategy equilibrium; ISD = iterated strict dominance)Example:biddinggameRecall the bidding game from lecture 1:$4$3$2$1$0$4.00$4.57$5.33$6.40$8.00$4$4.43$5.00$5.80$7.00$9.00$3$4.67$5.20$6.00$7.33$10.00$2$4.60$5.00$5.67$7.00$11.00$1$4.00$4.00$4.00$4.00$4.00$0Player 2’s bidPlayer 1’s bidExample:biddinggameHere (2,2) is the unique (pure strategy) NE:$4$3$2$1$0$4.00$4.57$5.33$6.40$8.00$4$4.43$5.00$5.80$7.00$9.00$3$4.67$5.20$6.00$7.33$10.00$2$4.60$5.00$5.67$7.00$11.00$1$4.00$4.00$4.00$4.00$4.00$0Player 2’s bidPlayer 1’s bidSummaryofrelationshipsGiven a game:• Any DSE also survives ISD, and is a NE.• If a game is dominance solvable, the resulting strategy vector is a NEAnother example of this: the Cournot game.• Any NE survives ISD (and is also rationalizable).(DSE = dominant strategy equilibrium; ISD = iterated strict dominance)Example:CournotduopolyUnique NE: (t/3 , t/3)t00s2R1(s2)R2(s1)tNash equilibrium =Any point where thebest response curvescross each other.s1Example:coordinationgameTwo players trying to coordinate their actions:(1,2)(0,0)r(0,0)(2,1)lRLPlayer 2Player 1Example:coordinationgameBest response of player 1:R1(L) = { l }, R1(R) = { r }(1,2)(0,0)r(0,0)(2,1)lRLPlayer 2Player 1Example:coordinationgameBest response of player 2:R2(l) = { L }, R2(r) = { R }(1,2)(0,0)r(0,0)(2,1)lRLPlayer 2Player 1Example:coordinationgameTwo Nash equilibria: (l, L) and (r, R).Moral: NE is not a unique predictor of play!(1,2)(0,0)r(0,0)(2,1)lRLPlayer 2Player 1Example:matchingpenniesNo pure strategy NE for this gameMoral: Pure strategy NE may not exist.(1,-1)(-1,1)T(-1,1)(1,-1)HTHPlayer 2Player 1Example:Bertrandcompetition•In Cournot competition, firms choosethe quantity they will produce.•In Bertrand competition, firms choosethe prices they will charge.Bertrandcompetition:model• Two firms• Each firm i chooses a price pi ≥ 0• Each unit produced incurs a cost c ≥ 0• Consumers only buy from the producer offering the lowest price• Demand is D > 0Bertrandcompetition:model• Two firms• Each firm i chooses a price pi• Profit of firm i:Πi(p1, p2) = (pi- c)Di(p1, p2)where0, if pi> p-iDi(p1, p2) = D, if pi< p-i½ D, if pi= p-iBertrandcompetition:analysisSuppose firm 2 sets a price = p2< c.What is the best response set of firm 1?Firm 1 wants to price higher than p2.R1(p2) = (p2, ∞)Bertrandcompetition:analysisSuppose firm 2 sets a price = p2> c.What is the best response set of firm 1?Firm 1 wants to price slightly lower than p2… but there is no best response!R1 (p2) = ∅Bertrandcompetition:analysisSuppose firm 2 sets a price = p2= c.What is the best response set of firm 1?Firm 1 wants to price at or higher than c.R1 (p2) = [c, ∞)Best response of firm 1:cBertrandcompetition:analysis00p2R1(p2)p1cBest response of firm 2:cBertrandcompetition:analysis00p2p1cR2(p1)Where do they “cross”?cBertrandcompetition:analysis00p2p1cR2(p1)R1(p2)Thus the unique NE is where p1= c, p2= c.cBertrandcompetition:analysis00p2p1cR2(p1)R1(p2)Unique NEBertrandcompetitionStraightforward to show:The same result holds ifdemand depends on price, i.e.,if the demand at price p is D(p) > 0.Proof technique:(1) Show pi< c is never played in a NE.(2) Show if c < p1< p2, then firm 2 prefers to lower p2.(3) Show if c < p1= p2, then firm 2prefers to lower p2BertrandcompetitionWhat happens if c1< c2?No pure NE exists; however, an ε-NE exists:Each player is happy as long as they arewithin ε of their optimal payoff.ε-NE : p2= c2, p1= c2- δ(where δ is infinitesimal)Bertrandvs.CournotAssume demand is D(p) = a - p.Interpretation: D(p) denotes the total number of consumers willing to payat least p for the good.Then the inverse demand isP (Q) = a - Q.This is the market-clearing price at which Q total units of supply would be sold.Bertrandvs.CournotAssume demand is D(p) = a - p.Then the inverse demand isP (Q) = a - Q.Assume c < a.Bertrand eq.: p1= p2= cCournot eq: q1= q2= (a - c)/3⇒ Cournot price = a/3 + 2c/3 > cCournottotal profits(Producersurplus)Bertrandvs.Cournot00pP (Q)QcaBertrand eq.(perfectly competitive)Cournot eq.ConsumersurplusCournottotal profits(Producersurplus)Bertrandvs.Cournot00pP (Q)QcaConsumersurplusDeadweight loss:Consumers arewilling to pay, andfirms could havemade a profit by sellingBertrandvs.Cournot• Cournot eq. price > Bertrand eq. price• Bertrand price =marginal cost of production• In Cournot eq., there is positive deadweight loss.This is because firms have market power:they anticipate their effect on prices.Questionstothinkabout•Can a weakly dominated strategy be played in a Nash equilibrium?•Can a strictly dominated strategy be played in a Nash equilibrium?• Why is any NE rationalizable?• What are real-world examples ofBertrand competition?Cournot competition?Summary:FindingNEFinding NE is typically a matter of checking the definition.Two basic approaches…FindingNE:Approach1First approach to finding NE:(1) Compute the complete best response mapping for each player.(2) Find where they intersect each other (graphically or otherwise).FindingNE:Approach2Second approach to finding NE:Fix a strategy vector (s1, …, sN).Check if any player has a profitable deviation.If so, it cannot be a NE.If not, it is an