Normal form games and Nash equilibrium
Week 1, ECON2112
Arghya Ghosh
1
Table of contents
1. Introduction
2. Normal Form Games
3. Nash Equilibrium
4. Mixed Strategies
2
Introduction
Game Theory (Informally)
ˆ Game theory studies strategic, multi-person decision problems.
ˆ A strategic situation (game) is a situation in which two or more individuals
(players) interact and each player’s action have (some) effect on outcome
ˆ How to find a solution in such situations? - Game theory provides a path.
ˆ A solution is a set of recommendations about how to play the game
ˆ For a solution concept to be appealing, no player would have an incentive to
deviate from these recommendation.
3
Game Theory (Informally)
ˆ Game theory studies strategic, multi-person decision problems.
ˆ A strategic situation (game) is a situation in which two or more individuals
(players) interact and each player’s action have (some) effect on outcome
ˆ How to find a solution in such situations? - Game theory provides a path.
ˆ A solution is a set of recommendations about how to play the game
ˆ For a solution concept to be appealing, no player would have an incentive to
deviate from these recommendation.
3
Game Theory (Informally)
ˆ Game theory studies strategic, multi-person decision problems.
ˆ A strategic situation (game) is a situation in which two or more individuals
(players) interact and each player’s action have (some) effect on outcome
ˆ How to find a solution in such situations? - Game theory provides a path.
ˆ A solution is a set of recommendations about how to play the game
ˆ For a solution concept to be appealing, no player would have an incentive to
deviate from these recommendation.
3
Game Theory (Informally)
ˆ Game theory studies strategic, multi-person decision problems.
ˆ A strategic situation (game) is a situation in which two or more individuals
(players) interact and each player’s action have (some) effect on outcome
ˆ How to find a solution in such situations? - Game theory provides a path.
ˆ A solution is a set of recommendations about how to play the game
ˆ For a solution concept to be appealing, no player would have an incentive to
deviate from these recommendation.
3
Game Theory (Informally)
ˆ Game theory studies strategic, multi-person decision problems.
ˆ A strategic situation (game) is a situation in which two or more individuals
(players) interact and each player’s action have (some) effect on outcome
ˆ How to find a solution in such situations? - Game theory provides a path.
ˆ A solution is a set of recommendations about how to play the game
ˆ For a solution concept to be appealing, no player would have an incentive to
deviate from these recommendation.
3
Game Theory (Informally)
ˆ Game theory studies strategic, multi-person decision problems.
ˆ A strategic situation (game) is a situation in which two or more individuals
(players) interact and each player’s action have (some) effect on outcome
ˆ How to find a solution in such situations? - Game theory provides a path.
ˆ A solution is a set of recommendations about how to play the game
ˆ For a solution concept to be appealing, no player would have an incentive to
deviate from these recommendation.
3
Example: The Prisoners’ dilemma
Description of the game taken from Wikipedia:
“Two members of a criminal gang are arrested and imprisoned. Each prisoner
is in solitary confinement with no means of speaking to or exchanging messages
with the other. The police admit they don’t have enough evidence to convict
the pair on the principal charge. They plan to sentence both to a year in prison
on a lesser charge. Simultaneously, the police offer each prisoner a Faustian
bargain. If he testifies against his partner, he will go free while the partner will
get nine years in prison on the main charge. Oh, yes, there is a catch ... If
both prisoners testify against each other, both will be sentenced to six years
in jail.”
4
Example: The Prisoners’ dilemma
Prisoner 1
Prisoner 2
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
ˆ The Prisoners’ dilemma is a multi-person decision problem: the outcome is jointly
determined by Prisoner 1 and Prisoner 2.
ˆ What should be the solution to this game?
5
Example: The Prisoners’ dilemma
Prisoner 1
Prisoner 2
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
ˆ The Prisoners’ dilemma is a multi-person decision problem: the outcome is jointly
determined by Prisoner 1 and Prisoner 2.
ˆ What should be the solution to this game?
5
Normal Form Games
Normal form games: General case
What do we need to have a multi-person decision problem or strategic situation?
(What constitutes a game?)
ˆ We need players, say n players.
ˆ Each player has to take a decision or strategy, therefore, for each player we need a
strategy set.
ˆ For each player and each strategy profile (a strategy for each player) we need to
specify payoff
6
Normal form games: General case
What do we need to have a multi-person decision problem or strategic situation?
(What constitutes a game?)
ˆ We need players, say n players.
ˆ Each player has to take a decision or strategy, therefore, for each player we need a
strategy set.
ˆ For each player and each strategy profile (a strategy for each player) we need to
specify payoff
6
Normal form games: General case
What do we need to have a multi-person decision problem or strategic situation?
(What constitutes a game?)
ˆ We need players, say n players.
ˆ Each player has to take a decision or strategy, therefore, for each player we need a
strategy set.
ˆ For each player and each strategy profile (a strategy for each player) we need to
specify payoff
6
Normal form games: Formal definition
Definition 1 (Normal Form game)
An n-player normal form game G = (S1, . . . ,Sn; u1, . . . , un) consists of
ˆ for each player i = 1, . . . , n, a set of strategies Si ; and
ˆ for each player i = 1, . . . , n a utility function ui that, for each strategy profile
(s1, . . . , sn) ∈ S1 × · · · × Sn specifies a real number ui (s1, . . . , sn) ∈ R.
7
Example: Prisoners’ Dilemma
ˆ There are two players, therefore, n = 2.
ˆ A strategy set for each player
ˆ S1 = {Not Confess,Confess}
ˆ S2 = {Not Confess,Confess}
ˆ a utility function for each player
8
Example: Prisoners’ Dilemma
ˆ There are two players, therefore, n = 2.
ˆ A strategy set for each player
ˆ S1 = {Not Confess,Confess}
ˆ S2 = {Not Confess,Confess}
ˆ a utility function for each player
8
Example: Prisoners’ Dilemma
ˆ There are two players, therefore, n = 2.
ˆ A strategy set for each player
ˆ S1 = {Not Confess,Confess}
ˆ S2 = {Not Confess,Confess}
ˆ a utility function for each player
u1(Not Confess,Not Confess) = −1 u2(Not Confess,Not Confess) = −1
u1(Not Confess,Confess) = −9 u2(Not Confess,Confess) = 0
u1(Confess,Not Confess) = 0 u2(Confess,Not Confess) = −9
u1(Confess,Confess) = −6 u2(Confess,Confess) = −6 8
Example: The Prisoners’ dilemma
Of course, all this information can be summarised using the following normal form
(sometimes called matrix form) representation.
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
9
Example: Battle of the sexes
Description of the game taken from Wikipedia:
“Imagine a couple that agreed to meet this evening, but cannot recall if they
will be attending the opera or a football match (and the fact that they forgot is
common knowledge). The husband would most of all like to go to the football
game. The wife would like to go to the opera. Both would prefer to go to
the same place rather than different ones. If they cannot communicate, where
should they go?”
ˆ There are two players, therefore n = 2. Let player 1 be the wife and player 2 be
the husband.
ˆ A strategy set for each player. S1 = {O,F} and S2 = {O,F}
10
Example: Battle of the sexes
Description of the game taken from Wikipedia:
“Imagine a couple that agreed to meet this evening, but cannot recall if they
will be attending the opera or a football match (and the fact that they forgot is
common knowledge). The husband would most of all like to go to the football
game. The wife would like to go to the opera. Both would prefer to go to
the same place rather than different ones. If they cannot communicate, where
should they go?”
ˆ There are two players, therefore n = 2. Let player 1 be the wife and player 2 be
the husband.
ˆ A strategy set for each player. S1 = {O,F} and S2 = {O,F}
10
Example: Battle of the sexes
Description of the game taken from Wikipedia:
“Imagine a couple that agreed to meet this evening, but cannot recall if they
will be attending the opera or a football match (and the fact that they forgot is
common knowledge). The husband would most of all like to go to the football
game. The wife would like to go to the opera. Both would prefer to go to
the same place rather than different ones. If they cannot communicate, where
should they go?”
ˆ There are two players, therefore n = 2. Let player 1 be the wife and player 2 be
the husband.
ˆ A strategy set for each player. S1 = {O,F} and S2 = {O,F}
10
Example: Battle of the sexes
ˆ a utility function for each player
u1(O,O) = 2 u2(O,O) = 1
u1(O,F ) = 0 u2(O,F ) = 0
u1(F ,O) = 0 u2(F ,O) = 0
u1(F ,F ) = 1 u2(F ,F ) = 2
ˆ Again we can represent this in the matrix form
O F
O 2, 1 0, 0
F 0, 0 1, 2
11
Example: Battle of the sexes
ˆ a utility function for each player
u1(O,O) = 2 u2(O,O) = 1
u1(O,F ) = 0 u2(O,F ) = 0
u1(F ,O) = 0 u2(F ,O) = 0
u1(F ,F ) = 1 u2(F ,F ) = 2
ˆ Again we can represent this in the matrix form
O F
O 2, 1 0, 0
F 0, 0 1, 2
11
Game Theory: Assumptions
ˆ Players have common knowledge about the structure of the game.
ˆ Players choose their strategies independently.
ˆ If players can communicate at no cost, then the messages they send are part of
their strategies and the game specifies what messages can be sent (not in this
course). Second part of the course deals with “costly” signaling/communication.
12
Nash Equilibrium
Nash equilibrium
ˆ The aim of Game Theory is to provide at least one solution for every game.
ˆ A solution is understood as a set of recommendations, one for each player.
ˆ The solution has to be stable: no player has any reason to stray from the
recommendation (that is, they can’t achieve a strictly higher payoff by straying).
Definition 2 (Nash equilibrium)
A Nash equilibrium is a strategy profile such that no player has an incentive to
unilaterally deviate from his strategy.
13
Nash equilibrium
ˆ The aim of Game Theory is to provide at least one solution for every game.
ˆ A solution is understood as a set of recommendations, one for each player.
ˆ The solution has to be stable: no player has any reason to stray from the
recommendation (that is, they can’t achieve a strictly higher payoff by straying).
Definition 2 (Nash equilibrium)
A Nash equilibrium is a strategy profile such that no player has an incentive to
unilaterally deviate from his strategy.
13
Nash equilibrium. Formal definition
Notation: Denote as S the set of strategy profiles S1 × · · · × Sn.
Consider an n-player normal form game G = (S1, . . . ,Sn; u1, . . . , un),
Definition 3 (Nash equilibrium (formal))
The strategy profile s∗ = (s∗1 , . . . , s
∗
n) ∈ S is a (pure strategy) Nash equilibrium of G
if for each i = 1, . . . , n
ui (s
∗
1 , . . . , s
∗
i−1, s
∗
i , s
∗
i+1, . . . , s
∗
n) ≥ ui (s∗1 , . . . , s∗i−1, si , s∗i+1, . . . , s∗n)
for every si ∈ Si .
14
Nash equilibrium. A characterisation
Consider an n-player normal form game G = (S1, . . . ,Sn; u1, . . . , un) and a strategy
profile (s1, . . . , sn).
Definition 4 (Best response)
The set of player i ’s best responses against (s1, . . . , sn) is the set of player i ’s
strategies that solve:
max
s′i ∈Si
ui (s1, . . . , si−1, s ′i , si+1, . . . , sn).
Furthermore, we denote as Ri (s1, . . . , si−1, si+1, . . . , sn) the set of player i ’s best
responses against (s1, . . . , si−1, si+1, . . . , sn).
15
Nash equilibrium. A characterisation
Theorem 1 (NE iff BR)
The strategy profile (s∗1 , . . . , s
∗
n) is a Nash equilibrium if and only if for every
i = 1, . . . , n we have s∗i ∈ Ri (s∗1 , . . . , s∗i−1, s∗i+1, . . . , s∗n).
16
Nash equilibrium
Consider an n-player normal form game G = (S1, . . . ,Sn; u1, . . . , un).
If the strategy profile (s1, . . . , sn) is not a Nash equilibrium then there is a player i and
a strategy s ′i ∈ Si such that:
ui (s1, . . . , si−1, si , si+1, . . . , sn) < ui (s1, . . . , si−1, s ′i , si+1, . . . , sn).
That is, if (s1, . . . , sn) is not a Nash equilibrium at least one player has an incentive to
deviate from (s1, . . . , sn).
17
Nash Equilibrium: Examples
Example: Prisoners’ dilemma.
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
R1(Not Confess) =
{Confess}
R1(Confess) =
{Confess}
R2(Not Confess) =
{Confess}
R2(Confess) =
{Confess}
ˆ Therefore, NE = {(Confess,Confess)}.
18
Nash Equilibrium: Examples
Example: Prisoners’ dilemma.
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
R1(Not Confess) = {Confess}
R1(Confess) =
{Confess}
R2(Not Confess) =
{Confess}
R2(Confess) =
{Confess}
ˆ Therefore, NE = {(Confess,Confess)}.
18
Nash Equilibrium: Examples
Example: Prisoners’ dilemma.
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
R1(Not Confess) = {Confess}
R1(Confess) = {Confess}
R2(Not Confess) =
{Confess}
R2(Confess) =
{Confess}
ˆ Therefore, NE = {(Confess,Confess)}.
18
Nash Equilibrium: Examples
Example: Prisoners’ dilemma.
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
R1(Not Confess) = {Confess}
R1(Confess) = {Confess}
R2(Not Confess) = {Confess}
R2(Confess) =
{Confess}
ˆ Therefore, NE = {(Confess,Confess)}.
18
Nash Equilibrium: Examples
Example: Prisoners’ dilemma.
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
R1(Not Confess) = {Confess}
R1(Confess) = {Confess}
R2(Not Confess) = {Confess}
R2(Confess) = {Confess}
ˆ Therefore, NE = {(Confess,Confess)}.
18
Nash Equilibrium: Examples
Example: Prisoners’ dilemma.
Not Confess Confess
Not Confess −1,−1 −9, 0
Confess 0,−9 −6,−6
R1(Not Confess) = {Confess}
R1(Confess) = {Confess}
R2(Not Confess) = {Confess}
R2(Confess) = {Confess}
ˆ Therefore, NE = {(Confess,Confess)}.
18
Nash Equilibrium: Examples
Example: Battle of the sexes
O F
O 2, 1 0, 0
F 0, 0 1, 2
R1(O) =
{O}
R1(F ) =
{F}
R2(O) =
{O}
R2(F ) =
{F}
ˆ NE = {(O,O), (F ,F )}
ˆ Note: There’s actually another NE here, but it involves something called mixed
strategies (next week’s topic).
19
Nash Equilibrium: Examples
Example: Battle of the sexes
O F
O 2, 1 0, 0
F 0, 0 1, 2
R1(O) = {O}
R1(F ) =
{F}
R2(O) =
{O}
R2(F ) =
{F}
ˆ NE = {(O,O), (F ,F )}
ˆ Note: There’s actually another NE here, but it involves something called mixed
strategies (next week’s topic).
19
Nash Equilibrium: Examples
Example: Battle of the sexes
O F
O 2, 1 0, 0
F 0, 0 1, 2
R1(O) = {O}
R1(F ) = {F}
R2(O) =
{O}
R2(F ) =
{F}
ˆ NE = {(O,O), (F ,F )}
ˆ Note: There’s actually another NE here, but it involves something called mixed
strategies (next week’s topic).
19
Nash Equilibrium: Examples
Example: Battle of the sexes
O F
O 2, 1 0, 0
F 0, 0 1, 2
R1(O) = {O}
R1(F ) = {F}
R2(O) = {O}
R2(F ) =
{F}
ˆ NE = {(O,O), (F ,F )}
ˆ Note: There’s actually another NE here, but it involves something called mixed
strategies (next week’s topic).
19
Nash Equilibrium: Examples
Example: Battle of the sexes
O F
O 2, 1 0, 0
F 0, 0 1, 2
R1(O) = {O}
R1(F ) = {F}
R2(O) = {O}
R2(F ) = {F}
ˆ NE = {(O,O), (F ,F )}
ˆ Note: There’s actually another NE here, but it involves something called mixed
strategies (next week’s topic).
19
Nash Equilibrium: Examples
Example: Battle of the sexes
O F
O 2, 1 0, 0
F 0, 0 1, 2
R1(O) = {O}
R1(F ) = {F}
R2(O) = {O}
R2(F ) = {F}
ˆ NE = {(O,O), (F ,F )}
ˆ Note: There’s actually another NE here, but it involves something called mixed
strategies (next week’s topic).
19
Nash Equilibrium: Examples
Example: Battle of the sexes
O F
O 2, 1 0, 0
F 0, 0 1, 2
R1(O) = {O}
R1(F ) = {F}
R2(O) = {O}
R2(F ) = {F}
ˆ NE = {(O,O), (F ,F )}
ˆ Note: There’s actually another NE here, but it involves something called mixed
strategies (next week’s topic).
19
Nash Equilibrium: Examples
Example: Another 2x2 game
L R
T 1, 1 0, 0
B 0, 0 0, 0
R1(L) = {T}
R1(R) =
{T ,B}
R2(T ) = {L}
R2(B) =
{L,R}
ˆ NE = {(T , L), (B,R)}
20
Nash Equilibrium: Examples
Example: Another 2x2 game
L R
T 1, 1 0, 0
B 0, 0 0, 0
R1(L) = {T}
R1(R) = {T ,B}
R2(T ) = {L}
R2(B) =
{L,R}
ˆ NE = {(T , L), (B,R)}
20
Nash Equilibrium: Examples
Example: Another 2x2 game
L R
T 1, 1 0, 0
B 0, 0 0, 0
R1(L) = {T}
R1(R) = {T ,B}
R2(T ) = {L}
R2(B) = {L,R}
ˆ NE = {(T , L), (B,R)}
20
Nash Equilibrium: Examples
Example: Another 2x2 game
L R
T 1, 1 0, 0
B 0, 0 0, 0
R1(L) = {T}
R1(R) = {T ,B}
R2(T ) = {L}
R2(B) = {L,R}
ˆ NE = {(T , L), (B,R)}
20
Nash Equilibrium: Examples
Example: A 4x3 game
L C R
TT 0, 3 8, 8 8, 9
T 1, 8 7, 9 6, 4
M 2, 2 6, 1 9, 1
B 1, 8 7, 9 9, 7
R1(L) = {M}
R1(C ) = {TT}
R1(R) = {M,B}
R2(TT ) = {R}
R2(T ) = {C}
R2(M) = {L}
R2(B) = {C}
ˆ NE = {(M, L)}.
21
Nash Equilibrium: Examples
Example: A 4x3 game
L C R
TT 0, 3 8, 8 8, 9
T 1, 8 7, 9 6, 4
M 2, 2 6, 1 9, 1
B 1, 8 7, 9 9, 7
R1(L) = {M}
R1(C ) = {TT}
R1(R) = {M,B}
R2(TT ) = {R}
R2(T ) = {C}
R2(M) = {L}
R2(B) = {C}
ˆ NE = {(M, L)}.
21
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) =
{T}
R1(L,E ) =
{B}
R1(R,W ) =
{B}
R1(R,E ) =
{T ,B}
R2(T ,W ) =
{L}
R2(T ,E ) =
{L}
R2(B,W ) =
{R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) =
{B}
R1(R,W ) =
{B}
R1(R,E ) =
{T ,B}
R2(T ,W ) =
{L}
R2(T ,E ) =
{L}
R2(B,W ) =
{R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) =
{B}
R1(R,E ) =
{T ,B}
R2(T ,W ) =
{L}
R2(T ,E ) =
{L}
R2(B,W ) =
{R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) =
{T ,B}
R2(T ,W ) =
{L}
R2(T ,E ) =
{L}
R2(B,W ) =
{R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) =
{L}
R2(T ,E ) =
{L}
R2(B,W ) =
{R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) =
{L}
R2(B,W ) =
{R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) =
{R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) = {R}
R2(B,E ) =
{R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) = {R}
R2(B,E ) = {R}
R3(T , L) =
{E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) = {R}
R2(B,E ) = {R}
R3(T , L) = {E}
R3(T ,R) =
{W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) = {R}
R2(B,E ) = {R}
R3(T , L) = {E}
R3(T ,R) = {W ,E}
R3(B, L) =
{W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) = {R}
R2(B,E ) = {R}
R3(T , L) = {E}
R3(T ,R) = {W ,E}
R3(B, L) = {W ,E}
R3(B,R) =
{W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) = {R}
R2(B,E ) = {R}
R3(T , L) = {E}
R3(T ,R) = {W ,E}
R3(B, L) = {W ,E}
R3(B,R) = {W }
ˆ NE = {(B,R,W )}
22
Nash Equilibrium: Examples
Example: A 3-player game (2x2x2)
L R
T 1, 1, 1 0, 0, 0
B 0, 0, 0 1, 1, 1
W
L R
T 1, 1, 3 0, 0, 0
B 2, 0, 0 0, 1, 0
E
R1(L,W ) = {T}
R1(L,E ) = {B}
R1(R,W ) = {B}
R1(R,E ) = {T ,B}
R2(T ,W ) = {L}
R2(T ,E ) = {L}
R2(B,W ) = {R}
R2(B,E ) = {R}
R3(T , L) = {E}
R3(T ,R) = {W ,E}
R3(B, L) = {W ,E}
R3(B,R) = {W }
ˆ NE = {(B,R,W )} 22
Matching Pennies
Example: Matching Pennies
A game is played between two players, player 1 and player 2. Each player has
a penny and must secretly turn the penny to heads or tails. The players then
reveal their choices simultaneously. If the pennies match (both heads or both
tails) player 1 keeps both pennies, so wins one from player 2 (+1 for player 1,
-1 for player 2). If the pennies do not match (one heads and one tails) player 2
keeps both pennies, so receives one from Player 1 (-1 for player 1, +1 for
player 2).
23
Matching Pennies
Example: Matching Pennies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
R1(H) = {H}
R1(T ) = {T}
R2(H) = {T}
R2(T ) = {H}
ˆ NE = ?
24
Matching Pennies
Example: Matching Pennies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
R1(H) = {H}
R1(T ) = {T}
R2(H) = {T}
R2(T ) = {H}
ˆ NE = ?
24
Mixed Strategies
Mixed Strategies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
ˆ Suppose players were allowed to randomise between H and T .
ˆ That is, suppose that player 1 is allowed to play H with probability 0 ≤ x ≤ 1 and
T with probability 1− x .
ˆ In turn, suppose that player 2 is allowed to play H with probability 0 ≤ y ≤ 1 and
T with probability 1− y .
ˆ These will be called mixed strategies.
25
Mixed Strategies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
ˆ Suppose players were allowed to randomise between H and T .
ˆ That is, suppose that player 1 is allowed to play H with probability 0 ≤ x ≤ 1 and
T with probability 1− x .
ˆ In turn, suppose that player 2 is allowed to play H with probability 0 ≤ y ≤ 1 and
T with probability 1− y .
ˆ These will be called mixed strategies.
25
Mixed Strategies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
ˆ Suppose players were allowed to randomise between H and T .
ˆ That is, suppose that player 1 is allowed to play H with probability 0 ≤ x ≤ 1 and
T with probability 1− x .
ˆ In turn, suppose that player 2 is allowed to play H with probability 0 ≤ y ≤ 1 and
T with probability 1− y .
ˆ These will be called mixed strategies.
25
Mixed Strategies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
ˆ Suppose players were allowed to randomise between H and T .
ˆ That is, suppose that player 1 is allowed to play H with probability 0 ≤ x ≤ 1 and
T with probability 1− x .
ˆ In turn, suppose that player 2 is allowed to play H with probability 0 ≤ y ≤ 1 and
T with probability 1− y .
ˆ These will be called mixed strategies.
25
Mixed Strategies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
ˆ Really, we are extending the strategy sets from S1 = {H,T}, to
S1 = {xH + (1− x)T | x ∈ [0, 1]}
and from S2 = {H,T}, to
S2 = {yH + (1− y)T | y ∈ [0, 1]}
.
ˆ Also note that x and y are just arbitrary variable names, that is, S1 = S2.
ˆ Are there values 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1 that constitute a Nash equilibrium?
26
Mixed Strategies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
ˆ Really, we are extending the strategy sets from S1 = {H,T}, to
S1 = {xH + (1− x)T | x ∈ [0, 1]}
and from S2 = {H,T}, to
S2 = {yH + (1− y)T | y ∈ [0, 1]}
.
ˆ Also note that x and y are just arbitrary variable names, that is, S1 = S2.
ˆ Are there values 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1 that constitute a Nash equilibrium?
26
Mixed Strategies
H T
H 1,−1 −1, 1
T −1, 1 1,−1
ˆ Really, we are extending the strategy sets from S1 = {H,T}, to
S1 = {xH + (1− x)T | x ∈ [0, 1]}
and from S2 = {H,T}, to
S2 = {yH + (1− y)T | y ∈ [0, 1]}
.
ˆ Also note that x and y are just arbitrary variable names, that is, S1 = S2.
ˆ Are there values 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1 that constitute a Nash equilibrium?
26
Matching Pennies: Mixed Strategies
Suppose that player 2 plays H with probability 0 ≤ y ≤ 1 and T with probability 1− y .
Example: Expected payoffs for player 1
y
H
1− y
T
H 1,−1 −1, 1
T −1, 1 1,−1
U1(H, y) =y − (1− y)
U1(T , y) =− y + (1− y).
27
Matching Pennies: Mixed Strategies
We now want to compute R1(y): player 1’s best response to player 2 playing H with
probability y and T with probability (1-y).
Example: Comparing expected payoffs for player 1
U1(H, y) =y − (1− y)
U1(T , y) =− y + (1− y).
That is, player 1 prefers H to T if and only if
y − (1− y) >− y + (1− y),
y >
1
2
28
Matching Pennies: Mixed Strategies
ˆ Player 1 prefers H to T if and only if y > 12
ˆ If x represents the probability that player 1 plays H, we have that:
Example: Best response function for player 1
R1(y)

