Dynamic Games of Complete Information
Dynamic Games of Complete and Imperfect Information
73-347 Game Theory--Lecture 21
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 21
Today’s Agenda
Review of previous class
Infinitely repeated games
73-347 Game Theory--Lecture 21
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 21
Present value
73-347 Game Theory--Lecture 21
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 21
Every subgame of an infinitely repeated game is identical to the game as a whole
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 21
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 21
Example: subgame perfect Nash equilibrium
Check whether there is a subgame perfect Nash equilibrium in which player i plays Li at every stage, or the Nash equilibrium of the stage game is played at each stage.
This can be done by the following two steps.
73-347 Game Theory--Lecture 21
Example: subgame perfect Nash equilibrium
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 21
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 21
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 this Nash equilibrium induces a Nash equilibrium in every subgame
73-347 Game Theory--Lecture 21
Trigger strategy: step 1
1
2
t-1
t
t+1
t+2
Stage
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, L2)
(L1, L2)
(L1, L2)
P2: Trigger
P2: deviate trigger at t
73-347 Game Theory--Lecture 21
Trigger strategy: step 1 cont’d
1
2
t-1
t
t+1
t+2
Stage
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, L2)
(L1, L2)
(L1, L2)
P2: Trigger
P2: deviate trigger at t
73-347 Game Theory--Lecture 21
Trigger strategy: step 1 cont’d
1
2
t-1
t
t+1
t+2
Stage
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, R2)
(R1, L2)
(L1, L2)
(L1, L2)
P2: Trigger
P2: deviate trigger at t
73-347 Game Theory--Lecture 21
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
73-347 Game Theory--Lecture 21
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 21
Trigger strategy: step 2 cont’d
We have two classes of subgames:
subgame following a history (from stage 1) in which the stage outcomes are all (R1, R2)
subgame following a history (from stage 1) 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 21
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 21
Lecture 21
Lecture 21
Lecture 21
