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

DOI10.1007/S13235-018-0288-0MaRDI QIDQ2292118zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 3 February 2020

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

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

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)

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.

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

Cites work

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

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)