# converging_on_common_knowledge__5b5dbb8a.pdf

Converging on Common Knowledge

Dominik Klein1 and Rasmus Kræmmer Rendsvig2

1University of Bamberg and University of Bayreuth 2Center for Information and Bubble Studies, University of Copenhagen dominik.klein@uni-bayreuth.de, rasmus@hum.ku.dk

Common knowledge, as is well known, is not attainable in finite time by unreliable communication, thus hindering perfect coordination. Focusing on the coordinated attack problem modeled using dynamic epistemic logic, this paper discusses unreliable communication protocols from a topological perspective and asks If the generals may communicate indefinitely, will they then converge to a state of common knowledge? We answer by making precise and showing the following: common knowledge is attainable if, and only if, we do not care about 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

1Common 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.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

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.

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

x1 e1 7 x2 e2 7 x3 e3 7 x4 e4 7

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

ϕ := | p | ϕ | ϕ ϕ | Kaϕ | Kbϕ | Cϕ

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:

p p b a, b a, b s: t:

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.

Ms Kiϕ iff for all t, s i t implies Mt ϕ Ms Cϕ iff for all t, s t implies Mt ϕ 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 = Kb Kap. 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 = Ka Kb Kap, 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

µ(x) = max {m M : x m} if exists else 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.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

ϕ i a, b a, b s: f :

Figure 2: The unreliable communication (i: ϕ). General i successfully sends the message ϕ to general j, with i uncertain about the success. The double lined success event s represents that the message ϕ is delivered successfully. In the failure event f, the null information message is received by agent j: f represents that the courier did not arrive. The recipient j can tell which event occurred. Assuming that j knows the courier arrives within some fixed time or not at all, this simplistically, but faithfully, represents successful passing of unreliable messages.

p p p a b (s, s): (s, f): (t, f):

Figure 3: The update g2 := g1 (a: Kap) of the initial epistemic state x1 (Figure 1) with the first courier-send message. Reflexive loops are omitted. The update g2 may be divided in two: the state (s, s) as the sole child of the success event s and all the rest : a full copy of g1 with all states children of the failure event f. The two parts are connected by linking the two children of the actual state of g1 with an uncertainty relation of the message s author: the sender cannot tell whether b received ma1, i.e., the message that Kap, or . The update g2 satisfies Kbma1 and Ka Kbma1.

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

(i: ϕ) = ({s, f}, i, j, pre(s), pre(f))

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 Ms (i: ϕ) := M s = (S , a, b, V , s ) 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

p p p t f : s f : s s:

p p p p t ff: s ff: s sf : s ss:

p p p p p t fff : s fff : s sff: s ssf : s sss: g4 :

Figure 4: Epistemic states g1 g4. Reflexive loops are omitted together with commas and parentheses in state names.

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:

x (a : µ(x)) if µ(x) = mak for some k x (b : µ(x)) if µ(x) = mbk for some k x else

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

Sk = Sk 1 {sk},

ak= ak 1 {sk, sk 1}2 if k is odd, ak 1 {(sk, sk)} else

bk= bk 1 {sk, sk 1}2 if k is odd, bk 1 {(sk, sk)} else Vk(p) = Vk 1(p) {sk}.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

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 for all n N, gn Cp. (1)

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

E1ϕ := Kaϕ Kbϕ and Ek+1ϕ := E1Ekϕ

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

gn+1 Enp En+1p (2)

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 i. positivity: d(x, y) 0, ii. identity: d(x, y) = 0 iff x = y, iii. symmetry: d(x, y) = d(y, x), and iv. 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:

