A Polynomial Time Algorithm for Spatio-Temporal Security Games
A Polynomial Time Algorithm for Spatio-Temporal Security Games
复制标题
时空安全博弈的多项式时间算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Aleksandrs Slivkins
中科院分区：
文献类型：
--
作者：
Soheil Behnezhad;Mahsa Derakhshan;M. Hajiaghayi;Aleksandrs Slivkins
一个日益重要的问题是保护基础设施和其他有价值的目标免受破坏、盗窃、海盗和恐怖主义等一系列威胁。“防御者”很少能够提供所需的资源来提供100%的保护。因此，关键问题是，如何利用有限的可用资源提供最好的保护。我们研究了一种非常重要的安全游戏，它是在空间和时间中进行的，目标和“巡逻队”在一条真实的线上移动。这里的一个中心问题是纳什均衡（即防守方的极大极小策略）能否在多项式时间内计算出来。我们肯定地解决了这个问题。我们的算法在输入大小上以时间多项式运行，在可能的巡逻地点m的数量上仅以多对数运行。此外，我们提供了一个连续扩展，其中巡逻地点可以取任意实值。先前的工作只在一个实质性的假设下获得多项式时间算法，例如，一个常数的轮数。此外，所有这些算法的运行时间都是多项式M，这可能非常大。
An ever-important issue is protecting infrastructure and other valuable targets from a range of threats from vandalism to theft to piracy to terrorism. The "defender" can rarely afford the needed resources for a 100% protection. Thus, the key question is, how to provide the best protection using the limited available resources. We study a practically important class of security games that is played out in space and time, with targets and "patrols" moving on a real line. A central open question here is whether the Nash equilibrium (i.e., the minimax strategy of the defender) can be computed in polynomial time. We resolve this question in the affirmative. Our algorithm runs in time polynomial in the input size, and only polylogarithmic in the number of possible patrol locations M. Further, we provide a continuous extension in which patrol locations can take arbitrary real values. Prior work obtained polynomial-time algorithms only under a substantial assumption, e.g., a constant number of rounds. Further, all these algorithms have running times polynomial in M, which can be very large.