Dynamic Games of Complete Information
Dynamic Games of Complete and Imperfect Information
73-347 Game Theory--Lecture 16
Outline of dynamic games of complete information
Dynamic games of complete information
Extensive-form representation
Dynamic games of complete and perfect information
Game tree
Subgame-perfect Nash equilibrium
Backward induction
Applications
Dynamic games of complete and imperfect information
More applications
Repeated games
73-347 Game Theory--Lecture 16
Today’s Agenda
Review of previous class
Game tree representing imperfect information
Subgame
Subgame-perfect Nash equilibrium
Backward induction
73-347 Game Theory--Lecture 16
Dynamic (or sequential-move) games of complete information
A set of players
Who moves when and what action choices are available?
What do players know when they move?
Players’ payoffs are determined by their choices.
All these are common knowledge among the players.
73-347 Game Theory--Lecture 16
Definition: extensive-form representation
The extensive-form representation of a game specifies:
the players in the game
when each player has the move
what each player can do at each of his or her opportunities to move
what each player knows at each of his or her opportunities to move
the payoff received by each player for each combination of moves that could be chosen by the players
73-347 Game Theory--Lecture 16
Dynamic games of complete and perfect information
Perfect information
All previous moves are observed before the next move is chosen.
A player knows Who has made What choices when she has an opportunity to make a choice
73-347 Game Theory--Lecture 16
Perfect information: illustration (sequential matching pennies)
Each of the two players has a penny.
Player 1 first chooses whether to show the Head or the Tail.
After observing player 1’s choice, player 2 chooses to show Head or Tail
Both players know the following rules:
If two pennies match (both heads or both tails) then player 2 wins player 1’s penny.
Otherwise, player 1 wins player 2’s penny.
Player 1
Player 2
H
T
-1, 1
1, -1
H
T
Player 2
H
T
1, -1
-1, 1
73-347 Game Theory--Lecture 16
Dynamic games of complete and imperfect information
Imperfect information
A player may not know exactly Who has made What choices when she has an opportunity to make a choice.
Example: player 2 makes her choice after player 1 does. Player 2 needs to make her decision without knowing what player 1 has made.
73-347 Game Theory--Lecture 16
Imperfect information: illustration
Each of the two players has a penny.
Player 1 first chooses whether to show the Head or the Tail.
Then player 2 chooses to show Head or Tail without knowing player 1’s choice,
Both players know the following rules:
If two pennies match (both heads or both tails) then player 2 wins player 1’s penny.
Otherwise, player 1 wins player 2’s penny.
Player 2
Player 1
Player 2
H
T
-1, 1
1, -1
H
T
H
T
1, -1
-1, 1
73-347 Game Theory--Lecture 16
Information set
Gibbons’ definition: An information set for a player is a collection of nodes satisfying:
the player has the move at every node in the information set, and
when the play of the game reaches a node in the information set, the player with the move does not know which node in the information set has (or has not) been reached.
All the nodes in an information set belong to the same player
The player must have the same set of feasible actions at each node in the information set.
73-347 Game Theory--Lecture 16
Information set: illustration
Player 1
L
R
Player 2
L’
R’
2, 2, 3
Player 2
L’
R’
3
L”
R”
3
L”
R”
3
L”
R”
3
L”
R”
1, 2, 0
3, 1, 2
2, 2, 1
2, 2, 1
0, 1, 1
1, 1, 2
1, 1, 1
an information set for player 3 containing three nodes
an information set for player 3 containing a single node
two information sets for player 2 each containing a single node
73-347 Game Theory--Lecture 16
Information set: illustration
All the nodes in an information set belong to the same player
Player 1
C
D
Player 2
E
F
3, 0, 2
2, 1, 3
Player 3
G
H
1, 3, 1
0, 2, 2
This is not a correct information set
73-347 Game Theory--Lecture 16
Information set: illustration
The player must have the same set of feasible actions at each node in the information set.
Player 1
C
D
Player 2
E
F
3, 0
2, 1
Player 2
G
H
1, 3
0, 2
1, 1
An information set cannot contains these two nodes
K
73-347 Game Theory--Lecture 16
Represent a static game as a game tree: illustration
Prisoners’ dilemma (another representation of the game in Figure of Gibbons. The first number is the payoff for player 1, and the second number is the payoff for player 2)
Prisoner 1
Prisoner 2
Prisoner 1
Mum
Fink
4, 4
5, 0
Mum
Fink
Mum
Fink
0, 5
1, 1
73-347 Game Theory--Lecture 16
Example: mutually assured destruction
Two superpowers, 1 and 2, have engaged in a provocative incident. The timing is as follows.
The game starts with superpower 1’s choice either ignore the incident ( I ), resulting in the payoffs (0, 0), or to escalate the situation ( E ).
Following escalation by superpower 1, superpower 2 can back down ( B ), causing it to lose face and result in the payoffs (1, -1), or it can choose to proceed to an atomic confrontation situation ( A ). Upon this choice, the two superpowers play the following simultaneous move game.
They can either retreat ( R ) or choose to doomsday ( D ) in which the world is destroyed. If both choose to retreat then they suffer a small loss and payoffs are (, ). If either chooses doomsday then the world is destroyed and payoffs are (-K, -K), where K is very large number.
73-347 Game Theory--Lecture 16
Example: mutually assured destruction
1
I
E
0, 0
2
B
A
1, -1
1
2
R
D
,
-K, -K
R
D
R
D
2
-K, -K
-K, -K
73-347 Game Theory--Lecture 16
Perfect information and imperfect information
A dynamic game in which every information set contains exactly one node is called a game of perfect information.
A dynamic game in which some information sets contain more than one node is called a game of imperfect information.
73-347 Game Theory--Lecture 16
Strategy and payoff
A strategy for a player is a complete plan of actions.
It specifies a feasible action for the player in every contingency in which the player might be called on to act.
It specifies what the player does at each of her information sets
Player 1
Player 2
H
T
-1, 1
1, -1
H
T
Player 2
H
T
1, -1
-1, 1
a strategy for player 1: H
a strategy for player 2: T
Player 1’s payoff is 1 and player 2’s payoff is -1 if player 1 plays H and player 2 plays T
73-347 Game Theory--Lecture 16
Strategy and payoff: illustration
1
I
E
0, 0
2
B
A
1, -1
1
2
R
D
,
-K, -K
R
D
R
D
2
-K, -K
-K, -K
a strategy for player 1: E, and R if player 2 plays A, written as ER
a strategy for player 2: A, R, if player 1 plays E, written as AR
73-347 Game Theory--Lecture 16
Nash equilibrium in a dynamic game
We can also use normal-form to represent a dynamic game
The set of Nash equilibria in a dynamic game of complete information is the set of Nash equilibria of its normal-form
How to find the Nash equilibria in a dynamic game of complete information
Construct the normal-form of the dynamic game of complete information
Find the Nash equilibria in the normal-form
73-347 Game Theory--Lecture 16
Remove nonreasonable Nash equilibrium
Subgame perfect Nash equilibrium is a refinement of Nash equilibrium
It can rule out nonreasonable Nash equilibria or non-creditable threats
We first need to define subgame
73-347 Game Theory--Lecture 16
Subgame
A subgame of a dynamic game tree
begins at a singleton information set (an information set contains a single node), and
includes all the nodes and edges following the singleton information set, and
does not cut any information set; that is, if a node of an information set belongs to this subgame then all the nodes of the information set also belong to the subgame.
73-347 Game Theory--Lecture 16
Subgame: illustration
1
I
E
0, 0
2
B
A
1, -1
1
2
R
D
,
-K, -K
R
D
R
D
2
-K, -K
-K, -K
a subgame
a subgame
Not a subgame
73-347 Game Theory--Lecture 16
Subgame-perfect Nash equilibrium
A Nash equilibrium of a dynamic game is subgame-perfect if the strategies of the Nash equilibrium constitute or induce a Nash equilibrium in every subgame of the game.
Subgame-perfect Nash equilibrium is a Nash equilibrium.
73-347 Game Theory--Lecture 16
Find subgame perfect Nash equilibria: backward induction
1
I
E
0, 0
2
B
A
1, -1
1
2
R
D
,
-K, -K
R
D
R
D
2
-K, -K
-K, -K
a subgame
a subgame
Starting with those smallest subgames
Then move backward until the root is reached
One subgame-perfect Nash equilibrium ( IR, AR )
73-347 Game Theory--Lecture 16
Find subgame perfect Nash equilibria: backward induction
1
I
E
0, 0
2
B
A
1, -1
1
2
R
D
,
-K, -K
R
D
R
D
2
-K, -K
-K, -K
a subgame
a subgame
Starting with those smallest subgames
Then move backward until the root is reached
Another subgame-perfect Nash equilibrium ( ED, BD )
73-347 Game Theory--Lecture 16
Summary
Dynamic game of complete and imperfect information
Subgame perfect Nash equilibrium
Backward induction
Next time
Bank runs ( of Gibbons)
Tariffs and imperfect international competition ( of Gibbons)
Reading lists
Sec A-C of Gibbons
73-347 Game Theory--Lecture 16
Lecture 16
Lecture 16
Lecture 16
