The Folk Theorems for Repeated Games: A Synthesis

Jean-Pierre Beno t Department of Economics and School of Law New York University Vijay Krishna Department of Economics Penn State University

March 10, 2000

Abstract We present a synthesis of the various folk theorems for repeated games using a model that accommodates both nitely and innitely 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. JEL Classication Number: C72 Key Words: Folk Theorems, Repeated Games.

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 Sjstrm and Matthew Spitzer made helpful suggestions. o o

Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . 3 The Main Result . . . . . . . . . . . . . . . . . . . . 3.1 Order of Limits . . . . . . . . . . . . . . . . . . 4 Applications . . . . . . . . . . . . . . . . . . . . . . . 4.1 Finitely Repeated Games . . . . . . . . . . . . . 4.1.1 Games with Distinct Equilibrium Payos 4.1.2 -Equilibria . . . . . . . . . . . . . . . . 4.1.3 Games with Incomplete Information . . 4.2 Innitely Repeated Games . . . . . . . . . . . . 4.2.1 Stationary Discounting . . . . . . . . . . 4.2.2 Non-Stationary Discounting . . . . . . . 4.3 Overlapping Generations . . . . . . . . . . . . . 5 Extensions . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Unobservable Mixed Strategies . . . . . . . . . . 5.2 Nash Equilibria . . . . . . . . . . . . . . . . . . 5.3 Frequent Response Games . . . . . . . . . . . . 6 Reformulations . . . . . . . . . . . . . . . . . . . . . 6.1 Games of Division . . . . . . . . . . . . . . . . . 6.2 Exogenous Payos . . . . . . . . . . . . . . . . 7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . A Appendix . . . . . . . . . . . . . . . . . . . . . . . . A.1 Proof of Theorem A1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 8 15 15 15 16 17 19 22 22 22 24 25 26 26 27 28 28 29 30 31 31

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 nite or innite, 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 satiscers, and whether the set of players remains the same or consists of overlapping generations.1 Perhaps the most debated of these aspects concerns the duration of the repeated game: whether it is nite or innite. As is well-known, the set of equilibrium outcomes of a game repeated a large but nite number of times, may be radically dierent from the equilibrium outcomes of its innitely repeated counterpart. This is sometimes referred to as the nite 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 nite or innite game is the appropriate choice for modelling repeated interaction among economic agents. For instance, Rubinstein (1991) has taken the position that players generally perceive repeated games, including those with a known, xed, and even short nite duration as a game of innite duration, and thus innite games are the appropriate model. However, the reasons underlying Rubinsteins position are dicult to fathom. The assumption that otherwise rational players view the twenty-fold repetition of the prisoners dilemma as being innitely repeated is rather curious. And while the predictions of the innite game are certainly consistent with observed behavior in the nitely repeated prisoners 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 nite models, such as those with incomplete information or satiscing players, are more in tune with observed behavior. In our opinion, generally modelling nitely repeated games as innitely 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 innite duration is neither necessary nor sucient for this. That it is
Detailed references are given below. See Aumann (1980), Pearce (1992) and Sorin (1993, 1996) for surveys of the area.
1

not necessary is well-known; if the constituent game has multiple equilibrium payos folk theorems for games with a long but nite duration are available. To see that it is not sucient, 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, t , declines and approaches 1 as t increases.2 Specically, given a (0, 1) 2 let 1 t t = + . 2 2 1 Notice that for all , limt t = 2 , while for all t, lim1 t = 1. The latter property implies that as 1, players become arbitrarily patient. Now, consider the following game 0, 0 x, 3 3, x 2, 2 which is a prisoners dilemma when x > 2. It may be veried that if x = 5, for all , the unique equilibrium payo in the innitely repeated game is (0, 0) . Although the game is of innite 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 nite horizon situation rather than an innite one. However, such a contention is refuted by the fact that if x = 4, then for large any feasible individually rational payo can be obtained in a perfect equilibrium. Thus, an argument that this is like or unlike a nite horizon could not be based upon the underlying time structure, that is the sequence ht i, but rather, would have to depend on the payos. The example shows that the nite-innite distinction is of limited use in analyzing or classifying the strategic possibilities.3 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 nitely repeated game followed by an end-game whose exact form and duration we leave unspecied. 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 nite 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 nite horizon games are rather simple corollaries of a single central result. Furthermore, innite games may also be treated in the
Q The payos from period t are then discounted by a factor of t =1 . 3 Moreover, even if one favors the modeling ction 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.
2

same way: an innitely repeated game may be thought of as a nitely repeated game followed by an end-game of innite duration. Our approach oers 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 Radners (1980) -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 suciently severely. Our approach relies essentially on the fact that payos from the end-game are negligible in the limit. While this allows us to consider innitely repeated games with discounting, it cannot accommodate innitely repeated games in which, say, the limit of means is used to evaluate innite payo streams. With the limit of means criterion, the payo from any nite 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 payos (Aumann and Shapley (1994) or Rubinstein (1994)). This paper is organized as follows. Main Result. Section 2 contains basics and some preliminary results. We consider perfect equilibria of repeated games with common discounting and dene the central concept: a two-part game that consists of a nitely repeated game followed by an end-game. We adopt the eective minmax methodology of Wen (1994) as it leads to the most general results. In Section 3 we derive the main result (Theorem 1) which identies 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 applications of the main result, its extensions and some reformulations of the results. 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 nitely repeated games. Section 4.1.1 concerns the folk theorem for nitely repeated games in which each player has distinct equilibrium payos (Beno and Krishna (1985)). Theorem 2 is the basic it result and Theorem 2 is a recent generalization to the case where the players have recursively distinct equilibrium payos (Smith (1995)). In Section 4.1.2 we consider epsilon equilibria of nitely repeated games and derive two folk theorems (Theorems 5

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 innitely 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 innitely 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). 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 xed but players revise moves rapidly and shows how Theorem 1 may be reinterpreted to this context. 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. 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 unication 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 dicult, 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.

Preliminaries

Let G = (A1 , A2 , ..., An ; U1 , U2 , ..., Un ) be a game in strategic form where Ai is is strategy space and Ui is his payo function. We assume that the Ai s are compact Q Q and the Ui s are continuous. As usual, we write A n Aj and Ai j6=i Aj j=1 6

with generic elements a and ai respectively. We also assume that G has at least one equilibrium. If the Ai s are convex subsets of a Euclidean space we call G a continuous game. If the Ai s are nite sets we call G a nite game. Let vi be player is minmax payo dened as: vi = min max Ui (ai , ai ) .
a ai

Let F denote the feasible and individually rational payos in G, that is, F = {u co U (A) : u v} . Two players i and j are said to have equivalent utilities if is payo function is an increasing ane transformation of js (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) denes an equivalence class. Following Wen (1994), let vi be player is eective minmax payo dened as: vi = min max max Ui (ak , ak ). (1)
a kN(i) ak

For all i let mi be the solution to (1), and for all j N (i) choose mj = mi .We have that for all j N (i):
max Uj (aj , mi ) max max Uj (ak , mi ) = vj . j k aj kN(i) ak If mi is played, no player j N(i) can obtain more than vj by playing a best response. Clearly, vi vi . Normalize the game so that for all i, vi = 0 and dene:

F = {u co U (A) : u 0} . to be the set of feasible and eectively rational payos in G. We assume that there exists a u F , u 0.4 Note that if no two players have equivalent utilities, then F = F . Wen (1994) also shows that F = F for all two player games. G (T ) will denote the game which consists of T repetitions of G and in which players use a discount factor of (0, 1) to evaluate payos. If (a1 , a2 , ..., aT ) is a path in G (T ) the resulting payo vector is the discounted average of the per period payos: T (1 ) X t U(at ). (1 T ) t=1
4

