Reasoning under uncertainty in the game of Cops and Robbers

Dazhu Li, Sujata Ghosh, Fenrong LiuarXiv 2025 · DOI · arXiv

Abstract

This paper introduces the Epistemic Logic of Cops and Robbers (ELCR), a formal framework designed to model pursuit-evasion games where players have limited visibility. By incorporating "k-sight" (the ability to see an opponent within a certain graph distance), the authors provide a decidable logic that can automatically track how players update their knowledge and infer an opponent's location through reasoning, even when they are out of sight. The framework offers a more succinct alternative to standard Dynamic Epistemic Logic for turn-based movement on graphs.

Introduction

The classic game of Cops and Robbers is a staple of graph theory and computer science, typically used to study pursuit-evasion strategies. However, most existing models assume perfect information: the cop always knows exactly where the robber is, and vice versa.

In real-world scenarios—like robotic search missions or adversarial search—information is rarely perfect. While some logicians have explored "Hide and Seek" variants, these models often struggle with computational complexity or fail to capture the specific "turn-based movement" dynamics of Cops and Robbers. The authors identify a gap: we need a formal way to reason about how players use partial observations and the underlying graph structure to "narrow down" where their opponent must be.

Methodology

The authors develop a specialized logic called ELCR, which models the game using several key components:

  • k-sight Models: A semantic structure where players' observational power is defined by a distance $k$. If an opponent is within $k$ steps on the graph, their position is known; otherwise, the player must rely on inference.
  • Epistemic Operators: The logic includes operators for "knowing the value" of a position ($K_z t$) and "knowing a fact" ($K_z \phi$).
  • Dynamic Update Operators: The core innovation is the $[z]\phi$ operator, which models what becomes true after a player moves. Unlike standard Dynamic Epistemic Logic (DEL), which often uses complex "product updates" that can lead to a blow-up of possible states, ELCR uses a more succinct update mechanism tailored to graph movement.
Figure 1: A 6-node directed graph used to illustrate game dynamics and player positions.

The paper relies on mathematical proofs and illustrative examples, such as the 6-node directed graph shown in Figure 1, to demonstrate how knowledge evolves over turns based on the graph's topology.

Key Insights and Results

A major contribution of the paper is demonstrating that a player can "know" an opponent's location without seeing them. By knowing where the opponent was and which vertices are reachable, a player can use the process of elimination to pinpoint a target.

Figure 2: An epistemic state model representing the possible configurations and transitions within the game.

The authors compare their approach to the standard DEL "product update" method. They argue that ELCR is more efficient for this domain because it filters out "irrelevant situations," focusing only on the possible positions consistent with the game's rules and the players' sight. Figure 2 visualizes these epistemic states and the transitions between them as knowledge is updated.

Significant theoretical results include:

  • The ELCR Calculus: The paper defines a complete set of axioms (like k-sight and Structure-Knowledge) that govern how information flows.
  • Winning Conditions as Formulas: Winning the game (the Cop knowing the Robber's exact position within $n$ rounds) can be expressed as a single formula in ELCR.
  • Decidability and Complexity: ELCR is decidable, and its static fragment (ELCR-) has a P-complete model-checking problem, providing a baseline for computational efficiency.

Conclusion and Future Work

ELCR provides a robust foundation for reasoning in pursuit-evasion under uncertainty. However, the current version does not handle "higher-order" reasoning (e.g., "The Cop knows that the Robber knows..."). Future work will explore these complexities, as well as "bounded memory" for more realistic robotic agents, multi-player scenarios, and probabilistic movement in stochastic games.

Summary updated

BibTeX
@misc{li2025reasoning,
  author = {Dazhu Li and Sujata Ghosh and Fenrong Liu},
  title = {{Reasoning under uncertainty in the game of Cops and Robbers}},
  year = {2025},
  eprint = {2508.00004},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.00004},
}
Figure