# Common Identification and Common Learning

Martin W. Cripps

(Date: June, 2024)

###### Abstract.

Cripps, Ely, Mailath, and Samuelson (2008) showed that if there are finitely
many states, and the signals are i.i.d and finite, then individual learning is
sufficient for common learning. In this note we describe what is commonly
learned when this sufficient condition does not hold.

Department of Economics, University College London<EMAIL_ADDRESS>My
thanks are due to Johannes Hörner who posed this question and to Duarte
Goncalves for his comments and advice.

##  1\. Introduction

Cripps, Ely, Mailath, and Samuelson (2008) (henceforth CEMS) showed that if
agents observe sequences of iid private signals that ensure they learn an
underlying state, then the state will also become approximate common
knowledge. Thus, individual learning is a sufficient condition for common
learning. Here we provide a characterization of what is commonly learned in
settings where individual learning does not occur. That is, we consider
settings where the agents’ private signals are not rich enough to ensure that
all states are learned. As each agent accumulates signals they are only able
to learn a partition of the state space: their “identification partition”.
Proposition 1 shows that the join of the agents’ identification partitions
determines what is commonly learned.

A motivation for studying common learning is to understand agents’ ability to
coordinate when they privately learn about the appropriate action. For
example, Frick, Iijima, and Ishii (2023) study how rates of common learning
affect equilibrium outcomes and welfare in coordination games. However, a
maintained assumption in the literature on common learning is that it is
_possible_ for all agents to learn all of the states. This seems unlikely to
be true in many important macro-based coordination games. It would, therefore,
be useful to have a result that details what is commonly learned when not all
agents can learn all states. This is the purpose of this note.

In Section 2 we describe the information structures we study and what
restrictions we place on them. We also define the notion of common
identification and give an illustrative example. The section ends with a
restatement of the definition of common learning for these more general
information structures. Section 3 contains the result characterising what is
commonly learned. The section begins with a description of the events that
will be used to establish common learning. Then some well-known results on
individual learning are given in Lemma 1. After this, the example is revisited
to explain our result on common learning and finally the result is proven.

##  2\. The Model and Definitions

There are $L$ agents named $\ell\in\\{1,2,\dots,L\\}:=[L]$ who each privately
observe a sequence of state-dependent signals. Time is discrete and the time
periods are denoted $t=0,1,2,\dots$ . Before period $t=0$, nature selects a
state $\theta$ from a finite set $\Theta$ according to a full-support common
prior $p\in\Delta(\Theta)$. Then, in the periods $t=0,1,2,\dots$, each agent
privately observes a signal. Agent $\ell$ has a finite set of signals
$x_{\ell}\in X_{\ell}$ and a signal profile is denoted
$x=(x_{1},\dots,x_{L})\in X:=X_{1}\times\dots\times X_{L}$. Conditional on
$\theta$, the signals are generated by independent sampling from the joint
distribution $\pi^{\theta}\equiv(\pi^{\theta}(x))_{x\in X}\in\Delta(X)$. We
will denote the marginal over agent $\ell$’s signals in state $\theta$ as
$\phi^{\theta}_{\ell}\equiv(\phi^{\theta}_{\ell}(x_{\ell}))_{x_{\ell}\in
X_{\ell}}$, that is,

$\phi_{\ell}^{\theta}(x_{\ell}):=\sum_{x_{-\ell}\in
X_{-\ell}}\pi^{\theta}(x_{\ell},x_{-\ell}),\qquad\phi_{\ell}^{\theta}\in\Delta(X_{\ell}).$

It may not be possible for agent $\ell$ to learn a particular state from
repeated observation of their signals. We do not assume that the states
generate marginal distributions $\\{\phi_{\ell}^{\theta}:\theta\in\Theta\\}$
for agent $\ell$ that are distinct. To describe what the agents are able to
learn, we partition $\Theta$ into the sets of states that agent $\ell$ can
identify.

######  Definition 1.

For each agent $\ell\in[L]$, their _identification partition_ ,
$\mathcal{Q}_{\ell}=(Q_{\ell}^{1},\dots,Q_{\ell}^{n_{\ell}})$, is a partition
of $\Theta$, such that $\theta,\theta^{\prime}\in
Q_{\ell}\in\mathcal{Q}_{\ell}$ if and only if
$\phi_{\ell}^{\theta}=\phi_{\ell}^{\theta^{\prime}}$.

######  Example 1 (An Information Structure with Unidentified States).

Consider the following information structure with two agents
$\ell\in\\{1,2\\}$. There are four states
$\Theta=\\{\theta_{1},\theta_{2},\theta_{3},\theta_{4}\\}$ and in these states
each agent repeatedly observes one of two signals $x_{1},x_{2}\in\\{0,1\\}$.
The joint distributions of the signals in these four states,
$(\pi^{\theta_{k}})_{k=1}^{4}$, are given in the tables below.

22 $\theta_{1}$& $x_{2}=0$ $x_{2}=1$

$x_{1}=0$ $\frac{3}{8}$ $\frac{1}{8}$

$x_{1}=1$ $\frac{1}{8}$ $\frac{3}{8}$ 22 $\theta_{2}$& $x_{2}=0$ $x_{2}=1$

$x_{1}=0$ $\frac{5}{12}$ $\frac{1}{12}$

$x_{1}=1$ $\frac{1}{4}$ $\frac{1}{4}$

22 $\theta_{3}$& $x_{2}=0$ $x_{2}=1$

$x_{1}=0$ $\frac{5}{12}$ $\frac{1}{4}$

$x_{1}=1$ $\frac{1}{12}$ $\frac{1}{4}$ 22 $\theta_{4}$& $x_{2}=0$ $x_{2}=1$

$x_{1}=0$ $\frac{2}{5}$ $\frac{1}{5}$

$x_{1}=1$ $\frac{1}{5}$ $\frac{1}{5}$

Figure 1. Four Signal Distributions

In these four distributions the marginal over agent 1’s signals, $x_{1}$, in
the states $\theta_{1}$ and $\theta_{2}$ is $(\frac{1}{2},\frac{1}{2})$, but
in all other states agent 1’s marginals are distinct. By observing enough of
her signals, agent 1 can learn the partition
$\mathcal{Q}_{1}=\\{\\{\theta_{1},\theta_{2}\\},\\{\theta_{3}\\},\\{\theta_{4}\\}\\}$.
This is agent 1’s identification partition in this information structure. Her
(conditional) posterior over the set $\\{\theta_{1},\theta_{2}\\}$ will never
vary from her prior. For agent 2 the signal distributions in the states
$\theta_{1}$ and $\theta_{3}$ have the marginal $(\frac{1}{2},\frac{1}{2})$,
while all other states have distinct marginals. Thus agent 2 has the
identification partition
$\mathcal{Q}_{2}=\\{\\{\theta_{1},\theta_{3}\\},\\{\theta_{2}\\},\\{\theta_{4}\\}\\}$.

