Best Response and Nash Equilibrium

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

1

Outline�

• Review
• Nash equilibrium
• Best response function
• Using best response function to find Nash equilibria
• Examples

2

Review�

• DEFENITION: The normal-form representation of a game G specifies:
• A finite set of players {1, 2, ..., n}
• Players’ strategy spaces S₁, S₂, ..., S_n
• Players’ payoff functions u₁, u₂, ..., u_n, where u_i: S₁×S₂×…×S_n → R�
• The timing of the game:
• Each player i chooses his/her strategy s_i without knowledge of others’ choices
• Then each player i receives his/her payoff u_i(s₁, s₂, ..., s_n)
• The game ends

​

​

3

Review�

• DEFINITION: Strictly dominated strategy
• In the normal-form game {S₁, S₂,..., S_n, u₁, u₂,..., u_n}, let s_i', s_i" ∈ S_i be feasible strategies for player i
• Strategy s_i“ strictly dominates strategy s_i' if u_i(s₁,s₂,...,s_i-1,s_i',s_i+1,...,s_n) < u_i(s₁,s₂,...,s_i-1,s_i",s_i+1,...,s_n) for all s₁∈ S₁, s₂∈ S₂, ..., s_i-1∈S_i-1, s_i+1∈ S_i+1, ..., s_n∈ S_n

​

​

​

• We say that s_i' is strictly dominated strategy

4

Review�

• Iterated elimination of dominated strategy (IEDS):
• If a strategy is strictly dominated, eliminate it
• The size and complexity of the game is reduced
• Then eliminate any strictly dominated strategies from the reduced game
• Continue doing so successively

​

5

Review�

• Iterated elimination of dominated strategy

​

6

Player 1

Player 2

Middle

Up

Down

Left

Right

Review�

• The advantage of IEDS (iterated elimination of dominated strategy) is that:
• It is based on the appealing idea that rational players do not play dominated strategies

​

• The disadvantages of IEDS is that:
• (1) Rationality: it assumes that all players are completely rational and it is common knowledge
• (2) Existence: not all games are dominance solvable

​

​

7

New solution concept: Nash equilibrium�

• The main idea behind Nash equilibrium:
• Nash equilibrium is a set of strategies, one for each player, such that each player’s strategy is best for her, given that all other players are playing their best strategies
• In other words, Nash equilibrium is a stable situation that no player would like to deviate if others stick to it

8

John F. Nash�

• John F. Nash (1994 Nobel Memorial Prize in Economics, “Beautiful Mind”)

​

​

​

​

9

Nash equilibrium�

• DEFINITION: Nash equilibrium
• In the normal-form game {S₁, S₂,..., S_n, u₁, u₂,..., u_n}, a combination of strategies (s₁*,…, s_n*) is a Nash equilibrium if for every player i

u_i(s₁*,...,s_i-1*,s_i*,s_i+1*,...,s_n*) ≥ u_i(s₁*,...,s_i-1*,s_i,s_i+1*,...,s_n*) for all s_i∈ S_i

​

​

​

• That is s_i* solves the following problem: Maximize u_i(s₁*,...,s_i-1*,s_i,s_i+1*,...,s_n*) subject to s_i∈ S_i

10

Nash Equilibrium:�3×3 game

• Strategy profile (B, R) has the following property:
• Player 1 cannot do better by choosing a strategy different from B, given that Player 2 chooses R
• Player 2 cannot do better by choosing a strategy different from R, given that Player 1 chooses B
• Therefore, (B, R) is called a Nash equilibrium

11

Best response function�

• DEFINITION: Best response
• In the normal-form game {S₁, S₂,..., S_n, u₁, u₂,..., u_n}, if players 1, 2, ..., i-1, i+1, ..., n choose strategies, s₁,s₂,...,s_i-1,s_i+1,...,s_n, respectively, then player i‘s best response function is defined by:

B_i(s₁,...,s_i-1,s_i+1,...,s_n) = {s_i∈ S_i: u_i(s₁,...,s_i-1,s_i,s_i+1,...,s_n) ≥ u_i(s₁,...,s_i-1,s_i', s_i+1,...,s_n), for all s_i'∈ S_i }

​

12

Best response function�

• DEFINITION: Best response (alternative)
• In the normal-form game {S₁, S₂,..., S_n, u₁, u₂,..., u_n}, if players 1, 2, ..., i-1, i+1, ..., n choose strategies, s₁,s₂,...,s_i-1,s_i+1,...,s_n, respectively, then player i‘s strategy s_i ∈ B_i(s₁,...,s_i-1,s_i+1,...,s_n) if and only if it solves (or it is an optimal solution to)

Maximize u_i(s₁,...,s_i-1,s_i',s_i+1,...,s_n) subject to s_i'∈ S_i

13

Nash equilibrium: Using best response function�

• DEFINITION: Nash Equilibrium
• In the normal-form game {S₁, S₂,..., S_n, u₁, u₂,..., u_n}, a combination of strategies (s₁*,…, s_n*) is a Nash equilibrium if for every player i

s_i* ∈ B_i(s₁*,...,s_i-1*,s_i+1*,...,s_n*)

​

​

​

​

• Nash equilibrium is a set of strategies, one for each player, such that each player’s strategy is best for her, given that others are playing their best strategies

14

Using best response: 3×3 game�

• Best response:
• What is Player 1’s best response if Player 2 chooses L, C, R?
• What is Player 2’s best response if Player 1 chooses T, M, B?

​

• Therefore, (B, R) is a Nash equilibrium

15

Using best response: Prisoners’ Dilemma�

• Best response:
• What is Prisoner 1’s best response if Prisoner 2 chooses NC, C?
• What is Prisoner 2’s best response if Prisoner 1 chooses NC, C?

​

• Therefore, (C, C) is a Nash equilibrium in Prisoners’ Dilemma

16

Using best response: The Battle of the Sexes�

• Best response:
• What is Rebecca’s best response if Steve chooses Mall, Game?
• What is Steve’s best response if Rebecca chooses Head, Tail?

​

• Therefore, there are two Nash equilibria in the Battle of the Saxes:
• (Mall, Mall) is a Nash equilibrium
• (Game, Game) is a Nash equilibrium

17

Using best response: Matching Pennies�

• Best response:
• What is Player 1’s best response if Player 1 chooses Head, Tail?
• What is Player 2’s best response if Player 1 chooses Head, Tail?

​

• There are no combinations of best responses that match!
• Therefore, NO Nash equilibrium

​

18

IEDS and Nash equilibrium: Prisoners’ Dilemma�

• IEDS?
• (C, C)

​

• Nash equilibrium?
• (C, C)

19

IEDS and Nash equilibrium: Matching Pennies�

• IEDS?
• None

​

• Nash equilibrium?
• None

​

20

IEDS and Nash equilibrium: The Battle of the Sexes�

• IEDS?
• None

​

• Nash equilibrium?
• (Mall, Mall)
• (Game, Game)

21

IEDS and Nash equilibrium�

• If a strategic game has an IEDS equilibrium, this outcome must also be a Nash equilibrium
• Example: Prisoners’ Dilemma

​

• However, not every Nash equilibrium can be obtained as the solution to IEDS
• Example: Battle of the Sexes

​

22

Coordination and social welfare�

• Because of conflict between individual incentives Nash equilibrium does not always entail strategies that are preferred by the players as a group
• Example: Prisoner’s Dilemma

​

• Sometimes a socially inefficient outcome prevails not because of conflict between individual incentives but because there is more than one Nash equilibrium
• Example: Coordination games with multiple equilbria

​

23

Coordination and social welfare�

• What are the Nash equilibria of this game?
• (A, A)
• (B, B)

​

• The problem is that (B, B) is Pareto inefficient (not socially optimal), but an equilibrium nonetheless
• Given that the other chooses B, each player’s only rational strategy is to select B as well

​

24

Practice problem�

• Find IEDS?

​

• Find Nash equilibrium?

25

Nash equilibrium: Games with continuous strategies�

• Set of players: {Firm 1, Firm 2}
• Sets of strategies: S₁=[0, +∞), S₂=[0, +∞)
• Payoff functions: u₁(q₁, q₂)=q₁{a-(q₁+q₂)}-q₁c,

u₂(q₁, q₂)=q₂{a-(q₁+q₂)}-q₂c

�

26

Math review�

• Next Time!

27

Thank you!

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

28

References�

• Watson, J. (2013). Strategy: An Introduction to Game Theory (3rd Edition). Publisher: W. W. Norton & Company. (Chapter 9)

​

29