Generalized cops and robbers: a multi-player pursuit game on graphs

DOI10.1007/S13235-018-0288-0zbMATH Open1431.91045arXiv1807.08500OpenAlexW2883617225MaRDI QIDQ2292118FDOQ2292118

Authors: Yanyan Li 

Publication date: 3 February 2020

Published in: Dynamic Games and Applications (Search for Journal in Brave)

Abstract: We introduce and study the Generalized Cops and Robbers game (GCR), an N-player pursuit game in graphs. The two-player version is essentially equivalent to the classic Cops and Robbers (CR) game. The three-player version can be understood as two CR games played simultaneously on the same graph; a player can be at the same time both pursuer and evader. The same is true for four or more players. We formulate GCR as a discounted stochastic game of perfect information and prove that, for three or more players, it has at least two Nash Equilibria: one in positional deterministic strategies and another in non-positional ones. We also study the capturing properties of GCR Nash Equilibria in connection to the cop-number of a graph. Finally, we briefly discuss GCR as a member of a wider family of multi-player graph pursuit games with rather interesting properties.

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

Recommendations

• The game of cops and robbers on graphs
• Selfish cops and active robber: multi-player pursuit evasion on graphs
• The game of Cops and Robber on circulant graphs
• Characterizations and algorithms for generalized cops and robbers games
• A game of cops and robbers on graphs with periodic edge-connectivity
• Cops and Robber game with a fast robber on expander graphs and random graphs
• A game of cops and robbers played on products of graphs
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• The game of cops and robbers on directed graphs with forbidden subgraphs
• Cops and Robbers on Dynamic Graphs: Offline and Online Case

zbMATH Keywords

cops and robberspursuit\(N\)-player game

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Stochastic games, stochastic differential games (91A15) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Perfect information stochastic games and related classes
• Nonzero-sum differential games
• Title not available (Why is that?)
• Algorithms for stochastic games ? A survey
• Title not available (Why is that?)
• Vertex-to-vertex pursuit in a graph
• The game of cops and robbers on graphs
• Title not available (Why is that?)
• Characterizations and algorithms for generalized cops and robbers games
• Multi-player pursuit-evasion games with one superior evader
• Computer Science Logic
• The structure of median graphs
• Selfish cops and passive robber: qualitative games
• A class of differential games with two pursuers versus one evader

Cited In (5)

• Selfish cops and active robber: multi-player pursuit evasion on graphs
• Some game-theoretic remarks on two-player generalized cops and robbers games
• A survey on the relationship between the game of cops and robbers and other game representations
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• Cops and Robber game with a fast robber on expander graphs and random graphs

This page was built for publication: Generalized cops and robbers: a multi-player pursuit game on graphs

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