We will assume (Assumption 1) that for every $\theta$ the marginal
distribution of any pair of agents’ signals has full support. This assumption
is not made in CEMS. Its purpose here is make the proof of common learning
robust to uncertainty in the state that agents cannot detect. Here agents will
not know the state but only a subset of states. Thus their inferences about
other agents’ signals need to be robust to this lack of certainty about the
state. This full-support assumption is a simple way to ensure that this lack
of certainty does not prevent common learning of a coarser class of events.
(We will use $x_{-\ell\ell^{\prime}}$ to denote the signal profile $x$ with
the $\ell^{\rm th}$ and $\ell^{\prime\rm th}$ entry deleted.)

######  Assumption 1.

For all $\theta\in\Theta$, all $\ell,\ell^{\prime}\in[L]$ and all
$(x_{\ell},x_{\ell^{\prime}})\in X_{\ell}\times X_{\ell^{\prime}}$,

$\sum_{x_{-\ell\ell^{\prime}}\in
X_{-\ell\ell^{\prime}}}\pi^{\theta}(x_{\ell},x_{\ell^{\prime}},x_{-\ell\ell^{\prime}})>0.$

This assumption excludes the possibility that agents’ signals are perfectly
correlated. It is slightly more general than the “fully private” case by
Frick, Iijima, and Ishii (2023) which requires $\pi^{\theta}$ to have a full
support.

The model of states and signal sequences above defines a probability space on
the set of states of the world $\Omega:=\Theta\times X^{\infty}$. The prior
$p$, the signal distributions $(\pi^{\theta})_{\theta\in\Theta}$ and the
i.i.d. assumption determine a probability measure $\mathbbm{P}$ on $\Omega$.
Associated with $\mathbbm{P}$ is an expectation operator $E(.)$. We also use
$\mathbbm{P}^{\theta}$ and $E^{\theta}(.)$ to denote their
$\theta$-conditional versions. It will often be convenient to abbreviate the
event $\\{\theta\\}\times X^{\infty}\subset\Omega$ to $\\{\theta\\}$ or just
$\theta$.

###  2.1. Common Identification and Common Learning

This section provides definitions of common learning and common
identification. We begin by defining common identification and then explain
how it works in the above example. Then some additional notation is defined
and the section ends with an extension of CEMS’s definition of common learning
to sets of states.

######  Definition 2 (Common Identification).

The sets of states that are _commonly identified_ are given by the partition
$\mathcal{QI}:=\bigvee_{\ell\in L}\mathcal{Q}_{\ell}$, where
$\mathcal{Q}_{\ell}$, $\ell\in[L]$, are the agents’ identification
partitions.111The join of two partitions $A\vee B$ is the finest partition
that has components that are unions of elements of $A$ and of $B$.

######  Example 1 (Continued).

In the information structure of Figure 1, agent 1 can identify the partition
$\mathcal{Q}_{1}=\\{\\{\theta_{1},\theta_{2}\\},\\{\theta_{3}\\},\\{\theta_{4}\\}\\}$
and agent 2 can identify the partition
$\mathcal{Q}_{2}=\\{\\{\theta_{1},\theta_{3}\\},\\{\theta_{2}\\},\\{\theta_{4}\\}\\}$.
The join of the two partitions is
$\mathcal{QI}:=\mathcal{Q}_{1}\vee\mathcal{Q}_{2}=\\{\\{\theta_{1},\theta_{2},\theta_{3}\\},\\{\theta_{4}\\}\\}$.
The partition $\mathcal{QI}$ contains the events that the agents can _commonly
identify_ in this setting. In Proposition 1 we show that the events in
$\mathcal{QI}$ are commonly learned.

It is now necessary to provide the notation to describe the agents’ learning.
At the start of period $t$ there is a past history $h_{\ell t}$ of signals for
player $\ell$, where $h_{\ell t}=(x_{\ell 0},\dots,x_{\ell t-1})\in
X_{\ell}^{t}$. The filtration induced by agent $\ell$’s histories is denoted
$\mathcal{H}_{\ell}:=(\mathcal{H}_{\ell t})_{t=0}^{\infty}$. Agent $\ell$’s
posterior beliefs about the set $Q\subset\Theta$ of states is written in the
usual way

$E(\mathbbm{1}_{\\{\theta\in Q\\}}\mid\mathcal{H}_{\ell
t})(\omega)\equiv\mathbbm{P}(Q\mid h_{\ell t}(\omega))\equiv\mathbbm{P}(Q\mid
h_{\ell t}).$

For any event $F\in\Omega$ we need to define some other events that describe
the agents’ knowledge about $F$. First $B^{q}_{\ell t}(F)$ is the event that
agent $\ell$ attaches at least probability $q$ to the event $F$ at time $t$.
Second, $B^{q}_{t}(F)$ is the event that all agents attach at least
probability $q$ to $F$ at time $t$:

$B^{q}_{\ell t}(F):=\\{\omega\in\Omega:E(\mathbbm{1}_{F}\mid\mathcal{H}_{\ell
t})\geq q\\},\qquad B^{q}_{t}(F):=\bigcap_{\ell\in[L]}B^{q}_{\ell t}(F).$

It is well known that if an individual gets enough signals, then they will
learn those states that they can identify. That is, individuals’ beliefs
eventually will attach high probability to only those states that could have
generated the signals they observe. More formally, for all $\ell\in[L]$, any
$q<1$, and any $Q_{\ell}\in\mathcal{Q}_{\ell}$

(1) $\lim_{t\rightarrow\infty}\mathbbm{P}^{\theta}\left(B^{q}_{\ell
t}(Q_{\ell})\right)=1,\qquad\forall\theta\in Q_{\ell}.$

A proof of this claim follows from Lemma 1 and, for completeness, is given in
the Appendix.

We now define common learning of sets of states. After this we report an
important sufficient condition for common learning. The event $F$ is said to
be _common $q$-belief at $t$_ on the set of states

(2) $C^{q}_{t}(F):=\bigcap_{n\geq 1}[B^{q}_{t}]^{n}(F).$

Common learning of a set of states $Q\subset\Theta$ requires that for any
$\theta\in Q$ the event $Q$ is eventually common-$q$-belief for any $q$. That
is, for all $q\in(0,1)$ and all $\theta\in Q$

(3)
$\lim_{t\rightarrow\infty}\mathbbm{P}^{\theta}\left(C^{q}_{t}\left(Q\right)\right)=1.$

The characterization of common $q$-belief of Monderer and Samet (1989) below
can be used to write an equivalent but more useful definition of common
learning. The event $F$ is said to be _$q$ -evident at $t$_ if $F\subset
B^{q}_{t}(F)$. That is, if the event $F$ occurred all then agents attach at
least probability $q$ to it. The result below shows that verifying
$q$-evidence of an event is a way of establishing common $q$-belief.

######  Result 1 (Monderer and Samet).

$F^{\prime}$ is common $q$-belief at $\omega\in\Omega$ at time $t$ if and only
if there exists an event $F$ such that $F$ is $q$-evident at time $t$ and
$\omega\in F\subset B^{q}_{t}(F^{\prime})$.

As common $q$-belief (for any $q$) is necessary and sufficient for common
learning, CEMS show that the previous definition for common learning (2) can
be rewritten in terms of $q$-evidence.

