October  2014, 1(4): 599-619. doi: 10.3934/jdg.2014.1.599

A game theoretic analysis of the cops and robber game

1. 

Department of Electrical and Computer Eng, Aristotle University, Thessaloniki, Greece

Received  June 2014 Revised  September 2014 Published  November 2014

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.
Citation: Georgios Konstantinidis. A game theoretic analysis of the cops and robber game. Journal of Dynamics & Games, 2014, 1 (4) : 599-619. doi: 10.3934/jdg.2014.1.599
References:
[1]

C. Alós-Ferrer and K. Ritzberger, Trees and decisions,, Economic Theory, 25 (2005), 763. doi: 10.1007/s00199-004-0487-3. Google Scholar

[2]

________, Trees and extensive forms,, Journal of Economic Theory, 143 (2008), 216. doi: 10.1016/j.jet.2007.11.002. Google Scholar

[3]

________, Characterizing existence of equilibrium for large extensive form games,, (2012)., (2012). Google Scholar

[4]

________, Large extensive form games,, Economic Theory, 52 (2013), 75. doi: 10.1007/s00199-011-0674-y. Google Scholar

[5]

F. V. Fomin and D. M. Thilikos, An annotated bibliography on guaranteed graph searching,, Theoretical Computer Science, 399 (2008), 236. doi: 10.1016/j.tcs.2008.02.040. Google Scholar

[6]

G. Hahn and G. MacGillivray, A note on k-cop, l-robber games on graphs,, Discrete mathematics, 306 (2006), 2492. doi: 10.1016/j.disc.2005.12.038. Google Scholar

[7]

A. Kehagias and P. Prałat, Some remarks on cops and drunk robbers,, Theoretical Computer Science, 463 (2012), 133. doi: 10.1016/j.tcs.2012.08.016. Google Scholar

[8]

Y. Khomskii, Unbeatable Strategies,, 2013., (). Google Scholar

[9]

D. A. Martin, Borel determinacy,, Annals of Mathematics, 102 (1975), 363. doi: 10.2307/1971035. Google Scholar

[10]

J. R. Munkres, Topology: A First Course,, vol. 23, (1975). Google Scholar

[11]

J. Mycielski, Games with perfect information,, Handbook of game theory with economic applications, 11 (1992), 41. doi: 10.1016/S1574-0005(05)80006-2. Google Scholar

[12]

R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph,, Discrete Mathematics, 43 (1983), 235. doi: 10.1016/0012-365X(83)90160-7. Google Scholar

[13]

M. J. Osborne and A. Rubinstein, A Course in Game Theory,, MIT press, (1994). Google Scholar

[14]

A. Quilliot, Jeux et pointes fixes sur les graphes,, Ph.D. thesis, (1978). Google Scholar

show all references

References:
[1]

C. Alós-Ferrer and K. Ritzberger, Trees and decisions,, Economic Theory, 25 (2005), 763. doi: 10.1007/s00199-004-0487-3. Google Scholar

[2]

________, Trees and extensive forms,, Journal of Economic Theory, 143 (2008), 216. doi: 10.1016/j.jet.2007.11.002. Google Scholar

[3]

________, Characterizing existence of equilibrium for large extensive form games,, (2012)., (2012). Google Scholar

[4]

________, Large extensive form games,, Economic Theory, 52 (2013), 75. doi: 10.1007/s00199-011-0674-y. Google Scholar

[5]

F. V. Fomin and D. M. Thilikos, An annotated bibliography on guaranteed graph searching,, Theoretical Computer Science, 399 (2008), 236. doi: 10.1016/j.tcs.2008.02.040. Google Scholar

[6]

G. Hahn and G. MacGillivray, A note on k-cop, l-robber games on graphs,, Discrete mathematics, 306 (2006), 2492. doi: 10.1016/j.disc.2005.12.038. Google Scholar

[7]

A. Kehagias and P. Prałat, Some remarks on cops and drunk robbers,, Theoretical Computer Science, 463 (2012), 133. doi: 10.1016/j.tcs.2012.08.016. Google Scholar

[8]

Y. Khomskii, Unbeatable Strategies,, 2013., (). Google Scholar

[9]

D. A. Martin, Borel determinacy,, Annals of Mathematics, 102 (1975), 363. doi: 10.2307/1971035. Google Scholar

[10]

J. R. Munkres, Topology: A First Course,, vol. 23, (1975). Google Scholar

[11]

