Security games with multiple attacker resources


Conference Paper

Algorithms for finding game-theoretic solutions are now used in several real-world security applications. This work has generally assumed a Stackelberg model where the defender commits to a mixed strategy first. In general two-player normal-form games, Stackelberg strategies are easier to compute than Nash equilibria, though it has recently been shown that in many security games, Stackelberg strategies are also Nash strategies for the defender. However, the work on security games so far assumes that the attacker attacks only a single target. In this paper, we generalize to the case where the attacker attacks multiple targets simultaneously. Here, Stackelberg and Nash strategies for the defender can be truly different. We provide a polynomial-time algorithm for finding a Nash equilibrium. The algorithm gradually increases the number of defender resources and maintains an equilibrium throughout this process. Moreover, we prove that Nash equilibria in security games with multiple attackers satisfy the interchange property, which resolves the problem of equilibrium selection in such games. On the other hand, we show that Stackelberg strategies are actually NP-hard to compute in this context. Finally, we provide experimental results.

Full Text

Duke Authors

Cited Authors

  • Korzhyk, D; Conitzer, V; Parr, R

Published Date

  • December 1, 2011

Published In

Start / End Page

  • 273 - 279

International Standard Serial Number (ISSN)

  • 1045-0823

International Standard Book Number 13 (ISBN-13)

  • 9781577355120

Digital Object Identifier (DOI)

  • 10.5591/978-1-57735-516-8/IJCAI11-056

Citation Source

  • Scopus