%Paper: ewp-game/9601001
%From: vxk5@psu.edu (Vijay Krishna)
%Date: Wed, 17 Jan 1996 15:29:25 -0500


--=====================_821935765==_
Content-Type: text/plain; charset="us-ascii"

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


\documentstyle[12pt,thmsb,sw20lart]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{TCIstyle=Article/art4.lat,lart,article}

\input tcilatex
\QQQ{Language}{
American English
}

\begin{document}

\author{Jean-Pierre Beno\^{\i}t\thanks{%
We are grateful to the C. V. 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.} \\
%EndAName
Department of Economics\\
New York University \and Vijay Krishna$^{*}$ \\
%EndAName
Department of Economics\\
Penn State University}
\title{The Folk Theorems for Repeated Games:\\
A Synthesis }
\maketitle

\begin{abstract}
We present a synthesis of various folk theorems for repeated games.
\end{abstract}

\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 horizon 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) for surveys of the area.}

Perhaps the most debated of these aspects concerns the time horizon 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 horizon 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 horizon as a game of infinite duration, and thus infinite
horizon 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 horizon model 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 horizon
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, it is unnecessary. 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 horizon 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 long but
finite horizons are available.

To see that it is not sufficient, consider the following example. Suppose
the discount rate, 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 12$
as $t$ increases.\footnote{%
Thus payoffs from period $t$ are discounted by a factor of $\prod_{\tau
=1}^t\delta _\tau .$} Specifically, given a $\gamma \in \left( 0,1\right) $
let 
\[
\delta _t=\frac 12+\frac{\gamma ^t}2. 
\]
Notice that for all $\gamma ,$ $\lim_{t\rightarrow \infty }\delta _t=$ $%
\frac 12$ and that 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 horizon is infinite, 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 illustrates that the
finite-infinite distinction is of limited use in analyzing or classifying
the strategic possibilities. 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.%
\footnote{%
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
horizon 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.

Finally, rather than focusing attention on the horizon 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.

This paper is organized as follows. 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.

Section 4 derives the various folk theorems for finitely repeated games by
invoking the main result of Section 3. Theorem 2 is the folk theorem for
finitely repeated games in which each player has distinct equilibrium
payoffs (Beno\^{\i}t and Krishna (1985)). Theorem 3 is the recent
generalization to the case where the players have recursively distinct
equilibrium payoffs (Smith (1995)). We then 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
(forthcoming). Finally, we consider games with incomplete information and
derive a result (Theorem 6) along the lines of Fudenberg and Maskin (1986).

Section 5 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). We then consider the recent model of an
infinitely repeated game with a declining discount factor studied by
Bernheim and Dasgupta (1995) (Theorem 8).

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

