Optimal patrolling strategies for trees and complete networks

Research output: Contribution to journalArticlepeer-review

Abstract

We present solutions to a continuous patrolling game played on network. In this zero-sum game, an Attacker chooses a time and place to attack a network for a fixed amount of time. A Patroller patrols the network with the aim of intercepting the attack with maximum probability. Our main result is the proof of a recent conjecture on the optimal patrolling strategy for trees. The conjecture asserts that a particular patrolling strategy called the E-patrolling strategy is optimal for all tree networks. The conjecture was previously known to be true in a limited class of special cases. The E-patrolling strategy has the advantage of being straightforward to calculate and implement. We prove the conjecture by presenting ε-optimal strategies for the Attacker which provide upper bounds for the value of the game that come arbitrarily close to the lower bound provided by the E-patrolling strategy. We also solve the patrolling game in some cases for complete networks.

Original languageEnglish (US)
Pages (from-to)769-776
Number of pages8
JournalEuropean Journal of Operational Research
Volume311
Issue number2
DOIs
StatePublished - Dec 1 2023

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Game theory
  • Networks
  • Patrolling
  • Zero-sum games

Fingerprint

Dive into the research topics of 'Optimal patrolling strategies for trees and complete networks'. Together they form a unique fingerprint.

Cite this