Converging on Common Knowledge

1 Introduction

The concept of common knowledge is ubiquitous in contexts of informationally driven rational agents, whether in philosophy, economics or computer science. Though common knowledge is not a requirement for all rational interaction [Aumann and Brandenburger, 2016], it is a prerequisite for coordination in a plethora of contexts, including social life [Lewis, 1969], game theory [Morris and Shin, 1997; Rubinstein, 1989] and distributed systems [Fagin et al., 1995].

However, as shown by Halpern and Moses [1990], in systems where message passing may fail, attaining common knowledge is impossible. The trouble is exemplified by the coordinated attack problem:

Two allied generals desire to overrun a besieged township. Any unilateral attack will certainly fail, but a simultaneous attack is guaranteed victorious. The generals can only communicate by courier, who may face peril on route, and thus fail to deliver its message. Can the generals ensure victory?

Already Akkoyunlu et al. [1975] show that even when the courier is always successful, no finite number of messages will suffice to establish an agreement to attack: If n ≥ 1 is the least number of messages that suffice, loss of the nth message results in non-agreement. Hence the delivery of the nth message must be acknowledge before its sender is certain agreement is reached. For this, an n+1st message is required, contradicting the assumption. See also [Gray, 1978; Yemini and Cohen, 1979].

Hapern and Moses [1990] show that no correct protocol can ensure victory through a formal representation of the involved higher-order reasoning using interpreted systems. 1 They link the coordinated attack problem and common knowledge by showing that

Prop. 4:

common knowledge to attack is a prerequisite for coordinated attack, and

Thm. 5: when communication is unreliable, it is impossible to attain common knowledge, and hence

Cor. 6:

the generals will never attack.

The content of Thm. 5 nowadays enjoys slogan-like status in multi-agent dynamics. The result is a hallmark of epistemic logic and the coordinated attack problem has become a stable showcase for formal systems of epistemic dynamics.

Yet, the generals' epistemic dynamics exhibit a tendency towards common knowledge. Since common knowledge is characterizable as having all levels of mutual knowledge, and each successful message delivery yields a raise in the level of mutual knowledge of agreement, we face the following

Question: If the generals may communicate indefinitely, will they then converge to a state of common knowledge?

"Yes" may seem a tempting answer: keep adding 1 for long enough and you will reach the first infinity and thus common knowledge. This paper argues that this intuition is both correct and not.

The paper discusses unreliable communication protocols from a topological perspective, focusing on the coordinated attack problem. We cast the analysis in a mathematically expressive framework where convergent sequences and limit points are natural inhabitants, allowing us to show when and how unreliable communication converges to a state of common knowledge. Jumping ahead, we show that common knowledge is attainable if, and only if, we do not care about common knowledge. This statement is made precise by the framework of the paper, where caring about common knowledge means that it is expressible in the formal logical language. Section 2 models the coordinated attack problem using dynamic epistemic logic (DEL). Section 3 introduces a notion of convergence and argues its intuitiveness. Section 4 contains results and Section 5 concludes.

1 Common knowledge is also unattainable when messages are delivered reliably, but with unbounded delivery time [Halpern and Moses, 1990], under asynchronous message-passing [Fagin et al., 1995] and in systems with temporal imprecision (ibid.). Dimitri [2003], however, identifies variation in the communication structure, that allow to approximate common knowledge.

2 Coordinated Attack Problem in DEL

A DEL model typically consists of a sequence of small models, each representing a snapshot of the factual and higherorder information of all agents at a given moment in time. All but the first of these is the result of updating its predecessor with a non-guaranteed communication event. The dynamic model may thus be seen as an evolution

Each snapshot model xk is self-contained and each ek is an operation on xk transforming it into xk+1. Each snapshot model xk is a multi-agent epistemic state-a pointed Kripke model-and each ek is an epistemic event, modeled e.g. using an action model, see e.g [Baltag and Renne, 2016; van Benthem, 2011; van Ditmarsch et al., 2008]. Details follow.

