7 Repeated Games with Absorbing States

In this chapter we shall briefly examine repeated games with absorbing

states. A repeated game with absorbing states can be represented by just
one game (bi)matrix, where like before the entries contain payo↵s to the
players but now there are some entries that also contain an asterisk: ⇤.
These entries are called absorbing and this is to be interpreted in the
following way. Like in a repeated game, the players play the (bi)matrix
repeatedly, as long as none of the absorbing entries has been chosen. How-
ever, as soon as an absorbing entry has been selected with payo↵s (a, b),
play is essentially over: Player 1 will receive a at each further stage and
player 2 will receive b at each further stage. Like before we assume that
the players, independently, each want to maximize their own, individual,
average reward. If at some stage, no matter when, an absorbing entry with
payo↵s (a, b) is chosen, then the average reward to player 1 is a, while for
player 2 it is b, regardless of the payo↵s they got before hitting the absorb-
ing entry. Since after selecting an absorbing entry players have no more
strategic choices left, it looks like play moved to a new state, an absorbing
state, in which players 1 and 2 always receive a and b respectively.
The first repeated game with absorbing states that was ever examined,
is called the Big Match. We shall discuss this game in detail.

The Big Match is a zerosum repeated game with absorbing states that was
introduced by Gillette [1957], who raised the question whether it had a
value. It took eleven years for this question to be answered affirmatively.
This was done by Blackwell and Ferguson [1968], who describe the game
as follows:

“Every day player 2 chooses a number, 1 or 2, and player 1

tries to predict 2’s choice, winning a point if he is correct.
This continues as long as player 1 predicts 1. But if he ever
predicts 2, all future choices for both players are required to be
the same as that day’s choices: If player 1 is correct on that
day, he wins a point every day thereafter; if he is wrong on
that day, he wins zero every day thereafter. The payo↵ to 1 is
1
lim inf (a1 + · · · + at ), where at is the payo↵ at day t.”
t!1 t

This game, in which player 1 tries to match player 2’s choices by his own,
especially at the very moment that he predicts number 2, can be repre-
sented in the following way, where the payo↵s presented are those by player

59
2 to player 1 and where the asterisks denote the absorbing entries.

✓ L R ◆
T 1 0
B 0⇤ 1⇤

Clearly, T and L correspond to choosing number 1, while B and R cor-

respond to choosing number 2. Gillette [1957] made several observations
about this Big Match:

Observation 1: If player 1 would play a strategy that consists of playing

(1 p, p) at all stages for some fixed probability p, then he can not be sure
of getting any positive reward. This is clear if we distinguish two cases. If
p = 0, then player 1 would get a reward of 0 if player 2 is playing R all
the time. On the other hand, if p > 0, then player 1 would get 0 if player
2 is playing L all the time. The latter applies if p > 0, because then the
probability that player 1 will ever play B is equal to 1.

Observation 2: If player 1 would play a strategy that consists of playing