######  Definition 3 (Common Learning).

Individuals commonly learn the event $Q\subset\Theta$, if for all $q\in(0,1)$
there exists a time $T$ and a sequence of events $(F_{t})_{t=0}^{\infty}$ such
that for all $t\geq T$ and for all $\theta\in Q$: (1) $F_{t}\subset
B^{q}_{t}(Q)$; (2) $\mathbbm{P}^{\theta}\left(F_{t}\right)>q$; (3) $F_{t}$ is
$q$-evident at $t$.

Notice that if $Q$ is a set with only one element this is equivalent to the
previous definitions of common learning.

##  3\. Common Learning

In this section we will show that the sets in the partition of commonly
identified sets, $\mathcal{QI}$, are commonly learned. We being by describing
some features of individual learning and then move on to proving the main
result.

###  3.1. Individual Learning

Here we define events on signals that will later be used to define $q$-evident
events. These are different from the events used in previous proofs of common
learning. The $q$-evident sets of signals are defined in a way that depends on
$Q_{\ell}$ but they are independent of the particular $\theta\in Q_{\ell}$.
This is because an agent does not know which state in $Q_{\ell}$ is actually
generating their signals. It contrasts with CEMS and Frick, Iijima, and Ishii
(2023), where the $q$-evident sets are sometimes chosen in a way that depends
on the details of the joint distributions of signals $\pi^{\theta}$. In those
constructions, signal profiles that have zero probability affect the fine
details of the $q$-evident event for each state. Assumption 1 allows us avoid
this issue. Also, the total variation norm, $\|.\|_{TV}$, will be used.222
$\|\phi_{\ell}\|_{TV}:=\frac{1}{2}\sum_{x_{\ell}}|\phi_{\ell}(x_{\ell})|$.
This norm permits the use of the Dobrushin Ergodicity Coefficient, which has
useful contraction properties when applied to Markov-like operators. CEMS use
the $\sup$ norm and Frick, Iijima, and Ishii (2023) who use the relative
entropy distance to build a contraction.

The $q$-evident events necessary to establish common learning are constructed
so that all agents observe signals with empirical measures close to their
marginals in a state. For each agent $\ell$ and each signal $x_{\ell}\in
X_{\ell}$, let $\hat{x}_{\ell}(h_{\ell t})\in\mathbbm{Z}_{+}$ count the number
of times the signal $x_{\ell}$ occurs in the history $h_{\ell t}$. Then,
$\hat{\phi}_{\ell t}\in\Delta(X_{\ell})$ is the period-$t$ empirical measure
of agent $\ell$’s signals, where $\hat{\phi}_{\ell
t}(x_{\ell}):=t^{-1}\hat{x}_{\ell}(h_{\ell t})$. If all agents’ empirical
measures at time $t$ are within $\varepsilon$ of their marginal distribution
of signals in state $\theta$, then $I_{t\varepsilon}(\theta)$ has occurred.
That is,

$I_{t\varepsilon}(\theta):=\\{\omega:\|\hat{\phi}_{\ell
t}-\phi^{\theta}_{\ell}\|_{TV}\leq\varepsilon,\forall\ell\in[L]\\}.$

The earlier proofs of common learning showed that neighborhoods like
$I_{t\varepsilon}(\theta)$ are common $q$-belief. In our setting it is
possible that no agent can identify the state $\theta$ or this neighborhood,
so we consider unions of these neighborhoods over the sets of states. The
event $I_{t\varepsilon}(Q)$ is defined so that there is some $\theta\in Q$
such that all agents have observed signals close to the marginals in the state
$\theta$.

######  Definition 4.

For any $\varepsilon>0$ and $Q\subset\Theta$ let
$I_{t\varepsilon}(Q):=\cup_{\theta\in Q}I_{t\varepsilon}(\theta)$.

The following lemma now records some well-know properties of the events
$I_{t\varepsilon}(Q)$ when $Q$ is chosen to lie in the partition of commonly
identified sets: $(I_{t\varepsilon}(Q))_{Q\in\mathcal{QI}}$ . It shows (in
parts (1) and (2)) that if $\theta\in Q\in\mathcal{QI}$, then the agents’
empirical distributions are in the sets $I_{t\varepsilon}(\theta)$ and
$I_{t\varepsilon}(Q)$ with arbitrarily high probability for $t$ sufficiently
large. This follows from the fact that signals are iid and the strong laws of
large numbers. It also shows (part (3)) that if
$Q_{\ell}\in\mathcal{Q}^{\ell}$ is in agent $\ell$’s identification partition
and $Q_{\ell}\ni\theta$, then a lower bound on the agent’s posterior on
$Q_{\ell}$ converges to one on the event $I_{t\varepsilon}(\theta)$ as $t$
grows. This uses the fact that on $I_{t\varepsilon}(\theta)$ the log
likelihoods grow linearly in $t$. Hence (in part 4) $I_{t\varepsilon}(\theta)$
is a subset of the event where $Q_{\ell}$ is $q$-believed by agent $\ell$ for
a suitably chosen $q$. The proof of the Lemma is given in the appendix. It
uses standard results on learning that can be found many places in the
literature.

######  Lemma 1.

There exists $\bar{\varepsilon}>0$ such that for all
$\varepsilon\in(0,\bar{\varepsilon})$ and all $Q\in\mathcal{QI}$

  1. (1)

For all $\theta$, $\mathbbm{P}^{\theta}(I_{t\varepsilon}(\theta))\rightarrow
1$ as $t\rightarrow\infty$.

  2. (2)

For all $\theta\in Q$, $\mathbbm{P}^{\theta}(I_{t\varepsilon}(Q))\rightarrow
1$ as $t\rightarrow\infty$.

  3. (3)

There exists $b>0$ such that for any
$\theta\in\bigcap_{\ell=1}^{L}Q_{\ell}\subset Q$, $\ell\in[L]$, and $\omega\in
I_{t\varepsilon}(\theta)$, $\mathbbm{P}(Q_{\ell}|h_{\ell t}(\omega))\geq
1-\frac{e^{-tb}}{p^{\theta}}$.

  4. (4)

There exists $b>0$ such that for any $\theta\in
Q_{\ell}\in\mathcal{Q}_{\ell}$, any $\ell$, and any $t$,

$I_{t\varepsilon}(\theta)\subset B_{\ell
t}^{q}(Q_{\ell}),\qquad\makebox{if}\qquad q=1-\frac{e^{-tb}}{p^{\theta}}.$

######  Example 1 (Continued).

