Chapter Twenty-Eight
Game Theory
博弈论
Contents
Dominant strategy
Nash equilibrium
Prisoner’s dilemma and repeated
games
Multiple equilibria and sequential
games
Pure and mixed strategies
Game Theory
Game theory models strategic
behavior by agents who understand
that their actions affect the actions of
other agents,
Some Applications of Game Theory
The study of oligopolies (industries
containing only a few firms)
The study of cartels; e.g,OPEC
The study of externalities; e.g,using
a common resource such as a
fishery.
The study of military strategies.
What is a Game?
A game consists of
–a set of players
–a set of strategies for each player
–the payoffs to each player for every
possible list of strategy choices by
the players.
Two-Player Games
A game with just two players is a
two-player game.
We will study only games in which
there are two players,each of whom
can choose between only two
strategies.
An Example of a Two-Player Game
The players are called A and B.
Player A has two strategies,called
“Up” and,Down”.
Player B has two strategies,called
“Left” and,Right”.
The table showing the payoffs to
both players for each of the four
possible strategy combinations is
the game’s payoff matrix (支付矩阵 ).
An Example of a Two-Player Game
A play of the game is a pair such as (U,R)
where the 1st element is the strategy
chosen by Player A and the 2nd is the
strategy chosen by Player B.
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
What plays are we likely to see for this
game?
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
If B plays Left then A’s best reply is Down.
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
If B plays Right then A’s best reply is Down.
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
So no matter what B plays,A’s
best reply is always Down,
Down is A’s dominant strategy （ 超优策略）,
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
Similarly,Left is B’s dominant strategy,
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
Therefore,(Down,Left) is dominant strategy
for both players,It is the only equilibrium,
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
No Dominant Strategy for One Player
When Strength Is Weakness
大猪小猪
P W
P
W
(-1,10)
(6,4)
(-1,10)
(0,0)
No Dominant Strategy for Both
The Battle of Sexes
小红小东
C S
C
S
(2,1)
(0,0)
(0,0)
(1,2)
Nash Equilibrium
A play of the game where each strategy is
a best reply to the other is a Nash
equilibrium.
A dominant strategy equilibrium is a Nash
equilibrium;
In the,strength is weakness” example,
(W,P) is a Nash equilibrium.
In the,battle of sexes” example,there are
two Nash equilibria.
The Prisoner’s Dilemma
A Nash equilibrium may not be
Pareto optimal/efficient.
Consider a famous second example
of a two-player game called the
Prisoner’s Dilemma （ 囚徒困境）,
The Prisoner’s Dilemma
What plays are we likely to see for this
game?
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
If Bonnie plays Silence then Clyde’s best
reply is Confess.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
If Bonnie plays Silence then Clyde’s best
reply is Confess.
If Bonnie plays Confess then Clyde’s
best reply is Confess.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
So no matter what Bonnie plays,Clyde’s
best reply is always Confess.
Confess is a dominant strategy for Clyde.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
Similarly,no matter what Clyde plays,
Bonnie’s best reply is always Confess.
Confess is a dominant strategy for
Bonnie also.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
So the only Nash equilibrium for this
game is (C,C),even though (S,S) gives
both Bonnie and Clyde better payoffs.
The only Nash equilibrium is inefficient.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
Other Examples of Prisoner’s Dilemma
Cheating in a Cartel.
Price competition.
Military competition in the cold war.
How to Avoid Prisoner’s Dilemma
Repeated games
– Finite number of periods
– Infinite number of periods or uncertain
about the (finite number of periods)
Tit-for-tat
The demand factor (water meters and
airlines)
Binding contract
Multiple Equilibria
Chicken game
Youth 2
Youth 1
Swerve
Straight
Swerve (0,0)
(1,-1)
(-1,1)
(-2,-2)
Straight
Multiple Equilibria
Sometimes a game has more than
one Nash equilibrium and it is hard
to say which is more likely to occur.
Solutions:
–Coordination
–Strategic behavior; establish
reputation
–Sequential moves
A Sequential Game Example
When such a game is sequential it is
sometimes possible to argue that
one of the Nash equilibria is more
likely to occur than the other,
A Sequential Game Example
Incumbent
Entrant
(Enter,don’t fight) and (stay out,fight) are
both Nash equilibria when this game is
played simultaneously
and we have no way of deciding which
equilibrium is more likely to occur.
Fight Don’t fight
Enter
Stay
out (1,9)
(0,0)
(1,8)
(2,1)
Suppose instead that the game is played
sequentially,with incumbent leading and
entrant following.
We can rewrite the game in its extensive
form.
A Sequential Game Example
Incumbent
Entrant
Fight Don’t fight
Enter
Stay
out (1,9)
(0,0)
(1,8)
(2,1)
A Sequential Game Example
Fight Don’t
fight
EnterStay out
(1,9) (1,8) (0,0) (2,1)
Entrant
Incumbent Incumbent
Don’t
fightFight
(Stay out,Fight) is a Nash equilibrium.
A Sequential Game Example
Fight Don’t
fight
EnterStay out
(1,9) (1,8) (0,0) (2,1)
Entrant
Incumbent Incumbent
Don’t
fightFight
(Stay out,Fight) is a Nash equilibrium.
(Enter,Don’t Fight) is a Nash equilibrium.
Which is more likely to occur?
The entrant prefers (Enter,Don’t
Fight),but the incumbent may threat
to fight.
Is the threat credible?
Can make it credible.
A Sequential Game Example
A Sequential Game Example
Fight Don’t
fight
EnterStay out
(1,9) (1,8) (0,2) (2,1)
Entrant
Incumbent Incumbent
Don’t
fightFight
By building up excess capacity,the threat
becomes credible,The potential entrant
stays out,
Pure Strategies
In all previous examples,players are
thought of as choosing to play either one
or the other,but no combination of
both; that is,as playing purely one or the
other,
The strategies presented so far are
players’ pure strategies （ 纯粹策略）,
Consequently,equilibria are pure
strategy Nash equilibria,
Must every game have at least one pure
strategy Nash equilibrium?
Pure Strategies
Player B
Player A
Here is a new game,Are there any pure
strategy Nash equilibria?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium? No.
Is (D,L) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium? No.
Is (D,L) a Nash equilibrium? No.
Is (D,R) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium? No.
Is (D,L) a Nash equilibrium? No.
Is (D,R) a Nash equilibrium? No.
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
More Examples
Matching Pennies
Player B
Player A
(1,-1) (-1,1)
(-1,1) (1,-1)
H
T
H T
More Examples
点球进攻球员守门员
(1,0) (0,1)
(0,1) (1,0)
左右左 右
Pure Strategies
Player B
Player A
So the game has no Nash equilibria in pure
strategies,Even so,the game does have a
Nash equilibrium,but in mixed strategies
(混合策略 ).
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Mixed Strategies
Instead of playing purely Up or Down,
Player A selects a probability
distribution (pU,1-pU),meaning that with
probability pU Player A will play Up and
with probability 1-pU will play Down.
Player A is mixing over the pure
strategies Up and Down.
The probability distribution (pU,1-pU) is a
mixed strategy for Player A.
Mixed Strategies
Similarly,Player B selects a probability
distribution (pL,1-pL),meaning that with
probability pL Player B will play Left and
with probability 1-pL will play Right.
Player B is mixing over the pure
strategies Left and Right.
The probability distribution (pL,1-pL) is a
mixed strategy for Player B.
Mixed Strategies
Player A
This game has no pure strategy Nash
equilibria but it does have a Nash
equilibrium in mixed strategies,How is it
computed?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Player B
Mixed Strategies
Player A
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
If B plays Left her expected payoff is2 5 1p p
U U( )
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
If B plays Left her expected payoff is
If B plays Right her expected payoff is
2 5 1p pU U( ).
4 2 1p pU U( ).
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
2 5 1 4 2 1p p p pU U U U( ) ( )If then
B would play only Left,But there are no
Nash equilibria in which B plays only Left,
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
2 5 1 4 2 1p p p pU U U U( ) ( )If then
B would play only Right,But there are no
Nash equilibria in which B plays only Right,
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,B
must be indifferent between playing Left or
Right; i.e.
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
2 5 1 4 2 1p p p pU U U U( ) ( )
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,B
must be indifferent between playing Left or
Right; i.e.
2 5 1 4 2 1
3 5
p p p p
p
U U U U
U
( ) ( )
/,
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,B
must be indifferent between playing Left or
Right; i.e.
2 5 1 4 2 1
3 5
p p p p
p
U U U U
U
( ) ( )
/,
(1,2) (0,4)
(0,5) (3,2)
U,
D,
L,pL R,1-pL
5
3
5
2
Player B
Mixed Strategies
Player A
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
If A plays Up his expected payoff is,)1(01
LLL p?pp?
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
If A plays Up his expected payoff is
If A plays Down his expected payoff is ).1(3)1(30
LLL ppp?
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
.)1(01 LLL p?pp?
Player B
Mixed Strategies
Player A
p pL L3 1( )If then A would play only Up.
But there are no Nash equilibria in which A
plays only Up,
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
If
Down,But there are no Nash equilibria in
which A plays only Down,
p pL L3 1( )then A would play only
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,A
must be indifferent between playing Up or
Down; i.e.p pL L3 1( )
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,A
must be indifferent between playing Up or
Down; i.e.p p pL L L3 1 3 4( ) /,
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,A
must be indifferent between playing Up or
Down; i.e.p p pL L L3 1 3 4( ) /,
(1,2) (0,4)
(0,5) (3,2)
L,R,
U,
D,
5
3
5
2
4
3
4
1Player B
Mixed Strategies
Player B
Player A
So the game’s only Nash equilibrium has A
playing the mixed strategy (3/5,2/5) and has
B playing the mixed strategy (3/4,1/4).
(1,2) (0,4)
(0,5) (3,2)
U,
D,
5
3
5
2
L,R,4
3
4
1
Mixed Strategies
Player B
Player A
The payoffs will be (1,2) with probability3
5
3
4
9
20
(1,2) (0,4)
(0,5) (3,2)
U,
D,
L,R,4
3
4
1
5
3
5
2 9/20
Mixed Strategies
Player B
Player A
The payoffs will be (0,4) with probability3
5
1
4
3
20
(0,4)
(0,5) (3,2)
U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
Mixed Strategies
Player B
Player A
The payoffs will be (0,5) with probability2
5
3
4
6
20
(0,4)
(0,5)
U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
6/20 (3,2)
Mixed Strategies
Player B
Player A
The payoffs will be (3,2) with probability2
5
1
4
2
20
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
Player B
Player A
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
Player B
Player A
A’s expected Nash equilibrium payoff is1 9
20 0
3
20 0
6
20 3
2
20
3
4,
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
Player B
Player A
A’s expected Nash equilibrium payoff is1 9
20 0
3
20 0
6
20 3
2
20
3
4,
B’s expected Nash equilibrium payoff is2 9
20 4
3
20 5
6
20 2
2
20
16
5,
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
For games with multiple pure
strategies,there also exists mixed
strategies.
Example,Chicken game,The
probability that each player plays
straight is?.
How Many Nash Equilibria?
A game with a finite number of
players,each with a finite number of
pure strategies,has at least one
Nash equilibrium.
So if the game has no pure strategy
Nash equilibrium then it must have at
least one mixed strategy Nash
equilibrium.
Game Theory
博弈论
Contents
Dominant strategy
Nash equilibrium
Prisoner’s dilemma and repeated
games
Multiple equilibria and sequential
games
Pure and mixed strategies
Game Theory
Game theory models strategic
behavior by agents who understand
that their actions affect the actions of
other agents,
Some Applications of Game Theory
The study of oligopolies (industries
containing only a few firms)
The study of cartels; e.g,OPEC
The study of externalities; e.g,using
a common resource such as a
fishery.
The study of military strategies.
What is a Game?
A game consists of
–a set of players
–a set of strategies for each player
–the payoffs to each player for every
possible list of strategy choices by
the players.
Two-Player Games
A game with just two players is a
two-player game.
We will study only games in which
there are two players,each of whom
can choose between only two
strategies.
An Example of a Two-Player Game
The players are called A and B.
Player A has two strategies,called
“Up” and,Down”.
Player B has two strategies,called
“Left” and,Right”.
The table showing the payoffs to
both players for each of the four
possible strategy combinations is
the game’s payoff matrix (支付矩阵 ).
An Example of a Two-Player Game
A play of the game is a pair such as (U,R)
where the 1st element is the strategy
chosen by Player A and the 2nd is the
strategy chosen by Player B.
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
What plays are we likely to see for this
game?
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
If B plays Left then A’s best reply is Down.
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
If B plays Right then A’s best reply is Down.
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
So no matter what B plays,A’s
best reply is always Down,
Down is A’s dominant strategy （ 超优策略）,
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
Similarly,Left is B’s dominant strategy,
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
An Example of a Two-Player Game
Therefore,(Down,Left) is dominant strategy
for both players,It is the only equilibrium,
Player B
Player A
L R
U
D
(1,2)
(2,1)
(0,1)
(1,0)
No Dominant Strategy for One Player
When Strength Is Weakness
大猪小猪
P W
P
W
(-1,10)
(6,4)
(-1,10)
(0,0)
No Dominant Strategy for Both
The Battle of Sexes
小红小东
C S
C
S
(2,1)
(0,0)
(0,0)
(1,2)
Nash Equilibrium
A play of the game where each strategy is
a best reply to the other is a Nash
equilibrium.
A dominant strategy equilibrium is a Nash
equilibrium;
In the,strength is weakness” example,
(W,P) is a Nash equilibrium.
In the,battle of sexes” example,there are
two Nash equilibria.
The Prisoner’s Dilemma
A Nash equilibrium may not be
Pareto optimal/efficient.
Consider a famous second example
of a two-player game called the
Prisoner’s Dilemma （ 囚徒困境）,
The Prisoner’s Dilemma
What plays are we likely to see for this
game?
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
If Bonnie plays Silence then Clyde’s best
reply is Confess.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
If Bonnie plays Silence then Clyde’s best
reply is Confess.
If Bonnie plays Confess then Clyde’s
best reply is Confess.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
So no matter what Bonnie plays,Clyde’s
best reply is always Confess.
Confess is a dominant strategy for Clyde.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
Similarly,no matter what Clyde plays,
Bonnie’s best reply is always Confess.
Confess is a dominant strategy for
Bonnie also.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
The Prisoner’s Dilemma
So the only Nash equilibrium for this
game is (C,C),even though (S,S) gives
both Bonnie and Clyde better payoffs.
The only Nash equilibrium is inefficient.
Clyde
Bonnie
(-5,-5) (-30,-1)
(-1,-30) (-10,-10)
S
C
S C
Other Examples of Prisoner’s Dilemma
Cheating in a Cartel.
Price competition.
Military competition in the cold war.
How to Avoid Prisoner’s Dilemma
Repeated games
– Finite number of periods
– Infinite number of periods or uncertain
about the (finite number of periods)
Tit-for-tat
The demand factor (water meters and
airlines)
Binding contract
Multiple Equilibria
Chicken game
Youth 2
Youth 1
Swerve
Straight
Swerve (0,0)
(1,-1)
(-1,1)
(-2,-2)
Straight
Multiple Equilibria
Sometimes a game has more than
one Nash equilibrium and it is hard
to say which is more likely to occur.
Solutions:
–Coordination
–Strategic behavior; establish
reputation
–Sequential moves
A Sequential Game Example
When such a game is sequential it is
sometimes possible to argue that
one of the Nash equilibria is more
likely to occur than the other,
A Sequential Game Example
Incumbent
Entrant
(Enter,don’t fight) and (stay out,fight) are
both Nash equilibria when this game is
played simultaneously
and we have no way of deciding which
equilibrium is more likely to occur.
Fight Don’t fight
Enter
Stay
out (1,9)
(0,0)
(1,8)
(2,1)
Suppose instead that the game is played
sequentially,with incumbent leading and
entrant following.
We can rewrite the game in its extensive
form.
A Sequential Game Example
Incumbent
Entrant
Fight Don’t fight
Enter
Stay
out (1,9)
(0,0)
(1,8)
(2,1)
A Sequential Game Example
Fight Don’t
fight
EnterStay out
(1,9) (1,8) (0,0) (2,1)
Entrant
Incumbent Incumbent
Don’t
fightFight
(Stay out,Fight) is a Nash equilibrium.
A Sequential Game Example
Fight Don’t
fight
EnterStay out
(1,9) (1,8) (0,0) (2,1)
Entrant
Incumbent Incumbent
Don’t
fightFight
(Stay out,Fight) is a Nash equilibrium.
(Enter,Don’t Fight) is a Nash equilibrium.
Which is more likely to occur?
The entrant prefers (Enter,Don’t
Fight),but the incumbent may threat
to fight.
Is the threat credible?
Can make it credible.
A Sequential Game Example
A Sequential Game Example
Fight Don’t
fight
EnterStay out
(1,9) (1,8) (0,2) (2,1)
Entrant
Incumbent Incumbent
Don’t
fightFight
By building up excess capacity,the threat
becomes credible,The potential entrant
stays out,
Pure Strategies
In all previous examples,players are
thought of as choosing to play either one
or the other,but no combination of
both; that is,as playing purely one or the
other,
The strategies presented so far are
players’ pure strategies （ 纯粹策略）,
Consequently,equilibria are pure
strategy Nash equilibria,
Must every game have at least one pure
strategy Nash equilibrium?
Pure Strategies
Player B
Player A
Here is a new game,Are there any pure
strategy Nash equilibria?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium? No.
Is (D,L) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium? No.
Is (D,L) a Nash equilibrium? No.
Is (D,R) a Nash equilibrium?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Pure Strategies
Player B
Player A
Is (U,L) a Nash equilibrium? No.
Is (U,R) a Nash equilibrium? No.
Is (D,L) a Nash equilibrium? No.
Is (D,R) a Nash equilibrium? No.
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
More Examples
Matching Pennies
Player B
Player A
(1,-1) (-1,1)
(-1,1) (1,-1)
H
T
H T
More Examples
点球进攻球员守门员
(1,0) (0,1)
(0,1) (1,0)
左右左 右
Pure Strategies
Player B
Player A
So the game has no Nash equilibria in pure
strategies,Even so,the game does have a
Nash equilibrium,but in mixed strategies
(混合策略 ).
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Mixed Strategies
Instead of playing purely Up or Down,
Player A selects a probability
distribution (pU,1-pU),meaning that with
probability pU Player A will play Up and
with probability 1-pU will play Down.
Player A is mixing over the pure
strategies Up and Down.
The probability distribution (pU,1-pU) is a
mixed strategy for Player A.
Mixed Strategies
Similarly,Player B selects a probability
distribution (pL,1-pL),meaning that with
probability pL Player B will play Left and
with probability 1-pL will play Right.
Player B is mixing over the pure
strategies Left and Right.
The probability distribution (pL,1-pL) is a
mixed strategy for Player B.
Mixed Strategies
Player A
This game has no pure strategy Nash
equilibria but it does have a Nash
equilibrium in mixed strategies,How is it
computed?
(1,2) (0,4)
(0,5) (3,2)
U
D
L R
Player B
Mixed Strategies
Player A
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
If B plays Left her expected payoff is2 5 1p p
U U( )
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
If B plays Left her expected payoff is
If B plays Right her expected payoff is
2 5 1p pU U( ).
4 2 1p pU U( ).
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
2 5 1 4 2 1p p p pU U U U( ) ( )If then
B would play only Left,But there are no
Nash equilibria in which B plays only Left,
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
2 5 1 4 2 1p p p pU U U U( ) ( )If then
B would play only Right,But there are no
Nash equilibria in which B plays only Right,
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,B
must be indifferent between playing Left or
Right; i.e.
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
2 5 1 4 2 1p p p pU U U U( ) ( )
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,B
must be indifferent between playing Left or
Right; i.e.
2 5 1 4 2 1
3 5
p p p p
p
U U U U
U
( ) ( )
/,
(1,2) (0,4)
(0,5) (3,2)
U,pU
D,1-pU
L,pL R,1-pL
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,B
must be indifferent between playing Left or
Right; i.e.
2 5 1 4 2 1
3 5
p p p p
p
U U U U
U
( ) ( )
/,
(1,2) (0,4)
(0,5) (3,2)
U,
D,
L,pL R,1-pL
5
3
5
2
Player B
Mixed Strategies
Player A
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
If A plays Up his expected payoff is,)1(01
LLL p?pp?
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
If A plays Up his expected payoff is
If A plays Down his expected payoff is ).1(3)1(30
LLL ppp?
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
.)1(01 LLL p?pp?
Player B
Mixed Strategies
Player A
p pL L3 1( )If then A would play only Up.
But there are no Nash equilibria in which A
plays only Up,
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
If
Down,But there are no Nash equilibria in
which A plays only Down,
p pL L3 1( )then A would play only
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,A
must be indifferent between playing Up or
Down; i.e.p pL L3 1( )
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,A
must be indifferent between playing Up or
Down; i.e.p p pL L L3 1 3 4( ) /,
(1,2) (0,4)
(0,5) (3,2)
L,pL R,1-pL
U,
D,
5
3
5
2
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium,A
must be indifferent between playing Up or
Down; i.e.p p pL L L3 1 3 4( ) /,
(1,2) (0,4)
(0,5) (3,2)
L,R,
U,
D,
5
3
5
2
4
3
4
1Player B
Mixed Strategies
Player B
Player A
So the game’s only Nash equilibrium has A
playing the mixed strategy (3/5,2/5) and has
B playing the mixed strategy (3/4,1/4).
(1,2) (0,4)
(0,5) (3,2)
U,
D,
5
3
5
2
L,R,4
3
4
1
Mixed Strategies
Player B
Player A
The payoffs will be (1,2) with probability3
5
3
4
9
20
(1,2) (0,4)
(0,5) (3,2)
U,
D,
L,R,4
3
4
1
5
3
5
2 9/20
Mixed Strategies
Player B
Player A
The payoffs will be (0,4) with probability3
5
1
4
3
20
(0,4)
(0,5) (3,2)
U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
Mixed Strategies
Player B
Player A
The payoffs will be (0,5) with probability2
5
3
4
6
20
(0,4)
(0,5)
U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
6/20 (3,2)
Mixed Strategies
Player B
Player A
The payoffs will be (3,2) with probability2
5
1
4
2
20
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
Player B
Player A
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
Player B
Player A
A’s expected Nash equilibrium payoff is1 9
20 0
3
20 0
6
20 3
2
20
3
4,
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
Player B
Player A
A’s expected Nash equilibrium payoff is1 9
20 0
3
20 0
6
20 3
2
20
3
4,
B’s expected Nash equilibrium payoff is2 9
20 4
3
20 5
6
20 2
2
20
16
5,
(0,4)U,
D,
L,R,4
3
4
1
5
3
5
2
(1,2)
9/20 3/20
(0,5) (3,2)
6/20 2/20
Mixed Strategies
For games with multiple pure
strategies,there also exists mixed
strategies.
Example,Chicken game,The
probability that each player plays
straight is?.
How Many Nash Equilibria?
A game with a finite number of
players,each with a finite number of
pure strategies,has at least one
Nash equilibrium.
So if the game has no pure strategy
Nash equilibrium then it must have at
least one mixed strategy Nash
equilibrium.