For generality, we do not define our model directly as an evolution, but as a composition of two maps. The first takes an epistemic state x as input and outputs a message to be send; the second takes the epistemic state and the selected message as input and outputs an updated epistemic state. The composition of these two functions then maps epistemic states to (updated) epistemic states. A run of the model on an initial state is then obtained by re-applying the map to its own output indefinitely.

To simplify, we will be concerned only with whether the generals attain common knowledge of a given target proposition (working with a single atom is for simplicity only; see Section 5). We thus omit modeling any attacks or lack thereof, implicitly taking such events to be synonymous with attaining common knowledge of the target proposition.

2.1 Languages and Epistemic States

We make use of two languages to describe epistemic states, both defined for two agents, a and b, and a single atom p, representing the target proposition. Our main concern thus is whether a and b can attain common knowledge that p.

Let the language LC be given by

Let L ⊆ LC be the sub-language of formulas with no occurrences of the common knowledge operator, C.

As semantics for L and LC, we use a special case of pointed Kripke models: an epistemic state for LC is a pair (M, s) with M = (S, ∼a, ∼b, V (p)) where S is a non-empty set of states, ∼i is an equivalence relation on S for i ∈ {a, b} and V (p) ⊆ S is the valuation of the atom p; finally, s ∈ S is the actual state. For an epistemic state (M, s), write Ms. Let G be (a set representation of) the class of all epistemic states.

With ∼ the transitive closure of ∼a ∪ ∼b, the language LC is evaluated over epistemic states using standard clauses. We only mention those for the modalities:

Figure 1: The generals' initial epistemic state for coordinated attack, g1. The model has two states, s and t, with the double lining indicating s as actual state. In s, general a knows p, but general b does not: g1 |=Kap ∧¬Kbp.

The epistemic state of the two generals prior to any communication is illustrated in Figure 1.

2.2 Messages and Acknowledgments

Beyond the first, messages passed between the generals acknowledge receipt of the previous message. The content of the acknowledgments can be encoded either using atomic propositions or epistemic formulas. We choose the latter for simplicity.

Using epistemic formulas, the messages may be given a simple recursive build, suitable irrespective of which general knows the target proposition p. To exemplify, let first general a communicate knowledge of p with the message Kap. Call it ma1, as it is send by a as first message. If the message is received, this informs b that p. To acknowledge delivery, b returns a second message mb2 := Kbma1 = KbKap. As b will know Kap only in the case ma1 is delivered, mb2 captures acknowledgment of receipt of ma1. In turn, a may acknowledge receipt of mb2 by replying with ma3 := Kamb2 = KaKbKap, etc. The messages may be given recursively by ma1 := Kap, mb1 := Kbp and mak := Kambk-1, mbk := Kbmak-1. By the set of messages, we then refer to M := {mik : i ∈ {a, b}, k ∈ N}.

2.3 Communication Protocol

We focus on a simple alternating communication protocol akin to that described in the cited literature. The below map takes an epistemic state as input and returns a message. The message returned describes the highest level of higher-order knowledge that p, corresponding to an acknowledgment of the previous message. When both know p or in case of a 'higher-order tie', i.e., when the agents have n levels of mutual knowledge that p without either general knowing this, we take the liberty of letting only general a send a message. A protocol for all epistemic states where either general knows p is captured by the following message selection map µ : G -→M∪ {⊤}:

Define a total lexicographic order ⪯ on M by mik ⪯ mjk′ iff k < k′ , or k = k′ and i = b, j = a. For all x ∈ G let

No m ∈ M is redundant: for each, there is an x ∈ G such that µ(x) = m. For x ⊨ Kap ∧ ¬Kbp, µ(x) = Kap = ma1, while for y ⊨ Kbp ∧ ¬Kap, µ(y) = Kbp = mb1. In general, for x ∈ G such that x ⊨ ma,k ∧¬mb,k, the message picked is µ(x) = ma,k. Symmetrically, for y with y ⊨ mb,k ∧ ¬ma,k, µ(y) = mb,k.

2.4 Unreliable Message Passing

Beyond deciding on the content of the messages, we must also model the epistemic circumstances of delivery. In particular, the sending agent should consider it possible that the message is not delivered. To model unreliable communication acts, we use a form of semi-private announcements, illustrated in Figure 2.