There are two commonly identified sets of states:
$\\{\theta_{1},\theta_{2},\theta_{3}\\}$ and $\\{\theta_{4}\\}$. We will,
therefore, want to consider the events
$I_{t\varepsilon}(\\{\theta_{1},\theta_{2},\theta_{3}\\})$ and
$I_{t\varepsilon}(\\{\theta_{4}\\})$. The last of these,
$I_{t\varepsilon}(\\{\theta_{4}\\})$, occurs if the empirical measure of agent
1’s signals and the empirical measure of agent 2’s signals are within
$\varepsilon$ of $(3/5,2/5)$. (This is the blue region in Figure 2.) The lemma
says that if $\theta_{4}$ is the true state then this will happen with high
probability for $t$ large. Furthermore, on this event both agents will attach
high probability the $\theta_{4}$. The event
$I_{t\varepsilon}(\\{\theta_{1},\theta_{2},\theta_{3}\\})$ occurs if: the
empirical measure of agent 1’s signals is within $\varepsilon$ of $(1/2,1/2)$
and the empirical measure of agent 2’s signals is within $\varepsilon$ of
either $(1/2,1/2)$ or $(2/3,1/3)$; or if the empirical measure of agent 1’s
signals is within $\varepsilon$ of $(2/3,1/3)$ and the empirical measure of
agent 2’s signals is within $\varepsilon$ of $(1/2,1/2)$. (In pink in the
figure.) These are illustrated in the figure below where the axes describe the
probabilities of the zero signal. When
$I_{t\varepsilon}(\\{\theta_{1},\theta_{2},\theta_{3}\\})$ occurs and agent 1
observes frequencies close to $\frac{1}{2}$ they do not know whether agent 2
has seen frequencies close to $\frac{1}{2}$ or $\frac{2}{3}$. Similarly, if
agent 2 observes frequencies close to $\frac{1}{2}$ they do not know whether
agent 1 has seen frequencies close to $\frac{1}{2}$ or $\frac{2}{3}$.

$\phi_{1}(0)$$0$$\phi_{2}(0)$$\frac{2}{3}$$\frac{3}{5}$$\frac{2}{3}$$\frac{3}{5}$$\frac{1}{2}$$\frac{1}{2}$
Figure 2. $I_{t\varepsilon}(\theta_{4})$ in Blue and
$I_{t\varepsilon}(\theta_{1},\theta_{2},\theta_{2})$ in Pink

###  3.2. Common Learning

What follows is the main/only result of this paper. It shows that the sets in
the partition $\mathcal{QI}$ are commonly learned. The proof simplifies the
original construction of CEMS which allows us to deal with the case that there
are several states that agents cannot detect. The way to proof works is first
explained in the example below.

######  Example 1 (Continued).

Consider the event $I_{t\varepsilon}(\\{\theta_{1},\theta_{2},\theta_{3}\\})$
illustrated in Figure 2. The proof shows that this is common $q$-belief for
$t$ sufficiently large. If this event has occurred, then agent 1 will either
have seen signals that are close to $(\frac{1}{2},\frac{1}{2})$ or close
$(\frac{2}{3},\frac{1}{3})$. Suppose that at time $t$ agent 1 has observed
signals with the empirical probability $(\frac{1}{2}+\nu,\frac{1}{2}-\nu)$.
That is, agent 1 has observed signals distance $\nu$ from the true
distribution of signals in states $\theta_{1}$ and $\theta_{2}$. If $\nu$ is
small and $t$ is large, agent 1 will only attach high probability to these two
states. Agent 1’s expected frequencies agent 2’s signals will depend on which
state ($\theta_{1}$ or $\theta_{2}$) occurred. Conditional on $\theta_{1}$ she
will do the calculation below to form her expectation of the empirical measure
of agent 2’s signals:

$({\textstyle\frac{1}{2}}+\nu,{\textstyle\frac{1}{2}}-\nu)\left[\begin{array}[]{cc}\frac{3}{4}&\frac{1}{4}\\\
\frac{1}{4}&\frac{3}{4}\end{array}\right]=({\textstyle\frac{1+\nu}{2}},{\textstyle\frac{1-\nu}{2}}).$

Conditional on $\theta_{2}$ she will do the different calculation:

$({\textstyle\frac{1}{2}}+\nu,{\textstyle\frac{1}{2}}-\nu)\left[\begin{array}[]{cc}\frac{5}{6}&\frac{1}{6}\\\
\frac{1}{2}&\frac{1}{2}\end{array}\right]=({\textstyle\frac{2+\nu}{3}},{\textstyle\frac{1-\nu}{3}}),$

Whichever of the states $\theta_{1}$ or $\theta_{2}$ occurred, her
expectations of agent 2’s empirical measure are even closer (in the variation
norm) to agent 2’s marginals than agent 1’s signals are.333For this to be true
in general requires Assumption 1. If agent 1 observes signals close to the
marginal in the partition element $\\{\theta_{1},\theta_{2}\\}$, they do not
know which of these two states has occurred, but if it was $\theta_{1}$
(respectively $\theta_{2}$) then agent 2’s signals are in
$I_{t\varepsilon}(\\{\theta_{1}\\})$ (respectively
$I_{t\varepsilon}(\\{\theta_{2}\\})$) with high probability. As
$I_{t\varepsilon}(\\{\theta_{1},\theta_{2}\\})\subset
I_{t\varepsilon}(\\{\theta_{1},\theta_{2},\theta_{3}\\})$ they also attach
high probability to this event. Repeating this procedure for all agents and
all elements of the identification partitions that lie in
$\\{\theta_{1},\theta_{2},\theta_{3}\\}$ we can show that this event is
$q$-believed for $t$ large.

This illustrates the principal difference between this result and ones where
all states are identified. It is necessary that expectations are closer in the
variation norm for _all_ of the states in the partition element
$\\{\theta_{1},\theta_{2}\\}$, thus the fine details of the joint
distributions of the signals in one of these states cannot be used to define
$q$-evident events.

######  Proposition 1.

The event $Q\subset\Theta$ is commonly learned if and only if
$Q\in\mathcal{QI}$.

###### Proof.

We begin by proving sufficiency. Let $Q^{*}\in\mathcal{QI}$ and $q\in(0,1)$ be
given. Choose $\varepsilon\in(0,\bar{\varepsilon})$ as in Lemma 1 and
$\beta\in(0,1)$ sufficiently small so that $q^{\beta}(1-L(1-q^{\beta}))>q$. We
will show that the sequence of events
$(I_{t\varepsilon}(Q^{*}))_{t=0}^{\infty}$ has the properties required of the
sequence $(F_{t})_{t=0}^{\infty}$ in Definition 3. Hence we will show that
$Q^{*}$ is commonly learned.

By Part 2 of Lemma 1,
$\mathbbm{P}^{\theta}(I_{t\varepsilon}(Q^{*}))\rightarrow 1$ for any
$\theta\in Q^{*}$. Choose $T^{\prime}$ so that
$\mathbbm{P}^{\theta}(I_{t\varepsilon}(Q^{*}))>q^{\beta}$ for all $t\geq
T^{\prime}$ and all $\theta\in Q^{*}$. We, then, will choose

$T\geq T^{\prime}\wedge\max_{\theta}\frac{\log(1-q^{\beta})p_{\theta}}{-b}.$

