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 $\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. We also solve the patrolling game in some cases for complete networks.
翻译:我们展示了网络上持续巡逻游戏的解决方案。 在这个零和游戏中, 攻击者选择了攻击网络的时间和地点, 固定时间。 巡逻者巡逻网络的目的是以最大概率拦截袭击。 我们的主要结果证明最近对最佳树木巡逻战略的推测。 推测表明, 被称为电子巡逻战略的特定巡逻战略对所有树木网络都是最佳的。 先前已知, 在一个有限的特殊案例中是真实的。 电子旅行战略的好处是直截了当地计算和执行。 我们为攻击者展示了美元和瓦雷普西隆- 最佳策略,为任意接近E- 巡逻战略提供的较低界限的游戏的价值提供了上限。 我们有时也为完整的网络解决了巡逻游戏。