WIXLIB

Nash EquilibriumIchiro ObaraUCLAJanuary 11, 2012Obara (UCLA)Nash EquilibriumJanuary 11, 20121 / 31

Best Response and Nash EquilibriumIn many games, there is no obvious choice (i.e. dominant action).In such games, players are in strategic situation: each player’s optimalchoice depends on the other players’ choices.Obara (UCLA)Nash EquilibriumJanuary 11, 20122 / 31

Best Response and Nash EquilibriumCoordination GameObara (UCLA)BCB1, 10, 0C0, 01, 1Nash EquilibriumJanuary 11, 20123 / 31

Best Response and Nash EquilibriumChicken GameObara (UCLA)ABA0, 04, 1B1, 43, 3Nash EquilibriumJanuary 11, 20124 / 31

Best Response and Nash EquilibriumMatching PennyOne more.Obara (UCLA)HTH1, -1-1, 1T-1, 11, -1Nash EquilibriumJanuary 11, 20125 / 31

Best Response and Nash EquilibriumWe need a solution concept to make a prediction in such situations.The one that is most common one in Economics is Nash EquilibriumIn Nash equilibrium, every player plays a best response against theother players simultaneously.Obara (UCLA)Nash EquilibriumJanuary 11, 20126 / 31

Best Response and Nash EquilibriumBest ResponseBest Responseai Ai is a best response to a i A i ifui (ai , a i ) ui (ai0 , a i ) for all ai0 AiFor example, B is player 1’s best response to A by player 2 in Chickengame.Obara (UCLA)Nash EquilibriumJanuary 11, 20127 / 31