Define for i, j ∈ {a, b}, i ̸= j and ϕ ∈ LC, the unreliable communication that ϕ from i to j as the tuple

with a 'success event' s and a 'failure event' f, relations ≈i = {s, f}2 , ≈j = {(s, s), (f, f)} and preconditions pre(s) = ϕ, pre(f) = ⊤.

To capture the effect of an unreliable communication on an epistemic state, we use product update: The product update of Ms with (i : ϕ) is the epistemic state Ms ⊗ (i : ϕ) defined by

with states S′ = {(t, t) ∈ S ×{s, f}: Mt |= pre(t)}, relations (t, t) ∼′j (t′ , t′ ) iff t ∼j t′ and t ≈j t′ , for j ∈ {a, b}, valuation V ′ (p) = {(t, t) ∈ S′ : Mt ⊨ p}, and actual state s′ = (s, s).

The effect of updating the initial epistemic state x1 of Figure 1 with the unreliable communication of the first message (a: ma1) is depicted and described in Figure 3.

Remark. Semi-private announcements are special cases of pointed action models, introduced along with product updates by Baltag et al. [1998]; Baltag and Moss [2004]. For introductions, see e.g. [Baltag and Renne, 2016; van Benthem, 2011; van Ditmarsch et al., 2008]. Aucher et al. [2012] also use DEL semi-private announcements to model the coordinated attack problem. For alternative approaches, see e.g. [Fagin et al., 1995; Herzig et al., 2015].

2.5 The Dynamic Model

Finally, we define the map f : G -→ G representing the generals' unreliable communication. Given an epistemic state x, the map distinguishes three cases: i) the message selected by µ at x 'belongs' to a, ii) the message 'belongs' to b, or iii) the message of x is the empty message:

The map f is total on G, but only represents the communication protocol on the sub-domain where either agent knows p, i.e., the set of epistemic states [Kap ∨Kbp].

2.6 Running for Common Knowledge

Iteratively applying the map f to the initial epistemic state g1 produces an infinite, but neatly structured, sequence of epistemic states ¯ g := g1, g2, ... with gn+1 := f n (g1). The first elements of ¯ g are depicted in Figure 4.

The form of the update described in Figure 3 is symptomatic for all latter. The states of gn+1 may be divided in two: a single child of the actual state of gn and event s and a full copy of gn courtesy of f. The only link between the two components belongs to the general that sends the nth message: it links the two children of gn's actual state.

The sequence ¯ g = g1, g2, ... adheres to a recursive construction up to isomorphism: x1 = (S1,∼a1,∼b1, V1, s1) with S1 = {s1, t}, ∼a1= {(s, s), (t, t)}, ∼b1= {s, t}2 , and V1(p) = {s}, cf. Figure 1, and xk = (Sk,∼ak,∼bk, Vk, sk) with

The run ¯ g mirrors the aforementioned result by Halpern and Moses [1990]: common knowledge is not attained in finite time. For every n ∈ N, gn contains a child of the state t, and this child is not in Vn(p). Yet, it is reachable from the actual state of gn by the transitive closure of ∼an ∪ ∼bn. Hence

2.7 Approaching Common Knowledge

Though the generals at no time attain common knowledge, they are seemingly getting closer: with each trip of the courier, another level of higher-order knowledge that p is created, bringing the generals one step closer to common knowledge. To make things formal, define

Then for any epistemic state x, x ⊨ Cϕ iff x ⊨ Enϕ for all n ∈ N, cf. e.g. [Fagin et al., 1995]. For the generals' sequence of epistemic states, ¯ g = g1, g2, ..., it then holds true for all n ∈ N that

Hence, as n grows larger, the set of formulas that 'support' common-knowledge-that-p satisfied by gn grows, while the set of formulas contradicting common-knowledge-that-p satisfied by gn shrinks. Does this then mean that the generals attain common knowledge as n goes to infinity?

3 Logical Convergence and its Topology

To answer this question, it is natural to turn to the mathematical notions of convergence and limits. These notions, however, are relative to structure beyond only sequences of models. For an answer to the above question to be illuminating, also this additional structure must be natural.

