Patrolling a border

Papadaki, Katerina and Alpern, Steve and Lidbetter, Thomas and Morton, Alec (2016) Patrolling a border. Operations Research, 64 (6). 1256–1269. ISSN 0030-364X (https://doi.org/10.1287/opre.2016.1511)

[thumbnail of Papadaki_etal_OR2016_patrolling_the_border]
Preview
 Text. Filename: Papadaki_etal_OR2016_patrolling_the_border.pdf
Accepted Author Manuscript
Download (1MB)| Preview

Abstract

Patrolling games were recently introduced by Alpern, Morton and Papadaki 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).

  • Item type:Article
    ID code:55777
    Dates:
    Date
    Event
    12 September 2016
    Published
    4 March 2016
    Accepted
    Notes:The title of this output was changed post-acceptance from "Patrolling the line" to "Patrolling a border".
    Subjects:Military Science
    Department:Strathclyde Business School > Management Science
    Depositing user: Pure Administrator
    Date deposited:07 Mar 2016 13:31
    Last modified:14 Apr 2024 00:35
    URI:https://strathprints.strath.ac.uk/id/eprint/55777
CORE (COnnecting REpositories)