Patrolling a border

Katerina Papadaki, Steve Alpern, Thomas Lidbetter, Alec Morton

Research output: Contribution to journalArticle

10 Citations (Scopus)

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).
LanguageEnglish
Pages1256–1269
Number of pages15
JournalOperations Research
Volume64
Issue number6
DOIs
Publication statusPublished - 12 Sep 2016

Fingerprint

Infiltration
Node
Attack
Optimal strategy

Keywords

  • search and surveillance
  • patrolling
  • patrolling games
  • game theory

Cite this

Papadaki, K., Alpern, S., Lidbetter, T., & Morton, A. (2016). Patrolling a border. Operations Research, 64(6), 1256–1269. https://doi.org/10.1287/opre.2016.1511
Papadaki, Katerina ; Alpern, Steve ; Lidbetter, Thomas ; Morton, Alec. / Patrolling a border. In: Operations Research. 2016 ; Vol. 64, No. 6. pp. 1256–1269.
@article{b1d65c0a573543c08fcf3388a6e4c414,
title = "Patrolling a border",
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).",
keywords = "search and surveillance, patrolling, patrolling games, game theory",
author = "Katerina Papadaki and Steve Alpern and Thomas Lidbetter and Alec Morton",
note = "The title of this output was changed post-acceptance from {"}Patrolling the line{"} to {"}Patrolling a border{"}.",
year = "2016",
month = "9",
day = "12",
doi = "10.1287/opre.2016.1511",
language = "English",
volume = "64",
pages = "1256–1269",
journal = "Operations Research",
issn = "0030-364X",
number = "6",

}

Papadaki, K, Alpern, S, Lidbetter, T & Morton, A 2016, 'Patrolling a border' Operations Research, vol. 64, no. 6, pp. 1256–1269. https://doi.org/10.1287/opre.2016.1511

Patrolling a border. / Papadaki, Katerina; Alpern, Steve; Lidbetter, Thomas; Morton, Alec.

In: Operations Research, Vol. 64, No. 6, 12.09.2016, p. 1256–1269.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Patrolling a border

AU - Papadaki, Katerina

AU - Alpern, Steve

AU - Lidbetter, Thomas

AU - Morton, Alec

N1 - The title of this output was changed post-acceptance from "Patrolling the line" to "Patrolling a border".

PY - 2016/9/12

Y1 - 2016/9/12

N2 - 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).

AB - 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).

KW - search and surveillance

KW - patrolling

KW - patrolling games

KW - game theory

U2 - 10.1287/opre.2016.1511

DO - 10.1287/opre.2016.1511

M3 - Article

VL - 64

SP - 1256

EP - 1269

JO - Operations Research

T2 - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 6

ER -

Papadaki K, Alpern S, Lidbetter T, Morton A. Patrolling a border. Operations Research. 2016 Sep 12;64(6):1256–1269. https://doi.org/10.1287/opre.2016.1511