Common knowledge/shared knowledge

2.1 A world of four bits

Large worlds hurt my brain, so here is a small one. Take \(\Omega = \{0,1\}^4\), a bitstring of length four drawn uniformly. Aulia reads the first two bits, \(\pi_a(\omega_1\omega_2\omega_3\omega_4) = \omega_1\omega_2\); Bayu reads the middle two, \(\pi_b(\omega_1\omega_2\omega_3\omega_4) = \omega_2\omega_3\). Their acuities overlap without nesting. “Is the second bit \(1\)?” is a question both can pose; “is the first bit \(1\)?” only Aulia; “is the third bit \(1\)?” only Bayu; and the fourth bit is invisible to both. Neither agent is strictly “sharper” than the other, so neither \(\mathscr{G}_a \subseteq \mathscr{G}_b\) nor \(\mathscr{G}_b \subseteq \mathscr{G}_a\). The two of them have identical observation spaces here, \(\mathcal{X}_a = \mathcal{X}_b = \{0,1\}^2\) with \(\mathscr{B}_i\) the power set; all the asymmetry lives in the maps \(\pi_i\).

Another useful term: The fibre of agent \(i\) over a reading \(x \in \mathcal{X}_i\) is the preimage \(\pi_i^{-1}(\{x\})\): the world-states that reading cannot separate. Aulia’s fibre over the reading \(01\) is the four states \(01{*}{*}\), so her fibres partition \(\Omega\) into four blocks of four, and Bayu’s partition it into four different blocks of four. Everything an agent can express is a union of their own fibres.

For general \(\pi_a, \pi_b\), the induced algebras \(\mathscr{G}_a\) and \(\mathscr{G}_b\) can stand in complicated relationships. They could overlap partially, as in the four-bit world; they could share nothing but \(\{\emptyset, \Omega\}\); each could express events the other cannot. Let us define some operations on the algebras to talk about these relationships.

the join \(\sigma(\mathscr{G}_a \cup \mathscr{G}_b)\)

Everything the two agents can express between them. A union of two σ-algebras is not generally a σ-algebra, so we have to close it under complement and countable union. It is the smallest σ-algebra containing both \(\mathscr{G}_a\) and \(\mathscr{G}_b\).

the common ground \(\mathscr{G}_a \cap \mathscr{G}_b\)

Events both agents can express. An intersection of σ-algebras is a σ-algebra already, so there is nothing to close. It can be as small as \(\{\emptyset, \Omega\}\).

Both of those are defined in \(\mathscr{F}\). The join may be described explicitly as \(\sigma(\pi_a, \pi_b)\) — in the four-bit world, \(\sigma(\omega_1, \omega_2, \omega_3)\) — which is what a third agent who collates both Aulia and Bayu’s observations would register. The common ground has no such description, for interesting reasons.

Which of the two carries the common knowledge is worth spelling out, since both are easy to misfile against the vocabulary at the top of this page. The join is what epistemic logicians call distributed knowledge: what the pair would know pooled, which is to say what neither of them knows (Halpern and Moses 1990). Shared knowledge is not an algebra here at all — “both of them know \(E\)” is itself an event, the set of world-states where each one’s fibre lies inside \(E\) — and iterating it, each knowing that each knows and so on up, is the alternating hopping defined below, whose limit is the common ground. The common ground, standardly the meet of the two agents’ partitions, is therefore where common knowledge lives.

Why can we not write out the common ground \(\mathscr{G}_a \cap \mathscr{G}_b\) explicitly in terms of the agents’ own spaces \((\mathcal{X}_a, \mathscr{B}_a)\) and \((\mathcal{X}_b, \mathscr{B}_b)\), as we can with the join?

The common ground turns out not to be any explicit function of the two agents’ spaces. Hold the four-bit world fixed and change only which bits Bayu reads. Reading \(\omega_2\omega_3\), as above, he shares the second bit with Aulia. Reading the last two bits instead, \(\pi_b(\omega) = \omega_3\omega_4\), he shares nothing with her, and the common ground collapses to \(\{\emptyset, \Omega\}\). Nothing about either agent’s space changed between those two cases — both readings hand Bayu \(\{0,1\}^2\) and the same σ-algebra on it, and Aulia’s map is untouched. What differs is how the two sets of fibres cut across each other inside \(\Omega\).