J. Mycielski, Games with perfect information,, Handbook of game theory with economic applications, 11 (1992), 41. doi: 10.1016/S1574-0005(05)80006-2. Google Scholar

[12]

R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph,, Discrete Mathematics, 43 (1983), 235. doi: 10.1016/0012-365X(83)90160-7. Google Scholar

[13]

M. J. Osborne and A. Rubinstein, A Course in Game Theory,, MIT press, (1994). Google Scholar

[14]

A. Quilliot, Jeux et pointes fixes sur les graphes,, Ph.D. thesis, (1978). Google Scholar

[1]

Yannick Viossat. Game dynamics and Nash equilibria. Journal of Dynamics & Games, 2014, 1 (3) : 537-553. doi: 10.3934/jdg.2014.1.537

[2]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013

[3]

Astridh Boccabella, Roberto Natalini, Lorenzo Pareschi. On a continuous mixed strategies model for evolutionary game theory. Kinetic & Related Models, 2011, 4 (1) : 187-213. doi: 10.3934/krm.2011.4.187

[4]

Anna Lisa Amadori, Astridh Boccabella, Roberto Natalini. A hyperbolic model of spatial evolutionary game theory. Communications on Pure & Applied Analysis, 2012, 11 (3) : 981-1002. doi: 10.3934/cpaa.2012.11.981

[5]

William H. Sandholm. Local stability of strict equilibria under evolutionary game dynamics. Journal of Dynamics & Games, 2014, 1 (3) : 485-495. doi: 10.3934/jdg.2014.1.485

[6]

Jiahua Zhang, Shu-Cherng Fang, Yifan Xu, Ziteng Wang. A cooperative game with envy. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2049-2066. doi: 10.3934/jimo.2017031

[7]

Ying Ji, Shaojian Qu, Fuxing Chen. Environmental game modeling with uncertainties. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 989-1003. doi: 10.3934/dcdss.2019067

[8]

Tinggui Chen, Yanhui Jiang. Research on operating mechanism for creative products supply chain based on game theory. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1103-1112. doi: 10.3934/dcdss.2015.8.1103

[9]

Serap Ergün, Bariş Bülent Kırlar, Sırma Zeynep Alparslan Gök, Gerhard-Wilhelm Weber. An application of crypto cloud computing in social networks by cooperative game theory. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019036

[10]

Sheri M. Markose. Complex type 4 structure changing dynamics of digital agents: Nash equilibria of a game with arms race in innovations. Journal of Dynamics & Games, 2017, 4 (3) : 255-284. doi: 10.3934/jdg.2017015

[11]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[12]

Tao Li, Suresh P. Sethi. A review of dynamic Stackelberg game models. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 125-159. doi: 10.3934/dcdsb.2017007

[13]

Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Two-person knapsack game. Journal of Industrial & Management Optimization, 2010, 6 (4) : 847-860. doi: 10.3934/jimo.2010.6.847

[14]

Hyeng Keun Koo, Shanjian Tang, Zhou Yang. A Dynkin game under Knightian uncertainty. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5467-5498. doi: 10.3934/dcds.2015.35.5467

[15]

Valery Y. Glizer, Oleg Kelis. Singular infinite horizon zero-sum linear-quadratic differential game: Saddle-point equilibrium sequence. Numerical Algebra, Control & Optimization, 2017, 7 (1) : 1-20. doi: 10.3934/naco.2017001

[16]

Eunha Shim, Beth Kochin, Alison Galvani. Insights from epidemiological game theory into gender-specific vaccination against rubella. Mathematical Biosciences & Engineering, 2009, 6 (4) : 839-854. doi: 10.3934/mbe.2009.6.839

[17]

Hideo Deguchi. A reaction-diffusion system arising in game theory: existence of solutions and spatial dominance. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3891-3901. doi: 10.3934/dcdsb.2017200

[18]

Wai-Ki Ching, Sin-Man Choi, Min Huang. Optimal service capacity in a multiple-server queueing system: A game theory approach. Journal of Industrial & Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73

[19]

King-Yeung Lam. Dirac-concentrations in an integro-pde model from evolutionary game theory. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 737-754. doi: 10.3934/dcdsb.2018205

[20]

Pierre Cardaliaguet, Chloé Jimenez, Marc Quincampoix. Pure and Random strategies in differential game with incomplete informations. Journal of Dynamics & Games, 2014, 1 (3) : 363-375. doi: 10.3934/jdg.2014.1.363

 Impact Factor: 

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]