Approximation algorithm for security games with costly resources

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Bhattacharya, S; Conitzer, V; Munagala, K

Published Date

  • January 1, 2011

Published In

Volume / Issue

  • 7090 LNCS /

Start / End Page

  • 13 - 24

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783642255090

Digital Object Identifier (DOI)

  • 10.1007/978-3-642-25510-6_2

Citation Source

  • Scopus