ε R>0, N N, n N, d(xn, 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 T i I Ui T ; 3. T is closed under arbitrary unions: if Uj T for all j J, then S 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:

U T : x U N N, n N, xn 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

(1/2n)n N = 1/2, 1/4, 1/8, 1/16, . . .

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.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

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

ϕ L : x ϕ N N n N, xn ϕ.

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.,

XL = {x L : x X} for x L = {y X : ϕ L, y ϕ iff x ϕ}.

With XL given, the truth set of ϕ L is [ϕ]L = {x L XL : x x L, x ϕ}. As only the languages L and LC are used below, the subscripts of x L 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 From Logical 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 on XL. 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

Figure 5: The epistemic state cp G where the generals have common knowledge that p.

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

2Other 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.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

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 Ekp for some k N. I.e., [ Ekp] is an open neighborhood of x but it does not contain gk+1, as gk+1 Ekp 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).

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 {ENp: N N}. Thus, for every open neighborhood U TL of cp, [ENp] U for some N N. Now, for all n N + 1, gn ENp, cf. Eq. 2. I.e., gn [ENp] 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: Proposition 7. For all x [Kap Kbp] G, limn f n(x) = cp in the topology TL. 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 d E on G for which metric space (G, d E) 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 d E : G G R given by

d E(x, y) =

0 if x Enp y Enp for all n 1 n+1 if n is the least integer such that not x Enp y Enp

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

Proof. By results of Klein and Rendsvig [2017]. In their terminology, the set D = {Ekp}k N is a finite representative descriptor, and with the weight function w(Enp) := 1 n+1 for all n, d E is obtained as a metric of their family of generalized Hamming distances. Hence d E 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], d E) and has fixed point cp.

Proof. Let x, y [Kap Kbp], x = y. Then d E(x, y) = 1 n+1 for some n. I.e., both x and y satisfy Enp, but only one satisfies En+1p. Yet, both f 2(x) and f 2(y) satisfy En+1: Wlog, assume x En+1p and y En+1p. Then f 2(x) En+1p as f preserves satisfaction of Ekp, for all k. For f 2(y), notice that y must satisfy either 1. Ka Enp Kb Enp, 2. Kb Enp Ka Enp, or 3. Kb Enp Ka Enp. In the first case, µ(y) = Ka Enp, so f(y) = y (a : Ka Enp) satisfies Kb Ka Enp, and hence Kb Enp, so also En+1p. Hence also f 2(y) En+1p. The second case is symmetric. In the third case, µ(y) = Ka En 1p. Hence f(y) satisfies Kb Ka En 1p, so also Kb Enp which is µ(f(y)). Then f 2(y) Ka Kb Enp, and hence f 2(y) En+1p. As both f 2(x) and f 2(y) satisfy En+1, d E(f 2(x), f 2(y)) = 1 n+2 < d E(x, y). Finally, cp is a fixed point as µ(cp) = .

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

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].

[Akkoyunlu et al., 1975] Eralp Abdurrahim Akkoyunlu, Kattamuri Ekanadham, and R. V. Huber. Some Constraints and Tradeoffs in the Design of Network Communications. In SOSP 75 Proceedings of the Fifth ACM Symposium on Operating Systems Principles, pages 67 74, 1975.

[Aucher et al., 2012] Guillaume Aucher, Bastien Maubert, and François Schwarzentruber. Generalized DELSequents. In Luis Fariñas del Cerro, Andreas Herzig, and Jérôme Mengin, editors, Logics in Artificial Intelligence, volume 7519 of Lecture Notes in Computer Science, pages 54 66. Springer, 2012.

[Aumann and Brandenburger, 2016] Robert J. Aumann and Adam Brandenburger. Epistemic Conditions for Nash Equilibrium. In Horacio Arlo-Costa, Vincent F. Hendricks, and Johan van Benthem, editors, Readings in Formal Epistemology, chapter 41. Springer, 2016.

