A Survey on the Relationship Between the Game of Cops and Robbers and Other Game Representations

Shravan Luckraz

Dynamic Games and Applications, 2019, vol. 9, issue 2, No 9, 506-520

Abstract: Abstract This paper surveys the similarities and differences between the game of cops and robbers and classes of related games. The game of cops and robbers is a class of pursuit–evasion games played on a finite graph. The players comprise a set of cops and a robber located on vertices of the graph, and they move alternately along edges of the graph. The cops win the game if at least one cop occupies the same vertex of the robber in finite time; otherwise, the robber wins. Quilliot (Jeux de points fixes sur les graphes, These de 3ieme Cycle, Universite de Paris VI, Paris, pp 131–145, 1978) and Nowakowski and Winkler (Discrete Math 43:235–239, 1983) were among the first to study this class of games. The main questions studied in the literature of cops and robbers games are on the class of graphs that characterize cop-win games, on the minimum number of cops needed for classes of graphs to be cop-win, on a conjecture due Meyniel (Personal communication, 1985) about the cop number of a graph and more recently on the game played on random and/or infinite graphs (Bonato and Nowakowski in The game of cops and robbers, Student mathematical library, vol 61, American Mathematical Society, Providence, 2010; Bonato and Pralat in Graph searching games and probabilistic methods, CRC Press, Boca Raton, 2017). While the game of cops and robbers is not traditionally modeled in the language of extensive game theory (Kuhn, in: Kuhn, Tucker (eds) Contributions to the theory of games II, Princeton University Press, Princeton, 1953), Kehagias et al. (The role of visibility in pursuit/evasion games, 2014) give a general framework for the game of cops and robbers that relate to extensive games. By using the notion of “capture time,” they are able to represent the game using a standard discrete dynamic game model with explicit payoff functions for the cops and the robber. More recently, the game of cops and robbers has also been related to dynamic games with state variables (Bonato and Macgillivray in Contrib Discrete Math, 2017) and discounted stochastic games (Konstantinidis and Kehagias in Selfish cops and adversarial robber: multi-player pursuit evasion on graphs, 2017a, arXiv:1703.07695 ; Theor Comput Sci 680:25–35, 2017b). In this survey, we study these connections.

Keywords: Pursuit–evasion; Graph theory; Cops and robbers (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s13235-018-0275-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:dyngam:v:9:y:2019:i:2:d:10.1007_s13235-018-0275-5

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/13235

DOI: 10.1007/s13235-018-0275-5

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

More articles in Dynamic Games and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().