Patrolling a Border

Katerina Papadaki (), Steve Alpern (), Thomas Lidbetter () and Alec Morton ()
Additional contact information
Katerina Papadaki: Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom
Steve Alpern: Warwick Business School, University of Warwick, Coventry CV4 7AL, United Kingdom
Thomas Lidbetter: Rutgers Business School, Department of Management Science and Information Systems, Newark, New Jersey 07102
Alec Morton: Department of Management Science, University of Strathclyde, Glasgow G1 1XQ, United Kingdom

Operations Research, 2016, vol. 64, issue 6, 1256-1269

Abstract: Patrolling games were recently introduced to model the problem of protecting the nodes of a network from an attack. Time is discrete and in each time unit the Patroller can stay at the same node or move to an adjacent node. The Attacker chooses when to attack and which node to attack and needs m consecutive time units to carry it out. The Attacker wins if the Patroller does not visit the chosen node while it is being attacked; otherwise, the Patroller wins. This paper studies the patrolling game where the network is a line graph of n nodes, which models the problem of guarding a channel or protecting a border from infiltration. We solve the patrolling game for any values of m and n , providing an optimal Patroller strategy, an optimal Attacker strategy, and the value of the game (optimal probability that the attack is intercepted).

Keywords: search and surveillance; patrolling (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1511 (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:64:y:2016:i:6:p:1256-1269

Access Statistics for this article

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