Epistemic Logic of Know-Who

Sophia Epstein, Pavel NaumovAAAI 2021 · DOI

Abstract

Traditional epistemic logics excel at modeling "knowing that" ($K\phi$) but often struggle to capture the nuances of "knowing who" ($W\phi$). This paper introduces a propositional framework based on Grove-Halpern semantics that treats identification as a standalone modal operator. By incorporating "name spaces," the authors provide a sound and complete system for reasoning about identity across different contexts, such as legal names, pseudonyms, or biometric identifiers.

Introduction

In fields ranging from artificial intelligence to cybersecurity, identifying an entity is rarely a simple binary state. One might know a user's IP address without knowing their legal identity, or a detective might know that a specific individual dubbed the "Night Stalker" committed a series of crimes without knowing the person's actual name. Standard epistemic logic typically handles these scenarios using first-order logic with quantifiers (e.g., $\exists x K(x = \text{killer})$), but this approach is often computationally expensive and complex.

The "Night Stalker" example: In state $s_1$, the name "Night Stalker" refers to individual $d$, while in $s_2$ it refers to $e$. If an agent considers both states possible, they know *that* the Night Stalker is the murderer ($p$) but do not *know who* the murderer is.

The authors address this by proposing a propositional framework where "know-who" is a primary modality. This allows for efficient reasoning about identification relative to specific "name spaces"—mechanisms like social security numbers or fingerprints that map names to individuals.

Formal Framework and Semantics

The logic is built upon Grove-Halpern semantics, an extension of Kripke models that accounts for agent presence and identification mechanisms. A model in this system includes:

  1. Presence: Agents are not necessarily present in every possible state.
  2. Identification ($I$): A mapping that determines how a name $n$ from a name space $N$ refers to an agent in a given state, from the perspective of another agent.
  3. Relative Interpretation: Propositions are evaluated relative to an agent. For instance, $(a, s) \Vdash p$ indicates that agent $a$ satisfies property $p$ in state $s$.

The central contribution is the $W\phi$ modality. An agent $a$ "knows who" satisfies $\phi$ if there exists a name $n$ such that, in all states $a$ considers possible, $n$ consistently refers to an agent who satisfies $\phi$.

A semantic model illustrating the interaction between knowledge ($K$), universality ($A$), and the know-who operator ($W$). At state $u$, the agent knows who satisfies $p$ ($Wp$) because the identification remains consistent across accessible states.

Axiomatization of Identity

The paper identifies several key axioms that govern the behavior of the $W$ operator:

  • Know-Nobody ($A\neg\phi \to \neg W\phi$): If no agent satisfies $\phi$ universally, one cannot know who satisfies $\phi$.
  • Know-All ($KA(\phi \to \psi) \to (W\phi \to W\psi)$): If it is known that every $\phi$ is a $\psi$, then knowing who the $\phi$ is implies knowing who the $\psi$ is.
  • Introspection ($W\phi \to KW\phi$): Agents have meta-knowledge of their own identification capabilities; if they know who someone is, they know that they know.

By avoiding explicit quantifiers, the logic remains closer to propositional logic, enhancing its potential for decidability and automated reasoning.

Technical Results

The primary technical achievement is the proof of soundness and completeness for the proposed set of six axioms within Grove-Halpern semantics. To prove completeness, the authors developed a novel tree construction for the canonical model. This technique ensures that every agent-state pair corresponds to at most one "view" (a maximal consistent set), satisfying the structural requirements of the semantics. Furthermore, the authors suggest that the system is likely decidable via standard filtration techniques, making it a viable candidate for algorithmic verification in multi-agent systems.

Conclusion and Future Directions

While the current framework provides a robust foundation, it is limited to a single, fixed name space. Future work involves extending the logic to support multiple name spaces ($W_\eta$) to model scenarios where agents link different identities (e.g., connecting a pseudonym to a credit card). Additionally, the authors aim to explore group "know-who" logic and explicit naming modalities ($@_n \phi$) to reason directly about specific identifiers.

Summary updated

BibTeX
@inproceedings{epstein2021epistemic,
  author = {Sophia Epstein and Pavel Naumov},
  title = {{Epistemic Logic of Know-Who}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17367},
}
Figure