The nowadays most common type of additional structure comes in the form of a metric, or perhaps it's more general cousin, a topology. Roughly, a metric is a distance-measure, specifying quantitatively how far any two points are apart. That is, a metric on a set X is a function

that satisfies the four natural requirements

1. positivity: d(x, y) ≥ 0,
2. identity: d(x, y) = 0 iff x = y,
3. symmetry: d(x, y) = d(y, x), and
4. the triangular inequality: d(x, z) ≤ d(x, y) +d(y, z).

A metric allows to define convergence. Formally, a sequence ¯x = x1, x2, · · · ∈ X of points converges to a point x in the metric space (X, d) iff for every real number ε > 0, there is a time N after which every point in ¯x is within ε distance of x:

The concept of convergence can also be defined in a more abstract setting: a topology is a conceptual abstraction, qualitatively specifying closeness in space. A set imbued with a metric is called a metric space, while a set with a topology is a topological space. Topological spaces are generalizations of metric spaces: every metric space gives rise to a topological space, but not vice versa. For present purposes, perhaps think of a topological space as obtained from a metric space by throwing away the real values on distances, remembering only which points are closer to some point than others. Formally, a topology on a set X is a collection of subsets of X, T ⊆ P(X), satisfying three abstract requirements:

1. The full and empty sets are in T : X ∈ T and ∅ ∈ T ;
2. T is closed under finite intersections: if Ui ∈ T for all i ∈ I and I is finite, then ⋂i∈I Ui ∈ T ;
3. T is closed under arbitrary unions: if Uj ∈ T for all j ∈ J, then ⋃j∈J Ui ∈ T .

Members of T ⊆ P(X) are called open sets of X, while the complement of an open set is called closed. The notion of convergence, finally, has a topological counterpart: a sequence ¯x = x1, x2, · · · ∈ X of points converges to a point x in the topological space (X, T ) iff for every U ∈ T with x ∈ U, there is a time N after which every point in ¯x is in U:

To obtain reasonable insights on the convergence of unreliable communication, it does not suffice to fix just any metric or topological space-the space must also capture our intuitions concerning distances between models. Else convergence results are without bite. Consider for example the sequence of reals

It is forever decreasing yet always positive, with each incremental point having a smaller difference with 0 than its predecessor: in one intuitive understanding of the reals, the sequence converges to 0. This is also true under the Euclidean metric de (for all x, y ∈ R, de(x, y) = |x - y|), but it is false under the discrete metric dd (for all x, y ∈ R, if x ̸= y, de(x, y) = 1, else 0). This illustrates the importance of choosing a natural notion of distance for results to be of interest: that 1/2, 1/4, 1/8, 1/16, . . . converges in (R, de) reflects a strong intuition concerning the nature of the reals, while the conclusion concerning (R, dd) seems merely obscure.

Our results pertain to a type of topology that we find highly intuitive. To argue its intuitiveness, we present it through an alternative approach to convergence, namely sequential convergence.

3.1 Sequential and Logical Convergence

In the most general formulation, a sequential convergence on a set X is a subset L of XN × X. When a sequence-element pair (σ, x) belongs to L, the sequence σ is said to sequentially converge to x in L. Three standard coherence axioms for a sequential convergence are i) that a constant sequence converges to its only value, ii) that all subsequences of a convergent sequence share its limit, and iii) that limits are unique. When L satisfies suitable coherence axioms, the sequential convergence in turn induces a topology, possibly with standard structural properties-like being Hausdorff. Friˇc [1997] presents the theory and a worthwhile historical review.

We find the following approach to convergence through sequential convergence highly intuitive: Given that one has chosen a formal language L that represents exactly the features of interest over some class of models, a natural sequential convergence may be defined. The intuition is that a sequence of models x1, x2, ... converges to the model x just in case the models in the sequence steadily become more like the model x. With the features of interest given by formulas of L, this means that the models x1, x2, ... move towards satisfying all the same formulas as x.

The corresponding convergence notion was introduced in [Klein and Rendsvig, 2017] under the label logical convergence. A general definition may be given as follows:

