Discussion Paper No.

597

BELIEFS IN REPEATED GAMESJohn H. Nachbar

September 2003

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

Beliefs in Repeated GamesJohn H. Nachbar∗
September 23, 2003

Abstract
Consider a two-player discounted inﬁnitely repeated game. A player’s belief
is a probability distribution over the opponent’s repeated game strategies. This
paper shows that, for a large class of repeated games, there are no beliefs thatsatisfy three conditions, learnability, consistency, and a diversity condition, CS.
This impossibility theorem generalizes results in Nachbar (1997).
Keywords: Bayesian learning, repeated games.

1

Introduction.

1.1

A statement of the result.

Consider an inﬁnitely repeated game with discounting and perfect monitoring basedon a ﬁnite stage game. For simplicity, I restrict attention to two-player games, but
the results extend to games with any ﬁnite number of players. A belief is a probability
distribution over the opponent’s repeated game strategies. This paper establishes
an impossibility theorem for beliefs.
By way of motivation and illustration, suppose that each player has only twostage game actions, H and T . Suppose further that each player is certain that the
opponent’s repeated game behavior strategy is i.i.d. – in each period, the opponent
plays H with some probability q, independent of history – but is uncertain as tothe value of q ∈ [0, 1]. Each player’s belief can then be represented as a probability
over [0, 1]. Suppose that each player’s belief has a continuous and strictly positive
density. In the special case in which each player’s belief is a Beta distribution, and∗Department of Economics, Box 1208; Washington University; One Brookings Drive; St. Louis,
MO 63130. Phone: (314) 935-5612; e-mail: nachbar@wueconc.wustl.edu. I wish to thank theInstitute for Social and Economic Research at Osaka University and the Center in Political Economy
at Washington University for their support. I wish to thank the editor and three anonymous referees
for their comments. And I would like to thank Larry Blume, Yaw Nyarko, Alvaro Sandroni, Rann
Smorodinsky, and Bill Zame for helpful conversations. Finally, and as will be obvious to readers
who know this literature, both this paper and its predecessor, Nachbar(1997), owe a great debt toKalai and Lehrer (1993).

players best respond, it is a folk theorem that, for any discount factor, this Bayesianmodel is equivalent to ﬁctitious play.1
In this model, player beliefs satisfy three conditions. The belief supports arelearnable, meaning that if player i’s opponent were to play an i.i.d. strategy then(one can show) player i’s one-period-ahead forecasts along the path of play would
become accurate asymptotically. Beliefs are weakly cautious because the support ofeach player’s belief over q is the entire interval [0, 1]; no i.i.d. strategy is excluded (asdeﬁned, weak caution actually requires less than this). And beliefs are symmetricin that they have the same supports, reﬂecting the symmetry of the strategy setsin this repeated game. Symmetry does not require that probabilities over q havethe same densities. For general deﬁnitions (not restricted to i.i.d. strategies) andadditional motivation, see Section 4.1 (learnability) and Section 4.3 (weak caution
and symmetry).
But player beliefs are not consistent. Consistency requires that each player havea best response in the support of his opponent’s belief; the formal deﬁnition is in
Section 4.2. It is not hard to see that, with any beliefs of the sort described, noi.i.d. strategy will be optimal, except in the trivial case that one of the stage gameactions is weakly dominant. Informally, each player is certain the other is playing
an i.i.d. strategy even though, if players optimize, neither player is. It is as thougheach player were certain that he were more sophisticated than his opponent.
The main result of this paper, Theorem 1, is that this generalized, Bayesianversion of ﬁctitious play exhibits a phenomenon that is common in repeated gamemodels: for a large class of repeated games, there are no beliefs that simultaneously
satisfy learnability, consistency, and CS, a diversity condition that is weaker thanweak caution and symmetry.
The proof of Theorem 1 rests on the following observation. For a large class of
repeated games, for any strategy σ1 that player 1 might play, there is a strategy σ2 ,an evil twin of σ1 , such that, were player 2 actually to play σ2 and were player 1’s oneperiod-ahead forecasts along the path of play to become accurate asymptotically,
then player 1 would eventually learn that continued play of σ1 was suboptimal.
Because a player can hold erroneous beliefs about his opponent’s behavior oﬀ thepath of play even if his forecasts along the path of play are accurate, the statementthat σ2 is σ1 ’s evil twin is strictly stronger than the statement that σ1 is not a best
response to σ2 .
It follows from the deﬁnitions that if player 1’s belief satisﬁes learnability and if
σ1 ’s evil twin is in the support of player 1’s belief then σ1 is not optimal. Say that
beliefs have the evil twin property if every strategy in the support of player 2’s belief
about player 1 has an evil twin in the support of player 1’s belief about player 2,
and vice versa. If learnability is satisﬁed and if the evil twin property holds thenconsistency fails. This observation, which is simply a marshalling of deﬁnitions, isrecorded in the paper as Theorem 2. The bulk of the proof of Theorem 1 is devoted
1

See the appendix to Chapter 2 in Fudenberg and Levine (1998) and also Lehrer (1996).

2

to showing that CS implies the evil twin property.
The above discussion glossed over an ambiguity in the deﬁnition of “support”
stemming from the fact that there are typically many equivalent ways to represent
the same belief. For example, in the two action case, the degenerate belief thatassigns probability one to the i.i.d. behavior strategy with q = 1/2 is outcome
equivalent to the belief that is uniform over pure strategies that specify actions as
a function of time but that are otherwise independent of history (for example, thestrategy “play H in period 1, T in period 2, etc.”). This paper ﬁnesses this ambiguity
by stating results in a form that is independent of the belief representation. A moreaccurate statement of Theorem 1 is, For a large class of repeated games, for any
beliefs, there are no strategy subsets that are simultaneously learnable, consistent,
and satisfy CS. Learnability of a given strategy subset holds for one belief if andonly if it holds for all outcome equivalent beliefs, and similarly for consistency. The
deﬁnition of CS does not depend on beliefs at all.
In the remainder of this introductory section, I discuss the application of Theorem 1 to models of out of equilibrium learning and I review some of the otherrelevant literature. Section 2 provides basic notation and deﬁnitions for repeatedgames. Section 3 deals with beliefs and learning. Section 4 provides formal deﬁnitions of learnability, consistency, and CS. Section 5 states and proves Theorem 1.
Section 6 contains some concluding remarks.

1.2

An application to learning in repeated games.

Suppose that two players are engaged in a repeated game, with neither player knowing the strategy of her opponent. One would like to argue that, via Bayesian updating of their beliefs, players learn to make increasingly accurate forecasts, andthat, as a result, play asymptotically resembles that of a Nash equilibrium of therepeated game. This is the class of learning models examined in Kalai and Lehrer(1993). A natural way to proceed in constructing such a model is to start by identifying strategy subsets, to be interpreted as the supports of player beliefs, with theproperty that there are, in fact, beliefs for which these sets are both learnable andconsistent. For such beliefs, consistency guarantees that an optimizing player mightplay a strategy in the support of his opponent’s belief, and, assuming such a strategy
is played, learnability then guarantees that each player will indeed learn to makeincreasingly accurate forecasts. Theorem 1 says that, for a large class of repeatedgames, any such strategy sets will violate CS. Put diﬀerently, Theorem 1 says that,given learnability, consistency requires that a certain kind of equilibrium assumption be built into the supports of player beliefs. Consistency doesn’t require thatthe supports exclude everything except i’s actual strategy, as in a Nash equilibrium.
But consistency goes a non-trivial distance in that direction.
To head oﬀ confusion, let me make two additional comments. First, there is awell developed literature that examines within equilibrium (rather than out of equilibrium) learning in repeated games with a type space structure. In particular, each3

