MODULE 3: NASH
EQUILIBRIUM I
PROF LIONEL PAGE
1
LAST LECTURE
We have seen…
1. That a dominant action is the best action regardless of what the opponents are doing
2. The criterion of dominance is “global”: an action has to be the best regardless of
what the opponents are doing
3. That a dominated action is always worse than another particular action regardless of
what the opponents are doing
4. that we can solve some games using dominant actions or iterative elimination of
dominated strategies
…But not every game can be solved this way!
2
BEST RESPONSE: IDEA
• The criterion of dominance is “global”: an action has to be the best regardless of what the
opponents are doing
• We can take another approach: suppose I know my opponent is playing a certain action,
what would be my best action against it?
 If player 2 goes to Boxing, the best action for player 1 is Opera
 If player 2 goes to Opera, the best action for player 1 is Boxing
• This idea is known as Best Response
3
Opera Boxing
Opera 3, 1 0, 0
Boxing 0, 0 1, 3
BEST RESPONSE: DEFINITION
4
Definition
An action of player i is a Best Response against an
opponent action profile if, given this opponent action
profile, yields the highest payoff (i.e., utility) to Player i
among all Player i 's actions.
FINDING BEST RESPONSES IN A PAYOFF MATRIX
• We will proceed to mark the best-response actions of each player.
5
Yes No
Yes 1, 1 0, 0
No 0, 0 0, 0
• Note that there are multiple best responses against Player 2 choice of No
FINDING BEST RESPONSES IN A PAYOFF MATRIX
6
Yes No
Yes 1, 1 0, 0
No 0, 0 0, 0
• Note that there are multiple best responses against Player 1 choice of No
FINDING BEST RESPONSES IN A PAYOFF MATRIX
7
Yes No
Yes 1, 1 0, 0
No 0, 0 0, 0
• Notice also that there are two outcomes (or cells) in which both players are playing their
best-response to the other.
FINDING BEST RESPONSES IN THREE-PLAYER
GAMES
• Same idea. How many opponent action profiles does Player 1 have?
8
Prepare Shirk
Prepare 3, 3, 3 0, 1, 0
Shirk 1, 0, 0 1, 1, 0
Prepare
Prepare Shirk
Prepare 0, 0, 1 0, 1, 1
Shirk 1, 0, 1 1, 1, 1
Shirk
CORRESPONDENCE
• When we don't have a payoff matrix, we can use Best Response Correspondence
• A correspondence is a multi-valued function
9
= 2
Input
2
25
0
Output
4
5, -5
0
g =
BEST RESPONSE CORRESPONDENCE
• A Best Response Correspondence of Player gives, for each opponent action profile,
the set of best responses of Player ∈ {1,2}.
10
Yes No
Yes 1, 1 0, 0
No 0, 0 0, 0
BEST RESPONSE CORRESPONDENCE
• For Player 1:
1 2 = � if 2 = , if 2 =
• For Player 2:
2 1 = � if 1 = , if 1 =
11
Yes No
Yes 1, 1 0, 0
No 0, 0 0, 0
PURE STRATEGY NASH EQUILIBRIUM: IDEA
• Notice that if both players go to the opera, they are best-responding to each other
• Suppose there is a convention “everyone always go to the opera”
• Believing that the other will adhere to this convention, no player would want to do otherwise
• Idea of Nash Equilibrium: “if everyone believes this profile of actions will be played, then
everyone will indeed want to play their action in this profile”
12
Opera Boxing
Opera 3, 1 0, 0
Boxing 0, 0 1, 3
PURE STRATEGY NASH EQUILIBRIUM:
DEFINITION
13
Definition
An action profile ∗ = (1∗ ,2∗ , … ,∗ ) is a Pure Strategy Nash Equilibrium
(PSNE) of an N-player normal form game if,
for each player = 1, … ,,
∗ is a best response to − ∗ = 1∗ , … ,−1∗ , +1∗ … ,∗ ,
…where − ∗ means “the actions of all other players except for Player i.”
SOME QUICK REMARKS
1. An equilibrium is an action profile. So (Opera, Opera) is an equilibrium of the Battle of the Sexes; (3,1)
is not.
2. The definition of equilibrium does NOT say how an equilibrium is reached. It just says “if we are at an
equilibrium nobody would like to deviate" (we will discuss this later)
14
EQUILIBRIUM AND PROFITABLE DEVIATION
• If you want to show that ∗ is a PSNE, you need to demonstrate that each player is best responding to
each other
• If you want to show that ∗ is NOT a PSNE, you only need to find one player and one of his action ≠

∗ such that yields a strictly higher payoff than ∗ against −∗ .
 We call such a profitable deviation.
• A profitable deviation must yields a strictly higher payoff than ∗ against −∗ , just an equal payoff does
not qualify
15
EQUILIBRIUM?
• Prisoner’s dilemma
• PSNE?
16
Diamonds Nothing
Money 10 , 10 -5 , 20
Nothing 20 , -5 0 , 0
EQUILIBRIUM?
• Prisoner’s dilemma
• PSNE?
 One: (N,N)
17
Diamonds Nothing
Money 10 , 10 -5 , 20*
Nothing 20* , -5 0* , 0*
EQUILIBRIUM?
• Matching pennies
• PSNE?
18
Head Tail
Head 1 , -1 -1 , 1
Tail -1 , 1 1 , -1
EQUILIBRIUM?
• Matching pennies
• PSNE?
 No
19
Head Tail
Head 1* , -1 -1 , 1*
Tail -1 , 1* 1* , -1
EQUILIBRIUM?
• Battle of the sexes
• PSNE?
20
Opera Boxing
Opera 3 , 1 0 , 0
Boxing 0, 0 1 , 3
EQUILIBRIUM?
• Battle of the sexes
• PSNE?
 Two
