Introduction
In the field of artificial intelligence and formal verification, modeling the knowledge of agents is a fundamental challenge. Standard epistemic logic uses the operator $K$ to denote what an agent knows. However, a more nuanced requirement often arises: modeling "all that an agent knows," or only knowing ($O$). If an agent only knows $p$, they should logically conclude they do not know $q$. While this is intuitive for a single agent, extending this to multi-agent systems where common knowledge ($C$)—an infinite nesting of beliefs—exists has proven mathematically difficult.
The Limitation of Finite Structures
Previous attempts to formalize multi-agent "only knowing" relied on $k$-structures. These models are restricted to a fixed depth $k$ of nested beliefs. Because common knowledge is inherently infinite (I know that you know that I know... ad infinitum), $k$-structures are fundamentally incapable of representing it. This created a divide in epistemic logic: one could model "only knowing" or "common knowledge," but rarely both in a unified, rigorous way.
The $COL_n$ Framework
This paper introduces $COL_n$ (Common Knowledge + Only Knowing for $n$ agents), a new logic that bridges this gap. The authors move beyond finite structures by defining an epistemic state as an infinite sequence of structures.
To maintain logical coherence, the authors introduce the concept of i-compatibility. This requirement ensures that an agent's beliefs at any given level of the infinite sequence are consistent with the levels below it. Furthermore, $COL_n$ is a first-order logic framework. Unlike propositional models that only handle simple truth values, $COL_n$ supports quantification and equality, allowing agents to reason about objects and identities (e.g., "There exists an individual $x$ such that I know $x$ is the culprit").
The logic also incorporates a modality for public announcements ($[\phi]$). This allows the system to model dynamic epistemic progression: when a fact is publicly announced, the agents' epistemic states are updated simultaneously, transforming their "only knowing" status in response to the new information.
Theoretical Insights and the Muddy Children Puzzle
The integration of $O$ and $C$ leads to several profound logical insights:
- The Only Knowing Paradox: The authors prove that while "only knowing" implies "knowing" ($O_i \alpha \supset K_i \alpha$), it is impossible to have common knowledge of only knowing ($C O_i p$ is a contradiction). Common knowledge requires agents to have information about each other’s epistemic states, whereas "only knowing $p$" implies the agent knows nothing else—including the status of others' beliefs.
- Deductive Problem Solving: A classic benchmark for epistemic logic is the "Muddy Children" puzzle. Traditionally, this is solved via model checking (eliminating impossible worlds). This paper demonstrates that in $COL_n$, the puzzle can be solved through pure logical deduction. By starting from a state where children "only know" the mud on others and the father's public announcement, the solution—that all muddy children eventually know their status—emerges as a logical implication (Theorem 17).
- Compatibility: The authors show that $COL_n$ is a "well-behaved" extension of standard multi-agent epistemic logic ($KC45_n$). It preserves essential properties like positive and negative introspection: if an agent knows something, they know they know it; if they do not know something, they know they do not know it.
Conclusion and Future Work
The $COL_n$ framework provides a robust semantics for a first-order language combining knowledge, only knowing, and common knowledge. While it successfully solves long-standing puzzles and provides a rigorous foundation for multi-agent reasoning, challenges remain. Specifically, a complete first-order axiomatization—the set of rules for calculation—is notoriously difficult to achieve for "only knowing" logics. Additionally, because "only knowing" is non-monotonic (new information can invalidate previous "only knowing" conclusions), further research is needed to explore how this interacts with the infinite nature of common knowledge in more complex, evolving environments.
Summary updated