player may privately learn his stage game payoﬀ function, drawn from a commonly
known distribution, before engaging in the repeated game. A strategy in the typespace game is a map from types to strategies in the repeated game. By “withinequilibrium,” I mean that players play a Nash equilibrium of the type space game.
The classic cite is Jordan (1991).
The assumption that players are in a Nash equilibrium means that, in eﬀect, eachplayer knows the other’s type space strategies. If one relaxes the Nash equilibrium
assumption, the analog of the results in this paper hold, now for type space strategies
rather than for strategies in the realized repeated game; see Nachbar (2001) and also
Section 4.1.
Second, there is a large literature in which players use prediction rules, which arefunctions from histories to one period ahead forecasts of the opponent’s action. A
prediction rule is formally equivalent to a behavior strategy, and so a model in which
players use prediction rules is formally equivalent to a Bayesian model in which eachplayer’s belief places probability 1 on a behavior strategy.2 There will, typically, bemany other, less trivial, belief representations generating the same prediction rule.
Theorem 1 states that, for a large class of repeated games, for any learning modelusing prediction rules, there is no equivalent Bayesian model in which the supportof player beliefs are learnable, consistent, and satisfy CS.3

1.3

Other relevant literature.

Theorem 1 generalizes the results of Nachbar (1997). Most notably, Nachbar (1997)
had left largely unresolved whether an impossibility result continues to hold if players
simultaneously (a) ε optimize rather than optimize and (b) randomize.4 If theanswer were “no” then the impossibility results in Nachbar (1997) could be avoided
by appealing to a form of bounded rationality. The present paper shows that theimpossibility results of Nachbar (1997) are robust in this respect. The present paper
also provides a reformulation that is, I think, much more transparent.
Propositions 4 and 5 of Nachbar (1997) are immediate corollaries of Theorem 1of this paper. The Theorem and Proposition 3 of Nachbar (1997) are corollaries as
well, with the minor qualiﬁcation that weak caution condition (1) is stronger thanits counterpart in Nachbar (1997). See also the discussion of neutrality in Remark 4
in Section 4.3 of this paper. Theorem 1 is also stronger than its analogs in Nachbar(1997) in that it uses a weaker deﬁnition of prediction, and in that it applies to a
2
In many such models, players maximize, or ε maximize, payoﬀs period-by-period. Myopic ε
optimization corresponds to δ = 0 uniform ε optimization in the present paper; see Section 3.3.
3
I have implicitly assumed that prediction rules are deterministic. There is also a literature (e.g.
Young (1993)) in which players use prediction rules that are probabilistic. Probabilistic prediction
rules are not equivalent to beliefs over strategies and hence the players using them are not Bayesianin the standard sense. Theorem 1 has no implications for such learning models.
4
Proposition 5 in Nachbar (1997) showed, using a computability argument, that the inconsistency
arises if the Σ̂i comprise the behavior strategies that can be implemented by Turing machines withaccess to randomization devices. Proposition 5 in Nachbar (1997) was restricted to δ close to zero.

4somewhat larger class of repeated games (condition MM in this paper is somewhat
weaker than its analog, assumption M, in Nachbar (1997)). The basic argument,
however, is essentially the same as in Nachbar (1997); in particular the proof of
Lemma 3 of this paper is a modiﬁcation of the proof of Proposition 1 in Nachbar(1997).
Both this paper and Nachbar (1997) are close relatives of Dawid (1985). Roughly
put, Dawid (1985) points out that if a Bayesian, looking at the data generated byan unknown stochastic process, thinks that the set of possible stochastic processes
satisﬁes a condition similar to weak caution then the Bayesian’s prediction rule,
which is itself a stochastic process, will be, loosely speaking, more complicated thanany of the processes that he thinks are possible. Both Nachbar (1997) and thepresent paper can be viewed as exploring the implications of this observation forgame theory.
Finally, as noted in Nachbar (1997), these impossibility results are reminiscentof diﬃculties that arise in static (rather than repeated) environments in which eachplayer chooses a decision procedure that takes his opponent’s decision procedure as
input. The classic cite is Binmore (1987). I refer the reader to Nachbar (1997) fora discussion.

2

Repeated Games.

As in Nachbar (1997), I focus on two-player inﬁnitely repeated games of perfectmonitoring. The analysis extends easily to games with more than two players, butadding additional players introduces the possibility that correlation may be built
into beliefs.

2.1

The stage game.

Let Ai denote the set of actions available to player i in the stage game. Let ai
denote an element of Ai . I assume that |Ai | < ∞, where |Ai | is the cardinality of
Ai . Let A = A1 × A2 . An element a = (a1 , a2 ) ∈ A is an action proﬁle.
Let ∆(Ai ) denote the set of probability mixtures over Ai . ∆(Ai ) can be identiﬁed
with the unit simplex in R|Ai | .
Each player has a stage game payoﬀ function, ui : A → R. I also let ui denote themixed extension of ui . Thus ui (α) = Eα ui (a), where Eα denotes expectation withrespect to the measure over A deﬁned by the mixed action proﬁle α ∈ ∆(A1 )×∆(A2 ).

2.2

Histories and paths of play.

An n period history, denoted h, is an element of An , the n-fold Cartesian productof A. Let h0 denote the null history, the history that obtains before play begins.
Let H denote the set of all ﬁnite histories, including h0 .

5A path of play, denoted z, is an inﬁnite history, an element of A∞ . Let Z = A∞
denote the set of paths of play. zn denotes the action proﬁle played at date nunder the path of play z. π(z, n) ∈ An denotes the projection of z onto its ﬁrst ncoordinates, giving the initial n period history determined by z.
Make Z measurable by giving it the σ-algebra generated by the cylinders C(h) ⊂Z, where C(h) is the set of paths of play with initial segment h. Let ∆(Z) denotethe set of probability measures over Z.

2.3

Behavior strategies and mixed strategies.

Players at date n + 1 know the realized n period history (perfect monitoring). I
adopt the convention that the term action refers to the stage game while the term
strategy refers to the repeated game. A behavior strategy for i is a function of theform
σi : H → ∆(Ai ).
Given a behavior strategy σi and a history h, the probability that player i chooses
action ai in the period following h is σi (h)(ai ). Let Σi denote the set of i’s behavior
strategies. Since H is countable, Σi can be identiﬁed with [R|Ai | ]∞ . Let Σ = Σ1 ×Σ2 .
I use si to denote a pure strategy, which is a behavior strategy that, for each h,assigns probability 1 to an element of Ai . Following history h, if the pure strategy
si assigns probability 1 to ai then I write si (h) = ai . Si ⊂ Σi denotes the set ofplayer i’s pure strategies.
Make Σi measurable by giving [R|Ai | ]∞ the product Borel σ algebra. Let ∆(Σi )denote the set of probability measures over Σi .

2.4

Induced measures over Z.

A behavior strategy proﬁle σ induces a probability measure µσ ∈ ∆(Z). Similarly, a
mixed strategy proﬁle β ∈ ∆(Σ1 )×∆(Σ2 ) induces a probability measure µβ ∈ ∆(Z),
and so on for combinations of mixed and behavior strategies.
Say that history h is reachable under the behavior strategy proﬁle σ iﬀ µσ (C(h)) >0. Say that history h is reachable under σ1 iﬀ there exists some pure strategy s2 forwhich µ(σ1 ,s2 ) (C(h)) > 0. Analogous deﬁnitions hold for mixed strategies.

2.5

Outcome equivalence.

