Depth-bounded epistemic logic

Farid Arthaud, Martin C. RinardarXiv 2023 · DOI · arXiv

Abstract

Standard epistemic logics assume agents are logically omniscient, possessing infinite reasoning depth. This paper introduces Depth-Bounded Epistemic Logic (DBEL), a formal framework that incorporates an agent's modal depth—the number of nested "knows" operators they can process—as a first-class citizen. We define depth atoms to represent reasoning capacities and extend the system to Depth-bounded Public Announcement Logic (DPAL) using a world-duplication technique. Our results show that DBEL remains PSPACE-complete, and we provide formal bounds for reasoning depth in classic puzzles like the Muddy Children problem.

Introduction

In formal logic, agents are often treated as "logically omniscient" beings. Standard epistemic logics (like S5) assume that if an agent knows $A$, and $A$ implies $B$, they automatically know $B$. In reality, reasoning has a cost. While humans can easily grasp "I know it's raining," we struggle with deeper nested modalities like "I know that you know that she knows that I know it's raining."

This paper addresses the lack of a sound mathematical framework to model agents with finite reasoning capacities. Specifically, it focuses on modal depth—the number of nested "knows" operators an agent can track. The goal is to allow agents to reason about their own and others' cognitive limits and to handle information spread when agents have varying levels of "depth."

The DBEL Framework

The authors introduce DBEL, an extension of S5 logic that introduces depth atoms:

  • $E^d_a$: Agent $a$ has a reasoning depth of exactly $d$.
  • $P^d_a$: Agent $a$ has a reasoning depth of at least $d$.

In this system, for an agent to "know" a formula, the formula must be true in all possible worlds (the standard requirement), and the agent's current depth must be greater than or equal to the complexity (modal depth) of that formula. The axiomatization of this logic is detailed in Figure 1.

Axiomatization of Depth-Bounded Epistemic Logic (DBEL).

Key axioms like Depth deduction ($K_a \phi \to P_a^{d(\phi)}$) ensure that knowledge is constrained by the agent's depth capacity. The logic also modifies standard introspection to account for the depth required to reason about one's own knowledge.

Dynamic Epistemic Logic with Depth

The paper extends DBEL to DPAL (Depth-bounded Public Announcement Logic). To handle announcements, the authors use a "world duplication" technique. When a public announcement is made, the model creates two versions of every state: a "positive" one where the announcement was processed and a "negative" one where it wasn't.

Agents who are deep enough "move" to the positive state, while those who are too shallow remain uncertain between the two. This effectively models failures to perceive or process new information. This approach avoids common pitfalls in depth-bounded design:

  • Amnesia: Where agents "forget" everything if an announcement is too complex.
  • Knowledge Leakage: Where shallow agents accidentally learn facts from deeper agents by observing their behavior.

Key Results and Complexity

The authors prove that the satisfiability problem for DBEL is PSPACE-complete for two or more agents. This is a significant result, as it shows that adding depth constraints does not increase the computational complexity beyond that of standard S5 logic. However, model checking for DPAL is more intensive (EXPTIME and NP-hard) due to the exponential growth of the model size with each announcement.

To illustrate the logic, the authors analyze the Muddy Children problem. They prove that for $k$ muddy children to solve the puzzle, the key agent must have a reasoning depth of at least $k-1$ and know that they have that depth. This provides a formal mathematical proof for the intuition that the puzzle's difficulty scales with the number of participants.

Conclusion

DBEL provides a rigorous way to analyze resource-constrained reasoning. While the state-space explosion in DPAL presents a computational challenge, the framework successfully bridges the gap between ideal logic and realistic cognitive limits. Future work involves exploring more efficient model representations and extending the logic to handle private or semi-public communications.

Summary updated

BibTeX
@misc{arthaud2023depth,
  author = {Farid Arthaud and Martin C. Rinard},
  title = {{Depth-bounded epistemic logic}},
  year = {2023},
  eprint = {2305.08607},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.08607},
}
Figure