Approximation Algorithm for Security Games with Costly Resources

Sayan Bhattacharya Duke University Department of Computer Science N303, North Building 304 Research Drive Durham, NC 27708 United States of America
Tuesday, 29 Nov 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).