<p>The game of Cops and Robbers is an important model for studying computational queries in pursuit-evasion environments, among others. As recent logical explorations have shown, its structure exhibits appealing analogies with modal logic. In this paper, we enrich the game with a setting in which players may have imperfect information. We propose a new formal framework, Epistemic Logic of Cops and Robbers <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11229_2025_5165_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="53" /> </InlineMediaObject> <EquationSource Format="TEX">\((\mathsf{ELCR})\)</EquationSource> </InlineEquation>, to make the core notions of the game precise, for instance, players’ positions, observational power and inference. Applying <InlineEquation ID="IEq15877"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11229_2025_5165_Article_IEq15877.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathsf{ELCR}\)</EquationSource> </InlineEquation> to analyze the game, we obtain an automated way to track interactions between players and characterize their information updates during the game. The update mechanism is defined by a novel dynamic operator, and we compare it with some relevant paradigms from the game and logic perspectives. We study various properties of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11229_2025_5165_Article_IEq15877.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathsf{ELCR}\)</EquationSource> </InlineEquation> including axiomatization and decidability. To our knowledge, this is the first attempt to explore these games from a formal point of view where (partial) information available to players is taken into account.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reasoning under uncertainty in the game of Cops and Robbers

  • Dazhu Li,
  • Sujata Ghosh,
  • Fenrong Liu

摘要

The game of Cops and Robbers is an important model for studying computational queries in pursuit-evasion environments, among others. As recent logical explorations have shown, its structure exhibits appealing analogies with modal logic. In this paper, we enrich the game with a setting in which players may have imperfect information. We propose a new formal framework, Epistemic Logic of Cops and Robbers \((\mathsf{ELCR})\) , to make the core notions of the game precise, for instance, players’ positions, observational power and inference. Applying \(\mathsf{ELCR}\) to analyze the game, we obtain an automated way to track interactions between players and characterize their information updates during the game. The update mechanism is defined by a novel dynamic operator, and we compare it with some relevant paradigms from the game and logic perspectives. We study various properties of \(\mathsf{ELCR}\) including axiomatization and decidability. To our knowledge, this is the first attempt to explore these games from a formal point of view where (partial) information available to players is taken into account.