%Paper: ewp-game/9902001
%From: vkrishna@psu.edu
%Date: Wed, 3 Feb 1999 10:56:16 -0600 (CST)

%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
%\newtheorem{proposition}{Proposition}
%\newtheorem{conjecture}{Conjecture}
%\newtheorem{example}{Example}
%\newtheorem{definition}{Definition}
%\newtheorem{corollary}{Corollary}


\documentstyle[amssymb,12pt,thmsb,sw20elba]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{TCIstyle=article/art1.lat,elba,article}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Created=Mon Jul 29 09:13:37 1996}
%TCIDATA{LastRevised=Thu Dec 10 12:24:49 1998}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=article.cst}

\input tcilatex

\begin{document}

\author{Jean-Pierre Beno\^{\i }t\thanks{%
We are grateful to the CV Starr Center at NYU for research support and the
Institute of Economics at the University of Copenhagen for its generous
hospitality during a visit while part of this paper was written. Drew
Fudenberg, Olivier Gossner, Wojciech Olszewski, Michael Riordan, Tomas
Sj\"{o}str\"{o}m and Matthew Spitzer made helpful suggestions.} \\
%EndAName
Department of Economics and\\
School of Law\\
New York University \and Vijay Krishna$^{*}$ \\
%EndAName
Department of Economics\\
Penn State University}
\title{The Folk Theorems for Repeated Games: A Synthesis}
\date{December 10, 1998}
\maketitle

\begin{abstract}
We present a synthesis of the various folk theorems for repeated games using
a model that accommodates both finitely and infinitely repeated games with
discounting. We derive a central result for this model and show that the
various folk theorems follow as a consequence. Our result encompasses
theorems involving epsilon equilibria and incomplete information.\bigskip 

JEL\ Classification Number: C72

Key Words: Folk Theorems, Repeated Games.

\newpage
\end{abstract}

\tableofcontents

\newpage

\section{Introduction}

The theory of repeated games occupies a central place in noncooperative game
theory as it forms a relatively simple platform from which to study dynamic
aspects of strategic interaction. The key results concerning repeated games,
often called `folk theorems,' delineate the set of equilibrium outcomes in
situations where the future looms large in players' assessments of their
prospects. Typically, the folk theorems show that under these circumstances
the set of equilibrium outcomes is essentially unrestricted.

There are numerous results of this genre, varying along many dimensions:
whether the duration of the game is finite or infinite, whether the
equilibria are perfect or not, whether there is discounting or not, whether
there is complete or incomplete information, whether players are maximizers
or `satisficers,' and whether the set of players remains the same or
consists of overlapping generations.\footnote{%
Detailed references are given below. See Aumann (1980), Pearce (1992) and
Sorin (1993, 1996) for surveys of the area.}

Perhaps the most debated of these aspects concerns the duration of the
repeated game: whether it is finite or infinite. As is well-known, the set
of equilibrium outcomes of a game repeated a large but finite number of
times, may be radically different from the equilibrium outcomes of its
infinitely repeated counterpart. This is sometimes referred to as the
`finite horizon paradox' and the numerous attempts to resolve it have been
responsible for much of the work alluded to above. In addition, there has
been some debate on whether a finite or infinite game is the appropriate
choice for modelling repeated interaction among economic agents. For
instance, Rubinstein (1991) has taken the position that players generally%
{\em \ }perceive repeated games, including those with a known, fixed, and
even short finite duration as a game of infinite duration, and thus infinite
games are the appropriate model. However, the reasons underlying
Rubinstein's position are difficult to fathom. The assumption that {\em %
otherwise rational} players view the twenty-fold repetition of the
prisoners' dilemma as being infinitely repeated is rather curious. And while
the predictions of the infinite game are certainly consistent with observed
behavior in the finitely repeated prisoner's dilemma, there is little in the
model to particularly suggest the sort of end-game play that is typically
observed. Indeed, the predictions of some finite models, such as those with
incomplete information or satisficing players, are more in tune with
observed behavior.

In our opinion, generally modelling finitely repeated games as infinitely
repeated ones is unwarranted. Perhaps any attempt to reach an unequivocal
conclusion on this issue is futile. In any case, such an attempt is
unnecessary and misleading. The theory of repeated games seeks to identify
circumstances in which the set of equilibrium outcomes of repeated games is
larger than that of the one-shot game. Postulating an infinite duration is
neither necessary nor sufficient for this. That it is not necessary is
well-known; if the constituent game has multiple equilibrium payoffs folk
theorems for games with a long but finite duration are available.

To see that it is not sufficient, consider the following example. Suppose
the discount factor, which may also be interpreted as the probability of
continuation, is time dependent. In particular, suppose that the sequence of
per-period discount factors, $\delta _{t}$, declines and approaches $\frac{1%
}{2}$ as $t$ increases.\footnote{%
The payoffs from period $t$ are then discounted by a factor of $\prod_{\tau
=1}^{t}\delta _{\tau }.$} Specifically, given a $\gamma \in \left(
0,1\right) $ let 
\[
\delta _{t}=\frac{1}{2}+\frac{\gamma ^{t}}{2}.
\]
Notice that for all $\gamma ,$ $\lim_{t\rightarrow \infty }\delta _{t}=$ $%
\frac{1}{2}$, while for all $t,$ $\lim_{\gamma \rightarrow 1}\delta _{t}=1.$
The latter property implies that as $\gamma \rightarrow 1,$ players become
arbitrarily patient. Now, consider the following game 
\[
\begin{tabular}{|r|r|}
\hline
$\;\,0,\;0$ & $x,-3$ \\ \hline
$-3,\;x$ & $2,\quad 2$ \\ \hline
\end{tabular}
\]
which is a prisoners' dilemma when $x>2$. It may be verified that if $x=5,$
for all $\gamma ,$ the unique equilibrium payoff in the infinitely repeated
game is $\left( 0,0\right) .$ Although the game is of infinite duration,
there is a unique equilibrium outcome even when players are arbitrarily
patient.

One might be tempted to argue that since the discount factors decline this
is `just like' a finite horizon situation rather than an infinite one.
However, such a contention is refuted by the fact that if $x=4$, then for
large $\gamma $ any feasible individually rational payoff can be obtained in
a perfect equilibrium. Thus, an argument that this is like or unlike a
finite horizon could not be based upon the underlying time structure, that
is the sequence $\left\langle \delta _{t}\right\rangle $, but rather, would
have to depend on the payoffs. The example shows that the finite-infinite
distinction is of limited use in analyzing or classifying the strategic
possibilities.\footnote{%
Moreover, even if one favors the modeling fiction of an unbounded time
horizon, there is little reason to further assume that the continuation
probability, or discount rate, is constant. In Section 6 we discuss the
paper of Bernheim and Dasgupta (1995), where the continuation probability is
not constant.}

In this paper we attempt a synthesis of the various folk theorems by
adopting a point of view which de-emphasizes the choice of horizon. Instead,
we choose to view any repeated game as consisting of a finitely repeated
game followed by an `end-game' whose exact form and duration we leave
unspecified. We show that a folk theorem like result can be established
whenever the end-game has enough threat potential to discipline players;
this requires that the end-game have multiple equilibria. From this
perspective the various resolutions of the finite horizon paradox may simply
be viewed as devices which create or enhance this threat potential. Indeed,
we show that all of the disparate folk theorems for finite horizon games are
rather simple corollaries of a single central result. Furthermore, infinite
games may also be treated in the same way: an infinitely repeated game may
be thought of as a finitely repeated game followed by an end-game of
infinite duration.

Our approach offers some advantages. First, it demonstrates the essential
unity of the various folk theorems and their proofs. The proof of each
theorem may be decomposed into two parts: The construction of the threat in
the end-game and an application of our central result.

Second, we are able to derive some new results and stronger versions of
existing results. For instance, our methodology yields a strong version of
Radner's (1980) $\epsilon $-equilibrium folk theorem that is `uniform' in
the needed variance from optimizing behavior. Similarly, we obtain a folk
theorem with incomplete information that is uniform in the type of
incomplete information needed. Moreover, the methodology itself immediately
suggests the generalizations.

Finally, rather than focusing attention on the duration of the game our
approach isolates what is essential for the folk theorems to hold: whether
there is an end-game in which players' may be threatened sufficiently
severely.

Our approach relies essentially on the fact that payoffs from the `end-game'
are negligible in the limit. While this allows us to consider infinitely
repeated games with discounting, it cannot accommodate infinitely repeated
games in which, say, the `limit of means' is used to evaluate infinite
payoff streams. With the limit of means criterion, the payoff from any
finite number period is irrelevant and thus consequences of play in the
end-game completely dominate earlier play. Thus our methodology does not
apply to the `classical' folk theorems with undiscounted payoffs (Aumann and
Shapley (1994) or Rubinstein (1994)).

This paper is organized as follows.

{\bf Main Result.} Section 2 contains basics and some preliminary results.
We consider perfect equilibria of repeated games with common discounting and
define the central concept: a two-part game that consists of a finitely
repeated game followed by an `end-game.' We adopt the effective minmax
methodology of Wen (1994) as it leads to the most general results. In
Section 3 we derive the main result (Theorem \ref{main}) which identifies
circumstances under which a folk theorem like result may be derived for the
two-part game.

The remainder of the paper is organized into three sections dealing with 
{\em applications} of the main result, its {\em extensions} and some {\em %
reformulations} of the results.

{\bf Applications.} In Section 4, we show how the main result of Section 3
may be applied to obtain various folk theorems.

Section 4.1 derives the various folk theorems for finitely repeated games.
Section 4.1.1 concerns the folk theorem for finitely repeated games in which
each player has distinct equilibrium payoffs (Beno\^{i}t and Krishna
(1985)). Theorem 2 is the basic result and Theorem 2 is a recent
generalization to the case where the players have recursively distinct
equilibrium payoffs (Smith (1995)). In Section 4.1.2 we consider epsilon
equilibria of finitely repeated games and derive two folk theorems (Theorems
4 and 5) that originate in the work of Radner (1980) and Chou and
Geanakoplos (1988). Finally, in Section 4.1.3 we consider games with
incomplete information and derive a result (Theorem 6) along the lines of
Fudenberg and Maskin (1986).

Section 4.2 concerns infinitely repeated games. We consider the Fudenberg
and Maskin (1986) result and its generalizations by Abreu, Dutta and Smith
(1994) and Wen (1994) (Theorem 7). In Section 4.2.2 we consider the recent
model of an infinitely repeated game with a declining discount factor
studied by Bernheim and Dasgupta (1995) (Theorem 8).

Section 4.3 derives a folk theorem for a model with overlapping generations
similar to results of Kandori (1992) and Smith (1992) (Theorem 9).

{\bf Extensions.} Section 5 derives some extensions and generalizations of
the main result.

While the main result is derived for the case of pure strategies (or
alternatively, for the case when mixed strategies are observable), in
Section 5.1 we establish a generalization of Theorem 1 for situations in
which mixed strategies are not observable. Section 5.2 delineates
circumstances under which the statement of Theorem 1 may be strengthened so
the the order in which the limits are taken is irrelevant. While most of the
paper is concerned with subgame perfect equilibria, Section 5.3 shows how
the same methodology can be used to derive an analog of Theorem 1 for Nash
equilibria. The Nash equilibrium result is derived, of course, under much
weaker conditions. Section 5.4 introduces the notion of a `frequent response
game' in which the horizon is fixed but players revise moves rapidly and
shows how Theorem 1 may be reinterpreted to this context.

{\bf Reformulations.} Section 6 shows that the some of the ideas underlying
the main result can be used to derive results in contexts other than
repeated games.\bigskip

A few words to the reader are in order. First, the primary purpose of this
paper is to present a framework that allows for a unification of existing
results on repeated games and derivation of new ones. It relies on and
incorporates ideas from many sources. While some have been explicitly
acknowledged, it would be difficult, if not impossible, to identify all of
these.

A secondary purpose of this paper is expository. Many of the underlying
ideas will be familiar to the reader acquainted with recent developments.
Nevertheless, we present complete proofs while keeping an eye on exposition.
In this manner, the current paper is more or less self contained, while
remaining relatively brief.

\section{Preliminaries}

Let $G=(A_1,A_2,...,A_n;\;U_1,U_2,...,U_n)$ be a game in strategic form
where $A_i$ is $i$'s strategy space and $U_i$ is his payoff function. We
assume that the $A_i$'s are compact and the $U_i$'s are continuous. As usual
we write $A\equiv \prod_{j=1}^nA_j$ and $A_{-i}\equiv \prod_{j\neq i}A_j$
with generic elements $a$ and $a_{-i}$ respectively. We also assume that $G$
has at least one equilibrium.

If the $A_i$'s are convex subsets of a Euclidean space we call $G$ a {\em %
continuous game. }If the $A_i$'s are finite sets we call $G$ a {\em finite
game}.

Let $v_{i}$ be player $i$'s {\em minmax} payoff defined as: 
\[
v_{i}=\min_{a}\max_{a_{i}}U_{i}\left( a_{i},a_{-i}\right) . 
\]
Let $F$ denote the feasible and {\em individually rational} payoffs in $G,$
that is, 
\[
F=\left\{ u\in \limfunc{co}U\left( A\right) :\;u\geq v\right\} . 
\]

Two players $i$ and $j$ are said to have {\em equivalent utilities} if $i$'s
payoff function is an increasing affine transformation of $j$'s (see Abreu,
Dutta and Smith (1994)). Let $N(i)$ denote the set of players $j$ such that $%
i$ and $j$ have equivalent utilities. $N(i)$ defines an equivalence class.
Following Wen (1994) let $v_i^{*}$ be player $i$'s {\em effective minmax}
payoff defined as: 
\begin{equation}
v_i^{*}=\min_a\max_{k\in N(i)}\max_{a_k}U_i(a_k,a_{-k}).  \label{eff}
\end{equation}
As in Wen (1994), for all $i$\ let $m^i$ be the solution to (\ref{eff}) so
that we have that for all $j\in N\left( i\right) $: 
\[
\max_{a_j}U_j(a_j,m_{-j}^i)\leq \max_{k\in N\left( i\right)
}\max_{a_k}U_j(a_k,m_{-k}^i)=v_j^{*}. 
\]
If $m^i$ is played, each player $j\in N(i)$ obtains $v_j^{*}$ and is at a
best response. Clearly, $v_i^{*}\geq v_i.$

Normalize the game so that for all $i$, $v_{i}^{\ast }=0$ and define: 
\[
F^{\ast }=\left\{ u\in \limfunc{co}U\left( A\right) :u\geq 0\right\} . 
\]
to be the set of feasible and {\em effectively rational} payoffs in $G.$ We
assume that there exists a $u\in F^{\ast },$ $u\gg 0.$\footnote{%
Given two vectors $x,y\in {\bf R}^{n},$ $x\gg y$ means that for all $i$, $%
x_{i}>y_{i}.$}

Note that if no two players have equivalent utilities, then $F^{\ast }=F$.
Wen (1994) also shows that $F^{\ast }=F$ for all two player games.

$G^{\delta }(T)$ will denote the game which consists of $T$ repetitions of $%
G $ and in which players use a discount factor of $\delta \in \left(
0,1\right) $ to evaluate payoffs. If $(a^{1},a^{2},...,a^{T})$ is a path in $%
G^{\delta }(T)$ the resulting payoff vector is the discounted average of the
per period payoffs: 
\[
\frac{\left( 1-\delta \right) }{\delta \left( 1-\delta ^{T}\right) }%
\sum_{t=1}^{T}\delta ^{t}U(a^{t}). 
\]
$G^{\delta }(\infty )$ denotes the infinitely repeated game with discount
factor $\delta .$

A pure strategy for player $i$ in $G^{\delta }(T)$ is a sequence $\left(
\sigma _{i}^{1},\sigma _{i}^{2},...,\sigma _{i}^{T}\right) $ such that $%
\sigma _{i}^{1}\in A_{i}$ and for all $t>1,$ $\sigma
_{i}^{t}:A^{t-1}\rightarrow A_{i}.$ Similarly, a pure strategy in $G^{\delta
}(\infty )$ is an infinite sequence $\left( \sigma _{i}^{1},\sigma
_{i}^{2},...\right) $ of this form. Thus, we are assuming that there is {\em %
perfect monitoring} (also called `standard signalling').

Let $P^{\delta }\left( T\right) $ be the set of (subgame) perfect
equilibrium payoffs of $G^{\delta }(T).$ Similarly, $P^{\delta }\left(
\infty \right) $ denotes the set of perfect equilibrium payoffs of $%
G^{\delta }(\infty ).$

The minmax level $v_{i}$ is an obvious lower bound on player $i$'s payoff in
any equilibrium of $G^{\delta }\left( T\right) $\ or $G^{\delta }\left(
\infty \right) $. If $i$ and $j$ have equivalent utilities, \ $j$\ is
unwilling to take any action that is too detrimental for $i,$ since such
action is inevitably detremental for j as well. The effective minmax level $%
v_{i}^{\ast }$ then becomes the natural lower bound.{\em \ }Indeed, Wen
(1994) has shown that for all $\delta $ and $T,$ $P^{\delta }\left( T\right) 
$ $\subseteq F^{\ast }$ and that for all $\delta ,$ $P^{\delta }\left(
\infty \right) $ $\subseteq F^{\ast }.$

{\bf Public Randomization.} Suppose $u\in \limfunc{co}U\left( A\right) .$
Then by definition there exist $L$ pure strategy action profiles $%
a^{1},a^{2},...,a^{L}$ and weights $\lambda _{1},\lambda _{2},...,\lambda
_{L}$ such that $\sum_{l=1}^{L}\lambda _{l}U\left( a^{l}\right) =u.$ Now
suppose there is a publicly observed randomizing device such that the
`state' $l$ occurs with probability $\lambda _{l}.$ Then for all $i$ and $l,$
if each player $i$ plays $a_{i}^{l}$ when the state is $l,$ the resuling
expected payoff will be exactly $u.$ Moreover, since $l$ is common
knowledge, if any player were to choose an $a_{i}\neq a_{i}^{l}$ in state $l$
then this deviation would be commonly observed.

In what follows, in both $G^{\delta }(T)$ and $G^{\delta }(\infty )$, it is
convenient to assume that the players have access to such a randomizing
device and by these means, can achieve any $u\in \limfunc{co}U\left(
A\right) $ exactly. Usually, we will not refer to the randomizing device
explicitly, rather, instead of saying that there is a randomizing device $%
\lambda $ that achieves the payoff $u,$ we economize on notation and say
that there is an `action' $a$ that achieves every payoff $u\in $ $\limfunc{co%
}U\left( A\right) .$ Whenever, $u\notin U\left( A\right) $ this should be
understood to mean that $u$ is achieved in the manner outlined above.%
\footnote{%
Alternatively, every payoff $u$ can be approximated by playing $a^{1}$ for
some $\mu _{1}$ periods, then $a^{2}$ for $\mu _{2}$ periods, $a^{3}$ for $%
\mu _{3}$ periods etc. where the $\mu _{l}$ are integers satisfying $\mu
_{l}\simeq \lambda _{l}\left( \sum \mu _{k}\right) .$ See Sorin (1996) for
details.}

