Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Dynamic Games and Applications 4/2019

20-11-2018

Generalized Cops and Robbers: A Multi-player Pursuit Game on Graphs

Author: Ath. Kehagias

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

Login to get access
share
SHARE

Abstract

We introduce and study the Generalized Cops and Robbers (GCR) game, an N-player pursuit game in graphs. The two-player version is essentially equivalent to the classic Cops and Robbers (CR) game. The three-player version can be understood as two CR games played simultaneously on the same graph; a player can be at the same time both pursuer and evader. The same is true for four or more players. We formulate GCR as a discounted stochastic game of perfect information and prove that, for three or more players, it has at least two Nash equilibria: one in positional deterministic strategies and another in nonpositional ones. We also study the capturing properties of GCR Nash equilibria in connection with the cop number of a graph. Finally, we briefly discuss GCR as a member of a wider family of multi-player graph pursuit games with rather interesting properties.

To get access to this content you need the following product:

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.

Footnotes
1
That is, they never produce moves outside the player’s action set.
 
2
As will be seen, since GCR is a game of perfect information, the player loses nothing by using only deterministic strategies.
 
3
It is worth noting that \(\varGamma _{2}\left( G|s_{0}\right) \) can be expanded to incorporate a placement round as well. This is done as follows. Using \(\xi \) to denote that a player is positioned “outside” the graph, we must introduce a starting state \(\left( \xi ,\xi \right) \) (no player has played yet) and, for each \(x\in V\), a state \(\left( x,\xi \right) \) (\(P_{1}\) has already played his first move but not \(P_{2}\)). Actions, state transitions, payoffs, etc. can be similarly modified to represent the “classic” CR move sequence. Under this approach (which can also be applied to the \(\varGamma _{N}\left( G|s_{0}\right) \) games introduced in later sections), all our essential results still hold. This route is eschewed in the current paper, for reasons of simplicity.
 
4
Up to a time rescaling, due to the above-mentioned difference in time units.
 
5
Since \(\varGamma _{3}\left( G|s_{0}\right) \) is a perfect information game, the deviation will be detected immediately.
 
6
We define \(\rho ^{1}\) such that, when combined with \({\widetilde{s}}_{T_{1}-1},{\widehat{\phi }}_{1}^{2} ,{\widehat{\phi }}_{1}^{3}\), will produce the same history \({\widetilde{s}}_{T_{1} }{\widetilde{s}}_{T_{1}+1}{\widetilde{s}}_{T_{1}+2}\ldots \) as \(\sigma ^{1}\). Note that \(\rho ^{1}\) will in general depend (in an indirect way) on \(\widetilde{s}_{0}{\widetilde{s}}_{1}\ldots {\widetilde{s}}_{T_{1}-2}\).
 
7
A clarification is needed here: the domain of \(\varGamma _{2}\left( G|s_{0}\right) \) (positional) strategies is \(V\times V\times \left\{ 1,2\right\} \), while the domain of \(\varGamma _{3}\left( G|s_{0}\right) \) (positional) strategies is \(V\times V\times V\times \left\{ 1,2\right\} \). However, we can “extend” a \(\varGamma _{2}\left( G|s_{0}\right) \) strategy to use it in \(\varGamma _{3}\left( G|s_{0}\right) \). For example, suppose \(\sigma ^{1}\left( x^{1} ,x^{2}\right) \) is a \(P_{1}\) strategy in \(\varGamma _{2}\left( G|s_{0}\right) \); then, it can also be extended to a \(\varGamma _{3}\left( G|s_{0}\right) \) strategy \({\widetilde{\sigma }}^{1}\left( x^{1},x^{2},x^{3}\right) \) by letting
$$\begin{aligned} \forall x^{3}:{\widetilde{\sigma }}^{1}\left( x^{1},x^{2},x^{3}\right) =\sigma ^{1}\left( x^{1},x^{2}\right) . \end{aligned}$$
In other words, \(P_{1}\) applies \(\sigma ^{1}\) in \(\varGamma _{3}\left( G|s_{0}\right) \) by ignoring \(P_{3}\)’s position. We will often use this and similar constructions in what follows, without further comment; and we will denote the \(\varGamma _{2}\left( G|s_{0}\right) \) and \(\varGamma _{3}\left( G|s_{0}\right) \) strategies by the same symbol, e.g., \(\sigma ^{n}\).
 
8
The conditions in (7.1) encode “minimum” requirements, additional restrictions may be imposed, e.g., no simultaneous captures.
 