Definition 1. Let L be a language binarily interpreted over a set of models X by a satisfaction relation ⊨. A sequence x1, x2, ... = σ ∈ XN then L-converges to x ∈ X iff for every L-formula ϕ for which x ⊨ ϕ, there is N ∈ N such that xn ⊨ ϕ for all n ≥ N.

Logical convergence for the language L induces a sequential convergence: define LL to contain exactly the pairs (σ, x) ∈ XN × X such that

In the ensuing, specifically the sequential convergences of the languages L and LC will be of interest. We refer simply to L-convergence and LC-convergence.

3.2 Modal Spaces

In applying a logical convergence to a set of epistemic states X, an annoyance may surface: if the set X is not suitably filtered, limits need not be unique. This runs somewhat counter to intuitions: when a sequence σ logically converges to both x and y, this entails that x and y share all features of interest-hence, for all intents and purposes, the models are the same. Yet, x and y need not be set-theoretically identical, making limits non-unique.

There are several ways to restore the uniqueness of limits without interfering with the represented logical dynamics. We choose what we consider the simplest: quotients by logical equivalence. In parlance, we follow [Klein and Rendsvig, 2017] in referring to modal spaces:

Definition 2. Let L be a language binarily interpreted over a set of models X by a satisfaction relation ⊨. The modal space XL is the quotient of X under L-equivalence. I.e.,

With XL given, the truth set of ϕ ∈ L is [ϕ]L = {xL ∈ XL : ∀x ∈ xL, x ⊨ ϕ}.

As only the languages L and LC are used below, the subscripts of xL and [ϕ]L are omitted. This causes no confusion concerning x as XL = XLC for any X, nor for [ϕ] as [ϕ]L = [ϕ]LC for all ϕ ∈ L ⊆ LC and the subscript is clearly LC when ϕ contains common knowledge operators. Throughout, write x ⊨ ϕ for x ∈ [ϕ].

As every epistemic state x ∈ G is uniquely represented in G := GL = GLC , we again refer to the elements x ∈ G as epistemic states.

3.3 FromLogical Convergence to Topology

The study of convergence and limits is the hallmark of topology. Though sequential convergence-through logical convergence-may be useful in fixing intuitions, as analytical framework it has long been surpassed by general topology.

If one agrees that logical convergence captures a natural notion of convergence and further finds it reasonable to identify models under logical equivalence, then finding a topology which respects one's intuitions is straightforward. In fact, there is a unique topology which respects the intuition behind logical convergence-a unique topology for which logical convergence and topological convergence are equivalent:

Theorem 3 ([Klein and Rendsvig, 2018]). Let L ∈ {L, LC} and let T be a topology onXL. The following are equivalent:

1. A sequence x1, x2, ... of points from XL converges to x in the topological space (XL, T ) if, and only if, x1, x2, ... logically converges to x in XL.
2. T is the Stone topology TL on XL i.e. the topology whose open sets are exactly {[ϕ] ⊆ XL : ϕ ∈ L}.

Both logical convergence and the Stone topology are language relative, but for each language, there is a unique topology capturing its logical convergence. Importantly, while XL =XLC , it is not the case that TL and TLC are the same topologies. A similar observation about topologies on type spaces is made by Rubinstein [1989] in his seminal work on almost common knowledge. 2

4 Unreliable Communication in the Limit

In the modal space G, there is exactly one element that satisfies Cp. This is the point cp ∈ G containing the epistemic state cp ∈ G of Figure 5. Given Theorem 3, whether the generals attain common knowledge in the limit reduces to the question of whether the sequence ¯g converges to cp in the topological space (G, TLC ). As it happens, hope for common knowledge in the limit is futile:

Proposition 4. In (G, TLC ), the sequence ¯g does not converge.

