Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Dynamic Games and Applications 4/2021

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
share
TEILEN

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.

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

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
  • Business IT + Informatik
  • 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
  • Business IT + Informatik
  • 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
  • Business IT + Informatik
  • 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.
Zurück zum Zitat Apt KR, Grädel E (2011) Lectures in game theory for computer scientists. Cambridge University Press, Cambridge CrossRef Apt KR, Grädel E (2011) Lectures in game theory for computer scientists. Cambridge University Press, Cambridge CrossRef
3.
Zurück zum Zitat Berwanger D (2013) “Graph games with perfect information.” Preprint Berwanger D (2013) “Graph games with perfect information.” Preprint
4.
Zurück zum Zitat Bonato A, Nowakowski R (2011) The game of cops and robbers on graphs. American Mathematical Society, USA CrossRef Bonato A, Nowakowski R (2011) The game of cops and robbers on graphs. American Mathematical Society, USA CrossRef
5.
Zurück zum Zitat Bonato A, MacGillivray G (2017) Characterizations and algorithms for generalized Cops and Robbers games. Contributions to Discrete Mathematics, vol.12 Bonato A, MacGillivray G (2017) Characterizations and algorithms for generalized Cops and Robbers games. Contributions to Discrete Mathematics, vol.12
6.
Zurück zum Zitat Chung TH, Hollinger GA, Isler V (2011) Search and pursuit-evasion in mobile robotics. Auton Robots 31:299–310 CrossRef Chung TH, Hollinger GA, Isler V (2011) Search and pursuit-evasion in mobile robotics. Auton Robots 31:299–310 CrossRef
7.
Zurück zum Zitat Filar J, Vrieze K (1996) Competitive Markov Decision Processes Filar J, Vrieze K (1996) Competitive Markov Decision Processes
8.
Zurück zum Zitat Fomin FV, Thilikos DM (2008) An annotated bibliography on guaranteed graph searching. Theor Comput Sci 399(3):236–245 MathSciNetCrossRef Fomin FV, Thilikos DM (2008) An annotated bibliography on guaranteed graph searching. Theor Comput Sci 399(3):236–245 MathSciNetCrossRef
9.
Zurück zum Zitat Hahn G, MacGillivray G (2006) A note on \(k\)-cop, \(l\)-robber games on graphs. Discret Math 306(19–20):2492–2497 MathSciNetCrossRef Hahn G, MacGillivray G (2006) A note on \(k\)-cop, \(l\)-robber games on graphs. Discret Math 306(19–20):2492–2497 MathSciNetCrossRef
10.
Zurück zum Zitat 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 MathSciNetCrossRef 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 MathSciNetCrossRef
11.
Zurück zum Zitat Kehagias A, Konstantinidis G (2017) Selfish cops and passive robber: qualitative games. Theor Comput Sci 680:25–35 MathSciNetCrossRef Kehagias A, Konstantinidis G (2017) Selfish cops and passive robber: qualitative games. Theor Comput Sci 680:25–35 MathSciNetCrossRef
12.
Zurück zum Zitat Kehagias A, Konstantinidis G (2019) Selfish cops and active robber: multi-player pursuit evasion on graphs. Theor Comput Sci 780:84–102 MathSciNetCrossRef Kehagias A, Konstantinidis G (2019) Selfish cops and active robber: multi-player pursuit evasion on graphs. Theor Comput Sci 780:84–102 MathSciNetCrossRef
13.
Zurück zum Zitat Kehagias A (2019) Generalized cops and robbers: a multi-player Pursuit game on graphs. Dyn Games Appl 9:1076–1099 MathSciNetCrossRef Kehagias A (2019) Generalized cops and robbers: a multi-player Pursuit game on graphs. Dyn Games Appl 9:1076–1099 MathSciNetCrossRef
14.
15.
16.
Zurück zum Zitat 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 MathSciNetCrossRef 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 MathSciNetCrossRef
17.
Zurück zum Zitat Mazala R (2002) Infinite games. Automata logics, and infinite games. Springer, Berlin, Heidelberg, pp 23-38 Mazala R (2002) Infinite games. Automata logics, and infinite games. Springer, Berlin, Heidelberg, pp 23-38
19.
Zurück zum Zitat Quilliot A (1978) Thèse de 3ème cycle, Université de Paris VI, pp 131–145 Quilliot A (1978) Thèse de 3ème cycle, Université de Paris VI, pp 131–145
20.
Zurück zum Zitat 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 (1983) Problemes de jeux, de point fixe, de connectivite et de representation sur des graphes, des ensembles ordonnes et des hypergraphes
21.
Zurück zum Zitat 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 MathSciNetCrossRef 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 MathSciNetCrossRef
22.
Zurück zum Zitat Ummels M (2010) Stochastic multiplayer games: theory and algorithms. Amsterdam University Press, Amsterdam CrossRef Ummels M (2010) Stochastic multiplayer games: theory and algorithms. Amsterdam University Press, Amsterdam CrossRef
Metadaten
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

Weitere Artikel der Ausgabe 4/2021

Dynamic Games and Applications 4/2021 Zur Ausgabe

Premium Partner