The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design
The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design
复制标题
安全博弈的奥秘：平衡计算成为组合算法设计
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Haifeng Xu
中科院分区：
文献类型：
--
作者：
Haifeng Xu
安全博弈是对抗环境下资源分配的基本模型。这里有两个球员，一个防守队员和一个进攻队员。防御者希望分配她有限的资源来防御关键目标，而攻击者则寻求他最有利的目标进行攻击。在过去的十年中，有一个研究兴趣激增，在分析和解决安全游戏，从各个领域的应用程序的动机。值得注意的是，这些模型及其博弈论解决方案已经导致主要安全机构（如洛杉矶国际机场、美国海岸警卫队和联邦空军元帅服务）以及非政府组织在实际部署中使用。在所有这些研究和应用中，平衡计算是一个基础。本文从理论的角度研究安全博弈，并提供了一个统一的观点，各种安全博弈模型。特别地，每个安全博弈都可以由防御者的纯策略组成的集合系统E来表征;防御者的最佳对策问题可以被看作是E上的组合优化问题。我们的框架捕获了文献中的大多数基本安全博弈模型，包括所有部署的系统;集合系统E产生于各个域编码标准的组合问题，如二分匹配，最大覆盖，最小成本流，包装问题等。我们的主要结果表明，在安全博弈中的均衡计算本质上是一个组合问题。特别地，我们证明了对任意集合系统E，下列问题可以在多项式时间内相互转化：（0）E上的组合优化问题，（1）E上零和安全对策的极大极小均衡问题，（2）E上安全对策的强Stackelberg均衡问题，（3）E上安全对策的强Stackelberg均衡问题，（4）E上安全对策的强Stackelberg均衡问题。（3）计算E上安全对策的最佳或最差（防御者）纳什均衡。因此，这些问题中任何一个的难度[多项式可解性]都意味着所有其他问题的难度[多项式可解性]。在这里，我们所说的“E上的博弈”是指具有任意支付结构的安全博弈类，但防御者的纯策略是固定的。这表明，安全博弈的复杂性本质上是由集合系统E决定的。我们认为，绘制这些连接作为本文的一个重要的概念贡献。
The security game is a basic model for resource allocation in adversarial environments. Here there are two players, a defender and an attacker. The defender wants to allocate her limited resources to defend critical targets and the attacker seeks his most favorable target to attack. In the past decade, there has been a surge of research interest in analyzing and solving security games that are motivated by applications from various domains. Remarkably, these models and their game-theoretic solutions have led to real-world deployments in use by major security agencies like the LAX airport, the US Coast Guard and Federal Air Marshal Service, as well as non-governmental organizations. Among all these research and applications, equilibrium computation serves as a foundation. This paper examines security games from a theoretical perspective and provides a unified view of various security game models. In particular, each security game can be characterized by a set system E which consists of the defender's pure strategies; The defender's best response problem can be viewed as a combinatorial optimization problem over E. Our framework captures most of the basic security game models in the literature, including all the deployed systems; The set system E arising from various domains encodes standard combinatorial problems like bipartite matching, maximum coverage, min-cost flow, packing problems, etc. Our main result shows that equilibrium computation in security games is essentially a combinatorial problem. In particular, we prove that, for any set system $E$, the following problems can be reduced to each other in polynomial time: (0) combinatorial optimization over E; (1) computing the minimax equilibrium for zero-sum security games over E; (2) computing the strong Stackelberg equilibrium for security games over E; (3) computing the best or worst (for the defender) Nash equilibrium for security games over E. Therefore, the hardness [polynomial solvability] of any of these problems implies the hardness [polynomial solvability] of all the others. Here, by "games over E" we mean the class of security games with arbitrary payoff structures, but a fixed set E of defender pure strategies. This shows that the complexity of a security game is essentially determined by the set system E. We view drawing these connections as an important conceptual contribution of this paper.