Repeated Games with Observation Costs∗
Eiichi Miyagawa
Department of Economics
Columbia University
Yasuyuki Miyahara
Graduate School of Business Administration
Kobe University
Tadashi Sekiguchi
Institute of Economic Research
Kyoto University
January 27, 2003
Abstract
This paper analyzes repeated games in which it is possible for players to observe the other players’ past actions without noise but it iscostly. One’s observation decision itself is not observable to the otherplayers, and this private nature of monitoring activity makes it diﬃcult
to give the players proper incentives to monitor each other. We provide
a suﬃcient condition for a feasible payoﬀ vector to be approximatedby a sequential equilibrium when the observation costs are suﬃciently
small. We then show that this result generates an approximate Folk
Theorem for a wide class of repeated games with observation costs.
The Folk Theorem holds for a variant of prisoners’ dilemma, partnership games, and any games in which the players have an ability to“burn” small amounts of their own payoﬀs.
Journal of Economic Literature Classiﬁcation Numbers: C72, C73,
D43, D82.
Key Words: repeated games, private monitoring, costly monitoring, Folk Theorem.
∗
This research was started while Miyagawa was visiting the Graduate School of Economics at Kobe University; he thanks the school for its hospitality. Sekiguchi thanks
ﬁnancial supports from Grant-in-Aid for Scientiﬁc Research and the Japan Economic Research Foundation. All of us thank the participants of the 8th Decentralization Conferencein Japan and the workshops at the University of Tokyo and Hitotsubashi University for
helpful comments.

1

1

Introduction

In the theory of repeated games, the benchmark assumption is that of perfect monitoring, i.e., the players obtain perfect information about the otherplayers’ past actions. Under the assumption, the theory shows that theplayers can sustain a large set of payoﬀ vectors as equilibria by making theiractions contingent on the other players’ past actions.1 The recent literature relaxes the assumption of perfect monitoring and considers the case inwhich players receive only imperfect (public or private) information about
the other players’ past actions.2
The present paper relaxes the assumption of perfect monitoring in adiﬀerent direction. We consider the case in which it is possible for theplayers to obtain perfect information about the other players’ past actions
but it is costly. We assume that at the end of each period, each player
decides whether to obtain information about the actions chosen by the otherplayers in the period. Obtaining the information costs a certain amount ofutility, which is referred to as the observation cost. If a player chooses not
to pay the observation cost at the end of a period, then she obtains noinformation about the other players’ actions chosen in the period.3 We also
assume that a player’s observation decision itself is not observable to theother players. Perfect monitoring can be considered as the limit case inwhich the observation costs are zero for all players.
It is important to note that the model of costly monitoring diﬀers considerably from that of perfect (costless) monitoring even when the observation
costs are arbitrarily small as long as they are positive. To see this, consider a repeated prisoners’ dilemma with costly monitoring. Suppose thatthe players use the trigger strategy proﬁle, in which each player starts withcooperation but switches to perpetual defection if (and only if) a defection
is observed in the past. If the observation costs are zero and the players
are suﬃciently patient, then the trigger strategy proﬁle is an equilibrium.
However, this strategy proﬁle is not an equilibrium when the observation
1

See, e.g., Abreu (1986, 1988) and Fudenberg and Maskin (1986).
For the case of imperfect public monitoring, see, e.g., Abreu, Pearce, andStacchetti (1990), Fudenberg, Levine, and Maskin (1994), and Fudenberg andLevine (1994). For the case of imperfect private monitoring, see, e.g., Sekiguchi (1997),
Bhaskar and van Damme (2002), Bhaskar and Obara (2002), Ely and Valimaki (2002),
Mailath and Morris (2002), Matsushima (2002), and Piccione (2002).
3
This formulation raises a subtle issue on when the players receive payoﬀs. While thisis discussed in detail in subsequent sections, for the time being imagine that the payoﬀs
are received as a whole when the game “ends,” interpreting the discount factor as theprobability with which the game continues.
22

costs are strictly positive even when they are arbitrarily small. The reason
is simply that since the strategy proﬁle is deterministic, each player knows
the other player’s past and future actions on the equilibrium path and has
no reason to pay the observation costs. Therefore, in equilibrium, no one
monitors the other player. However, then deviations from the strategy proﬁle are not detected and hence cooperation is not sustained as an equilibrium. This argument generalizes and we can show that at any pure-strategy
equilibrium of a repeated game with observation costs, the players play astage-game equilibrium in every period (with no observation activity).4
Therefore, a construction of non-trivial cooperative/eﬃcient equilibria
must use strategy proﬁles in which some of the players randomize. The
main contribution of the present paper is to show that such a construction
is possible and therefore some positive results are obtained in a wide classof situations. First, we provide a suﬃcient condition for a payoﬀ vector
to be approximated by a sequential equilibrium when the observation costs
are suﬃciently small and the players are suﬃciently patient. Using thecondition, we then prove an approximate Folk Theorem for several classesof repeated games with observation costs. The approximate Folk Theorem
is shown to hold for a variant of prisoners’ dilemma, partnership games, andany game in which the players have an ability to “burn” small amounts of
their own payoﬀs.
An important assumption for the positive results is small observation
costs. The results say only that a large set of payoﬀ vectors can be sustained
when the observation costs are small and the players are patient. We areunable to prove a general Folk Theorem/eﬃciency result for a given level ofobservation cost. However, we believe that our result is of some economic
relevance because in many interesting economic applications, the observation
costs can be considerably small. For example, consider two ﬁrms competingin terms of prices. If these ﬁrms compete in a small local market, it canbe a matter of walking several blocks to see the rival’s prices. The cost ofsuch activity can be indeed small in comparison with the magnitude of theirbusiness.
More theoretically, it can be argued that the approximate Folk Theorem
4

The unobservability of monitoring decisions plays an important role in the result. If
monitoring decisions are observable, then the situation does not diﬀer very much fromperfect monitoring. Indeed, in the repeated prisoners’ dilemma with observation costs,
cooperation can be sustained by a modiﬁed trigger strategy proﬁle in which punishment
is triggered by not only a single defection but also a single failure to observe the otherplayer’s action. On the other hand, the perfect observability of monitoring decisions isdiﬃcult to imagine when the monitoring activity takes the form of spying or glimpsing.

3

demonstrates the robustness of the assumption of perfect monitoring. On
the one hand, many regard perfect monitoring as an extreme assumption. In
reality, information about the past comes at a (possibly small) cost. On theother hand, as we have seen before, the model with zero observation costs
and the one with positive costs diﬀer signiﬁcantly in terms of the incentive
for monitoring. Thus, it is theoretically an interesting question whether
the two models yield qualitatively similar results, justifying our approach toregard perfect monitoring as a limit of costly monitoring.
A few papers have studied repeated games with costly monitoring. Ahn
and Suominen (2001) consider a random matching game (like the one in
Kandori (1992)) with a twist that each player is given an opportunity toinvest in a monitoring technology in the initial period. If the player invests
in the technology in the initial period, she can observe her neighbors’ actions
in all subsequent periods. Thus the costly monitoring activity in their model
has a once-and-for-all nature. In our model, on the other hand, the player
has to engage in costly monitoring in every period if she wants to keep trackof the other players’ behavior completely.
A paper more closely related to ours is Miyahara (2002), who considers
a repeated prisoners’ dilemma in which monitoring at the end of a period
gives a player information not only about the period but also about someof the previous periods. Miyahara (2002) shows that eﬃciency can be approximated if the monitoring costs are suﬃciently small. It is importantto point out that the result in the present paper does not subsume that of
Miyahara (2002) since the latter uses a construction that takes advantageof the assumption that more than one period in the past can be observed.
Our model is a special example of repeated games with private monitoring. Since each player’s observation (if any) is not observable to the otherplayers, it is private information, which makes our model private monitoring. The literature of repeated games with private monitoring has focusedon the case when players receive noisy signals of the other players’ actions
costlessly, while we examine the case when players obtain complete information if they pay observation costs. Thus, the results and the construction ofcooperative/eﬃcient equilibria in the literature do not apply in our model.
However, this does not mean that our model has no bearing on repeatedgames with noisy costless private monitoring. In Section 6, we brieﬂy discuss what happens if costly monitoring is introduced into repeated gameswith noisy private monitoring.
The remaining part of this paper is organized as follows. Section 2
introduces the model. Section 3 provides important deﬁnitions. Section 4states our main result, describes the strategy proﬁle used in the proof, and4sketches the proof. Section 5 applies the result to prove an approximate
Folk Theorem in a variant of prisoners’ dilemma, partnership games, andgames with an opportunity of utility burning. Section 6 discusses possible
extensions of our model. The Appendix proves the main result.

2

Model

The stage game is a ﬁnite n-player game G = {n, A, (ui )ni=1 }, where A =×ni=1 Ai and ui : A → R is player i’s stage payoﬀ function. We often writeu(a) = (ui (a))ni=1 . For each i, let Si be the set of all mixed actions forplayer i and let S = ×ni=1 Si . For a mixed action proﬁle s ∈ S, we abusenotation and let ui (s) denote the expected payoﬀ of player i under s. Let“co” denote convex hull, and deﬁne V = co{u(a) : a ∈ A}, which is the setof feasible payoﬀ vectors.
Game G itself does not include monitoring activity. Thus, precisely
speaking, G is not the game played in every period. It is meant to describe
the basic strategic interaction within each period.
The inﬁnitely repeated version of G (plus monitoring activity) with discounting and observation costs is denoted by Γ(δ, λ), where δ = (δ1 , . . . , δn ) ∈(0, 1)n is a vector of discount factors and λ = (λ1 , . . . , λn ) ∈ Rn++ is a vector of observation costs. We permit diﬀerential discount factors.5 In eachperiod, each player simultaneously chooses an action ai ∈ Ai and then decides whether to privately observe the actions that the other players chosein the period. For each player i, λi denotes the cost of observing the others’
actions. We also assume that if player i does not monitor the other players
at the end of a period, then no information about the action proﬁle of theother players in the period is revealed to player i. Each player’s monitoring decision itself is assumed to be private and not observable to the otherplayers. Hence player i’s private information on the play of a given past
period can be represented by a pair of her chosen action and observations,(ai , ωi ) ∈ Ai × (A−i ∪ {φ}). Here, (ai , ωi ) = (ai , a−i ) means that player ichose ai , monitored the other players, and observed a−i . On the other hand,(ai , ωi ) = (ai , φ) means that player i chose ai and did not monitor the otherplayers.
5