Given two vectors x, y Rn , x y means that for all i, xi > yi .

G () denotes the innitely repeated game with discount factor . 1 2 T A pure strategy for player i in G (T ) is a sequence i , i , ..., i such that 1 t i Ai and for all t > 1, i : At1 Ai . Similarly, a pure strategy in G () is an 1 2 innite sequence (i , i , ...) of this form. Thus, we are assuming that there is perfect monitoring (also called standard signalling). Let P (T ) be the set of (subgame) perfect equilibrium payos of G (T ). Similarly, P () denotes the set of perfect equilibrium payos of G (). The minmax level vi is an obvious lower bound on player is payo in any equilibrium of G (T ) or G (). 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 eective minmax level vi then becomes the natural lower bound. Indeed, Wen (1994) has shown that for all and T, P (T ) F and that for all , P () F . Public Randomization. Suppose u co U (A) . Then by denition there ex1 2 L ist l PLL pure strategy action proles a , a , ..., a and weights 1 , 2 , ..., L such that = u. Now suppose there is a publicly observed randomizing device l=1 l U a such that the state l occurs with probability l . Then for all i and l, if each player i plays al when the state is l, the resuling expected payo will be exactly u. Moreover, i since l is common knowledge, if any player were to choose an ai 6= al in state l then i this deviation would be commonly observed. In what follows, in both G (T ) and G (), it is convenient to assume that the players have access to such a randomizing device. Usually, we will not refer to the randomizing device explicitly, rather, instead of saying that there is a randomizing device that achieves the payo u, we economize on notation and say that there is an action a that achieves every payo u co U (A) . Whenever, u U (A) this / should be understood to mean that u is achieved in the manner outlined above.5 Initially, we also assume that when players randomize independently, their mixed (behavioral) strategies are observable (alternatively, we can say that the Ai s themselves subsume all mixing possibilities). This assumption is relaxed later in Section 5.

The Main Result

Let H = (S1 , S2 , ..., Sn ; V1 , V2 , ..., Vn ) be a game with parameter (0, 1).

Denition 1 Given a nitely repeated game G (T ) and another game H , the conjunction of the two games, written hG (T ) , H i, is a T +1 period game that consists of G (T ) followed by H , with perfect monitoring throughout. H is then referred to
Alternatively, every payo u can be approximated by playing a1 for some 1P periods, then a2 3 for 2 periods, a for 3 periods etc. where the l are integers satisfying l ' l ( k ) . See Sorin (1996) for details.
5

as the end-game. If (a1 , a2 , ..., aT , s) is a path in hG (T ) , H i, the resulting payo is # " T X (1 ) t U (at ) + T +1 V (s) . T +1 ) (1 t=1 If ( 1 , 2 , ..., T , T +1 ) is a perfect equilibrium of the game hG (T ) , H i, then for all (a1 , a2 , ..., aT ) AT , we must have that T +1 (a1 , a2 , ..., aT ) is a perfect equilibrium of H .6 Notice that if H is itself a repeated game G (T 0 ) (where T 0 may be nite or innite) then a perfect equilibrium payo of hG (T ) , H i is a perfect equilibrium payo of G (T + T 0 ). Denition 2 The game H = S1 , ..., Sn , V1 , ..., Vn has a perfect threat of M if there exist n + 1 perfect equilibria of H : s, s1 , s2 , ..., sn satisfying for all i, Vi (s) Vi (si ) M. (2) s, s1 , s2 , ..., sn will be referred to as the perfect threat strategies which yield M. A perfect threat of M consists of a target path s and for each player i a punishment path si ; each player i can then be threatened with a loss of at least M by a play of si rather than s. Note that s1 , s2 , ..., sn need not be distinct. Let (T ) be the set of (subgame) perfect equilibrium payos of the conjoined game hG (T ) , H i. Our main result concerns the Hausdor limit of (T ) as 1 and T : if the end-game H has a large enough threat then the set of perfect equilibrium payos of the conjoined game hG (T ) , H i approaches the set of eectively rational payos F of the game G.7 When H has a large threat, it is obvious that towards the end of G (T ) the players can be induced to follow any path, since possible losses in H swamp any gains from deviating in the small time remaining in G (T ) . It is less obvious that the threat in H can have any impact on play at the beginning of an arbitrarily long G (T ) . 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 (T ) are (potentially) much larger than any payos in H . Nonetheless, H serves to prevent an unravelling at the very end of the game. In earlier periods, threats built within the game G (T ) itself are used to sustain eectively rational paths.
Of course, if H has no proper subgames, the set of perfect equilibria of H is the same as the set of Nash equilibria of H . 7 We show below in Section 5 that under a slightly stronger assumption on H the order of limits in the statement below is unimportant. This stronger assumption is satised for nitely repeated games.
6

Theorem 1 There exists an M such that if for all large , H has a perfect threat of M then lim lim (T ) F .
1 T

Proof. Let a F be the smallest ane space containing F .8 Dene B (u, ) = {v a F : |u v| } , the closed ball of radius around u. For > 0, dene F () = u F : B (u, ) F and choose > 0 small enough so that rel int F () 6= . As in Abreu, Dutta and Smith (1994), from the denition of equivalent utilities, there exist n vectors x1 , x2 , ..., xn in F () that satisfy payo asymmetry: j N (i) , xi < xj / i i j N (i) , xi = xj

(3)

We proceed in three steps. Step 1 establishes punishment vectors wi for each player that have the property that given any planned payo u F () , each player prefers the planned payo ui j i to his punishment payo wi , and moreover, prefers the payo wi when some player i j N (i) is punished to his own punishment payo wi . / Step 1 For all there exists an 0 < and w1 , w2 , ..., wn in F (0 ) such that for all u F (): i i N, wi < ui 0 j i j N (i) , wi < wi 0 / (4) j i j N (i) , wi = wi
i

i For all i, let y i be such that yi = min {vi : vi , (vi , vi ) F ()} . Similarly, let i i z be such that zi = min {vi : vi , (vi , vi ) F (/3)} . Then zii < yi . Notice that j i if j N (i) then yi = yi and zii = zij . i Since for all i N, zii < yi there exists a (0, 1) such that for all i N, i i i yi (1 ) zi xi > 0. Fix such a . i i Choose 0 to satisfy: for all i, yi (1 ) zi xi > 0 and for all i and all i j j N (i), xi xi > 0 . / i Dene

wi = (1 ) z i + xi It is routine to verify that the wi satisfy (4).

8

a F =

nP L

i i i=1 i x : x F ,

PL

o i = 1 . See Rockafellar (1970). i=1

10

