Patrolling games

Steven Alpern, Alec Morton and Katerina Papadaki

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

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. Subject classifications: games; noncooperative; military, search/surveillance; decision analysis; risk; networks/graphs. Area of review: Military and Homeland Security. History: Received November 2009; revisions received March 2010, September 2010; accepted November 2010

Keywords: ISI; games; noncooperative; military; search/surveillance; decision analysis; risk; networks/graphs (search for similar items in EconPapers)
JEL-codes: C02 C72 (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Published in Operations Research, 2011, 59(5), pp. 1246-1257. ISSN: 0030-364X

Downloads: (external link)
http://eprints.lse.ac.uk/32210/ Open access version. (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:ehl:lserod:32210

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().