Two behavior strategies σ1 and σ1∗ are outcome equivalent iﬀ for any behavior strategy σ2 ∈ Σ2 ,µ(σ1 ,σ2 ) = µ(σ1∗ ,σ2 ) .
One can verify that σi and σi∗ are outcome equivalent iﬀ µ(σ1 ,β2 ) = µ(σ1∗ ,β2 ) for any
β2 . The deﬁnition of outcome equivalence for mixed strategies is analogous.
6One can prove the following variant of Kuhn’s theorem, establishing outcome
equivalence between mixed and behavior strategies (in the standard version of
Kuhn’s Theorem, mixtures are over Si rather than Σi ).
Lemma 1 (Kuhn’s Theorem). For any mixed strategy βi there is a behavior
strategy σi such that βi is outcome equivalent to σi , and conversely.
If σi is outcome equivalent to the mixed strategy βi then say that σi is a reduced
form of βi .
Much of this paper implicitly assumes that players adopt behavior strategies
rather than mixed strategies. By Kuhn’s Theorem, this is largely a matter of interpretation. If one wants, for reasons of interpretation, to retain mixed strategies, one
way to do so is to introduce types. The results of this paper carry over into typespace models; see Section 1.2.

2.6

Repeated game payoﬀs.

Player i’s payoﬀ in the repeated game is the expectation of the discounted value ofthe payoﬀs he receives along the realized path of play. Formally, given a behavior
strategy proﬁle σ, the expected payoﬀ to player i is
Vi (σ) = Eµσ

∞




δ

n−1

ui (zn ) ,n=1

where δ ∈ [0, 1). One can analogously deﬁne Vi (β) and Vi (σ1 , β2 ).

2.7Continuation games.

An n period history h deﬁnes a continuation game, the repeated game starting inperiod n + 1. In the continuation game following h, a behavior strategy σi induces
a continuation behavior strategy σih deﬁned byσih (h ) = σi (h · h )for any history h , where h · h denotes the concatenation of h and h . Given a proﬁleσ = (σ1 , σ2 ), let σh = (σ1h , σ2h ).
The proﬁle σh induces the distribution µσh over the set of continuation paths,
which is simply Z. Given a history h and the proﬁle σ, the expected continuation
payoﬀ to player i is
Vi (σh ) = Eµσh

∞




δ

n−1

ui (zn ) .

n=1

Note that, in this deﬁnition, payoﬀs are discounted to the start of the period following h, rather than back to the ﬁrst period.
7

3

Beliefs, Optimization, and Learning.

3.1

Beliefs.

A belief about player i is a probability distribution over player i’s behavior strategies.
A belief about player i is thus formally equivalent to a mixed strategy for player
i. By Kuhn’s Theorem, for any belief βi there is a reduced form σiβ , not uniquelydeﬁned, that is outcome equivalent to βi , and conversely. It is often more convenient
to work with a reduced form σiβ than with βi .

3.2

Bayesian updating.

As the game proceeds, each player learns by Bayesian updating of her prior. Givena prior βi , any history h that is reachable under βi , and any reduced form σiβ , aβ.
reduced form of the posterior over continuation game strategies is simply σih

3.3

Optimization.

Given ε ≥ 0, σ1∗ is an ex ante ε best response to β2 (or σ1∗ is ex ante ε optimal) iﬀ
V1 (σ1∗ , β2 ) + ε ≥ max V1 (σ1 , β2 ).
σ1 ∈Σ1

Even if a behavior strategy is ex ante ε optimal, the induced continuation strategy
may be ε suboptimal in subgames that are far in the future or that the player views
as unlikely. Should such a subgame be reached, the player would, presumably,
deviate from her behavior strategy. The following stronger version of ε optimization
eliminates this problem for subgames that are reachable given the player’s belief(see also Lehrer and Sorin (1998)).
Deﬁnition 1. Given ε ≥ 0, σ1∗ is a uniform ε best response to β2 (or σ1∗ is uniformly
ε optimal) iﬀ, for any reduced form σ2β of β2 and any h that is reachable under(σ1∗ , σ2β ),ββ∗V1 (σ1h, σ2h) + ε ≥ max V1 (σ1 , σ2h).
σ1 ∈Σ1

If σ1∗ is a uniform ε best response to β2 , write σ1∗ ∈ BRε1 (β2 ). The deﬁnition forplayer 2 is analogous.
Note that if δ = 0 then uniform ε optimization corresponds to myopic (periodby-period) ε optimization.

3.4

Learning to predict the path of play.

Informally, player 1 learns to predict the path of play generated by σ2 (and player
1’s own strategy) if her one period ahead forecasts along the path of play eventually8become almost as accurate as if she knew σ2 . This is not the same thing as sayingthat player 1 learns σ2 . Player 1 could learn to predict the path of play generatedby σ2 and still hold erroneous beliefs about what player 2 would do oﬀ the path ofplay. Note also that if σi (h) = αi is not pure then accurate prediction means onlythat the player predicts approximately αi , not that she predicts the realized action.
Recall that π(z, n) is the history corresponding to the n period initial segmentof z and that C(h) is the cylinder of all paths of play with initial segment h.
Deﬁnition 2. Fix a belief β2 . Player 1 learns to predict the path of play generated
by the behavior strategy proﬁle σ = (σ1 , σ2 ) iﬀ the following conditions hold.
1. µσ (C(h)) > 0 implies µ(σ1 ,β2 ) (C(h)) > 0 for any ﬁnite history h.
2. For any real number η > 0 and µσ almost any path of play z, there is a periodn(η, z) such that, for any n > n(η, z) and any a2 ∈ A2 , letting h = π(z, n),|σ2 (h)(a2 ) − σ2β (h)(a2 )| < η.
A similar deﬁnition holds for player 2.
This deﬁnition is equivalent to the one given in Nachbar (1997). Prediction
corresponds to the more general concept of weak merging; see Kalai and Lehrer(1994).
As deﬁned, prediction requires accurate forecasts in every period following periodn(η, z). To be able to apply results from Lehrer and Smorodinsky (1996) (see also
Section 4.1), I consider a weaker form of prediction that requires forecasts to beaccurate only on a set of dates of density 1. Formally, let N be the set of natural
numbers (excluding zero) and consider a set N ⊂ N. Say that N has density 1 iﬀ|{1, 2, . . . , n} ∩ N |
= 1.
n→∞
n
Deﬁnition 3. Fix a belief β2 . Player 1 weakly learns to predict the path of play
generated by the behavior strategy proﬁle σ = (σ1 , σ2 ) iﬀ the following conditions
hold.
lim

1. µσ (C(h)) > 0 implies µ(σ1 ,β2 ) (C(h)) > 0, for any ﬁnite history h.
2. For any real number η > 0 and µσ almost any path of play z, there is a set
NP (η, z) ⊂ N of density 1 such that, for any n ∈ NP (η, z) and any a2 ∈ A2 ,letting h = π(z, n),|σ2 (h)(a2 ) − σ2β (h)(a2 )| < η.
A similar deﬁnition holds for player 2.
Weak prediction corresponds to the more general concept of almost weak merging
introduced in Lehrer and Smorodinsky (1996). Prediction implies weak prediction
but not conversely.
9

4Consistency, Learnability, and CS

4.1

Learnability.