This completes Step 1. Step 2 shows that when is large enough, the wi determined in Step 1 constitute sucient punishments in the early periods of the game to enforce proposed paths. Towards the end of the game there is insucient time to use these punishments, but now the threats in the end-game H can be used. Step 2 For all > 0 there exists an M () such that if for all large , H has a perfect threat of M () then there exists T () and () , such that for all T > T () z }| { and > () , for all a satisfying U (a) F () the path (a, a, ..., a, s) is a perfect equilibrium path of hG (T ) , H i. Observe that in the statement above, M (), T () and () are independent of a. Let a A be such that U (a) F () . From Step 1 there exists an 0 < and vectors w1 , w 2 , ..., wn in F (0 ) that satisfy (4) when u = U (a) . For all i, let ai A be such that U (ai ) = w i . Suppose Q, R and T are given, R < Q < T . Let s, s1 , s2 , ..., sn be perfect equilibria of H . (Note that s and si depend on ). 0 Let 1 be a path from period 1 to T + 1 described by:
0 1 = (a, a, ..., a, s). i For i = 1, 2, ..., n, and T Q let be a path that begins in period and ends in period T + 1 described by: T periods

i Given a strategy combination , we say that i deviates from a path in period i t if calls for i to play (t) but i plays something else. Consider the following (recursively dened) strategies: 0 Follow 1 (until someone deviates). j If player i is the (lowest indexed) player to deviate from , j = 0, 1, ..., n in i period t T Q, switch to t+1 . j If player i is the rst player (with the lowest index) to deviate from in some period t, T Q < t T , then play some equilibrium e of G in each subsequent period through period T, and play si in period T + 1. Any deviation after the rst is ignored.

z }| { i = (mi , mi , ..., mi , ai , ai , ..., ai , s).

R periods

11

We now show that for large enough Q, R, T and these are perfect equilibrium strategies. It is sucient to verify that no player wants to deviate from these strategies just once and conform thereafter.9 0 j First, consider t T Q and deviations by player i N(j) from 1 or . 0 j If i N(j) deviates from 1 or from in any period where a or aj is being played, his remaining payo stream is bounded above by: z }| { j j (u, 0, 0, ..., 0, wi , ..., wi , Vi (s))
R periods

(5)

where u is the maximum payo of any player in G. To see this, recall from (4) that j i for i N (j), wi = wi . On the other hand, if i does not deviate his remaining payo stream will be no worse than: z }| { j j j j j j (wi , wi , wi , ..., wi , wi , ..., wi , Vi (s)) z }| { j j (0 , 0 , 0 , ..., 0 , wi , ..., wi , Vi (s))
R periods R periods

(6)

j Since wi > 0 , (6) is no worse than

(7)

For large enough R and the discounted value of (7) is greater than that of (5). Note that the R and so chosen depend on 0 and hence on . j If i N (j) deviates from in one of the rst R periods (where mj is being played), the resulting payo stream is bounded above by z { }| i i (0, ui mi , ui mi , ..., ui mi , wi , ..., wi , Vi (s))
R periods R periods

(8)

On the other hand, if i does not deviate his payo stream is bounded below by z { }| j j j j j j (ui m , ui m , ..., ui m , wi , wi , ..., wi , Vi (s)) (9)

j i Since i N (j) , mi = mj and wi = wi > 0, for large enough the discounted value of (9) is greater than that of (8). j Next, consider t T Q and deviations by player i N (j) from . Deviating / once yields a remaining payo stream bounded above by:

This is known as the one deviation property of subgame perfect equilibrium. See Osborne and Rubinstein (1994).

z }| { z i }| { z i }| { i i (u, 0, ..., 0 , wi , ..., wi , wi , ..., wi , Vi (s))

R periods

QR

T tQ

(10)

12

Not deviating yields i at worst: { z }| { z j }| { z j }| j j j ( u, ..., u , wi , ..., wi , wi , wi , ..., wi , Vi (s))

R periods QR T tQ+1

(11)

j i where u is the minimum payo of any player in G. Since i N (j), from (4) wi wi > / 0 , and thus we can choose Q so that the discounted value of (11) is greater than that of (10) for all i, j, i N (j), when t = T Q and = 1. The inequality then also / holds for all large and t < T Q. Once again, Q depends only on . Finally, consider deviations by a rst deviator i in a period t > T Q. If i deviates his remaining payo stream is bounded above by:

If i does not deviate his remaining payo stream will be at worst: z }| { (u, u, ..., u, Vi (s))
Q periods

z }| { (u, u, ..., u, Vi (si ))

Q periods

(12)

(13)

Let M () be a number satisfying M () > Q (u u) (Since Q depends only on , so does M ). Suppose s, s1 , s2 , ..., sn are perfect equilibria of H such that for all i Vi (s) Vi (si ) M () . For large enough , the discounted value of (13) is greater than that of (12), for all i. This completes Step 2. Notice that the threats used in Step 2 depend upon (hence we write M ()). Step 3 shows that M can be chosen independently of . Step 3 There exists an M such that if for all large , H has a perfect threat of M then for all > 0 there exists a () such that for all > () , there exists a T (, ) such that for all T > T (, ), if u F then there exists a v (T ) with |u v| < . Fix an and a point u F (b) . From Step 1 there exists an 0 < and b b b b b w1 , w2 , ..., wn in F (b0 ) satisfying (4). Let M = M (b0 ) as determined in the statement b b of Step 2. Let b, b1 , b2 , ..., bn be outcomes corresponding to u, w 1 , w2 , ..., w n , respectively. a a a a b b b b Suppose that for all large , H has a perfect threat of M = M (b0 ) . We now 0 0 0 show that for all M there exists a T (M ) such that for all T > T (M ) and large , the conjoined game H 0 hG (T ) , H i, itself viewed as an end-game, has a perfect threat of M 0 . This is because from Step 2, (b, b, ..., b, s) and (bi , bi , ..., bi , s) are perfect a a a a a a 13

equilibrium paths of hG (T ) , H i, and the dierence in player is payos from these paths exceeds M 0 when T and are large. Now for any u F take a u0 F () satisfying |u u0 | < . Consider the game G (T ) followed by an end-game. As in Step 2, for > (), u0 can be obtained as a perfect equilibrium payo in every period but the last, if the end-game has a large enough threat M (). While H has a threat of (only) M, we have shown that for all large , the conjoined game hG (T (M ())), H i has a threat M () . Therefore, u0 can be obtained in every period but the last of the game G (T ) followed by the end-game H hG (T (M ())), H i. But this game, hG (T ) , H i, is the same as hG (T + T (M ())), H i. Hence u0 can be obtained in every period but the last K () T (M ()) + 1 periods of the game hG (T + T (M ())), H i for all T. Finally note that for large enough T (, ) , for all T > T (, ) the payo from one of these paths is within of u0 . When T is large, the perfect threat M required for Theorem 1 is small relative to the total payos in G (T ). The following corollary gives a sucient condition for M to be small relative to the payos in G. Given an outcome a, dene the maximum gain from deviating from a : d (a) = max {Ui (bi (a) , ai ) Ui (a)} .
i

where bi (a) is is best response to ai . Corollary 1 Suppose G has an equilibrium e that is inecient. If for all large , H has a perfect threat of M > inf {d (a) : U (a) U (e)} then
1 T

lim lim (T ) = F .

Proof. Choose a such that U (a) U (e) and d (a) < M. Let s, s1 , s2 , ..., sn be the threat strategies which yield M . Then for all T and large the path (a, a, ..., a, s) is a perfect equilibrium path of hG (T ) , H i since deviations can be punished with (e, e, ..., e, si ) . Since the payo dierence between (a, a, ..., a, s) and (e, e, ..., e, s) can be made arbitrarily large, the game H = hG (T 0 ), H i has an arbitrarily large threat for large and T 0 . Apply Theorem 1 to hG (T ), H i. Note that for continuous games inf {d (a) : U (a) U (e)} = 0, so that if G is a continuous game with an inecient equilibrium it is enough for H to have any positive threat.10
10 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.

14

3.1

Order of Limits

In many contexts, in particular for nitely repeated games, the end-game H satises the condition that for all i and s, lim sup1 Vi (s) < . Under this assumption, we obtain the stronger result that the order of limits in the conclusion of Theorem 1 is unimportant. Theorem 10 Suppose H satises for all i and s, lim sup1 Vi (s) < . There exists an M such that if for all large , H has a threat of M then
1 T

lim (T ) F .

The proof follows the proof of Theorem 1 exactly, with the double limit being taken in Step 3 instead of the sequential limit. The condition that the payos V (s) are bounded as 1 ensures that the contribution of H to the average payos in the conjoined game hG (T ) , H i is negligible, regardless of the order in which the limits are taken.

4
4.1

Applications
Finitely Repeated Games

As noted earlier, if H is itself a repeated game G (T 0 ) then a perfect equilibrium payo of hG (T ) , H i is a perfect equilibrium payo of G (T + T 0 ), that is, (T + 1) = P (T + T 0 ). Furthermore, if there exists a set of perfect equilibrium strategies s, s1 , s2 , ..., sn of G (T 0 ) which, for all 0 , yield any positive perfect threat for G (T 0 ), then by choosing k large enough, the game G (kT 0 ) can be made to have an arbitrarily large threat for large . This threat can be obtained simply by patching together the relevant threat strategies of G (T 0 ) k times.11 Applying Theorem 10 to the conjoined game hG (T ) , G (kT 0 )i, we have that there exists a k such that lim 1 (T ) = lim 1 P (T + kT 0 ) F . Proposition 1 Suppose that for some T 0 and 0 there exists a set of strategies which, for all 0 , yield a positive perfect threat in G (T 0 ). Then
1 T

Since for all and T, P (T ) F , we have the following:

lim P (T ) = F .

In Section 5.2 we show that the above limits, and indeed all the limits for nitely repeated games, can be taken simultaneously.
Suppose (a1 , a2 , ..., aT ) is a perfect equilibrium path of G (T ) and (a1 , a2 , ..., aT ) is a perfect equilibrium path of G (T ). Then (a1 , a2 , ..., aT , a1 , a2 , ..., aT ) is a perfect equilibrium path of G (T + T ). This process is referred to as patching the two paths together.
11

15

4.1.1

Games with Distinct Equilibrium Payos

Say that G has distinct equilibrium payos if every player has two equilibrium payos. The following result is due to Beno and Krishna (1985).12 it Theorem 2 If G has distinct equilibrium payos then
1 T

lim P (T ) = F .

Proof. For all i, let Ui ei > Ui (ei ) be the best and worst equilibrium payo, respectively, for player i. Set T 0 = 2n, and let s = (e1 , e1 , e2 , e2 , ..., en , en) and si = (ei , ei , ..., ei ) be T 0 period paths. Note that for all , s, s1 , s2 , ..., sn forms a positive threat in G (T 0 ). Now apply Proposition 1. As in Smith (1995) we say that G has recursively distinct equilibrium payos if there exists an ordering of the players 1, ..., n such that (a) player 1 has two equilibrium payos, and (b) for all i, 1 i < n, there exist strategy combinations hi+1 and li+1 such that ui+1 (hi+1 ) > ui+1 (li+1 ) and each player i + 1, ..., n is at a best response.13 The following generalization of Theorem 2 is due to Smith (1995). Theorem 3 If G has recursively distinct equilibrium payos then
1 T

lim P (T ) = F .

Proof. We proceed inductively. Suppose that for some i, 1 i < n, there exists a Qi such that G1 (Qi ) has two equilibrium payos 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 i and i be such perfect equilibrium paths of G1 (Qi ) yielding i his highest and lowest payo among such paths, respectively. Since G has recursively distinct equilibrium payos there exists a k such that z }| { z }| { z }| { z }| { (hi+1 , 1 , ..., 1 , 1 , ..., 1 , ... , i , ..., i , i , ..., i ) (l
12

k times

k times

k times

k times

and

i+1

We remind the reader that this and all other folk theorems are rewritten in Wens (1994) eective minmax formulation. Also, the original theorem was stated without discounting. 13 This denition is equivalent to the denition in Smith (1995).

z }| { z }| { z }| { z }| { 1 1 1 1 , , ..., , , ..., , ... , i , ..., i , i , ..., i )

k times

k times

k times

k times

16

are perfect equilibrium paths of G1 (2ikQi + 1) with dierent payos 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 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 nd a Q such that every player has two equilibrium payos for all suciently close to 1. By patching these equilibria together as in the proof of Theorem 2, the game G (T 0 ) has a positive threat, where now T 0 = 2nQ. Now apply Proposition 1.

4.1.2

-Equilibria

Radner (1980) introduced the following notion of approximate equilibrium behavior. Denition 3 An -equilibrium of G (T ) is a strategy combination such that for 0 all i and i " T " T # # X X 1 1 0 t U(at ()) t U (at (i , i )) (1 T ) t=1 (1 T ) t=1
0 0 where at () and at (i , i ) are the outcomes at time t resulting from and (i , i ) respectively. A perfect -equilibrium is an -equilibrium in every subgame of G (T ) .

Below we establish a folk theorem for perfect -equilibria along the lines of Radner (1980). However, the notion of perfect -equilibrium may be criticized on the grounds that while a players payo is close to his best-response payo in terms of averages, in long horizon game the discrepancy may be quite large in terms of totals. The following denition, suggested in the work of Chou and Geanakoplos (1988), is intended to address this issue directly. Denition 4 An -satiscing equilibrium of G (T ) is a strategy combination 0 such that for all i and i " T # T X X 0 t U(at ()) t U (at (i , i )) .
t=1 t=1

A perfect -satiscing equilibrium is an -satiscing equilibrium in every subgame of G (T ) .

17

The notion of perfect -satiscing equilibrium may be criticized on the grounds that while in a long horizon game a players total loss from not optimizing is small relative to his overall payo, this loss may be large relative to the remaining payo towards the end of the game. We now show how Theorem 10 , and hence Proposition 1, may be applied to obtain folk theorems for both notions. Let P (T ) be the set of perfect -equilibrium average payos of G (T ) . Let P (T ) be the set of perfect -satiscing equilibrium average payos of G (T ). To apply Theorem 10 and Proposition 1 in the present context recall that a strategy combination in hG (T ) , H i such that (1) no player can protably deviate in any subgame which starts in one of the rst T periods, and (2) for any history induces a subgame perfect equilibrium of H , is a subgame perfect equilibrium of hG (T ) , H i. A strategy combination in hG (T ) , H i such that (1) no player can protably deviate in any subgame which starts in one of the rst T periods, and (20 ) for any history induces a perfect -equilibrium of H , is a perfect -equilibrium of hG (T ) , H i. Similarly, for perfect -satiscing equilibria. This reasoning can be carried through to Proposition 1 so that: Remark 1 If the threat strategies in Denition 2 are perfect -equilibria rather than perfect equilibria, then in Proposition 1, P (T ) can be replaced by P (T ). Similarly, if there exists an 0 such that the threat strategies are perfect 0 -satiscing equilibria, then there exists an such that P (T ) can be replaced by P (T ). In light of the two criticisms mentioned above, Theorem 4 below requires a strategy combination to be both a perfect -equilibrium and a perfect -satiscing equilibrium. Theorem 4 There exists an such that for all > 0, lim P (T ) P (T ) F .
1 T

Proof. Let e be an equilibrium of G, and let u, u1 , u2 , ..., un be elements of F satisb b b b fying for all i: ui > ui . b bi

Clearly, given an > 0, for all outcomes a there exists a T 0 and 0 such that for all > 0 , (a, e, e, ..., e) is a perfect -equilibrium path of G (T 0 ) and for 0 = (u u) it is also an 0 -satiscing equilibrium. Using the outcomes corresponding to the n + 1 above points yields a positive threat in G (T 0 ) for all > 0 . Now if we apply Remark 1 the conclusion of the theorem holds for = k0 . Notice that if is very small, then the notion of a perfect -satiscing equilibrium is satisfactory on its own. The following theorem is due to Chou and Geanakoplos (1988). 18

Theorem 5 Suppose G is a continuous game with an inecient equilibrium. Then for any > 0, lim P (T ) F .
1 T

Proof. For any choose a such that U (a) U (e) and the maximal deviation d (a) < . This is an -satiscing equilibrium of G (1) . Set H = G (1) and apply Corollary 1 (modied as in Theorem 10 ). Since the threat in G (1) is -satiscing, the equilibria of G (T + 1) = G (T ) , G (1) are -satiscing. 4.1.3 Games with Incomplete Information

Following Kreps 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. Specically, they showed that for every u F , there is a game of incomplete information in which u is a sequential equilibrium payo. 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 same type of irrationality. Thus, the (optimistic) claim that dierent 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 identied, these can be used in a suitable end-game to immediately establish a folk theorem. To apply Theorem 1 to games of incomplete information recall from earlier sections that a strategy combination in hG (T ) , H i such that (1) no player can protably deviate in any subgame which starts in one of the rst T periods, and (2) for any history, induces a subgame perfect equilibrium of H , is a subgame perfect equilibrium of hG (T ) , H i. Suppose H is a game of incomplete information. Then a strategy combination in hG (T ) , H i such that (1) no player can protably deviate in any subgame which starts in one of the rst T periods, and (200 ) for any history induces a sequential equilibrium of H , is a sequential equilibrium of conjoined game hG (T ) , H i. Thus: Remark 2 If the threat strategies in Denition 2 are sequential equilibria, then in Theorem 1 (T ) can be replaced by the set of sequential equilibrium payos of hG (T ) , H i.

19

Theorem 6 For all T there exists a game of incomplete information G (T, ) in which with probability (1 ) each players payos are the same as in G (T ) and lim lim lim Seq (T, ) = F ,
0 1 T

where Seq (T, ) is the set of sequential equilibrium payos of G (T, ) . Proof. Let G (Q, ) be the Q period game of incomplete information in which each player is rational with probability (1 ) and with probability is an irrational player who is completely indierent among all outcomes. Fix some equilibrium e of G satisfying U (e) 0.14 Let u F and let a A be such that U (a) = u. Consider the following behavior strategies. Irrational player i. I1. Play ai in period 1. If each player j plays aj in period 1, then play ei for the remaining Q 1 periods of the game at all information sets. I2. Suppose that some player j does not play aj in period 1, and indeed let j be the lowest indexed such player. Then: In period t = 2 : (eectively) minmax j In period t > 2 : if for all such that 2 < t, all players have minmaxed j then minmax j in period t; if there is a , 2 < t, such that some player did not minmax j, then play ei in period t. Rational player i. R1. Play ai in period 1. If each player j plays aj in period 1, then play ei for the remaining Q 1 periods of the game at all information sets. R2. Suppose that some player j does not play aj in period 1, and let j be the lowest indexed such player. In period t > 2, if there is a , 2 < t, such that some player did not minmax j, then play ei in period t. Otherwise for t 2, all rational players play to a particular sequential equilibrium derived under the restriction that all players strategies conform to the above restrictions.15
The assumption that G has an equilibrium such that U (e) 0 is made only for convenience. That is, dene a new game in which the players strategy spaces are as in the original game but with the above restrictions. This is a well-dened game with a sequential equilibrum.
15 14

20

We now verify that the above constitutes a sequential equilibrium. Since irrational players are always indierent, 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 ai is strictly optimal in period 1 when = 1. Playing ai yields ui (a) + (Q 1) ui (e) . Deviating (once) yields a payo which is bounded above by u + n1 (Q 1) 0 + 1 n1 [u + (Q 2) ui (e)] (14)

(15)

where u is the maximum payo of any player in G. (15) < (14) for large enough Q. Thus, we have shown that for all u F , there exists a Q such that for all Q > Q, there is a sequential equilibrium of G (Q, ) which results in a stream of payos (u, U (e) , ..., U (e)) . Now let u, u1 , u2 , ..., un be elements of F satisfying for all i: b b b b We have found n + 1 sequential equilibrium payos of G (Q, ) which show that G (Q, ) has a positive sequentially perfect threat. An arbitrarily large threat can be obtained by patching together sequential equilibria of G (Q , ), say k times, to obtain sequential equilibria of H hG (Q , ), ..., k times, ..., G (Q , )i. The resulting strategy combination is a sequential equilibrium. Remark 2 shows that Theorem 1 may be applied. Finally, note that a sequential equilibrium of hG (T ) , H i 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). 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 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.16
16

