EC202
Dynamic Games of Complete Information and
Repeated Games
Week 5
Christian Soegaard∗
∗Department of Economics
University of Warwick
8th February 2021
1/37
Overview of this lecture
Dynamic games of complete information
Repeated games
Repeated games: Preferences and discounting
Finitely repeated games
Infinitely repeated games
Grim trigger strategy
Tit-for-tat strategy
2/37
Reading
A Primer in Game THeory
Robert Gibbons
Pearson
Ch. 2
An Introduction to Game Theory
Martin J. Osborne
Oxford University Press
Ch. 5,14,15
3/37
Reading
Microeconomics: an intuitive approach
with calculus
Thomas Nechyba
Cengage
Ch. 24.A
Intermediate Microeconomics
with calculus
Hal R. Varian
Norton
Ch. 29
4/37
Dynamic games of complete information
I In this course we will consider many applications to game
theory.
I We will study games with different levels of information:
1. Static games of complete information
2. Dynamic games of complete information
3. Static games of incomplete information
4. Dynamic games of incomplete information
I In this lecture, we will consider the second type.
5/37
Dynamic games of complete information
I Every game is played by a set of rules, which have to specify
five things:
1. who is playing (which players)
2. what they are playing with (alternative actions or choices)
3. when each player gets to play (or in what order)
4. how much they stand to gain
5. what each player knows when they act
6/37
The normal form of static game of complete information
I Consider the following game, represented in normal form:
1, 2 L R
U 1,1 0,0
D 0,0 2,2
I Nash equilibria: (U, L) and (D,R).
7/37
Dynamic games of complete information: the extensive
form
I In a sequential game, players move sequentially. The
extensive form of a game specifies the following:
1. The set of players
2. The sequence of moves (who moves when)
3. Each player’s possible actions
4. Each player’s level of information
5. Each player’s pay-off contingent on all of the possible choices
8/37
The extensive form representation: simultaneous moves
I The extensive form of a game is essentially a game tree:
U D
L R L R
Player 1
Player 2 Player 2
(1, 1) (0, 0) (0, 0) (2, 2)
9/37
The extensive form representation: sequential moves
I In this game, Player 1 moves first. Player 2 then observes
Player 1’s choice and then gets to move.
U D
L R L R
Player 1
Player 2 Player 2
(1, 1) (0, 0) (0, 0) (2, 2)
10/37
Level of information
I In a sequential game, players have complete information if
the extensive form is common knowledge.
I Players have perfect information if at every instance that a
player has to make a move, he or she knows the full history of
moves up until that point, before making his or her choice.
11/37
Backward induction
I The sequential move game can be solved by backward
induction.
I Consider Player 2’s decision. Having observed Player 1’s
move, Player 2 knows at which of the two possible nodes she
is located. Hence,
I If Player 1 has chosen U, Player 2 would choose L since 1 > 0.
I If Player 1 has chosen D, Player 2 would choose R since 2 > 0.
I Player 1 would anticipate Player 2’s optimal response to each
of her own choices:
I If Player 1 plays U, Player 2 would respond with L, and Player
1’s pay-off would be 1.
I If Player 1 plays D, Player 2 would respond with R, and Player
1’s pay-off would be 2.
I Thus, backward induction requires Player 1’s best response
choice be D with pay-offs (2, 2).
12/37
Strategies and actions
I In game theory, a strategy is a complete plan of action, which
specifies a feasible action in every contingency in which the
player is called on to act.
I Notice that in the game considered here for Player 1, who
moves only at the beginning, there is no difference between
actions and strategies.
I Player 1 has two feasible actions and two (pure) strategies –
U and D.
I In contrast, since Player 2 has two feasible actions in each of
the two contingencies where Player 2 has to make a choice,
she has four feasible strategies:
I LL: Play L if Player 1 plays U and L if Player 1 plays D,
I LR: Play L if Player 1 plays U and R if Player 1 plays D,
I RL: Play R if Player 1 plays U and L if Player 1 plays D,
I RR: Play R if Player 1 plays U and R if Player 1 plays D.
13/37
Normal form of a sequential game
I Hence, the normal form of the sequential game takes the
following form:
1, 2 LL LR RL RR
U 1,1 1,1 0,0 0,0
D 0,0 2,2 0,0 2,2
I Nash equilibria: (U, LL), (D, LR) and (D,RR).
14/37
Non-credible threats
I The Nash equilibrium allows non-credible threats.
I For example, (U, LL) requires Player 2’s response to D be L.
I But if Player 1 does play D, it would be irrational for Player 2
to play L. Thus, Player 1 shouldn’t believe that Player 2 will
respond with L if she chooses D.
I If Player 1 realises that Player 2’s threat is unreasonable, it
doesn’t make sense for Player 1 to play U.
I Similarly, (D,RR) requires Player 2’s response to U be R.
However, if Player 1 does play U, it would be irrational for
Player 2 to play R.
I By forcing each player to actually carry out her actions
(threats), backward induction rules out those Nash equilibria
based on unrealistic beliefs.
15/37
Non-credible threats
I What about (D, LR)? In this NE, the actions chosen by
Player 1 and Player 2, respectively, are optimal at every node
where the players have to play.
I The Nash equilibrium (D, LR) is said to be a subgame
perfect equilibrium, because the actions prescribed by the
equilibrium strategies D and LR are optimal in every possible
subgame of the game.
I In games with complete and perfect information, a subgame is
any part of a game that meets the following criteria:
1. It has a single initial node.
2. It contains all the nodes that are successors of the initial node.
3. It contains all the nodes that are successors of any node it
contains.
I The key feature about a subgame is that, when seen in
isolation, it constitutes a game on its own.
16/37
Games and subgames
I In the game we have just considered, there are three
subgames:
U D
L R L R
Player 1
Player 2 Player 2
(1, 1) (0, 0) (0, 0) (2, 2)
L R
Player 2
(1, 1) (0, 0)
L R
Player 2
(0, 0) (2, 2)
I There are three subgames in this game: 1) The entire game;
2) The subgame beginning at Player 2’s node after Player 1
has chosen U; 3) The subgame beginning at Player 2’s node
after Player 1 has chosen D.
17/37
Subgame perfection
I The solution concept of subgame perfect Nash equilibrium is a
refinement of the Nash equilibrium that eliminates
non-credible threats.
I Subgame perfection requires that an equilibrium strategy
profile be a Nash equilibrium in every subgame.
I As a result, in a subgame perfect Nash equilibrium each
player’s behaviour is optimal even in positions not reached on
the equilibrium path.
I Backward induction coincides with subgame perfection
because it involves working from the end of the game back to
the root of the game tree and identifying for each player, at
every possible node where the agent has to play, her best
response to the action that got her to that particular node.
18/37
Subgame perfection
I Note that (D,RR) involves Player 2 playing R in the subgame
beginning at Player 2’s node after Player 1 has chosen U,
which is not a Nash equilibrium for that (single-player) game.
I Similarly, (U, LL) involves Player 2 playing L in the subgame
beginning at Player 2’s node after Player 1 has chosen D,
which is not a Nash equilibrium for that (single-player) game.
I In contrast, (D, LR) is a Nash equilibrium in each subgame.
19/37
Application: entry deterrence
I In the following game, Player 1 is a potential entrant whereas
Player 2 is an incumbent firm:
Out Enter
Fight Accommodate
Firm 1
Firm 2
(0, 2)
(−3,−1) (2, 1)
I Firm 1, who moves first, can either stay out or enter. If Firm
1 enters, Firm 2 can either fight or accommodate.
20/37
Application: entry deterrence
I The subgames are:
Out Enter
Fight Accommodate
Firm 1
Firm 2
(0, 2)
(−3,−1) (2, 1)
Fight Accommodate
Firm 2
(−3,−1) (2, 1)
21/37
Application: entry deterrence
I Backward induction (subgame perfection) stipulates that Firm
1 should enter and Firm 2 should accommodate. Notice,
however, that there is also a Nash equilibrium where Firm 1
chooses to stay out and Firm 2 fights if Firm 1 enters.
(1, 2) Fight Accommodate
Out 0, 2 0, 2
Enter −3,−1 2, 1
I The threat on which this Nash Equilibrium is based on,
namely that Firm 2 will fight if Firm 1 enters, is non-credible,
because it would not be in Firm 2’s interests to carry out that
threat. Subgame perfection eliminates this equilibrium.
22/37
Preferences: discounting
I The outcome of a repeated game is a sequence of outcomes
of a strategic game.
I We assume pay-off of a game is the discounted sum of the
associated sequence of pay-offs.
I Each player i has pay-off function ui for strategic game and a
discount factor δi ∈ [0, 1].
I Player evaluates sequence (a1, a2, ..aT ) as:
ui (a1) + δiui (a2) + δ
2
i ui (a3) + ...+ δ
T−1
i ui (aT ) =
T∑
t=1
δt−1i ui (at)
23/37
Two-stage repeated games: preferences over outcomes
I Different pay-offs for the same strategic game may generate
different preferences for the repeated game.
I Consider the following prisoners’ dilemma games (C is
cooperate, D is defect):
1, 2 C D
C 2,2 0,3
D 3,0 1,1
1, 2 C D
C 2,2 0,5
D 5,0 1,1
I In the first game the sequence of outcomes [(C ,C ), (C ,C )] is
preferred to [(D,C ), (C ,D)].
I This is not so for the second game.
24/37
Repeated games: definition
I We will formally define a repeated game.
Definition
The T-period repeated game G – or G (T ) – for the discount
factor δ is the extensive game with complete information and
simultaneous moves in which:
1 The set of players is L;
2 The set of terminal histories is the set of sequences
(a1, a2, ..., aT ) of action profiles in G ;
3 The set of actions available to any player i after any history is
Si ;
4 Each player i evaluates each terminal history (a1, a2, ..., aT )
according to its discounted average (1− δ)∑Tt=1 δt−1i ui (at).
25/37
Two-stage repeated prisoners’ dilemma
I Consider the following prisoners’ dilemma (C is cooperate, D
is defect):
1, 2 C D
C 0,0 -2,1
D 1,-2 -1,-1
I Players 1 and 2 play this game twice.
I The sets of actions available are Sit , i = 1, 2, t = 1, 2.
I In the first stage, players pick actions from S11 and S21,
respectively.
I In the second stage, players pick from S12 and S22,
respectively.
26/37
Two-stage repeated prisoners’ dilemma
I For each feasible outcome of the first stage game (s11, s21),
the second-stage game that remains has a unique Nash
equilibrium denoted (s∗12(s11, s21), s
∗
22(s11, s21)).
I That is, the unique Nash equilibrium of the second-stage
game is (D,D) regardless of the first-stage outcome.
I Payoffs are u1 (s∗12(s11, s21), s
∗
22(s11, s21)) and
u2 (s
∗
12(s11, s21), s
∗
22(s11, s21)).
27/37
Two-stage repeated prisoners’ dilemma
I We will analyse the first stage of the two-stage prisoners’
dilemma by taking into account the outcome of the remaining
two-stage game, namely (D,D) with payoffs (−1,−1).
(i) Stage game
1, 2 C D
C 0,0 -2,1
D 1,-2 -1,-1
(ii) First stage
1, 2 C D
C -1,-1 -3,0
D 0,-3 -2,-2
I The first stage game also has a unique equilibrium.
I Cooperation cannot be achieved.
28/37
Two-stage repeated prisoners’ dilemma
I More generally, let G = {L;S1, ..,Sn; u1, .., un} denote a static
game of complete information in which players 1 through n
choose actions s1 through sn from the action spaces S1
through Sn with payoffs u1(s1, .., sn) through un(s1, .., sn).
The game G is the stage game of the repeated game.
29/37
Two-stage repeated prisoners’ dilemma
Definition
Given a stage game G , let G (T ) denote the finitely repeated game
in which G is played T times, with the outcomes of all preceding
plays observed before the next play begins. The payoffs for G (T )
are simply the sum of the payoffs from the T stage games.
Proposition
If the stage game G has a unique Nash equilibrium then, for any
finite T , the repeated game G (T ) has a unique subgame-perfect
outcome: the Nash equilibrium of G is played in every stage.
30/37
Two-stage repeated games
I Consider the following game:
1, 2 L′′ M ′′ R ′′
L′ 1,1 5,0 0,0
M ′ 0,5 4,4 0,0
R ′ 0,0 0,0 3,3
I Pure-strategy Nash-equilibria (L′, L′′) and (R ′,R ′′).
31/37
Two-stage repeated games
I We would like to show that there is a subgame perfect
equilibrium in which the strategy pair (M ′,M ′′) is played in
the first stage.
I Assume as before that players anticipate that the second-stage
outcome will be a Nash equilibrium of the first-stage game.
I Since the stage game has more than one Nash equilibrium, it
is now possible for the players to anticipate that different
first-stage outcomes will be followed by different stage-game
outcomes in the second stage.
I Suppose players anticipate that (R ′,R ′′) will be the
second-stage outcome of the game if the first-stage outcome
was (M ′,M ′′), but that it will be (L′, L′′) if any of the other
eight first-stage outcomes occur.
32/37
Two-stage repeated games
I Add the payoffs of the second stage to the first-stage game
(i) Stage game
1, 2 L′′ M ′′ R ′′
L′ 1,1 5,0 0,0
M ′ 0,5 4,4 0,0
R ′ 0,0 0,0 3,3
(ii) First stage
1, 2 L′′ M ′′ R ′′
L′ 2,2 6,1 1,1
M ′ 1,6 7,7 1,1
R ′ 1,1 1,1 4,4
33/37
Two-stage repeated games
I Let ((w , x), (y , z)) denote an outcome of the repeated game –
(w , x) in the first stage and (y , z) in the second.
I The Nash equilibrium (L′, L′′) in Table (ii) corresponds with
the subgame-perfect outcome ((L′, L′′) , (L′, L′′)).
I Likewise, the Nash equilibrium (R ′,R ′′) in Table (ii)
corresponds with the subgame-perfect outcome
((R ′,R ′′) , (L′, L′′)).
I The third Nash equilibrium in Table (ii), (M ′,M ′′), is
different, however. It corresponds with the subgame-perfect
outcome ((M ′,M ′′) , (R ′,R ′′)).
I Thus, cooperation can be achieved in the first stage of a
subgame-perfect outcome of the repeated game.
34/37
Two-stage repeated games
I This is an example of a more general point: if
G = {L;S1, ..,Sn; u1, .., un} is a static game of complete
information with multiple Nash equilibria then there may be
subgame-perfect outcomes of the repeated game G (T ) in
which, for any t < T , the outcome in stage t is not a Nash
equilibrium of G .
35/37
Infinitely repeated games: grim trigger strategy
I Consider the following Prisoner’s Dilemma:
1, 2 C D
C 2,2 0,3
D 3,0 1,1
I What is the pay-off from infinite cooperation?
I What is the deviation pay-off?
36/37
Infinitely repeated games: tit-for-tat
I Consider instead a tit-for-tat strategy.