Here and throughout, Σ̂i ⊂ Σi and Σ̂ = Σ̂1 × Σ̂2 .
Deﬁnition 4. Given Σ̂ ⊂ Σ and belief β2 , Σ̂2 is learnable iﬀ for any σ1 ∈ Σ̂1
and any σ2 ∈ Σ̂2 , player 1 weakly learns to predict the path of play. An analogous
deﬁnition holds for learnability of Σ̂1 . Σ̂ is learnable iﬀ Σ̂i is learnable for each i.
There are product sets that are not learnable for any beliefs. In particular, Theorem 1 implies that if either player has at least two actions in the stage game thenthere are no beliefs for which Σ, the full product set of behavior strategies, is learnable; this is a game theoretic version of an observation about stochastic processes
made in Dawid (1985). Thus, Σ̂ ⊂ Σ can be learnable only if it is suﬃciently small
in some sense.
A well known suﬃcient condition for player 1 to learn to predict the path of play
is for player 1’s belief to assign positive probability to player 2’s actual strategy.
Even if the probability assigned to player 2’s strategy is extremely low, a strong
form of prediction will be satisﬁed: player 1 learns to accurately forecast the entire
inﬁnite tail of the game, rather than merely the next period. Since every elementof a countable set can be given positive probability, it follows that if Σ̂ is countable
there are beliefs for which that set will be learnable.
Uncountable Σ̂ can also be learnable. Example 2 in Lehrer and Smorodinsky(1996) implies that if the Σ̂2 has a “nice” ﬁnite dimensional parameterization thenthere are beliefs for which Σ̂2 is learnable. By “nice,” I mean that if two parameters are close in the standard Euclidean topology then the associated strategies are
likewise close under a particular metric on Σ2 .5 The i.i.d. example of Section 1.1 isan example of a “nice” ﬁnite dimensional parameterization.6
Theorem 1 can be viewed as a purely positive statement: if the strategy sets
happen to be learnable then either consistency or CS must fail. But one can argue
that learnability should be “built in” by choosing belief representations in which, asin the i.i.d. example, beliefs are probabilities over learnable strategies. Such learnable representations are always possible: given any belief βi , take the alternative
5

Adapting the deﬁnition of neighborhood in Lehrer and Smorodinsky (1996) to the present
context (strategies in repeated games rather than stochastic processes), σ  is in the ε neighborhoodof σ iﬀ, for any history h that is reachable under σ2 and any a2 ∈ A2 for which σ(h)(a2 ) > 0,|σ2 (h)(a2 ) − σ2 (h)(a2 )| < εσ2 (h)(a2 ).
This deﬁnition of neighborhood is more restrictive than that implied by the sup norm. It is notknown whether the sup norm will suﬃce.
6
One can show that beliefs in the i.i.d. example allow prediction rather than merely weak prediction. A natural conjecture is that, more generally, beliefs allow prediction rather than merely
weak prediction if, as in the i.i.d. example, the parameter set is closed and the distribution overparameters admits a strictly positive density. But at this writing this conjecture has not been
established.

10

representation that places probability 1 on the reduced form σiβ . This representation is trivial, but non-trivial learnable representations are typically also available;see, in particular, the representation proposed by Jackson, Kalai, and Smorodinsky(1999).
An argument for adopting learnable representations is the following. Supposethat the beliefs used in Bayesian models are a construction by boundedly rational
players who consider the game, decide what strategies their opponents might play,and choose probability distributions over those strategies. If a player really thinksthat an opposing strategy σi is possible then his belief should give every neighborhood of σi positive probability. If one deﬁnes neighborhood with a suﬃciently
strong metric, a metric that takes into account behavior in the tails, then σi willbe learnable (exactly what metrics will serve remains an open question; see alsofootnote 5).
Adoption of a strong metric implies that players care about the tail of the game,
which conﬂicts with modeling them as discounting ε optimizers. One, informal,
justiﬁcation for nevertheless focusing on learnable representations mirrors the justiﬁcation oﬀered for uniform, as opposed to ex ante, ε optimization. Upon reaching
the subgame deﬁned by history h, a player wants to get a high average payoﬀ fromthat point forward. So his continuation strategy should be ε optimal with respect tohis posterior, and his posterior should itself be “good.” The player should not, onreaching h, want to violate Bayes’s rule by reconsidering the game and constructing
a new posterior to permit forecasting of strategies eﬀectively ruled out by his prior.
To avoid this kind of dynamic problem, the priors in a Bayesian model should bemodeled as if players cared about the tail of the game.7 Whether one can build acoherent model of belief construction along the lines sketched remains a topic for
future work.
Remark 1. Weak prediction is stronger than necessary for the main results of thispaper. As will be clear from the proofs, a weaker condition that will work just as
well is that, for any positive integer , with high probability, there is a period after
which the player’s forecast of his opponent’s play over the next  periods is highly
accurate. Even one such period will serve; the proof does not require that the setof such periods have density 1.
Also, for the sake of generality, the deﬁnition of learnability, like the deﬁnitionof conventional prediction in Nachbar (1997), requires prediction by player 1 only
if she herself plays a strategy in Σ̂1 . The suﬃcient conditions for prediction given
above do not, in fact, require that player 1’s strategy be restricted to Σ̂1 . The results
hold a fortiori if the deﬁnition of learnability is strengthened to require prediction
regardless of one’s own strategy. 
Remark 2. In type space models (see Section 1.2), the requirement that players
learn to predict the path of play generated by the opponent’s realized repeated7

For a model, necessarily non-Bayesian, in which players do jettison their Bayes’s rule posteriors,
see Foster and Young (2003).

11

game strategy can be too strong, and must be replaced by the appropriate analog,
namely that players learn to predict the path of play generated by the opponent’s
type space strategy (a map from types to repeated game strategies). See Nachbar(2001). Thus deﬁned, learnability is compatible with puriﬁcation in the spirit ofHarsanyi (1973), a phenomenon that has been emphasized in the context of typespace learning models by Jackson and Kalai (1997) (although, strictly speaking, thisis for recurring rather than repeated games), Jordan (1995), and Nyarko (1998). 

4.2

Consistency.

Deﬁnition 5. Given beliefs β1 and β2 , Σ̂ ⊂ Σ is ε consistent iﬀ for any ε > 0,
player 1 has a uniform ε best response in Σ̂1 and player 2 has a uniform ε best
response in Σ̂2 : BRε1 (β2 ) ∩ Σ̂1 = ∅ and BRε2 (β1 ) ∩ Σ̂2 = ∅. Σ̂ is consistent iﬀ Σ̂ is εconsistent for every ε > 0.
A trivial learnable and consistent strategy set is a Nash equilibrium strategy
proﬁle with associated beliefs (probability 1 on the opponent’s actual strategy). A
Nash equilibrium proﬁle, however, violates CS, deﬁned below.

4.3

CS, weak caution, and symmetry.

Deﬁnition 6. Σ̂ ⊂ Σ satisﬁes CS iﬀ the following conditions hold.
1. There is an ξ ∈ (0, 1) such that, for each i, the following is true. Consider
any σi ∈ Σ̂i . There is a pure strategy si ∈ Σ̂i such that, for any history h, if
si (h) = ai then σi (h)(ai ) > ξ.
2. Consider any pure strategy s1 ∈ S1 . For any function γ12 : A1 → A2 there isa pure strategy s2 ∈ Σ̂2 such that the following is true. Let z be the path ofplay generated by (s1 , s2 ). There is a set Nγ (z) ⊂ N of density 1 such that for
any n ∈ Nγ (z), letting h = π(z, n),s2 (h) = γ12 (s1 (h)).
And an analogous statement holds for s2 ∈ Σ̂2 and γ21 : A2 → A1 .
The motivation for condition (1) is that if a behavior strategy σ2 is in Σ̂2 (tobe thought of as the support of player 1’s belief) then a prudent player 1 should
think that at least one comparatively simple, nonrandomizing variation on σ2 iscontained in Σ̂2 as well. The leading candidate for a nonrandomizing variation ona behavior strategy σ2 is the pure strategy, call it s∗2 , that, for any history h, plays
the action to which σ2 assigns highest probability. s∗2 has the property that, for any
h, if s∗2 (h) = a2 thenσ2 (h)(a2 ) ≥
12