ui > ui . b bi

We thank Drew Fudenberg for suggesting this interpretation.

21

4.2
4.2.1

Innitely Repeated Games

Stationary Discounting

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

lim P () = F

Since for all , P () F , Theorem 7 follows from Theorem 1 if G () can be shown to have an arbitrarily large threat as 1. To see this set H = G () , and note that a perfect equilibrium payo of hG (T ) , H i is a perfect equilibrium payo of G () . If G has (recursively) distinct equilibrium payos 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 nite case. If G has an inecient equilibrium e this threat can be constructed as follows: Let a be such that u (a) u (e) . Let s be the strategies: each player i plays ai so long as all others do; if anyone deviates play ei forever. Let s be e repeated forever. For large these strategies form an arbitrarily large threat. If G has a single equilibrium which is ecient Theorem 1 may still be applied, however it appears that it is then no easier to establish that G () has an arbitrarily large threat than it is to establish Theorem 7 directly (the latter can be done by setting T = and Q = 0 in the proof of Theorem 1).17 Theorems 2 and 7 together conrm a conjecture of Pearce (1992) that if G has (recursively) distinct equilibrium payos then
T

lim P 1 (T ) = lim P () .
1

Note, however, that an example in Beno and Krishna (1987) shows that even with t distinct equilibrium payos, for xed , it may be that
T