_(1) To show $I_{t\varepsilon}(Q^{*})\subset B^{q}_{t}(Q^{*})$ for all $t\geq
T$:_ Note that the above lower bound on $T$ ensures that $q^{\beta}\leq
1-e^{-tb}/p^{\theta}$ for all $t\geq T$ and $\theta$. Pick
$\theta\in\bigcap_{\ell=1}^{L}Q_{\ell}\subset Q^{*}$, then by Part 3 of Lemma
1, $I_{t\varepsilon}(\theta)\subset B_{\ell t}^{q^{\beta}}(Q_{\ell})$ for all
$\ell\in[L]$ and $t\geq T$. As $Q_{\ell}\subset Q^{*}$ this implies
$I_{t\varepsilon}(\theta)\subset B_{\ell t}^{q^{\beta}}(Q^{*})$ for all $\ell$
and all $t\geq T$. Therefore, $I_{t\varepsilon}(\theta)\subset
B_{t}^{q^{\beta}}(Q^{*})$ for all $t\geq T$. This inclusion holds for all
$\theta\in Q^{*}$, so we can take a union over the events on the left to get
$I_{t\varepsilon}(Q^{*})\subset B_{t}^{q^{\beta}}(Q^{*})$ for all $t\geq T$.
The claim $I_{t\varepsilon}(Q^{*})\subset B^{q}_{t}(Q^{*})$ follows as
$\beta<1$.

_(2) To show that for all $\theta\in Q^{*}$ and all $t\geq T$,
$\mathbbm{P}^{\theta}(I_{t\varepsilon}(Q^{*}))>q$:_ This follows from the
choice of $T\geq T^{\prime}$ and $\beta<1$.

(3) _$I_{t\varepsilon}(Q^{*})$ is $q$-evident for all $t>T$:_ Pick $\omega\in
I_{t\varepsilon}(Q^{*})$, then by definition there must be some
$\theta\in\bigcap_{\ell=1}^{L}Q^{*}_{\ell}\subset Q^{*}$ such that $\omega\in
I_{t\varepsilon}(\theta^{*})$. Hence, at $\omega$ the empirical measure of
each agent’s signals is close to their marginals under $\theta^{*}$:
$\|\hat{\phi}_{\ell t}-\phi^{\theta^{*}}_{\ell}\|_{TV}<\varepsilon$ for all
$\ell$.

Now we define a family of matrices for each state $\theta\in\Theta$. The
matrix $M^{\theta}_{\ell\ell^{\prime}}$ is
$|X_{\ell}|\times|X_{\ell^{\prime}}|$ and has rows that describe agent
$\ell$’s conditional beliefs about agent $\ell^{\prime}$’s signals in the
state $\theta$.

The entries in the matrix are $\pi^{\theta}(x_{\ell},x_{\ell^{\prime}})$, the
marginal distribution on agents $\ell$ and $\ell^{\prime}$’s signals,
normalized by $\phi_{\ell}^{\theta}(x_{\ell})$ the marginal on agent $\ell$’s
signals. Therefore, these non-square matrices have rows that sum to unity like
Markov matrices.

$M^{\theta}_{\ell\ell^{\prime}}:=\left(\frac{\pi^{\theta}(x_{\ell},x_{\ell^{\prime}})}{\phi_{\ell}^{\theta}(x_{\ell})}\right)_{x_{\ell}\in
X_{\ell},x_{\ell^{\prime}}\in X_{\ell^{\prime}}},\makebox{where}\ \ \
\pi^{\theta}(x_{\ell},x_{\ell^{\prime}}):=\sum_{x_{-\ell\ell^{\prime}}\in
X_{-\ell\ell^{\prime}}}\pi^{\theta}(x_{\ell},x_{\ell^{\prime}},x_{-\ell\ell^{\prime}}).$

(Recall that will use $x_{-\ell\ell^{\prime}}$ to denote the signal profile
$x\in X$ with the $\ell^{\rm th}$ and $\ell^{\prime\rm th}$ entries omitted.)
If we treat $\phi^{\theta}_{\ell}$ and $\phi^{\theta}_{\ell^{\prime}}$ as
column vectors then elementary arithmetic shows that

(4)
$(\phi^{\theta}_{\ell})^{T}M^{\theta}_{\ell\ell^{\prime}}=(\phi^{\theta}_{\ell^{\prime}})^{T},\qquad\forall\ell\not=k.$

We now describe the _Doeblin contraction coefficient_ or _Dobrushin’s ergodic
coefficient_ of the matrix $M^{\theta}_{\ell\ell^{\prime}}$. Let
$m^{\theta}_{\ell\ell^{\prime}}(x_{\ell})\in\Delta(X_{\ell^{\prime}})$ be the
$x_{\ell}^{\rm th}$ row of $M^{\theta}_{\ell\ell^{\prime}}$. By Assumption 1,
these conditional probability distributions have full support, therefore, for
all $\theta$ and all $\ell\not=\ell^{\prime}$

$\displaystyle\|m^{\theta}_{\ell\ell^{\prime}}(x_{\ell})-m^{\theta}_{\ell\ell^{\prime}}(x^{\prime}_{\ell})\|_{TV}$
$\displaystyle<1,\qquad\forall x_{\ell},x^{\prime}_{\ell}\in X_{\ell}.$

(The variation distance will equal one only if the measures have disjoint
support.) We will define $\lambda^{\theta}_{\ell\ell^{\prime}}<1$ to be the
maximum variation distance between the rows of
$M^{\theta}_{\ell\ell^{\prime}}$, that is,

$\lambda^{\theta}_{\ell\ell^{\prime}}:=\max_{x_{\ell},x^{\prime}_{\ell}\in
X_{\ell}}\|m^{\theta}_{\ell\ell^{\prime}}(x_{\ell})-m^{\theta}_{\ell\ell^{\prime}}(x^{\prime}_{\ell})\|_{TV}.$

This maximum is also strictly less than one by finiteness. The value
$\lambda^{\theta}_{\ell\ell^{\prime}}$ is known as Doeblin contraction
coefficient or Dobrushin’s Ergodic Coefficient of the matrix
$M^{\theta}_{\ell\ell^{\prime}}$. Let $\lambda<1$ be the largest value of
$\lambda^{\theta}_{\ell\ell^{\prime}}$, that is
$\lambda:=\max_{\ell,\ell^{\prime},\theta}\lambda^{\theta}_{\ell\ell^{\prime}}$.
By Theorem 7.3 Brémaud (1999) p.237 we have that for any
$\ell\not=\ell^{\prime}$, any
$\phi_{\ell},\phi^{\prime}_{\ell}\in\Delta(X_{\ell})$ and any $\theta$

(5)
$\|(\phi_{\ell})^{T}M^{\theta}_{\ell\ell^{\prime}}-(\phi^{\prime}_{\ell})^{T}M^{\theta}_{\ell\ell^{\prime}}\|_{TV}\leq\lambda^{\theta}_{\ell\ell^{\prime}}\|\phi_{\ell}-\phi^{\prime}_{\ell}\|_{TV}\leq\lambda\|\phi_{\ell}-\phi^{\prime}_{\ell}\|_{TV}.$

Thus the matrices $M^{\theta}_{\ell\ell^{\prime}}$ describe linear operators
from $\Delta(X_{\ell})$ to $\Delta(X_{\ell^{\prime}})$ that are contractions
in the variation norm and $\lambda$ is an upper bound this contraction.

