Skip to main content
Fachgebiete
Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Weitere Formate
Webinare Technik
Webinare Wirtschaft
Kongresse
Veranstaltungskalender
Podcasts
Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Erweiterte Suche
Anmelden
nach oben
Dynamic Games and Applications

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

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.
Vorheriger Artikel Privacy, Patience, and Protection
Nächster Artikel Effect of Variability in Payoffs on Conditions for the Evolution of Cooperation in a Small Population

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Jetzt informieren
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.
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 MathSciNetCrossRef
9.
Hahn G, MacGillivray G (2006) A note on \(k\)-cop, \(l\)-robber games on graphs. Discret Math 306(19–20):2492–2497 MathSciNetCrossRef
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 MathSciNetCrossRef
11.
Kehagias A, Konstantinidis G (2017) Selfish cops and passive robber: qualitative games. Theor Comput Sci 680:25–35 MathSciNetCrossRef
12.
Kehagias A, Konstantinidis G (2019) Selfish cops and active robber: multi-player pursuit evasion on graphs. Theor Comput Sci 780:84–102 MathSciNetCrossRef
13.
Kehagias A (2019) Generalized cops and robbers: a multi-player Pursuit game on graphs. Dyn Games Appl 9:1076–1099 MathSciNetCrossRef
14.
15.
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 MathSciNetCrossRef
17.
Mazala R (2002) Infinite games. Automata logics, and infinite games. Springer, Berlin, Heidelberg, pp 23-38
18.
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 MathSciNetCrossRef
22.
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

OriginalPaper

Subgame Maxmin Strategies in Zero-Sum Stochastic Games with Tolerance Levels

OriginalPaper

Modeling COVID-19 Pandemic with Hierarchical Quarantine and Time Delay

OriginalPaper

Asymmetric Partisan Voter Turnout Games

OriginalPaper

Games Without Winners: Catching-up with Asymmetric Spillovers

OriginalPaper

Privacy, Patience, and Protection

OriginalPaper

Effect of Variability in Payoffs on Conditions for the Evolution of Cooperation in a Small Population

Premium Partner