lim P (T ) 6= P () .

4.2.2

Non-Stationary Discounting

The standard model of an innitely repeated game with a common discount factor of can be reinterpreted to represent a situation where the horizon of the game is uncertain and represents the probability that the game will be played in period t+1
We note that in the class of continuous games with smooth payos, the eciency of equilibria is a non-generic property (see Dubey (1986)).
17

22

conditional on it being played in period t. With probability (1 ) the game ends in period t. Notice that in this formulation players are assumed to maximize their expected payo 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.18 Thus let t represent the probability that the game will be played in period t given that it was played in period t 1. Let ht i be the sequence of such continuation probabilities and given such a sequence, let Ght i () represent a repeated game in which the total (expected) payo vector from a path (a1 , a2 , ...) is, t ! X Y U (at ).
t=1 =1

Suppose that e is inecient. Bernheim and Dasgupta (1995) then show that Ght i () has a non-trivial equilibrium (that is, other than playing the one-shot equilibrium e
18

Ght i () is said to be a repeated game with an asymptotically nite horizon if for all t, t > 0 and limt t = 0. Let t be a monotonically declining sequence satisfying limt t = 0 and for xed and T consider the game hG (T ), Ght i ()i which consists of a T period repeated game followed by an innitely repeated game with an asymptotically nite horizon in which the sequence of continuation probabilities is ht i. First, suppose that the constituent game G is nite (that is, all the Ai s are nite) and has a unique equilibrium, say e. Then for all , the game Ght i () also has a unique perfect equilibrium. This is because there exists a c > 0 such that from any a 6= e each player can gain at least c by deviating. Since t 0, there exists a Tc such that for all t Tc , no deviations can be punished in the subsequent game and thus no a 6= e can be played after period Tc . 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 payos, then the arguments of the section on nitely repeated games may be applied to derive a folk theorem for hG (T ), Ght i ()i as 1 and T . 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 hG (T ), Ght i ()i as dened above? The answer depends on how fast the continuation probabilities are declining. Say that the sequence of continuation probabilities ht i declines slowly if T X lim 2t ln t > .
T t=1

Alternatively, the discount factor declines with time.

23

repeatedly) only if ht i declines slowly.19 They also prove the following folk theorem: Theorem 8 Suppose that G is a continuous game with an inecient equilibrium. If ht i declines slowly then, lim lim (T ) = F ,
1 T