9
That is, the players have not yet placed their tokens; see footnote 3 for details.
 
Literature
1.
go back to reference Bonato A, Nowakowski RJ (2011) The game of cops and robbers on graphs. American Mathematical Society, Providence CrossRef Bonato A, Nowakowski RJ (2011) The game of cops and robbers on graphs. American Mathematical Society, Providence CrossRef
3.
go back to reference Boros E, Gurvich V (2009) Why chess and back gammon can be solved in pure positional uniformly optimal strategies. Rutcor research report 21-2009, Rutgers University Boros E, Gurvich V (2009) Why chess and back gammon can be solved in pure positional uniformly optimal strategies. Rutcor research report 21-2009, Rutgers University
4.
go back to reference Chatterjee K, Majumdar R, Jurdziński M (2004) On Nash equilibria in stochastic games. In: Marcinkowski J, Tarlecki A (eds) International workshop on computer science logic. Springer, Berlin, pp 26–40 CrossRef Chatterjee K, Majumdar R, Jurdziński M (2004) On Nash equilibria in stochastic games. In: Marcinkowski J, Tarlecki A (eds) International workshop on computer science logic. Springer, Berlin, pp 26–40 CrossRef
6.
go back to reference Filar J, Vrieze K (1997) Competitive Markov decision processes. Springer-Verlag, New York MATH Filar J, Vrieze K (1997) Competitive Markov decision processes. Springer-Verlag, New York MATH
7.
8.
go back to reference Foley M, Schmitendorf W (1974) A class of differential games with two pursuers versus one evader. IEEE Trans Autom Control 19(3):239–243 MathSciNetCrossRef Foley M, Schmitendorf W (1974) A class of differential games with two pursuers versus one evader. IEEE Trans Autom Control 19(3):239–243 MathSciNetCrossRef
9.
go back to reference Isaacs R (1999) Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Courier Corporation, North Chelmsford MATH Isaacs R (1999) Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Courier Corporation, North Chelmsford MATH
10.
go back to reference Jang JS, Tomlin C (2005) Control strategies in multi-player pursuit and evasion game. In: AIAA guidance, navigation, and control conference and exhibit Jang JS, Tomlin C (2005) Control strategies in multi-player pursuit and evasion game. In: AIAA guidance, navigation, and control conference and exhibit
11.
14.
go back to reference Pham KD, Lacy S, Robertson L (2008) Multi-cumulant and Pareto strategies for stochastic multi-player pursuit-evasion. In: American control conference Pham KD, Lacy S, Robertson L (2008) Multi-cumulant and Pareto strategies for stochastic multi-player pursuit-evasion. In: American control conference
15.
go back to reference Quilliot A (1978) Jeux et pointes fixes sur les graphes. These de 3me cycle, Universit de Paris VI Quilliot A (1978) Jeux et pointes fixes sur les graphes. These de 3me cycle, Universit de Paris VI
16.
17.
go back to reference Souidi M et al (2015) Coalition formation algorithm based on organization and Markov decision process for multi-player pursuit evasion. Multiagent Grid Syst 11(1):1–13 MathSciNetCrossRef Souidi M et al (2015) Coalition formation algorithm based on organization and Markov decision process for multi-player pursuit evasion. Multiagent Grid Syst 11(1):1–13 MathSciNetCrossRef
19.
go back to reference Sun W et al (2017) Multiple-pursuer/one-evader pursuit-evasion game in dynamic flowfields. J Guid Control Dyn 40:1627–1637 CrossRef Sun W et al (2017) Multiple-pursuer/one-evader pursuit-evasion game in dynamic flowfields. J Guid Control Dyn 40:1627–1637 CrossRef
20.
go back to reference Thuijsman F, Raghavan TES (1997) Perfect information stochastic games and related classes. Int J Game Theory 26(3):403–408 MathSciNetCrossRef Thuijsman F, Raghavan TES (1997) Perfect information stochastic games and related classes. Int J Game Theory 26(3):403–408 MathSciNetCrossRef
Metadata
Title
Generalized Cops and Robbers: A Multi-player Pursuit Game on Graphs
Author
Ath. Kehagias
Publication date
20-11-2018
Publisher
Springer US
Published in
Dynamic Games and Applications / Issue 4/2019
Print ISSN: 2153-0785
Electronic ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-018-0288-0

Other articles of this Issue 4/2019

Dynamic Games and Applications 4/2019 Go to the issue

Premium Partner