(1 pt , pt ) at stage t = 1, 2, 3, . . . , for some fixed probabilities p1 , p2 , p3 , . . .,
then he can not be sure of getting any positive reward. Here, the argu-
ment is that given the sequence of probabilities, there are two possibilities:
Either the probability that player 1 will ever play B is 1, or it is smaller
than 1. In the former case player 1 will get 0 if player 2 plays L all the
time, while in the latter case one can compute, for each " > 0 a stage N"
such that the probability of [player 1 ever choosing B after stage N" ] will
be at most ". Now player 1’s average reward will be at most " if player 2
plays L up to stage N" and R ever thereafter.

Observation 3: Player 2 can guarantee that player 1’s reward will not
exceed 12 , but he can not guarantee any lower reward. This can be seen as
follows: If player 2 plays ( 12 , 12 ) at all stages, then at any stage the expected
payo↵ to player 1 is 12 , no matter if he plays T or B. If player 2 plays
a strategy that consists of playing (1 qt , qt ) at stage t = 1, 2, 3, . . . , for
some fixed probabilities q1 , q2 , q3 , . . . , then again there are two possibilities:
Either qt  12 for all t, or there is some stage N with qN > 12 . In the former
case player 1 gets at least 12 by playing T all the time, while in the latter
case player 1 gets more than 12 by playing T at stages 1, 2, . . . , N 1, and
playing B at stage N (at which moment play absorbs).

Observation 4: Player 1 can not have any strategy ⇡ that guarantees

a reward of 12 . Why not? Remember that at any stage player 1 could

60
choose B with a probability that depends on his observation of player 2’s
behaviour in choosing L and R thus far. Again there are two possibilities:
Either there is, or there is not, a sequence of L’s and R’s such that at some
stage t player 1, using ⇡, chooses B with positive probability for the very
first time. If there is not, then clearly player 1 will get only 0 if player 2 is
choosing R all the time. And if there is, then assume that player 2 plays
the strategy that tells him to play such a specific sequence up to t 1,
where t is the first time that player 1 will play B with probability p > 0,
followed by playing L at stage t, and playing ( 12 , 12 ) at all later stages. Now
the average reward to player 1 for the strategy pair (⇡, ) is:
1 1
(1 p) · +p·0< .
2 2
Gillette’s observations tell us that player 1 can not guarantee to get any
amount higher than 0, which is not much considering that 0 is the smallest
payo↵ in the game, whereas player 2 can guarantee that player 1 will get
at most 12 . So the maxmin of the game is 0, while the minmax6 is 12 . As
such, the question arose: Does the Big Match have a value?

This question was answered affirmatively by Blackwell and Ferguson [1968].

Their paper was a real breakthrough because it shows that, in this type of
game, behavioural strategies are indispensable in achieving "-optimality,
which means getting at least the value minus ". To emphasize this point:
They showed that player 1 can guarantee in the Big Match an average
reward as close to 12 as he likes, by carefully taking into account the oppo-
nent’s behaviour, i.e., his past actions, in the process of choosing his own
actions. Here we write “can guarantee as close to 12 as he likes,” because
there is no way that player 1 can guarantee 12 (see observation 4). To
be more precise: Blackwell and Ferguson [1968] show that, for any non-
negative integer N , player 1 can get at least 12 N1 by using the following
strategy:
Let kt = Lt Rt be the number of times player 2 has chosen L minus the
number of times he has chosen R during the first t stages. Then at stage
t + 1 player 1 should play B with probability
1
.
(kt + N + 1)2
6
Here we write maxmin and minmax to simplify the notions of sup inf (⇡, ) and
⇡
inf sup (⇡, ), where (⇡, ) is the average reward to player 1 for the pair (⇡, ).
⇡

61
Notice that if player 2 chooses L all the time, then player 1 will not play
B during the first t stages with probability
1 1 1
(1 ) · (1 ) · · · (1 )
(N + 1)2 (N + 2)2 (N + t)2
which is equal to
1 1 1 1 1 1
(1 )·(1+ )·(1 )·(1+ ) · · · (1 )·(1+ )
N +1 N +1 N +2 N +2 N +t N +t
which equals
N N +2 N +1 N +2 N +t 1 N +t+1 N N +t+1
· · · ··· · = · .
N +1 N +1 N +2 N +3 N +t N +t N +1 N +t
By letting t go to infinity, we conclude by this expression that the prob-
ability of player 1 never choosing B is NN+1 and thus player 1’s average
reward is NN+1 .
Also notice that if player 2 chooses R all the time, then up to absorption
player 1 chooses B with probability
1 1 1 1 1 1
2
, 2, 2
, ..., , ,
(N + 1) N (N 1) 9 4 1
respectively at the first N stages. Hence absorption would happen for sure
and player 1’s average reward would be 1.

This work by Blackwell and Ferguson [1968] was generalized by Kohlberg

[1974] to show that every zerosum repeated game with absorbing states
has a value. For this purpose Kohlberg employs a slightly di↵erent type of
"-optimal strategy, which for the case of the Big Match would tell player
1 to play action 2 at stage t + 1 with probability "2 if kt < 0; and with
probability "2 (1 ")kt otherwise, where, as above, kt = Lt Rt , denotes
the excess of L’s over R’s among the first t choices of player 2.
Notice that if, playing against this strategy, player 2 would play R all
the time, then player 1 will play B at all stages with probability "2 > 0
and therefore, with probability 1, sooner or later player 1 will play B and
his average reward will be 1. If, on the other hand, player 2 would play
L all the time, then player 1 would play B at stage t with probability
"2 (1 ")t 1 for t = 1, 2, . . . . Given these probabilities it can be verified
that the probability of player 1 not choosing B in any of the first t stages
is at least