Section 7 introduces the notion of a `frequent response game' in which the
horizon is fixed but players revise moves rapidly. Section 8 indicates some
possible extensions and Section 9 concludes.

While all of the above results are derived for the case of pure strategies
or alternatively for the case when mixed strategies are observable, in an
appendix we show that our main result, and thus all of the results that stem
from it, remain true even if mixed strategies are not observable.

\section{Preliminaries}

Let $G=(A_1,A_2,...,A_n;\;U_1,U_2,...,U_n)$ be a game 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^{*}=0$ and define: 
\[
F^{*}=\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^{*},$ $u\gg 0.$

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

Let $\overline{u}$ denote the maximum payoff of any player in $G$ and let $%
\underline{u}$ denote the minimum payoff.

$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 discounted
average payoff vector is 
\[
\frac{\left( 1-\delta \right) }{\delta \left( 1-\delta ^T\right) }%
\sum_{t=1}^T\delta ^tU(a^t). 
\]

$G^\delta (\infty )$ denotes the infinitely repeated game with discount
factor $\delta .$

In both $G^\delta (T)$ and $G^\delta (\infty )$ we assume that players can
coordinate their actions by means of a public randomizing device. Initially,
we assume that mixed strategies are observable (alternatively, we can say
that the $A_i$'s themselves subsume all mixing possibilities). In an
appendix we show that all of our results are true even if the mixed
strategies themselves are not observable; rather only the pure strategy
choices of the players may be observed.

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

Wen (1994) easily establishes that for all $\delta $ and $T,$ $P^\delta
\left( T\right) $ $\subseteq F^{*}$ and that for all $\delta ,$ $P^\delta
\left( \infty \right) $ $\subseteq F^{*}.$

\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 $. $H^\delta $ is then
referred to as the {\bf end-game.}
\end{definition}

If $(a^1,a^2,...,a^T,s)$ is a path in $\langle G^\delta \left( T\right)
,H^\delta \rangle $, the resulting discounted average payoff is 
\[
\frac{\left( 1-\delta \right) }{\delta \left( 1-\delta ^{T+1}\right) }\left[
\sum_{t=1}^T\delta ^tU(a^t)+\delta ^{T+1}V^\delta (s)\right] . 
\]

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}A game $H=\left( S_1,...,S_n,V_1,...,V_n\right) $ has a {\bf %
threat}{\em \ }of $M$ if there exist $n+1$ perfect equilibria of $H:\,$ $s,$ 
$s^1,s^2,...,s^n$ satisfying for all $i,$%
\begin{equation}
\left[ V_i(s)-V_i(s^i)\right] \geq M.  \label{threat}
\end{equation}
$\,$ $s,$ $s^1,s^2,...,s^n$ will be referred to as the {\bf threat strategies%
}{\em \ }which yield $M.$
\end{definition}

\bigskip 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 (double) limit of $\Pi
^\delta (T)$ as $\delta \rightarrow 1$ and $T\rightarrow \infty $. In the
statement below, $F^{*}$ is derived from the game $G$.

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

\TeXButton{Proof}{\proof}Let $u\ \in F^{*},$ $u\gg 0.$ From Abreu, Dutta and
Smith (1994) there exist $n$ vectors $u^1,u^2,...,u^n$ in $F^{*},$ $u^i\gg 0$%
, such that for all $i\in N,$ 
\begin{equation}
u_i^i<u_i  \label{i}
\end{equation}
for all $j\notin N(i),$%
\begin{equation}
u_i^i<u_i^j  \label{ii}
\end{equation}
and for all $j\in N(i),$%
\begin{equation}
u_i^i=u_i^j.
\end{equation}

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.$

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). If player $i$ is the
(lowest indexed) player to deviate from $\pi _\tau ^j$ in period $t\leq T-Q,$
follow $\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 to 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.

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}}%
,u_i^j,...,u_i^j,V_i^\delta (s))  \label{dev1}
\end{equation}
On the other hand, if $i$ does not deviate his remaining payoff stream will
be at worst: 
\begin{equation}
(u_i^j,\stackrel{R\text{ periods}}{\overbrace{u_i^j,u_i^j,...,u_i^j}}%
,u_i^j,...u_i^j,V_i^\delta (s))  \label{ndev1}
\end{equation}
(recalling that for $i\in $ $N(j),$ $u_i^j<u_i$).

For large enough $R$ and $\delta $ the discounted value of (\ref{ndev1}) is
greater than that of (\ref{dev1}). Fix $R$ so that this inequality holds for
all $i.$

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%
\text{ periods}}{\overbrace{u_i^i,...,u_i^i}},\stackrel{T-t-Q}{\overbrace{%
u_i^i,...,u_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\text{ periods}}{\overbrace{u_i^j,...,u_i^j}},\stackrel{T-t-Q+1%
}{\overbrace{u_i^j,u_i^j,...,u_i^j}},V_i^\delta (s))  \label{ndev2}
\end{equation}
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.$

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( u\right) $ be a number satisfying $M\left( u\right) >Q\left( 
\overline{u}-\underline{u}\right) $ and 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( u\right) . 
\]
For large enough $\delta ,$ the discounted value of (\ref{ndev3}) is greater
than that of (\ref{dev3}), for all $i$.

Thus, we have shown that for all $u\in F^{*},$ $u\gg 0,$ there exists an $%
M\left( u\right) $ such that if for all large $\delta ,$ $H^\delta $ has a
threat of $M\left( u\right) $ then for all large $T$ and $\delta $, $%
(a,a,...,a,s)$ is an equilibrium path of $\langle G^\delta \left( T\right)
,H^\delta \rangle $.

Now fix $n+1$ points $\widehat{u},$ $\widehat{u}^1,\widehat{u}^2,...,%
\widehat{u}^n$ in $F^{*}$, $\widehat{u}\gg 0,$ $\widehat{u}^i\gg 0,$ with
corresponding outcomes $\widehat{a},$ $\widehat{a}^1,\widehat{a}^2,...,%
\widehat{a}^n,$ such that for all $i\in N,$ 
\begin{equation}
\widehat{u}_i^i<\widehat{u}_i  \label{i}
\end{equation}
and for all $j\notin N(i),$%
\begin{equation}
\widehat{u}_i^i<\widehat{u}_i^j.  \label{ii}
\end{equation}

Let $M=\max \left\{ M\left( \widehat{u}\right) ,M\left( \widehat{u}^1\right)
,M\left( \widehat{u}^2\right) ,...,M\left( \widehat{u}^n\right) \right\} $.

Suppose that for all large $\delta ,\,H^\delta $ has a threat of $M.$ We use
this threat $M$ to construct an arbitrarily large threat $M^{\prime }$. In
fact, 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 ,$ $%
\langle G^\delta \left( T\right) ,H^\delta \rangle $ has a threat of $%
M^{\prime }.$ This follows from the fact that for large $\delta $, $(%
\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$ is large.

Consider an arbitrary $u^{\prime }\in F^{*}$, $u^{\prime }\gg 0,$ and the
game $G^\delta \left( T\right) $ followed by an end-game. As above, $%
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^{\prime }\;(=$ $%
M\left( u^{\prime }\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^{\prime })),H^\delta \rangle $ has a threat $M^{\prime }.$
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^{\prime })),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^{\prime })),H^\delta \rangle $.

Since for large $T$ and $\delta $ the payoff $u^{\prime }$ can obtained in
all but the last $T\left( M^{\prime }\right) +1$ periods of $\langle
G^\delta \left( T\right) ,\overline{H}^\delta \rangle =\langle G^\delta
(T+T(M^{\prime })),H^\delta \rangle $, the resulting discounted average
payoff is approximately $u^{\prime }.$ \TeXButton{End Proof}{\endproof}%
\bigskip 

When $T$ is large, the 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 threat of $M>\inf \left\{ d\left(
a\right) :U\left( a\right) \gg U\left( e\right) \right\} $ then 
\[
\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb \Pi ^\delta
(T)=F^{*}.
\]
\end{corollary}

\TeXButton{Proof}{\proof}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 $. \TeXButton{End Proof}{\endproof}\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 (forthcoming) show that for ``smooth commitment'' games
a folk theorem may obtain with any positive commitment. For more on this see
the {\it extensions }section at the end of this paper.}

\section{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 a positive 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.} Then,
applying Theorem \ref{main} to $\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^{*}. 
\]

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 threat in\thinspace $\,G^\delta (T^{\prime })$. Then 
\[
\lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb P^\delta \left(
T\right) =F^{*}.
\]
\end{proposition}

\subsection{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 the folk theorems are given in
Wen's (1994) `effective minmax formulation.'}