where (T ) is the set of perfect equilibrium average payos in the conjoined game hG (T ), Ght i ()i. Proof. By Theorem 2 in Bernheim and Dasgupta (1995) the game Ght i () has a perfect equilibrium whose payos Pareto dominate the payo U (e) from an inecient equilibrium e of G. Thus the game Ght i () has a positive threat. Apply Corollary 1.

4.3

Overlapping Generations

Crmer (1986), Kandori (1992) and Smith (1992) have examined models in which e each player is nitely lived but there is an innite population of players who interact in overlapping generations. Consider a model with n types of players (indexed by i) of dierent generations (indexed by r = 1, 2, ...). Player (i, r) is the player of type i in the rth generation. Let K > 0 be xed and suppose that each player (i, r) lives for T > nK periods. For r > 1, player (i, r) is assumed to be born in period (i 1) K + (r 1) T + 1 and die in period (i 1) K + (r 1) T + T. Thus, all n players of a given generation r overlap for exactly T (n 1) K periods. We will refer to such a game as OLG (T, K) . Dene Pr (T, K) = {u F : there is a perfect equilibrium of OLG (T, K) in which the payos of all generations 1 through r is u}. The following theorem is similar to results derived by Kandori (1992) and Smith (1992). Theorem 9 There exists a K such that for every r,
1 T
19

lim lim Pr (T, K) = F

Some additional conditions are also needed for this result: the payo functions and the bestresponse functions must be twice continuously dierentiable and the equilibrium must be regular. See Bernheim and Dasgupta (1995) for details.

24

Proof. Fix some inecient equilibrium e of G.20 For ease of exposition suppose that n = 3. We rst nd two equilibria of OLG (T, K) . The rst is simply s = (e, e, . . .), that is a path in which all players play e. s is dened as follows. Let ai be the outcome that is best for a player of type i, and let a be such that U (a) U (e). For k1 < K and k2 < K consider the T period path beginning with the birth of a type 1 player:
1 Kk Kk z }| { z }| 2 { z }| { z T 3K { z }| { z }| 1 { }| 2 2 3 3 1 1 (a , ..., a , e, ..., e, a , ..., a , a, a, ..., a, a , ..., a , e, ..., e).

k2 periods

(16)

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 k1 , we can choose k2 to be large enough so that a player of type 2 cannot gain by deviating in the k1 periods that a1 is played. For every k1 and k2 , K can be chosen large enough so that there is no gain for a player of type 3 from deviating either in the k1 periods that a1 is played or in the k2 periods that a2 is played. Let M be dened as in the statement of Theorem 1 and choose k1 , k2 and K large enough so that k1 U(a1 ) U1 (e) > M k1 U2 (a1 ) U2 (e) + k2 U2 (a2 ) U2 (e) > M k1 U3 (a1 ) U3 (e) + k2 U3 (a2 ) U3 (e) + K U3 (a3 ) U3 (e) > M and the deviations of the previous paragraph are not protable. Finally, choose T large enough so that no player can protably deviate in the remaining periods. Fix a generation r and let G (T 3K) be a nitely repeated game among the r players of generation r. For suciently large T and , let H be the OLG (T, K) that begins when a type 1 player of generation r is T K periods old. H has a threat of M. Applying Theorem 1 to hG (T 3K) , H i shows that any payo u > 0 and r a payo u0 u can be sustained in this game when T and are large. Let c be the outcome which results in u, and c0 be the outcome which results in u0 . We can now construct threats which yield the players in generation r 1 a payo of (approximately) u, and in which the play for generation r is like (16), but with c replacing a along the path, and with c0 replacing e as the punishment for a deviation from c. Continuing in this manner for earlier generations establishes the theorem.

5
20

Extensions
We assume that G has an inecient equilibrium only for convenience.

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

25

5.1

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 innitely repeated games: punishing players are kept indierent on the support of the minmax (mixed) strategy. For this result we suppose that the game G is nite. Let (T ) denote the set of perfect equilibrium average payos when mixed strateu gies are unobservable. Theorem A1 There exists an M such that if for all large , H has a threat of M then lim lim (T ) = F . u 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 nitely repeated games without discounting, G1 (T ), when mixed strategies are not observable and public randomization is not allowed. He makes use of Blackwells approachability theorem, in order to construct the equilibrium strategies and in this construction seems to need the assumption that the set of feasible payos is full dimensional. Fudenberg and Maskin (1991) show that the use of public randomization is not needed for the folk theorem for innitely repeated games with discounting.
1 T

5.2

Nash Equilibria

A simple modication of our framework can also accommodate Nash equilibrium folk theorems. Instead of requiring that H have a suciently large (perfect equilibrium) threat, the weaker condition that H have a Nash equilibrium whose payos are suciently greater than minmax levels (of H ) is enough to establish a Nash equilibrium analog of Theorem 10 (along the lines of Beno and Krishna (1987)). it Let V denote player is minmax payo in H . We say that H has a Nash threat i of M if there exists a Nash equilibrium s of H satisfying for all i, Vi (s) V M. i Let N (T ) denote the set of Nash equilibrium payos of the game hG (T ) , H i. Then we obtain: Theorem 10 There exists an M such that if for all large , H has a Nash threat of M then lim N (T ) = F
1 T

Observe that in Theorem 10 F replaces F . 26

5.3

Frequent Response Games

One recommendation for a nite model over an innite model is that agents typically do not live forever. However, neither do they have extremely long albeit nite lives. Nevertheless, even with a short horizon, say, xed 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 payo function U refers to annual ow payos; that is, U (a) is the payo when all players play a throughout the year. Similarly, let 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 payo received at the end of the year is U (a) and its value discounted to the beginning of the year is U (a) . Now suppose that players can move more frequently in this same one year game. For instance, if they moved twice a year, and there were no discounting then their semi-annual payo from playing a in any period would be 1 (a). With discounting U 2 their semi-annual payo would be the discounted average 1+ U (a) . More generally, if players move K times during the course of the year and the path (a1 , a2 , ..., aK ) results, the discounted total payo at the beginning of the year is 1 K X k (1 K ) K U (ak ). 1 K (1 ) k=1 b b By writing K K and UK, (ak )
1

(1 K ) K (1)
1

U(ak ) this can be rewritten in a familiar

form as,

b Furthermore, for all , limK K = 1. Call the game described above a game with K-responses denoted by G (1), and K let be the game which consists of G (1) followed by an end-game H . The total K K payo from the path (a1 , a2 , ..., aK , s) is,
K X k=1

1 Notice that with this specication, the one-period ( K th of a year) payo func1 K b tion is UK, (1 ) U, the discounted average of an annual payo function U. 1 K (1)

K X k=1

bk b K UK, (ak ).

k K

(1 )

(1 K )
1 K

U(ak ) +

K+1 K

V (s)

or, more compactly,

K X k=1

bk b bK+1 K UK, (ak ) + K V (s). 27

Let (1) denote the set of perfect equilibrium payos from . We obtain the K K following result21 : Theorem 11 For all , if there exists an M > 0 such that H has a threat of M then
K

lim (1) = F . K

Proof. The proof is virtually the same as the proof of Theorem 1, once it is recognized b that the rescaling of the payos from U to UK, implies that the threat M needed to sustain u, goes to 0 as K increases.

Note that in Theorem 11, H can have an arbitrarily small threat. Section 4 derived theorems for nitely repeated games as the length T increased. Using Theorem 11, one can derive an analogue of each of these theorems for games of a xed duration as the frequency of response K increases. An overlapping generations folk theorem for short-lived frequently responding agents can similarly be derived.

Reformulations

In the game hG (T ) , H i, G (T ) was followed by an end-game H and in applying Theorem 1, H was itself taken to be a repeated game. In this section we present suggest some alternative formulations.

6.1

Games of Division

Let H be a game of division in which players split a pie of size L. That is, the P players simultaneously announce an x Rn : n xi = L. If the players make the i1 same announcement they receive this payo, otherwise they receive 0. Call such an end-game a 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: 0, 0 5, 3 3, 5 2, 2 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 T +1 , say, 4 T +1 at the beginning of the game D (T ). For large T, these deposits are innitesimal; 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, (4, 4) , (8, 0) and (0, 8) are possible divisions of the pie. Thus a threat of 4
21

Remarks by Michael Riordon led to this formulation.

28

is available to discipline each players behavior in the period T . Corollary 1 implies that for large and T, any feasible individually rational payo is then sustainable in the game D (T ). For a game with a xed length, but frequent responses Theorem 11 yields the following strong result. Proposition 2 Let G (1) be a game with K responses. If the end-game H is a K game of division with a pie of positive size then
1 K

lim (1) = F . K

In particular, if players move frequently enough in a prisoners dilemma, cooperation can be sustained with any positive pie. For continuous games we also have a strong result, similar to Theorem 5. Proposition 3 Let G be a continuous game with an inecient equilibrium. If the end-game H is a game of division with a pie of positive size then
1 T

lim (T ) = F .

Recall the standard linear Cournot oligopoly model. This has a unique equilibrium if repeated any nite number of times. Nonetheless, Proposition 3 implies that if the rms have a penny to split at the end, then for large any feasible individually rational payo is sustainable with enough repetitions, a result similar to that of Conlon (1996).

6.2

Exogenous Payos

Suppose that after the end of the repeated game G (T ) players receive additional payos according to the exogenously specied function h : AT Rn . Specically, the total payo from a path (a1 , a2 , ..., aT ) is: " T # X t U (at ) + T +1 h(a1 , a2 , ..., aT ).
t=1

Some possible interpretations of the function h are given below.22

Kandoris (1992) model of a nitely 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).
22

