Patrolling a Border

• 成果类型: Article
• 署名作者: Papadaki, Katerina; Alpern, Steve; Lidbetter, Thomas; Morton, Alec
• 署名单位: University of London; London School Economics & Political Science; University of Warwick; Rutgers University System; Rutgers University New Brunswick; Rutgers University Newark; University of Strathclyde
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1511
• 发表日期: 2016
• 页码: 1256-1269
• 关键词: ambush game

摘要

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