Similarities and Differences between the Game of Cops and Robbers and Pursuit Differential Games

This paper examines the conceptual and methodological parallels and divergences between two paradigms of pursuit-evasion: the discrete “cops and robbers” game on graphs and continuous-time pursuit differential games as developed by Isaacs [4]. We first review the foundations of differential games in Isaacs’ treatise, with emphasis on the Homicidal Chauffeur model and on geometric and integral constraints on the controls. We then trace the origins of the cops and robbers game as formulated by Quilliot [30] and Nowakowski-Winkler [28], highlighting graph dismantlability and its equivalence to cop-win graphs. Extensions to infinite graphs and to visibility graphs of polygons are surveyed, focusing on results by Lubiw et al. [40] and Bonato-Nowakowski [41]. We also discuss pursuit differential games described by infinite systems of first-order equations in Hilbert spaces (Ibragimov et al. [39, 50]) and games with integral constraints (Mai Umar et al. [48]), as well as Luckraz’s work [43] relating cops and robbers to extensive and stochastic games. We then introduce a common reachability framework for both paradigms: we characterize the cop’s winning region on a finite graph as the least fixed point of a controllable-predecessor operator, show that folding a dominated vertex delays capture by at most one round, and relate these sets to capture basins and discriminating kernels of differential games. Finally, we compare the two paradigms with respect to information, timing, speed constraints and computational complexity, and identify open problems.