Patrolling Games
Authors:
- 1 October 2011
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 59 (5) , 1246-1257
Abstract
A key operational problem for those charged with the security of vulnerable facilities (such as airports or art galleries) is the scheduling and deployment of patrols. Motivated by the problem of optimizing randomized, and thus unpredictable, patrols, we present a class of patrolling games. The facility to be patrolled can be thought of as a network or graph Q of interconnected nodes (e.g., rooms, terminals), and the Attacker can choose to attack any node of Q within a given time T. He requires m consecutive periods there, uninterrupted by the Patroller, to commit his nefarious act (and win). The Patroller can follow any path on the graph. Thus, the patrolling game is a win-lose game, where the Value is the probability that the Patroller successfully intercepts an attack, given best play on both sides. We determine analytically either the Value of the game, or bounds on the Value, for various classes of graphs, and we discuss possible extensions and generalizations.Keywords
This publication has 17 references indexed in Scilit:
- Policing for crime prevention2010
- The influence of secrecy on the communication structure of covert networksSocial Networks, 2009
- Defending Critical InfrastructureInterfaces, 2006
- Continuous accumulation games on discrete locationsNaval Research Logistics (NRL), 2002
- Art Gallery and Illumination Problems2000
- On the infiltration gameInternational Journal of Game Theory, 1997
- Infiltration games on arbitrary graphsJournal of Mathematical Analysis and Applications, 1992
- An infiltration game onk arcsNaval Research Logistics (NRL), 1991
- The number hides gameProceedings of the American Mathematical Society, 1989
- The search value of a networkNetworks, 1985