\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^{*}.
\]
\end{theorem}

\TeXButton{Proof}{\proof}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}. \TeXButton{End Proof}
{\endproof}\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^{*}.
\]
\end{theorem}

\TeXButton{Proof}{\proof}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}. 
\TeXButton{End Proof}{\endproof}\bigskip 

\subsection{$\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
^tU(a^t\left( \sigma \right) )\right] \geq \frac{1-\delta }{\delta \left(
1-\delta ^T\right) }\left[ \sum_{t=1}^T\delta ^tU(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 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 ^tU(a^t\left( \sigma \right) )\geq \left[
\sum_{t=1}^T\delta ^tU(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 \ref{main}, 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 
\ref{main} 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, then in Proposition \ref{coda}, $P^\delta (T)$ can be
replaced by $P_\epsilon ^\delta (T).$ Similarly, if the threat strategies
are perfect $\Omega $-satisficing equilibria, $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 for all $\epsilon >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] \supseteq F^{*}.
\]
\end{theorem}

\TeXButton{Proof}{\proof}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, 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 })$. 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 apply Remark \ref{M}. \TeXButton{End Proof}{\endproof}%
\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 (forthcoming).

\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) \supseteq F^{*}.
\]
\end{theorem}

\TeXButton{Proof}{\proof}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} and Remark \ref{M}. \TeXButton{End Proof}
{\endproof}\bigskip

\subsection{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^{*}$, 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) state that
``One may 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 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 .$ Similarly, 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 $\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\Sb \delta \rightarrow 1 \\ T\rightarrow
\infty  \endSb Seq^\delta \left( T,\epsilon \right) =F^{*},
\]
where $Seq^\delta \left( T,\epsilon \right) $ is the set of sequential
equilibrium payoffs of $G^\delta \left( T,\epsilon \right) .$
\end{theorem}

\TeXButton{Proof}{\proof} 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$ 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 
\end{itemize}

We now verify that the above constitutes a sequential equilibrium.

We need only check that rational players are optimizing.

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

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}

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

Thus, we have shown that for all $u\in F,$ 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$ 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 $H^\delta \equiv \langle G^\delta (Q\,,\epsilon ),...,\,k$
times$,...,G^\delta (Q\,,\epsilon )\rangle $, for some $k.$ 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). \TeXButton{End Proof}{\endproof}%
\bigskip 

