TL;DR
This paper investigates whether unreliable communication, even if ongoing indefinitely, can lead to common knowledge between two agents. Using dynamic epistemic logic and a topological framework, they show that common knowledge is only attainable if we don't care about it, meaning it's achievable precisely when the formal language used doesn't include a common knowledge operator.
What Problem Does This Paper Address?
The "coordinated attack problem" is a classic thought experiment illustrating the difficulty of achieving common knowledge. Imagine two generals who need to attack a town simultaneously to succeed, but their communication channels are unreliable (messages can be lost). If a general doesn't know that the other general knows, and knows that the other knows that they know, and so on, they can't be sure of coordinated action. This problem highlights that in systems with unreliable communication, achieving common knowledge – where everyone knows something, everyone knows that everyone knows it, and so on, infinitely – is impossible in finite time. The paper asks: if communication continues forever, does this problem resolve? Can agents eventually converge to a state of common knowledge, even with imperfect communication?
Methods
The authors employ Dynamic Epistemic Logic (DEL), a framework for modeling how agents' knowledge and beliefs change over time due to events like communication. They model the communication process as a sequence of "epistemic states," where each state represents the agents' current knowledge. Unreliable communication is modeled using semi-private announcements, which capture the uncertainty of message delivery.
A key methodological contribution is the use of a topological perspective. Instead of just looking at discrete steps, they analyze the convergence of epistemic states over time. This involves defining logical convergence (where states become increasingly similar in terms of what formulas they satisfy) and then relating it to topological convergence using modal spaces (quotients of epistemic states under logical equivalence) and the Stone topology. This allows them to rigorously ask if the sequence of epistemic states "approaches" a state of common knowledge.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Paradox of "Not Caring": The most striking insight is that common knowledge is attainable if and only if we don't care about it. This means that if the formal language used to describe the agents' knowledge lacks a common knowledge operator, then unreliable communication will converge to a state where common knowledge is semantically achieved. However, if the language includes the common knowledge operator, convergence to common knowledge is impossible, even in the limit.
- Topology as a Revealer: The topological framework is crucial. It reveals that while agents might get "closer" to common knowledge in a step-by-step sense (satisfying more and more levels of mutual knowledge), the specific state representing common knowledge is often an "isolated point" in the topological space of epistemic states. This means you can't gradually approach it through a sequence of imperfect communications.
- Finite vs. Infinite Time: The paper confirms the classic result that common knowledge is impossible in finite time with unreliable communication. However, it then explores the infinite time case, showing that while the sequence of states might not converge to a state of common knowledge in the formal sense (when the common knowledge operator is present), the semantic content of what is known can converge.
Key Results
- Non-Convergence to Common Knowledge: The sequence of epistemic states generated by the unreliable communication protocol does not converge to a state of common knowledge in the topological space when the common knowledge operator is part of the language. This is demonstrated by Proposition 4.
- Convergence Without the Common Knowledge Operator: If the common knowledge operator is omitted from the language, the sequence of epistemic states does converge to a state of common knowledge (Proposition 5). This highlights the language's role in defining what "convergence" means.
- Common Knowledge Must Be Reached in Finite Time (If At All): For any convergent sequence of epistemic states, if it converges to a state of common knowledge, then common knowledge must have been attained at some finite step (Proposition 6). This reinforces that the limit doesn't "create" common knowledge if it wasn't already there.
- Semantic Convergence of Knowledge: The communication protocol, when agents know p (the target proposition), semantically leads to a state of common knowledge, even if it's not formally expressible as such in the language (Proposition 7).
Limitations and Future Work
- Simplified Model: The analysis is based on a simplified model with only two agents and a single atomic proposition. The authors note that similar techniques can be extended to more complex scenarios with additional agents and propositions.
- Language Dependence: The results are highly dependent on the chosen formal language. Future work could explore how different language choices impact convergence.
- Specific Protocol: The paper focuses on a specific alternating communication protocol. Investigating other protocols and their convergence properties would be a natural extension.
- Expressibility vs. Attainability: A key takeaway is the distinction between semantic attainability of common knowledge (what is true in the state) and formal expressibility of common knowledge (whether it can be stated in the language). Future work could delve deeper into this tension.
Summary updated