1
.
|A2 |

CS condition (1) is in the spirit of requiring that s∗2 be contained in Σ̂2 , but it is
weaker. CS condition (1) requires only that one such pure strategy be contained inΣ̂2 , not that every such pure strategy be contained in Σ̂2 .
CS condition (2) is implied by two stronger conditions, weak caution and symmetry (the name CS is derived from Caution and Symmetry) that are easier tomotivate.
Deﬁnition 7. Σ̂i ⊂ Σi is weakly cautious iﬀ the following is true.
1. CS Condition 1 holds.
2. Consider any strategy σi ∈ Σ̂i and any function g : Ai → Ai (not necessarily
1-1 or onto). There is a strategy σig ∈ Σ̂i such that, for any h and anya∗i ∈ g(Ai ),σig (h)(a∗i ) =σi (h)(ai ).

ai ∈g −1 (a∗i )Σ̂ is weakly cautious iﬀ Σ̂i is weakly cautious for each i.
The motivation for weak caution condition (2) is that if a strategy σ2 is in Σ̂2(still to be thought of as the support of player 1’s belief) then a prudent player
1 should include all computationally trivial variants of σ2 in Σ̂2 as well. Moreexplicitly, view a behavior strategy as a black box that takes histories as input andyields stage game actions as output. Condition (2) states that if σi is in Σ̂i then so
is any behavior strategy generated by using a function g to relabel outputs, leaving
the black box, which is where all of the strategic complexity resides, unchanged.
For any σi , the set of such computationally trivial variants is ﬁnite, since I haveassumed that the action set is ﬁnite.
Naively, one might demand, instead of weak caution, full caution: Σ̂i = Σi . But,
as noted in Section 4.1, if either player has at least two stage game actions then Σ̂ isnot learnable for any beliefs. Thus, to avoid triviality when dealing with learnable
sets, one must restrict attention to some weakened form of caution. The deﬁnitionoﬀered here is arguably too strong in that it is payoﬀ independent, but it is not clear
how much payoﬀ dependence would be incorporated into the support of a prudent
player’s belief. The payoﬀ independent formulation is, at a minimum, a natural anduseful benchmark.
Deﬁnition 8. Σ̂ ⊂ Σ is symmetric iﬀ the following holds. Consider any behavior
strategy σ1 ∈ Σ̂1 . Let A∗1 ⊂ A1 be the set of actions such that if a1 ∈ A∗1 then there
exists a history h for which σ1 (h)(a1 ) > 0. Let r = min{|A∗1 |, |A2 |}. Then there isa set A∗2 ⊂ A2 with |A∗2 | = r, an onto map γ : A∗1 → A∗2 , and a behavior strategy
σ2γ ∈ Σ̂2 such that, for any a∗2 ∈ A∗2 ,σ2γ (h)(a∗2 ) =

a1 ∈γ −1 (a∗2 )

13

σ1 (h)(a1 ).

And a similar condition holds for any behavior strategy σ2 ∈ Σ̂2 .
Symmetry is motivated by the idea that, aside from diﬀerences in the composition and cardinality of the stage game action sets, the mechanics of constructing
strategies are the same for the two players. More explicitly, as in the discussion of
weak caution condition (2), view a strategy as a black box that takes histories as
inputs and produces stage game actions as outputs. Then symmetry requires thatfor every σ1 ∈ Σ̂1 , Σ̂2 contains a strategy σ2γ constructed from σ1 by relabeling outputs (using the function γ) while leaving the black box unchanged. σ2γ is the sameas σ1 , except that whenever σ1 chooses, say, up, σ2 chooses, say, H. The deﬁnitionof symmetry is complicated by the desire to ensure that the relabeling function γ
is, loosely speaking, complexity preserving.
Lemma 2. If Σ̂ is weakly cautious and symmetric then Σ̂ satisﬁes CS.
Proof. CS condition (1) is immediate. For CS condition (2), it is easy to verify
that weak caution condition (2) and symmetry imply that, for any γ12 : A1 → A2
and any pure strategy s1 ∈ Σ̂1 , there is a pure strategy s2 ∈ Σ̂2 such that, for any
history h (not just histories along the path of play generated by (s1 , s2 )),s2 (h) = γ(s1 (h)).
That is, CS condition (2) holds for every z (not just z generated by (s1 , s2 )), andNγ (z) = N. 
Example 1. Consider any Σ̂ where, for each i, Σ̂i is deﬁned as the set of strategies
that satisfy some bound on strategic complexity. For example, Σ̂i might be the set ofstrategies that have one period memory, or k-period memory, or are implementableby automata or, or by Turing machines, possibly with access to randomization
devices. Any such set is weakly cautious and symmetric, and hence satisﬁes CS. 
Example 2. Suppose that Σ̂1 is the set of pure strategies for player 1 that are implementable by automata and Σ̂2 is the set of pure strategies for player 2 that are
implementable by Turing machines. Then Σ̂ violates CS and, in particular, violates
symmetry. It is not hard to see, however, that Σ̂ is nevertheless inconsistent for any
beliefs for which Σ̂ is learnable. 
Example 3. Each player’s action set in the stage game is Ai = {H, T }.
1. Suppose that Σ̂i consists of the two elements H and T , where H is the purestrategy “play H in every period” and T is the pure strategy “play T in every
period.” Then Σ̂ satisﬁes weak caution and symmetry and hence CS. This Σ̂iis sparse, which underscores the fact that weak caution is, as a characterizationof prudence, weak.

14

2. Suppose that, for each i, Σ̂i consists of the single element “randomize 50:50
in every period, regardless of history,” hereafter 50:50. This Σ̂ violates weak
caution and CS. In particular, it is not hard to see that CS requires here that
if 50:50 is in Σ̂i then so are H and T .
Remark 3. Trembles can be accommodated by the following slight weakening of
weak caution condition (1). Fix k ∈ (0, 1). There is a ξ > 0 such that, for any
σi ∈ Σ̂i , there is a behavior strategy σik ∈ Σ̂i such that, for any history h, there isan ai ∈ Ai for which
1. σik (h)(ai ) > 1 − k, and
2. σi (h)(ai ) > ξ.
One can verify that the main results continue to hold with this modiﬁcation, for any
k suﬃciently small. See also the discussion of trembling in Nachbar (1997). Remark 4. Symmetry and weak caution are, collectively, analogous to what Nachbar(1997) called neutrality. Symmetry and weak caution condition (2) are weaker thanthe ﬁrst four neutrality conditions in Nachbar (1997). Weak caution condition (1) isstronger than neutrality condition (5) in Nachbar (1997). Neutrality condition (5) inNachbar (1997) in eﬀect allowed the bound ξ to depend both on the history and on
the behavior strategy. Weak caution (1) requires ξ to be uniform across histories andbehavior strategies. Although, as a technical exercise, one can construct examples
in which neutrality condition (5) holds but weak caution condition (1) fails, I am
not aware of any interesting examples where this occurs. 

5Impossibility.

5.1

The main result and the evil twin property.

