Approximation Algorithm for Security Games with Costly Resources
Approximation Algorithm for Security Games with Costly Resources
复制标题
资源昂贵的安全博弈的近似算法
DOI：
10.1007/978-3-642-25510-6_2
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Kamesh Munagala
中科院分区：
文献类型：
--
作者：
Sayan Bhattacharya;Vincent Conitzer;Kamesh Munagala
近年来，针对现实世界的安全领域开发了计算博弈论解决方案的算法。这些游戏是在防御者和攻击者之间进行的，防御者必须分配她的资源来防御潜在的目标，攻击者选择一个目标进行攻击。现有的工作已经假定防御者的资源集合是固定的。这个假设排除了近似算法的有效使用，因为防御者的分配策略的微小变化可能导致她的效用的巨大变化。相比之下，我们考虑一个模型，其中资源是以成本获得的，开始研究以下优化问题：最小化购买资源的总成本，给定每个目标必须至少有一定的概率进行防御。我们给出了一个有效的对数近似算法。
In recent years, algorithms for computing game-theoretic solutions have been developed for real-world security domains. These games are between a defender, who must allocate her resources to defend potential targets, and an attacker, who chooses a target to attack. Existing work has assumed the set of defender's resources to be fixed. This assumption precludes the effective use of approximation algorithms, since a slight change in the defender's allocation strategy can result in a massive change in her utility. In contrast, we consider a model where resources are obtained at a cost, initiating the study of the following optimization problem: Minimize the total cost of the purchased resources, given that every target has to be defended with at least a certain probability. We give an efficient logarithmic approximation algorithm for this problem.