Tata Institute of Fundamental Research

Approximation Algorithm for Security Games with Costly Resources

Speaker: Sayan Bhattacharya Duke University Department of Computer Science N303, North Building 304 Research Drive Durham, NC 27708 United States of America
Date: Tuesday, 29 Nov 2011, 16:00 to 17:00
Venue: A-212 (STCS Seminar Room)

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