Patrolling Games

Steve Alpern (), Alec Morton () and Katerina Papadaki ()
Additional contact information
Steve Alpern: Department of Mathematics and Management Science Group, Department of Management, London School of Economics and Political Science, London WC2A 2AE, United Kingdom
Alec Morton: Management Science Group, Department of Management, London School of Economics and Political Science, London WC2A 2AE, United Kingdom
Katerina Papadaki: Management Science Group, Department of Management, London School of Economics and Political Science, London WC2A 2AE, United Kingdom

Operations Research, 2011, vol. 59, issue 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: games; noncooperative; military; search/surveillance; decision analysis; risk; networks/graphs (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0983 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:5:p:1246-1257

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().