Article Contents
Article Contents

# A game theoretic analysis of the cops and robber game

• We provide a game theoretic framework for the game of cops and robbers. Within this framework we study certain assumptions which underlie the concepts of optimal strategies and capture time. We show rigorously that these assumptions are justified. Our results are based on the theory developed by C. Alos-Ferrer and K. Ritzberger on the existence of subgame perfect equilibria in extensive form games which are infinite and / or have infinite horizon.
Mathematics Subject Classification: Primary: 91A24, 91A43; Secondary: 05C57, 91A18.

 Citation:

•  [1] C. Alós-Ferrer and K. Ritzberger, Trees and decisions, Economic Theory, 25 (2005), 763-798.doi: 10.1007/s00199-004-0487-3. [2] ________, Trees and extensive forms, Journal of Economic Theory, 143 (2008), 216-250.doi: 10.1016/j.jet.2007.11.002. [3] ________, Characterizing existence of equilibrium for large extensive form games, (2012). [4] ________, Large extensive form games, Economic Theory, 52 (2013), 75-102.doi: 10.1007/s00199-011-0674-y. [5] F. V. Fomin and D. M. Thilikos, An annotated bibliography on guaranteed graph searching, Theoretical Computer Science, 399 (2008), 236-245.doi: 10.1016/j.tcs.2008.02.040. [6] G. Hahn and G. MacGillivray, A note on k-cop, l-robber games on graphs, Discrete mathematics, 306 (2006), 2492-2497.doi: 10.1016/j.disc.2005.12.038. [7] A. Kehagias and P. Prałat, Some remarks on cops and drunk robbers, Theoretical Computer Science, 463 (2012), 133-147.doi: 10.1016/j.tcs.2012.08.016. [8] Y. Khomskii, Unbeatable Strategies, 2013. [9] D. A. Martin, Borel determinacy, Annals of Mathematics, 102 (1975), 363-371.doi: 10.2307/1971035. [10] J. R. Munkres, Topology: A First Course, vol. 23, Prentice-Hall Englewood Cliffs, NJ, 1975. [11] J. Mycielski, Games with perfect information, Handbook of game theory with economic applications, 11 (1992), 41-70.doi: 10.1016/S1574-0005(05)80006-2. [12] R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics, 43 (1983), 235-239.doi: 10.1016/0012-365X(83)90160-7. [13] M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT press, 1994. [14] A. Quilliot, Jeux et pointes fixes sur les graphes, Ph.D. thesis, Ph. D. Dissertation, Université de Paris VI, 1978.