An action a∗1 ∈ A1 is weakly dominant iﬀ, for any a2 ∈ A2 ,u1 (a∗1 , a2 ) ≥ max u1 (a1 , a2 ).
a1 ∈A1This deﬁnition is somewhat weaker than the standard one in that I do not require
strict inequality for any a2 . The deﬁnition for player 2 is similar.
Deﬁnition 9. The stage game satisﬁes No Weak Dominance (NWD) iﬀ neither
player has a weakly dominant action.
Player 1’s minmax payoﬀ is given by
m1 =

min

max

α2 ∈∆(A2 ) α1 ∈∆(A1 )15

u1 (α1 , α2 ).

Player 1’s pure action maxmin payoﬀ is given by
M1 = max min u1 (a1 , a2 ).
a1 ∈A1 a2 ∈A2The deﬁnitions for player 2 are analogous.
Deﬁnition 10. The stage game satisﬁes MM iﬀ, for each player i, the pure action
maxmin payoﬀ is strictly less than the minmax payoﬀ,
Mi < mi .
Examples of stage games that satisfy MM are matching pennies, rock-scissorspaper, battle of the sexes, and many coordination games.
The main result of the paper is the following.
Theorem 1. Fix beliefs β1 and β2 . Consider any Σ̂ ⊂ Σ.
1. If NWD holds then there is a δ̄ ∈ (0, 1] such that, for any δ ∈ [0, δ̄), if Σ̂ islearnable and satisﬁes CS then Σ̂ is not consistent.
2. If MM holds then, for any δ ∈ [0, 1), if Σ̂ is learnable and satisﬁes CS andsymmetric then Σ̂ is not consistent.
The intended interpretation is that, for a large set of repeated games, if beliefs
have supports that are both learnable and suﬃciently diverse then the beliefs areinconsistent.
NWD cannot be relaxed. If δ is low and NWD fails then at least one of theplayers will be able to satisfy consistency because, no matter what his belief, it will
be a best response for him to play the constant strategy in which he repeatedly
plays his weakly dominant stage game action. The repeated prisoner’s dilemma, forexample, is not vulnerable to this form of inconsistency.
It is not clear whether MM is necessary, although it is used in an important way
in the proof of Theorem 3, which is the key technical result.
For more on the hypotheses in Theorem 1, see the discussion following Lemma 3
in Section 5.2.
The proof of Theorem 1 relies on the following concept.
Deﬁnition 11. Fix δ. A behavior strategy σ2 ∈ Σ2 is an ε evil twin of a behavior
strategy σ1 ∈ Σ1 iﬀ σ1 is not a uniform ε best response to any belief β2 for which
player 1 weakly learns to predict the path of play generated by (σ1 , σ2 ). A similardeﬁnition holds for player 2.
In the coordination game below, it is easy to show thatHT
H −1, −1
1, 1
T
1, 1
−1, −116

an ε evil twin of any pure strategy s1 , for any ε, is simply s1 itself, that is, thestrategy s2 deﬁned by, for any h,s2 (h) = s1 (h).
In this case, an evil twin is an identical twin. In repeated matching pennies, an εevil twin of any pure strategy s1 , for any ε, is any best response to s1 . I take up thegeneral construction of evil twins in Section 5.2.
Deﬁnition 12. Fix δ. Σ̂ ⊂ Σ has the evil twin property iﬀ there is an ε > 0 suchthat, for any σ1 ∈ Σ̂1 , there is a strategy σ2 ∈ Σ̂2 that is an ε evil twin of σ1 , andsimilarly for player 2.
Marshaling deﬁnitions yields the following observation.
Theorem 2. Fix δ and ﬁx beliefs β1 and β2 . If Σ̂ ⊂ Σ is learnable and has the evil
twin property then it is not consistent.
The key technical fact underlying Theorem 1 is that the evil twin property follows
from CS.
Theorem 3. Consider any Σ̂ ⊂ Σ.
1. If NWD holds then there is a δ̄ ∈ (0, 1] such that, for any δ ∈ [0, δ̄), if Σ̂satisﬁes CS then Σ̂ has the evil twin property.
2. If MM holds then, for any δ ∈ [0, δ̄), if Σ̂ satisﬁes CS then Σ̂ has the evil twin
property.
The proof of Theorem 1 follows immediately from Theorems 2 and 3. It remains
to prove Theorem 3.

5.2

The proof of Theorem 3.

The proof of Theorem 3 follows from a sequence of lemmas. I begin by showing how
to construct evil twins for pure strategies.
Deﬁne aM
2 : A1 → A2 by, for any pure action a1 ∈ A1 ,aM
2 (a1 ) = arg min u1 (a1 , a2 ).
a2 ∈A2

If the right-hand side is not single valued, arbitrarily pick one of the values to be
MaM
2 (a1 ). The function a1 is deﬁned similarly.
Recall that π(z, n) is the n period initial segment of the inﬁnite path of play z.
Given s1 , deﬁne S2M (s1 ) ⊂ S2 to be the set consisting of all s2 for which there exists
a set N ⊂ N of density 1 such that, for all n ∈ N , letting z denote the path of play
generated by (s1 , s2 ) and letting h = π(z, n),s2 (h) = aM
2 (s1 (h)).
17The deﬁnition of S1M (s2 ) is analogous.
Deﬁne the function ã2 : A1 → A2 by, for any pure action a1 ∈ A1 ,
ã2 (a1 ) = arg max

a2 ∈A2max u1 (a1 , a2 ) − u1 (a1 , a2 ) .

a1 ∈A1

If the right-hand side is not single valued, arbitrarily pick one of the values to beã2 (a1 ). The function ã1 is deﬁned similarly. Loosely, ã2 (a1 ) is the action that gives
player 1 maximal one-period incentive not to play a1 . ã2 (a1 ) does not necessarily
minimize player 1’s payoﬀ from a1 . That is, it is not necessarily true that ã2 (a1 ) =aM
2 (a1 ).
Given s1 , deﬁne S̃2 (s1 ) ⊂ S2 to be the set consisting of all s2 for which there
exists a set N ⊂ N of density 1 such that, for all n ∈ N , letting z denote the pathof play generated by (s1 , s2 ) and letting h = π(z, n),s2 (h) = ã2 (s1 (h))
The deﬁnition of S̃1 (s2 ) is analogous.
Lemma 3 conﬁrms that, for a large set of games, elements of either S̃1 (s2 ) or
S1M (s2 ) are indeed evil twins of s1 . The proof is in the appendix.
Lemma 3.
1. Suppose that NWD holds. Then there is a δ̄ ∈ (0, 1) and an ε > 0 such that,for any δ ∈ [0, δ̄), any ε ∈ [0, ε ), and any pure strategy s1 ∈ S1 , if s2 ∈ S̃2 (s1 )then s2 is an ε evil twin of s1 . And an analogous statement holds for any
s2 ∈ S2 .
2. Suppose that MM holds. Then there is an ε > 0 such that, for any δ ∈ [0, 1),any ε ∈ [0, ε ), and any pure strategy s1 ∈ S1 , if s2 ∈ S2M (s1 ) then s2 is an εevil twin of s1 . And an analogous statement holds for any s2 ∈ S2 .
Informally, the logic of the argument is as follows. If NWD holds, then s1 (h) is
not a stage game ε best response to ã2 (s1 (h)) for any h, for ε suﬃciently small. If
δ is close to zero, therefore, and if player 1 learns to predict the path of play, thenplayer 1 will learn to predict that the continuation strategy induced by s1 is not
ε optimal on a set of periods of density 1, which means that s1 is not uniformly ε
optimal.
On the other hand, for any δ, if MM holds, then player 1 will learn to predictthat his payoﬀ average is at most M1 , which, by assumption, is strictly less thanthe minmax payoﬀ m1 . But a uniform ε optimizing player always expects to earn
at least m1 − ε, on average, in any continuation game he thinks is reachable.
If MM fails then it is possible that player 1 never learns to expect to receive lessthan m1 , on average. Although meager, a payoﬀ average of m1 can be consistent
with ε optimization, depending on what player 1 expects to happen should she
18

