Some Game-Theoretic Remarks on Two-Player Generalized Cops and Robbers Games
Tóm tắt
In this paper, we study the two-player generalized cops and robbers (GCR) games introduced by Bonato and MacGillivray. Our main goals are to provide: (a) a game-theoretic formulation of GCR and (b) a self-contained game-theoretic proof that GCR has a value and an optimal strategy profile. To achieve our goals, we first formulate GCR (and CR as a special case) as a zero-sum stochastic game. Then we study a Vertex Labeling (VL) algorithm and prove it computes the value of the GCR game (for every starting “condition”) and that the vertex labels can be used to specify a positional deterministic optimal strategy for each player. We also compare our game-theoretic analysis to some of the usual graph theoretic/combinatorial approaches to CR/GCR.
Tài liệu tham khảo
Apt KR, Grädel E (2011) Lectures in game theory for computer scientists. Cambridge University Press, Cambridge
Berarducci A, Intrigila B (1993) On the cop number of a graph. Adv Appl Math 14(4):389–403
Berwanger D (2013) “Graph games with perfect information.” Preprint
Bonato A, Nowakowski R (2011) The game of cops and robbers on graphs. American Mathematical Society, USA
Bonato A, MacGillivray G (2017) Characterizations and algorithms for generalized Cops and Robbers games. Contributions to Discrete Mathematics, vol.12
Chung TH, Hollinger GA, Isler V (2011) Search and pursuit-evasion in mobile robotics. Auton Robots 31:299–310
Filar J, Vrieze K (1996) Competitive Markov Decision Processes
Fomin FV, Thilikos DM (2008) An annotated bibliography on guaranteed graph searching. Theor Comput Sci 399(3):236–245
Hahn G, MacGillivray G (2006) A note on \(k\)-cop, \(l\)-robber games on graphs. Discret Math 306(19–20):2492–2497
Ibragimov G, Luckraz S (2017) On a characterization of evasion strategies for pursuit-evasion games on graphs. J Optim Theory Appl 175(2):590–596
Kehagias A, Konstantinidis G (2017) Selfish cops and passive robber: qualitative games. Theor Comput Sci 680:25–35
Kehagias A, Konstantinidis G (2019) Selfish cops and active robber: multi-player pursuit evasion on graphs. Theor Comput Sci 780:84–102
Kehagias A (2019) Generalized cops and robbers: a multi-player Pursuit game on graphs. Dyn Games Appl 9:1076–1099
Kehagias A, Konstantinidis G. “Some Game Theoretic Remarks on Two-Player Generalized Cops and Robbers Games.” arXiv:2007.14758
Konstantinidis G, Kehagias Ath (2016) Simultaneously moving cops and robbers. Theor Comput Sci 645:48–59
Luckraz S (2019) A survey on the relationship between the game of cops and robbers and other game representations. Dyn Games Appl 9(2):506–520
Mazala R (2002) Infinite games. Automata logics, and infinite games. Springer, Berlin, Heidelberg, pp 23-38
Nowakowski R, Winkler P (1983) Vertex-to-vertex pursuit in a graph. Discret Math 43:235–239
Quilliot A (1978) Thèse de 3ème cycle, Université de Paris VI, pp 131–145
Quilliot A (1983) Problemes de jeux, de point fixe, de connectivite et de representation sur des graphes, des ensembles ordonnes et des hypergraphes
Quilliot A (1985) A short note about pursuit games played on a graph with a given genus. J Comb Theory Ser B 38:89–92
Ummels M (2010) Stochastic multiplayer games: theory and algorithms. Amsterdam University Press, Amsterdam