\section{Infinitely Repeated Games}

\subsection{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^{*}
\]
\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}).

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, in general 
\[
\lim_{T\rightarrow \infty }P^\delta \left( T\right) \neq P^\delta \left(
\infty \right) . 
\]

\subsection{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}^T2^{-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 $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\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb \Pi ^\delta
(T)=F^{*},
\]
where $\Pi ^\delta (T)$ is the set of perfect equilibrium average payoffs in
the game $\langle G^\delta (T),G^{\left\langle \delta \gamma _t\right\rangle
}(\infty )\rangle .$
\end{theorem}

\TeXButton{Proof}{\proof}By Theorem 1 in Bernheim and Dasgupta (1995) the
game $G^{\left\langle \delta \gamma _t\right\rangle }(\infty )$ has a
perfect equilibrium whose payoffs Pareto dominate $U\left( e\right) .$ Thus
the game $G^{\left\langle \delta \gamma _t\right\rangle }(\infty )$ has a
positive threat. Apply Corollary \ref{inf}. \TeXButton{End Proof}{\endproof}

\section{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 all $u$ $\in F^{*},$ 
\[
u\in \lim\Sb \delta \rightarrow 1 \\ T\rightarrow \infty  \endSb P_r^\delta
\left( T,K\right) 
\]
for every $r.$
\end{theorem}

\TeXButton{Proof}{\proof}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 $c^{\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. 
\TeXButton{End Proof}{\endproof}

\section{Frequent Response Games}

One recommendation for a finite horizon model over an infinite horizon 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.$

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:

\begin{theorem}
\label{response}If there exists an $M>0$ such that for all large $\delta ,$ $%
H^\delta $ has a threat of $M$ then 
\[
\lim\Sb \delta \rightarrow 1 \\ K\rightarrow \infty  \endSb \Pi _K^\delta
\left( 1\right) =F^{*}.
\]
\end{theorem}

\TeXButton{Proof}{\proof}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 $M\left( u\right)
,$ the threat needed to sustain $u,$ goes to $0$ as $K$ increases. 
\TeXButton{End Proof}{\endproof}\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 horizon $T$
increased. Using Theorem \ref{response}, one can derive an analogue of each
of these theorems for a fixed horizon as the frequency of response $K$
increases. An overlapping generations folk theorem for short-lived
frequently responding agents can similarly be derived.

\section{Extensions}

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 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 the market interest rate and
let each player contribute $3\delta ^{T+1}$ at the beginning of the game $%
D^\delta \left( T\right) $ . For large $T,$ these contributions are
infinitesimal; they grow to a pie of size $6$ at the end of the game.
Corollary \ref{inf} implies that for large $\delta $ and $T,$ any feasible
individually rational payoff is sustainable in the game $D^\delta \left(
T\right) $ ending with this pie.

For a game with a fixed horizon, 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^{*}.
\]
\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^{*}.
\]
\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}

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}
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.

\paragraph{Commitments}

Chou and Geanakoplos (forthcoming) 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.

\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 an equilibrium whose payoffs are sufficiently greater than
minmax levels (of $H^\delta $ ) is enough to establish a Nash equilibrium
analog of Theorem \ref{main} (along the lines of Beno\^{\i}t and Krishna
(1987)).

\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{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 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\Sb \delta \rightarrow 1  \\ T\rightarrow \infty  \endSb \Pi _u^\delta
(T)=F^{*}. 
\]

\TeXButton{Proof}{\proof}Let $u,u^1,u^2,...,u^n$ in $F^{*},$ $u\gg 0,u^i\gg
0\ be$ such that for all $i\in N,$ 
\[
u_i^i<u_i 
\]
and for all $j\notin N(i),$%
\[
u_i^i<u_i^j. 
\]

For every player $i$ define 
\[
L\left( i\right) =\left\{ j\in N:U_j=\alpha ^{ji}U_i+\beta ^{ji},\text{ }%
\alpha ^{ji}\neq 0\text{ }\right\} . 
\]
(Notice that here we allow $\alpha ^{ji}<0$ and thus $L\left( i\right) $ is
different from $N\left( i\right) $). Consider a partition of $N$ into $K$
equivalence classes: 
\[
N=L(i_1)\cup L(i_2)\cup ...\cup L(i_K). 
\]

>From each member of the partition choose exactly one player. Suppose the
players so chosen are $i_1,i_2,...,i_K$ and without loss of generality,
rename these $1,2,...,K.$

