Top

Dynamic Games and Applications

Published in:

18-04-2021

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

Authors: Athanasios Kehagias, Georgios Konstantinidis

Published in: Dynamic Games and Applications | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Privacy, Patience, and Protection

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

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

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.

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

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

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.

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

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.

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

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.

Apt KR, Grädel E (2011) Lectures in game theory for computer scientists. Cambridge University Press, CambridgeCrossRef

Berarducci A, Intrigila B (1993) On the cop number of a graph. Adv Appl Math 14(4):389–403MathSciNetCrossRef

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, USACrossRef

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–310CrossRef

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–245MathSciNetCrossRef

Hahn G, MacGillivray G (2006) A note on \(k\)-cop, \(l\)-robber games on graphs. Discret Math 306(19–20):2492–2497MathSciNetCrossRef

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–596MathSciNetCrossRef

11.

Kehagias A, Konstantinidis G (2017) Selfish cops and passive robber: qualitative games. Theor Comput Sci 680:25–35MathSciNetCrossRef

12.

Kehagias A, Konstantinidis G (2019) Selfish cops and active robber: multi-player pursuit evasion on graphs. Theor Comput Sci 780:84–102MathSciNetCrossRef

13.

Kehagias A (2019) Generalized cops and robbers: a multi-player Pursuit game on graphs. Dyn Games Appl 9:1076–1099MathSciNetCrossRef

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–59MathSciNetCrossRef

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–520MathSciNetCrossRef

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–239MathSciNetCrossRef

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–92MathSciNetCrossRef

22.

Ummels M (2010) Stochastic multiplayer games: theory and algorithms. Amsterdam University Press, AmsterdamCrossRef

Title: Some Game-Theoretic Remarks on Two-Player Generalized Cops and Robbers Games
Authors: Athanasios Kehagias
Georgios Konstantinidis
Publication date: 18-04-2021
Publisher: Springer US
Published in: Dynamic Games and Applications / Issue 4/2021
Print ISSN: 2153-0785
Electronic ISSN: 2153-0793
DOI: https://doi.org/10.1007/s13235-021-00385-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2021

Correction to: Nash Equilibria and Bargaining Solutions of Differential Bilinear Games

Privacy, Patience, and Protection

Games Without Winners: Catching-up with Asymmetric Spillovers

Asymmetric Partisan Voter Turnout Games

Modeling COVID-19 Pandemic with Hierarchical Quarantine and Time Delay

An Impulse-Regime Switching Game Model of Vertical Competition

Premium Partner