Best Response and Nash EquilibriumNash EquilibriumNash equilibrium for a strategic game is a profile of actions suchthat each action is a best response to the other actions.Let Bi (a i ) Ai be the set of player i’s best response actions againsta i A i . Here is the formal definition of Nash equilibrium.Nash Equilibrium ) for everya (a1 , · · · , an ) A is a Nash Equilibrium if ai Bi (a ii N.Obara (UCLA)Nash EquilibriumJanuary 11, 20128 / 31

Best Response and Nash EquilibriumNash EquilibriumHow to find a Nash equilibrium? It’s easy for games with two players and finiteactions.Chicken GameObara (UCLA)ABA0, 04, 1B1, 43, 3Nash EquilibriumJanuary 11, 20129 / 31

Best Response and Nash EquilibriumNash EquilibriumHow to find a Nash equilibrium? It’s easy for games with two players and finiteactions.IPlayer 1’s best response against each of player 2’s strategy red circle.Chicken GameObara (UCLA)ABA0, 04, 1B1, 43, 3Nash EquilibriumJanuary 11, 20129 / 31

Best Response and Nash EquilibriumNash EquilibriumHow to find a Nash equilibrium? It’s easy for games with two players and finiteactions.IPlayer 1’s best response against each of player 2’s strategy red circle.IPlayer 2’s best response against each of player 1’s strategy blue circle.Chicken GameObara (UCLA)ABA0, 04, 1B1, 43, 3Nash EquilibriumJanuary 11, 20129 / 31

Best Response and Nash EquilibriumNash EquilibriumHow to find a Nash equilibrium? It’s easy for games with two players and finiteactions.IPlayer 1’s best response against each of player 2’s strategy red circle.IPlayer 2’s best response against each of player 1’s strategy blue circle.INE (A,B),(B,A).Chicken GameABA0, 04, 1B1, 43, 3NEObara (UCLA)Nash EquilibriumJanuary 11, 20129 / 31

Best Response and Nash EquilibriumNash Equilibrium(B, B) and (C , C ) are NE for Coordination game. There is no NE forMP.A few observations regarding NE and DSE:IA dominant strategy equilibrium is a Nash equilibrium.IIf every player has a strictly dominant action (as in PD), then a profileof strictly dominant actions is the only Nash equilibrium.Obara (UCLA)Nash EquilibriumJanuary 11, 201210 / 31

Best Response and Nash EquilibriumIs Nash equilibrium reasonable?1Nash Equilibrium as Self-Enforcing Behavior: If every playerbelieves that a particular Nash equilibrium is played, then there is noincentive to deviate from it for any player.2Nash Equilibrium as a Steady State of Learning/Evolution:Suppose that a player plays the same game repeatedly with differentplayers in a large population. If players’ behavior converges to aparticular action profile, then it is reasonable to think that it must bea Nash equilibrium.11This may be true even if a player plays the same game with the same playerrepeatedly.Obara (UCLA)Nash EquilibriumJanuary 11, 201211 / 31

Best Response and Nash EquilibriumIs Nash equilibrium reasonable?There are some issues, which we will deal with in more detail later.ICoordination: There are often many NE. Why should we expect thatthe expectations of the players are consistent?IEquilibrium Selection: Suppose that players play a NE. Even so, asan outsider, we are not sure about which NE is played. Some NE seemsto be more reasonable than others. So we need “refinement” of NE.INon-Nash Behavior: Nash equilibrium is sometimes too strong. Insome experiments, people don’t play any Nash equilibrium, especially inthe short run. We may want to relax the notion of Nash equilibrium orcome up with a new notion of equilibrium to capture actual behavior insuch games.Obara (UCLA)Nash EquilibriumJanuary 11, 201212 / 31

ApplicationsExample 1: First Price AuctionWe discuss a few examples to illustrate the idea of NE. Let’s start with FPA.Suppose that n bidders with values v1 v2 . vn 0 submit bidsb (b1 , ., bn ) n simultaneously for some good.The highest bidder wins and pays his or her own bid. Bidder i’s payoff isvi bi when winning the good by bidding bi . The winner isdetermined randomly when tied. The bidders maximize their expectedpayoffs.Can you find any Nash equilibrium? Who wins?Change the tie-breaking rule: the bidder with the smallest index would winwhen tied. Can you find any Nash equilibrium? Who wins?Obara (UCLA)Nash EquilibriumJanuary 11, 201213 / 31

ApplicationsExample 2: Cournot Model of DuopolyFirm 1 and firm 2 produce a homogeneous good.The firms choose their output q (q1 , q2 ) 2 simultaneously.The market price is determined by the inverse demand function:P(q1 q2 ).Firm i’s profit is πi (q) P(q1 q2 )qi Ci (qi ).Ci (qi ) is firm i’s costfunction.Obara (UCLA)Nash EquilibriumJanuary 11, 201214 / 31

ApplicationsExample 2: Cournot Model of DuopolySuppose that P(q) 12 q1 q2 (or 0 if negative) and Ci (qi ) 3qi .Find a Nash equilibrium.Consider a simple adaptive process (q1 (0), q2 (1), q1 (2), .) whereqi (t) is a best response to q i (t 1). Verify that it converges to aNash equilibrium given any starting point (q1 (0)).Consider n firms with the same identical linear cost function and thesame inverse demand function.ICan you find a Nash equilibrium?IIs there any relationship between the market price and the number offirms in equilibrium?Obara (UCLA)Nash EquilibriumJanuary 11, 201215 / 31

ApplicationsExample 3: Bertrand Model of DuopolyThere are two firms 1 and 2 that produce similar, but differentproducts (differentiated products).The firms choose their prices p (p1 , p2 ) simultaneously.Each firm’s demand qi depends on both prices (their products areimperfect substitutes, ex. coffee and tea).Firm i’s profit is πi (p) pi qi (p) Ci (qi (p)).Obara (UCLA)Nash EquilibriumJanuary 11, 201216 / 31

ApplicationsExample 3: Bertrand Model of DuopolySuppose that qi (p) a pi bpj and each firm’s marginal cost is c.Assume that b 2.Find a Nash equilibrium.Obara (UCLA)Nash EquilibriumJanuary 11, 201217 / 31

ApplicationsExample 4: Voluntary Contribution of Public GoodThere is a village with n residents.Each resident’s wealth is W . Assume that W is large enough.The residents decide simultaneously how much they donate theirmoney, which will be used to provide public goods in the village. Resident i’s payoff is W xi y where xi is player i’s privatePdonation and y nj 1 xj is the amount of public goods.Find a Nash equilibrium.Obara (UCLA)Nash EquilibriumJanuary 11, 201218 / 31

ApplicationsExample 5: Rent Seeking GameThere are n lobbying groups.Only one of them “wins” and gains V 0.Group i chooses its “effort level” xi at the cost of cxi 0.The probability that group i wins isGroup i’s expected payoff isPnxij 1 xjPnxij 1 xj.V cxi .Find a Nash equilibrium.Obara (UCLA)Nash EquilibriumJanuary 11, 201219 / 31

ApplicationsExample 6: AdAuctionM links on a webpage are auctioned among n M biddersThe top link gets the largest number of clicks, then the second toplink and so on.Suppose that bidders need only one link and their values per click arev1 . vn .Bidders bid how much they would pay per click. The highest bidderwins the top link and pays the second highest bid. The secondhighest bidder wins the second link and pays the third highest bid.This ad auction or Pay-per-Click auction is a generalized secondprice auction (it reduces to SPA when M 1).Obara (UCLA)Nash EquilibriumJanuary 11, 201220 / 31

ApplicationsExample 6: AdAuctionBidder i’s payoff given b (b1 , ., bn ) isui (b) MX 1(bi b (k) ) vi b (k 1) xkk 1where 1(bi b (k) ) 1 if and only if bidder i’s bid is the kth highestbid (otherwise 0) and xk is the number of clicks at the kth link(ignoring any tie).Obara (UCLA)Nash EquilibriumJanuary 11, 201221 / 31

ApplicationsExample 6: AdAuctionSuppose thatIM 2 and n 3.IThe first link generates 100 click/day. The second link generates60/day.IThe value of one click is v1 20, v2 10, and v3 5 for bidder1,2, and 3 respectively.Is it a dominant action to bid vi for bidder i?Find a Nash equilibrium.Obara (UCLA)Nash EquilibriumJanuary 11, 201222 / 31

ExistenceExistence of NEThere is sometimes no Nash equilibrium (ex. MP, completeinformation FPA with random tie-breaking).When does a Nash equilibrium exist?Obara (UCLA)Nash EquilibriumJanuary 11, 201223 / 31

ExistenceExistence of NENash Existence TheoremSuppose that Ai is a nonempty compact convex subset of k and ui iscontinuous in A and quasi-concave in Ai given any a i A i for everyi N for strategic game (N, (Ai ), (ui )). Then there exists a Nashequilibrium .Obara (UCLA)Nash EquilibriumJanuary 11, 201224 / 31

ExistenceKakutani’s Fixed Point TheoremWe use Kakutani’s fixed point theoremKakutani’s Fixed Point TheoremLet X be a nonempty compact and convex subset of k and f : X Xbe a correspondence. Suppose that f is convex-valued and upperhemicontinuous (has a closed graph). Then there exists x such thatx f (x ).Note: We always assume that a correspondence’s value (f (x) in this case) is notempty.Obara (UCLA)Nash EquilibriumJanuary 11, 201225 / 31

ExistenceProofFor any a i , Bi (a i ) is nonempty (by continuity and compactness),convex (by quasi-concavity) and upper hemicontinuous (by Maximumtheorem).The product B (B1 , ., Bn ) is a correspondence from A to A and isnonempty, convex-valued and upper hemicontinuous.By Kakutani’s fixed point theorem there is a fixed point a where ) for every i N. Clearly a is a NE.ai B i (a iObara (UCLA)Nash EquilibriumJanuary 11, 201226 / 31

Zero-Sum GameZero-Sum gameA two-player strategic game G is a zero-sum game (a strictlycompetitive game) if u1 (a) u2 (a) 0 for every a A.INote: If u1 (a) u2 (a) K for every a A for some constant K(constant-sum game), then we can subtract K from one player’s payoffwithout loss of generality to turn it into a zero-sum game.For this class of games, the set of NE has a simple structure.Obara (UCLA)Nash EquilibriumJanuary 11, 201227 / 31

Zero-Sum GameMaxminMaxminai Ai is a maxminimizer for player i ifmin ui (ai , a i ) min ui (ai , a i ) ai Ai .a i A ia i A iThat is, a maximizer is a (part of) solution formaxai mina i A i ui (ai , a i ).A maximizer maximizes the payoff in the worst case scenario. So itmay be a reasonable choice when someone makes a very conservativechoice.Obara (UCLA)Nash EquilibriumJanuary 11, 201228 / 31

Zero-Sum GameMinimax TheoremThis is a version of Minimax theorem.Minimax TheoremLet G ({1, 2} , (Ai ), (ui )) be a zero-sum game where Ai is compact andui is continuous for every i N. Then a A is a Nash equilibrium if andonly if, for i 1, 2,1ai is a maxminimizer.2ui (a ) maxai Ai mina i A i ui (a) mina i A i maxai Ai ui (a).Obara (UCLA)Nash EquilibriumJanuary 11, 201229 / 31