1 of 24

Repeated Games:�Theorems 5 and 6�

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

1

2 of 24

Outline�

Review
Repeated games

2

3 of 24

Repeated Game�

People often interact repeatedly:

Most employment relationships last a long time
Countries competing over tariff levels know that they will be affected by each others’ policies far into the future

In these dynamic situations, players “condition” their decisions on the history of their relationship

An employee may choose to work hard only if his employer gave him a good bonus in the preceding month
One country may set a low import tariff only if its trading partners had maintained low tariffs in the past

3

4 of 24

Repeated Game�

Stage game:

G = {Player 1, Player 2, S₁, S₂; u₁, u₂} denotes a static stage game in which player 1 chooses an action s₁from the action space S₁and player 2 chooses an action s₂ from the action space S₂, and payoffs are u₁ and u₂, respectively

Finitely repeated game:

G(T) denotes the finitely repeated game in which a stage game 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
In other words, a repeated game is a dynamic game of complete information in which a simultaneous-move game is played at least twice

4

5 of 24

Two-Stage Prisoners’ Dilemma�

Rules of the game:

Two players play (by choosing to Defect or Cooperate) the simultaneous move prisoners’ dilemma 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

Question: what is the SPNE?

5

		Player 2
		D₂	C₂
Player 1	D₁	1 , 1	5 , 0
Player 1	C₁	0 , 5	4 , 4

6 of 24

Two-Stage Prisoners’ Dilemma�

Informal game tree of the two-stage prisoners’ dilemma

D₁

C₁

P2

D₂

C₂

P2

D₂

C₂

D₁

C₁

P2

D₂

C₂

D₂

C₂

1�1

5� 0

0�5

4�4

P1

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

P1

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₁

C₁

D₁

C₁

D₁

C₁

P2

7 of 24

Two-Stage Prisoners’ Dilemma�

Formal game tree of the two-stage prisoners’ dilemma

D₁

C₁

P2

D₂

C₂

P2

D₂

C₂

D₁

C₁

P2

D₂

C₂

D₂

C₂

P1

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₁

C₁

D₁

C₁

D₁

C₁

P2

1+1�1+1

1+5�1+0

1+0�1+5

1+4�1+4

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

8 of 24

Two-Stage Prisoners’ Dilemma�

Question: what is the SPNE?

Start with stage 2
Disregarding the outcome of stage 1, the Nash equilibrium outcome in stage 2 is (D₁, D₂) with payoff of (1, 1)

8

		Player 2
		D₂	C₂
Player 1	D₁	1 , 1	5 , 0
Player 1	C₁	0 , 5	4 , 4

9 of 24

Two-Stage Prisoners’ Dilemma�

Informal game tree of the two-stage prisoners’ dilemma

D₁

C₁

P2

D₂

C₂

P2

D₂

C₂

D₁

C₁

P2

D₂

C₂

D₂

C₂

1�1

5� 0

0�5

4�4

P1

1�1

5� 0

0�5

4�4

1�1

5� 0

0�5

4�4

1�1

5� 0

0�5

4�4

P1

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₂

C₂

D₁

C₁

D₁

C₁

D₁

C₁

P2

1�1

5� 0

0�5

4�4

+1�+1

10 of 24

Two-Stage Prisoners’ Dilemma�

Question: what is the SPNE?

The unique SPNE is (D₁D₁D₁D₁D₁, D₂D₂D₂D₂D₂)
Player 1 plays D₁ at stage 1, and plays D₁ at stage 2 for any outcome of stage 1
Player 2 plays D₂ at stage 1, and plays D₂ at stage 2 for any outcome of stage 1

10

		Player 2
		D₂	C₂
Player 1	D₁	1+1,1+1	5+1,0+1
Player 1	C₁	0+1,5+1	4+1,4+1

11 of 24

Theorem 5: �Finitely Repeated Game

THEOREM 5: If the stage game G has a unique Nash equilibrium, then the repeated game G(T) has a unique SPNE, in which the Nash equilibrium of G is played in every stage t < T

In other words, if the simultaneous-move stage game G has a unique Nash equilibrium then a finitely repeated game G(T) has a SPNE, and this equilibrium is unique

11

12 of 24

N-Stage Prisoners’ Dilemma�

What is the SPNE if the prisoners’ dilemma game is played N times?

The unique SPNE is (D₁ ….. D₁, D₂ ….. D₂)

12

13 of 24

Experiment #7:�Repeated Game

Class experiment:

Prisoner’s dilemma game is played 10 times

The unique SPNE is (D₁D₁D₁D₁D₁…, D₂D₂D₂D₂D₂…)

13

		Player 2
		D₂	C₂
Player 1	D₁	1 , 1	5 , 0
Player 1	C₁	0 , 5	4 , 4

14 of 24

Experiment #7:�Results (2019 CWRU)

14

15 of 24

What happens if the stage game has more than one Nash equilibrium?

Rules of the game:

Two players play the following simultaneous move game twice
The outcome of the first stage is observed before the second stage begins
The payoff for the entire game is simply the sum of the payoffs from the two stages

What are the NE in the second stage of this game?

15

			Player 2
		D₂	C₂	M₂
Player 1	D₁	1 , 1	5 , 0	0 , 0
	C₁	0 , 5	4 , 4	0 , 0
	M₁	0 , 0	0 , 0	3 , 3

16 of 24

What happens if the stage game has more than one Nash equilibrium?

Informal game tree

16

P1

D₁

M₁

P2

D₂

M₂

C₂

D₂

M₂

C₂

D₂

M₂

C₂

P2

D₁

M₁

P2

D₂

M₂

C₂

D₂

M₂

C₂

D₂

M₂

C₂

P2

C₁

(1, 1)

(5, 0)

(0, 5)

(4, 4)

(0, 0)

C₁

(0, 0)

P1

(1, 1)

(5, 0)

(0, 5)

(0, 0)

(3, 3)

(4, 4)

(3, 3)

17 of 24

What happens if the stage game has more than one Nash equilibrium?

Question: what are the SPNE?

Assume that in the second stage in each subgame players play D₁ and D₂, then in the first stage the game will look like shown below
(D₁D₁D₁D₁D₁D₁D₁D₁D₁D₁, D₂D₂D₂D₂D₂D₂D₂D₂D₂D₂)
(M₁D₁D₁D₁D₁D₁D₁D₁D₁D₁, M₂D₂D₂D₂D₂D₂D₂D₂D₂D₂)

17

			Player 2
		D₂	C₂	M₂
Player 1	D₁	1+1,1+1	5+1,0+1	0+1,0+1
	C₁	0+1,5+1	4+1,4+1	0+1,0+1
	M₁	0+1,0+1	0+1,0+1	3+1,3+1

18 of 24

What happens if the stage game has more than one Nash equilibrium?

Question: what are the SPNE?

Assume that in the second stage in each subgame players play M₁ and M₂, then in the first stage the game will look like shown below
(D₁M₁M₁M₁M₁M₁M₁M₁M₁M₁, D₂M₂M₂M₂M₂M₂M₂M₂M₂M₂)
(M₁M₁M₁M₁M₁M₁M₁M₁M₁M₁, M₂M₂M₂M₂M₂M₂M₂M₂M₂M₂)

18

			Player 2
		D₂	C₂	M₂
Player 1	D₁	1+3,1+3	5+3,0+3	0+3,0+3
	C₁	0+3,5+3	4+3,4+3	0+3,0+3
	M₁	0+3,0+3	0+3,0+3	3+3,3+3

19 of 24

What happens if the stage game has more than one Nash equilibrium?

Question: what are the SPNE?

Assume that in the second stage in some subgames players play D₁ and D₂ while in others they play M₁ and M₂, then in the first stage the game will look like shown below (as an example)
(D₁D₁D₁D₁D₁M₁D₁D₁D₁D₁, D₂D₂D₂D₂D₂M₂D₂D₂D₂D₂)
(M₁D₁D₁D₁D₁M₁D₁D₁D₁D₁, M₂D₂D₂D₂D₂M₂D₂D₂D₂D₂)
(C₁D₁D₁D₁D₁M₁D₁D₁D₁D₁, C₂D₂D₂D₂D₂M₂D₂D₂D₂D₂)

19

			Player 2
		D₂	C₂	M₂
Player 1	D₁	1+1,1+1	5+1,0+1	0+1,0+1
	C₁	0+1,5+1	4+3,4+3	0+1,0+1
	M₁	0+1,0+1	0+1,0+1	3+1,3+1

20 of 24

What happens if the stage game has more than one Nash equilibrium?

Question: what are the SPNE?

There are also many other equilibria in this game
(D₁D₁M₁M₁M₁M₁M₁M₁M₁M₁, D₂D₂M₂M₂M₂M₂M₂M₂M₂M₂)
(D₁D₁D₁M₁M₁M₁M₁M₁M₁M₁, D₂D₂D₂M₂M₂M₂M₂M₂M₂M₂)
(D₁D₁M₁D₁M₁M₁M₁M₁M₁M₁, D₂D₂M₂D₂M₂M₂M₂M₂M₂M₂)
…

20

21 of 24

THEOREM 6: �Finitely Repeated

THEOREM 6: If the stage game G has multiple Nash equilibria, then the repeated game G(T) will have multiple SPNE, some of which may not be a part of the original stage game

In other words, if the simultaneous-move stage game G has multiple Nash equilibria then a finitely repeated game G(T) has multiple SPNE, and some of these equilibria may be “new”

21

22 of 24

Infinitely Repeated Games�

Next Time!

23 of 24

Thank you!

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

23

24 of 24

References�

Watson, J. (2013). Strategy: An Introduction to Game Theory (3rd Edition). Publisher: W. W. Norton & Company. (Chapter 22)

24