A game theoretic analysis of the cops and robber game

Georgios Konstantinidis

doi:10.3934/jdg.2014.1.599

Article Contents

2014, Volume 1, Issue 4: 599-619. Doi: 10.3934/jdg.2014.1.599

This issue Previous Article Investment under uncertainty, competition and regulation Next Article Payoff performance of fictitious play

A game theoretic analysis of the cops and robber game

Georgios Konstantinidis^1,

1.
Department of Electrical and Computer Eng, Aristotle University, Thessaloniki

Received: June 2014

Revised: September 2014

Published: October 2014

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 91A24, 91A43; Secondary: 05C57, 91A18.

Citation:

Related Papers

Cited by

References

[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.