Chapter Twenty-Eight
Game Theory
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; . OPEC
The study of externalities; . 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
This is the game’s
payoff matrix.
Player B
Player A
Player A’s payoff is shown first. Player B’s payoff is shown second.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
. if A plays Up and B plays Right then A’s payoff is 1 and B’s payoff is 8.
This is the game’s
payoff matrix.
Player B
Player A
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
And if A plays Down and B plays Right then A’s payoff is 2 and B’s payoff is 1.
This is the game’s
payoff matrix.
Player B
Player A
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
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.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
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
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
Is (U,R) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
If B plays Right then A’s best reply is Down since this improves A’s payoff from 1 to 2. So (U,R) is not a likely play.
Is (U,R) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
Is (D,R) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
Is (D,R) a likely play?
If B plays Right then A’s best reply is Down.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
If B plays Right then A’s best reply is Down.
If A plays Down then B’s best reply is Right.
So (D,R) is a likely play.
Is (D,R) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
Is (D,L) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
If A plays Down then B’s best reply is Right, so (D,L) is not a likely play.
Is (D,L) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
Is (U,L) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
If A plays Up then B’s best reply is Left.
Is (U,L) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
If A plays Up then B’s best reply is Left.
If B plays Left then A’s best reply is Up.
So (U,L) is a likely play.
Is (U,L) a likely play?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Nash Equilibrium
A play of the game where each strategy is a best reply to the other is a Nash equilibrium.
Our example has two Nash equilibria; (U,L) and (D,R).
An Example of a Two-Player Game
Player B
Player A
(U,L) and (D,R) are both Nash equilibria for the game.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
An Example of a Two-Player Game
Player B
Player A
(U,L) and (D,R) are both Nash equilibria for the game. But which will we see? Notice that (U,L) is preferred to (D,R) by both players. Must we then see (U,L) only?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
The Prisoner’s Dilemma
To see if Pareto-preferred outcomes must be what we see in the play of a game, 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
Who Plays When?
In both examples the players chose their strategies simultaneously.
Such games are simultaneous play games.
Who Plays When?
But there are games in which one player plays before another player.
Such games are sequential play games.
The player who plays first is the leader. The player who plays second is the follower.
A Sequential Game Example
Sometimes a game has more than one Nash equilibrium and it is hard to say which is more likely to occur.
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
Player B
Player A
(U,L) and (D,R) are both Nash equilibria when this game is played simultaneously and we have no way of deciding which equilibrium is more likely to occur.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
A Sequential Game Example
Player B
Player A
Suppose instead that the game is played sequentially, with A leading and B following.
We can rewrite the game in its extensive
form.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first. B plays second.
A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first. B plays second.
(U,L) is a Nash equilibrium.
A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first. B plays second.
(U,L) is a Nash equilibrium.
(D,R) is a Nash equilibrium. Which is more likely to occur?
A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first. B plays second.
If A plays U then B plays L; A gets 3.
A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first. B plays second.
If A plays U then B plays L; A gets 3.
If A plays D then B plays R; A gets 2.
A Sequential Game Example
U
D
L
L
R
R
(3,9)
(1,8)
(0,0)
(2,1)
A
B
B
A plays first. B plays second.
If A plays U then B plays L; A gets 3.
If A plays D then B plays R; A gets 2. So (U,L) is the likely Nash equilibrium.
Pure Strategies
Player B
Player A
This is our original example once more. Suppose again that play is simultaneous. We discovered that the game has two Nash equilibria; (U,L) and (D,R).
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Pure Strategies
Player B
Player A
Player A’s has been thought of as choosing to play either U or D, but no combination of both; that is, as playing purely U or D. U and D are Player A’s pure strategies.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Pure Strategies
Player B
Player A
Similarly, L and R are Player B’s pure strategies.
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
Pure Strategies
Player B
Player A
Consequently, (U,L) and (D,R) are pure strategy Nash equilibria. Must every game have at least one pure strategy Nash equilibrium?
L
R
U
D
(3,9)
(0,0)
(1,8)
(2,1)
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
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 is
(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
(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
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
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; .
(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; .
(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; .
(1,2)
(0,4)
(0,5)
(3,2)
U,
D,
L,pL
R,1-pL
Player B
Mixed Strategies
Player A
(1,2)
(0,4)
(0,5)
(3,2)
L,pL
R,1-pL
U,
D,
Player B
Mixed Strategies
Player A
If A plays Up his expected payoff is
(1,2)
(0,4)
(0,5)
(3,2)
L,pL
R,1-pL
U,
D,
Player B
Mixed Strategies
Player A
If A plays Up his expected payoff is If A plays Down his expected payoff is
(1,2)
(0,4)
(0,5)
(3,2)
L,pL
R,1-pL
U,
D,
Player B
Mixed Strategies
Player A
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,
Player B
Mixed Strategies
Player A
If
Down. But there are no Nash equilibria in
which A plays only Down.
then A would play only
(1,2)
(0,4)
(0,5)
(3,2)
L,pL
R,1-pL
U,
D,
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium, A must be indifferent between playing Up or Down; .
(1,2)
(0,4)
(0,5)
(3,2)
L,pL
R,1-pL
U,
D,
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium, A must be indifferent between playing Up or Down; .
(1,2)
(0,4)
(0,5)
(3,2)
L,pL
R,1-pL
U,
D,
Player B
Mixed Strategies
Player A
So for there to exist a Nash equilibrium, A must be indifferent between playing Up or Down; .
(1,2)
(0,4)
(0,5)
(3,2)
L,
R,
U,
D,
Player 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,
L,
R,
Mixed Strategies
Player B
Player A
The payoffs will be (1,2) with probability
(1,2)
(0,4)
(0,5)
(3,2)
U,
D,
L,
R,
9/20
Mixed Strategies
Player B
Player A
The payoffs will be (0,4) with probability
(0,4)
(0,5)
(3,2)
U,
D,
L,
R,
(1,2)
9/20
3/20
Mixed Strategies
Player B
Player A
The payoffs will be (0,5) with probability
(0,4)
(0,5)
U,
D,
L,
R,
(1,2)
9/20
3/20
6/20
(3,2)
Mixed Strategies
Player B
Player A
The payoffs will be (3,2) with probability
(0,4)
U,
D,
L,
R,
(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,
(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 is
(0,4)
U,
D,
L,
R,
(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 is
B’s expected Nash equilibrium payoff is
(0,4)
U,
D,
L,
R,
(1,2)
9/20
3/20
(0,5)
(3,2)
6/20
2/20
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.