Fix a player $i\ $and without loss of generality, in all that follows
suppose that $i=1.$ For each $k=2,3,...,K$ and $j\in L\left( k\right) $,
choose $x^{ij}\in F^{*}$ and $x^{ij}$ close enough to $u_j^i$ so that 
\begin{equation}
\begin{array}{cc}
x_j^{ij}\neq u_j^i\text{ and }x_j^{ij}>u_j^j\text{ } & \text{if }j\in
L\left( k\right) \\ 
x_h^{ij}=u_h^i & \text{if }1<h\leq K,\text{ }h\neq k
\end{array}
\label{xij}
\end{equation}
since $j\notin L\left( i\right) $ $\left( =L\left( 1\right) \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(a^{ik})=\ x^{ik}.$

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

Consider the following paths:

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

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

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

\paragraph{$\pi _{\tau +1}^i:$}

\begin{itemize}
\begin{itemize}
\item  In periods $\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=2,3,...,K:$

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

\item  play $a^i$ with probability $1-\sum_{k=2}^Kp^{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 $s.$
\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 $i$ is observed to deviate from $\pi _\tau ^j$ in period $t\leq
T-Q $, start $\pi _{t+1}^i.$

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

We now show 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 $i:$%
\[
\left( R+1\right) u_i>\overline{u} 
\]
Such an $R$ exists since $u_i>0.$ Choose $\delta _R$ so that for all $\delta
>\delta _R,$ for all $i:$%
\[
\frac{\left( 1-\delta ^{R+1}\right) }{\left( 1-\delta \right) }u_i>\overline{%
u} 
\]
and for all $i:$%
\[
\left( 1-\delta ^{R+1}\right) \underline{u}+\delta ^{R+1}u_i^i>0. 
\]

As before fix a player $i$ and suppose that $i=1.$\bigskip\ 

\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 , for all }$k=2,3,...,K${\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  \label{indiff} \\
&=&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_{k=2}^Kp^{ik}\left( \alpha ^{\prime }\right) <1. 
\]
{\em where }$U_k^R(\alpha ^{\prime })\equiv \sum_{r=1}^R\delta ^rU_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: }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 these paths rewrite the equality in (\ref{indiff}) as: 
\begin{equation}
\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) }=\left[ p^{ik}(\alpha )-p^{ik}(\overline{\alpha }^k)\right]
\left( x_k^{ik}-u_k^i\right)  \label{indiff2}
\end{equation}

By choosing $\delta $ and $R$ large enough, the left hand side of (\ref
{indiff2}) can be made arbitrarily small. Therefore, $p^{ik}\left( \alpha
\right) $'s can be chosen such that for all $i,$ for all $k=2,3,...,K$ and
for all $\alpha ,$ (\ref{indiff2}) holds and

\[
\sum_{k=2}^Kp^{ik}\left( \alpha ^{\prime }\right) <1.\quad \Box 
\]

\bigskip\ 

Once again fix a player $i=1$ (say)$.$ For every $k\leq K,$ $k\neq 1,$
choose the $p^{ik}(\alpha )$ as in the claim.

Suppose $i=1$ deviates. 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=2,3,...,K$ 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. Now consider a
player $j\in L\left( k\right) ,$ $k\neq i.$ Since $j$'s payoff function is
just an affine transformation of $k$'s, $j$ is indifferent between these
paths. Thus every player $j\notin L\left( i\right) $ is indifferent among
all the paths that lie in $\left( \limfunc{supp}m^i\right) ^R$.

Players in $j\in L\left( i\right) $ are all at single-period best responses
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{xij}) is important
here). The remainder of the proof may be completed by following the proof of
Theorem 1 exactly. \TeXButton{End Proof}{\endproof}\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. The non-discounting
assumption appears to be crucial to his argument as he makes use of
Blackwell's approachability theorem. Fudenberg and Maskin (1991) show that
the use of public randomization is not needed for the folk theorem for
infinitely repeated games with discounting. Note also that public
randomization plays

\newpage\ 

\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{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 (forthcoming) : ``The Power of
Commitment,'' {\em Journal of Economic Theory}, Yale University.

\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{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{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{Rubinstein}  Rubinstein, A. (1991): ``Comments on the
Interpretation of Game Theory,'' {\em Econometrica}, 59, pp. 909-924.

\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{Wen}  Wen, Q. (1994): ``The `Folk Theorem' for Repeated Games with
Complete Information,'' {\em Econometrica}, 62, pp. 949-954.
\end{thebibliography}

\end{document}

--=====================_821935765==_--