29

Games with a Bonus - The Gold Watch Let h be a bonus payo contingent on actions taken during the course of a nitely repeated game. For any u F , there is a contract specifying a strategy combination and a payment of size M to the players contingent on being followed, such that u is sustainable. Although this does not follow directly from Theorem 1 exactly as stated, it is immediately clear from its proof, since h functions exactly as H . 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 1 and Theorem 11 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.23 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 nitely repeated game. The function h can be viewed as resulting from such a commitment.24 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 payo in the repeated game. Nonetheless, it is sucient to permit cooperation to be sustained.

Conclusion

Our earlier work established that if the stage game has distinct equilibrium payos, a folk theorem can be derived (Beno and Krishna (1985)). This paper extends that it idea: The distinct payos in the stage game enables the construction of suciently severe threats in an end-game, and our main result (Theorem 1) essentially takes these end-game threats as a starting point. The utility of Theorem 1 should be apparent: All the major folk theorems can be recast so that they are simple consequences of this result.
We thank Matthew Spitzer for suggesting the gold watch application. 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 1 is a simple consequence of Theorem 2.
24 23

30

A
A.1

Appendix
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 innitely repeated games: punishing players are kept indierent on the support of the minmax (mixed) strategy. For this result we suppose that the game G is nite. Let (T ) denote the set of perfect equilibrium average payos when mixed strateu gies are unobservable. Theorem A1 There exists an M such that if for all large , H has a threat of M then lim lim (T ) = F . u Proof. Recall that for every player i the set N (i) = j N : Uj = ji Ui + ji , ji > 0
1 T

consists of those players whose payos are positive ane transformations of is payo. This denes a partition of N into, say, K equivalence classes: N = N (i1 ) N (i2 ) ... N (iK ) . Choose exactly one player from each member of the partition . Suppose the players so chosen are i1 , i2 , ..., iK and without loss of generality, rename these 1, 2, ..., K. Dene K = {1, 2, ..., K} . For all j, k N if j N (k) we will say that j and k are equivalent players. By construction, for every j N there exists a unique k K such that j and k are equivalent. Let u F , u 0. There exist K vectors u1 , u2 , ..., uK in F satisfying uk 0 such that for all k, l K, k 6= l, uk < ul . (17) k k (as in Abreu, Dutta and Smith (1994)). Fix a player i K and for each k K, k 6= i let xik F be such that xik 6= ui and xik > uk k k k k xik = ui h h if h K, h 6= k (18)

(Such a vector xik exists since for all h K, h 6= k, it is the case that k N (h).) / Let a A be such that U (a) = u. Similarly, for all i let ai A be such that U (ai ) = ui and let aik A be such that U aik = xik . i Given a strategy combination , say that j is observed to deviate from a path i in period t if calls for the players to play the mixed strategy (t) , but js (pure) i action is not in the support of the jth component of (t). 31

Consider the paths dened below (where the probabilities pik and time periods Q, R, R0 and T will be determined later). First, dene
0 :

In periods , + 1, + 2, ..., T : play a; and In period T + 1 : play s.

Next, for every i K, dene:

i :

In periods , + 1, + 2, ..., + R : play mi ; In periods + R + 1, + R + 2, ..., + R + R0 : if the observed outcome R path in the rst R periods is 0 (supp mi ) , for each k K such that k 6= i : play aik with probability pik (0 ) , and P play ai with probability 1 kK pik (0 ) ;
k6=i 0

In periods, + R + R + 1, + R + R0 + 2, ..., T : play ai ; and In period T + 1 : play the equilibrium s of H . Now consider the following strategies.
0 0 Start 1 and continue to follow 1 if no one deviates. l i If j N is observed to deviate from in period t T Q, start t+1 , where i K is equivalent to j. l If player j N is the rst player observed to deviate from in some period t, T Q < t T , then play an equilibrium e of G in each of the periods t + 1, t + 2, ..., T and play sj in period T + 1.

We now show that there exist probabilities pik such that for large enough , Q, R, R0 and T, these are perfect equilibrium strategies. It is sucient to verify that no player wants to deviate from these strategies just once and conform thereafter. Choose R so that for all j N : (R + 1) uj > u where u is the maximum payo of any player in G. Such an R exists since uj > 0. Choose R so that for all > R , for all j N : 1 R+1 uj > u (1 ) 32

