Security Games on a Plane
Security Games on a Plane
复制标题
DOI：
10.1609/aaai.v31i1.10614
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Jiarui Gan;Bo An;Yevgeniy Vorobeychik;B. Gauch
中科院分区：
文献类型：
--
作者：
Jiarui Gan;Bo An;Yevgeniy Vorobeychik;B. Gauch
大多数现有的Stackelberg安全博弈模型忽略了目标和防御资源所在空间的基本拓扑结构。因此，资源分配仅限于外部定义的目标的离散集合。然而，在许多实际的安全设置中，防御资源可以位于连续的平面上。因此，通过将资源放置在实际目标之外的空间中（例如，目标之间）。为了解决这个问题，我们提出了一个模型，称为安全游戏的平面（SGP）中的目标分布在一个二维平面上，安全资源，在同一平面上分配，保护目标在一定的有效距离。我们调查的算法方面的SGP。我们发现，计算一个强Stackelberg平衡的SGP是NP-困难的，即使是零和游戏，这些是不可近似的一般。在积极的一面，我们找到了一个精确的解决方案技术，一般SGP的基础上现有的方法，并开发了一个PTAS（多项式时间近似计划）零和SGP更根本地克服计算障碍。我们的实验证明了考虑SGP的价值和我们的算法的有效性。
Most existing models of Stackelberg security games ignore the underlying topology of the space in which targets and defence resources are located. As a result, allocation of resources is restricted to a discrete collection of exogenously defined targets. However, in many practical security settings, defense resources can be located on a continuous plane. Better defense solutions could therefore be potentially achieved by placing resources in a space outside of actual targets (e.g., between targets). To address this limitation, we propose a model called Security Game on a Plane (SGP) in which targets are distributed on a 2-dimensional plane, and security resources, to be allocated on the same plane, protect targets within a certain effective distance. We investigate the algorithmic aspects of SGP. We find that computing a strong Stackelberg equilibrium of an SGP is NP-hard even for zero-sum games, and these are inapproximable in general. On the positive side, we find an exact solution technique for general SGPs based on an existing approach, and develop a PTAS (polynomial-time approximation scheme) for zero-sum SGP to more fundamentally overcome the computational obstacle. Our experiments demonstrate the value of considering SGP and effectiveness of our algorithms.