Initially, we also assume that when players randomize independently, their
mixed ({\em behavioral}) strategies are observable (alternatively, we can
say that the $A_{i}$'s themselves subsume all mixing possibilities). This
assumption is relaxed later in Section 5.

\section{The Main Result}

Let $H^\delta =(S_1,S_2,...,S_n;\;V_1^\delta ,V_2^\delta ,...,V_n^\delta )$
be a game with parameter $\delta \in \left( 0,1\right) $.

\begin{definition}
Given a finitely repeated game $G^{\delta }\left( T\right) $ and another
game $H^{\delta },$ the {\bf conjunction} of the two games, written $\langle
G^{\delta }\left( T\right) ,H^{\delta }\rangle ,$ is a $T+1$ period game
that consists of $G^{\delta }(T)$ followed by $H^{\delta },$ with perfect
monitoring throughout. $H^{\delta }$ is then referred to as the {\bf %
end-game. }If $(a^{1},a^{2},...,a^{T},s)$ is a path in $\langle G^{\delta
}\left( T\right) ,H^{\delta }\rangle $, the resulting payoff is 
\[
\frac{\left( 1-\delta \right) }{\delta \left( 1-\delta ^{T+1}\right) }\left[
\sum_{t=1}^{T}\delta ^{t}U(a^{t})+\delta ^{T+1}V^{\delta }(s)\right] .
\]
\end{definition}

If $(\sigma ^{1},\sigma ^{2},...,\sigma ^{T},\sigma ^{T+1})$ is a perfect
equilibrium of the game $\langle G^{\delta }\left( T\right) ,H^{\delta
}\rangle ,$ then for all $(a^{1},a^{2},...,a^{T})\in A^{T},$ we must have
that $\sigma ^{T+1}(a^{1},a^{2},...,a^{T})$ is a perfect equilibrium of $%
H^{\delta }.$\footnote{%
Of course, if $H^{\delta }$ has no proper subgames, the set of perfect
equilibria of $H^{\delta }$ is the same as the set of Nash equilibria of $%
H^{\delta }$.} Notice that if $H^{\delta }$ is itself a repeated game $%
G^{\delta }\left( T^{\prime }\right) $ (where $T^{\prime }$ may be finite or
infinite) then a perfect equilibrium payoff of $\langle G^{\delta }\left(
T\right) ,H^{\delta }\rangle $ is a perfect equilibrium payoff of $G^{\delta
}(T+T^{\prime })$.

\begin{definition}
\label{def}The game $H^{\delta }=\left( S_{1}^{\delta },...,S_{n}^{\delta
},V_{1}^{\delta },...,V_{n}^{\delta }\right) $ has a {\bf perfect threat}%
{\em \ }{\bf of} $M$ if there exist $n+1$ perfect equilibria of $H^{\delta
}:\,$ $s,$ $s^{1},s^{2},...,s^{n}$ satisfying for all $i,$%
\begin{equation}
\left[ V_{i}^{\delta }(s)-V_{i}^{\delta }(s^{i})\right] \geq M.
\label{threat}
\end{equation}
$\,$ $s,$ $s^{1},s^{2},...,s^{n}$ will be referred to as the {\bf perfect
threat strategies}{\em \ }which yield $M.$
\end{definition}

A perfect threat of $M$ consists of a `{\em target}' path $s$\ and for each
player $i$\ a `{\em punishment}' path $s^{i}$;\ each player $i$\ can then be
`threatened' with a\ loss\ of at least $M$ by a play of $s^{i}$\ rather than 
$s$.\ Note that $s^{1},s^{2},...,s^{n}$\ need not be distinct.

Let $\Pi ^{\delta }(T)$ be the set of (subgame) perfect equilibrium payoffs
of the conjoined game $\langle G^{\delta }\left( T\right) ,H^{\delta
}\rangle .$ Our main result concerns the Hausdorff limit of $\Pi ^{\delta
}(T)$ as $\delta \rightarrow 1$ and $T\rightarrow \infty $: {\em \ }if the
end-game $H^{\delta }$\ has a large enough threat then the set of perfect
equilibrium payoffs of the conjoined game $\langle G^{\delta }\left(
T\right) ,H^{\delta }\rangle $\ approaches the set of effectively rational
payoffs $F^{\ast }$\ of the game{\bf \ }$G$.\footnote{%
We show below in Section 5 that under a slightly stronger assumption on $%
H^{\delta }$ the order of limits in the statement below is unimportant. This
stronger assumption is satisfied for finitely repeated games.} When $%
H^{\delta }$\ has a large threat, it is obvious that towards the end of $%
G^{\delta }\left( T\right) $\ the players can be induced to follow any path,
since possible losses in $H^{\delta }$ swamp any gains from deviating in the
small time remaining in $G^{\delta }\left( T\right) .$\ It is less obvious
that the threat in $H^{\delta }$ can have any impact on play at the
beginning of an arbitrarily long $G^{\delta }\left( T\right) .$\ This is
both because viewed from the beginning of the game the discounted threat
appears small and because the sums of the payments over the entire course of 
$G^{\delta }\left( T\right) $\ are (potentially) much larger than any
payoffs in $H^{\delta }$. Nonetheless, $H^{\delta }$ serves to prevent an
`unravelling' at the very end of the game. In earlier periods, threats built
within the game $G^{\delta }\left( T\right) $ itself are used to sustain
effectively rational paths.

\begin{theorem}
\label{main} There exists an $M$ such that if for all large $\delta ,$ $%
H^{\delta }$ has a perfect threat of $M$ then 
\[
\lim_{\delta \rightarrow 1}\lim_{T\rightarrow \infty }\Pi ^{\delta
}(T)=F^{\ast }.
\]
\medskip 
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
Let $\limfunc{aff}F^{*}$ be the smallest affine space containing $F^{*}.$%
\footnote{$\limfunc{aff}F^{*}=\left\{ \sum_{i=1}^L\lambda _ix^i:x^i\in
F^{*},\sum_{i=1}^L\lambda _i=1\right\} .$ See Rockafellar (1970).} Define $%
\overline{B}\left( u,\varepsilon \right) =\left\{ v\in \limfunc{aff}%
F^{*}:\left| u-v\right| \leq \varepsilon \right\} ,$ the closed ball of
radius $\varepsilon $ around $u.$

For $\varepsilon >0,$ define 
\[
F^{*}\left( \varepsilon \right) =\left\{ u\in F^{*}:\overline{B}\left(
u,\varepsilon \right) \subset F^{*}\right\} 
\]
and choose $\varepsilon >0$ small enough so that $\limfunc{rel}\limfunc{int}%
F^{*}\left( \varepsilon \right) \neq \emptyset .$ As in Abreu, Dutta and
Smith (1994), from the definition of equivalent utilities, there exist $n$
vectors $x^1,x^2,...,x^n$ in $F^{*}\left( \varepsilon \right) $ that satisfy
payoff asymmetry: 
\begin{equation}
\begin{array}{ll}
\forall j\notin N\left( i\right) , & x_i^i<x_i^j \\ 
\forall j\in N\left( i\right) , & x^i=x^j
\end{array}
\label{asymm}
\end{equation}

We proceed in three steps.

Step 1{\em \ }establishes\ punishment vectors $w^{i}$\ for each player that
have the property that given any planned payoff $u\in F^{\ast }\left(
\varepsilon \right) ,$\ each player prefers the planned payoff $u_{i}$\ to
his punishment payoff $w_{i}^{i}$,\ and moreover, prefers the payoff $%
w_{i}^{j}$\ when some player $j\notin N\left( i\right) $\ is punished to his
own punishment payoff $w_{i}^{i}.$

\paragraph{Step 1}

{\em For all }$\varepsilon ${\em \ there exists an }$\varepsilon ^{\prime
}<\varepsilon ${\em \ and }$w^1,w^2,...,w^n${\em \ in }$F^{*}\left(
\varepsilon ^{\prime }\right) $ {\em such that for all }$u\in F^{*}\left(
\varepsilon \right) ${\em :} 
\begin{equation}
\begin{array}{ll}
\forall i\in N, & w_i^i<u_i-\varepsilon ^{\prime } \\ 
\forall j\notin N\left( i\right) , & w_i^i<w_i^j-\varepsilon ^{\prime } \\ 
\forall j\in N\left( i\right) , & w_i^i=w_i^j
\end{array}
\label{uniform}
\end{equation}

For all $i,$ let $y^{i}$ be such that $y_{i}^{i}=\min \left\{ v_{i}:\exists
v_{-i},\text{ }\left( v_{i},v_{-i}\right) \in F^{\ast }\left( \varepsilon
\right) \right\} .$ Similarly, let $z^{i}$ be such that $z_{i}^{i}=\min
\left\{ v_{i}:\exists v_{-i},\text{ }\left( v_{i},v_{-i}\right) \in F^{\ast
}\left( \varepsilon /3\right) \right\} .$ Then $z_{i}^{i}<y_{i}^{i}.$ Notice
that if $j\in N\left( i\right) $\ then $y_{i}^{i}=y_{i}^{j}$\ and{\bf \ }$%
z_{i}^{i}=z_{i}^{j}.$

Since for all $i\in N,$ $z_i^i<y_i^i$ there exists a $\beta \in \left(
0,1\right) $ such that for all $i\in N,$ $y_i^i-\left( 1-\beta \right)
z_i^i-\beta x_i^i>0.$ Fix such a $\beta .$

Choose $\varepsilon ^{\prime }$ to satisfy: for all $i$, $y_i^i-\left(
1-\beta \right) z_i^i-\beta x_i^i>\varepsilon ^{\prime }$ and for all $i$
and all $j\notin N\left( i\right) $, $\beta \left( x_i^j-x_i^i\right)
>\varepsilon ^{\prime }.$

Define

\[
w^{i}=\left( 1-\beta \right) z^{i}+\beta x^{i} 
\]
It is routine to verify that the $w^{i}$ satisfy (\ref{uniform}).

This completes Step 1.\medskip

Step 2 shows\ that when $\delta $\ is large enough, the $w^{i}$\ determined
in Step 1 constitute sufficient punishments in the early periods of the game
to enforce proposed paths. Towards the end of the game there is insufficient
time to use these punishments, but now the threats in the end-game $%
H^{\delta }$\ can be used.

\paragraph{Step 2}

{\em For all }$\varepsilon >0${\em \ there exists an }$M\left( \varepsilon
\right) ${\em \ such that if for all large }$\delta ,${\em \ }$H^\delta $%
{\em \ has a perfect threat of }$M\left( \varepsilon \right) ${\em \ then
there exists a }$\delta \left( \varepsilon \right) ,$ {\em such that for all 
}$T$ {\em and }$\delta >\delta \left( \varepsilon \right) ,${\em \ }${\em for%
}$ ${\em all}$ $a$ ${\em satisfying}$ $U\left( a\right) \in F^{*}\left(
\varepsilon \right) $ ${\em the}$ ${\em path}$ $(\stackrel{T\text{ periods}}{%
\overbrace{a,a,...,a}},s)${\em \ is a perfect equilibrium path of }$\langle
G^\delta \left( T\right) ,H^\delta \rangle .$

Observe that in the statement above, $M\left( \varepsilon \right) $, $%
T\left( \varepsilon \right) $ and $\delta \left( \varepsilon \right) $ are
independent of $a.$

Let $a$ $\in A$ be such that $U\left( a\right) \in F^{*}\left( \varepsilon
\right) .$ From Step 1 there exists an $\varepsilon ^{\prime }$ and vectors $%
w^1,w^2,...,w^n$ in $F^{*}\left( \varepsilon ^{\prime }\right) $ that
satisfy (\ref{uniform}) when $u=U\left( a\right) .$

For all $i,$ let $a^i$ $\in A$ be such that $U\left( a^i\right) =w^i.$

Suppose $Q$, $R$ and $T$ are given, $R<Q$ $<T$. Let $s,$ $s^1,s^2,...,s^n$
be perfect equilibria of $H^\delta $. (Note that $s$ and $s^i$ depend on $%
\delta $).

Let $\pi _1^0$ be a path from period $1$ to $T+1$ described by: 
\[
\pi _1^0=(a,a,...,a,s). 
\]

For $i=1,2,...,n$, and $\tau \leq T-Q$ let $\pi _\tau ^i$ be a path that
begins in period $\tau $ and ends in period $T+1$ described by:

\[
\pi _\tau ^i=(\stackrel{R\text{ periods}}{\overbrace{m^i,m^i,...,m^i}}%
,a^i,a^i,...,a^i,s). 
\]

Given a strategy combination $\sigma ,$ we say that {\em i deviates from a
path }$\pi _\tau ^i${\em \ }${\em in}$ {\em period }$t$ if $\sigma $ calls
for $i$ to play $\pi _\tau ^i\left( t\right) $ but $i$ plays something else.
Consider the following (recursively defined) strategies:

\begin{itemize}
\item  Follow $\pi _{1}^{0}$ (until someone deviates).

\item  If player $i$ is the (lowest indexed) player to deviate from $\pi
_{\tau }^{j},$ $j=0,1,...,n$ in period $t\leq T-Q,$ switch to $\pi
_{t+1}^{i}.$

\item  If player $i$ is the first player (with the lowest index) to deviate
from $\pi _{\tau }^{j}$ in some period $t$, $T-Q<t\leq T$, then play some
equilibrium $e$ of $G$ in each subsequent period through period $T,$ and
play $s^{i}$ in period $T+1$. Any deviation after the first is ignored.
\end{itemize}

We now show that for large enough $Q$, $R$, $T$ and $\delta $ these are
perfect equilibrium strategies. It is sufficient to verify that no player
wants to deviate from these strategies just once and conform thereafter.%
\footnote{%
This is known as the `one deviation property' of subgame perfect
equilibrium. See Osborne and Rubinstein (1994).}

First, consider $t\leq T-Q$ and deviations by player $i\in $ $N(j)$ from $%
\pi _1^0$ or $\pi _\tau ^j.$ Clearly $i$ cannot gain by deviating from $\pi
_\tau ^j$ while being (effectively) minmaxed. For other periods, if $i$
deviates his remaining payoff stream is bounded above by: 
\begin{equation}
(\overline{u},\stackrel{R\text{ periods}}{\overbrace{0,0,...,0}}%
,w_i^j,...,w_i^j,V_i^\delta (s))  \label{dev1}
\end{equation}
where $\overline{u}$ is the maximum payoff of any player in $G$. To see
this, recall from (\ref{uniform}) that for $i\in $ $N(j),$ $w_i^i=w_i^j$. On
the other hand, if $i$ does not deviate his remaining payoff stream will be
no worse than: 
\begin{equation}
(w_i^j,\stackrel{R\text{ periods}}{\overbrace{w_i^j,w_i^j,...,w_i^j}}%
,w_i^j,...,w_i^j,V_i^\delta (s))  \label{ndev1}
\end{equation}
Since $w_i^j>\varepsilon ^{\prime },$ (\ref{ndev1}) is no worse than 
\begin{equation}
(\varepsilon ^{\prime },\stackrel{R\text{ periods}}{\overbrace{\varepsilon
^{\prime },\varepsilon ^{\prime },...,\varepsilon ^{\prime }}}%
,w_i^j,...,w_i^j,V_i^\delta (s))  \label{ndev11}
\end{equation}

For large enough $R$ and $\delta $ the discounted value of (\ref{ndev11}) is
greater than that of (\ref{dev1}). Note that the $R$ and $\delta $ so chosen
depend on $\varepsilon ^{\prime }$ and hence on $\varepsilon .$

Next, consider $t\leq T-Q$ and deviations by player $i\notin N(j)$ from $\pi
_\tau ^j.$ Deviating once yields a remaining payoff stream bounded above by: 
\begin{equation}
(\overline{u},\stackrel{R\text{ periods}}{\overbrace{0,...,0}},\stackrel{Q-R%
}{\overbrace{w_i^i,...,w_i^i}},\stackrel{T-t-Q}{\overbrace{w_i^i,...,w_i^i}}%
,V_i^\delta (s))  \label{dev2}
\end{equation}
Not deviating yields $i$ at worst: 
\begin{equation}
(\stackrel{R\text{ periods}}{\overbrace{\underline{u},...,\underline{u}}},%
\stackrel{Q-R}{\overbrace{w_i^j,...,w_i^j}},\stackrel{T-t-Q+1}{\overbrace{%
w_i^j,w_i^j,...,w_i^j}},V_i^\delta (s))  \label{ndev2}
\end{equation}
where $\underline{u}$ is the minimum payoff of any player in $G.$ Since $%
i\notin N(j),$ from (\ref{uniform}) $w_i^j-w_i^i>\varepsilon ^{\prime },$
and thus we can choose $Q$ so that the discounted value of (\ref{ndev2}) is
greater than that of (\ref{dev2}) for all $i,j,$ $i\notin N(j)$, when $t=T-Q$
and $\delta =1.$ The inequality then also holds for all large $\delta $ and $%
t<T-Q.$ Once again, $Q$ depends only on $\varepsilon .$

Finally, consider deviations by a first deviator $i$ in a period $t>T-Q.$ If 
$i$ deviates his remaining payoff stream is bounded above by: 
\begin{equation}
(\stackrel{Q\text{ periods}}{\overbrace{\overline{u},\overline{u},...,%
\overline{u}}},V_i^\delta (s^i))  \label{dev3}
\end{equation}
If $i$ does not deviate his remaining payoff stream will be at worst: 
\begin{equation}
(\stackrel{Q\text{ periods}}{\overbrace{\underline{u},\underline{u},...,%
\underline{u}}},V_i^\delta (s))  \label{ndev3}
\end{equation}

Let $M\left( \varepsilon \right) $ be a number satisfying $M\left(
\varepsilon \right) >Q\left( \overline{u}-\underline{u}\right) $ (Since $Q$
depends only on $\varepsilon ,$ so does $M$). Suppose $s,$ $s^1,s^2,...,s^n$
are perfect equilibria of $H^\delta $ such that for all $i$%
\[
\left[ V_i^\delta (s)-V_i^\delta (s^i)\right] \geq M\left( \varepsilon
\right) . 
\]
For large enough $\delta ,$ the discounted value of (\ref{ndev3}) is greater
than that of (\ref{dev3}), for all $i$.

This completes Step 2.\medskip

{\em Notice that the threats used in Step 2 depend upon }$\varepsilon $ {\em %
(we have }$M\left( \varepsilon \right) ${\em ). Step 3 shows that }$M$ {\em %
can be chosen independently of }$\varepsilon .$

\paragraph{Step 3}

{\em There exists an }$M${\em \ such that if for all large }$\delta ,${\em \ 
}$H^{\delta }${\em \ has a perfect threat of }$M${\em \ then for all }$%
\varepsilon >0$ {\em there exists a }$\delta \left( \varepsilon \right) $ 
{\em such that for all} $\delta >\delta \left( \varepsilon \right) ,$ {\em %
there exists a }$T\left( \varepsilon ,\delta \right) $ {\em such that for
all }$T>T\left( \varepsilon ,\delta \right) ${\em , if} $u\in F^{\ast }$ 
{\em then} {\em there exists a }$v\in \Pi ^{\delta }\left( T\right) $ {\em %
with }$\left| u-v\right| <\varepsilon .$

Fix an $\widehat{\varepsilon }$ and a point $\widehat{u}\in F^{\ast }\left( 
\widehat{\varepsilon }\right) .$ From Step 1 there exists an $\widehat{%
\varepsilon }^{\prime }<\widehat{\varepsilon }$ and $\widehat{w}^{1},%
\widehat{w}^{2},...,\widehat{w}^{n}$ in $F^{\ast }\left( \widehat{%
\varepsilon }^{\prime }\right) $ satisfying (\ref{uniform}). Let $M=M\left( 
\widehat{\varepsilon }^{\prime }\right) $ as determined in the statement of
Step 2$.$

Let $\widehat{a},\widehat{a}^1,\widehat{a}^2,...,\widehat{a}^n$ be outcomes
corresponding to $\widehat{u},$ $\widehat{w}^1,\widehat{w}^2,...,\widehat{w}%
^n,$ respectively.

Suppose that for all large $\delta ,\,H^\delta $ has a perfect threat of $%
M=M\left( \widehat{\varepsilon }^{\prime }\right) .$ We now show that for
all $M^{\prime }$ there exists a $T\left( M^{\prime }\right) $ such that for
all $T>T\left( M^{\prime }\right) $ and large $\delta ,$ the conjoined game $%
\hat{H}^{\prime }\equiv \langle G^\delta \left( T\right) ,H^\delta \rangle ,$
itself viewed as an end-game, has a perfect threat of $M^{\prime }.$ This is
because from Step 2, $(\widehat{a},\widehat{a},...,\widehat{a},s)$ and $(%
\widehat{a}^i,\widehat{a}^i,...,\widehat{a}^i,s)$ are perfect equilibrium
paths of $\langle G^\delta \left( T\right) ,H^\delta \rangle ,$ and the
difference in player $i$'s payoffs from these paths exceeds $M^{\prime }$
when $T$ and $\delta $ are large.

Now for any $u\in F^{*}$ take a $u^{\prime }\in F^{*}\left( \varepsilon
\right) $ satisfying $\left| u-u^{\prime }\right| <\varepsilon .$ Consider
the game $G^\delta \left( T\right) $ followed by an end-game. As in Step 2,
for $\delta >\delta \left( \varepsilon \right) $, $u^{\prime }$ can be
obtained as a perfect equilibrium payoff in every period but the last, if
the end-game has a large enough threat $M\left( \varepsilon \right) $. While 
$H^\delta $ has a threat of (only) $M,$ we have shown that for all large $%
\delta $, the conjoined game $\langle G^\delta (T(M\left( \varepsilon
\right) )),H^\delta \rangle $ has a threat $M\left( \varepsilon \right) .$
Therefore, $u^{\prime }$ can be obtained in every period but the last of the
game $G^\delta \left( T\right) $ followed by the end-game $\overline{H}%
^\delta \equiv \langle G^\delta (T(M\left( \varepsilon \right) )),H^\delta
\rangle .$ But this game, $\langle G^\delta \left( T\right) ,\overline{H}%
^\delta \rangle $, is the same as $\langle G^\delta (T+T(M\left( \varepsilon
\right) )),H^\delta \rangle $. Hence $u^{\prime }$ can be obtained in every
period but the last $K\left( \varepsilon \right) \equiv T(M\left(
\varepsilon \right) )+1$ periods of the game $\langle G^\delta (T+T(M\left(
\varepsilon \right) )),H^\delta \rangle $ for all $T.$

Finally note that for large enough $T\left( \varepsilon ,\delta \right) ,$
for all $T>$ $T\left( \varepsilon ,\delta \right) $ the payoff from one of
these paths is within $\varepsilon $ of $u^{\prime }$.%
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

When $T$ is large, the perfect threat $M$ required for Theorem \ref{main} is
small relative to the total payoffs in $G^{\delta }\left( T\right) $. The
following corollary gives a sufficient condition for $M$ to be small
relative to the payoffs in $G$.

Given an outcome $a$, define the maximum gain from deviating from $a:$ 
\[
d\left( a\right) =\max_{i}\left\{ U_{i}\left( b_{i}\left( a\right)
,a_{-i}\right) -U_{i}\left( a\right) \right\} . 
\]
where $b_{i}\left( a\right) $ is $i$'s best response to $a_{-i}.$

\begin{corollary}
\label{inf}Suppose $G$ has an equilibrium $e$ that is inefficient. If for
all large $\delta ,$ $H^{\delta }$ has a perfect threat of $M>\inf \left\{
d\left( a\right) :U\left( a\right) \gg U\left( e\right) \right\} $ then 
\[
\lim_{\delta \rightarrow 1}\lim_{T\rightarrow \infty }\Pi ^{\delta
}(T)=F^{\ast }.
\]
\end{corollary}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
Choose $a$ such that $U\left( a\right) \gg U\left( e\right) $ and $d\left(
a\right) <M.$ Let $s,$ $s^1,s^2,...,s^n$ be the threat strategies which
yield $M$. Then for all $T$ and large $\delta $ the path $\left(
a,a,...,a,s\right) $ is a perfect equilibrium path of $\langle G^\delta
\left( T\right) ,H^\delta \rangle $ since deviations can be punished with $%
\left( e,e,...,e,s^i\right) .$ Since the payoff difference between $\left(
a,a,...,a,s\right) $ and $(e,e,...,e,s)$ can be made arbitrarily large, the
game $\overline{H}^\delta =\langle G^\delta (T^{\prime }),H^\delta \rangle $
has an arbitrarily large threat for large $\delta $ and $T^{\prime }.$ Apply
Theorem 1 to $\langle G^\delta (T),\overline{H}^\delta \rangle $. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

Note that for continuous games $\inf \left\{ d\left( a\right) :U\left(
a\right) \gg U\left( e\right) \right\} $ $=0,$ so that if $G$ is a
continuous game with an inefficient equilibrium it is enough for $H^{\delta
} $ to have any positive threat.\footnote{%
Chou and Geanakoplos (1988) show that for ``smooth commitment'' games a folk
theorem may obtain with any positive commitment. See Section 6 for a further
discussion.}

\subsection{Order of Limits}

In many contexts, in particular for finitely repeated games, the end-game $%
H^\delta $ satisfies the condition that for all $i$ and $s,$ $\lim
\sup_{\delta \rightarrow 1}\left| V_i^\delta (s)\right| <\infty .$

Under this assumption, we obtain the stronger result that the order of
limits in the conclusion of Theorem \ref{main} is unimportant.\bigskip

\noindent {\bf Theorem }${\bf 1}^{\prime }$ {\em Suppose }$H^\delta ${\em \
satisfies for all }$i${\em \ and }$s,${\em \ }$\lim \sup_{\delta \rightarrow
1}\left| V_i^\delta (s)\right| <\infty ${\em . There exists an }$M${\em \
such that if for all large }$\delta ,${\em \ }$H^\delta ${\em \ has a threat
of }$M${\em \ then} 
\[
\lim\Sb \delta \rightarrow 1  \\ T\rightarrow \infty  \endSb \Pi ^\delta
(T)=F^{*}. 
\]

The proof follows the proof of Theorem \ref{main} exactly, with the double
limit being taken in Step 3 instead of the sequential limit. The condition
that the payoffs $V^{\delta }\left( s\right) $ are bounded as $\delta
\rightarrow 1$ ensures that the contribution of $H^{\delta }$ to the average
payoffs in the conjoined game $\langle G^{\delta }\left( T\right) ,H^{\delta
}\rangle $ is negligible, regardless of the order in which the limits are
taken.

\section{Applications}

\subsection{Finitely Repeated Games}

As noted earlier, if $H^{\delta }$ is itself a repeated game $G^{\delta
}(T^{\prime })$ then a perfect equilibrium payoff of $\langle G^{\delta
}\left( T\right) ,H^{\delta }\rangle $ is a perfect equilibrium payoff of $%
G^{\delta }(T+T^{\prime }),$ that is, $\Pi ^{\delta }\left( T+1\right)
=P^{\delta }(T+T^{\prime })$. Furthermore, if there exists a set of perfect
equilibrium strategies $s,s^{1},s^{2},...,s^{n}$ of $G^{\delta }(T^{\prime
}) $ which, for all $\delta \geq \delta ^{\prime },$ yield any positive
perfect threat for $G^{\delta }(T^{\prime })$, then by choosing $k$ large
enough, the game $G^{\delta }\left( kT^{\prime }\right) $ can be made to
have an arbitrarily large threat for large $\delta $. This threat can be
obtained simply by `patching' together the relevant threat strategies of $%
G^{\delta }(T^{\prime })\,\,k$ times.\footnote{%
Suppose $(a^{1},a^{2},...,a^{T})$ is a perfect equilibrium path of $%
G^{\delta }\left( T\right) $ and $(\overline{a}^{1},\overline{a}^{2},...,%
\overline{a}^{\overline{T}})$ is a perfect equilibrium path of $G^{\delta }(%
\overline{T}).$ Then $(a^{1},a^{2},...,a^{T},\overline{a}^{1},\overline{a}%
^{2},...,\overline{a}^{\overline{T}})$ is a perfect equilibrium path of $%
G^{\delta }(T+\overline{T}).$ This process is referred to as `patching' the
two paths together.} Applying Theorem $1^{\prime }$ to the conjoined game $%
\langle G^{\delta }\left( T\right) ,G^{\delta }(kT^{\prime })\rangle ,$ we
have that there exists a $k$ such that $\lim\Sb \delta \rightarrow 1  \\ %
T\rightarrow \infty  \endSb \Pi ^{\delta }\left( T\right) =\lim\Sb \delta
\rightarrow 1  \\ T\rightarrow \infty  \endSb P^{\delta }(T+kT^{\prime
})=F^{\ast }.$

Thus, we have the following:

\begin{proposition}
\label{coda}Suppose that for some $T^{\prime }$ and $\delta ^{\prime }$
there exists a set of strategies which, for all $\delta \geq \delta ^{\prime
}$, yield a positive perfect threat in\thinspace $\,G^{\delta }(T^{\prime })$%
. Then 
\[
\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb P^{\delta
}\left( T\right) =F^{\ast }.
\]
\end{proposition}

In Section 5.2 we show that the above limits, and indeed all the limits for
finitely repeated games, can be taken simultaneously.

\subsubsection{Games with Distinct Equilibrium Payoffs}

Say that $G$ has {\em distinct} equilibrium payoffs\ if every player has two
equilibrium payoffs. The following result is due to Beno\^{i}t and Krishna
(1985).\footnote{%
We remind the reader that this and all other folk theorems are rewritten in
Wen's (1994) `effective minmax' formulation. Also, the original theorem was
stated without discounting.}

\begin{theorem}
\label{frg}If $G$ has distinct equilibrium payoffs then 
\[
\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb P^{\delta
}\left( T\right) =F^{\ast }.
\]
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
For all $i,$ let $U_i\left( \overline{e}^i\right) >U_i\left( \underline{e}%
^i\right) $ be the best and worst equilibrium payoff, respectively, for
player $i$. Set $T^{\prime }=2n$, and let $s=\left( \overline{e}^1,%
\underline{e}^1,\overline{e}^2,\underline{e}^2,...,\overline{e}^n,\underline{%
e}^n\right) $ and $s^i=(\underline{e}^i,\underline{e}^i,...,\underline{e}^i)$
be $T^{\prime }$ period paths. Note that for all $\delta ,$ $%
s,s^1,s^2,...,s^n$ forms a positive threat in $G^\delta (T^{\prime })$. Now
apply Proposition \ref{coda}. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip\ 

As in Smith (1995) we say that $G$ has {\em recursively distinct}
equilibrium payoffs if there exists an ordering of the players $1,...,n$
such that (a) player $1$ has two equilibrium payoffs, and (b) for all $i,$ $%
1\leq i<n$, there exist strategy combinations $h^{i+1}$ and $l^{i+1}$ such
that $u_{i+1}\left( h^{i+1}\right) >$ $u_{i+1}\left( l^{i+1}\right) $ and
each player $i+1,...,n$ is at a best response.\footnote{%
This definition is equivalent to the definition in Smith (1995).} The
following generalization of Theorem \ref{frg} is due to Smith (1995).

\begin{theorem}
If $G$ has recursively distinct equilibrium payoffs then 
\[
\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb P^{\delta
}\left( T\right) =F^{\ast }.
\]
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
We proceed inductively. Suppose that for some $i,$ $1\leq i<n,$ there exists
a $Q_i$ such that $G^1(Q_i)$ has two equilibrium payoffs for players $%
1,...,i $ in which, in every period, each player either strictly prefers to
follow the equilibrium path than to deviate from it or is at a single period
best response. For all $i$ let $\overline{\pi }^i$ and $\underline{\pi }^i$
be such perfect equilibrium paths of $G^1(Q_i)$ yielding $i$ his highest and
lowest payoff among such paths, respectively. Since $G$ has recursively
distinct equilibrium payoffs there exists a $k$ such that 
\[
(h^{i+1},\stackrel{k\text{ times}}{\overbrace{\overline{\pi }^1,...,%
\overline{\pi }^1}},\stackrel{k\text{ times}}{\overbrace{\underline{\pi }%
^1,...,\underline{\pi }^1}},\;...\;,\stackrel{k\text{ times}}{\overbrace{%
\overline{\pi }^i,...,\overline{\pi }^i}},\stackrel{k\text{ times}}{%
\overbrace{\underline{\pi }^i,...,\underline{\pi }^i}}) 
\]
and 
\[
(l^{i+1},\stackrel{k\text{ times}}{\overbrace{\overline{\pi }^1,...,%
\overline{\pi }^1}},\stackrel{k\text{ times}}{\overbrace{\underline{\pi }%
^1,...,\underline{\pi }^1}},\;...\;,\stackrel{k\text{ times}}{\overbrace{%
\overline{\pi }^i,...,\overline{\pi }^i}},\stackrel{k\text{ times}}{%
\overbrace{\underline{\pi }^i,...,\underline{\pi }^i}}) 
\]
are perfect equilibrium paths of $G^1(2ikQ_i+1)$ with different payoffs for
player $i+1$, and again in every period each player either strictly prefers
to follow the equilibrium path than to deviate or is at a single period best
response . These paths are supported by threatening player $j=$ $1,...,i$
with a punishment of going to $\underline{\pi }^j$ ($2ik$ times) for a
deviation in period $1;$ note that players $i+1,...,n$ are all at best
responses in period $1$. Thus, continuing inductively, we can find a $Q$
such that every player has two equilibrium payoffs for all $\delta $
sufficiently close to $1$. By patching these equilibria together as in the
proof of Theorem \ref{frg}, the game $G^\delta (T^{\prime })$ has a positive
threat, where now $T^{\prime }=2nQ$. Now apply Proposition \ref{coda}. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

\subsubsection{$\protect\epsilon $-Equilibria}

Radner (1980) introduced the following notion of approximate equilibrium
behavior.

\begin{definition}
An $\epsilon ${\bf -equilibrium} of $G^{\delta }\left( T\right) $ is a
strategy combination $\sigma $ such that for all $i$ and $\sigma
_{i}^{\prime }$ 
\[
\frac{1-\delta }{\delta \left( 1-\delta ^{T}\right) }\left[
\sum_{t=1}^{T}\delta ^{t}U(a^{t}\left( \sigma \right) )\right] \geq \frac{%
1-\delta }{\delta \left( 1-\delta ^{T}\right) }\left[ \sum_{t=1}^{T}\delta
^{t}U(a^{t}\left( \sigma _{i}^{\prime },\sigma _{-i}\right) )\right]
-\epsilon 
\]
where $a^{t}\left( \sigma \right) $ and $a^{t}\left( \sigma _{i}^{\prime
},\sigma _{-i}\right) $ are the outcomes at time $t$ resulting from $\sigma $
and $\left( \sigma _{i}^{\prime },\sigma _{-i}\right) $ respectively. A {\bf %
perfect }$\epsilon ${\bf -equilibrium} is an $\epsilon $-equilibrium in
every subgame of $G^{\delta }\left( T\right) .$
\end{definition}

Below we establish a folk theorem for perfect $\epsilon $-equilibria along
the lines of Radner (1980). However, the notion of perfect $\epsilon $%
-equilibrium may be criticized on the grounds that while a player's payoff
is close to his best-response payoff in terms of {\em averages}, in long
horizon game the discrepancy may be quite large in terms of {\em totals. }%
The following definition, suggested in the work of Chou and Geanakoplos
(1988), is intended to address this issue directly.

\begin{definition}
An $\Omega ${\bf -satisficing equilibrium} of $G^{\delta }\left( T\right) $
is a strategy combination $\sigma $ such that for all $i$ and $\sigma
_{i}^{\prime }$ 
\[
\sum_{t=1}^{T}\delta ^{t}U(a^{t}\left( \sigma \right) )\geq \left[
\sum_{t=1}^{T}\delta ^{t}U(a^{t}\left( \sigma _{i}^{\prime },\sigma
_{-i}\right) )\right] -\Omega .
\]
A {\bf perfect }$\Omega ${\bf -satisficing equilibrium} is an $\Omega $%
-satisficing equilibrium in every subgame of $G^{\delta }\left( T\right) .$
\end{definition}

The notion of perfect $\Omega $-satisficing equilibrium may be criticized on
the grounds that while in a long horizon game a player's {\em total }loss
from not optimizing is small relative to his overall payoff, this loss may
be large relative to the remaining payoff towards the end of the game.

We now show how Theorem $1^{\prime }$, and hence Proposition \ref{coda}, may
be applied to obtain folk theorems for both notions.

Let $P_{\epsilon }^{\delta }\left( T\right) $ be the set of perfect $%
\epsilon $-equilibrium average payoffs of $G^{\delta }\left( T\right) .$ Let 
$P_{\Omega }^{\delta }\left( T\right) $ be the set of perfect $\Omega $%
-satisficing equilibrium average payoffs of $G^{\delta }\left( T\right) $.
To apply Theorem $1^{\prime }$ and Proposition \ref{coda} in the present
context recall that a strategy combination $\sigma $ in \ $\langle G^{\delta
}\left( T\right) ,H^{\delta }\rangle $ such that ($1$) no player can
profitably deviate in any subgame which starts in one of the first $T$
periods, and ($2$) for any history $\sigma $ induces a subgame perfect
equilibrium of $H^{\delta }$, is a subgame perfect equilibrium of $\langle
G^{\delta }\left( T\right) ,H^{\delta }\rangle .$ A strategy combination $%
\sigma $ in \ $\langle G^{\delta }\left( T\right) ,H^{\delta }\rangle $ such
that ($1$) no player can profitably deviate in any subgame which starts in
one of the first $T$ periods, and ($2^{\prime }$) for any history $\sigma $
induces a perfect $\epsilon $-equilibrium of $H^{\delta },$ is a perfect $%
\epsilon $-equilibrium of $\langle G^{\delta }\left( T\right) ,H^{\delta
}\rangle .$ Similarly, for perfect $\Omega $-satisficing equilibria. This
reasoning can be carried through to Proposition \ref{coda} so that:

\begin{remark}
\label{M}If the threat strategies in Definition \ref{def} are perfect $%
\epsilon $-equilibria rather than perfect equilibria, then in Proposition 
\ref{coda}, $P^{\delta }(T)$ can be replaced by $P_{\epsilon }^{\delta }(T).$
Similarly, if there exists an $\Omega ^{\prime }$ such that the threat
strategies are perfect $\Omega ^{\prime }$-satisficing equilibria, then
there exists an $\Omega $ such that $P^{\delta }(T)$ can be replaced by $%
P_{\Omega }^{\delta }(T)$.
\end{remark}

In light of the two criticisms mentioned above, Theorem \ref{epsilon} below
requires a strategy combination to be both a perfect $\epsilon $-equilibrium
and a perfect $\Omega $-satisficing equilibrium.

\begin{theorem}
\label{epsilon}There exists an $\Omega $ such that, 
\[
\lim_{\epsilon \rightarrow 0}{\em \ }\lim\Sb \delta \rightarrow 1 \\ %
T\rightarrow \infty  \endSb \left[ P_{\Omega }^{\delta }\left( T\right) \cap
P_{\epsilon }^{\delta }\left( T\right) \right] =F^{\ast }.
\]
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
Let $e$ be an equilibrium of $G,$ and let $\widehat{u},\widehat{u}^1,%
\widehat{u}^2,...,\widehat{u}^n$ be elements of $F$ satisfying for all $i$: 
\[
\widehat{u}_i>\widehat{u}_i^i. 
\]
Clearly, given an $\epsilon >0,$ for all outcomes $a$ there exists a $%
T^{\prime }$ and $\delta ^{\prime }$ such that for all $\delta >\delta
^{\prime },$ $\,\,(a,e,e,...,e)$ is a perfect $\epsilon $-equilibrium path
of $G^\delta (T^{\prime })$ and for $\Omega ^{\prime }=\left( \overline{u}-%
\underline{u}\right) $ it is also an $\Omega ^{\prime }$-satisficing
equilibrium. Using the outcomes corresponding to the $n+1$ above points
yields a positive threat in $G^\delta (T^{\prime })$ for all $\delta >\delta
^{\prime }.$ Now if we apply Remark \ref{M} the conclusion of the theorem
holds for $\Omega =k\Omega ^{\prime }$. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

Notice that if $\Omega $ is very small, then the notion of a perfect $\Omega 
$-satisficing equilibrium is satisfactory on its own. The following theorem
is due to Chou and Geanakoplos (1988).

\begin{theorem}
\label{contin}Suppose $G$ is a continuous game with an inefficient
equilibrium. Then for any $\Omega >0,$%
\[
{\em \ }\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb %
P_{\Omega }^{\delta }\left( T\right) =F^{\ast }.
\]
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
For any $\Omega $ choose $a$ such that $U\left( a\right) \gg $ $U\left(
e\right) $ and the maximal deviation $d\left( a\right) <\Omega .$ This is an 
$\Omega $-satisficing equilibrium of $G^{\delta }\left( 1\right) .$ Set $%
H^{\delta }=G^{\delta }\left( 1\right) $ and apply Corollary \ref{inf}
(modified as in Theorem $1^{\prime }$). Since the threat in $G^{\delta
}\left( 1\right) $ is $\Omega $-satisficing, the equilibria of $G^{\delta
}\left( T+1\right) =\left\langle G^{\delta }\left( T\right) ,G^{\delta
}\left( 1\right) \right\rangle $ are $\Omega $-satisficing. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip 

\subsubsection{Games with Incomplete Information\ }

Following Kreps {\em et al.} (1982), Fudenberg and Maskin (1986) have shown
that even if a game has a unique equilibrium, a folk theorem may obtain if a
small amount of incomplete information is introduced. Specifically, they
showed that for every $u\in F^{\ast }$, there is a game of incomplete
information in which $u$ is a sequential equilibrium payoff. Note that in
this statement the type of incomplete information used may vary with the
outcome $u$ being sustained. Indeed, Fudenberg and Maskin (1986) view this
dependence as a possible virtue as it may enable one ``to argue for or
against certain equilibria on the basis of the type of irrationality needed
to support them.''

In this section, we present a stronger version of their result in which all
the outcomes can be sustained with the {\em same} type of irrationality.
Thus, the (optimistic) claim that different outcomes can be distinguished on
the basis of the `needed' irrationality is mistaken. In fact, Theorem 1
shows that this must be the case: once two Pareto comparable equilibria, for
instance, have been identified, these can be used in a suitable end-game to
immediately establish a folk theorem.

To apply Theorem \ref{main} to games of incomplete information recall from
earlier sections that a strategy combination $\sigma $ in $\langle G^{\delta
}\left( T\right) ,H^{\delta }\rangle $ such that ($1$) no player can
profitably deviate in any subgame which starts in one of the first $T$
periods, and ($2$) for any history, $\sigma $ induces a subgame perfect
equilibrium of $H^{\delta }$, is a subgame perfect equilibrium of $\langle
G^{\delta }\left( T\right) ,H^{\delta }\rangle .$ Suppose $H^{\delta }$\ is
a game of incomplete information. Then a strategy combination $\sigma $ in $%
\langle G^{\delta }\left( T\right) ,H^{\delta }\rangle $ such that ($1$) no
player can profitably deviate in any subgame which starts in one of the
first $T$ periods, and ($2^{\prime \prime }$) for any history $\sigma $
induces a sequential equilibrium of $H^{\delta },$ is a sequential
equilibrium of conjoined game $\langle G^{\delta }\left( T\right) ,H^{\delta
}\rangle .$ Thus:

\begin{remark}
\label{seq}If the threat strategies in Definition \ref{def} are sequential
equilibria, then in Theorem \ref{main} $\Pi ^{\delta }(T)$ can be replaced
by the set of sequential equilibrium payoffs of $\langle G^{\delta }\left(
T\right) ,H^{\delta }\rangle .$
\end{remark}

\begin{theorem}
For all $T$ there exists a game of incomplete information $G^{\delta }\left(
T,\epsilon \right) $ in which with probability $\left( 1-\epsilon \right) $
each player's payoffs are the same as in $G^{\delta }\left( T\right) $ and 
\[
\lim_{\epsilon \rightarrow 0}\lim_{\delta \rightarrow 1}\lim_{T\rightarrow
\infty }Seq^{\delta }\left( T,\epsilon \right) =F^{\ast },
\]
where $Seq^{\delta }\left( T,\epsilon \right) $ is the set of sequential
equilibrium payoffs of $G^{\delta }\left( T,\epsilon \right) .$
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%} }%
%BeginExpansion
\proof%
%
%EndExpansion
Let $G^\delta \left( Q,\epsilon \right) $ be the $Q $ period game of
incomplete information in which each player is `rational' with probability $%
\left( 1-\epsilon \right) $ and with probability $\epsilon $ is an
`irrational' player who is completely indifferent among all outcomes.

Fix some equilibrium $e$ of $G$ satisfying $U\left( e\right) \gg 0$.%
\footnote{%
The assumption that $G$ has an equilibrium such that $U\left( e\right) \gg 0$
is made only for convenience.} Let $u\in F^{\ast }$ and let $a\in A$ be such
that $U\left( a\right) =u.$ Consider the following behavior strategies.\
\smallskip 

\noindent {\bf Irrational player }$i.$

{\bf I1.} Play $a_i$ in period $1$. If each player $j$ plays $a_j$ in period 
$1,$ then play $e_i$ for the remaining $Q-1$ periods of the game at all
information sets.

{\bf I2. }Suppose that some player $j$ does not play $a_j$ in period $1,$
and indeed let $j$ be the lowest indexed such player. Then:

\begin{itemize}
\item  In period $t=2:$ (effectively) minmax $j$

\item  In period $t>2:$

\begin{itemize}
\item  if for all $\tau $ such that $2\leq \tau <t,$ all players have
minmaxed $j$ then minmax $j$ in period $t;$

\item  if there is a $\tau ,$ $2\leq \tau <t,$ such that some player did not
minmax $j$, then play $e_{i}$ in period $t.$\smallskip\ 
\end{itemize}
\end{itemize}

\noindent {\bf Rational player }$i.$

{\bf R1.} Play $a_i$ in period $1$. If each player $j$ plays $a_j$ in period 
$1,$ then play $e_i$ for the remaining $Q-1$ periods of the game at all
information sets.

{\bf R2}. Suppose that some player $j$ does not play $a_j$ in period $1,$
and let $j$ be the lowest indexed such player.

\begin{itemize}
\item  In period $t>2$, if there is a $\tau ,$ $2\leq \tau <t,$ such that
some player did not minmax $j,$ then play $e_{i}$ in period $t.$

\item  Otherwise for $t\geq 2,$ all rational players play to a particular
sequential equilibrium derived under the restriction that all players'
strategies conform to the above restrictions.\smallskip \footnote{%
That is, define a new game in which the players' strategy spaces are as in
the original game but with the above restrictions. This is a well-defined
game with a sequential equilibrum.}
\end{itemize}

We now verify that the above constitutes a sequential equilibrium. Since
irrational players are always indifferent, we need only concern ourselves
with rational players.

When the players are playing to $e,$ their beliefs are irrelevant. At other
times, by construction their beliefs are sequentially consistent.

Following period $1,$ all players are either at a single period best
response, or by construction cannot gain by deviating.

We now verify that for $Q$ large enough playing $a_i$ is strictly optimal in
period $1$ when $\delta =1$. Playing $a_i$ yields 
\begin{equation}
u_i\left( a\right) +\left( Q-1\right) u_i\left( e\right) .  \label{p1}
\end{equation}
Deviating (once) yields a payoff which is bounded above by 
\begin{equation}
\overline{u}+\epsilon ^{n-1}\left( Q-1\right) 0+\left( 1-\epsilon
^{n-1}\right) \left[ \overline{u}+\left( Q-2\right) u_i\left( e\right) %
\right]  \label{d1}
\end{equation}
where $\overline{u}$ is the maximum payoff of any player in $G.$

(\ref{d1}) $<$ (\ref{p1}) for large enough $Q$.

Thus, we have shown that for all $u\in F^{\ast },$ there exists a $\overline{%
Q}$ such that for all $Q>\overline{Q},$ there is a sequential equilibrium of 
$G^{\delta }(Q,\epsilon )$ which results in a stream of payoffs $\left(
u,U\left( e\right) ,...,U\left( e\right) \right) .$

Now let $\widehat{u},\widehat{u}^{1},\widehat{u}^{2},...,\widehat{u}^{n}$ be
elements of $F^{\ast }$ satisfying for all $i$: 
\[
\widehat{u}_{i}>\widehat{u}_{i}^{i}. 
\]
We have found $n+1$ sequential equilibrium payoffs of $G^{\delta
}(Q,\epsilon )$ which show that $G^{\delta }(Q,\epsilon )$ has a positive
`sequentially perfect threat.'

An arbitrarily large threat can be obtained by patching together sequential
equilibria of $G^{\delta }(Q\,,\epsilon ),$ say $k$ times, to obtain
sequential equilibria of $H^{\delta }\equiv \langle G^{\delta }(Q\,,\epsilon
),...,\,k$ times$,...,G^{\delta }(Q\,,\epsilon )\rangle .$ The resulting
strategy combination is a sequential equilibrium$.$ Remark \ref{seq} shows
that Theorem \ref{main} may be applied. Finally, note that a sequential
equilibrium of $\langle G^{\delta }\left( T\right) ,H^{\delta }\rangle $ is
a sequential equilibrium of a $T+kQ$ period game of incomplete information
(in this game of incomplete information, the irrationality manifests itself
independently every $kQ$ periods). 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

Notice that in the above proof, the incomplete information is introduced
only towards the end of the game. In contrast, the proof in Fudenberg and
Maskin (1986) (and the earlier work of Kreps {\em et al.} (1982)) introduces
this incomplete information throughout. Thus, whereas this latter work is
often characterized as allowing for ``irrationality,'' our theorem is
perhaps more aptly described as allowing for ``senility'' on the part of the
players.\footnote{%
We thank Drew Fudenberg for suggesting this interpretation.}

\subsection{Infinitely Repeated Games}

\subsubsection{Stationary Discounting}

For infinitely repeated games with discounting, the following generalization
of the theorem of Fudenberg and Maskin (1986) is due to Wen (1994).

\begin{theorem}
\label{fm} 
\[
\lim_{\delta \rightarrow 1}P^{\delta }\left( \infty \right) =F^{\ast }
\]
\end{theorem}

Theorem \ref{fm} follows from Theorem \ref{main} if $G^\delta \left( \infty
\right) $ can be shown to have an arbitrarily large threat as $\delta
\rightarrow 1.$ To see this set $H^\delta =G^\delta \left( \infty \right) ,$
and note that a perfect equilibrium payoff of $\langle G^\delta \left(
T\right) ,H^\delta \rangle $ is a perfect equilibrium payoff of $G^\delta
\left( \infty \right) .$

If $G$ has (recursively) distinct equilibrium payoffs for each player then
an arbitrarily large threat can be constructed by patching together
single-shot equilibria in much the same manner as in the finite case. If $G$
has an inefficient equilibrium $e$ this threat can be constructed as
follows: Let $a$ be such that $u\left( a\right) \gg u\left( e\right) .$ Let $%
\overline{s}$ be the strategies: each player $i$ plays $a_i$ so long as all
others do; if anyone deviates play $e_i$ forever. Let $\underline{s}$ be $e$
repeated forever. For large $\delta $ these strategies form an arbitrarily
large threat.

If $G$ has a single equilibrium which is efficient Theorem \ref{main} may
still be applied, however it appears that it is then no easier to establish
that $G^{\delta }\left( \infty \right) $ has an arbitrarily large threat
than it is to establish Theorem \ref{fm} directly (the latter can be done by
setting $T=\infty $ and $Q=0$ in the proof of Theorem \ref{main}).\footnote{%
We note that in the class of continuous games with smooth payoffs, the
efficiency of equilibria is a non-generic property (see Dubey (1986)).}

Theorems \ref{frg} and \ref{fm} together confirm a conjecture of Pearce
(1992) that if $G$ has (recursively) distinct equilibrium payoffs then 
\[
\lim_{T\rightarrow \infty }P^1\left( T\right) =\lim_{\delta \rightarrow
1}P^\delta \left( \infty \right) . 
\]
Note, however, that an example in Beno\^{\i}t and Krishna (1987) shows that
even with distinct equilibrium payoffs, for fixed $\delta ,$ it may be that 
\[
\lim_{T\rightarrow \infty }P^\delta \left( T\right) \neq P^\delta \left(
\infty \right) . 
\]

\subsubsection{Non-Stationary Discounting}

The standard model of an infinitely repeated game with a common discount
factor of $\delta $ can be reinterpreted to represent a situation where the
horizon of the game is uncertain and $\delta $ represents the probability
that the game will be played in period $t+1$ conditional on it being played
in period $t.$ With probability $\left( 1-\delta \right) $ the game ends in
period $t$. Notice that in this formulation players are assumed to maximize
their expected payoff and the probability of continuation is independent of
the period.

In a recent paper, Bernheim and Dasgupta (1995) have examined repeated games
where the probability of continuation is time dependent; in particular, it
declines over time.\footnote{%
Alternatively, the discount factor declines with time.} Thus let $\delta _t$
represent the probability that the game will be played in period $t$ given
that it was played in period $t-1.$ Let $\left\langle \delta _t\right\rangle 
$ be the sequence of such continuation probabilities and given such a
sequence, let $G^{\left\langle \delta _t\right\rangle }(\infty )$ represent
a repeated game in which the total (expected) payoff vector from a path $%
(a^1,a^2,...)$ is, 
\[
\sum_{t=1}^\infty \left( \prod_{\tau =1}^t\delta _\tau \right) U(a^t). 
\]
$G^{\left\langle \delta _t\right\rangle }(\infty )$ is said to be a repeated
game with an{\em \ asymptotically finite horizon} if for all $t,$ $\delta
_t>0$ and $\lim_{t\rightarrow \infty }\delta _t=0.$

Let $\gamma _t$ be a monotonically declining sequence satisfying $%
\lim_{t\rightarrow \infty }\gamma _t=0$ and for fixed $\delta $ and $T$
consider the game $\langle G^\delta (T),G^{\left\langle \delta \gamma
_t\right\rangle }(\infty )\rangle $ which consists of a $T$ period repeated
game followed by an infinitely repeated game with an asymptotically finite
horizon in which the sequence of continuation probabilities is $\left\langle
\delta \gamma _t\right\rangle $.

First, suppose that the constituent game $G$ is finite (that is, all the $%
A_i $'s are finite) and has a{\em \ unique} equilibrium, say $e$. Then for
all $\delta ,$ the game $G^{\left\langle \delta \gamma _t\right\rangle
}(\infty )$ also has a unique perfect equilibrium. This is because there
exists a $c>0$ such that from any $a\neq e$ each player can gain at least $c$
by deviating. Since $\delta _t\rightarrow 0,$ there exists a $T_c$ such that
for all $t\geq T_c,$ no deviations can be punished in the subsequent game
and thus no $a\neq e$ can be played after period $T_c.$ The fact that this
is the only perfect equilibrium path in the overall game now follows from
backwards induction.

Second, if the constituent game $G$ has (recursively) distinct equilibrium
payoffs, then the arguments of the section on finitely repeated games may be
applied to derive a folk theorem for $\langle G^\delta (T),G^{\left\langle
\delta \gamma _t\right\rangle }(\infty )\rangle $ as $\delta \rightarrow 1$
and $T\rightarrow \infty .$

Finally, suppose that the game $G$ has a continuum of strategies and that $G$
has a unique equilibrium $e$. When can a folk theorem like result be derived
for the game $\langle G^{\delta }(T),G^{\left\langle \delta \gamma
_{t}\right\rangle }(\infty )\rangle $ as defined above? The answer depends
on how fast the continuation probabilities are declining. Say that the
sequence of continuation probabilities $\left\langle \delta
_{t}\right\rangle $ declines {\em slowly} if 
\[
\lim_{T\rightarrow \infty }\sum_{t=1}^{T}2^{-t}\ln \delta _{t}>-\infty . 
\]
Suppose that $e$ is inefficient. Bernheim and Dasgupta (1995) then show that 
$G^{\left\langle \delta _{t}\right\rangle }(\infty )$ has a non-trivial
equilibrium (that is, other than playing the one-shot equilibrium $e$
repeatedly) {\em only if }$\left\langle \delta _{t}\right\rangle $ declines
slowly.\footnote{%
Some additional conditions are also needed for this result: the payoff
functions and the best-response functions must be twice continuously
differentiable and the equilibrium must be regular. See Bernheim and
Dasgupta (1995) for details.}

They also prove the following folk theorem:

\begin{theorem}
Suppose that $G$ is a continuous game with an inefficient equilibrium. If $%
\left\langle \gamma _{t}\right\rangle $ declines slowly then, 
\[
\lim_{\delta \rightarrow 1}\lim_{T\rightarrow \infty }\Pi ^{\delta
}(T)=F^{\ast },
\]
where $\Pi ^{\delta }(T)$ is the set of perfect equilibrium average payoffs
in the conjoined game $\langle G^{\delta }(T),G^{\left\langle \delta \gamma
_{t}\right\rangle }(\infty )\rangle .$
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
By Theorem 2 in Bernheim and Dasgupta (1995) the game $G^{\left\langle
\delta \gamma _{t}\right\rangle }(\infty )$ has a perfect equilibrium whose
payoffs Pareto dominate the payoff $U\left( e\right) $ from an inefficient
equilibrium $e$ of $G$. Thus the game $G^{\left\langle \delta \gamma
_{t}\right\rangle }(\infty )$ has a positive threat. Apply Corollary \ref
{inf}. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion

\subsection{Overlapping Generations}

Cr\'{e}mer (1986), Kandori (1992) and Smith (1992) have examined models in
which each player is finitely lived but there is an infinite population of
players who interact in `overlapping generations.'

Consider a model with $n$ {\em types} of players (indexed by $i$) of
different generations (indexed by $r=1,2,...$). Player $\left( i,r\right) $
is the player of type $i$ in the $r$th generation. Let $K>0$ be fixed and
suppose that each player $\left( i,r\right) $ lives for $T>nK$ periods. For $%
r>1,$ player $\left( i,r\right) $ is assumed to be born in period $\left(
i-1\right) K+\left( r-1\right) T+1$ and die in period $\left( i-1\right)
K+\left( r-1\right) T+T.$ Thus, all $n$ players of a given generation $r$
overlap for exactly $T-\left( n-1\right) K$ periods. We will refer to such a
game as $OLG^\delta \left( T,K\right) .$

Define 
\begin{eqnarray*}
P_r^\delta \left( T,K\right) &=&\{u\in F^{*}:\text{there is a perfect
equilibrium of }OLG^\delta \left( T,K\right) \\
&&\text{ in which the payoffs of all generations }1\text{ through }r\text{
is }u\}.
\end{eqnarray*}

The following theorem is similar to results derived by Kandori (1992) and
Smith (1992).

\begin{theorem}
There exists a $K$ such that for every $r,$ 
\[
\lim_{\delta \rightarrow 1}\lim_{T\rightarrow \infty }P_{r}^{\delta }\left(
T,K\right) =F^{\ast }
\]
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
Fix some inefficient equilibrium $e$ of $G$.\footnote{%
We assume that $G$ has an inefficient equilibrium only for convenience.} For
ease of exposition suppose that $n=3.$ We first find two equilibria of $%
OLG^\delta \left( T,K\right) .$ The first is simply $\underline{s}%
=(e,e,\ldots )$, that is a path in which all players play $e.$ $\overline{s}$
is defined as follows.

Let $a^{i}$ be the outcome that is best for a player of type $i$, and let $a$
be such that $U\left( a\right) \gg U\left( e\right) $. For $k_{1}<K$ and $%
k_{2}<K$ consider the $T$ period path beginning with the birth of a type $1$
player: 
\begin{equation}
(\stackrel{k_{2}\text{ periods}}{\overbrace{a^{2},...,a^{2}}},\stackrel{%
K-k_{2}\text{ }}{\overbrace{e,...,e}},\stackrel{K\text{ }}{\overbrace{%
a^{3},...,a^{3}}},\stackrel{T-3K\text{ }}{\overbrace{a,a,...,a}}\stackrel{%
k_{1}}{,\overbrace{a^{1},...,a^{1}}},\stackrel{K-k_{1}\text{ }}{\overbrace{%
e,...,e}}).  \label{olgpath}
\end{equation}
This is repeated in successive generations with the birth of each new player
of type 1.

Any deviation is met by a play of $e$ forever.

For every $k_1$, we can choose $k_2$ to be large enough so that a player of
type 2 cannot gain by deviating in the $k_1$ periods that $a^1$ is played.
For every $k_1$ and $k_2$, $K$ can be chosen large enough so that there is
no gain for a player of type 3 from deviating either in the $k_1$ periods
that $a^1$ is played or in the $k_2$ periods that $a^2$ is played.

Let $M$ be defined as in the statement of Theorem \ref{main} and choose $%
k_{1},k_{2}$ and $K$ large enough so that 
\begin{eqnarray*}
k_{1}\left[ U(a^{1})-U_{1}\left( e\right) \right] &>&M \\
k_{1}\left[ U_{2}(a^{1})-U_{2}\left( e\right) \right] +k_{2}\left[
U_{2}(a^{2})-U_{2}\left( e\right) \right] &>&M \\
k_{1}\left[ U_{3}(a^{1})-U_{3}\left( e\right) \right] +k_{2}\left[
U_{3}(a^{2})-U_{3}\left( e\right) \right] +K\left[ U_{3}(a^{3})-U_{3}\left(
e\right) \right] &>&M
\end{eqnarray*}
and the deviations of the previous paragraph are not profitable.

Finally, choose $T$ large enough so that no player can profitably deviate in
the remaining periods.

Fix a generation $r$ and let $G_{r}^{\delta }\left( T-3K\right) $ be a
finitely repeated game among the players of generation $r.$ For sufficiently
large $T$ and $\delta ,$ let $H^{\delta }\ $be the $OLG^{\delta }\left(
T,K\right) $ that begins when a type $1$ player of generation $r$ is $T-K$
periods old. $H^{\delta }$ has a threat of $M$. Applying Theorem \ref{main}
to $\langle G_{r}^{\delta }\left( T-3K\right) ,H^{\delta }\rangle $ shows
that any payoff $u>0$ and a payoff $u^{\prime }\ll u$ can be sustained in
this game when $T$ and $\delta $ are large. Let $c$ be the outcome which
results in $u,$ and $c^{\prime }$ be the outcome which results in $u^{\prime
}.$

We can now construct threats which yield the players in generation $r-1$ a
payoff of (approximately) $u,$ and in which the play for generation $r$ is
like (\ref{olgpath}), but with $c$ replacing $a$ along the path, and with $%
c^{\prime }$ replacing $e$ as the punishment for a deviation from $c.$
Continuing in this manner for earlier generations establishes the theorem. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion

\section{Extensions}

In this section we indicate how the main result may be extended in a few
directions.

\subsection{Unobservable Mixed Strategies}

In this appendix we show that our main result, Theorem 1, continues to hold
if mixed strategies are unobservable. The basic idea of the proof is similar
to that given by Fudenberg and Maskin (1986) for infinitely repeated games:
punishing players are kept indifferent on the support of the minmax (mixed)
strategy. For this result we suppose that the game $G$ is finite.

Let $\Pi _u^\delta (T)$ denote the set of perfect equilibrium average
payoffs when mixed strategies are unobservable.\bigskip\ 

\noindent {\bf Theorem A1} {\em There exists an} $M$ {\em such that if for
all large} $\delta ,$ $H^{\delta }$ {\em has a threat of} $M$ {\em then} 
\[
\lim_{\delta \rightarrow 1}\lim_{T\rightarrow \infty }\Pi _{u}^{\delta
}(T)=F^{\ast }. 
\]

The proof of Theorem A1 is given in the appendix. It makes essential use of
the fact that players can coordinate their actions by means of public
randomization (correlation). Gossner (1995) demonstrates a folk-theorem for
finitely repeated games without discounting, $G^{1}\left( T\right) $, when
mixed strategies are not observable and public randomization is not allowed.
He makes use of Blackwell's approachability theorem, in order to construct
the equilibrium strategies and in this construction seems to need the
assumption that the set of feasible payoffs is full dimensional. Fudenberg
and Maskin (1991) show that the use of public randomization is not needed
for the folk theorem for infinitely repeated games with discounting.

\subsection{Nash Equilibria}

A simple modification of our framework can also accommodate {\em Nash}
equilibrium folk theorems. Instead of requiring that $H^{\delta }$ have a
sufficiently large (perfect equilibrium) threat, the weaker condition that $%
H^{\delta }$ have a Nash equilibrium whose payoffs are sufficiently greater
than minmax levels (of $H^{\delta }$ ) is enough to establish a Nash
equilibrium analog of Theorem $1^{\prime }$ (along the lines of Beno\^{i}t
and Krishna (1987)).

Let $\underline{V}_{i}^{\delta }$ denote player $i$'s minmax payoff in $%
H^{\delta }.$ We say that $H^{\delta }$ has a {\em Nash threat }of $M$ if
there exists a Nash equilibrium $s$ of $H^{\delta }$ satisfying for all $i,$%
\[
\left[ V_{i}^{\delta }(s)-\underline{V}_{i}^{\delta }\right] \geq M. 
\]
Let ${\frak N}^{\delta }\left( T\right) $ denote the set of Nash equilibrium
payoffs of the game $\langle G^{\delta }\left( T\right) ,H^{\delta }\rangle
. $ Then we obtain:

\begin{theorem}
\label{Nash}There exists an $M$ such that if for all large $\delta ,$ $%
H^{\delta }$ has a Nash threat of $M$ then 
\[
\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb {\frak N}%
^{\delta }\left( T\right) =F
\]
\end{theorem}

Observe that in Theorem \ref{Nash} $F$ replaces $F^{\ast }.$

\subsection{Frequent Response Games}

One recommendation for a finite model over an infinite model is that agents
typically do not live forever. However, neither do they have extremely long
albeit finite lives. Nevertheless, even with a short horizon, say, fixed at
one year, the players may move frequently, say daily. We now establish a
folk theorem for such situations.

Consider a game $G.$ Suppose the payoff function $U$ refers to annual flow
payoffs; that is, $U\left( a\right) $ is the payoff when all players play $a$
throughout the year. Similarly, let $\delta $ refer to the annual discount
rate.

If players move once at the beginning of the year and are not allowed to
revise their moves, the payoff received at the end of the year is $U\left(
a\right) $ and its value discounted to the beginning of the year is $\delta
U\left( a\right) .$

Now suppose that players can move more frequently in this {\it same} one
year game. For instance, if they moved twice a year, and there were no
discounting then their semi-annual payoff from playing $a$ in any period
would be $\frac 12U\left( a\right) $. With discounting their semi-annual
payoff would be the discounted average $\frac{\sqrt{\delta }}{1+\sqrt{\delta 
}}U\left( a\right) .$

More generally, if players move $K$ times during the course of the year and
the path $(a^1,a^2,...,a^K)$ results, the discounted total payoff at the
beginning of the year is 
\[
\sum_{k=1}^K\delta ^{\frac kK}\frac{(1-\delta ^{\frac 1K})}{\delta ^{\frac
1K}\left( 1-\delta \right) }\delta U(a^k). 
\]
By writing $\widehat{\delta }_K\equiv \delta ^{\frac 1K}$ and $\widehat{U}%
_{K,\delta }(a^k)\equiv \frac{(1-\delta ^{\frac 1K})}{\delta ^{\frac
1K}\left( 1-\delta \right) }\delta U(a^k)$ this can be rewritten in a
familiar form as, 
\[
\sum_{k=1}^K\widehat{\delta }_K^k\widehat{U}_{K,\delta }(a^k). 
\]

Notice that with this specification, the one-period ($\frac 1K$th of a year)
payoff function is $\widehat{U}_{K,\delta }\equiv \frac{(1-\delta ^{\frac
1K})}{\delta ^{\frac 1K}\left( 1-\delta \right) }\delta U$, the discounted
average of an annual payoff function $U.$ Furthermore, for all $\delta ,$ $%
\lim_{K\rightarrow \infty }\widehat{\delta }_K=1.$

Call the game described above a game with $K${\em -responses }denoted by $%
G_K^\delta (1)$, and let $\Gamma _K^\delta $ be the game which consists of $%
G_K^\delta (1)$ followed by an end-game $H^\delta .$ The total payoff from
the path $(a^1,a^2,...,a^K,s)$ is, 
\[
\sum_{k=1}^K\delta ^{\frac kK}\frac{(1-\delta ^{\frac 1K})}{\delta ^{\frac
1K}\left( 1-\delta \right) }\delta U(a^k)+\delta ^{\frac{K+1}K}V^\delta (s) 
\]
or, more compactly, 
\[
\sum_{k=1}^K\widehat{\delta }_K^k\widehat{U}_{K,\delta }(a^k)+\widehat{%
\delta }_K^{K+1}V^\delta (s). 
\]
Let $\Pi _K^\delta \left( 1\right) $ denote the set of perfect equilibrium
payoffs from $\Gamma _K^\delta .$ We obtain the following result\footnote{%
Remarks by Michael Riordon led to this formulation.}:

\begin{theorem}
\label{response}For all $\delta ,$ if there exists an $M>0$ such that $%
H^{\delta }$ has a threat of $M$ then 
\[
\lim_{K\rightarrow \infty }\Pi _{K}^{\delta }\left( 1\right) =F^{\ast }.
\]
\end{theorem}

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
The proof is virtually the same as the proof of Theorem \ref{main}$,$ once
it is recognized that the rescaling of the payoffs from $U$ to $\widehat{U}%
_{K,\delta }$ implies that the threat $M$ needed to sustain $u,$ goes to $0$
as $K$ increases. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

Note that in Theorem \ref{response}, $H^\delta $ can have an arbitrarily
small threat.\ 

Section $4$ derived theorems for finitely repeated games as the length $T$
increased. Using Theorem \ref{response}, one can derive an analogue of each
of these theorems for games of a fixed duration as the frequency of response 
$K$ increases. An overlapping generations folk theorem for short-lived
frequently responding agents can similarly be derived.

\section{Reformulations}

In the game $\langle G^{\delta }\left( T\right) ,H^{\delta }\rangle ,$ $%
G^{\delta }\left( T\right) $ was followed by an end-game $H^{\delta }$ and
in applying Theorem \ref{main}, $H^{\delta }$ was itself taken to be a
repeated game. In this section we present suggest some alternative
formulations.

\subsection{Games of Division}

Let $H^\delta $ be a {\em game of division} in which players `split a pie'
of size $L.$ That is, the players simultaneously announce an $x\in {\bf R}%
^n:\sum_{i-1}^nx_i=L.$ If the players make the same announcement they
receive this payoff, otherwise they receive $0.$ Call such an end-game a 
{\em game of division with a pie of size L. }

As an example consider two players engaged in an enterprise which has the
features of a prisoners' dilemma $D$: 
\[
\begin{tabular}{|r|r|}
\hline
$0,0$ & $5,-3$ \\ \hline
$-3,5$ & $2,\quad 2$ \\ \hline
\end{tabular}
\]
Suppose the players' discount factor comes from a bank interest rate and let
each player deposit to a joint bank account an amount greater than $3\delta
^{T+1}$, say, $4\delta ^{T+1}$ at the beginning of the game $D^{\delta
}\left( T\right) $. For large $T,$ these deposits are infinitesimal; the
bank account grows to an amount $8$ at the end of the game. Let the players
use this bank account at the end to play a game of division with a pie of
size $8.$ At the end of the game, $\left( 4,4\right) ,$ $\left( 8,0\right) $
and $\left( 0,8\right) $ are possible divisions of the pie. Thus a threat of 
$4$ is available to discipline each player's behavior in the period $T$.
Corollary \ref{inf} implies that for large $\delta $ and $T,$ any feasible
individually rational payoff is then sustainable in the game $D^{\delta
}\left( T\right) $.

For a game with a fixed length, but frequent responses Theorem \ref{response}
yields the following strong result.

\begin{proposition}
Let $G_{K}^{\delta }\left( 1\right) $ be a game with $K$ responses. If the
end-game $H^{\delta }$ is a game of division with a pie of positive size
then 
\[
\lim\Sb \delta \rightarrow 1 \\ K\rightarrow \infty  \endSb \Pi _{K}^{\delta
}\left( 1\right) =F^{\ast }.
\]
\end{proposition}

In particular, if players move frequently enough in a prisoner's dilemma,
cooperation can be sustained with any positive pie.

For continuous games we also have a strong result, similar to Theorem \ref
{contin}.

\begin{proposition}
\label{pie}Let $G$ be a continuous game with an inefficient equilibrium. If
the end-game $H^{\delta }$ is a game of division with a pie of positive size
then 
\[
\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb \Pi ^{\delta
}(T)=F^{\ast }.
\]
\end{proposition}

Recall the standard linear Cournot oligopoly model. This has a unique
equilibrium if repeated any finite number of times. Nonetheless, Proposition 
\ref{pie} implies that if the firms have a penny to split at the end, then
for large $\delta $ any feasible individually rational payoff is sustainable
with enough repetitions, a result similar to that of Conlon (1994).

\subsection{Exogenous Payoffs}

Suppose that after the end of the repeated game $G^\delta \left( T\right) $
players receive additional payoffs according to the exogenously specified
function $h:A^T\rightarrow {\bf R}^n.$ Specifically, the total payoff from a
path $(a^1,a^2,...,a^T)$ is: 
\[
\left[ \sum_{t=1}^T\delta ^tU(a^t)\right] +\delta ^{T+1}h(a^1,a^2,...,a^T). 
\]

Some possible interpretations of the function $h$ are given below.\footnote{%
Kandori's (1992) model of a finitely repeated game with `bonding' is quite
similar. However, his model cannot be used to derive the various folk
theorems of previous sections. The reasons for this are the same as those
discussed in Smith (1992).}

\paragraph{Games with a Bonus - ``The Gold Watch''}

Let $h$ be a {\em bonus} payoff contingent on actions taken during the
course of a finitely repeated game. For any $u\in F^{*},$ there is a
contract specifying a strategy combination $\sigma $ and a payment of size $%
M $ to the players contingent on $\sigma $ being followed, such that $u$ is
sustainable. Although this does not follow directly from Theorem \ref{main}
exactly as stated, it is immediately clear from its proof, since $h$
functions exactly as $H^{\delta }.$

Employment and other contracts which specify bonus payments (such as
pensions and buyouts) contingent on certain behavior may be functioning in
this role. Note that Corollary \ref{inf} and Theorem \ref{response} imply
that for many games this payment $M$ may be quite small.

In many companies, it is customary to reward long-time employees with a gift
of a gold watch at retirement. While this reward is a pittance relative to
lifetime wages, it may well function as an appropriately sized bonus.%
\footnote{%
We thank Matthew Spitzer for suggesting the gold watch application.}

\paragraph{Commitments}

Chou and Geanakoplos (1988) propose a model in which players can exogenously
commit to behave in a particular manner in the last few periods of a
finitely repeated game. The function $h$ can be viewed as resulting from
such a commitment.\footnote{%
Starting with this formulation they derive Theorem 4 and rederive Theorem 2.
Notice that in a similar vein we could have used Theorem 2 as the starting
point from which to derive all the theorems of Section 4. Indeed,
Proposition \ref{coda} is a simple consequence of Theorem 2.}

\paragraph{Psychological Costs}

Now suppose $h$ represents a (small) psychological cost. Consider the above
prisoners' dilemma $D.$ Suppose that after $T$ periods of cooperation each
player feels a psychological cost of $3$ from defecting. Notice that this
cost is small relative to the total payoff in the repeated game.
Nonetheless, it is sufficient to permit cooperation to be sustained.

\section{Conclusion}

Our earlier work established that if the stage game has distinct equilibrium
payoffs, a folk theorem can be derived (Beno\^{i}t and Krishna (1985)). This
paper extends that idea: The distinct payoffs in the stage game enables the
construction of sufficiently severe threats in an `end-game,' and our main
result (Theorem \ref{main}) essentially takes these end-game threats as a
starting point.

The utility of Theorem \ref{main} should be apparent: All the major folk
theorems can be recast so that they are simple consequences of this result.

\appendix 

\section{Appendix}

\subsection{Proof of Theorem A1}

In this appendix we show that our main result, Theorem 1, continues to hold
if mixed strategies are unobservable. The basic idea of the proof is similar
to that given by Fudenberg and Maskin (1986) for infinitely repeated games:
punishing players are kept indifferent on the support of the minmax (mixed)
strategy. For this result we suppose that the game $G$ is finite.

Let $\Pi _u^\delta (T)$ denote the set of perfect equilibrium average
payoffs when mixed strategies are unobservable.\bigskip\ 

\noindent {\bf Theorem A1} {\em There exists an} $M$ {\em such that if for
all large} $\delta ,$ $H^{\delta }$ {\em has a threat of} $M$ {\em then} 
\[
\lim_{\delta \rightarrow 1}\lim_{T\rightarrow \infty }\Pi _{u}^{\delta
}(T)=F^{\ast }. 
\]

%TCIMACRO{
%\TeXButton{Proof}{\proof%
%}}%
%BeginExpansion
\proof%
%
%EndExpansion
Recall that for every player $i$ the set 
\[
N\left( i\right) =\left\{ j\in N:U_{j}=\alpha ^{ji}U_{i}+\beta ^{ji},\text{ }%
\alpha ^{ji}>0\right\} 
\]
consists of those players whose payoffs are positive affine transformations
of $i$'s payoff. This defines a partition of $N$ into, say, $K$ equivalence
classes: $N=N\left( i_{1}\right) \cup N\left( i_{2}\right) \cup ...\cup
N\left( i_{K}\right) .$

Choose exactly one player from each member of the partition . Suppose the
players so chosen are $i_{1},i_{2},...,i_{K}$ and without loss of
generality, rename these $1,2,...,K.$ Define $K=\left\{ 1,2,...,K\right\} .$

For all $j,k\in N$ if $j\in N\left( k\right) $ we will say that $j$ and $k$
are {\em equivalent players}. By construction, for every $j\in N$ there
exists a unique $k\in K$ such that $j$ and $k$ are equivalent.

Let $u\in F^{\ast },$ $u\gg 0.$ There exist $K$ vectors $%
u^{1},u^{2},...,u^{K}$ in $F^{\ast }$ satisfying $u^{k}\gg 0$ such that for
all $k,l\in K,$ $k\neq l,$ 
\begin{equation}
u_{k}^{k}<u_{k}^{l}.  \label{i}
\end{equation}
(as in Abreu, Dutta and Smith (1994)). \qquad

Fix a player $i\in K\ $and for each $k\in K,$ $k\neq i$ let $x^{ik}\in
F^{\ast }$ be such that 
\begin{equation}
\begin{array}{cc}
x_{k}^{ik}\neq u_{k}^{i}\text{ and }x_{k}^{ik}>u_{k}^{k}\text{ } &  \\ 
x_{h}^{ik}=u_{h}^{i} & \text{if }h\in K,\text{ }h\neq k
\end{array}
\label{xik}
\end{equation}
(Such a vector $x^{ik}$ exists since for all $h\in K,$ $h\neq k,$ it is the
case that $k\notin N\left( h\right) $.)

Let $a$ $\in A$ be such that $U\left( a\right) =u.$ Similarly, for all $i$
let $a^{i}$ $\in A$ be such that $U\left( a^{i}\right) =u^{i}$ and let $%
a^{ik}\in A$ be such that $U\left( a^{ik}\right) =x^{ik}.$

Given a strategy combination $\sigma ,$ say that $j$ is{\em \ observed to
deviate }from a path{\em \ }$\pi _{\tau }^{i}${\em \ }in period{\em \ }$t$
if $\sigma $ calls for the players to play the mixed strategy $\pi _{\tau
}^{i}\left( t\right) ,$ but $j$'s (pure) action is not in the support of the 
$j$th component of $\pi _{\tau }^{i}\left( t\right) $.

Consider the paths defined below (where the probabilities $p^{ik}$ and time
periods $Q,\,R,R^{\prime }$ and $T$ will be determined later). First, define

\paragraph{$\protect\pi _{\protect\tau }^{0}:$}

\begin{itemize}
\item 
\begin{itemize}
\item  In periods $\tau ,\tau +1,\tau +2,...,T:$ play $a;$ and

\item  In period $T+1:$ play $s$.
\end{itemize}
\end{itemize}

Next, for every $i\in K,$ define:

\paragraph{$\protect\pi _{\protect\tau }^{i}:$}

\begin{itemize}
\item 
\begin{itemize}
\item  In periods $\tau ,\tau +1,\tau +2,...,\tau +R:$ play $m^{i};$

\item  In periods $\tau +R+1,\tau +R+2,...,\tau +R+R^{\prime }:$ if the
observed outcome path in the first $R$ periods is $\alpha ^{\prime }\in
\left( \limfunc{supp}m^{i}\right) ^{R},$ for each $k\in K$ such that $k\neq i
$ $:$

\begin{itemize}
\item  play $a^{ik}$ with probability $p^{ik}\left( \alpha ^{\prime }\right)
,$ and

\item  play $a^{i}$ with probability $1-\sum\Sb k\in K \\ k\neq i \endSb %
p^{ik}\left( \alpha ^{\prime }\right) ;$
\end{itemize}

\item  In periods, $\tau +R+R^{\prime }+1,\tau +R+R^{\prime }+2,...,T:$ play 
$a^{i};$ and

\item  In period $T+1:$ play the equilibrium $s$ of $H^{\delta }.$
\end{itemize}
\end{itemize}

Now consider the following strategies.

\begin{itemize}
\item  Start $\pi _{1}^{0}$ and continue to follow $\pi _{1}^{0}$ if no one
deviates.

\item  If $j\in N$ is observed to deviate from $\pi _{\tau }^{l}$ in period $%
t\leq T-Q$, start $\pi _{t+1}^{i},$ where $i\in K$ is equivalent to $j.$

\item  If player $j\in N$ is the first player observed to deviate from $\pi
_{\tau }^{l}$ in some period $t$, $T-Q<t\leq T$, then play an equilibrium $e$
of $G$ in each of the periods $t+1,t+2,...,T$ and play $s^{j}$ in period $T+1
$.
\end{itemize}

We now show that there exist probabilities $p^{ik}$ such that for large
enough $\delta ,$ $Q,\,R,R^{\prime }$ and $T,$ these are perfect equilibrium
strategies. It is sufficient to verify that no player wants to deviate from
these strategies just once and conform thereafter.

Choose $R$ so that for all $j\in N:$%
\[
\left( R+1\right) u_{j}>\overline{u} 
\]
where $\overline{u}$ is the maximum payoff of any player in $G$. Such an $R$
exists since $u_{j}>0.$ Choose $\delta _{R}$ so that for all $\delta >\delta
_{R},$ for all $j\in N:$%
\[
\frac{\left( 1-\delta ^{R+1}\right) }{\left( 1-\delta \right) }u_{j}>%
\overline{u} 
\]
and for all $j\in N:$%
\[
\left( 1-\delta ^{R+1}\right) \underline{u}+\delta ^{R+1}u_{j}^{i}>0 
\]
where $\underline{u}$ is the minimum payoff of any player in $G$ and $i\in K$
is equivalent to $j.$

\ 

\noindent {\bf Claim:}{\sc \ }{\em There exists an} $R^{\prime }$ {\em and a}
$\delta _{R^{\prime }}$ {\em such that for all} $\delta >\delta _{R^{\prime
}}{\em ,}$ {\em \ for all }$i,k\in K,$ $k\neq i${\em \ and for all }$\alpha
^{\prime },\alpha ^{\prime \prime }\in \left( \limfunc{supp}m^{i}\right)
^{R} ${\em \ there exist }$p^{ik}(\alpha ^{\prime })${\em \ and }$%
p^{ik}(\alpha ^{\prime \prime })${\em \ such that:} 
\begin{eqnarray}
&&U_{k}^{R}(\alpha ^{\prime })+\delta ^{R+1}\frac{(1-\delta ^{R^{\prime }})}{%
\left( 1-\delta \right) }\left( p^{ik}(\alpha ^{\prime })x_{k}^{ik}+\left(
1-p^{ik}(\alpha ^{\prime })\right) u_{k}^{i}\right)  \nonumber \\
&=&U_{k}^{R}(\alpha ^{\prime \prime })+\delta ^{R+1}\frac{(1-\delta
^{R^{\prime }})}{\left( 1-\delta \right) }\left( p^{ik}(\alpha ^{\prime
\prime })x_{k}^{ik}+\left( 1-p^{ik}(\alpha ^{\prime \prime })\right)
u_{k}^{i}\right)  \label{indiff}
\end{eqnarray}
\[
\text{and }\sum\Sb k\in K  \\ k\neq i  \endSb p^{ik}\left( \alpha ^{\prime
}\right) <1. 
\]
{\em where }$U_{k}^{R}(\alpha ^{\prime })\equiv \sum_{r=1}^{R}\delta
^{r}U_{k}\left( a^{\prime }\left( r\right) \right) ${\em \ is player }$k$%
{\em 's total payoff from the }$R${\em \ period path }$\alpha ^{\prime }.$%
{\em \ }$U_{k}^{R}(\alpha ^{\prime \prime })${\em \ is defined similarly.}%
\medskip\ 

\noindent {\bf Proof of claim: }

First, observe that there exists an $R^{\prime }$ and a $\delta _{R^{\prime
}}$ such that for all $\delta >$ $\delta _{R^{\prime }},$ for all $i,k\in K,$
$i\neq K:$ 
\begin{equation}
\frac{\delta \left( 1-\delta ^{R}\right) }{\delta ^{R+1}\left( 1-\delta
^{R^{\prime }}\right) }\left( \overline{u}-\underline{u}\right) <\frac{1}{K}%
\left| x_{k}^{ik}-u_{k}^{i}\right| .  \label{delta1}
\end{equation}
(This is because $\left[ \delta \left( 1-\delta ^{R}\right) /\delta
^{R+1}\left( 1-\delta ^{R^{\prime }}\right) \right] \rightarrow R/R^{\prime
} $ as $\delta \rightarrow 1.$)

Let $\overline{\alpha }^{k}$ $\in \left( \limfunc{supp}m^{i}\right) ^{R}$ be
the $R$ period path that is best for player $k$ and let $\alpha $ be an
arbitrary path in $\left( \limfunc{supp}m^{i}\right) ^{R}.$ For any such
path notice that : 
\begin{equation}
0\leq \frac{\left( 1-\delta \right) \left[ U_{k}^{R}(\overline{\alpha }%
^{k})-U_{k}^{R}(\alpha )\right] }{\delta ^{R+1}\left( 1-\delta ^{R^{\prime
}}\right) }<\frac{\delta \left( 1-\delta ^{R}\right) }{\delta ^{R+1}\left(
1-\delta ^{R^{\prime }}\right) }\left( \overline{u}-\underline{u}\right)
\label{indiff2}
\end{equation}

Now consider the expression 
\begin{equation}
\left[ p-p^{ik}(\overline{\alpha }^{k})\right] \left(
x_{k}^{ik}-u_{k}^{i}\right) .  \label{prob1}
\end{equation}

If $x_{k}^{ik}-u_{k}^{i}>0$ set $p^{ik}(\overline{\alpha }^{k})=0$ and
notice that if $p=\frac{1}{K}$ then by (\ref{delta1}) this exceeds the left
hand side of (\ref{indiff2}) and if $p=0$ it is no greater than the left
hand side of (\ref{indiff2}). Thus there exists a $p=p^{ik}(\alpha )\in
\lbrack 0,\frac{1}{K})$ such that the two are equal. Similarly, if $%
x_{k}^{ik}-u_{k}^{i}<0$ set $p^{ik}(\overline{\alpha }^{k})=\frac{1}{K}$ and
notice that if $p=0$ then again by (\ref{delta1}) this exceeds the left hand
side of (\ref{indiff2}) and if $p=\frac{1}{K}$ it is no greater than the
left hand side of (\ref{indiff2}). Thus, again there exists a $%
p=p^{ik}(\alpha )\in \lbrack 0,\frac{1}{K})$ such that the two are equal.

Therefore, $p^{ik}\left( \alpha \right) $'s can be chosen such that for all $%
i,$ for all $k\in K$, $k\neq i$ and for all $\alpha ,$ (\ref{indiff}) holds
and $\sum\Sb k\in K  \\ k\neq i  \endSb p^{ik}\left( \alpha ^{\prime
}\right) <1,$ establishing the claim. $\Box $

\bigskip\ 

For every $i,k\in K,$ $k\neq i$ and every path $\alpha \in \left( \limfunc{%
supp}m^{i}\right) ^{R}$ choose probabilities $p^{ik}(\alpha )$ as in the
claim.

Suppose a player $j\in N$ is observed to deviate from some $\pi _{\tau }^{l}$
and $i\in K$ is equivalent to $j.$ If $\alpha ^{\prime }\in $ $\left( 
\limfunc{supp}m^{i}\right) ^{R}$ is the path in the first $R$ periods of $%
\pi _{t}^{i}$ when $m^{i}$ is played, the payoff to player $k\notin N\left(
i\right) $ is the left hand side of the equation in (\ref{indiff}), whereas
if $\alpha ^{\prime \prime }$ $\in \left( \limfunc{supp}m^{i}\right) ^{R}$
is the path, the payoff is the right hand side of (\ref{indiff}). By
construction these are equal. Thus every player $j\notin N\left( i\right) $
is indifferent among all the paths that lie in $\left( \limfunc{supp}%
m^{i}\right) ^{R}$.

Next observe that from the definition of $m^{i}$ every player in $j\in
N\left( i\right) $ is at a single-period best response when $m^{i}$ is
played.

The verification that the strategies given above form an equilibrium is now
routine. (The fact that the$\ x_{j}^{ij}$'s satisfy (\ref{xik}) is important
here). The remainder of the proof may be completed by following the proof of
Theorem 1 exactly. 
%TCIMACRO{
%\TeXButton{End Proof}{\endproof%
%}}%
%BeginExpansion
\endproof%
%
%EndExpansion
\bigskip

In the proof given above we have made use of the fact that players can
coordinate their actions by means of public randomization (correlation).
Gossner (1995) demonstrates a folk-theorem for finitely repeated games
without discounting, $G^{1}\left( T\right) $, when mixed strategies are not
observable and public randomization is not allowed. He makes use of
Blackwell's approachability theorem, in order to construct the equilibrium
strategies and in this construction seems to need the assumption that the
set of feasible payoffs is full dimensional. Fudenberg and Maskin (1991)
show that the use of public randomization is not needed for the folk theorem
for infinitely repeated games with discounting.

\ 

\begin{thebibliography}{99}
\bibitem{ADS}  Abreu, D., P. K. Dutta and L. Smith (1994): ``The Folk
Theorem for Repeated Games: A NEU Condition,'' {\em Econometrica}, 62, pp.
939-948.

\bibitem{A-S}  Aumann, R. and L. Shapley (1994): ``Long-Term Competition: A
Game Theoretic Analysis,'' in {\em Essays in Game Theory}, edited by N.
Megiddo, Springer-Verlag, pp. 1-15.

\bibitem{BK}  Beno\^{i}t, J-P. and V. Krishna (1985): ``Finitely Repeated
Games,'' {\em Econometrica}, 53, pp. 905-922.

\bibitem{BK2}  Beno\^{i}t, J-P. and V. Krishna (1987): ``Nash Equilibria of
Finitely Repeated Games,'' {\em International Journal of Game Theory}, 16,
pp. 197-204.

\bibitem{BD}  Bernheim, B.\ D. and A. Dasgupta (1995): ``Repeated Games with
Asymptotically Finite Horizons,'' {\em Journal of Economic Theory}, 67, pp.
129-152.

\bibitem{Chou}  Chou, C-F. and J. Geanakoplos (1988) : ``The Power of
Commitment,'' Yale University, {\em Journal of Economic Theory}, forthcoming.

\bibitem{Conlon}  Conlon, J. (1994): ``Cooperation for Pennies,'' mimeo,
University of Mississippi.

\bibitem{Cremer}  Cr\'{e}mer, J. (1986): ``Cooperation in Ongoing
Organizations,'' {\em Quarterly Journal of Economics}, 101, pp. 33-49.

\bibitem{Dubey}  Dubey, P. (1986): ``Inefficiency of Nash Equilibria,'' {\em %
Mathematics of Operations Research}, 11, pp. 1-8.

\bibitem{FM}  Fudenberg, D. and E. Maskin (1986): ``The Folk Theorem for
Repeated Games with Discounting or with Incomplete Information,'' {\em %
Econometrica}, 54, pp. 533-554.

\bibitem{FM2}  Fudenberg, D. and E. Maskin (1991): ``On the Dispensability
of Public Randomization in Discounted Repeated Games,'' {\em Journal of
Economic Theory}, 53, pp. 428-438.

\bibitem{Gossner}  Gossner, O. (1995): ``The Folk Theorem for Finitely
Repeated Games with Mixed Strategies,'' {\em International Journal of Game
Theory}, 24, pp. 95-107.

\bibitem{Kandori}  Kandori, M. (1992): ``Repeated Games Played by
Overlapping Generations of Players,'' {\em Review of Economic Studies}, 59,
pp. 81-92.

\bibitem{KMRW}  Kreps, D., P. Milgrom, J. Roberts and R. Wilson (1982):
``Rational Cooperation in the Finitely Repeated Prisoners' Dilemma,'' {\em %
Journal of Economic Theory}, 27, pp. 245-252.

\bibitem{O-R}  Osborne, M. and A. Rubinstein (1994): {\em A Course in Game
Theory}, Cambridge: MIT\ Press.

\bibitem{Pearce}  Pearce, D. (1992): ``Repeated Games: Cooperation and
Rationality'' Chapter 4 in {\em Advances in Economic Theory: Sixth World
Congress}, Vol. 1 edited by J-J. Laffont, Econometric Society Monographs,
Cambridge University Press, Cambridge, pp. 132-174.

\bibitem{Radner}  Radner, R. (1980): ``Collusive Behavior in Noncooperative
Epsilon Equilibria of Oligopolies with Long but Finite Lives,'' {\em Journal
of Economic Theory}, 22, pp. 136-154.

\bibitem{Rockafellar}  Rockafellar, R., {\em Convex Analysis}, Princeton
University Press, Princeton NJ, 1970

\bibitem{Rubinstein}  Rubinstein, A. (1991): ``Comments on the
Interpretation of Game Theory,'' {\em Econometrica}, 59, pp. 909-924.

\bibitem{Rubin2}  Rubinstein, A. (1994): ``Equilibrium in Supergames,'' in 
{\em Essays in Game Theory}, edited by N. Megiddo, Springer-Verlag, pp.
17-27.

\bibitem{Smith}  Smith, L. (1992): ``Folk Theorems in Overlapping
Generations Games,'' {\em Games and Economic Behavior}, 4, pp. 426-449.

\bibitem{Smith2}  Smith, L. (1995): ``Necessary and Sufficient Conditions
for the Perfect Finite Horizon Folk Theorem,'' {\em Econometrica}, 63, pp.
425-430.

\bibitem{Sorin}  Sorin, S. (1993): ``Repeated Games with Complete
Information,'' Chapter 4 in {\em Handbook of Game Theory}, Volume 1, edited
by R. Aumann and S. Hart, North-Holland, pp. 71-107.

\bibitem{Sorin2}  Sorin, S. (1996): ``Cooperation Through Repetition:
Complete Information,'' in {\em Cooperation: Game Theoretic Approaches},
edited by S. Hart and A. Mas-Colell, Springer-Verlag, pp. 169-198.

\bibitem{Wen}  Wen, Q. (1994): ``The `Folk Theorem' for Repeated Games with
Complete Information,'' {\em Econometrica}, 62, pp. 949-954.
\end{thebibliography}

\end{document}