Dynamic Games of Complete Information
Dynamic Games of Complete and Imperfect Information
73-347 Game Theory--Lecture 20
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 20
Today’s Agenda
Review of previous class
Repeated games
Infinitely repeated games
73-347 Game Theory--Lecture 20
Two-stage repeated game
Two-stage prisoners’ dilemma
Two players play the following simultaneous move game twice
The outcome of the first play is observed before the second play begins
The payoff for the entire game is simply the sum of the payoffs from the two stages. That is, the discount factor is 1.
Question: what is the subgame perfect Nash equilibrium?
Player 2
R2
4 , 4
0 , 5
R1
Player 1
5 , 0
1 , 1
L1
L2
73-347 Game Theory--Lecture 20
Game tree of the two-stage prisoners’ dilemma
1
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
1+1 1+1
1+5 1+0
1+0 1+5
1+4 1+4
1
1
1
1
5+1 0+1
5+5 0+0
5+0 0+5
5+4 0+4
0+1 5+1
0+5 5+0
0+0 5+5
0+4 5+4
4+1 4+1
4+5 4+0
4+0 4+5
4+4 4+4
73-347 Game Theory--Lecture 20
Informal game tree of the two-stage prisoners’ dilemma
1
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
1 1
5 0
0 5
4 4
1
1
1
1
(1, 1)
(5, 0)
(0, 5)
(4, 4)
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
73-347 Game Theory--Lecture 20
Informal game tree of the two-stage prisoners’ dilemma
1
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
1 1
5 0
0 5
4 4
1
1
1
1
(2, 2)
(6, 1)
(1, 6)
(5, 5)
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
73-347 Game Theory--Lecture 20
two-stage prisoners’ dilemma
The subgame-perfect Nash equilibrium (L1 L1L1L1L1, L2 L2L2L2L2) Player 1 plays L1 at stage 1, and plays L1 at stage 2 for any outcome of stage 1. Player 2 plays L2 at stage 1, and plays L2 at stage 2 for any outcome of stage 1.
Player 2
R2
5 , 5
1 , 6
R1
Player 1
6 , 1
2 , 2
L1
L2
The payoff (1, 1) of the 2nd stage has been added to the first stage game.
73-347 Game Theory--Lecture 20
Finitely repeated game
A finitely repeated game is a dynamic game of complete information in which a (simultaneous-move) game is played a finite number of times, and the previous plays are observed before the next play.
The finitely repeated game has a unique subgame perfect Nash equilibrium if the stage game (the simultaneous-move game) has a unique Nash equilibrium. The Nash equilibrium of the stage game is played in every stage.
73-347 Game Theory--Lecture 20
What happens if the stage game has more than one Nash equilibrium?
Two players play the following simultaneous move game twice
The outcome of the first play is observed before the second play begins
The payoff for the entire game is simply the sum of the payoffs from the two stages. That is, the discount factor is 1.
Question: can we find a subgame perfect Nash equilibrium in which M1, M2 are played? Or, can the two players cooperate in a subgame perfect Nash equilibrium?
Player 2
3 , 3
0 , 0
0 , 0
R2
M2
0 , 0
0 , 0
R1
4 , 4
0 , 5
M1
Player 1
5 , 0
1 , 1
L1
L2
73-347 Game Theory--Lecture 20
Informal game tree
1
L1
R1
2
2
L2
R2
M2
L2
R2
M2
L2
R2
M2
2
L1
R1
2
2
L2
R2
M2
L2
R2
M2
L2
R2
M2
2
M1
(1, 1)
(5, 0)
(0, 5)
(4, 4)
(0, 0)
M1
(0, 0)
(0, 0)
(0, 0)
(3, 3)
1
(1, 1)
(5, 0)
(0, 5)
(0, 0)
(0, 0)
(0, 0)
(0, 0)
(3, 3)
(4, 4)
1
1
73-347 Game Theory--Lecture 20
Informal game tree and backward induction
1
L1
R1
2
2
L2
R2
M2
L2
R2
M2
L2
R2
M2
2
L1
R1
2
2
L2
R2
M2
L2
R2
M2
L2
R2
M2
2
M1
(1, 1)
(5, 0)
(0, 5)
(4, 4)
(0, 0)
M1
(0, 0)
(0, 0)
(0, 0)
(3, 3)
1
(1, 1)
(5, 0)
(0, 5)
(0, 0)
(0, 0)
(0, 0)
(0, 0)
(3, 3)
(4, 4)
(1, 1)
(1, 1)
(1, 1)
(3, 3)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
(1, 1)
+
1
1
73-347 Game Theory--Lecture 20
Two-stage repeated game
Subgame perfect Nash equilibrium:
At stage 1, player 1 plays M1, and player 2 plays M2.
At stage 2,
player 1 plays R1 if the first stage outcome is ( M1, M2 ), or plays L1 if the first stage outcome is not ( M1, M2 )
player 2 plays R2 if the first stage outcome is ( M1, M2 ), or plays L2 if the first stage outcome is not ( M1, M2 )
Player 2
4 , 4
1 , 1
1 , 1
R2
M2
1 , 1
1 , 1
R1
7 , 7
1 , 6
M1
Player 1
6 , 1
2 , 2
L1
L2
The payoffs of the 2nd stage has been added to the first stage game.
73-347 Game Theory--Lecture 20
Infinitely repeated game
A infinitely repeated game is a dynamic game of complete information in which a (simultaneous-move) game called the stage game is played infinitely, and the outcomes of all previous plays are observed before the next play.
Precisely, the simultaneous-move game is played at stage 1, 2, 3, ..., t-1, t, t+1, ..... The outcomes of all previous t-1 stages are observed before the play at the tth stage.
Each player discounts her payoff by a factor , where 0< < 1.
A player’s payoff in the repeated game is the present value of the player’s payoffs from the stage games.
73-347 Game Theory--Lecture 20
Present value
73-347 Game Theory--Lecture 20
Infinitely repeated game: example
The following simultaneous-move game is repeated infinitely
The outcomes of all previous plays are observed before the next play begins
Each player’s payoff for the infinitely repeated game is present value of the payoffs received at all stages.
Question: what is the subgame perfect Nash equilibrium?
Player 2
R2
4 , 4
0 , 5
R1
Player 1
5 , 0
1 , 1
L1
L2
73-347 Game Theory--Lecture 20
Example: subgame
Every subgame of an infinitely repeated game is identical to the game as a whole.
1
L1
R1
2
L2
R2
2
L2
R2
(1, 1)
(5, 0)
(0, 5)
(4, 4)
73-347 Game Theory--Lecture 20
Example: strategy
A strategy for a player is a complete plan. It can depend on the history of the play.
A strategy for player i: play Li at every stage (or at each of her information sets)
Another strategy called a trigger strategy for player i: play Ri at stage 1, and at the tth stage, if the outcome of each of all t-1 previous stages is (R1, R2) then play Ri; otherwise, play Li.
73-347 Game Theory--Lecture 20
Example: subgame perfect Nash equilibrium
Check whether there is a subgame perfect Nash equilibrium in which player i plays Li at every stage (or at each of her information sets).
This can be done by the following two steps.
Step 1: check whether the combination of strategies is a Nash equilibrium of the infinitely repeated game.
If player 1 plays L1 at every stage, the best response for player 2 is to play L2 at every stage.
If player 2 plays L2 at every stage, the best response for player 1 is to play L1 at every stage.
Hence, it is a Nash equilibrium of the infinitely repeated game.
73-347 Game Theory--Lecture 20
Example: subgame perfect Nash equilibrium cont’d
Step 2: check whether the Nash equilibrium of the infinitely repeated game induces a Nash equilibrium in every subgame of the infinitely repeated game.
Recall that every subgame of the infinitely repeated game is identical to the infinitely repeated game as a whole
Obviously, it induces a Nash equilibrium in every subgame
Hence, it is a subgame perfect Nash equilibrium.
73-347 Game Theory--Lecture 20
Example: subgame
1
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
1 1
5 0
0 5
4 4
1
1
1
1
(1, 1)
(5, 0)
(0, 5)
(4, 4)
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
TO INFINITY
73-347 Game Theory--Lecture 20
Trigger strategy
trigger strategy for player i: play Ri at stage 1, and at the tth stage, if the outcomes of all t-1 previous stages are (R1, R2) then play Ri; otherwise, play Li.
Check whether there is a subgame perfect Nash equilibrium in which each player plays the trigger strategy.
This can be done by the following two steps.
Step 1: check whether the combination of the trigger strategies is a Nash equilibrium of the infinitely repeated game
Step 2: if yes, check whether the Nash equilibrium induces a Nash equilibrium in every subgame
73-347 Game Theory--Lecture 20
Trigger strategy: step 1
Stage 1: (R1, R2)
Stage 2: (R1, R2)
Stage t-1: (R1, R2)
Stage t: (R1, L2)
Stage t+1: (L1, L2)
Stage t+2: (L1, L2)
73-347 Game Theory--Lecture 20
Trigger strategy: step 1 cont’d
Stage 1: (R1, R2)
Stage 2: (R1, R2)
Stage t-1: (R1, R2)
Stage t: (R1, L2)
Stage t+1: (L1, L2)
Stage t+2: (L1, L2)
73-347 Game Theory--Lecture 20
Trigger strategy: step 2
Step 2: check whether the Nash equilibrium induces a Nash equilibrium in every subgame of the infinitely repeated game.
Recall that every subgame of the infinitely repeated game is identical to the infinitely repeated game as a whole
Stage 1: (R1, R2)
Stage 2: (R1, R2)
Stage t-1: (R1, R2)
Stage t: (R1, R2)
Stage t+1: (R1, R2)
Stage t+2: (R1, R2)
73-347 Game Theory--Lecture 20
Step 2 cont’d: subgame
1
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
L1
R1
2
L2
R2
2
L2
R2
1 1
5 0
0 5
4 4
1
1
1
1
(1, 1)
(5, 0)
(0, 5)
(4, 4)
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
1 1
5 0
0 5
4 4
TO INFINITY
73-347 Game Theory--Lecture 20
Trigger strategy: step 2 cont’d
We have two classes of subgames:
subgame following a history in which the stage outcomes are all (R1, R2)
subgame following a history in which at least one stage outcome is not (R1, R2)
The Nash equilibrium of the infinitely repeated game induces a Nash equilibrium in which each player still plays trigger strategy for the first class of subgames
The Nash equilibrium of the infinitely repeated game induces a Nash equilibrium in which (L1, L2) is played forever for the second class of subgames.
73-347 Game Theory--Lecture 20
Summary
Finitely repeated games
Infinitely repeated games
Next time
Infinitely repeated games
Static games of incomplete information
Reading lists
Sec A-C of Gibbons
Sec of Gibbons
73-347 Game Theory--Lecture 20
Lecture 20
Lecture 20