By CEMS Lemma 3 (p.923), $(\hat{\phi}_{\ell
t})^{T}M^{\theta}_{\ell\ell^{\prime}}$ is agent $\ell$’s best prediction of
agent $\ell^{\prime}$’s empirical measure. To be precise, it is says that for
any $q<1$ there exists a $T_{3}$ such that for all $\theta$ all
$\ell^{\prime}\not=\ell$ and all $t\geq T_{3}$

(6) $\displaystyle\mathbbm{P}^{\theta}\left(\left\|(\hat{\phi}_{\ell
t})^{T}M^{\theta}_{\ell\ell^{\prime}}-(\hat{\phi}_{\ell^{\prime}t})^{T}\right\|_{TV}\leq(1-\lambda)\varepsilon\mid
h_{\ell t}\right)>q^{\beta},$

(Note: In CEMS the norm is the twice the total variation norm that is used
here.)

Now we will combine the conditions (5) and (6) to show that when $\omega\in
I_{t\varepsilon}(\theta^{*})$ agent $\ell$ attaches high probability to the
event $I_{t\varepsilon}(Q^{*}_{\ell})$ having occurred. Consider agent $\ell$
at $\omega\in I_{t\varepsilon}(\theta^{*})\subset I_{t\varepsilon}(Q^{*})$.
Conditional any $\theta$ we derive an upper bound on how far agent
$\ell^{\prime}$’s empirical measure is from its true marginal in terms on
agent $\ell$’s marginal. First notice we have the following upper bound on
this:

$\displaystyle\|\hat{\phi}_{\ell^{\prime}t}-\phi^{\theta}_{\ell^{\prime}}\|_{TV}$
$\displaystyle=\|(\hat{\phi}_{\ell^{\prime}t})^{T}-(\phi^{\theta}_{\ell})^{T}M^{\theta}_{\ell\ell^{\prime}}\|_{TV}$
$\displaystyle\leq\|(\hat{\phi}_{\ell^{\prime}t})^{T}-(\hat{\phi}_{\ell
t})^{T}M^{\theta}_{\ell\ell^{\prime}}\|_{TV}+\|(\hat{\phi}_{\ell
t})^{T}M^{\theta}_{\ell\ell^{\prime}}-(\phi^{\theta}_{\ell})^{T}M^{\theta}_{\ell\ell^{\prime}}\|_{TV}$
$\displaystyle\leq\|(\hat{\phi}_{\ell^{\prime}t})^{T}-(\hat{\phi}_{\ell
t})^{T}M^{\theta}_{\ell\ell^{\prime}}\|_{TV}+\lambda\|\hat{\phi}_{\ell
t}-\phi^{\theta}_{\ell}\|_{TV}$

(The first equality substitutes from (4), then there is an application of the
triangle inequality and the final upper bound uses (5).)

Suppose that $\omega\in I_{t\varepsilon}(\theta^{*})$. As
$\phi^{\theta^{*}}_{\ell}=\phi^{\theta}_{\ell}$ for all $\theta\in
Q^{*}_{\ell}$, we know that $\|\hat{\phi}_{\ell
t}-\phi^{\theta}_{\ell}\|_{TV}\leq\varepsilon$ for all $\theta\in
Q^{*}_{\ell}$. Thus if $\omega\in I_{t\varepsilon}(\theta^{*})$

$\|\hat{\phi}_{\ell^{\prime}t}-\phi^{\theta}_{\ell^{\prime}}\|_{TV}\leq\|(\hat{\phi}_{\ell^{\prime}t})^{T}-(\hat{\phi}_{\ell
t})^{T}M^{\theta}_{\ell\ell^{\prime}}\|_{TV}+\lambda\varepsilon,\qquad\forall\theta\in
Q^{*}_{\ell}.$

By (6) the first term on the right is less than $\varepsilon(1-\lambda)$ with
at least probability $q^{\beta}$ in any state $\theta$. Thus the right is less
than $\varepsilon$ with at least probability $q^{\beta}$ in all states
$\theta\in Q^{*}_{\ell}$. That is, for all $t>\max\\{T_{3},T\\}$, all
$\omega\in I_{t\varepsilon}(\theta^{*})$, all $\ell^{\prime}\not=\ell$ and all
$\theta\in Q^{*}_{\ell}$

(7)
$\mathbbm{P}^{\theta}\left(\left\|\hat{\phi}_{\ell^{\prime}t}-\phi^{\theta}_{\ell^{\prime}}\right\|_{TV}\leq\varepsilon\mid
h_{\ell t}\right)>q^{\beta}$

If agent $\ell$ observes a history consistent with $\omega\in
I_{t\varepsilon}(\theta^{*})$, the event $I_{t\varepsilon}(\theta^{*})$ occurs
if
$\|\hat{\phi}_{\ell^{\prime}t}-\phi^{\theta^{*}}_{\ell^{\prime}}\|_{TV}\leq\varepsilon$
for all agents $\ell^{\prime}\not=\ell$, because agent $\ell$ knows their
signals satisfy this condition. From the lower bound (7), the probability that
all $L-1$ of these events occurs is at least $1-L(1-q^{\beta})$. Hence we have
that if $\omega\in I_{t\varepsilon}(\theta^{*})$ for all $\theta\in
Q^{*}_{\ell}$

(8) $\mathbbm{P}^{\theta}(I_{t\varepsilon}(\theta)\mid h_{\ell
t})=\mathbbm{P}^{\theta}(\|\hat{\phi}_{\ell^{\prime}t}-\phi^{\theta}_{\ell^{\prime}}\|_{TV}\leq\varepsilon,\forall\ell^{\prime}\not=\ell\mid
h_{\ell t})>1-L(1-q^{\beta})$

Finally we can establish the $q$-evidence. Recall that $Q^{*}\in\mathcal{QI}$
and that $Q^{*}_{\ell}\subset Q^{*}$. We begin by doing the following
calculation which uses the fact that conditional on $\theta\in Q^{*}_{\ell}$
agent $\ell$’s beliefs are equal to their priors.

$\displaystyle\mathbbm{P}(I_{t\varepsilon}(Q^{*})\mid h_{\ell t})$
$\displaystyle\geq\mathbbm{P}(I_{t\varepsilon}(Q^{*}_{\ell})\mid h_{\ell t})$
$\displaystyle\geq\mathbbm{P}(Q^{*}_{\ell}\mid h_{\ell
t})\mathbbm{P}(I_{t\varepsilon}(Q^{*}_{\ell})\mid h_{\ell t},\theta\in
Q^{*}_{\ell})$ $\displaystyle=\mathbbm{P}(Q^{*}_{\ell}\mid h_{\ell
t})\frac{\sum_{\theta\in
Q^{*}_{\ell}}p_{\theta}\mathbbm{P}^{\theta}(I_{t\varepsilon}(Q^{*}_{\ell})\mid
h_{\ell t})}{\sum_{\theta^{\prime}\in Q^{*}_{\ell}}p_{\theta^{\prime}}}$
$\displaystyle\geq\mathbbm{P}(Q^{*}_{\ell}\mid h_{\ell
t})\frac{\sum_{\theta\in
Q^{*}_{\ell}}p_{\theta}\mathbbm{P}^{\theta}(I_{t\varepsilon}(\theta)\mid
h_{\ell t})}{\sum_{\theta^{\prime}\in Q^{*}_{\ell}}p_{\theta^{\prime}}}$