deviate. In this regard, recall that the Folk Theorem states that player 1 can receive
a payoﬀ average arbitrarily close to m1 in equilibrium (indeed, in subgame perfectequilibrium). This said, I do not know of any examples in which (a) MM is violated
but NWD is satisﬁed, and (b) learnability, consistency, and CS are all satisﬁed.
The next lemma records that evil twins of the sort just constructed will be
included in any Σ̂ that satisﬁes CS.
Lemma 4. Suppose that Σ̂ satisﬁes CS. Consider any s1 ∈ Σ̂1 .
1. There is an s2 ∈ Σ̂2 ∩ S̃2 (s1 ).
2. There is an s2 ∈ Σ̂2 ∩ S2M (s1 ).
And analogous statements hold with the roles of the players reversed.
Proof. Given s1 as in the statement of the lemma, deﬁne γ12 : A1 → A2 by
γ12 (a1 ) = ã2 (a1 ). In view of the deﬁnition of S̃2 (s1 ), the conclusion then follows
from CS condition (2), with N = Nγ (z). The proof for S2M (s1 ) is similar, as is theproof for the analogous claims with the roles of the players reversed. 
These lemmas establish Theorem 3, and hence Theorem 1, for the special casein which Σ̂ is pure. It remains to extend the argument to Σ̂ that include randomizing behavior strategies. I do so by means of the following fact about uniform εoptimization. The proof is in the appendix.
Lemma 5. Consider any belief β2 , any ε ≥ 0, any behavior strategy σ1 that is a
uniform ε best response to β2 , and any ξ > 0. Consider any pure strategy s1 suchthat, for any history h, if s1 (h) = a1 ∈ A1 thenσ1 (h)(a1 ) > ξ.
Then s1 is uniformlyε(1 − δ)ξ
optimal. A similar statement holds for player 2.
Proof of Theorem 3. Consider any belief β2 and any behavior strategy σ1 ∈ Σ̂1 .
By CS condition (1), there is a pure strategy s1 ∈ Σ̂1 and a ξ > 0 such that, for any
history h, if s1 (h) = a1 ∈ A1 , thenσ1 (h)(a1 ) > ξ.
By Lemma 5, if σ1 is a uniform ε best response to player 1’s belief then s1 is a
uniform ε/[(1 − δ)ξ] best response. By Lemma 3 and Lemma 4, it follows by contraposition that s1 cannot be a uniform ε/[(1 − δ)ξ] best response for ε/[(1 − δ)ξ] lessthan ε , where ε is as in the statement of Lemma 3, hence σ1 cannot be a uniform
ε best response for ε less than ε (1 − δ)ξ. The proof follows. 

19

6

Conclusion

The paper’s main result, Theorem 1, states that, for a large class of repeated games,
if beliefs have supports that are learnable and suﬃciently diverse, in the sense ofsatisfying CS, then the supports are inconsistent.
Although one can work with an inconsistent model, like Bayesian ﬁctitious play,consistency seems to me to be so attractive property that I would prefer to retain it,
if possible. And, for reasons discussed in Section 4.1, I would also like to represent
beliefs as probabilities over learnable strategies, in which case learnability is built
in. This leaves CS.
I have chosen deﬁnitions of CS, and of weak caution and symmetry, that are
based exclusively on complexity considerations, independent of payoﬀs. This formulation is, I think, a natural benchmark, but a compelling theory of belief formation
would also take account of payoﬀs. It is possible that, because of this, a prudent
player, according to some more fundamental deﬁnition of prudence, would nevertheless have beliefs that violate CS. But developing such a theory remains a topic
for future work.

20

Appendix
Proof of Lemma 3. The proof is a modiﬁcation of the proof of Proposition 1 in
Nachbar (1997).
Let

w1 = mina1 ∈A1

max u1 (a1 , ã2 (a1 )) − u1 (a1 , ã2 (a1 ))a1 ∈A1.

By NWD, w1 > 0. Letū1 = max u1 (a),a∈Au1 = min u1 (a),a∈A

By NWD, ū1 > u1 .
To prove the ﬁrst part of the lemma, choose δ̄ suﬃciently small that, underuniform ε optimization, player 1 acts to maximize his current period payoﬀ (i.e. heis eﬀectively myopic). In particular, it will turn out that the argument below goes
through for ε > 0 and δ̄ ∈ (0, 1] such that, for any ε ∈ [0, ε ) and any δ ∈ [0, δ̄),ε < w1 −δ[u1 − u1 ] .
1−δNote that such ε and δ̄ do exist.
Consider any pure strategy s1 ∈ S1 and any s2 ∈ S̃2 (s1 ). Temporarily ﬁxη ∈ (0, 1). Let z be the path of play generated by (s1 , s2 ) and suppose that player
1 weakly learns to predict the path of play. Then there is a set NP (η, z) ⊂ N of
density 1 such that, for any n ∈ NP (η, z), in the continuation game beginning inperiod n + 1, player 1 assigns some probability greater than 1 − η to the actual
action chosen by player 2 in period n + 1. Let N◦ (η, z) = NP (η, z) ∩ N , where N
is from the deﬁnition of S̃2 (s1 ). Note that N◦ (η, z), as the intersection of two setsof density 1, has density 1.
Choose any n ∈ N◦ (η, z). Recalling that π(z, n) is the history corresponding
to the n period initial segment of z, let s1 (π(z, n)) = a∗1 be the action chosen by
player 1 in period n + 1. Then player 2 chooses action ã2 (a∗1 ). Discounting payoﬀs
to period n + 1, player 1’s expected payoﬀ in the continuation game is at most
(1 − η)u1 (a∗1 , ã2 (a∗1 )) + ηu1 +

δ
u1 .
1−δ

If player 1 were instead to choose an action a1 in period n+1 to maximize u1 (a1 , ã2 (a∗1 )),his expected payoﬀ in the continuation game would be at least(1 − η) max u1 (a1 , ã2 (a∗1 )) + ηu1 +a1 ∈A1

21

δ
u .
1−δ 1

Thus, uniform ε optimization requires
ε + (1 − η)u1 (a∗1 , ã2 (a∗1 )) + ηu1 +

δ
u1
1−δ
≥ (1 − η) max u1 (a1 , ã2 (a∗1 )) + ηu1 +a1 ∈A1

δ
u
1−δ 1

or
ε + η(u1 − u1 ) ≥ w1 −

