Simultaneously moving cops and robbers

DOI10.1016/J.TCS.2016.06.039zbMATH Open1349.05236arXiv1506.03613OpenAlexW2962760065MaRDI QIDQ306253FDOQ306253

Ath. Kehagias, G. Konstantinidis

Publication date: 31 August 2016

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

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.

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

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

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)

Cites Work

• Stochastic Games
• Title not available (Why is that?)
• Infinite Games
• Vertex-to-vertex pursuit in a graph
• Some remarks on cops and drunk robbers
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Title not available (Why is that?)
• Concurrent reachability games
• Simultaneously moving cops and robbers
• Infinite Coordination Games
• Cops and invisible robbers: the cost of drunkenness
• Existence of Value and Randomized Strategies in Zero-Sum Discrete-Time Stochastic Dynamic Games
• Characterizations and algorithms for generalized Cops and Robbers games
• Cop-win graphs with maximum capture-time

Cited In (13)

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

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)