By (8) if $\omega\in I_{t\varepsilon}(\theta^{*})$ then we have a lower bound
on all of the terms in the final summation above. Hence for all
$t>\max\\{T_{3},T\\}$ and all $\omega\in I_{t\varepsilon}(\theta^{*})$ we have
that

$\mathbbm{P}(I_{t\varepsilon}(Q^{*})\mid h_{\ell
t})\geq\mathbbm{P}(Q^{*}_{\ell}\mid h_{\ell t})(1-L(1-q^{\beta})).$

By our choice of $T$ we also have that $\mathbbm{P}(Q^{*}_{\ell}\mid h_{\ell
t})\geq q^{\beta}$. Thus we have that for $t>\max\\{T_{3},T\\}$ and all
$\omega\in I_{t\varepsilon}(\theta^{*})$

$\mathbbm{P}(I_{t\varepsilon}(Q^{*})\mid h_{\ell t})\geq
q^{\beta}(1-L(1-q^{\beta}))>q.$

(The final inequality follows from our choice of $\beta$.) Using the language
of beliefs this shows that $I_{t\varepsilon}(\theta^{*})\subset
B^{q}_{\ell}(I_{t\varepsilon}(Q^{*}))$. As this holds for all agents $\ell$
and for any $\theta^{*}\in Q^{*}$ this implies $I_{t\varepsilon}(Q^{*})\subset
B^{q}(I_{t\varepsilon}(Q^{*}))$ and so $I_{t\varepsilon}(Q^{*})$ is
$q$-evident for all $t>\max\\{T,T_{3}\\}$ and we have completed the proof of
Step 3.

Finally, we need to show that $Q\in\mathcal{QI}$ is necessary for common
learning. Consider a set $\hat{Q}\not\in\mathcal{QI}$ we will show that this
cannot be commonly learned. As $\hat{Q}\not\in\mathcal{QI}$, the set $\hat{Q}$
is not generated by the information partition of some agent $\ell$. Hence
there exists $\tilde{\theta},\hat{\theta}\in Q_{\ell}\in\mathcal{Q}_{\ell}$ so
that $\hat{\theta}\in\hat{Q}$ but $\tilde{\theta}\not\in\hat{Q}$. By (1) we
know that for any $r<1$

$\lim_{t\rightarrow\infty}\mathbbm{P}^{\hat{\theta}}(B^{r}_{\ell
t}(Q_{\ell}))=1.$

Let $p^{\tilde{\theta}}$ be the prior probability of state $\tilde{\theta}$.
As the relative probabilities that agent $\ell$ attaches to states in
$Q_{\ell}$ do not change as they observe their signals, agent $\ell$ must
attach at least probability $rp^{\tilde{\theta}}$ to state $\tilde{\theta}$ if
she attaches probability $r$ to $Q_{\ell}$, hence for any $r<1$

$\lim_{t\rightarrow\infty}\mathbbm{P}^{\hat{\theta}}(B^{rp^{\tilde{\theta}}}_{\ell
t}(\\{\tilde{\theta}\\}))=1.$

Choose $\bar{q}\in(1-rp^{\tilde{\theta}},1)$. If you attach probability
$rp^{\tilde{\theta}}$ to an event it is impossible to attach probability
$\bar{q}$ to its complement. Therefore, as $\tilde{\theta}\not\in\hat{Q}$ the
above implies

(9) $\lim_{t\rightarrow\infty}\mathbbm{P}^{\hat{\theta}}(B^{q}_{\ell
t}(\hat{Q}))=0,\qquad\forall q>\bar{q}.$

From the definitions of common learning (2) and (3), $\hat{Q}$ is commonly
learned if for all $q\in(0,1)$ and for all $\theta\in\hat{Q}$

$\lim_{t\rightarrow\infty}\mathbbm{P}^{\theta}\left(C^{q}_{t}\left(\hat{Q}\right)\right)=1\qquad\makebox{where}\qquad
C^{q}_{t}(\hat{Q}):=\bigcap_{n\geq 1}[B^{q}_{t}]^{n}(\hat{Q}).$

But $C^{q}_{t}\left(\hat{Q}\right)\subset B^{q}_{t}(\hat{Q})\subset
B^{q}_{\ell t}(\hat{Q})$ and $\hat{\theta}\in\hat{Q}$ so

$\lim_{t\rightarrow\infty}\mathbbm{P}^{\hat{\theta}}\left(C^{q}_{t}\left(\hat{Q}\right)\right)\leq\limsup_{t\rightarrow\infty}\mathbbm{P}^{\hat{\theta}}\left(B^{q}_{\ell
t}(\hat{Q})\right)$

However, by (9) the right hand side is bounded by zero if $q>\bar{q}$. This
means common learning is does not hold. ∎

##  4\. Conclusion

We have generalised the results of CEMS to the case where not all agents learn
all the states. This generalisation is not without cost, however, as it was
necessary to assume that signals have full support.

## References

  * (1)
  * Brémaud (1999) Brémaud, P. (1999): _Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues_. Springer-Verlag, New York.
  * Cover and Thomas (1991) Cover, T. M., and J. A. Thomas (1991): _Elements of Information Theory_. John Wiley & Sons, Inc., New York.
  * Cripps, Ely, Mailath, and Samuelson (2008) Cripps, M. W., J. C. Ely, G. J. Mailath, and L. Samuelson (2008): “Common Learning,” _Econometrica_ , 76(4), 909–933.
  * Frick, Iijima, and Ishii (2023) Frick, M., R. Iijima, and Y. Ishii (2023): “Learning Efficiency of Multiagent Information Structures,” _Journal of Political Economy_ , 131(12), 3377–3414.
  * Monderer and Samet (1989) Monderer, D., and D. Samet (1989): “Approximating Common Knowledge with Common Beliefs,” _Games and Economic Behavior_ , 1(2), 170–190.

## Appendix

### Proof of Lemma 1

Let $\theta\in\bigcap_{\ell=1}^{L}Q_{\ell}$ be given, where every
$Q_{\ell}\in\mathcal{Q}_{\ell}$, and let

$H(\phi_{\ell}\|\phi_{\ell}^{\prime}):=\sum_{x_{\ell}}\phi_{\ell}(x_{\ell})\log\frac{\phi_{\ell}(x_{\ell})}{\phi^{\prime}_{\ell}(x_{\ell})},\qquad\phi_{\ell},\phi^{\prime}_{\ell}\in\Delta(X_{\ell});$

