Coordination failure in repeated games with almost-public monitoring

Mailath, George J.; Morris, Stephen Article Coordination failure in repeated games with almost-public monitoring Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Mailath, George J.; Morris, Stephen (2006) : Coordination failure in repeated games with almost-public monitoring, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New York, NY, Vol. 1, Iss. 3, pp. 311-340 This Version is available at: https://hdl.handle.net/10419/150082 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/2.5 Theoretical Economics 1 (2006), 311–340 1555-7561/20060311 Coordination failure in repeated games with almost-public monitoring GEORGE J. MAILATH Department of Economics, University of Pennsylvania STEPHEN MORRIS Department of Economics, Princeton University Some private-monitoring games, that is, games with no public histories, have histories that are almost public. These games are the natural result of perturbing public-monitoring games towards private monitoring. We explore the extent to which it is possible to coordinate continuation play in such games. It is always possible to coordinate continuation play by requiring behavior to have bounded recall (i.e., there is a bound Lsuch that in any period, the last Lsignals are sufficient to determine behavior). We show that, in games with general almost-public private monitoring, this is essentially the only behavior that can coordinate continuation play. KEYWORDS. Repeated games, private monitoring, almost-public monitoring, coordination, bounded recall. JEL CLASSIFICATION. C72, C73, D82. 1. INTRODUCTION Intertemporal incentives often allow players to achieve payoffs that are inconsistent with myopic incentives. For repeated games with public histories, the construction of sequentially rational equilibria with nontrivial intertemporal incentives is straightforward. Since continuation play in a public strategy profile is a function of public histories only, the requirement that continuation play induced by any public history constitute a Nash equilibrium of the original game is both the natural notion of sequential rationality and relatively easy to check (Abreu et al. 1990). These perfect public equilibria (or PPE) use public histories to coordinate continuation play. George J. Mailath: [email protected] Stephen Morris: [email protected] Earlier versions of this material have appeared under the title “Finite State Strategies and Coordination in Repeated Games with Private Monitoring.” Some parts of Sections 4 and 5 first appeared in “Repeated Games with Imperfect Private Monitoring: Notes on a Coordination Perspective.” That paper is subsumed by Mailath and Morris (2002) and this paper. We thank Andrew Postlewaite for helpful conversations and an anonymous referee and especially the editor, Jeffrey Ely, for valuable suggestions. Mailath is grateful for support from the National Science Foundation under grants #SES-0095768 and #SES-0350969. Morris is grateful for support from the John Simon Guggenheim Foundation, the Center for Advanced Studies in the Behavioral Sciences, and National Science Foundation Grant #SES-0518929. Copyright c2006 George J. Mailath and Stephen Morris. Licensed under the Creative Commons Attribution-NonCommercial License 2.5. Available at http://econtheory.org. 312 Mailath and Morris Theoretical Economics 1 (2006) While games with private monitoring (where actions and signals are private) have no public histories to coordinate continuation play, some do have histories that are almost public. We explore the extent to which perfect public equilibrium strategies continue to be equilibria when histories are only almost public. We show that it is always possible to coordinate continuation play by requiring behavior to have bounded recall (i.e., there is a bound Lsuch that in any period, the last Lsignals are sufficient to determine behavior).1But we also show a partial converse: in games with general almost-public private monitoring, this is the only behavior that can coordinate continuation play under an apparently mild restriction on strategies. To make this precise, we must describe “general but almost-public private monitoring” and characterize the restriction on strategies When is a general private-monitoring technology close to some public monitoring technology? To be close, there must be a signaling function for each player that assigns to each private signal either some value of the public signal or a dummy signal (with the interpretation that that private signal cannot be related to any public signal). Using these signaling functions (one for each player), the private monitoring is close to the public monitoring if the probability of private signals mapping to a given public signal, under the private-monitoring technology, is close to the probability of that public signal under the public monitoring (for any given action profile). If there exist such signaling functions satisfying this condition, we say there is almost-public monitoring. If every private signal is mapped to a public signal, we say the almost-public-monitoring game is strongly close to the public-monitoring game. Using the signaling functions, any strategy profile of the public-monitoring game induces behavior in strongly-close-by almost-public-monitoring games. Given a sequence of private signals for a player, that player’s private state is determined by the induced sequence of public signals that are the result of applying his signaling function. We show that every strict PPE with bounded recall induces equilibrium in every strongly-close-by almost-public-monitoring game; and even if the private-monitoring games are not strongly close to the public-monitoring game, there is still a natural sense in which every strict PPE with bounded recall induces equilibrium behavior in every close-by almost-public-monitoring game (Theorem 1). The idea is that with bounded recall we can always restrict posterior beliefs to be sufficiently close to the public monitoring by requiring the private-monitoring technology to be sufficiently close to the public-monitoring technology. This result generalizes the main result in Mailath and Morris (2002), where the private signal set was assumed to equal the public signal set.2 When a strategy profile of the public-monitoring game does not have bounded recall, realizations of the signal in early periods can have long-run implications for behavior. We call profiles with this property separating. While the properties of bounded 1Thus when we refer to strategy profiles that coordinate continuation play in games with private monitoring, we mean strategy profiles where players’ choices are best responses if histories are sufficiently close to being public. 2The extension is nontrivial because the richness of the private signals is important for the formation of that player’s beliefs about the other players’ private states. It turns out that the requirement that the privatemonitoring distribution be close to the public-monitoring distribution places essentially no restriction on the manner in which private signals enter into the formation of posterior beliefs. Theoretical Economics 1 (2006) Coordination failure in repeated games 313 recall and separation do not exhaust possible behavior, they do appear to cover most behaviors of interest.3When the space of private signals is sufficiently rich for some player iin the values of posterior-odds ratios (this is what we mean by “general almost public”), and the profile is separating, it is possible to manipulate that player’s updating over other players’ private states through an appropriate choice of private history. This suggests that it should be possible to choose a private history with the property that player iis in one private state and assigns arbitrarily high probability to all the other players being in a different common private state. A significant difficulty needs to be addressed in order to make this argument: The history needs to have the property that player iis very confident of the other players’ state transitions for any given initial state. This, of course, requires the monitoring to be almost-public. At the same time, monitoring must be sufficiently imprecise that player i, after an appropriate initial segment of the history, assigns positive probability to the other players being in a common state different from i’s private state. This is the source of the difficulty: Fix a period t. For any T-length history (T>t), there is an "(decreasing in T) such that for private monitoring "-close to the public monitoring, player iis sufficiently confident of the period Tprivate states of players j6=ias a function of their period tprivate states (and the history). However, this "puts an upper bound on the prior probability that player ican assign in period tto the players j6=ibeing in a common state different from i’s private state. Since the choice of Tis decreasing in this prior (i.e., larger Tis required for smaller priors), there is a tension in the determination of T and ". We show, however, that this tension can be resolved for separating profiles implementable using a finite number of states. For such profiles the history can be chosen so that not only do the relevant states cycle, but every other state transits under the cycle to a cycling state. The cycle allows us to effectively choose the Tabove independently of the prior, and gives us our main result (Theorem 3): Separating strict PPE profiles of public-monitoring games implementable using a finite number of states do not induce Nash equilibria in any strongly-close-by games with rich private monitoring. Thus, separating strict PPE of public-monitoring games are not robust to the introduction of even a minimal amount of private monitoring. Consequently, separating behavior in private-monitoring games typically cannot coordinate continuation play (Corollary 1). On the other hand, bounded recall profiles are robust to the introduction of private monitoring. The extent to which bounded recall is a substantive restriction on the set of payoffs is unknown.4Our results do suggest, even for public-monitoring games, that bounded recall profiles are particularly attractive (since they are robust to the introduction of private monitoring). Moreover, other apparently simple strategy profiles are problematic. 3We provide one example of a non-separating profile without bounded recall in Section 4 (Example 3). This profile is not robust to the introduction of private monitoring. We do not know if there exist nonseparating profiles without bounded recall that are robust to private monitoring. 4Cole and Kocherlakota (2005) show that for some parameterizations of the repeated prisoners’ dilemma, the restriction to strongly symmetric bounded recall PPE results in a dramatic collapse of the set of equilibrium payoffs. 314 Mailath and Morris Theoretical Economics 1 (2006) We have analyzed the robustness of fixed strategy profiles to private monitoring. Our results do not say anything about the set of all equilibrium payoffs in private-monitoring games.5While this classic question is important, we believe that there are at least three reasons why it is nonetheless also interesting to focus on a fixed strategy profile. First, researchers using repeated game theory to understand economic phenomena are interested in hypothesizing and testing particular strategy profiles.6Second, understanding properties of particular strategy profiles may turn out to be an important step in characterizing the set of all equilibrium payoffs. Finally, one of our findings is that fine details of strategy profiles, such as history dependence, that are irrelevant for the classic recursive characterization of the PPE payoff set are very important for the robustness question we consider, and such fine details might turn out to be significant for other questions as well. Both our positive and negative results restrict attention to strict PPE, and the assumption is important for both kinds of results. In such equilibria, players are not indifferent between alternative actions and are thus coordinated in their continuation play. Such strategy profiles capture basic intuitions about how cooperation can be sustained in repeated games by the threat of coordinated deviation to punishment paths; they form the basis of empirical applications of repeated game theory (see the references in footnote 6); and we believe they are interesting objects of study. However, as noted in footnote 5, the most permissive results in the private-monitoring literature have used strategies with a significant amount of randomization and indifference. The results in this paper do not have anything to say about the robustness of such strategies.7 This paper introduces a useful representation of finite state strategies for privatemonitoring games. Each player has a finite set of private states, a transition function mapping private signals and states into new states, and decision rules for the players, specifying behavior in each state. The transition function and decision rules define a Markov process on vectors of private states. This representation is sufficient to describe behavior under the given strategies, but is not sufficient to verify that the strategies are 5Mailath and Samuelson (2006, Chapter 12) introduces the main issues and concepts. See Kandori (2002) for a brief survey of this literature, as well as the accompanying symposium issue of the Journal of Economic Theory on “Repeated Games with Private Monitoring.” For the repeated prisoners’ dilemma with almost-perfect private monitoring, folk theorems have been proved using both equilibria with a coordination interpretation (for example, Sekiguchi 1997 and Bhaskar and Obara 2002) and those that are “belief-free” (for example, Piccione 2002,Ely and Välimäki 2002, and Matsushima 2004), where equilibrium strategies are constructed using randomization to ensure that players are indifferent between some actions at all histories. While folk theorems cannot be proved using belief-free strategies for general payoff matrices (Ely et al. 2005), variations on belief-free strategy profiles have been used to prove general folk theorems (Hörner and Olszewski 2005). 6See, for example, Axelrod (1984), Ellison (1994), and Greif (2005). 7Bhaskar and van Damme (2002) and Ely (2002) show that trigger strategy profiles, which are strict PPE of a repeated prisoners’ dilemma with imperfect public public monitoring, can be approximated in nearby games with private monitoring with a strategy profile with strict mixing. This possibility suggests that allowing non-strict equilibria may greatly assist in establishing robustness results. On the other hand, the equilibria with mixing require players to randomize differently at different payoff-equivalent histories, which is arguably implausible. Bhaskar (1998) and Bhaskar and van Damme (2002) suggest that such strategies often do not survive extensive form purification perturbations. Theoretical Economics 1 (2006) Coordination failure in repeated games 315 optimal. It is also necessary to know how each player’s beliefs over the other players’ private states evolve. This is at the heart of the question of whether histories can coordinate continuation play, since, given a strategy profile, a player’s private state determines that player’s continuation play. The crux of our analysis concerns how to track the evolution of beliefs over other players’ private states during the course of play. In this paper, we use this representation to analyze private-monitoring profiles constructed from a PPE. However, the method is more general and we believe that it may be of more general use. Examples can be found in Mailath and Samuelson (2006, Section 12.4 and Chapter 14), where the method is used to analyze the mixed strategy employed in the classic analysis of Sekiguchi (1997) and define belief-free equilibria. Finally, we note that we have not allowed any communication beyond that contained in the equilibrium strategies. We view our findings as underlining the importance of public communication in private-monitoring games as a mechanism to facilitate coordination. For some recent work on communication in private-monitoring games, see Compte (1998), Kandori and Matsushima (1998), Fudenberg and Levine (2004), and McLean et al. (2002). 2. GAMES WITH IMPERFECT MONITORING 2.1 Private-monitoring games The infinitely-repeated game with private monitoring is the infinite repetition of a stage game in which at the end of each period, each player learns only the realized value of a private signal. There are nplayers, with the finite stage-game action set for player i∈N≡{1,...,n}denoted Ai. At the end of each period, each player iobserves a private signal, denoted ωi, drawn from a finite set Ωi. The signal vector ω≡(ω1,...,ωn)∈Ω≡ Ω1×···×Ωnoccurs with probability π(ω|a)when the action profile a∈A≡QiAiis chosen. Player idoes not receive any information other than ωiabout the behavior of the other players. All players use the same discount factor, δ. Since ωiis the only signal a player observes about opponents’ play, we assume (as usual) that player i’s payoff after the realization (ω,a)depends only on (ωi,ai). We denote this payoff by u∗ i(ωi,ai). Stage game payoffs are then given by ui(a)≡ Pωu∗ i(ωi,ai)π(ω|a). It is convenient to index games by the monitoring technology (Ω,π), fixing the set of players and action sets. A pure strategy for player iin the private-monitoring game is a function si:Hi→Ai, where Hi≡∪∞ t=1(Ai×Ωi)t−1 is the set of private histories for player i. 2.2 Public-monitoring games We turn now to the benchmark public-monitoring game for our games with private monitoring. The finite action set for player i∈Nis again Ai. The public signal is denoted yand is drawn from a finite set Y. The probability that the signal yoccurs when the action profile a∈A≡QiAiis chosen is denoted ρ(y|a). We refer to (Y,ρ)as 316 Mailath and Morris Theoretical Economics 1 (2006) the public-monitoring distribution. Player i’s payoff after the realization (y,a)is given by e u∗ i(y,ai). Stage game payoffs are then given by e ui(a)≡Pye u∗ i(y,ai)ρ(y|a). The infinitely repeated game with public monitoring is the infinite repetition of this stage game in which at the end of each period each player learns only the realized value of the signal y. Players do not receive any other information about the behavior of the other players. All players use the same discount factor, δ. A strategy for player iis public if, in every period t, the action it prescribes depends only on the public history ht∈Yt−1, and not on i’s private history. Henceforth, by the term public profile, we always mean a strategy profile for the public-monitoring game that is itself public. A perfect public equilibrium (PPE) is a profile of public strategies that, after any public history ht, specifies a Nash equilibrium for the repeated game. Under imperfect full-support public monitoring, every public history arises with positive probability, and so every Nash equilibrium in public strategies is a PPE. Any pure public strategy profile can be described as an automaton as follows: There is a set of states, W, an initial state, w1∈W, a transition function σ:W×Y→W, and a collection of decision rules, di:W→Ai. In the first period, each player ichooses action a1 i=di(w1). The vector of actions, a1, then generates a signal y1according to the distribution ρ(·|a1). In the second period, each player ichooses the action a2 i=di(w2), where w2=σ(w1,y1), and so on. Since we can take Wto be the set of all histories of the public signal, ∪t≥1Yt,Wis at most countably infinite. A public profile is finite if W is a finite set. Note that, given a pure strategy profile (and the associated automaton), continuation play after any history is determined by the public state reached by that history. Denote the vector of average discounted expected values of following the public profile (W,w,σ,d)(so that the initial state is w) by φ(w). Define a function g:A× W→Wby g(a;w)≡(1−δ)u(a) + δPyφ(σ(w,y))ρ(y|a). We have (from Abreu et al. 1990), that if the profile is an equilibrium, then, for all w∈W, the action profile (d1(w),...,dn(w)) ≡d(w)is a pure strategy equilibrium of the static game with strategy spaces Aiand payoffs gi(·;w)for each iand, moreover, φ(w) = g(d(w),w). Conversely, if (W,w1,σ,d)describes an equilibrium of the static game with payoffs g(·;w)for all w∈W, then the induced pure strategy profile in the infinitely repeated game with public monitoring is an equilibrium.8A PPE (W,w1,σ,d)is strict if, for all w∈W,d(w)is a strict Nash equilibrium of the static game g(·;w).9 A maintained assumption throughout our analysis is that public monitoring has full support. ASSUMPTION 1. ρ(y|a)>0 for all y∈Yand all a∈A. 8We have introduced a distinction between Wand the set of continuation payoffs for convenience. Any pure strategy equilibrium payoff can be supported by an equilibrium where W⊂RIand φ(w) = w(again, see Abreu et al. 1990). 9Equivalently, a PPE is strict if each player strictly prefers his equilibrium strategy to every other public strategy. For a large class of public-monitoring games, strictness is without loss of generality, in that a folk theorem holds for strict PPE (Fudenberg et al. 1994, Theorem 6.4 and remark). Theoretical Economics 1 (2006) Coordination failure in repeated games 317 We extend the domain of σfrom W×Yto W×∪∞ t=1Ytby recursively defining σ(w1,ht) = σ(σ(w1,ht−1),yt)for all ht∈Yt−1, where ht= (ht−1,yt). DEFINITION 1. An automaton (W,w1,σ,d)is minimal if for every state b w∈Wthere exists a sequence of signals b h`such that b w=σ(w1,b h`)and for every pair of states w,b w∈W, there exists a sequence of signals hLsuch that for some i,di(σ(w,hL)) 6= di(σ(b w,hL)). The restriction to minimal automata is without loss of generality: every profile has a minimal representing automaton. Moreover, this automaton is essentially unique.10 Accordingly, we treat a public strategy profile and its minimal representing automaton interchangeably. 2.3 Almost-public monitoring We now define what it means for a private-monitoring distribution to be close to a public-monitoring distribution. DEFINITION 2. The private-monitoring distribution (Ω,π)is "-close under fto the public-monitoring distribution (Y,ρ), where f= (f1,...,fn)is a vector of signaling functions fi:Ωi→Y∪{∅}, if 1. for each a∈Aand y∈Y, π({ω:fi(ωi) = yfor all i}|a)−ρ(y|a)≤", and 2. for all y∈Y,ωi∈f−1 i(y), and all a∈A, if π({ωi}|a)>0, then π({ω−i:fj(ωj) = yfor all j6=i}|(a,ωi)) ≥1−". The private-monitoring distribution (Ω,π)is strongly "-close under fto the publicmonitoring distribution (Y,ρ)if it is "-close under fand, in addition, all the signaling functions map into Y. A private-monitoring distribution (Ω,π)is (strongly) "-close to the public-monitor- ing distribution (Y,ρ)if there exists a vector of signaling functions fsuch that (Ω,π)is (strongly) "-close under fto (Y,ρ). If the private monitoring is "-close under f, but not strongly "-close under f, then some private signals are not associated with any public signal: there is a signal ωisatisfying fi(ωi) = ∅. Such an “uninterpretable” signal may contain no information about the signals observed by the other players. 10Suppose (W,w1,σ,d)and (f W,e w1,e σ,e d)are two minimal automata representing the same public strategy profile. Define a mapping ϕ:W→f Was follows: Set ϕ(w1) = e w1. For b w∈W\{w1}, let b h`be a public history reaching b w(i.e., b w=σ(w1,b h`)), and set ϕ(b w) = e σ(e w1,b h`). Since both automata are minimal and represent the same profile, ϕdoes not depend on the choice of public history reaching b w. It is straightforward to verify that ϕis one-to-one and onto. Moreover, e σ(e w,y) = ϕ(σ(ϕ−1(e w),y), and d(w) = e d(ϕ(w)). 318 Mailath and Morris Theoretical Economics 1 (2006) The condition of "-closeness in Definition 2 can be restated as follows. Recall from Monderer and Samet (1989) that an event is p-evident if, whenever it is true, everyone assigns probability at least pto it being true. The following lemma is a straightforward application of the definitions, and so we omit the proof. LEMMA 1. Suppose fi:Ωi→Y∪{∅}, i =1,...,n, is a collection of signaling functions. The private-monitoring distribution (Ω,π)is "-close under f to the public monitoring distribution (Y,ρ)if and only if for each public signal y , the set of private signal profiles {ω:fi(ωi) = y for all i}is (1−")-evident (conditional on any action profile) and has probability within "of the probability of y (conditional on that action profile). DEFINITION 3. A private-monitoring game (u∗,(Ω,π)) is "-close (under f ) to the publicmonitoring game (e u∗,(Y,ρ)) if (Ω,π)is "-close under fto (Y,ρ)and e u∗ i(fi(ωi),ai)−u∗ i(ωi,ai)< " for all i∈N,ai∈Ai, and ωi∈f−1 i(Y). We say also that such a private-monitoring game has almost-public monitoring. Note that because of our maintained assumption that public-monitoring games have full support monitoring, a private-monitoring game that has almost-public monitoring relative to a fixed ρdoes not have “almost perfect” monitoring in the sense usually assumed in the literature.11 The ex ante stage payoffs of any almost-public-monitoring game are close to the ex ante stage payoffs of the benchmark public-monitoring game (the proof is in the Appendix). LEMMA 2. For all η > 0, there is " > 0such that if (u∗,(Ω,π)) is "-close to (e u∗,(Y,ρ)), then X ω1,...,ωn u∗ i(ωi,ai)π(ω1,...,ωn|a)−X ye u∗ i(y,ai)ρ(y|a)< η. Fix a public profile (W,w1,σ,d)of a full-support public-monitoring game (e u∗, (Y,ρ)), and, under f, a strongly "-close private-monitoring game (u∗,(Ω,π)). The public profile induces a private profile in the private-monitoring game in a natural way: Player i’s strategy is described by the automaton (W,w1,σi,di), where σi(w,ωi) = σ(w,fi(ωi)) for all ωi∈Ωiand w∈W. The set of states, initial state, and decision function are from the public profile. The transition function σiis well-defined, because the signaling functions all map into Y, rather than Y∪{∅}. Note that by construction, each player’s strategy is “action-free,” i.e., it depends only on past signals and not on past actions of that player. (See Mailath and Samuelson 2006, Chapter 12 for more discussion of “action-free.”) 11The order of quantifiers is important: We can construct almost-perfect almost-public monitoring distributions by considering full-support public-monitoring distributions arbitrarily close to perfect monitoring—see Mailath and Morris (2002, Section 6). Theoretical Economics 1 (2006) Coordination failure in repeated games 325 private histories. Let e a1=d1(b w),e a2=d2(¯ w),b a2=d2(b w), and a† 2=d2(w†), and suppose there are two private signals, ω0 1and ω00 1consistent with y, satisfying π1(ω0 1|e a1,a† 2)> π1(ω0 1|e a)> π1(ω0 1|e a1,b a2) and π1(ω00 1|e a1,b a2)> π1(ω00 1|e a)> π1(ω00 1|e a1,a† 2). Then, after observing the private signal ω0 1, we have Pr(w2=b w|ht 1,ω0 1) Pr(w2=¯ w|ht 1,ω0 1)=π1(ω0 1|e a1,b a2) π1(ω0 1|e a) Pr(w2=b w|ht 1) Pr(w2=¯ w|ht 1)<Pr(w2=b w|ht 1) Pr(w2=¯ w|ht 1) as desired, but Pr(w2=w†|ht 1,ω0 1)/Pr(w2=¯ w|ht 1,ω0 1)increases. On the other hand, after observing another private signal ω00 1, also consistent with y, while the odds ratio Pr(w2=w†|ht 1,ω00 1)/Pr(w2=¯ w|ht 1,ω00 1)falls, Pr(w2=b w|ht 1,ω00 1)/Pr(w2=¯ w|ht 1,ω00 1) increases. However, it may be that the increases can be offset by appropriate decreases, so that, for example, ω0 1followed by two realizations of ω00 1results in a decrease in both odds ratios. If so, a sufficiently high number of realizations of ω0 1ω00 1ω00 1result in Pr(w26= ¯ w|ht 1)/Pr(w2=¯ w|ht 1)being close to zero. In terms of the odds ratios, the sequence of signals ω0 1ω00 1ω00 1lowers both odds ratios if, and only if, π1(ω0 1|e a1,b a2) π1(ω0 1|e a)π1(ω00 1|e a1,b a2) π1(ω00 1|e a)2 <1 and π1(ω0 1|e a1,a† 2) π1(ω0 1|e a)π1(ω00 1|e a1,a† 2) π1(ω00 1|e a)2 <1. Our richness condition on private-monitoring distributions captures this idea. For a private-monitoring distribution (Ω,π), define γaa0 −i(ωi)≡logπi(ωi|ai,a−i)−logπi(ωi|ai,a0 −i) and let γa(ωi) = (γaa0 −i(ωi))a0 −i∈A−i,a0 −i6=a−idenote the vector in R|A−i|−1of the log odds ratios of the signal ωiassociated with different action profiles. The last two displayed equations can then be written as 1 3γe a(ω0 1)+ 2 3γe a(ω00 1)>0, where 0is the 2×1 zero vector.16 DEFINITION 5. A private-monitoring distribution (Ω,π)is rich for player i, given his signaling function fi, if for all a∈Aand all y∈Y, the convex hull of the set of vectors {γa(ωi):ωi∈f−1 i(y)and πi(ωi|ai,a0 −i)>0 for all a0 −i∈A−i}has a nonempty intersection with R|A−i|−1 ++ . 16The convex combination is strictly positive (rather than negative) because the definition of γaa0 −iinverts the odds ratios from the displayed equations. 326 Mailath and Morris Theoretical Economics 1 (2006) Note that we require only that private monitoring be rich for one player. It is useful to quantify the extent to which the conditions of Definition 5 are satisfied. Since the spaces of signals and actions are finite, the number of constraints in Definition 5 is finite, and so for any rich private-monitoring distribution, the set of ζ over which the supremum is taken in the next definition is non-empty.17 DEFINITION 6. Given f, the richness of a rich private-monitoring distribution (Ω,π)for iis the supremum of all ζ > 0 satisfying: for all a∈Aand all y∈Y, the convex hull of the set of vectors {γa(ωi):ωi∈f−1 i(y)and πi(ωi|ai,a0 −i)≥ζfor all a0 −i∈A−i}has a nonempty intersection with R|A−i|−1 ζ≡{x∈R|A−i|−1 ++ :xk≥ζfor k=1,...,|A−i|−1}. The second weakening of the logic of Example 1 described above concerns the nature of the strategy profile. The logic assumed that there is a signal ysuch that b w= σ(b w,y)and ¯ w=σ(¯ w,y). Thus along the history (y,y,...), if the player started out in distinct states b wor ¯ w, he would remain in those distinct states and would continue to play in distinct ways. But the logic continues to hold if there exists an arbitrary history hsuch that some distinct initial states lead to distinct states forever and if, from such distinct states, play is distinct along that particular history infinitely often. This is the idea behind the following definition of a separating strategy profile. Define R(e w)as the set of states that are repeatedly reachable in the same period as e w(i.e., R(e w) = {w∈W:{w,e w} ⊂ Wtinfinitely often}). Given an outcome path h≡(y1,y2,...)∈Y∞, let τh≡(yτ,yτ+1,...)∈Y∞denote the outcome path from period τ, so that h= (hτ,τh)and τhτ+t= (yτ,yτ+1,...,yτ+t−1). Consider a continuation path (e w,h)consisting of an initial state e wfollowed by an outcome path h. The continuation path (e w,h)satisfies state-separation if there is another state w∈R(e w)such that starting in state winstead of e wwould lead to distinct states into the infinite future: formally, there exists another state w∈R(e w)that satisfies σ(w,ht)6=σ(e w,ht)for all t. In this case, state wis separated from e walong history h. Recall from the proof of the second claim in Lemma 3 that every unbounded recall profile induced by a finite automaton has a continuation path (e w,h)satisfying state-separation. The logic of our proof requires not only state-separation, but in addition distinct behavior on the continuation path satisfying state-separation. The continuation path (e w,h)satisfies behavior-separation if whenever state w∈R(σ(e w,hτ)) is separated from σ(e w,hτ), then all players choose different actions along the outcome path τhinfinitely often. Formally, for all τand w∈R(σ(e w,hτ)), if σ(w,τhτ+t)6=σ(e w,hτ+t)for all t≥0, then di(σ(w,τhτ+t)) 6=di(σ(e w,hτ+t)) infinitely often, for all i. Notice that every continuation path satisfies behavior-separation if, for each player, distinct states always lead to distinct actions. The need to behavior-separate the state e wfrom every other state that can be reached infinitely often is illustrated by our earlier discussion: because private monitoring implies all such states are assigned positive 17The bound ζappears twice in the definition. Its first appearance ensures that for all ζ > 0, there is a uniform upper bound on the number of private signals satisfying πi(ωi|ai,a0 −i)≥ζin any privatemonitoring distribution with a richness of at least ζ. Theoretical Economics 1 (2006) Coordination failure in repeated games 327 A B C A3,3 0,0 0,0 B0,0 3,3 0,0 C0,0 0,0 2,2 FIGURE 3. The normal form for Example 3. probability by a player’s beliefs, we need to have signals that are informative about these states relative to e w. Now we have: DEFINITION 7. The public strategy profile is separating if there is a state e wand an outcome path h∈Y∞such that (e w,h)satisfies state-separation and behavior-separation. Clearly, a separating profile cannot have bounded recall. The key question is how much stronger is this property than having unbounded recall under the restriction to finite state strategies. Since every finite unbounded recall profile has a state-separating path, the only way a finite state strategy profile with unbounded recall can fail separation is if every continuation path satisfying state-separation fails behavior-separation. The following example illustrates this possibility. EXAMPLE 3. The stage game is given in Figure 3. In the public-monitoring game, there are two public signals, y0and y00, with distribution (0 <q<p<1) ρ(y00 |a1a2) = (pif a1=a2 qotherwise. Finally, the public profile is illustrated in Figure 4. Under any outcome path in which the sequence y0y0or y0y00 occurs, all states transit to the same state. Under any outcome path in which only y00 appears, the state eventually cycles between wAand b wA. Thus continuation path (w,h)is state-separating only if h= (y00,y00,...). But this continuation path is not behavior separating, since action Ais then played forever. ◊ We think of this failure as pathological. In this example, it is easy to see that the profile is not robust. After enough realizations of private signals corresponding to y00, beliefs must assign roughly equal probability to wAand b wA,18 and so after the first realization of a private signal corresponding to y0,Bis the only best reply (even if the current state is wC). We do not have an example of a finite state strategy profile with unbounded recall that fails separation but is robust. Example 3 suggests an intuition why such an example might be hard to find: a strategy profile with unbounded recall can fail separation only if all state-separated states give rise to identical behavior most of the time. With the 18The details of this calculation can be found in Mailath and Samuelson (2006, Example 13.4.6). 328 Mailath and Morris Theoretical Economics 1 (2006) A wA w ˆ B wC w y′ y′ y′′ y′′ y′′ y ′ ′ y′ y′ FIGURE 4. The strategy profile for Example 3. In states wAand b wAthe action Ais played, while in wBthe action Band in wC, the action Cis played. possibility of belief drift, as in the example, it seems hard to make this consistent with equilibrium. Moreover, this possibility of drift implies also that showing that these unbounded recall strategy profiles are not robust requires a quite different proof strategy than that pursued in this paper. It remains to ensure that, under private monitoring, players may transit to different states. It suffices to assume the following, weaker than full-support, condition:19 DEFINITION 8. A private-monitoring distribution (Ω,π)that is "-close to a public-moni- toring distribution (Y,ρ)has essentially full support if for all (y1,...,yn)∈Yn, π{(ω1,...,ωn)∈Ω:fi(ωi) = yi,i=1,...,n}>0. THEOREM 3. Fix a separating strict finite PPE of a full-support public-monitoring game (e u∗,(Y,ρ)). For all ζ > 0, there exists "0>0such that for all " < "0, if (u,(Ω,π)) is a private-monitoring game strongly "-close under some signaling function f to (e u∗,(Y,ρ)) with (Ω,π)having richness, given f , for some player i of at least ζand essentially full support, then the induced private profile is not a Nash equilibrium of the private-monitoring game. It is worth noting that the bound on "is a function only of the richness of the private monitoring. It is independent of the probability that a disagreement in private states arises. By considering finite state profiles that are separating, not only is the difficulty identified in the Introduction dealt with (as we discuss at the end of the next section), but we can accommodate arbitrarily small probabilities of disagreement. 19If an essentially-full-support private monitoring distribution does not have full support, Nash equilibria of the private-monitoring game may not have realization-equivalent sequentially-rational strategy profiles. Theoretical Economics 1 (2006) Coordination failure in repeated games 329 Thus, separating strict PPE of public-monitoring games are not robust to the introduction of private monitoring. It, of course, implies also that separating behavior in the private-monitoring game typically cannot coordinate continuation play in the following sense. Say a profile is "-strict if all the incentive constraints are satisfied by at least ". (The result follows immediately from upperhemicontinuity and Theorem 3.) COROLLARY 1. Fix a vector of signaling functions f , fi:Ωi→Y . Suppose {(uk,(Ω,πk))} is a sequence of private-monitoring games, with (uk,(Ω,πk)) strongly 1/k-close to some public-monitoring game (e u∗,(Y,ρ)) and {(Ω,πk)}a rich (for some player i) sequence of distributions. Fix a pure strategy profile of the private-monitoring game in which each player’s strategy respects his signaling function f j(i.e., σj(hj,aj,ωj) = σj(hj,aj,b ωj)if fj(ωj) = fj(b ωj)6=∅). Suppose this profile is separating (when interpreted as a public profile). For all " > 0, there exists k0such that for k >k0, this profile is not an "-strict Nash equilibrium. Since the equilibrium failure of separating profiles seems to arise after private histories that have low probability, an attractive conjecture is that equilibrium can be restored by appropriately modifying the profile at only the problematic histories. Unfortunately, such a modification appears to require additional modifications to the profile, destroying the connection to the public-monitoring game. 5. THE PROOF OF THEOREM 3 Our proof exploits an alternative characterization of separation that holds for finite state strategies, reported in the next lemma and corollary (proved in the Appendix). LEMMA 4. A finite public strategy profile of the public-monitoring game is separating if, and only if, there is a finite sequence of signals hm, a collection of states Wc, and a state ¯ w∈Wcsuch that (i) σ(w,hm) = w for all w ∈Wc, (ii) σ(w,hm)∈Wcfor all w ∈R(¯ w), (iii) ∀w∈Wc\{ ¯ w},∀i∃`,2≤`≤m, such that di(σ(w,hk)6=di(σ(¯ w,hk), and (iv) |Wc|≥2. We emphasize that each state in the set of states Wccycles under the given finite sequence of signals and every state reachable (infinitely often) in the same period as ¯ w is taken into Wcby one round of the cycle. 330 Mailath and Morris Theoretical Economics 1 (2006) COROLLARY 2. Suppose (W,w1,σ,d)is the minimal automaton of a separating finite public strategy profile. For any player i, the history hm, set of states Wc, and state ¯ w∈Wc can be chosen so that, in addition, di(b w)6=di(¯ w)for some b w∈Wc\{ ¯ w}. The proof of Theorem 3 is by contradiction. Suppose there exists ζ > 0 such that for all kthere exists a private-monitoring game (u,(Ωk,πk)) strongly 1/k-close under some fto (e u∗,(Y,ρ)) with (Ωk,πk)having richness at least ζ, with the induced private profile a Nash equilibrium of the private-monitoring game. The basic argument is most easily seen if the space of signals for each player is independent of k, so that Ωk i= Ωi. Then, we can assume πkconverges to a limit distribution π∞on Ω(by choosing a subsequence if necessary). The behavior of the beliefs of player iover the private states of the other players under the limit private monitoring distribution (Ω,π∞)is significantly easier to describe. Since (Ω,πk)is strongly 1/k-close to (Y,ρ) and πk→π∞, for each y∈Ythe event {(ω1,...,ωn):ωi∈f−1 i(y)}is common belief under π∞. Moreover, if the other players start in the same state (such as ¯ w) then they stay in the same state thereafter. We can thus initially focus on finding the appropriate sequence of signals to manipulate i’s updating about the current private states of the other players, without being concerned about the possibility that subsequent realizations derail the process (we deal with that issue subsequently). The difficulty, of course, is that Ωk idepends on k, and moreover, that in principle as kgets large, so may Ωk i. We can however, proceed as follows: For each kand ai∈Ai, let Ωk,ai i={ωi∈Ωk i:πk i(ωi|ai,a0 −i)> ζ for all a0 −i∈A−i}. Since (Ωk,πk)is strongly close to (Y,ρ), every signal in Ωk iis associated with some public signal, and so we can partition Ωk,ai iinto subsets of private signals associated with the same public signal, Ωk,ai i(y). Order arbitrarily the signals in ∪aiΩk,ai i(y), and give the `-th signal in the order the label (y,`). Let λi,y≡∪aiΩk,ai i(y); note that λi,yis (crudely) bounded above by λ∗≡ |Ai|/ζ for all k(recall footnote 17). With this relabeling, and defining Ωi≡∪y∈Y{(y,1),(y,2),...,(y,λ∗)}, a finite set, we have, for all iand k, Ωk i⊂Ωi∪Ωk i\∪ai∈AiΩk,ai i (1) and Ωk i∩Ωi6=∅. Without loss of generality, we can assume (1) holds with equality (simply include any signal ωi∈Ωi\Ωk iin Ωk i, so that πk i(ωi|a) = 0). We augment Ωi, for each y∈Y, by a new signal denoted ωy i, and define Ω∞ i≡Ωi∪ (∪y{ωy i}). We interpret ωy ias the set of i’s private signals associated with ythat are not in Ωi. For each k, we can interpret Ω∞ ias a partition of Ωk i(each ωi∈Ωiappears as a singleton, while ωy i≡ {ωi∈Ωk i\(∪ai∈AiΩk,ai i):fi(ωi) = y}may be empty). For each a∈A, denote by b πk(· | a)the probability distribution on QiΩ∞ iinduced by πk(· | a). Note that we now have a sequence of probability distributions {b πk(·|a)}kfor each a∈A on a common finite signal space QiΩ∞ i. Theoretical Economics 1 (2006) Coordination failure in repeated games 331 By passing to a subsequence if necessary, we can assume {b πk(ω|a)}kis a convergent sequence with limit π∞(ω|a)for all a∈A,ω∈QiΩ∞ i. Note that (Ω∞,π∞)is 0-close to (Y,ρ). Because there are only a finite number of players, by passing to a further subsequence if necessary, we can assume that the private-monitoring distribution is rich for the same player i; we call this player the rich player. Moreover, by passing to yet a further subsequence if necessary, we can assume also that, for the rich player i,ai∈Ai, and y∈Y, the convex hull of the set of vectors {γ∞ a(ωi):ωi∈f−1 i(y),π∞ i(ωi|ai,a0 −i)> ζ for all a0 −i∈A−i}has a nonempty intersection with R|A−i|−1 ζ, where γ∞ aa0 −i (ωi)≡logπ∞ i(ωi|ai,a−i)−logπ∞ i(ωi|ai,a0 −i) and γ∞ a(ωi) = (γ∞ aa0 −i (ωi))a0 −i∈A−i,a0 −i6=a−i. In the following lemma, a private signal ωjfor player jis consistent with the private signal ωifor player iif fj(ωj) = fi(ωi), where fiand fjare the signaling functions from Definition 2. It is an implication of this lemma that if player iassigns strictly positive probability to all the other players being in the state ¯ w, then after sufficient repetitions of the cycle ~ ωL i(defined in Lemma 5), player ieventually assigns probability arbitrarily close to 1 that at the end of a cycle, all the other players are in the state ¯ w. LEMMA 5. Fix a finite separating public profile of the public-monitoring game, and let ¯ w , b w , Wc, be the states and set of states identified in Corollary 2 for the rich player i. Then, there exists a finite sequence of private signals for player i, ~ ωL i≡(ω1 i,ω2 i,...,ωL i), such that (i) σi(b w,~ ωL i) = b w , (ii) for all sequences of private signals, ~ ωL j, for any player j 6=i consistent with ~ ωL i, σj(w,~ ωL j) = w for all w ∈Wc, and (iii) for all w∈Wn−1 c\{ ¯ w1}, A(~ ωL i;w)≡Pr∞(~ ωL i|w−i=w,wi=b w) Pr∞(~ ωL i|w−i=¯ w1,wi=b w)<1, where Pr∞denotes probabilities calculated under π∞and the assumption that all players follow the private profile. PROOF. The cycle ¯ y1,..., ¯ ymfrom Lemma 4 induces a cycle in the states ¯ w=¯ w1, ..., ¯ wm+1=¯ w1and b w=b w1,..., b wm+1=b w1. We index the cycle by `and write ¯ a`=d(¯ w`) and b a` i=di(b w`). Let e a`≡(b a` i,¯ a` −i). Richness implies that for each `, there exists a vector of nonnegative integers, (nωi)ωi∈f−1 i(y`), so that for all a0 −i6=¯ a` −i, X ωi∈f−1 i(¯ y`) γ∞ e a`,a0 −i (ωi)nωi>0. 332 Mailath and Morris Theoretical Economics 1 (2006) Since γ∞ e a`,a0 −i (ωi) = logπ∞ i(ωi|e a`)/π∞ i(ωi|b a` i,a0 −i), we have, for all a0 −i6=¯ a` −i, Y ωi∈f−1 i(¯ y`)π∞ i(ωi|e a`) π∞ i(ωi|b a` i,a0 −i)nωi >1. Letting n`=Pωi∈f−1 i(y`)nωifor each `, denote by N0the lowest common multiple of {n1,...,nm}. Let ~ ωL idenote the cycle of private signals for player iconsistent with cycling Ntimes through the public signals ¯ y1,¯ y2,..., ¯ ymand in which for each `, the private signal ωi∈f−1 i(y`)appears (N0/n`)nωitimes. This cycle is of length L≡mN 0. Given a private state profile w∈Wn−1 c, let ˇ a` −idenote the action profile taken in period `of the cycle. Then, A(~ ωL i;w)≡Pr∞(~ ωL i|wt −i=w,wi=b w) Pr∞(~ ωL i|wt −i=¯ w1,wi=b w) = m Y `=1  Y ωi∈f−1 i(¯ y`)π∞ i(ωi|b a` i,ˇ a` −i) π∞ i(ωi|e a`)nωi   N/n` . For w6=¯ w1, in each period at least one player is in a private state different from ¯ w. From Lemma 4.2, ˇ a` −i6=e a` −ifor at least one `, and so A(~ hL i;w)must be strictly less than 1.  We are, of course, primarily concerned with private monitoring under the distribution (Ωk,πk). In this situation, one must deal with the possibility that player j’s private signals may be inconsistent with player i’s observations. However, by choosing ksufficiently large, one can ensure that this possibility does not arise with large probability along the cycle ~ ωL i. The subsequent lemma implies that this possibility never arises with large probability. LEMMA 6. Assume the hypotheses of Lemma 5, and let ht ibe a private history for player i satisfying b w=σi(ht i). For all η > 0, there exist ξ > 0and k0(independent of ht i) such that, for all k >k0, if η < Prk(wt −i∈Wn−1 c\{ ¯ w1}|ht i)<1and Prk(wt −i/∈Wn−1 c|ht i)< ξ, then Prk(wt+L −i6=¯ w1|~ ωL i,ht i) Prk(wt+L −i=¯ w1|~ ωL i,ht i)<(1−ξ)Prk(wt −i6=¯ w1|ht i) Prk(wt −i=¯ w1|ht i), (2) where Prkdenotes probabilities calculated under πkand the assumption that all players follow the private profile, and ~ ωL iis the sequence identified in Lemma 5. PROOF. For clarity, we suppress the conditioning on ht i. Denote the event that players other than iobserve some sequence of private signals consistent with the cycle (¯ y1,..., ¯ ym)Nby ~ y−i, and the complementary event by ¬~ y−i. Then, Prk(wt+L −i6=¯ w1,~ ωL i) = Prk(wt+L −i6=¯ w1,~ ωL i,~ y−i) + Prk(wt+L −i6=¯ w1,~ ωL i,¬~ y−i) Theoretical Economics 1 (2006) Coordination failure in repeated games 333 and Prk(wt+L −i6=¯ w1,~ ωL i,~ y−i) ≤Prk(wt −i6=¯ w1,~ ωL i,~ y−i) =Prk(wt −i∈Wn−1 c\{ ¯ w1},~ ωL i,~ y−i) + Prk(wt −i/∈Wn−1 c\{ ¯ w1},~ ωL i,~ y−i), where the inequality arises because a player j6=imay be in a private state not in Wc. Now, Prk(wt −i∈Wn−1 c\{ ¯ w1},~ ωL i,~ y−i) =Prk(~ ωL i,~ y−i|wt −i∈Wn−1 c\{ ¯ w1})Prk(wt −i∈Wn−1 c\{ ¯ w1}) ≤Prk(~ ωL i,~ y−i|wt −i∈Wn−1 c\{ ¯ w1})Prk(wt −i6=¯ w1), and if Prk(wt −i/∈Wn−1 c\{ ¯ w1})< ξ (where ξis to be determined), Prk(wt −i/∈Wn−1 c\{ ¯ w1},~ ωL i,~ y−i) + Prk(wt+L −i6=¯ w1,~ ωL i,¬~ y−i) < ξ+Prk(wt+L −i6=¯ w1,~ ωL i,¬~ y−i) ≤ξ+Prk(~ ωL i,¬~ y−i) =ξ+Prk(¬~ y−i|~ ωL i)Prk(~ ωL i). Moreover, Prk(wt+L −i=¯ w1,~ ωL i)≥Prk(wt −i=¯ w1,~ ωL i,~ y−i) =Prk(~ ωL i,~ y−i|wt −i=¯ w1)Prk(wt −i=¯ w1). Defining xt(k)≡1 Prk(wt −i6=¯ w1)(ξ+Prk(¬~ y−i|~ ωL i)Prk(~ ωL i)), we have, Prk(wt+L −i6=¯ w1|~ ωL i) Prk(wt+L −i=¯ w1|~ ωL i) <Prk(~ ωL i,~ y−i|wt −i∈Wn−1 c\{ ¯ w1}) + xt(k) Prk(~ ωL i,~ y−i|wt −i=¯ w1)×Prk(wt −i6=¯ w1) Prk(wt −i=¯ w1) ≤maxw∈Wn−1 c\{ ¯ w1}Prk(~ ωL i,~ y−i|wt −i=w) + xt(k) Prk(~ ωL i,~ y−i|wt −i=¯ w1)×Prk(wt −i6=¯ w1) Prk(wt −i=¯ w1). (3) From Lemma 5, max w∈Wn−1 c\{ ¯ w1}A(~ ωL i;w) = max w∈Wn−1 c\{ ¯ w1}lim k→∞ Prk(~ ωL i,~ y−i|wt −i=w) Prk(~ ωL i,~ y−i|wt −i=¯ w1)<1, and so there is ξ0>0 sufficiently small so that (recall that the denominator has a strictly positive limit) max w∈Wn−1 c\{ ¯ w1}lim k→∞ Prk(~ ωL i,~ y−i|wt −i=w) + ξ0 Prk(~ ωL i,~ y−i|wt −i=¯ w1)<1−ξ0. 334 Mailath and Morris Theoretical Economics 1 (2006) The finiteness of the state space and the number of players allows us to interchange the max and lim operations. Consequently, there exists k00 such that for all k≥k00, maxw∈Wn−1 c\{ ¯ w1}Prk(~ ωL i,~ y−i|wt −i=w) + ξ0 Prk(~ ωL i,~ y−i|wt −i=¯ w1)<1−ξ0. (4) Since (Ω,πk)is strongly 1/k-close to (Y,ρ), limk→∞Prk(¬~ y−i|~ ωL i) = 0, and so there exists k000 such that Prk(¬~ y−i|~ ωL i)< ξ0η/2 for all k≥k000. Suppose ξ=ξ0η//2 and k0=max{k00,k000}. Since η < Prk(wt −i∈Wn−1 c\{ ¯ w1})≤Prk(wt −i6=¯ w1),xt(k)≤ξ0. Consequently (4), with (3), implies (2) (since ξ < ξ0).  Lemma 4 guarantees that one round of the cycle of signals always takes a state not in Wcinto Wc, ensuring that the probability on states in W\Wccan be controlled. LEMMA 7. Assume the hypotheses of Lemma 5, and let ht ibe a private history for player i satisfying b w=σi(ht i). Fix η > 0and let ξand k0be the constants identified in Lemma 6 . There exists T such that if t ≥T , then for all k >k0, Prk(wt+L −i/∈Wn−1 c|~ ωL i,ht i)< ξ. PROOF. Fix Tlarge enough, so that if ¯ w∈Wt(the set of states reachable in period t) for t≥T, then Wt⊂R(¯ w). Separation then implies Prk(wt+L −i/∈Wn−1 c,~ y−i) = 0, and so Prk(wt+L −i/∈Wn−1 c|~ ωL i) =Prk(wt+L −i/∈Wn−1 c,~ y−i|~ ωL i) + Prk(wt+L −i/∈Wn−1 c,¬~ y−i|~ ωL i) =Prk(wt+L −i/∈Wn−1 c,¬~ y−i|~ ωL i) ≤Prk(¬~ y−i|~ ωL i), which is less than ξfor k≥k0. We are now in a position to complete the proof. Suppose b ht iis a private history for player ithat leads to the private state b wwith t≥T, and let ηbe the constant required by Theorem 2. Since b wand ¯ ware both reachable in the same period, with positive probability player iobserves a private history b ht ithat leads to the private state b w. Moreover, at b ht ihis posterior belief that all the other players are in the private state ¯ w, Prk(wt −i=¯ w1|b ht i), is strictly positive for all k, though converging to 0 as k→∞(where Prkdenotes probabilities under πk). If Prk(wt −i6=¯ w1|b ht i)≤η, then Prk(wt −i=¯ w1| b ht i)>1−η, and since di(b w)6=di(¯ w),Theorem 2 yields the desired conclusion. Suppose then that Prk(wt −i6=¯ w1|b ht i)> η and k>k0, where k0is from Lemma 6. Lemmas 6and 7immediately imply that, as long as Prk(wt+κL −i6=¯ w1|ht i,(~ ωL i)κ)> η, after the first cycle, the odds ratio falls until eventually Prk(wt0 −i6=¯ w1|ht0 i)≤η, at which point we are in the first case (since b wcycles under ~ ωL i,i’s private state continually returns to b w).