Stackelberg Security Games with Multiple Uncoordinated Defenders
Stackelberg Security Games with Multiple Uncoordinated Defenders
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Jiarui Gan;Edith Elkind;M. Wooldridge
中科院分区：
文献类型：
--
作者：
Jiarui Gan;Edith Elkind;M. Wooldridge
Stackelberg安全游戏近年来备受关注。虽然大多数现有的工作集中在单一的防御者设置，有许多现实世界的情况下，涉及多个防御者（例如，多国在国际沃茨采取打击犯罪行动，不同的安全机构在同一地区巡逻）。在本文中，我们认为安全游戏与不协调的防御者谁共同保护一组目标，但可能有不同的估值，这些目标，每个后卫调度自己的资源和自私地优化自己的效用。我们推广的标准（单后卫）模型的Stackelberg安全游戏到这种设置，并制定了一个均衡的概念，抓住了球员之间的战略互动的性质。我们认为，一个精确的均衡可能不存在，事实上，决定它是否存在是NP-难的。然而，在温和的假设下，每个多防御者安全博弈承认每个e>0$的e-均衡，并且对应于e\to 0$的极限点可以被有效地近似。
Stackelberg security games have received much attention in recent years. While most existing work focuses on single-defender settings, there are many real-world scenarios that involve multiple defenders (e.g., multi-national anti-crime actions in international waters, different security agencies patrolling the same area). In this paper, we consider security games with uncoordinated defenders who jointly protect a set of targets, but may have different valuations for these targets; each defender schedules their own resources and selfishly optimizes their own utility. We generalize the standard (single-defender) model of Stackelberg security games to this setting and formulate an equilibrium concept that captures the nature of strategic interaction among the players. We argue that an exact equilibrium may fail to exist, and, in fact, deciding whether it exists is NP-hard. However, under mild assumptions, every multi-defender security game admits an e-equilibrium for every e>0$, and the limit points corresponding to e\to 0$ can be efficiently approximated.