The cops and robber game is a well-studied model for investigating pursuit-evasion phenomena, among many others. Although many variants of this game have been studied in the literature, the epistemic assumptions underlying their game designs are often left implicit. In this work, we focus on the imperfect information version of the game and re-examine it from an epistemic perspective to explore the levels of player knowledge that are essential for playing the game. To facilitate our investigations on these knowledge levels, we discuss two kinds of strategies for the players, history-based and positional, and show what matters in this context. Our study eventually sheds light on the implicit assumptions prevalent in the existing literature in terms of player knowledge while playing the game, and provides a foundation for further studies on epistemically informed game structures.

Abstract In this article, we start with a two-player game that models communication under adverse circumstances in everyday life and study it from the perspective of a modal logic of graphs, where links can be deleted locally according to definitions available to the adversarial player. We first introduce a new language, semantics and some typical validities. We then formulate a new type of first-order translation for this modal logic and prove its correctness. Then, a novel notion of bisimulation is proposed that leads to a characterization theorem for the logic as a fragment of first-order logic, and a further investigation is made of its expressive power against hybrid modal languages. Next, we discuss how to axiomatize this logic of link deletion, using dynamic-epistemic logics as a contrast. Finally, we show that our new modal logic lacks both the tree model property and the finite model property and that its satisfiability problem is undecidable.