As Lehrer and Pauzner (1999) show, when discount factors are heterogeneous, payoﬀ
vectors outside V might be feasible. However, the present paper concentrates on sustaining
payoﬀ vectors in V for expositional simplicity. We consider diﬀerential discount factors
only to demonstrate that our analysis does not require identical discount factors, although
our construction can be used to sustain payoﬀ vectors outside V .

5

We assume that monitoring is the only way to obtain information about
the other players’ past actions. This implies that the players do not receive
the stage payoﬀs in each period, but receive them in total at the “end” ofthe repeated game. Of course, the inﬁnitely repeated game never ends under the basic interpretation of the game. However, if we regard each δi asa (subjective) probability with which the game continues, then the interpretation about the timing of receiving payoﬀ is less problematic. Anyway,
this assumption is extreme, and it is assumed to make the issue of costly
monitoring as stark as possible (and partly for analytical simplicity). In
Section 6, we brieﬂy comment on what happens if payoﬀs are received ineach period, in which case realized payoﬀs give players information about
the others’ actions.
We also assume that there exists a public randomization device which
generates a sunspot according to the uniform distribution over the unit
interval [0, 1]. At the beginning of each period, a sunspot is realized andobserved by the players before they choose their actions. The (private)
history for player i at the beginning of period t before she chooses an action
is denoted by hti and deﬁned as the sequence of her private information andrealized sunspots up to the beginning of the period. Thus, the set of all
possible histories for player i at period t is deﬁned by Hit = [0, 1]t × (Ai ×(A−i ∪ {φ}))t−1 , where Hi1 is equivalent to the set of sunspots. Then the settof possible histories for player i is Hi = ∪∞t=1 Hi .
Player i’s strategy σi is a function from Hi to Si × [0, 1]|Ai | where |Ai |is the cardinality of Ai . Thus, for any history hti ∈ Hi , we have σi (hti ) =(si (t), {li (ai , hti )}ai ∈Ai ), where si (t) is player i’s (possibly mixed) action inperiod t given hti , and li (ai , hti ) is the probability that player i monitors
the other players given that the history is hti and she played ai in period t.
Player i’s payoﬀs in Γ(δ, λ) are the average (expected) discounted sum of
the stage game payoﬀs minus observation costs. Formally, player i’s payoﬀsunder a strategy proﬁle σ = (σ1 , . . . , σn ) are denoted by gi (σ) and given bygi (σ) = (1 − δi )

∞

t=1



δit−1 E ui (a(t)) − λi · li (ai (t), hti ) | σ ,where E[ · | σ] denotes the expectation with respect to the probability
measure over histories induced by strategy proﬁle σ.

3

Deﬁnitions

