STANFORD UNIVERSITY Winter 2001DEPT. OF MANAGEMENT SCIENCE MS&E 241AND ENGINEERING ECONOMIC ANALYSISPRINCIPLES OF GAME THEORYLECTURE 2 NASH EQUILIBRIUMOne of the purposes of game theory is to predict the strategic behavior of people or economicinstitutions. Iterated elimination of dominated strategies serves to narrow down the number of"reasonable" strategies available to an individual. It may even narrow them down to one uniqueequilibrium stategy. In general, however, iterated elimination does not always lead to a stableequilibrium. We say a solution is strategically stable or self-enforcing if each player's strategy is thatplayer's best response to the strategies of the other players. This will ensure that no player wouldwant to deviate from his or her predicted strategy. We call such a set of strategically stablestrategies a Nash Equilibrium. It is a stronger solution concept in game theory than iteratedelimination of dominated strategies. Nash equilibria survive iterated elimination of dominatedstrategies, and in addition, provides a solution that is stable in the sense described above. As weshall see, if iterated elimination of dominated strategies yields a unique solution, then thatsolution is also a Nash Equilibrium.The payoff diagram on the next page shows the remainder of a game where all strictlydominating strategies have been eliminated. Obviously, not all remaining strategy combinationsare stable equilibria (verify), with the exception of the combination (B, R).LCRTMB0, 44, 05, 34, 00, 45, 33, 53, 56, 6Only the combination (B, R) is stable. If Player 1 plays B, then Player 2's best response is to playR. Conversely, playing B is Player 1's best response to Player 2's strategy R. [Verify that no otherstrategy pair in the payoff matrix is stable.] Hence, (B, R) is a Nash Equilibrium.Definition In the two-player strategic-form game G = {S1, S2; U1, U2}, the strategies (s*1,s*2) are a Nash Equilibrium if s*1 is (at least tied for) Player 1's best response to Player 2'sstrategy, s*2. s*2 is, likewise, Player 2's best response to s*1:U1(s*1, s*2) ≥ U1(s1, s*2) for every feasible strategy s1 in S1. U2(s*1, s*2) ≥ U2(s*1, s2) for every feasible strategy s2 in S2. In other words, s*1 solves \A(Max,s1∈S1) U1(s1, s*2), and analogously for s*2.[1] Proposition In the two-player strategic-form game G = {S1, S2; U1, U2}, if iteratedelimination of strictly dominated strategies eliminates all but the strategies (s*1, s*2), then these strategies are the unique Nash equilibrium of the game.Proof See, e.g., D. Fudenberg and J. Tirole, "Game Theory," Section 1.2.[2] Proposition In the two-player strategic-form game G = {S1, S2; U1, U2}, if thestrategies (s*1, s*2) are a Nash equilibrium, then they survive iterated elimination of strictlydominated strategies.Proof Fudenberg and Tirole, Section 1.2.Examples: Nash Equilibrium and Iterated Elimination of Dominated StrategiesBrute force approach to finding NE: Check whether each possible combination of strategiessatisfies the definition of NE. In a two-player game: For each player and for each feasiblestrategy for that player, determine the other player's best response to that strategy. A pair ofstrategies is a NE if each player's strategy is a best response to the other's.Example 1: Prisoner's Dilemma: Verify that (D, D) is the unique NE. Example 2: Consider the following strategic-form game:Player 2LeftMiddleRightPlayer 1UpDown1, 01, 20, 10, 30, 12, 0(Up, Middle) is the only strategy pair that survives iterated elimination of dominated strategies,hence it is the unique NE, by Proposition [1].Example 3: Multiple NE: Recall the Opera/Movie example:OperaMovieOperaMoviePlayer 2Player 12, 10, 00, 01, 2Verify that this game has two Nash Equilibria, namely (Opera, Opera) and (Movie, Movie).Application: Cournot Model of DuopolyThe Cournot duopoly model is one of the classics of game theory. This example uses the Cournotmodel to illustrate (a) translation of an informal, verbal statement of a problem into a strategic-form representation of a game; (b) the computations involved in solving for the game's Nashequilibrium; and (c) iterated elimination of strictly dominated strategies.Let q1 and q2 denote the quantities of a homogeneous product produced by firms 1 and 2,respectively. Let P(Q) = a - Q be the (inverse) market demand function, where Q = q1 + q2. P(Q) = 0 for Q ≥ a. There is no fixed cost and marginal cost is constant and equal toc < a. Following Cournot, we assume the firms choose their quantities simultaneously.The problem can be formulated as a strategic-form game: (1) Players are the two firms;(2) Strategies available are production quantities, so that each firm's strategy space is Si = [0, ∞),and a typical strategy choice is a production quantity, qi = si ∈ Si, i = 1, 2. [Verify that becauseP(Q) = 0 for Q > a, neither firm will produce a quantity qi ≥ a]; and (3) Each firm's payoff function is simply its profit: πi(q1, q2) = qi[P(q1 + q2) - c] = qi[a - (q1 + q2) - c].Recall the definition of NE: The strategy pair (s1*, s2*) is a NE if, for each player, i:Ui(s*i, s*j) ≥ Ui(si, s*j) ∀ si ∈ Si .Equivalently, each player solves \A(Max,si∈Si) Ui(si, s*j).In the Cournot duopoly model, the analogous formulation of NE is that the quantity pair (q*1,q*2) is a Nash equilibrium if for each firm i, q*i solves: \A(Max,0 ≤ qi < ∞) Ui(qi, q*j) = \A(Max,0 ≤ qi < ∞) qi[a - (qi+ q*j) - c]Solving FOC yields: qi = 0.5[a - q*j - c]Thus, if the quantity pair (q*1, q*2) is to be a Nash equilibrium, the firms' quantity choices mustsatisfy:q*1 = 0.5[a - q*2 - c].andq*2 = 0.5[a - q*1 - c].Solving:q*1 = q*2 =(a - c)/3.Graphically, with Best-Response Functions:Denote by Ri( qj) firm i's best response to firm j's output decision, qj.Then, by the FOC, R2( q1) = 0.5[a - q1 - c] and R1( q2) = 0.5[a - q2 - c].(q*1, q*2) is a Nash Equilibrium if q*1 = R1(q*2) and q*2 = R2(q*1).This NE is illustrated in the diagram on the next page.q2a - c(a-c)/2q2*q1*R1(q2)R2(q1)(a-c)/2a - cq1Bertrand duopoly: Work through the example in Varian, p. 291.Example The Commons ProblemSuppose there are I farmers, each of whom has the right to graze cows on the village common.The amount of milk a cow produces, denoted v(N), depends on the total number of cows, N,grazing on the green. A farmer who decides to raise ni cows will, for instance, receive a revenueof