Proof. For a contradiction, assume ¯g to converges to x in (G, TLC ). For every open neighborhood U of x, there must be an N ∈ N such that gn ∈ U for all n ≥ N. Both [Cp] and [¬Cp] are open in TLC . They partition G, so either x ∈ [Cp] or x ∈ [¬Cp]. If x is in [Cp], then [Cp] is an open neighborhood of x: but for no n ∈ N does gn ⊨ Cp, cf. Eq. 1, p. 4, so gn is not in [Cp]. The purported limit of ¯g can therefore not be in [Cp]. If x is in [¬Cp], then x ⊨ ¬Ek p for some k ∈ N. I.e., [¬Ek p] is an open neighborhood of x-but it does not contain gk+1, as gk+1 ⊨ Ek p cf. Eq. 2, p. 4. The purported limit of ¯g can therefore not be in [¬Cp] either. Hence ¯g does not converge in (G, TLC ).

2 Other topological approaches to belief and knowledge relate to the definition of common knowledge (e.g. [Lewis, 1969], see [Vanderschraaf and Sillari, 2014] for an overview) or to belief revision [Baltag et al., 2019]. These use topologies on the sets of worlds within a given model to define semantics for modal operators. In contrast, we assume standard Kripke semantics for modal operators and use topologies defined on a set of models to study convergence.

Proposition 4 may run counter to intuitions: while the generals in finite time attain any level of mutual higher-order knowledge that p, not even in the limit do they attain common knowledge. Topologically, the explanation is simple: the point cp is isolated in G and can therefore not be gradually approached. We return to this below.

Emphatically, this non-convergence is not a consequence of the epistemic states qua relational structures, but of how these are described by the formal language. Under exactly the same dynamics but omitting the common knowledge operator, all higher-order uncertainty that p is successfully eliminated:

Proposition 5. In (G, TL), the sequence ¯g converges to cp.

Proof. Every ϕ from L satisfied by cp is implied by some formula in {EN p: N ∈ N}. Thus, for every open neighborhood U ∈ TL of cp, [EN p] ⊆ U for some N ∈ N. Now, for all n ≥ N + 1, gn ⊨ EN p, cf. Eq. 2. I.e., gn ∈ [EN p] ⊆ U. Hence ¯g converges to cp.

Proposition 5 thus shows that omitting common knowledge syntactically lets the generals obtain it semantically.

Remark. For those who would prefer results concerning dynamics directly on the set of models G instead of on the modal space G, we remark that Proposition 4 implies that ¯ g also diverges in (G, TLC ). Proposition 5 only implies that if ¯ g converges in (G, TLC ), then its limit is some x ∈ cp.

4.1 Main Results

Propositions 4 and 5 apply to the specific run ¯g. Yet, similar conclusions may be drawn more generally for the dynamic model f. Our first main result generalizes the nonconvergence conclusion of Proposition 4 by showing that common knowledge, if attainable at all, must be reached in finite time:

Proposition 6. Let (xn)n∈N be any convergent sequence from (G, TLC ). If limn→∞(xn) ⊨ Cp, then there exists a k ∈ N such that xk ⊨ Cp.

Proof. By Theorem 3, (xn)n∈N converges topologically iff it converges logically. By Definition 1, limn→∞(xn) ⊨ Cp then implies that there is some k ∈ N such that xk ⊨ Cp.

Our second main result shows that the semantic attainment of common knowledge in Proposition 5 is not an artifact, but a robust consequence of the generals' communication protocol. When either general knows p, the protocol eliminates all uncertainty-semantically, the generals always converge to a state of common knowledge. To show this, encode the protocol f on the modal space G by the map f : G -→ G given by f(x) = y iff f(x) ∈ y, for all x ∈ G. This map is welldefined as product update preserves bisimulation and hence modal equivalence, cf. [Baltag and Moss, 2004]. We obtain:

The proof uses the following fixed point theorem:

Theorem 8 ([Edelstein, 1962]). Every map F on a compact metric space (X, d) for which d(F(x), F(y)) < d(x, y) for all x, y ∈ X, x ̸= y, has a unique fixed point in X.

Corollary 9. Let F, and (X, d) as in Theorem 8. Then for any x ∈ X, the sequence x, F(x), F 2 (x) . . . converges to the unique fix point of F .