This section introduces some deﬁnitions which facilitate subsequent analysis.
6Let the stage game G = {n, A, (ui )ni=1 } be given. For a given (possibly
mixed) action proﬁle s ∈ S for G, we deﬁne
BR i (s) = {ai ∈ Ai : ui (ai , s−i ) ≥ ui (ai , s−i )∀ai ∈ Ai },which is the set of (pure-action) best responses of player i against s−i . For
a given (pure) action proﬁle a ∈ A, we deﬁneBi (a) = {ai ∈ Ai : ui (ai , a−i ) > ui (a)},which is the set of (strictly) better replies to a−i ;/ BR i (a)},D(a) = {i : ai ∈which is the set of players for whom ai is not a best response to a−i ;D w (a) = {i : BR i (a) = {ai }},which is the set of players for whom ai is not a unique best response to a−i ;andSD(a) = {i : BR i (a ) = {ai } ∀a ∈ A},
which is the set of players for whom ai is the strictly dominant action.
Let NE (G) be the set of (mixed) Nash equilibria of G. A penal code
is a proﬁle of Nash equilibria, (ŝ(i))ni=1 , where ŝ(i) ∈ NE (G) for each i ∈{1, . . . , n}.6 We allow ŝ(i) = ŝ(j) for some i and j = i.
Given a penal code (ŝ(i))ni=1 , let E1 ⊆ A be the set of all action proﬁlesa ∈ A such that for some player i,(1-i) D(a) = {i},(1-ii) for all j = i, BR j (a) ∩ BR j (ŝ(i)) = ∅, and(1-iii) there exist ai ∈ Bi (a) and ζ ∈ (0, 1) such that for all j = i,aj ∈ BR j ((1 − ζ)ai + ζai , a−i ).

(1)

Next, let E2 ⊆ A be the set of all action proﬁles a ∈ A such that forsome players i and j = i,(2-i) {i, j} ⊆ D(a),6This terminology follows Abreu (1988), although our use of the term is slightly diﬀerent: while Abreu (1988) used the term for a proﬁle of repeated game equilibria, we use it
for a proﬁle of stage game equilibria.

7(2-ii) there exist ai ∈ Bi (a) and aj ∈ Bj (a) such that for all k ∈ {i, j},{ak , ak } ∩ BR k (ŝ(i)) ∪ BR k (ŝ(j)) = ∅,/ BR k (ŝ(i)) ∩ BR k (ŝ(j)).
(2-iii) for all k ∈/ {i, j} ∪ SD(a), ak ∈For a given a ∈ E2 , players i and j for whom (2-i)–(2-iii) hold are calledassociated players. For a given a ∈ E2 , there may exist more than one pairof associated players, but we select a pair {i, j} arbitrarily for each a ∈ E2
and denote the selected pair by AP (a). Similarly, for each a ∈ E1 and isuch that {i} = D(a), we let AP (a) = {i}. Let E = E1 ∪ E2 .
Given a penal code (ŝ(i))ni=1 , we say that a payoﬀ vector v = (vi )ni=1 ∈ Rn
is supportable with respect to (ŝ(i))ni=1 , if there exists a probability distribution on E, denoted (ρ(a))a∈E , such that(s-i) for any i, vi = a∈E ρ(a)ui (a),(s-ii) for any i, if there exists a ∈ E1 such that ρ(a) > 0 and D(a) = {i},then vi > ui (ŝ(i)),(s-iii) for any i, if there exists a ∈ E2 such that ρ(a) > 0 and i ∈ D w (a),then vi > ui (ŝ(i)), and(s-iv) for any a ∈ E2 such that ρ(a) > 0 and any k ∈ SD(a), if there existsâ ∈ E such that ρ(â) > 0 and âk = ak , then there exists such an âthat satisﬁes either â ∈ E2 or [â ∈ E1 (k) and âk = ak ] where âk is abetter reply that satisﬁes (1-iii) with respect to â.
Note that in (s-iii), i is not required to be an associated player. Condition (s-iv) says that if there exists a player k who plays her dominant action
in some a ∈ E2 in the support of ρ but does not play it in some â ∈ E in
the support, then either there exists such an â in E2 , or there exists suchan â ∈ E1 (k) such that an associated better reply that satisﬁes (1-iii) is not
the dominant action of the player. This technical condition is irrelevant for
many cases. For example, if no one plays her dominant action (if any) inthe support of ρ, then (s-iv) is trivially satisﬁed. Note also that if two or
more players have a dominant action in the stage game, then E1 is emptyby (1-ii) and therefore (s-iv) holds for any ρ.
Let V ∗ ⊆ V denote the set of supportable payoﬀ vectors with respect toa given penal code (ŝ(i))ni=1 .7
7

When the penal code is understood, we simply call V ∗ the set of supportable payoﬀ
vectors.

8

4

A Characterization of Equilibrium Payoﬀ Vectors

We are now ready to state our main result, which gives a suﬃcient condition
for a given payoﬀ vector to be approximated by a sequential equilibrium
when the observation costs (λi )ni=1 are suﬃciently small and the discountfactors (δi )ni=1 are suﬃciently close to one.
Proposition 1 Let (ŝ(i))ni=1 be a penal code and V ∗ be the set of supportable
payoﬀ vectors with respect to the penal code. Then for any v ∈ V ∗ and any
 > 0, there exist λ̄ = (λ̄i )ni=1 ∈ Rn++ and δ = (δ i )ni=1 ∈ (0, 1)n such that, forany game Γ(δ, λ) with δ ≥ δ and λ ≤ λ̄, there exists a sequential equilibriumσ ∗ that satisﬁes |gi (σ ∗ ) − vi | <  for any i.
Proof. See the Appendix.
While the proof in the Appendix provides a general construction of an
equilibrium that approximates a given supportable payoﬀ vector, we here
give its main idea, restricting ourselves to special examples of supportable
payoﬀ vectors. Let us begin with the simplest case, which is to approximate
a payoﬀ vector that is equal to u(a) for some a ∈ E2 such that D w (a) ={1, 2, . . . , n}. Since a ∈ E2 , there exist a pair of associated players {i, j} =AP (a) and better replies {ai , aj } of them such that (2-i)–(2-iii) hold. Since
D w (a) = {1, 2, . . . , n}, supportability implies vk > uk (ŝ(k)) for all k. Thus
the penal code Nash equilibrium for player k, ŝ(k), indeed makes k suﬀer.
To simplify our exposition, we call action ak “cooperation,” action akgiven by (2-ii) “minor-deviation,” and any other action “major-deviation.”
Note that only the associated players {i, j} = AP (a) can minor-deviate.
We construct a strategy proﬁle that uses n + 1 states. The set of statesis {0, 1, . . . , n}. State 0 is regarded as the cooperative state, in which (i)each player k ∈ {i, j} randomizes between cooperation and minor-deviation,
where the probability of cooperation is suﬃciently close to 1, (ii) all otherplayers k ∈/ {i, j} cooperate, and (iii) all players monitor the other players.
On the other hand, in state i ≥ 1, player i is punished; the players play ŝ(i)and no one monitors the others.
We now specify the rule that governs the transition of states. The initialstate is 0 (cooperative state). If the state is 0 in period t − 1, then period t
is in(i) state k if player k ∈ {1, . . . , n} is the only player who major-deviated,
9

(ii) state k if player k ∈ {i, j} minor-deviated and all other players cooperated, and(iii) state 0 otherwise.
For any k ≥ 1, if the state moves to k because of a unilateral major-deviationof player k (case (i)), then the state remains k for all subsequent periods.
On the other hand, if the state moves to k because of a unilateral minordeviation of player k ∈ {i, j} (case (ii)), then state remains k for a certain
number of periods and then moves back to 0. The length of the k-state
periods is set so that the gain from the minor-deviation is exactly equal to
the loss from playing ŝ(k). Since uk (a) > uk (ŝ(k)), the appropriate length of
the k-state periods can be found if the players are suﬃciently patient. Since
the appropriate length is not necessarily an integer, the public randomization device is used to make the transition from state k to 0 contingent on
sunspots. Moreover, since when the state moves back to 0 depends only
on sunspots, the state is common knowledge although the players do notmonitor each other during the punishment periods.
This speciﬁcation is suﬃcient to determine what happens on the path.
Since the players cooperate with a probability suﬃciently close to 1, thepath approximates the payoﬀ vector u(a) as long as the observation costs
are suﬃciently small. Note that the above speciﬁcation also determines
the continuation play at oﬀ-the-path histories if the player did not deviate
in terms of monitoring in the previous periods (since then she knows thestate). To deﬁne the equilibrium strategy formally, it remains to specify
how a player behaves after she deviates in terms of monitoring. However,since this speciﬁcation does not aﬀect the following argument, we do notcomplete the speciﬁcation of strategy here.
Let us now examine the incentive to follow the state-dependent play described above. First, for δ suﬃciently close to the unit vector, no player has
an incentive to major-deviate in state 0. This is because uk (a) > uk (ŝ(k))
for all k and once player k major-deviates, the resulting outcome is theperpetual play of ŝ(k). Second, players k ∈ {i, j} are indiﬀerent between
cooperation and minor-deviation because of the way in which the numberof k-state periods is set. Third, in state k ≥ 1, no player has an incentive todeviate in terms of action or monitoring since (i) a stage game Nash equilibrium is played, (ii) the play does not aﬀect the transition of the state, and(iii) no monitoring is required.
The remaining step is to examine the monitoring incentive in state 0.
We start with players k ∈/ {i, j}. Suppose that the state was 0 in period t
and player k ∈/ {i, j} did not monitor at the end of the period. Then,10

in period t + 1, she is uncertain about the state, which is either 0, i, or jdepending on whether i or j (or both) minor-deviated in period t. By (2-iii),
playing ak in period t + 1 is not optimal if the state is either i or j. On theother hand, if player k plays an action other than ak in period t+1, the action
is considered as a major-deviation and triggers a perpetual punishment if
the state is actually 0. Therefore, if λk is suﬃciently small, the gain from
eliminating the uncertainty exceeds the cost of monitoring.
Let us now consider a player k ∈ {i, j}. Without loss of generality, let
k = i. Suppose that the state was 0 in period t and player i did not monitor
at the end of the period, so i is uncertain about the state in period t + 1.
First, consider the case in which player i cooperated in period t. Then thestate in period t + 1 is either j or 0 depending on the action of player j
in period t. Thus, if i cooperates or minor-deviates in period t + 1, thenby (2-ii), the action is suboptimal if the state is j. On the other hand,
if i major-deviates in period t + 1, a perpetual punishment follows if theactual state is 0. Hence, player i suﬀers strictly from the uncertainty and
it is optimal for her to eliminate the uncertainty if her monitoring cost is
suﬃciently small.
Let us now consider the case when player i minor-deviated in period t.
Then the state in period t + 1 is either i or 0; the latter occurs if j also
minor-deviated. Since the latter case occurs with a small probability, thestate in period t + 1 is almost surely i, so by (2-ii), it is suboptimal for i toeither cooperate or minor-deviate in period t + 1. However, if she chooses
an action other than cooperation and minor-deviation in period t + 1, thenit is regarded as a major-deviation if the state in this period is actually 0,
which occurs with a small but positive probability. Thus, player i suﬀers
strictly from the uncertainty, which she is willing to avoid if her monitoring
cost is suﬃciently small.
In this way, we can prove that it is not proﬁtable for players to deviate in terms of monitoring (on the path). This together with the previous
arguments shows that the state-dependent play is an equilibrium when theplayers are patient and monitoring costs are small.
It is less straightforward to approximate other supportable payoﬀ vectors. For example, let us consider a payoﬀ vector that is equal to u(a) forsome a ∈ E1 . By (1-i), only one player has a short-run incentive to deviate
from a. The state-dependent play described above cannot be used since it
requires two players to minor-deviate (to give monitoring incentives to eachof them). Therefore, we consider a diﬀerent type of behavior in this case.
Speciﬁcally, in the cooperative state, the player i such that D(a) = {i}randomizes between cooperation and minor-deviation and does not monitor
11the other players, while all other players cooperate and monitor the others.
The state transition is speciﬁed similarly. Then, all agents j = i have amonitoring incentive in the cooperative state since the future play is either
to cooperate or to punish i and the state transition depends on i’s action.
On the other hand, since the state transition depends only on i’s action, i
can identify the current state even if she does not monitor the other players.
Thus, at equilibrium, the state is common knowledge among the players
although not all players observe the past actions.
The construction of an equilibrium is more complicated if the payoﬀ
vector to be approximated can be generated only by a randomization among
elements of E1 and E2 , or when some players play a dominant action in thecooperative stage. We deal with these cases in the Appendix.
A ﬁnal remark on Proposition 1 is that if the players use sunspots wisely,
many other payoﬀ vectors can be approximated. Let NE ∗ (G) be the set ofNash equilibrium payoﬀ vectors of G. Then it is easily seen that any payoﬀ
vector in the convex hull of V ∗ ∪ NE ∗ (G) can be approximated. Moreover,as we vary the penal code (ŝ(i))ni=1 , we obtain diﬀerent V ∗ and therefore
diﬀerent V ∗ ∪ NE ∗ (G), and all elements of those sets can be approximated.
Thus, if G has a number of Nash equilibria, the set of payoﬀ vectors that
our construction can approximate can be large.8 In the next section, we
demonstrate that the set is indeed large and yields an approximate Folk
Theorem.

5

Application: Approximate Folk Theorem

This section examines three examples and shows that Proposition 1 generates an approximate Nash Folk Theorem in each of the examples. In theseexamples, we consider a penal code in which the same Nash equilibrium isused for all players. Denoting the stage Nash equilibrium by ŝ, we will showthat all eﬃcient payoﬀ vectors that Pareto-dominate u(ŝ) are supportablewith respect to ŝ. Then, Proposition 1 proves that all those payoﬀ vectors
are approximated by equilibria if the monitoring costs are suﬃciently small.
Since sunspots are available, all interior payoﬀ vectors that Pareto-dominateu(ŝ) are also attainable as equilibria. In this way, we obtain an approximate
Nash Folk Theorem. A minimax version of approximate Folk Theorem may
also hold if, in addition, ui (ŝ) is the minimax value of player i for all i.
We indeed obtain an approximate minimax Folk Theorem in the example of8
Furthermore, there may be payoﬀ vectors that can be supported by other strategy
proﬁles than the ones we consider in this paper.

12

linear partnership examined below.

5.1

A Variant of Prisoners’ Dilemma

We begin our discussion with the following standard prisoners’ dilemma.
C
D

C
1, 1
2, −1

D
−1, 2
0, 0

If this is the stage game, then our construction of strategy proﬁle cannot
support cooperation. Indeed, since the Nash equilibrium is unique, the only
possible penal code is ŝ(1) = ŝ(2) = (D, D). Then, (C, C) violates (1-i) and(2-ii). Condition (2-ii) is simply impossible to satisfy if there are only two
actions. Similarly, (C, D) and (D, C) violate (1-ii) and (2-i). Thus E1 andE2 are empty for the prisoners’ dilemma.
On the other hand, the result changes considerably if the stage gamehas a slightly larger action set. For prisoners’ dilemma, our construction
can easily support cooperation if each player has another action. This is
illustrated by the following stage game.
C
D
E

C
1, 1
2, −1
−1, −1

D
−1, 2
0, 0
−1, −1E−1, −1−1, −10, 0This is a simpliﬁed version of the bilateral trade game with moral hazard in
Bhaskar and van Damme (2002). This game has two pure Nash equilibria,(D, D) and (E, E), as well as a mixed Nash equilibrium, s, where each player
randomizes between D and E with equal probabilities. Clearly, C is strictly
dominated, and (C, C) Pareto-dominates all Nash equilibria.
We present an approximate Nash Folk Theorem for the expanded prisoners’ dilemma. We set ŝ(1) = ŝ(2) = (E, E) as a penal code. Then, sinceneither C nor D is a best response to E, we have (C, C) ∈ E2 . Furthermore, since D is a unique best response to C, we also have (C, D) ∈ E1 and(D, C) ∈ E1 . Since no player has a dominant action, Condition (s-iv) of
supportability holds trivially. Since (C, C), (D, C), and (C, D) are the only
eﬃcient action proﬁles, any eﬃcient payoﬀ vector that Pareto-dominates(0, 0) is supportable and therefore approximated by an equilibrium. Thus
an approximate Nash Folk Theorem holds.
However, this is not an approximate minimax Folk Theorem since theminimax value in this game is −1/2 for each player. The fact that the13minimax value is attained by the mixed Nash equilibrium s does not enable
us to prove a minimax Folk Theorem. Indeed, if we set ŝ(1) = ŝ(2) = s
as a penal code, then E1 and E2 are both empty, and so is the set of
supportable payoﬀ vectors with respect to the penal code. This argument
also demonstrates that the set of supportable payoﬀ vectors depends on the
penal code.

5.2

Linear Partnership Games

This subsection further explores the idea that our construction of strategy
proﬁle can support cooperation if the action space is suﬃciently rich. We
consider a class of linear partnership games where each game is parameterized by the richness of action set. The assumption of linearity plays animportant expositional role; it ensures that the set of feasible payoﬀ vectors,
V , does not depend on the richness of action set. At the cost of complication,
the idea can be extended to more general games of partnership.
The linear n-player partnership game is deﬁned as follows. There aren players, and each player has m+1 actions where m ≥ 2. The set of actions. . . , (m − 1)/m, 1}. The production function
for each player is Ai = {0, 1/m, 
is linear and given by f (a) = ni=1 ai . Let ci (ai ) = αai be the cost that
player i has to pay if she chooses ai . The output is divided
 equally among
the players. Player i’s payoﬀs are therefore ui (a) = (1/n) nk=1 ak −αai . We
impose the non-triviality assumption that 1/n < α < 1. This implies thatai = 0 is a dominant action for each player, while (1, 1, . . . , 1) is the eﬃcientaction proﬁle. Hence, this game is also a variant of prisoners’ dilemma.
Note also that any ai ≥ 1/m is strictly dominated by ai − (1/m). The
minimax value for each player is 0, which is attained in the unique Nashequilibrium s0 = (0, . . . , 0), independently of m.
Since the partnership game has a unique Nash equilibrium, the only
possible penal code is ŝ(i) = s0 for all i. With respect to the penal code,
E1 = ∅ by (1-ii). This implies that (s-iv) holds trivially. On the other hand,
E2 is characterized as follows.
Proposition 2 E2 = {a ∈ A : ∃i, j = i s.t. min{ai , aj } ≥ 2/m}.
Proof. Let a ∈ A be such that min{ai , aj } ≥ 2/m for some i and j = i.
Then, {i, j} ⊆ D(a), and for all k ∈ {i, j}, 1/m ∈ Bk (a) \ {0}. For allk ∈/ {i, j} ∪ SD(a), ak ≥ 1/m and hence ak ∈/ BR k (s0 ). Therefore (2-i)–(2-iii) hold and a ∈ E2 .
To prove the converse, let a ∈ E2 . Then there exist associated players iand j = i for whom there exist ai ∈ Bi (a) \ {0} and aj ∈ Bj (a) \ {0}. Hence14min{ai , aj } ≥ 2/m.

Q.E.D.

Let V̄ be the boundary of V , and VIR ⊆ V be the set of feasible payoﬀ
vectors that are strictly individually rational, i.e., VIR = {v ∈ V : vi >0 for all i}. Since payoﬀ functions are linear, V , V̄ , and VIR are all independent of m. The following result proves that all feasible, boundary,and strictly individually rational payoﬀ vectors are supportable if m is sufﬁciently large. In view of Proposition 1 and the availability of sunspots, theresult implies that if m is large, any v ∈ VIR can be approximated by anequilibrium. Therefore, we have an approximate minimax Folk Theorem.
Proposition 3 If m ≥ 2/(nα − 1), any v ∈ VIR ∩ V̄ is supportable.
Proof. Assume m ≥ 2/(nα − 1) and let v ∈ VIR ∩ V̄ . Then there exists
a probability
 distribution on A, (ρ(a))a∈A , such that v = a∈A ρ(a)u(a).
Let ρ∗i = a∈A ρ(a)ai , which is the expected action level of player i. Sincev ∈ VIR ∩ V̄ , there exists a player i such that ρ∗i = 1 (otherwise, a Pareto
improvement can be achieved by multiplying everyone’s expected actionlevel by some β > 1). Without loss of generality, we assume ρ∗1 = 1. If∗k≥2 ρk < 2/m, then the expected utility of player 1 isv1 = (1/n)

nρ∗i − α < (1/n)(1 + 2/m) − α ≤ 0,

i=1

where the last inequality follows from m ≥ 2/(nα − 1). The inequalities
imply
that v is not strictly individually rational, a contradiction. Thus∗ρk≥2 k ≥ 2/m.
We have to show that there exists a probability distribution over E2
that generates payoﬀ vector v. Since payoﬀ functions are linear, it suﬃces
to prove that the convex hull of E2 includes ρ∗ = (ρ∗i )ni=1 . To prove this, letβ H and β L be deﬁned by
β H = 1/(max ρ∗k ) ≥ 1,k≥2
Lρ∗k ≤ 1,β = (2/m)/

(2)
(3)

k≥2

where the inequality in (3) is proved in the previous paragraph. Let ρH , ρL ∈L
H
H ∗[0, 1]n be deﬁned by ρH
1 = ρ1 = 1, and for all k ≥ 2, ρk = β ρk and
L
L
∗
∗
H
L
ρk = β ρk . Clearly, ρ is a convex combination of ρ and ρ . By (2), ρH
has at least two components of 1. Thus, it follows easily from Proposition 2
15

that ρH is in the convex hull of E2 . We now prove that ρL is also in theconvex hull of E2 . For each k ≥ 2, let ak ∈ A be the action proﬁle deﬁned by/ {1, k}. By Proposition 2, ak ∈ E2
ak1 = 1, akk = 2/m, and akj = 0 for all j ∈for each k ≥ 2. By (3), ρL 
is a convex combination of (ak )k≥2 where thek∗weight assigned to a is ρk /( j≥2 ρ∗j ).
Q.E.D.

5.3

Games with Utility Burning

The objective of this subsection is to demonstrate that an approximate Nash
Folk Theorem holds if the players are able to “burn” small amounts of theirown payoﬀs.
Let a stage game G = {n, A, (ui )ni=1 } be given. For a given number z > 0,
we deﬁne the game with z-utility burning as Gz = {n, A , (ui )ni=1 } whereAi = Ai × {0, 1, 2} for each i, and for any action proﬁle a = (ai , ki )ni=1 ∈ A ,ui (a ) = ui (a) − ki z.
In this game, each player chooses an action and at the same time chooses
the amount of her payoﬀs to burn. It is assumed that a player can decrease
her payoﬀs without aﬀecting the others’. We also assume that if a player
monitors the other players, she learns the amounts of payoﬀs that the otherplayers burnt.
It is easily seen that none of the Nash equilibria in Gz involves utility
burning. Note also that G and Gz have the same Pareto frontier. Moreover,
if we deﬁne V z = co{u (a ) : a = (ai , 2)ni=1 }, then V z converges to V asz → 0. Let us ﬁx a penal code (in Gz ), (ŝ (i))ni=1 , arbitrarily and consider
an action proﬁle a ∈ A of the form a = (ai , 2)ni=1 . Then for all i, we/
have (ai , 1) ∈ Bi (a ) and for all j ∈ {1, . . . , n} and all k ∈ {1, 2}, (ai , k) ∈BR i (ŝ (j)), which implies a ∈ E2 . Therefore, any v ∈ V z that Paretodominates (ui (ŝ (i)))ni=1 is supportable.9 Hence, if the unit of utility burning,z, is small, an approximate Nash Folk Theorem holds.10 Note that this result
holds for any game G.

6

Concluding Remarks

This section discusses possible extensions of our model.
9

Since v is represented by a convex combination of elements of E2 , Conditions (s-ii)
and (s-iv) hold trivially.
10
However, to sustain cooperation, the observation costs have to be small in comparison
with the already small level of utility burning.

16

6.1

Fixed Observation Costs

An important assumption in our characterization of equilibrium payoﬀ vectors and approximate Folk Theorems is that the observation costs are suﬃciently small. The results say nothing if the levels of observation costs are
ﬁxed. A simple, alternative framework in which we can deal with ﬁxed levelsof observation costs is one in which monitoring at the end of a period gives
information about not only the present period but all the previous periods.
This framework is a variation of that in Miyahara (2002), who examines
the case when at least the last two periods can be observed. However,Miyahara’s eﬃciency result for repeated prisoners’ dilemma also requires
small observation costs.
When all previous periods are observable (with costs), we can use
Miyahara’s construction of strategy proﬁle to support a large set of payoﬀ vectors for ﬁxed observation costs. To see this, assume that there exists
an action proﬁle â that attains a given target payoﬀ vector. Let us also
assume the existence of an action proﬁle a in which there exist at least two
potential deviators, i.e., |D(a)| ≥ 2. As in our construction, select two players {i, j} ⊆ D(a) and call them the associated players. Then consider thefollowing strategy proﬁle for a given T ∈ {2, 3, . . .}: (i) the players play âin the ﬁrst T − 1 periods without monitoring each other; (ii) in period T ,the players play a, except that the associated players mix between a andtheir minor-deviations, and all players monitor; (iii) the play in the next T
periods is either another sequence of (i) and (ii), or a repetition of a penal
code Nash equilibrium, depending on the presence of a deviator in the ﬁrst
T periods, and so on.
Under the strategy proﬁle, the players do not monitor the other players
in â state. But they have no incentive to deviate in terms of actions sincedeviations are detected at least T periods later and regarded as majordeviations. The incentive for monitoring in period T is guaranteed if foreach player k, âk is not a best response to the penal code Nash equilibria
designed for the associated players. Under this condition, the above strategy
proﬁle constitutes an equilibrium and approximates the target payoﬀ vector
for a given vector of observation costs if T is suﬃciently large and discountfactors are close to 1.11
11
In the strategy proﬁle, the action proﬁle is the same for the ﬁrst T − 1 periods.
Alternatively, we could consider a strategy proﬁle in which the action proﬁle during these
periods is time-dependent. The advantage of using the larger class of strategy proﬁles isthat the corresponding condition on the relation between “â” and the penal code can be
weakened considerably.

17This construction for multi-period observation technology can sustain
cooperation even for stage games whose action sets are small. Indeed, thestage game examined in Miyahara (2002) is the standard two-action prisoners’ dilemma and he obtains an eﬃciency result for the game.
In our future research, we will elaborate the strategy proﬁle (along theline mentioned in footnote 11) to obtain a characterization of payoﬀ vectorsthat can be approximated by equilibria and derive conditions on stage games
for which a Folk Theorem with ﬁxed observation costs holds.

6.2

Timing of Receiving Payoﬀs

We have assumed that the players do not receive payoﬀs in each period
but they receive the total payoﬀs when the game ends. We need theseassumptions in order to keep consistency with the assumption that, without
paying monitoring costs, a player receives no information about the others’
actions. If payoﬀs are received in every period, then they generally provide
players with some information about the other players’ actions.
However, we can imagine a framework in which payoﬀs are received inevery period but monitoring remains important because realized payoﬀs are
only a noisy signal of the other players’ actions. For example, let a stage
game G = {n, A, (ui )ni=1 } be given. Suppose that at the end of each period,
player i receives payoﬀs of ui (a) + i if a ∈ A is played in that period, wherei is a noise term which follows a normal distribution with mean 0. Assume
also that the noise terms are independent across the players.
In this formulation, the realized payoﬀ is not a sure indicator of theother players’ actions while it is informative. If we ignore the issue of costly
observation, the standard model of repeated games with imperfect private
monitoring (like Sekiguchi (1997)) falls into this category if the realized
payoﬀ is a suﬃcient statistic of the privately observed signal about the otherplayers’ actions.
Even in this framework, we can use the state-dependent strategy proﬁleconsidered in Section 4. Under this strategy proﬁle, players monitor eachother and do not use the information contained in the realized payoﬀs. The
monitoring incentive is weaker under this strategy proﬁle since realized payoﬀs also give players information about the state. However, players who do
not pay observation costs are not able to determine the state with certainty.
Therefore, if the likelihood ratio of any pair of action proﬁles that generate
the same level of payoﬀs is bounded away from zero, then the players dohave an incentive to pay observation costs, given any payoﬀ realization, if

18the observation costs are suﬃciently small.12 Hence the basic idea of ourconstruction also applies to the case in which payoﬀs are received in eachperiod.
This observation is important because it suggests a possibility that costly
observation is one comprehensive solution to the private monitoring problem. The literature of repeated games with imperfect private monitoringhas shown diﬃculty in constructing a cooperative/eﬃcient equilibrium, andthe existing positive results (reported in the papers cited in footnote 2) arelimited to simple speciﬁc games, e.g., repeated prisoners’ dilemma and its
variations.13 It is still unknown whether a Folk Theorem or an eﬃciency
result holds in general settings with private monitoring. In contrast, ourresult and the above discussions show that an approximate Folk Theorem
does hold in general environments if the players have an ability to observe
the other players’ actions directly and the observation costs are suﬃciently
small.
The literature also identiﬁes communication among the players as a driving force to cooperation in general environments with private monitoring(Compte (1998), Kandori and Matsushima (1998), and Aoyagi (2002)).14
Thus our analysis may as well be seen as demonstrating that costly observation is a convenient substitute for communication. This interpretation
has a strong implication on antitrust laws since they control communication
among ﬁrms in the belief that communication is a major tool that facilitatescartels.

6.3

Partial Monitoring

The monitoring activity that we have considered has a binary aspect in thateach player has to decide whether to obtain complete information about theaction proﬁle of the other players in the period or to obtain no information.
A more realistic formulation is that each player can choose to what
extent she observes the other players’ actions, and the more she spends for
12

Precisely speaking, the likelihood ratio is not bounded away from zero when the noise
terms are normally distributed. However, the likelihood ratio is close to zero only at
the tails. Hence, we conjecture that there exists a cooperative equilibrium in which theplayers monitor each other unless the realized payoﬀs take extreme values. Moreover, thelikelihood ratio condition can be satisﬁed for other speciﬁcations of the noise term.
13
Mailath and Morris (2002) consider more general stage games, but they assume thatprivate signals are correlated across the players. Amarante (2002) also conducts a general
analysis. For some negative results, see Matsushima (1991) and Compte (2002).
14
See also Ben-Porath and Kahneman (1996) for the role of communication in related
environments with private monitoring.

19

monitoring, the more information she obtains. For example, suppose that
λi is the unit monitoring cost and player i incurs the cost of mλi if shemonitors m of the other players. This alternative framework is relevant in
the price-setting oligopoly if the goods are sold at each ﬁrm’s own outlet.
In this framework, each ﬁrm decides the set of ﬁrms to monitor and thetotal observation cost depends on the number of ﬁrms to monitor. Such
partial monitoring is relevant even in the case of duopoly if the ﬁrms operate
in multiple markets. In this case, each ﬁrm decides the set of markets tomonitor, and the total observation cost depends on the number of markets tomonitor. Thus the price-setting oligopoly is a prominent example of partial
monitoring since the ﬁrms often compete in a large number of dimensions.
As Stigler (1964) concluded, collusion is hard to implement since it requires
an ability to detect any possible secret price-cuts in any market.
In general, partial monitoring is relevant whenever the action proﬁle ofn − 1 players is multi-dimensional (this is trivially the case when n ≥ 3)
and a player can choose to observe only a subset of the coordinates in the
proﬁle of the other players’ actions. A basic diﬃculty in analyzing the casewhen partial monitoring is feasible is that the players have an incentive toeconomize on observation expenses by not monitoring some of the players(or markets). In the strategy proﬁle used in our proof, some of the players
do not randomize in the cooperative state, but this is not a problem in the
proof since these players are also monitored by the other players. Under thebinary nature of our monitoring technology, any player who has an incentive
to monitor at least one of the other players has no choice but to monitor
all other players. However, if partial monitoring is feasible, players would
monitor only those who randomize, but then deviations of non-randomizing
players are not detected. Therefore, if partial monitoring is feasible, thecooperative equilibria that we constructed are upset.
Nevertheless, our construction can be modiﬁed to deal with partial monitoring if the payoﬀ vector to be approximated can be generated by action
proﬁles in which all players have proper minor-deviations. Formally, let a
stage game G and a penal code (ŝ(k))nk=1 be given. Let En ⊆ A be the setof all a ∈ A such that(n-i) D(a) = {1, 2, . . . , n},(n-ii) for each player i, there exists ai ∈ Bi (a) such that{ai , ai } ∩ ∪nk=1 BR i (ŝ(k)) = ∅.

20

It is then not very diﬃcult to see that for all a ∈ En , if ui (a) > ui (ŝ(i))
for all i, then u(a) can be approximated by an equilibrium, in which all
players randomize between ai and ai in the cooperative state. Thus, any
convex combination of such u(a)’s can be also approximated. We have seenin Subsection 5.2 that the ﬁner the action set is, the more payoﬀ vectors
are approximated using action proﬁles where all players have short-run incentives to deviate. Therefore, our result extends to the case of partial
monitoring when the underlying strategic situation involves suﬃciently ﬁne
action sets.
This idea also applies to the case of duopoly with multiple markets. If a
price proﬁle is such that each ﬁrm has a short-run incentive to deviate in every market, then the price proﬁle can be supported by an equilibrium wherethe ﬁrms randomize between cooperation and minor-deviation in every market. Again, if the price space is suﬃciently ﬁne, many levels of collusion canbe sustained, so an approximate Folk Theorem will be obtained.

6.4

Finite Repetition

Assuming that the horizon is ﬁnite has both an advantage and a disadvantage. An advantage is that the ﬁnite horizon makes it easier to interpretthe assumption that the payoﬀs are received in total at the end of the repeated game. A disadvantage is that the ﬁnite horizon makes cooperation
unsustainable if the stage game has a unique equilibrium.
On the other hand, it might be possible to obtain an approximate Folk
Theorem under a ﬁnite horizon if the stage game has multiple equilibrium
payoﬀs for each player as in Benoit and Krishna (1985). We conjecture that
if the number of periods is suﬃciently large, an action proﬁle that Paretodominates a stage-game equilibrium can be sustained in early periods. Thisis another topic of our future research.

21

Appendix: Proof of Proposition 1
Let v ∈ V ∗ and  > 0. Since v is supportable, there exists a probability
distribution on E, denoted (ρ(a))a∈E , such that (s-i)–(s-iv) hold. Let us
deﬁne E1∗ (i) = {a ∈ E1 : ρ(a) > 0 and D(a) = {i}}, E1∗ = ∪i E1∗ (i), E2∗ ={a ∈ E2 : ρ(a) > 0}, and E ∗ = E1∗ ∪ E2∗ . Thus, E ∗ is the support of ρ.
We can choose a suﬃciently small  > 0 so that for all players i, if there
exists a ∈ E ∗ such that either [a ∈ E1 and D(a) = {i}] or [a ∈ E2 andi ∈ D w (a)], then vi −  > ui (ŝ(i)). This is possible since v is supportable.
Let SD ∗ = {i : i ∈ SD(a) ∀a ∈ E ∗ } be the set of players i such thatfor all a, â ∈ E ∗ , ai = âi and it is the strictly dominant action for i.
For each i and a ∈ E1∗ (i), ﬁx ai ∈ Bi (a) such that (1-iii) and (s-iv) hold.
Similarly, for each a ∈ E2∗ , we ﬁx ai ∈ Bi (a) and aj ∈ Bj (a) that satisfy(2-ii), where {i, j} = AP (a).
Since G is a ﬁnite game, there exists ζ̄ ∈ (0, 1) such that for all a ∈ E1∗ ,(1-iii) holds with ζ = ζ̄, and for all a ∈ E2 and all k ∈/ D w (a),{ak } = BR k ((1 − ζ̄)ai + ζ̄ai , (1 − ζ̄)aj + ζ̄aj , a−i−j ),(4)where {i, j} = AP (a). Note that these conditions also hold when ζ̄ isreplaced with any ζ ∈ [0, ζ̄).
Let η ∈ [0, ζ̄], λi ≥ 0, and δi ∈ (0, 1) for all i. For any a ∈ E ∗ and any
k ∈ AP (a), we deﬁne a mixed action aηk asaηk = (1 − η)ak + ηak ,with the obvious interpretation that aηk assigns probability 1 − η to ak andthe remaining probability to ak . We now deﬁne the following vectors andnumbers: V 0 ∈ Rn , V 0 (a) ∈ Rn , V k (a) ∈ Rn , and ν k (a) ∈ (0, 1) for anya ∈ E ∗ and any k ∈ AP (a). We deﬁne them as a solution of the following
system:
V0 =ρ(a)V 0 (a);
(5)
a∈E ∗
0
Vi (a) = (1 − δi )ui (a) + δi Vi0= (1 − δi )ui (ai , a−i ) + δi Vii (a)for any i and any a ∈ E1∗ (i);
Vk0 (a) = (1 − δk ) uk (aηi , a−i ) − λk + δk (1 − η)Vk0 + ηVki (a)

22

(6)
(7)

(8)

for any i, any a ∈ E1∗ (i), and any k = i;
V i (a) = [1 − ν i (a)]u(ŝ(i)) + ν i (a)V 0
for any i and any a ∈ E1∗ (i);Vi0 (a) = (1 − δi ) ui (aηj , a−j ) − λi + δi (1 − η)Vi0 + ηVij (a)= (1 − δi ) ui (ai , aηj , a−i−j ) − λi + δi (1 − η)Vii (a) + ηVi0

(9)

(10)
(11)

and




Vj0 (a) = (1 − δj ) uj (aηi , a−i ) − λj + δj (1 − η)Vj0 + ηVji (a)= (1 − δj ) uj (aj , aηi , a−i−j ) − λj + δj (1 − η)Vjj (a) + ηVj0

(13)

for any a ∈ E2∗ and the associated players {i, j} = AP (a);
Vk0 (a) = (1 − δk ) uk (aηi , aηj , a−i−j ) − λk




+ δk (1 − η)2 + η 2 Vk0 + η(1 − η) Vki (a) + Vkj (a)

(14)

(12)

/ AP (a) ∪ SD ∗ , and {i, j} = AP (a);for any a ∈ E2∗ , any k ∈Vk0 (a) = (1 − δk )uk (aηi , aηj , a−i−j )




+ δk (1 − η)2 + η 2 Vk0 + η(1 − η) Vki (a) + Vkj (a)(15)

for any a ∈ E2∗ , any k ∈ SD ∗ (note that AP (a) ∩ SD ∗ = ∅ by (2-i)), and{i, j} = AP (a); andV k (a) = [1 − ν k (a)]u(ŝ(k)) + ν k (a)V 0(16)

for any a ∈ E2∗ and any k ∈ AP (a).
Regarding system (5)–(16), we prove the following lemma.
Lemma 1 There exist η̂ ∈ (0, ζ̄], λ̂ > 0, κ̂ > 0, and δ̂ ∈ (0, 1) such that(i) System (5)–(16) has a solution if η ≤ η̂, λi ≤ λ̂, and δi ≥ δ̂ for any i.
(ii) The solution satisﬁes|Vi0 − vi | < (17)

1 − ν k (a)> κ̂1 − δk(18)

for any i, andfor any a ∈ E ∗ and any k ∈ AP (a).
23

Proof. We ﬁrst examine system (5)–(16) when η = λi = 0 for any i. By(5), (6), (8), (10), (12), (14), and (15), any solution satisﬁes
Vi0 = vi

(19)

Vi0 (a) = (1 − δi )ui (a) + δi vi
for any a ∈ E ∗ and any i. Therefore, (6), (7), and (9) reduce to(1 − δi ) ui (ai , a−i ) − ui (a) = δi (1 − ν i (a)) vi − ui (ŝ(i))(20)

for any i and a ∈ E1∗ (i). Since v is supportable, vi > ui (ŝ(i)). Sinceai ∈ Bi (a), (20) has a unique solution ν i (a) ∈ (0, 1) if δi is suﬃciently close
to 1. By (9) and (19), this solution uniquely determines V i (a). Furthermore,(20) yields
ui (ai , a−i ) − ui (a)1 − ν i (a).
(21)>
1 − δivi − ui (ŝ(i))
Similarly, for any a ∈ E2∗ , (10)–(13) and (16) reduce to(1 − δk ) uk (ak , a−k ) − uk (a) = δk (1 − ν k (a)) vk − uk (ŝ(k))(22)

for all k ∈ {i, j} = AP (a). Since {i, j} ⊆ D(a) and v is supportable,
vk > uk (ŝ(k)) for all k ∈ {i, j}. Since ak ∈ Bk (a) for all k ∈ {i, j}, (22) has
a unique solution (ν i (a), ν j (a)) ∈ (0, 1)2 if δi and δj are both suﬃciently close
to 1. By (16), the solution uniquely determines V i (a) and V j (a). Moreover,(22) yields
uk (ak , a−k ) − uk (a)1 − ν k (a)(23)>
1 − δkvk − uk (ŝ(k))
for all k ∈ AP (a).
Hence, if η = λi = 0 for all i, then there exists δ̂ ∈ (0, 1) such that if
δi ≥ δ̂ for all i, then system (5)–(16) has a unique solution satisfying (17).
Moreover, if we chooseκ̂ = (1/2) min∗a∈Ek∈AP (a) u (a , akk−k ) − uk (a)vk − uk (ŝ(k))



> 0,

then (21) and (23) imply that (18) holds for all a ∈ E ∗ and all k ∈ AP (a).
By the standard continuity argument, there exist η̂ ∈ (0, ζ̄], λ̂ > 0, andδ̂ ∈ (0, 1) such that if η ≤ η̂, λi ≤ λ̂, and δi ≥ δ̂ for all i, then system(5)–(16) has a nearby solution satisfying (17) and (18).
Q.E.D.

24

For any player k, if BR k (ŝ(i)) = Ak for some i, then let
pk = min uk (ŝ(i)) − uk (ak , ŝ−k (i)) :/ BR k (ŝ(i)) > 0.
i ∈ {1, . . . , n} and ak ∈That is, any player k who plays a suboptimal action against a penal code
Nash equilibrium loses at least pk in terms of per-stage payoﬀs.
For any player k, if k ∈/ D(a) for some a ∈ E1∗ , then let
rk = min uk (a) − uk (âk , a−k ) :a ∈ E1∗ , k ∈/ D(a), and âk ∈/ BR k (a) > 0.

This means that if player k such that k ∈/ D(a) for some a ∈ E1∗ plays asuboptimal action against a−k , then she loses at least rk in terms of per-stage
payoﬀs.
For any player k, if k ∈/ (D w (a) ∪ SD(a)) for some a ∈ E2∗ , then let
qk = min uk (a) − uk (âk , a−k ) :/ (D w (a) ∪ SD(a)), and âk = ak > 0.
a ∈ E2∗ , k ∈Thus, if player k does not play ak against a−k , then she loses at least qk interms of per-stage payoﬀs.
Let ρ = mina∈E ∗ ρ(a) and ∆i = maxa,a ∈A (ui (a) − ui (a )). We thenchoose η̄ ∈ (0, η̂], λ̄ = (λ̄i )ni=1 ∈ (0, λ̂]n , and δ = (δ i )ni=1 ∈ [δ̂, 1)n that satisfy
the following inequalities:(24)(1 − δ i + 2η̄)(∆i + λ̄i ) ≤ δ i (1 − η̄)2 vi −  − ui (ŝ(i))
for any i such that vi −  > ui (ŝ(i));λ̄i ≤ δ i ρκ̂(η̄/2)(1 − η̄)pi(25)

for any i ∈/ SD ∗ such that BR i (ŝ(k)) = Ai for some k;
(1 − δ i )λ̄i ≤ δ i ρκ̂(η̄/2) −(1 − δ i + η̄)(∆i + λ̄i ) + δ i vi −  − ui (ŝ(i)) (26)for any i such that i ∈ AP (a) for some a ∈ E2∗ ;λ̄i ≤ δ i ρκ̂(1 − η̄) (1 − η̄)ri − η̄∆i(27)

for any i such that i ∈/ D(a) for some a ∈ E1∗ ; and
λ̄i ≤ δ i ρκ̂(1 − η̄)2 (1 − η̄)2 qi − [1 − (1 − η̄)2 ]∆i

(28)

25

for any i such that i ∈/ (D w (a) ∪ SD(a)) for some a ∈ E2∗ .
Let us consider Γ(δ, λ) with δ ≥ δ and λ ≤ λ̄. Fix η ∈ [η̄/2, η̄] andconsider the system (5)–(16) associated with η, λ, and δ. By Lemma 1, thesystem has a solution satisfying (17) and (18).
We now construct an equilibrium of Γ(δ, λ) that approximates v. We
start with describing the play on the path. The equilibrium play in each period depends on the “state” of that period. The set of states is {0, 1, . . . , n}.
State 0 is called the “cooperative state,” while states i ≥ 1 are called “punishment states.” State i ≥ 1 is the state in which player i is punished.
The play in state 0 is determined by the “substate” of the period, which isdetermined by the sunspot in that period. The set of substates is identiﬁed
with E ∗ , and each substate a ∈ E ∗ is realized with probability ρ(a). In
substate a ∈ E1∗ (i), (aηi , a−i ) is played, while in substate a ∈ E2∗ , aη =(aηi , aηj , a−i−j ) is played where {i, j} = AP (a). In substate a ∈ E1∗ (i), allplayers except for i monitor the other players. In substate a ∈ E2∗ , allplayers not in SD ∗ monitor the other players. This describes the play in thecooperative state. In state i ≥ 1, on the other hand, the players play ŝ(i)and do not monitor the other players.
For future reference, given a-substate, we call action ai “cooperation,”action ai “minor-deviation,” and any other action “major-deviation.” Note
that, according to this terminology, only player i has a minor-deviation in
substate a ∈ E1∗ (i). Likewise, in substate a ∈ E2∗ , only players i and j
associated with a can minor-deviate.
Next, we deﬁne the rule that determines the transition of states. The
initial state is 0 (cooperative). If period t − 1 is in state 0 and substate a ∈E1∗ (i), then period t is in:(i) state i if player i major- or minor-deviated in period t − 1,(ii) state 0 otherwise.
Note that deviations of players j = i are ignored. If period t − 1 is in state 0
and substate a ∈ E2∗ , then period t is in:(i) state k if player k ∈ D w (a) is the only player in D w (a) who majordeviated in period t − 1,(ii) state k if player k ∈ {i, j} = AP (a) is the only player who minordeviated in period t − 1 and all other players in D w (a) cooperated inperiod t − 1,(iii) state 0 otherwise.
26

Note that, if a ∈ E2∗ and the associated players i and j both minor-deviated,then their deviations are ignored and the state remains 0. Any deviation ofplayer k ∈/ D w (a) is also ignored.
If the state changes to k because of player k’s major deviation, then thestate remains k in all subsequent periods. If the state changes to k because of
k’s minor deviation in a-substate, then the state remains k for τ k (a) periods
irrespective of the actions during the periods. The state of the subsequent
period depends on the sunspot at the beginning of the period: with probability ξ k (a), the state remains k for one more period and then moves backto 0; with probability 1 − ξ k (a), the state moves back to 0 immediately. The
numbers τ k (a) ∈ {0, 1, 2, . . .} and ξ k (a) ∈ [0, 1) are determined uniquely byτ k (a)(1 − ξ k (a))δkτ k (a)+1+ ξ k (a)δk= ν k (a),(29)

where ν k (a) is the relevant part of the solution of (5)–(16).
Note that τ k (a) = 0 is possible in the unique solution of (29). If this is
the case, then the state transition after player k’s unilateral minor-deviationis that with probability 1 − ξ k (a), the state remains 0, and with probabilityξ k (a), the state stays in k for one period and then moves back to 0.
A subtle issue that arises when τ k (a) = 0 is that the players seemingly
need two sunspots: one that determines whether the state stays at 0 or moves
to k, and the other that decides, if the state remains 0, which element of
E ∗ is played. However, a single sunspot suﬃces since one can always let asunspot play two roles at the same time.15
The above description speciﬁes only the play on the path. However,each player can follow the description as long as she does not deviate fromthe description in terms of monitoring. To see this, note ﬁrst that if thecurrent period is in a-substate of the cooperative state with a ∈ E1∗ (i), thenall players except for i monitor the other players, and the future state (onthe path) depends only on i’s action (recall that deviations by player j = i
are ignored). Thus the state in the next period is common knowledge eventhough player i does not monitor the other players. Second, if the current
period is in substate a ∈ E2∗ and if SD ∗ = ∅, then all players monitor eachother and the state in the next period is common knowledge. If SD ∗ = ∅,then the future state is common knowledge only among the players outside
SD ∗ . However, this does not cause a problem since each player in SD ∗ plays
15
For example, suppose E ∗ = {a , a } and ρ(a ) = ρ(a ) = 0.5. If τ k (a) = 0 andξ k (a) = 0.5, then after a minor deviation by player k in substate a, the players canarrange the next-period play so that ŝ(k) is played if the sunspot is in [0, 0.5], a if it is in(0.5, 0.75], and a if it is in (0.75, 1].

27

the (strictly) dominant action in all states, including the punishment states.
Thus, the players in SD ∗ can play consistently with the above description
without knowing the state.16 Finally, if the current state is i ≥ 1, then the
future state depends only on sunspots and hence is common knowledge.
Let us deﬁne a strategy proﬁle σ̂ which is consistent with the statedependent play described above. For each i, let Ĥi be the set of all histories
for player i such that i monitored the other players whenever it was prescribed by the state-dependent play. Note that, as long as the players follow
the state-dependent play, any history on the path is in Ĥi . On the other
hand, Ĥi includes other histories as well. It includes histories in which someplayer(s) (including i) deviated in terms of actions, and those in which imonitored the other players when she was not required to. Anyway, at any
history hti ∈ Ĥi , player i knows the state and therefore can follow the statedependent play described above. For i ∈/ SD ∗ , let σ̂i be a strategy that is
consistent with the above state-dependent play at any hti ∈ Ĥi . The behavior at the remaining histories can be arbitrary. For i ∈ SD ∗ , let σ̂i be thestrategy in which i always plays the dominant action and never monitors theother players. Then, σ̂ generates a path consistent with the state-dependentplay.
For σ̂ deﬁned as above, (5)–(16) and (29) imply that(i) V 0 is the expected payoﬀ vector under σ̂,(ii) V 0 (a) is the expected continuation payoﬀ vector at substate a, and(iii) V i (a) is the expected continuation payoﬀ vector if the previous period
is in substate a and player i unilaterally minor-deviates in that period.
We are now ready to prove the following:
Lemma 2 Strategy proﬁle σ̂ is a Nash equilibrium of Γ(δ, λ) and satisﬁes|gi (σ̂) − vi | <  for any i.
Proof. The second part follows directly from (17). Hence, it suﬃces toprove that σ̂ is a Nash equilibrium of Γ(δ, λ).
We ﬁrst show that it is not proﬁtable for any player i to major-deviate in
the cooperative state. To see this, note ﬁrst that player i’s major-deviation
at substate a is not proﬁtable in the short-run term if either a ∈ E1∗ (j) forj = i (by (1-iii) and η ≤ ζ̄) or a ∈ E2∗ and i ∈/ D w (a) (by (4) and η ≤ ζ̄). In
16

It is useful to note that if there exists a player in SD ∗ , then E1∗ = ∅, since (1-i) and(1-ii) cannot hold simultaneously.

28

either case, a major-deviation is not proﬁtable since it yields no gain in the
short run and does not change the future path. In any other case, we havevi − > ui (ŝ(i)). In this case, if i major-deviates unilaterally, then the future
play is the inﬁnite repetition of ŝ(i). While the major-deviation increases
the current period payoﬀ at most by ∆i + λi (note that i can also deviate inmonitoring), the continuation payoﬀ decreases at least by vi −  − ui (ŝ(i)).
By (24),
(1 − δi )(∆i + λi ) ≤ δi vi −  − ui (ŝ(i)) .
Therefore, a major-deviation does not pay.
By (6), (7), and (10)–(13), any player who can minor-deviate given a
cooperative substate is indiﬀerent between cooperation and minor-deviation.
Thus, in the cooperative state, no player has an incentive to deviate in termsof action. It is easy to see that, in state i ≥ 1, no player has an incentive todeviate in terms of action or monitoring since a stage game Nash equilibrium
is played and the future state depends only on sunspots (until the state
moves back to 0). Thus, the proof is complete if we show that no player has
an incentive to deviate in terms of monitoring at any substate a of state 0.
We start with substates in E1∗ .
Substates in E1∗ . Let us examine the monitoring incentive in state 0 when
the substate is a ∈ E1∗ (i) for some i. In the substate, all players except for imonitor the other players. Since the future play depends only on player i’s
action, player i has no incentive to monitor the others.
Consider player j = i. Suppose that the substate was a ∈ E1∗ (i) in
period t and player j cooperated as prescribed by σ̂ but did not monitor theother players. Then, in period t + 1, she is uncertain whether the state is 0
or i, since she does not know whether the action of player i in period t wascooperation or minor-deviation. In what follows, we show that player j has
an incentive to eliminate the uncertainty if the observation cost is suﬃciently
small.
If player i (and the others) cooperated in period t, then the state remains
cooperative in period t + 1. The substate remains a with probability ρ(a) ≥ρ, in which case the other players play (aηi , a−i−j ) again. On the other hand,
if player i minor-deviated in period t, then the other players play ŝ−j (i) in
period t+1 with a positive probability. More precisely, if τ i (a) ≥ 1, ŝ−j (i) is
played with probability 1. If τ i (a) = 0, then ŝ−j (i) is played with probabilityξ i (a) and (aηi , a−i−j ) is played with the remaining probability. (29) tells usthat when τ i (a) = 0, ξ i (a) is given byξ i (a) =1 − ν i (a)> κ̂,
1 − δi29(30)

where the inequality follows from (18).
Hence, if player j did not monitor the others at the end of period t,then in period t + 1, with a probability no less than ρκ̂, she is in a situation
where she believes that the other players play ŝ−j (i) with probability η and(aηi , a−i−j ) with probability 1 − η. In this situation, since the state is either
i or 0 with substate a ∈ E1∗ (i), player j’s action in period t + 1 does notchange the future play. By (1-ii), player j has no action that is a (static) best
response against both ŝ−j (i) and a−j . If she plays an action âj ∈/ BR j (ŝ(i)),
then she loses at least pj in the period if the other players coordinate onŝ−j (i), which occurs with probability η ≥ η̄/2 > 0. On the other hand, if sheplays âj ∈/ BR j (a), then she loses at least rj if the other players coordinate
on a−j , which occurs with probability (1 − η)2 ≥ (1 − η̄)2 > 0.
Thus, by not monitoring the other players in period t, player j saves
λj ≤ λ̄j in the period but suﬀers an expected loss of at leastρκ̂ min (η̄/2)pj , (1 − η̄) (1 − η̄)rj − η̄∆jin period t + 1 and possibly more in the future. By (25) and (27), thedeviation is not proﬁtable.
Substates in E2∗ . We now consider the cooperative state with substatea ∈ E2∗ . In this substate, σ̂ tells all players outside SD ∗ to monitor theother players. Let {i, j} = AP (a). We examine the monitoring incentive ofa given player k in the substate.
Case 1: k ∈ SD ∗ . Under σ̂, player k ∈ SD ∗ plays the dominant action
ak in every period regardless of the state (note that the dominant action
must be played in any penal code Nash equilibrium). Since her play neveraﬀects the future play of the other players, she has no reason to monitor theother players.
Case 2: k ∈/ D w (a) ∪ SD(a). This implies that ak is a unique best
/ AP (a).
response to a−k while it is not the dominant action. Note that k ∈Suppose that in period t, the substate was a and player k cooperated but
did not monitor. If the other players all cooperated or the associated players{i, j} both minor-deviated, then with probability ρ(a) ≥ ρ, the other players
play aη−k again in period t + 1. On the other hand, if either i or j (but notboth) minor-deviated, then ŝ−k (h) is played in period t + 1 where h ∈ {i, j}
is the minor-deviator.
By the same argument as above, if player k did not monitor the otherplayers in period t, then in period t + 1, with a probability no smaller thanρκ̂, player k is in a situation where she believes that the other players play30

aη−k with probability (1 − η)2 + η 2 , ŝ−k (i) with probability η(1 − η), andŝ−k (j) with probability η(1 − η).
In this situation, since the state is either i, j, or 0 with substate a,player k’s action does not aﬀect the future play. If player k plays ak , thenby (2-iii), she loses at least pk in the period if either the other players
coordinate on ŝ−k (i) or they coordinate on ŝ−k (j), each of which occurs
with probability η(1 − η) ≥ (η̄/2)(1 − η̄). On the other hand, if she plays
any other action, then she loses at least qk if the other players coordinate
on a−k , which occurs with probability [(1 − η)2 + η 2 ](1 − η)2 ≥ (1 − η̄)4 .
Therefore, by not observing the other players in period t, player k saves
λk ≤ λ̄k but suﬀers an expected loss of at leastρκ̂ min (η̄/2)(1 − η̄)pk , (1 − η̄)2 (1 − η̄)2 qk − [1 − (1 − η̄)2 ]∆kin period t + 1 (in terms of stage-game payoﬀs) and possibly more in the
future. Therefore, by (25) and (28), the deviation is not proﬁtable.
Case 3: k ∈ D w (a)\{i, j}. Suppose that in period t, the state was 0 with
substate a, and player k ∈ D w (a)\{i, j} cooperated but did not monitor theother players. Then by a similar argument, it follows that in period t + 1,
with a probability no smaller than ρκ̂, player k is in a situation where she
believes that the other players play aη−k with probability (1−η)2 +η 2 , ŝ−k (i)with probability η(1 − η), and ŝ−k (j) with probability η(1 − η).
We ﬁrst show that, under the uncertainty, it is suboptimal for player k
to play any action ak = ak . Indeed, she gains by choosing ak and monitoring
the other players. To see this, note ﬁrst that playing ak and monitoring theother players decreases the current payoﬀ at most by ∆k + λk . On the other
hand, it does not decrease the continuation payoﬀ if the state is either i or j.
If the state is 0 with substate a, which occurs with probability 1 − 2η(1 − η),then playing ak and monitoring the other players increases the continuation
payoﬀ (from period t + 2 on) at least by[1 − 2η(1 − η)]Vk0 + η(1 − η)[Vki (a) + Vkj (a)] − uk (ŝ(k))> [vk −  − uk (ŝ(k))] − 2η(1 − η)(∆k + λk ).

Therefore, by (24), the overall payoﬀ evaluated at t + 1 increases by playing
ak and monitoring the other players.
However, (2-iii) implies that playing ak in period t + 1 causes a loss ofat least pk to player k in the period if the state is either i or j, each ofwhich occurs with probability η(1 − η). Thus, by not monitoring the otherplayers in period t, player k saves λk ≤ λ̄k but suﬀers an expected loss of at31

least ρκ̂(η̄/2)(1 − η̄)pk in period t + 1 (in terms of stage game payoﬀs) andpossibly more in the future. Therefore, by (25), not monitoring in period t
is not optimal.
Case 4: k ∈ {i, j}. Without loss of generality, let k = i. We ﬁrst
consider the case in which player i cooperated but did not monitor theother players in period t. Then, again, with a probability no less than ρκ̂,
player i in period t + 1 is in a situation where she believes that the otherplayers play aη−i with probability 1 − η and ŝ−i (j) with probability η. Usinga similar argument and (24), it can be shown that, under the uncertainty, it
is suboptimal for i to play any ai ∈/ {ai , ai }. However, by (2-ii), playing ai or
ai causes a loss of at least pi in the period if the other players coordinate onŝ−i (j). Therefore, by (25), not monitoring the other players is suboptimal.
We also have to consider the case in which player i minor-deviated andthen did not monitor the other players in period t. Then, in period t + 1,
player i is uncertain whether the state is i or 0; the latter occurs if j also
minor-deviated in period t. Then, by a similar argument, it follows that witha probability no smaller than ρκ̂, player i in period t + 1 is in a situation
where she believes that the other players play ŝ−i (i) with probability 1 − ηand aη−i with probability η. Under the uncertainty, if player i chooses anaction ai ∈ {ai , ai }, then by (2-ii), it causes a loss of at least pi in the period
if the other players coordinate on ŝ−i (i). On the other hand, if she plays
any ai ∈/ {ai , ai }, it is regarded as a major-deviation if the other players
coordinate on (aηj , a−j−i ), which occurs with probability η.
Thus, if player i does not monitor the other players at period t, shesaves λi ≤ λ̄i in the period but the continuation payoﬀ evaluated at period t
decreases at least by the minimum of the following values:
δi ρκ̂(1 − η)(1 − δi )pi ,
δi ρκ̂η −(1 − δi )(∆i + λi ) + δi ηVij (a) + (1 − η)Vi0 − ui (ŝ(i)) .
The second value is greater than the right-hand side of (26). Therefore, by(25) and (26), not monitoring at period t is suboptimal.
Case 5: k ∈ SD(a) \ SD ∗ . Then since k ∈/ SD ∗ , there exist â ∈ E ∗ suchthat âk = ak . By Condition (s-iv) of supportability, there exists such anâ that satisﬁes either â ∈ E2∗ or [â ∈ E1∗ (k) and âk = ak ], where âk is theminor-deviation from â for player k. As before, suppose that in period t, thestate was 0 with substate a and player k cooperated but did not monitor theother players. Then, in the next period, with positive probability no smaller
than ρκ̂, the player is uncertain whether the state is 0 with substate â or iseither i or j. As before, we show that the loss that player k suﬀers from the32uncertainty exceeds the monitoring cost. We distinguish the following twocases.
First, consider the case when â ∈ E2∗ . An argument similar to the previous ones can show that, under the uncertainty, choosing a major-deviationfrom â is not optimal for player k. That is, it is suboptimal for her to play/ {âk , âk } if k ∈ AP (â) and ak = âk if k ∈/ AP (â). However, by âk = ak
ak ∈
and (2-ii), neither âk nor âk (if well deﬁned) is the dominant action, andtherefore, playing either action causes a loss of at least pk in the period if theother players coordinate on ŝ−k (i) or ŝ−k (j), which occurs with probability2η(1 − η). Thus, the desired conclusion follows from (25).
Second, consider the case when â ∈ E1∗ (k) and âk = ak . A similarargument shows that, under the uncertainty, a major-deviation from â is
not optimal for player k. But, since neither âk nor âk is her dominantaction, playing either action causes a loss of at least pk in the period if theother players coordinate on ŝ−k (i) or ŝ−k (j), which occurs with probability2η(1 − η). Thus, the desired conclusion follows from (25).
These arguments prove that no player has an incentive to deviate interms of monitoring on the equilibrium path.
Q.E.D.
The next lemma completes the proof of Proposition 1.
Lemma 3 There exists a sequential equilibrium in Γ(δ, λ) that generates thesame path as σ̂.
Proof. We start with the construction of a system of beliefs. First, consider
a sequence of totally mixed strategy proﬁles that converges to σ̂ and puts
far smaller weights on the trembles regarding monitoring, in comparison
with the trembles regarding actions. This generates a sequence of systemsof beliefs, whose limit is a system of belief that is consistent with σ̂ and suchthat, at any history (on or oﬀ the path), each player believes that the otherplayers did not deviate in terms of monitoring. Let us denote the system ofbeliefs by µ and let µ(hti ) denote the belief of player i at history hti about
the other players’ (private) histories.
We now construct each player’s strategy, σi∗ . For players i ∈ SD ∗ , wesimply set σi∗ = σ̂i . For players i ∈/ SD ∗ , we ﬁrst setσi∗ (hti ) = σ̂i (hti )for any hti ∈ Ĥi .

(31)/ Ĥi , let σi∗ (hti ) be an optimal continuation strategy at hti given
For any hti ∈her belief µ(hti ) and the other players’ strategies σ̂−i .
33

(31) means that, for any player i, σi∗ and σ̂i coincide at all histories hti
in which i never deviates in terms of monitoring. This together with theconstruction of µ implies that µ is also consistent with σ ∗ .
We now verify sequential rationality. We start with a player i ∈/ SD ∗ andta history hi ∈ Ĥi . At the history, player i knows the state. Moreover, by theconstruction of µ, player i believes that the other players not in SD ∗ also
know the state since i believes that these players never deviated in terms ofmonitoring. In other words, i believes that any other player j ∈/ SD ∗ is at ahistory in Ĥj and any other player j ∈ SD ∗ plays her dominant action in all
subsequent periods. Then, by Lemma 2 and (31), it is optimal for player i
to follow the state-dependent play, i.e., σ̂i . By (31), this is exactly what σi∗
prescribes. Thus the continuation play of σi∗ at history hti is sequentiallyrational.
/ Ĥi . We deﬁned
We now consider a player i ∈/ SD ∗ at a history hti ∈σi∗ (hti ) as an optimal continuation strategy at the history given that i’s belief∗ ). Sequential rationality
is µ(hti ) and the other players follow σ̂−i (not σ−ithen follows since player i believes that all other players j ∈/ SD ∗ are attsome histories hj ∈ Ĥj and therefore, by (31), their continuation strategies
coincide with σj∗ (htj ).
Finally, consider player i ∈ SD ∗ . At any history, she believes that theother players never deviated in terms of monitoring and thus she believes∗ and µ, it isthat her play does not aﬀect the future play. Thus, given σ−isequentially rational for i to play a short-run best response at any history.
This is nothing but following σi∗ .
Therefore, (σ ∗ , µ) is a sequential equilibrium of Γ(δ, λ). By (31), it
is outcome-equivalent to σ̂. This completes the proofs of the lemma and
Proposition 1.
Q.E.D.

34

References
Abreu, D. (1986): “Extremal Equilibria of Oligopolistic Supergames,” Journal of Economic Theory, 39, 191–225.
Abreu, D. (1988): “On the Theory of Inﬁnitely Repeated Games with Discounting,” Econometrica, 56, 383–396.
Abreu, D., D. Pearce, and E. Stacchetti (1990): “Toward a Theory of Discounted Repeated Games with Imperfect Monitoring,” Econometrica,
58, 1041–1063.
Ahn, I., and M. Suominen (2001): “Word-of-Mouth Communication andCommunity Enforcement,” International Economic Review, 42, 399–
415.
Amarante, M. (2002): “Recursive Structure and Equilibria in Games with
Private Monitoring,” forthcoming in Economic Theory.
Aoyagi, M. (2002): “Collusion in Dynamic Bertrand Oligopoly with Correlated Private Signals and Communication,” Journal of Economic
Theory, 102, 229–248.
Benoit, J.-P., and V. Krishna (1985): “Finitely Repeated Games,” Econometrica, 53, 905–922.
Ben-Porath, E., and M. Kahneman (1996): “Communication in RepeatedGames with Private Monitoring,” Journal of Economic Theory 70,
281–297.
Bhaskar, V., and E. van Damme (2002): “Moral Hazard and Private Monitoring,” Journal of Economic Theory, 102, 16–39.
Bhaskar, V., and I. Obara (2002): “Belief-based Equilibria in the RepeatedPrisoners’ Dilemma with Private Monitoring,” Journal of Economic
Theory, 102, 40–69.
Compte, O. (1998): “Communication in Repeated Games with ImperfectPrivate Monitoring,” Econometrica 66, 597–626.
Compte, O. (2002): “On Failing to Cooperate When Monitoring Is Private,”
Journal of Economic Theory, 102, 151–188.
Ely, J., and J. Valimaki (2002): “A Robust Folk Theorem for the Prisoner’s
Dilemma,” Journal of Economic Theory, 102, 84–105.
35

Fudenberg, D., and D. Levine (1994): “Eﬃciency and Observability with
Long-Run and Short-Run Players,” Journal of Economic Theory, 62,
103–135.
Fudenberg, D., and E. Maskin (1986): “The Folk Theorem in RepeatedGames with Discounting or with Incomplete Information,” Econometrica, 54 533–556.
Fudenberg, D., D. Levine, and E. Maskin (1994): “The Folk Theorem with
Imperfect Public Information,” Econometrica, 62, 997–1039.
Kandori, M. (1992): “Social Norms and Community Enforcement,” Review
of Economic Studies, 59, 63–80.
Kandori, M., and H. Matsushima (1998): “Private Observation, Communication and Collusion,” Econometrica, 66, 627–652.
Lehrer, E., and A. Pauzner (1999): “Repeated Games with Diﬀerential Time
Preferences,” Econometrica, 67, 393–412.
Mailath, G., and S. Morris (2002): “Repeated Games with Almost Public
Monitoring,” Journal of Economic Theory, 102, 189–228.
Matsushima, H. (1991): “On the Theory of Repeated Games with Private Information, Part 1: Anti-folk Theorem without Communication,” Economics Letters, 35, 253–256.
Matsushima, H. (2002): “The Folk Theorem for the Prisoner-Dilemma with
Imperfect Private Monitoring,” forthcoming in Econometrica.
Miyahara, Y. (2002): “Near Eﬃciency in Repeated Prisoner’s Dilemma with
Costly Monitoring,” mimeo.
Piccione, M. (2002): “The Repeated Prisoner’s Dilemma with ImperfectPrivate Monitoring,” Journal of Economic Theory, 102, 70–83.
Sekiguchi, T. (1997): “Eﬃciency in Repeated Prisoner’s Dilemma with Private Monitoring,” Journal of Economic Theory, 76, 345–361.
Stigler, G. (1964): “A Theory of Oligopoly,” Journal of Political Economy,
72, 44–61.

36