Aristotle University Of Thessaloniki (AUTH)
Παιγνιοθεωρητικές πτυχές του παιγνίου - αστυνόμοι και ληστής - και παραλλαγών αυτού
Abstract
dc:descriptionIn the present thesis we introduce some variants of the “Cops and robber” game (CR) and then we analyze game theoretically the original game and these variants, within the framework of stochastic games. CR is a pursuit-evasion game in graphs, between a player controlling a number of cops and a robber. Given a graph, the central questions that arise are: (a) what is the minimum number of cops needed to guarantee capture, a quantity called “the cop number of the graph”, and (b) which are the optimal strategies of the players. The games we introduce are: (a) the “Concurrent CR game” (CCR) where contrary to the original game players move simultaneously (and not sequentially), (b) the game “Selfish cops and passive robber” (SCPR) where two players, the cops, pursue independently one from the other a passive robber, and (c) the game “Selfish cops and active robber” (SCAR) where a number of cops pursue, independently one from the other a robber trying to evade. We model CR, CCR and SCPR as stochastic (2-player) zero sum games and we show the existence of value and optimal positional strategies in all cases and we present algorithms computing these. In CCR we also define “the concurrent cop number of a graph”, analogously to the classical definition and then we show it is always equal to the original cop number. SCAR we model as a stochastic N-player game between Ν-1 cops and a robber and we show it always has both positional and non-positional Nash equilibria. We also show a number of results relating cop number to capturability and, having first defined “the selfish cop number of a graph”, we then show it is always equal to the classical cop number.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Konstantinidis, Georgios
- Κωνσταντινίδης, Γεώργιος
Subjects
dc:subject × 14Rights
dc:rights- Statement dc:rights
-
- BY_NC_SA
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/44824