Call a map satisfying the condition of Theorem 8 Edelstein contractive. The property is used as follows: Lemma 10 introduces a metric dE on G for which metric space (G, dE) is compact and has as metric topology TL. Lemma 11 shows the second-iterate f 2 of f Edelstein contractive in the subspace [Kap ∨ Kbp] ⊆ G with fixed point cp. By Corollary 9, for any x in X, the sequences x, f 2 (x), f 4 (x) . . . andf(x), f 3 (x), f 5 (x) . . . converge to cp. Hence also the sequence x, f(x), f 2 (x) . . . does, establishing Proposition 7.

Lemma 10. The function dE : G ×G-→R given by

is a metric on G. The metric space (G, dE) is compact and has metric topology TL. The same holds for the subspace ([Kap ∨ Kbp], dE).

Proof. By results of Klein and Rendsvig [2017]. In their terminology, the set D = {Ek p}k∈N is a finite representative descriptor, and with the weight function w(Enp) := 1 n+1 for all n, dE is obtained as a metric of their family of generalized Hamming distances. Hence dE has metric topology TL, which is compact on the modal space G as S5 is complete w.r.t. G. The same holds for the subspace [Kap ∨Kbp] as it is closed in TL.

Lemma 11. The second-iterate f 2 of f is Edelstein contractive in ([Kap ∨ Kbp], dE) and has fixed point cp.

Proof. Let x, y ∈ [Kap ∨ Kbp], x ̸= y. Then dE(x, y) = 1 n+1 for some n. I.e., both x and y satisfy Enp, but only one satisfies En+1 p. Yet, both f 2 (x) and f 2 (y) satisfy En+1 : Wlog, assume x ⊨ En+1 p and y ⊨ ¬En+1 p. Then f 2 (x) ⊨ En+1 p as f preserves satisfaction of Ek p, for all k. For f 2 (y), notice that y must satisfy either 1. KaEnp∧¬KbEnp, 2. KbEnp ∧ ¬KaEnp, or 3. ¬KbEnp ∧ ¬KaEnp. In the first case, µ(y) = KaEnp, so f(y) = y⊗(a : KaEnp) satisfies KbKaEnp, and hence KbEnp, so also En+1 p. Hence also f 2 (y) ⊨ En+1 p. The second case is symmetric. In the third case, µ(y) = KaEn-1p. Hence f(y) satisfies KbKaEn-1p, so also KbEnp-which is µ(f(y)). Then f 2 (y) ⊨ KaKbEnp, and hence f 2 (y) ⊨ En+1 p. As both f 2 (x) and f 2 (y) satisfy En+1 , dE(f 2 (x), f 2 (y)) = 1 n+2 < dE(x, y). Finally, cp is a fixed point as µ(cp) = ⊤.

5 Concluding Remarks

We have modeled and analyzed the coordinated attack problem as a showcase example for asymptotic behavior of long term, asynchronous message passing with uncertain success. The analysis provided employs dynamic epistemic logic in a topological setting. The analysis and our main results concern a highly simplified representation of unreliable communicating, with but two agents and a single atomic proposition. Not much hinges on this choice. Similar techniques work for more complex representations with additional agents and atomic propositions. Generalized results on unreliable communication are obtainable by working with more advanced modal spaces, quotienting out what is not communicated about. As dynamic epistemic logic is a very general framework, the showcased techniques apply also to other instances of long-term informational dynamics.

Our main results imply that the analysis of long-term semantic updates is highly dependent on our choice of language and the corresponding topology. For a language without common knowledge operator, unreliable communication will converge to a state of common knowledge, but the agents are unable to express it. If, however, the language contains a common knowledge operator, then unreliable communication does not converge. Assuming that our choice of language exactly reflects the features we are interested in, this can be put precisely in a slogan-like statement: common knowledge is attainable, if, and only if, we do not care about common knowledge.

Acknowledgements

The Center for Information and Bubble Studies is funded by the Carlsberg Foundation. Both authors were partially supported by the DFG-ANR joint project Collective Attitude Formation [RO 4548/8-1], DK also by the DFG-GAˇCR joint project From Shared Evidence to Group Attitudes [RO 4548/6-1] and by the NSFC project Logics of Information Flow in Social Networks [17ZDA026].