1 "2 · [1 + (1 ") + (1 ")2 + · · · + (1 ")t 1 ]

62
From this we can conclude that the probability of player 1 never playing
B is at least

1 "2 · [1 + (1 ") + (1 ")2 + (1 ")3 + · · · ] = 1 ".

Problem 75 Examine the following repeated game with absorbing states

✓ ⇤ ◆
1 0
.
0 2⇤

What would be the value of this game for player 1 if the payo↵s are given
for him? Can you guess what the ("-)optimal strategies for the players
would look like? Can you prove that these are "-optimal?

Problem 76 Examine the following repeated game with absorbing states

✓ ◆
1 0
.
0 1⇤

What would be the value of this game for player 1 if the payo↵s are given
for him? Can you guess what the ("-)optimal strategies for the players
would look like? Can you prove that these are "-optimal?

Problem 77 Examine the following repeated game with absorbing states.

✓ ◆
0 1
.
2⇤ 0⇤

What would be the value of this game for player 2 if this time the payo↵s
are given for that player? Can you guess what the ("-)optimal strategies
for the players would look like? Can you prove that they are "-optimal?

Let us now discuss a non-zerosum repeated game with absorbing states

that was first examined by Sorin [1986]:
✓ ◆
1, 0 0, 1
.
0, 2⇤ 1, 0⇤

Notice that the bottom entries are again absorbing, just like in the Big
Match.
If we want to find an equilibrium for this game, then we should observe
that player 1’s average reward should be at least 12 , since the value of the
zerosum game made up by his payo↵s is 0 (it is the Big Match). Similarly,

63
player 2’s average reward should be at least 23 , since that is the value of
the zerosum game made up by player 2’s payo↵s. Like we have seen for
repeated games, all points that are in between the payo↵s (1, 0), (0, 1) and
(0, 2) are feasible, because for all these points we can find strategies that
will give the specified point as reward. The following picture shows this
triangular region of all feasible rewards, while the small triangular region
inside consists of the feasible rewards that are individually rational as well.

(0,2)

(0,1)

(0,0) (1,0)

This time however, to achieve a feasible reward it is not possible to play a

sequence of entries in cyclic order because the entries in the bottom row
are absorbing. Therefore we have to do it di↵erently:
Take for example the point (0.6, 0.7) that is in the interior of the triangle
determined by the payo↵s (1, 0), (0, 1) and (0, 2). We take one point on the
line from (1, 0) to (0, 1) and one on the line from (1, 0) to (0, 2) such that
(0.6, 0.7) is in between these two points. Thus, we could take the points
(0.6, 0.4) and (0.6, 0.8) which have (0.6, 0.7) in between. Therefore, if at
stage 1 player 1 plays B with probability 34 while player 2 plays (0.4, 0.6),
while at al further stages player 1 plays T and player 2 plays (0.6, 0.4),
then the resulting average reward is:
3 3 1 1
· 0.4 · (0, 2) + · 0.6 · (1, 0) + · 0.6 · (1, 0) + · 0.4 · (0, 1) =
4 4 4 4
3 1
· (0.6, 0.8) + · (0.6, 0.4) = (0.6, 0.7).
4 4
So the point (0.6, 0.7) is a feasible reward. It is also individually rational
because (0.6, 0.7) ( 12 , 23 ). Would it correspond to an ("-)equilibrium,
just like any feasible individually rational reward in an ordinary repeated
game? Obviously, the absorbing entries make it much more complex.

64
Sorin observed that none of the points in the interior of this triangle can
correspond to an "-equilibrium. Quoting the words of Sorin, the argument
is the following:
“The idea of the proof is very simple: If the probability of
getting an absorbing payo↵ on the equilibrium path is less than
1, then after some time player 1 is essentially playing action 1;
the corresponding feasible rewards from this stage on are not
individually rational, hence a contradiction.”
In his paper Sorin [1986] shows that for this specific game the feasible
rewards that correspond to "-equilibria are the individiully rational rewards
that are on the line from (1, 0) to (0, 2); these are the pairs between and
including the points ( 23 , 23 ) and ( 12 , 1):

(0,2)

(0,1)

(0,0) (1,0)

Sorin used “Big Match type” strategies to establish "-equilibrium strate-

gies for these rewards. The work of Sorin was generalized by Vrieze and
Thuijsman [1989], who proved that "-equilibria exist for any two-person
repeated game with absorbing states. Later the type of strategies needed
to define equilibria was simplified a great deal (cf. Thuijsman [1992]). As
an example we shall describe "-equilibrium strategies that correspond to
the reward (0.6, 0.8), which is on the line segment from ( 23 , 23 ) to ( 12 , 1).
We use strategies based on the following fact from statistics: If player 2
is using the mixed action (0.4, 0.6) at all stages, then his “action frequen-
cies” should converge to (0.4, 0.6) with probability 1. More precisely: If
Lt and Rt denote (again) the numbers of times player 2 played L and R
respectively during the first t stages, then
1 1
lim ( Lt , Rt ) = (0.4, 0.6).
t!1 t t

65
This implies that for any " > 0 we can find a stage N" such that, given
that player 2 always uses (0.4, 0.6),
1
Prob [ | Lt 0.4| > " for any t > N" ] < ".
t
Now assume that player 1 plays the strategy ⇡ that tells him to:
- play T up to stage N"
- play (1 ", ") afters stage N" as long as | 1t Lt 0.4| < "
- play an "-optimal strategy in player 2’s zerosum game as soon as for some
t > N" it turns out that | 1t Lt 0.4| > ".
The latter implies that player 1 punishes player 2 as soon as he suspects
that player 2 is not playing according to (0.4, 0.6). This punishment means
that player 2’s reward is going to be at most 23 + ". If we let be the
strategy for player 2 that consists of playing (0.4, 0.6) at all stages, then
the strategy pair (⇡, ) is an "-equilibrium.
Problem 78 Find, for Sorin’s game, a pair of "-equilibrium strategies for
the reward ( 12 , 1). Do the same for ( 23 , 23 ).
Problem 79 Find, for each of the following repeated games with absorbing
states, an "-equilibrium and the corresponding reward:
✓ ◆
1, 0⇤ 0, 1⇤
a. A =
0, 2 1, 0
✓ ◆
1, 0 0, 1
b. B =
0, 2 1, 0⇤
✓ ◆
1, 0 0, 1
c. C =
0, 2⇤ 1, 0 J
✓ ◆
1, 0 0, 1⇤
d. D =
0, 2⇤ 1, 0
✓ ◆
1, 0⇤ 0, 1
e. E =
0, 2 1, 0⇤
✓ ◆
3, 1 1, 5⇤
f. F =
2, 3⇤ 0, 4
0 1
4, 2 0, 3⇤
g. G = @ 1, 4⇤ 4, 0 A
2, 1 1, 0

66
 1
We now prove that the value of the Big Match is 2

Let jt be the action (L or R) chosen by player 2 at time t 2 N. Let Lt

and Rt be the number of L’s and R’s respectively in (j1 , j2 , . . . , jt ), and let
kt = Lt Rt for each t 2 N. For sake of completion define k0 = 0. Now,
for N 2 N, let ⇡N be the strategy for player 1 to choose B at time t + 1
with probability
1
.
(kt + N + 1)2
Let = (j1 , j2 , . . .) be a pure strategy for player 2. We will show that the
expected average reward for player 1, playing ⇡N against , denoted by
(⇡N , ), will be at least 12 . Let T be the random variable that denotes
the number of stages after which player 1 chooses B at time T + 1, and let
T (m) denote the event [T m, or (T < m and jT +1 = R)].

We distinguish two cases based on a property of the sequence of actions

that are played by : Either kt = N for some t 2 N, or kt > N for all
t 2 N.

Case 1: kt = N for some t 2 N

Notice that in this case player 1, using ⇡N , chooses B with probability 1
when play reaches stage t.
Below, at the end of this chapter, we prove by induction that for all m 2 N
we have
N
P⇡N [T (m)] .
2(N + 1)
Using that with probability 1 player 1 will ever play B, we derive from this
inequality:
N
(⇡N , ) = P⇡N [jT +1 = R] = lim P⇡N [T (m)] .
m!1 2(N + 1)

Case 2: kt > N for all t 2 N

For each m 2 N let µL (m) = P⇡N [T < m and jT +1 = L] and let µL =
limm!1 µL (m). Define µR (m) and µR analogously. Furthermore, let m
be the strategy defined by: play the same action jt as determined by for
any stage t 2 {1, 2, . . . , m} and play the mixed action ( 12 , 12 ) at all stages
t > m.
Any realization of strategy m , for any m 2 N, provides a sequence of
actions for which Case 1 applies, because km , km+1 , km+2 , . . . will behave

67
as random walk that visits all integers with probability 1. Because of this
we have
N
(⇡N , m ) ,
2(N + 1)
which implies for player’s reward against that
1
(⇡N , ) = µR + (1 µL µR )
2
1
= lim [µR (m) + (1 µL (m) µR (m))]
m!1 2
N
= lim (⇡N , m) .
m!1 2(N + 1)
The combination of Cases 1 and 2 proves that ⇡N yields at least 2(NN+1)
against each strategy , where player 1 can choose N to be as large as
he likes. Because by playing ( 12 , 12 )1 player 2 can guarantee a maximum
payo↵ to player 1 of 12 , the value of the Big Match is 12 .

We now prove that for all m 2 N we have P⇡N [T (m)] N

2(N +1)
.
Proof by induction:
Suppose m = 1.
• If j1 = R, then
P⇡N [T (1)] = P⇡N [T 1 or (T < 1 and jT +1 = R)] = 1.
• If j1 = L, then
1 N N
P⇡N [T (1)] = P⇡N [T 1] = 1 (N +1)2 N +1 2(N +1)
.

Suppose that for some m 2 N we have P⇡N [T (m)] N

2(N +1)
for all N .
• If j1 = R, then
1 1
P⇡N [T (m + 1)] = (N +1)2
+ (1 (N +1) 2 )P⇡N 1 [T (m)]

1
(N +1)2
+ (1 1
) N 1 = 2+(N
(N +1)2 2N
+2)(N 1)
2(N +1)2
= 2(NN+1) .
• If j1 = L, then
1
P⇡N [T (m + 1)] = (1 (N +1)2
)P⇡N +1 [T (m)]
1 N +1 N
(1 (N +1) 2 ) 2(N +2) = 2(N +1)
.
The inequalities in the second part follow from the induction hypothesis.
Moreover, we have used that if j1 = R, then playing ⇡N at stages 2, 3, . . .
is the same as playing ⇡N 1 from stage 2 onwards, while j1 = L results in
player 1 playing strategy ⇡N +1 from stage 2 onwards. By the principle of
induction we conclude that for all m, N 2 N we have P⇡N [T (m)] 2(NN+1) .

68