# 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