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

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.