[Baltag and Moss, 2004] Alexandru Baltag and Lawrence S. Moss. Logics for Epistemic Programs. Synthese, 139(2):165 224, 2004. [Baltag and Renne, 2016] Alexandru Baltag and Bryan Renne. Dynamic Epistemic Logic. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, 2016. [Baltag et al., 1998] Alexandru Baltag, Lawrence S. Moss, and Sławomir Solecki. The Logic of Public Announcements, Common Knowledge, and Private Suspicions (extended abstract). In TARK 98: Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge, pages 43 56. Morgan Kaufmann Publishers, 1998. [Baltag et al., 2019] Alexandru Baltag, Nick Bezhanishvili, Aybüke Özgün, and Sonja Smets. A Topological Approach to Full Belief. Journal of Philosophical Logic, 48(2):205 244, 2019. [van Benthem, 2011] Johan van Benthem. Logical Dynamics of Information and Interaction. Cambridge University Press, 2011. [Dimitri, 2003] Nicola Dimitri. Coordination in an Email Game Without Almost Common Knowledge . Journal of Logic, Language and Information, 12(1):1 11, 2003. [van Ditmarsch et al., 2008] Hans van Ditmarsch, Wiebe van der Hoek, and Barteld Kooi. Dynamic Epistemic Logic. Springer, 2008. [Edelstein, 1962] Michael Edelstein. On Fixed and Periodic Points under Contractive Mappings. Journal of the London Mathematical Society, 37:74 79, 1962. [Fagin et al., 1995] Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. Reasoning About Knowledge. The MIT Press, 1995. [Friˇc, 1997] Roman Friˇc. History of Sequential Convergence Spaces. In Charles E. Aull and Robert Lowen, editors, Handbook of the History of General Topology, volume 1, pages 343 355. Springer, 1997. [Gray, 1978] Jim Gray. Notes on Data Base Operating Systems. In Rudolf Bayer, Robert M. Graham, and Gerhard Seegmüller, editors, Operating Systems, volume 60 of Lecture Notes in Computer Science, pages 393 481. Springer, 1978. [Halpern and Moses, 1990] Joseph Y. Halpern and Yoram Moses. Knowledge and Common Knowledge in a Distributed Environment. Journal of the ACM, 37:549 587, 1990. [Herzig et al., 2015] Andreas Herzig, Emiliano Lorini, and Faustine Maffre. A Poor Man s Epistemic Logic Based on Propositional Assignment and Higher-Order Observation. In Wiebe van der Hoek, Wesley H. Holliday, and Wen-fang Wang, editors, Logic, Rationality, and Interaction, volume 9394 of Lecture Notes in Computer Science, pages 156 168. Springer, 2015. [Klein and Rendsvig, 2017] Dominik Klein and Rasmus K. Rendsvig. Convergence, Continuity and Recurrence in

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

Dynamic Epistemic Logic. In Alexandru Baltag, Jeremy Seligman, and Tomoyuki Yamada, editors, Logic, Rationality, and Interaction, volume 10455 of Lecture Notes in Computer Science, pages 108 122. Springer, 2017. [Klein and Rendsvig, 2018] Dominik Klein and Rasmus K. Rendsvig. Metrics for Formal Structures, with an Application to Kripke Models and their Dynamics. In Logical Dynamics and Dynamical Systems, pages 177 207. Lund University Press, 2018. [Lewis, 1969] David Lewis. Convention: A Philosophical Study. Harvard Univiersity Press, 1969. [Morris and Shin, 1997] Stephen Morris and Hyun Song Shin. Approximate Common Knowledge and Coordination: Recent Lessons from Game Theory. Journal of Logic, Language and Information, 6(2):171 190, 1997. [Rubinstein, 1989] Ariel Rubinstein. The Electronic Mail Game: Strategic Behavior under "Almost Common Knowledge". American Economic Review, 79:385 391, 1989. [Vanderschraaf and Sillari, 2014] Peter Vanderschraaf and Giacomo Sillari. Common Knowledge. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, 2014. [Yemini and Cohen, 1979] Yechiam Yemini and Danny Cohen. Some Issues in Distributed Processes Communication. In Proc. of the 1st International Conference on Distributed Computing Systems, pages 199 203, 1979.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)