Conference articles PUBLISHED

1. Bhattacharya, S; Conitzer, V; Munagala, K, Approximation algorithm for security games with costly resources, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7090 LNCS (January, 2011), pp. 13-24 [doi].
   (last updated on 2024/04/24)

   Abstract:
   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. © 2011 Springer-Verlag Berlin Heidelberg.