main-content

Erschienen in:

18.04.2021

# Some Game-Theoretic Remarks on Two-Player Generalized Cops and Robbers Games

verfasst von: Athanasios Kehagias, Georgios Konstantinidis

Erschienen in: Dynamic Games and Applications | Ausgabe 4/2021

Einloggen, um Zugang zu erhalten

## Abstract

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.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 50.000 Bücher
• über 380 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Maschinenbau + Werkstoffe

Testen Sie jetzt 15 Tage kostenlos.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Fußnoten
1
Let us add that the following remarks apply (to a certain extent) even to the simpler, original version of CR/GCR which is concerned with winning (i.e., capturing/evading) rather than time optimal strategies.

2
We mention, for the sake of completeness, that yet another possibility is the formulation and solution of GCR as an extensive form game.

3
It is worth noting that the VL algorithm is actually a special form of value iteration.

4
Note that in the usual CR description time is counted in rounds, where each round encompasses (in our terminology) one cop and one robber turn. The two approaches are essentially equivalent.

5
This point is also raised in [10], where an interesting alternative approach is proposed to characterize robber-win graphs.

6
Let us stress that they still deal with a two-player game: there is a single cop player and a single robber player, but each can control one or more (cop or robber) tokens.

7
Of course this is just a verbal description of the $$\sup$$ and $$\inf$$ conditions of our Definition 2.16.

8
There is one caveat: it is never specified in [5] whether once a state achieves a finite label can be subsequently relabeled (it should not); this is probably an oversight in the description.

Literatur
1.
Apt KR, Grädel E (2011) Lectures in game theory for computer scientists. Cambridge University Press, Cambridge CrossRef
2.
Berarducci A, Intrigila B (1993) On the cop number of a graph. Adv Appl Math 14(4):389–403
3.
Berwanger D (2013) “Graph games with perfect information.” Preprint
4.
Bonato A, Nowakowski R (2011) The game of cops and robbers on graphs. American Mathematical Society, USA CrossRef
5.
Bonato A, MacGillivray G (2017) Characterizations and algorithms for generalized Cops and Robbers games. Contributions to Discrete Mathematics, vol.12
6.
Chung TH, Hollinger GA, Isler V (2011) Search and pursuit-evasion in mobile robotics. Auton Robots 31:299–310 CrossRef
7.
Filar J, Vrieze K (1996) Competitive Markov Decision Processes
8.
Fomin FV, Thilikos DM (2008) An annotated bibliography on guaranteed graph searching. Theor Comput Sci 399(3):236–245
9.
Hahn G, MacGillivray G (2006) A note on $$k$$-cop, $$l$$-robber games on graphs. Discret Math 306(19–20):2492–2497
10.
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
11.
Kehagias A, Konstantinidis G (2017) Selfish cops and passive robber: qualitative games. Theor Comput Sci 680:25–35
12.
Kehagias A, Konstantinidis G (2019) Selfish cops and active robber: multi-player pursuit evasion on graphs. Theor Comput Sci 780:84–102
13.
Kehagias A (2019) Generalized cops and robbers: a multi-player Pursuit game on graphs. Dyn Games Appl 9:1076–1099
14.
Kehagias A, Konstantinidis G. “Some Game Theoretic Remarks on Two-Player Generalized Cops and Robbers Games.” arXiv:​2007.​14758
15.
Konstantinidis G, Kehagias Ath (2016) Simultaneously moving cops and robbers. Theor Comput Sci 645:48–59
16.
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
17.
Mazala R (2002) Infinite games. Automata logics, and infinite games. Springer, Berlin, Heidelberg, pp 23-38
18.
Nowakowski R, Winkler P (1983) Vertex-to-vertex pursuit in a graph. Discret Math 43:235–239
19.
Quilliot A (1978) Thèse de 3ème cycle, Université de Paris VI, pp 131–145
20.
Quilliot A (1983) Problemes de jeux, de point fixe, de connectivite et de representation sur des graphes, des ensembles ordonnes et des hypergraphes
21.
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
22.
Ummels M (2010) Stochastic multiplayer games: theory and algorithms. Amsterdam University Press, Amsterdam CrossRef
Titel
Some Game-Theoretic Remarks on Two-Player Generalized Cops and Robbers Games
verfasst von
Athanasios Kehagias
Georgios Konstantinidis
Publikationsdatum
18.04.2021
Verlag
Springer US
Erschienen in
Dynamic Games and Applications / Ausgabe 4/2021
Print ISSN: 2153-0785
Elektronische ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-021-00385-0

Zur Ausgabe