Approximation Algorithm for Security Games with Costly Resources


<p><a href="">Sayan Bhattacharya</a><br /> Duke University<br /> Department of Computer Science<br /> N303, North Building<br /> 304 Research Drive<br /> Durham, NC 27708<br /> United States of America</p>


Tuesday, 29 November 2011, 16:00 to 17:00


  • A-212 (STCS Seminar Room)

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 (joint work with Vincent Conitzer and Kamesh Munagala).