Simultaneously moving cops and robbers

DOI10.1016/J.TCS.2016.06.039MaRDI QIDQ306253zbMATHOpenAlexFDO

Authors G. Konstantinidis, Ath. Kehagias

Publication date 31 August 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.03613

zbMATH Keywords

game theorycops and robberspursuit evasion

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: In this paper we study the concurrent cops and robber (CCCR) game. CCCR follows the same rules as the classical, turn-based game, except for the fact that the players move simultaneously. The cops' goal is to capture the robber and the concurrent cop number of a graph is defined the minimum number of cops which guarantees capture. For the variant in which it it required to capture the robber in the shortest possible time, we let time to capture be the payoff function of CCCR; the (game theoretic) value of CCCR is the optimal capture time and (cop and robber) time optimal strategies are the ones which achieve the value. In this paper we prove the following. (1) For every graph G, the concurrent cop number is equal to the "classical" cop number. (2) For every graph G, CCCR has a value, the cops have an optimal strategy and, for every epsilon>0, the robber has an epsilon-optimal strategy.

Recommendations

• Cops and robber game without recharging
• A survey on the relationship between the game of cops and robbers and other game representations
• Cops and Robber game without recharging
• Bounds on the length of a game of cops and robbers
• Some game-theoretic remarks on two-player generalized cops and robbers games

Cites work

• scientific article; zbMATH DE number 6009880 (Why is no real title available?)
• A course in game theory.
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Characterizations and algorithms for generalized cops and robbers games
• Concurrent reachability games
• Cop-win graphs with maximum capture-time
• Cops and invisible robbers: the cost of drunkenness
• Existence of Value and Randomized Strategies in Zero-Sum Discrete-Time Stochastic Dynamic Games
• Infinite Games
• Infinite coordination games
• Simultaneously moving cops and robbers
• Some remarks on cops and drunk robbers
• Stochastic Games
• Vertex-to-vertex pursuit in a graph

Cited in

(13)

• Bounds for cops and robber pursuit
• Simultaneously moving cops and robbers
• Cops and robber game on infinite chessboard
• A survey on the relationship between the game of cops and robbers and other game representations
• Cops and an insightful robber
• Linear evasion differential game of one evader and several pursuers with integral constraints
• Chasing a drunk robber in many classes of graphs
• Selfish cops and active robber: multi-player pursuit evasion on graphs
• Some game-theoretic remarks on two-player generalized cops and robbers games
• Selfish cops and passive robber: qualitative games
• Police and robber game on infinite chessboard
• The role of quantum correlations in cop and robber game
• Some remarks on cops and drunk robbers

This page was built for publication: Simultaneously moving cops and robbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306253)