We settle a recent conjecture on a continuous patrolling game. 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. 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 $\varepsilon$-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.
翻译:我们解决了最近关于连续巡逻游戏的猜测。 在这个零和游戏中, 攻击者选择了一个时间和地点来攻击一个网络, 时间和地点固定。 巡逻者在网络上巡逻, 目的是以最大的概率拦截攻击。 猜测认为, 所谓的电子巡逻战略对所有树网来说都是最理想的。 先前在有限的特殊案例中, 预言是真实的。 电子巡逻战略的优点是直接计算和执行。 我们为攻击者展示了 $\ varepsilon$- 最佳策略, 为任意接近E- 旅行战略提供的较低约束的游戏的价值提供了上限。