and for all j N :

where u is the minimum payo of any player in G and i K is equivalent to j. Claim: There exists an R0 and a R0 such that for all > R0 , for all i, k K, k 6= i R and for all 0 , 00 (supp mi ) there exist pik (0 ) and pik (00 ) such that:
0 R ) ik 0 ik + p ( )xk + 1 pik (0 ) ui k (1 ) 0 (1 R ) ik 00 ik R = Uk (00 ) + R+1 p ( )xk + 1 pik (00 ) ui k (1 ) X and pik (0 ) < 1.

1 R+1 u + R+1 ui > 0 j

R Uk (0 )

R+1 (1

(19)

kK k6=i

P R where Uk (0 ) R r Uk (a0 (r)) is player ks total payo from the R period path r=1 R 0 . Uk (00 ) is dened similarly.

Proof of claim: First, observe that there exists an R0 and a R0 such that for all > R0 , for all i, k K, i 6= K : 1 R 1 ik xk ui . (20) 0 (u u) < k R+1 (1 R ) K 0 (This is because 1 R / R+1 1 R R/R0 as 1.) R Let k (supp mi ) be the R period path that is best for player k and let be R an arbitrary path in (supp mi ) . For any such path notice that : R R (1 ) Uk (k ) Uk () 1 R 0 < R+1 (u u) (21) R+1 (1 R0 ) (1 R0 ) Now consider the expression p pik (k ) xik ui . k k (22)

1 If xik ui > 0 set pik (k ) = 0 and notice that if p = K then by (20) this exceeds k k the left hand side of (21) and if p = 0 it is no greater than the left hand side of (21). 1 Thus there exists a p = pik () [0, K ) such that the two are equal. Similarly, if 1 xik ui < 0 set pik (k ) = K and notice that if p = 0 then again by (20) this exceeds k k 1 the left hand side of (21) and if p = K it is no greater than the left hand side of (21). 1 Thus, again there exists a p = pik () [0, K ) such that the two are equal. ik Therefore, p ()s can be chosen such that for all i, for all k K, k 6= i and for P all , (19) holds and kK pik (0 ) < 1, establishing the claim. 2 k6=i

33

For every i, k K, k 6= i and every path (supp mi ) choose probabilities ik p () as in the claim. l Suppose a player j N is observed to deviate from some and i K is R i equivalent to j. If 0 (supp mi ) is the path in the rst R periods of t when mi is played, the payo to player k N (i) is the left hand side of the equation in (19), / 00 i R whereas if (supp m ) is the path, the payo is the right hand side of (19). By construction these are equal. Thus every player j N (i) is indierent among all the / i R paths that lie in (supp m ) . Next observe that from the denition of mi every player in j N (i) is at a single-period best response when mi is played. The verication that the strategies given above form an equilibrium is now routine. (The fact that the xij s satisfy (18) is important here). The remainder of the proof j may be completed by following the proof of Theorem 1 exactly. 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 nitely repeated games without discounting, G1 (T ), when mixed strategies are not observable and public randomization is not allowed. He makes use of Blackwells approachability theorem, in order to construct the equilibrium strategies and in this construction seems to need the assumption that the set of feasible payos is full dimensional. Fudenberg and Maskin (1991) show that the use of public randomization is not needed for the folk theorem for innitely repeated games with discounting.

References
[1] Abreu, D., P. K. Dutta and L. Smith (1994): The Folk Theorem for Repeated Games: A NEU Condition, Econometrica, 62, pp. 939-948. [2] Aumann, R. and L. Shapley (1994): Long-Term Competition: A Game Theoretic Analysis, in Essays in Game Theory, edited by N. Megiddo, SpringerVerlag, pp. 1-15. [3] Beno J-P. and V. Krishna (1985): Finitely Repeated Games, Econometrica, it, 53, pp. 905-922. [4] Beno J-P. and V. Krishna (1987): Nash Equilibria of Finitely Repeated it, Games, International Journal of Game Theory, 16, pp. 197-204.

34

[5] Bernheim, B. D. and A. Dasgupta (1995): Repeated Games with Asymptotically Finite Horizons, Journal of Economic Theory, 67, pp. 129-152. [6] Chou, C-F. and J. Geanakoplos (1988) : The Power of Commitment, mimeo, Yale University. [7] Conlon, J. (1996): Cooperation for Pennies: A Note on -Equilibria, Journal of Economic Theory, 70, pp.489-500. [8] Crmer, J. (1986): Cooperation in Ongoing Organizations, Quarterly Journal e of Economics, 101, pp. 33-49. [9] Dubey, P. (1986): Ineciency of Nash Equilibria, Mathematics of Operations Research, 11, pp. 1-8. [10] Fudenberg, D. and E. Maskin (1986): The Folk Theorem for Repeated Games with Discounting or with Incomplete Information, Econometrica, 54, pp. 533554. [11] Fudenberg, D. and E. Maskin (1991): On the Dispensability of Public Randomization in Discounted Repeated Games, Journal of Economic Theory, 53, pp. 428-438. [12] Gossner, O. (1995): The Folk Theorem for Finitely Repeated Games with Mixed Strategies, International Journal of Game Theory, 24, pp. 95-107. [13] Kandori, M. (1992): Repeated Games Played by Overlapping Generations of Players, Review of Economic Studies, 59, pp. 81-92. [14] Kreps, D., P. Milgrom, J. Roberts and R. Wilson (1982): Rational Cooperation in the Finitely Repeated Prisoners Dilemma, Journal of Economic Theory, 27, pp. 245-252. [15] Osborne, M. and A. Rubinstein (1994): A Course in Game Theory, Cambridge: MIT Press. [16] Pearce, D. (1992): Repeated Games: Cooperation and Rationality Chapter 4 in Advances in Economic Theory: Sixth World Congress, Vol. 1 edited by J-J. Laont, Econometric Society Monographs, Cambridge University Press, Cambridge, pp. 132-174. [17] Radner, R. (1980): Collusive Behavior in Noncooperative Epsilon Equilibria of Oligopolies with Long but Finite Lives, Journal of Economic Theory, 22, pp. 136-154. [18] Rockafellar, R., Convex Analysis, Princeton University Press, Princeton NJ, 1970 35

[19] Rubinstein, A. (1991): Comments on the Interpretation of Game Theory, Econometrica, 59, pp. 909-924. [20] Rubinstein, A. (1994): Equilibrium in Supergames, in Essays in Game Theory, edited by N. Megiddo, Springer-Verlag, pp. 17-27. [21] Smith, L. (1992): Folk Theorems in Overlapping Generations Games, Games and Economic Behavior, 4, pp. 426-449. [22] Smith, L. (1995): Necessary and Sucient Conditions for the Perfect Finite Horizon Folk Theorem, Econometrica, 63, pp. 425-430. [23] Sorin, S. (1993): Repeated Games with Complete Information, Chapter 4 in Handbook of Game Theory, Volume 1, edited by R. Aumann and S. Hart, North-Holland, pp. 71-107. [24] Sorin, S. (1996): Cooperation Through Repetition: Complete Information, in Cooperation: Game Theoretic Approaches, edited by S. Hart and A. Mas-Colell, Springer-Verlag, pp. 169-198. [25] Wen, Q. (1994): The Folk Theorem for Repeated Games with Complete Information, Econometrica, 62, pp. 949-954.

36