denote the Kullback-Leibler divergence (assuming
$\phi^{\prime}_{\ell}(x_{\ell})>0$). Also,
$N_{\varepsilon}(\phi_{\ell}):=\\{\phi^{\prime}_{\ell}\in\Delta(X_{\ell}):\|\phi_{\ell}-\phi^{\prime}_{\ell}\|_{TV}\leq\varepsilon\\}$
will be used to denote an $\varepsilon$-neighbourhood of $\phi_{\ell}$ in the
total variation norm. If $\theta\in\bigcap_{\ell=1}^{L}Q_{\ell}$, then in
states $\theta\not\in Q_{\ell}$ agent $\ell$ observes signals sampled from
distinct distributions from those generated by signals in $Q_{\ell}$. So, if
$\phi_{\ell}=\phi_{\ell}^{\theta}$ then
$H(\phi_{\ell}\|\phi_{\ell}^{\theta})-H(\phi_{\ell}\|\phi_{\ell}^{\theta^{\prime}})<0$
for all $\theta^{\prime}\not\in Q_{\ell}$. As $H$ is a continuous function of
$\phi_{\ell}$, the finite set of strict inequalities

$H(\phi_{\ell}\|\phi_{\ell}^{\theta})-H(\phi_{\ell}\|\phi_{\ell}^{\theta^{\prime}})<0,\qquad\theta^{\prime}\not\in
Q_{\ell};$

continues to hold for $\phi_{\ell}$ close to $\phi_{\ell}^{\theta}$. As there
are a finite number of states and agents we can choose a neighborhood size so
these inequalities hold for all states and agents. That is, there exists an
$\bar{\varepsilon}>0$ such that for all $\theta\in\Theta$, all $\ell$, and all
$\varepsilon\in(0,\bar{\varepsilon})$

$H(\phi_{\ell}\|\phi_{\ell}^{\theta})-H(\phi_{\ell}\|\phi_{\ell}^{\theta^{\prime}})<0,\qquad\forall\phi_{\ell}\in
N_{\varepsilon}(\phi_{\ell}^{\theta}),\theta\in
Q_{\ell},\theta^{\prime}\not\in Q_{\ell}.$

Given this finite collection of strict inequalities there exists $b>0$,
dependent on $\varepsilon$, so that for all $\theta$ and all $\ell$

(10)
$H(\phi_{\ell}\|\phi_{\ell}^{\theta})-H(\phi_{\ell}\|\phi_{\ell}^{\theta^{\prime}})<-b,\qquad\forall\phi_{\ell}\in
N_{\varepsilon}(\phi_{\ell}^{\theta}),\theta\in
Q_{\ell},\theta^{\prime}\not\in Q_{\ell}.$

#### Part (1):

Sanov’s Theorem (see for example Cover and Thomas (1991) p.292) gives bounds
on the probability that $\hat{\phi}_{\ell t}\in
N_{\varepsilon}(\phi_{\ell}^{\theta})$ conditional on $\theta$ being the true
state.

(11)
$1-(t+1)^{-|X_{\ell}|}e^{-t\alpha_{\ell\theta}(\varepsilon)}\geq\mathbbm{P}^{\theta}\left(\hat{\phi}_{\ell
t}\in N_{\varepsilon}(\phi_{\ell}^{\theta})\right)\geq
1-(t+1)^{|X_{\ell}|}e^{-t\alpha_{\ell\theta}(\varepsilon)}.$

where
$\alpha_{\ell\theta}(\varepsilon):=\inf\\{H(\phi_{\ell}\|\phi_{\ell}^{\theta}):\phi_{\ell}\in\Delta(X_{\ell})\setminus
N_{\varepsilon}(\phi_{\ell}^{\theta})\\}$. The event
$I_{t\varepsilon}(\theta)$ is the intersection of the events $\hat{\phi}_{\ell
t}\in N_{\varepsilon}(\phi_{\ell}^{\theta})$ for $\ell\in[L]$. Thus

$\mathbbm{P}^{\theta}(I_{t\varepsilon}(\theta))\geq
1-\sum_{\ell\in[L]}(t+1)^{|X_{\ell}|}e^{-t\alpha_{\ell\theta}(\varepsilon)},$

and the claim follows.

#### Part (2):

This is true as $I_{t\varepsilon}(\theta)\subset I_{t\varepsilon}(Q)$ and part
(1) holds.

#### Part (3):

Let $\hat{\phi}_{\ell t}$ be the empirical probabilities of agent $\ell$’s
signals at time $t$. Then,

$\displaystyle\log\mathbbm{P}(\theta^{\prime}|h_{\ell t})$
$\displaystyle\leq\log\frac{\mathbbm{P}(\theta^{\prime}|h_{\ell
t})}{\mathbbm{P}(\theta|h_{\ell t})}=\log\frac{\mathbbm{P}(\theta^{\prime}\cap
h_{\ell t})}{\mathbbm{P}(\theta\cap h_{\ell t})}$
$\displaystyle=\log\frac{p^{\theta^{\prime}}}{p^{\theta}}+t\sum_{x_{\ell}\in
X_{\ell}}\hat{\phi}_{\ell
t}(x_{\ell})\log\frac{\phi_{\ell}^{\theta^{\prime}}(x_{\ell})}{\phi_{\ell}^{\theta}(x_{\ell})}$
$\displaystyle=\log\frac{p^{\theta^{\prime}}}{p^{\theta}}+t\left[H(\hat{\phi}_{\ell
t}\|\phi_{\ell}^{\theta})-H(\hat{\phi}_{\ell
t}\|\phi_{\ell}^{\theta^{\prime}})\right]$

(Here the second equality follows from a substitution for the probabilities of
the history $h_{\ell t}$.) For any $\varepsilon<\bar{\varepsilon}$ and
$\hat{\phi}_{\ell t}\in N_{\varepsilon}(\phi_{\ell}^{\theta})$ and
$\theta^{\prime}\not\in Q_{\ell}$ there is an upper bound of $-b$ on the term
in square parentheses in (10). Hence, for all $\theta^{\prime}\not\in
Q_{\ell}$ and all $\hat{\phi}_{\ell t}\in
N_{\varepsilon}(\phi_{\ell}^{\theta})$,

$\mathbbm{P}(\theta^{\prime}|h_{\ell
t})\leq\frac{p^{\theta^{\prime}}}{p^{\theta}}e^{-tb}.$

A summation then implies that for $\hat{\phi}_{\ell t}\in
N_{\varepsilon}(\phi_{\ell}^{\theta})$

(12) $\mathbbm{P}(Q_{\ell}|h_{\ell t})=1-\sum_{\theta^{\prime}\not\in
Q_{\ell}}\mathbbm{P}(\theta^{\prime}|h_{\ell t})\geq
1-\frac{e^{-tb}}{p^{\theta}}.$

### Proof of (1)

Conditional on $\theta\in\bigcap_{\ell=1}^{L}Q_{\ell}$ the random variables
$\mathbbm{P}(Q_{\ell}|h_{\ell t})$ are bounded submartingales with respect to
the filtrations $(\mathcal{H}_{\ell t})$. By Doob’s Theorem they converge
almost surely. It remains to show that this limit is one. This can be
established by combining (12) and (11). That is, $\mathbbm{P}(Q_{\ell}|h_{\ell
t})\geq 1-\frac{1}{p^{\theta}}e^{-tb}$ with at least probability
$1-(t+1)^{|X_{\ell}|}e^{-t\alpha_{\theta}(\varepsilon)}$ conditional on
$\theta$.