21
Opera Boxing
Opera 3* , 1* 0 , 0
Boxing 0, 0 1* , 3*
JUSTIFICATIONS OF THE NASH EQUILIBRIUM?
• Why would people play Nash equilibrium?
 If you do not play the Nash equilibrium, the other player can beat you
 But what if the other player does not play the Nash equilibrium?
• Justification 1:
 If you were to write a book about how to play the game, you would have to advise to play Nash
equilibrium
• Justification II:
 If you were to think about it over and over, the only thing you’d stop at would be a Nash
equilibrium
• Justification III
 If a population plays this game, the only stable way of playing this game is a Nash equilibrium
22
EXAMPLE: THE DRIVING GAME
23
L R
L 1* , 1* -1 , -1
R -1, -1 1* , 1*
COORDINATION GAME
• Your friend sends you a SMS: “Let’s meet in Paris at 12pm, at…” [the connection was lost]
• Where should you meet?
24
Go to www.menti.com and enter the code:
3873 1353
25
FOCAL POINT
• Thomas Schelling
• Sometimes a solution can stand out for external reasons
• Can help find equilibrium in coordination games
26
HOW IS AN EQUILIBRIUM REACHED?
• Equilibrium is a “fixed-point" concept: if we are there, we will stay there
• It is silent on how it is reached
• This is also true for the “demand equals supply" equilibrium you have seen in introductory economics
27
NASH EQUILIBRIUM IS NOT NECESSARILY PARETO
OPTIMAL
• (N; N) is the unique Nash equilibrium
• But it is Pareto dominated by (M; D)
• A strategy profile is Pareto dominated by another strategy profile if all
players have higher utility under than
• A strategy profile is Pareto optimal if it is not Pareto dominated
28
Diamonds Nothing
Money 10 , 10 -5 , 20
Nothing 20 , -5 0 , 0
HAVING MORE CHOICE CAN MAKE YOU WORSE OFF!
• (N; N) is the unique Nash equilibrium, Player 1's payoff is 1
• However, if Player 1 cannot play N (her dominant action), Player 2 will play D,
which gives Player 1 a payoff of 10
29
Diamonds Nothing
Money 10 , 10 -5 , 0
Nothing 20 , -5 0 , 0
A PLAYER CAN PLAY A WEAKLY DOMINATED ACTION
IN A NASH EQUILIBRIUM
• (B; R) is a Nash equilibrium
• But B is weakly dominated by T, and R is weakly dominated by L
30
EXAMPLE
31
Go to www.menti.com and enter the code:
3873 1353
32
Go to www.menti.com and enter the code:
3873 1353
33
NO EQUILIBRIUM?
• Matching Pennies has no PSNE
• This is intuitive: a Nash equilibrium is known but neither player wants her
action to be known by the other
• How can a player be “unpredictable"?
34
MIXED STRATEGY: IDEA
• Suppose Player 1 can choose between T and B in a game
• Nothing prohibits her to flip a coin and choose T if the coin comes up head and B if it comes up tail
• Or she can use her smart phone to generate a random number between 0 and 1 and choose T if the
random number is smaller than 0.748329 and B otherwise
• We call these options mixed strategies
35
MIXED STRATEGY: A DEFINITION
• Formally, a mixed strategy of Player i is a probability distribution over her action set
• {1,2,…, }
• {1,2,…,}
• With ≥ 0 for each and
• ∑=1 = 1
36
MIXED STRATEGY: NOTATION
• A typical mixed strategy of Player is denoted as
• ( ) is the probability assigns to the action
• In your problem sets or exams, if you need to refer to a mixed strategy, you can write a list of
probabilities, one for each actions, in the order the actions are given in the payoff matrix.
• For example, if a player's action set is {,} then (1/3 ; 2/3 ) means the mixed strategy that puts
probability 1/3 on and 2/3 on .
37
PURE STRATEGIES ARE MIXED STRATEGIES TOO!
• Nothing prohibits a mixed strategy to put probability 1 on an action
• So a pure strategy (an action) is also a mixed strategy
• If I just say “a strategy" or “a mixed strategy", it can be either pure or mixed
• If I want to refer to a pure strategy, I will say “a pure strategy"
38
MIXED STRATEGY PROFILES
• Suppose Player 1 plays the mixed strategy 1 = (, 1 − )
• And Player 2 plays the mixed strategy 2 = (, 1 − )
• Then if I want to write the Mixed Strategy Profile, i.e., the list of mixed
strategy played by each player, I have:
• (1,2) = , 1 − , (, 1 − )
39
EXPECTED PAYOFF FROM A MIXED STRATEGY PROFILE
• What is Player 1's expected payoff from this mixed strategy profile?
• 1 1,2 = Pr + Pr + Pr + Pr[]
• 1 1,2 = + (1 − ) + 1 − + (1 − )(1 − )
40
PAYOFF FROM A MIXED STRATEGY PROFILE, GENERAL
CASE
• 1,2, … , proba: 1 1 × 2 2 × ⋯× ()
• 1 = ∑∈ 1 1,2, … , ∏=1
41
Utility of Probability of
MIXED STRATEGY NASH EQUILIBRIUM
42
Definition
A mixed strategy profile = 1∗, 2∗, … , ∗ is a (mixed strategy) Nash
equilibrium if for each player ,
(∗, −∗ ) ≥ ( , −∗ )
for every mixed strategy
NASH THEOREM: INTUITION
• Action profile (1, 2,…, )
• Best response correspondence:
• (1, 2,…, )
• Nash equilibrium is a fixed point:
• (1∗, 2∗,…,∗ ) = (1∗, 2∗,…,∗ )
43