x = 1 if y > 12
0 ≤ x ≤ 1 if y = 12
x = 0 if y < 12 .
29
Mixed Strategies
Example: Plotting player 1’s best response function
1 x
1
y
R1(y)
1
2
1
2
T H
T
H
30
Mixed Strategies
We can also calculate R2:
Example: Expected payoffs for player 2
H T
x H 1,−1 −1, 1
(1− x) T −1, 1 1,−1
U2(H, x) =− x + (1− x)
U2(T , x) =x − (1− x).
We find that player 2 strictly prefers H to T if x < 12 31
Mixed Strategies
ˆ Player 2 strictly prefers H to T if x < 12
ˆ Remember: y represents the probability that player 2 plays H
Example: Best response function for player 2
R2(x)

y = 1 if x < 12
0 ≤ y ≤ 1 if x = 12
y = 0 if x > 12
32
Mixed Strategies
Example: Plotting player 2’s best response function
1 x
1
y
R1(y)
R2(x)
1
2
1
2
T H
T
H
33
Mixed Strategies
Recall Theorem 1,
Theorem 1 (NE iff BR)
The strategy profile (s∗1 , . . . , s
∗
n) is a Nash equilibrium if and only if for every
i = 1, . . . , n we have s∗i ∈ Ri (s∗1 , . . . , s∗i−1, s∗i+1, . . . , s∗n).
Example: Mixed strategy Nash equilibrium
ˆ The Nash equilibrium is the point where R1(y) and R2(x) intersect.
ˆ It corresponds to x = 12 and y =
1
2
ˆ Given y = 12 , player 1 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
ˆ Given x = 12 , player 2 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
34
Mixed Strategies
Recall Theorem 1,
Theorem 1 (NE iff BR)
The strategy profile (s∗1 , . . . , s
∗
n) is a Nash equilibrium if and only if for every
i = 1, . . . , n we have s∗i ∈ Ri (s∗1 , . . . , s∗i−1, s∗i+1, . . . , s∗n).
Example: Mixed strategy Nash equilibrium
ˆ The Nash equilibrium is the point where R1(y) and R2(x) intersect.
ˆ It corresponds to x = 12 and y =
1
2
ˆ Given y = 12 , player 1 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
ˆ Given x = 12 , player 2 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
34
Mixed Strategies
Recall Theorem 1,
Theorem 1 (NE iff BR)
The strategy profile (s∗1 , . . . , s
∗
n) is a Nash equilibrium if and only if for every
i = 1, . . . , n we have s∗i ∈ Ri (s∗1 , . . . , s∗i−1, s∗i+1, . . . , s∗n).
Example: Mixed strategy Nash equilibrium
ˆ The Nash equilibrium is the point where R1(y) and R2(x) intersect.
ˆ It corresponds to x = 12 and y =
1
2
ˆ Given y = 12 , player 1 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
ˆ Given x = 12 , player 2 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
34
Mixed Strategies
Recall Theorem 1,
Theorem 1 (NE iff BR)
The strategy profile (s∗1 , . . . , s
∗
n) is a Nash equilibrium if and only if for every
i = 1, . . . , n we have s∗i ∈ Ri (s∗1 , . . . , s∗i−1, s∗i+1, . . . , s∗n).
Example: Mixed strategy Nash equilibrium
ˆ The Nash equilibrium is the point where R1(y) and R2(x) intersect.
ˆ It corresponds to x = 12 and y =
1
2
ˆ Given y = 12 , player 1 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
ˆ Given x = 12 , player 2 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
34
Mixed Strategies
Recall Theorem 1,
Theorem 1 (NE iff BR)
The strategy profile (s∗1 , . . . , s
∗
n) is a Nash equilibrium if and only if for every
i = 1, . . . , n we have s∗i ∈ Ri (s∗1 , . . . , s∗i−1, s∗i+1, . . . , s∗n).
Example: Mixed strategy Nash equilibrium
ˆ The Nash equilibrium is the point where R1(y) and R2(x) intersect.
ˆ It corresponds to x = 12 and y =
1
2
ˆ Given y = 12 , player 1 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
ˆ Given x = 12 , player 2 obtains an expected payoff equal to zero and does not have
an incentive to deviate.
34