δ
[u1 − u1 ].
1−δBy the construction of ε and δ̄, there is an η suﬃciently small such that this inequality cannot hold for any ε ∈ [0, ε ) and δ ∈ [0, δ̄). This establishes the ﬁrst partof the lemma.
As for the second part of the lemma, suppose that Assumption MM holds. Fix
any δ ∈ [0, 1) and choose ε > 0 such that, for any ε ∈ [0, ε ),ε<1[m1 − M1 ] .
1−δBy Assumption MM, m1 > M1 , hence such ε exist.
Once again, consider any pure strategy s1 ∈ S1 and any s2 ∈ S2M (s1 ). Let z be
the path of play generated by (s1 , s2 ). Temporarily ﬁx η > 0 and an integer  > 0.
Again, suppose that player 1 weakly learns to predict the continuation path of play.
Then there is a set NP (η, z) ⊂ N of density 1 such that in the continuation game
beginning in period n + 1, player 1 assigns a probability greater than 1 − η to theactual action chosen by player 2 in period n + 1. Let N◦ (η, z) = NP (η, z) ∩ N , whereN  is from the deﬁnition of S2M (s1 ). Note that N◦ (η, z), as the intersection of two
sets of density 1, has density 1.
Let N (η, z) ⊂ N◦ (η, z) be such that for any n ∈ N (η, z) and any k ∈ {1, . . . , },player 1 assigns probability greater than 1 − η to the actual action chosen by player
2 in period n + k. Because N◦ (η, z) has density 1, N (η, z) has density 1 (and, inparticular, is not empty). Thus, for any n ∈ N (η, z), player 1 assigns a probability
greater than (1 − η) to the actual -period continuation history, beginning in periodn + 1. For ease of notation, deﬁne λ ∈ (0, 1) by
1 − λ = (1 − η) .
Note that λ decreases as either η decreases or  increases.
Consider any n ∈ N (η, z). In the -period continuation history beginning inperiod n + 1, player 1 receives at most M1 per period. On the other hand, player 1
believes that there is a probability of at most λ that the continuation history might
be something else. In an alternate -period continuation history, player 1 receives
at most u1 per period. Finally, from period n +  + 1 onwards, player 1 receives at22most u1 per period. Thus, beginning in period n + 1, player 1 expects to earn at
most
1 − δδu1 .
[(1 − λ)M1 + λu1 ] +1−δ
1−δIn contrast, any best response must expect to earn at least m1 , on average, following
any history given positive probability by µ(s1 ,σβ ) . (And, by the assumption that2
player 1 learns to predict the path of play, any history along z is given positive
probability.) Thus, under a true best response, player 1 expects to earn at leastm1.
1−δThus ε optimization requires
ε+

δ
m1
1 − δ
u1 ≥[(1 − λ)M1 + λu1 ] +
1−δ
1−δ
1−δ

or
ε ≥ (1 − λ)

δ  + λ(1 − δ  )1 − δ
[m1 − M1 ] −[u1 − m1 ].
1−δ
1−δ

By the construction of ε , one can ﬁnd η suﬃciently small and  suﬃciently largethat this inequality cannot hold for any ε ∈ [0, ε ). This establishes the second partof the lemma. 
Proof of Lemma 5. Fix any history h that is reachable under (σ1 , σ2β ). For
1
concreteness, let the length of h be n. I must show that s1h is (1−δ)ξ
ε optimal.
Following any history h, let J(a1 ) denote the expected discounted payoﬀ toplayer 1 from playing action a1 in the next period and thereafter playing accordingto σ1 . Let s1 (h) = a∗1 . Then, by the construction of s1 , for any h,βV1 (σ1h , σ2h) ≤ ξJ(a∗1 ) + (1 − ξ) max J(a1 ).
a1 ∈A1On the other hand, since σ1 is uniformly ε optimal, for any h that is reachable under(σ1 , σ2β ),β
β) + ε ≥ max
V1 (σ1 , σ2h).
V1 (σ1h , σ2h
σ1 ∈Σ1

Combining these inequalities with the fact thatβmax V1 (σ1 , σ2h) ≥ max J(a1 ),σ1 ∈Σ1

a1 ∈A123

one concludes that playing a∗1 next period and thereafter playing according to σ1
loses, relative to the optimal continuation strategy, at most ε/ξ:εβ
) − J(a∗1 ) ≤ .
max V1 (σ1 , σ2hξ

σ1 ∈Σ1

Fix any integer N > 0. Let sN
1 denote the pure strategy that is identical to s1
on every history of length n + N − 1 or less, and thereafter is identical to σ1 .
Consider any continuation history h of length N − 1 that is reachable underβ(σ1h , σ2h). From the argument above, the continuation payoﬀ from playing sN
1 ,starting at history h · h , is within ε/ξ of the maximum continuation payoﬀ.
Similarly, for any continuation history h of length N − 2 that is reachable underβ−1(σ1h , σ2h), the continuation payoﬀ from playing sN, starting at history h · h , is1−1within ε/ξ of the maximum continuation payoﬀ. If, instead of playing sN
, one
1
N
plays s1 , as in the previous paragraph, then one loses, at most, an additional δε/ξ,discounted back to date n + N − 1. Therefore, for any continuation history h ofβlength N − 2 that is reachable under (σ1h , σ2h), the continuation payoﬀ from playing
 , is withinsN,startingathistory
h
·
h
1
ε
ε
+δ
ξ
ξ
of the maximum continuation payoﬀ.
Continuing in this way, it follows that the continuation payoﬀ from playing sN
1 ,starting at history h, is withinεε+ · · · + δ N −1 =ξξ



1 − δN1−δεξ

of the maximum continuation payoﬀ. This holds for any integer N > 1. Therefore,taking the limit as N → ∞ (and noting that sN
1 converges to s1 in the producttopology, and that V1 is continuous in the product topology), the continuation payoﬀ
from playing s1 , starting at history h, is withinε(1 − δ)ξ
of the maximum continuation payoﬀ, as was to be shown. 

References
Binmore, K. G. (1987): “Modeling Rational Players, Part I,” Economics andPhilosophy, 3, 179–214.

24

Dawid, A. P. (1985): “The Impossibility of Inductive Inference,” Journal of theAmerican Statistical Association, 80(390), 340–341.
Foster, D., and P. Young (2003): “Learning, Hypothesis Testing, and Nash
Equilibrium,” Games and Economic Behavior, 45, 73–96.
Fudenberg, D., and D. Levine (1998): Theory of Learning in Games. MIT Press,
Cambridge, MA.
Harsanyi, J. (1973): “Games with Randomly Disturbed Payoﬀs: A New Rationale
for Mixed-Strategy Eequilibrium Points,” International Journal of Game Theory,2, 1–23.
Jackson, M., and E. Kalai (1997): “Social Learning in Recurring Games,”
Games and Economic Behavior, 21, 102–134.
Jackson, M., E. Kalai, and R. Smorodinsky (1999): “Bayesian Representationof Stochastic Processes under Learning: de Finetti Revisited,” Econometrica,
67(4), 875–893.
Jordan, J. S. (1991): “Bayesian Learning in Normal Form Games,” Games andEconomic Behavior, 3, 60–81.
(1995): “Bayesian Learning in Repeated Games,” Games and Economic
Behavior, 9, 8–20.
Kalai, E., and E. Lehrer (1993): “Subjective Equilibrium in Repeated Games,”
Econometrica, 61(5), 1231–1240.
(1994): “Weak and Strong Merging of Opinions,” Journal of Mathematical
Economics, 23, 73–86.
Lehrer, E. (1996): “Fictitious Play Fits the Subjective Learning Approach,” Tel
Aviv.
Lehrer, E., and R. Smorodinsky (1996): “Compatible Measures and Merging,”
Mathematics of Operations Research, 21(3), 697–706.
Lehrer, E., and S. Sorin (1998): “ε-Consistent Equilibrium In Repeated Games,”
International Journal of Game Theory, 27, 231–244.
Nachbar, J. H. (1997): “Prediction, Optimization, and Learning in RepeatedGames,” Econometrica, 65, 275–309.
(2001): “Bayesian Learning in Repeated Games of Incomplete Information,” Social Choice and Welfare, 18(2), 303–326.

25

Nyarko, Y. (1998): “Bayesian Learning and Convergence to Nash Equilibria Without Common Priors,” Economic Theory, 11(3), 643–655.
Young, H. P. (1993): “The Evolution of Conventions,” Econometrica, 61(1), 57–
84.

26