The common ground has to be approached rather than built. Write \(\omega \sim_i \omega'\) when agent \(i\) reads the two states identically, \[\omega \sim_i \omega' \iff \pi_i(\omega) = \pi_i(\omega'),\] which says exactly that \(\omega'\) lies in \(i\)’s fibre through \(\omega\). A hop is one step along one of these relations: an Aulia-hop moves along \(\sim_a\), a Bayu-hop along \(\sim_b\). In the four-bit world, \(\omega \sim_a \omega'\) iff \(\omega_1\omega_2 = \omega'_1\omega'_2\), and \(\omega \sim_b \omega'\) iff \(\omega_2\omega_3 = \omega'_2\omega'_3\) — so an Aulia-hop is free to rewrite \(\omega_3\omega_4\), and a Bayu-hop \(\omega_1\omega_4\). Chaining hops gives a coarser relation: we write \(\omega \approx \omega'\) when some finite alternating chain \[\omega \sim_a \omega^{(1)} \sim_b \omega^{(2)} \sim_a \cdots \omega'\] joins them. (Superscripts index the chain; subscripts on \(\omega\) still index bits.)

Read epistemically, \(\sim_i\) is considers-it-possible: having read \(\pi_i(\omega)\), agent \(i\) cannot rule out any \(\omega'\) with \(\omega' \sim_i \omega\), those states being the ones their reading does not separate. So agent \(i\) knows \(E\) at \(\omega\) when every \(\omega' \sim_i \omega\) lies in \(E\); both of them know \(E\) when that holds for \(i = a\) and for \(i = b\); Aulia knows that Bayu knows \(E\) when every \(\omega^{(2)}\) reachable as \(\omega \sim_a \omega^{(1)} \sim_b \omega^{(2)}\) lies in \(E\); and so on up the ladder from the top of this page. Each extra rung appends one hop, so the whole ladder is \(\approx\).

An event belongs to the common ground when it is a union of Aulia’s fibres and a union of Bayu’s, which is to say when it is \(\approx\)-closed. The blocks of the common ground are therefore the \(\approx\)-classes, and \(E\) is commonly known at \(\omega\) exactly when the whole \(\approx\)-class of \(\omega\) lies inside \(E\). In the four-bit world two hops already reach every state agreeing with the original on \(\omega_2\) alone, so the classes are the level sets of \(\omega_2\) and the common ground is \(\sigma(\omega_2)\), the single bit they both read. With finitely many fibres the chain stabilizes after finitely many hops; in general it need not stabilize at any finite stage. Conditioning a random variable alternately on \(\mathscr{G}_a\) and on \(\mathscr{G}_b\) converges to conditioning on the common ground, but only in the limit, and as slowly as one likes (Burkholder and Chow 1961). Strictly, that limit is the common ground modulo \(P\)-null sets, which is a different algebra; the gap between the two is the subject of the rest of this section. Hopping is how Aumann (1976) gets the “I know that you know that I know” regress to terminate in an object one can compute with — provided each agent knows how the other partitions the world, and knows that the other knows this, and so on up. That last proviso is a real assumption and we have been leaning on it silently. Nothing in the setup grants it: \(\pi_a\) has domain \(\Omega\), which is precisely what Bayu has no vocabulary for.

Worse still, the common ground is not determined by \(P\) at all, so no experiment converges to it either. Perturb a sensor on a set of probability zero and the join changes only by null sets, while the common ground can jump from one extreme to the other. Take \(\Omega = [0,1]\) under the uniform law, fix an event \(B\) with \(0 < P(B) < 1\) and \(1/2 \notin B\), and let Aulia’s sensor report whether \(\omega \in B\) while Bayu’s reports whether \(\omega \in B \cup \{1/2\}\) — a disagreement at one point, of probability zero. Aulia can express \(B\) and its complement, and beyond those only \(\emptyset\) and \(\Omega\); Bayu likewise for \(B \cup \{1/2\}\); and those two lists share nothing but the trivial events, so the common ground is \(\{\emptyset, \Omega\}\). Grant both agents every null event as well, which no measurement could object to, and they become the same agent, with a common ground holding everything Aulia could say.

The common ground, then, is a fact about which points \(\pi_a\) and \(\pi_b\) happen to separate, and \(P\) does not see points. The two sensors in that example agree except at one point of probability zero: no experiment can tell them apart, and no bet either agent places can turn on the difference. Yet across that same difference the question what do these two commonly know? takes two opposite answers — no shared event but the trivial one, or every event Aulia can express. Nothing observable picks between them, so the strict intersection \(\mathscr{G}_a \cap \mathscr{G}_b\) is the wrong object to identify with common knowledge, at least if we want common knowledge to show up in what agents do. The repair is to work modulo \(P\)-null sets: sensors that agree almost everywhere count as the same sensor, and the common ground is the intersection of what remains. This is also what the alternating conditioning was computing all along, since a projection cannot see a null set either. In the example just given the iterates never move, since Aulia’s and Bayu’s indicators are the same element of \(L^2\), while the strict intersection predicts they should collapse to a constant. Almost-everywhere equality is the finest distinction any experiment — or any wager between the two of them — could draw anyway.

2.2 The poll and the open secret

Two agents and four bits is a long way from a newsroom, but only the two-agent bookkeeping needs changing. With \(n\) agents, \(\approx\) is the transitive closure of \(\bigcup_i \sim_i\), and the two readings are as before: \(E\) is shared knowledge at \(\omega\) when every \(\omega' \sim_i \omega\) lies in \(E\) for each \(i\), and common knowledge when the whole \(\approx\)-class of \(\omega\) does. More agents put more relations into that union, making \(\approx\) coarser and the class that has to fit inside \(E\) larger. Common knowledge is harder to come by in a crowd.

For decades the insiders’ \(\sim_i\)-classes at the actual state lay inside “Weinstein is an abuser”, and stayed inside it for the first few hops. Longer chains did not: they ran out through states in which one insider could not rule out that another had heard nothing, and on into states where there was nothing to hear. Shared knowledge to many depths, then, and common knowledge not at all. The Times piece moved few of those \(\sim_i\)-classes; what it did was cut the chains, which is a different achievement from informing anybody.

The poll is the same move with the mechanism easier to see, and it shows what the setup above still lacks. Telling every voter privately that 70% oppose shrinks each \(\sim_i\) exactly as publication does. So on an \(\Omega\) whose states record only who-thinks-what, the two are the same intervention, and \(\approx\) cannot tell them apart. Give \(\Omega\) states that record who-was-told and the difference appears where it should, in the hops. After a private round each voter still has \(\sim_i\)-neighbours in which some other voter was left out, and the chain escapes through those. An announcement everyone watches lands inside every \(\sim_i\)-class at once, and leaves the chain nowhere to go.