Efficient Algorithms for Computing Stackelberg Strategies in Security Games
Abstract
Game theory provides a framework for modeling a wide range of security and defense problems. This project focuses on Stackelberg strategies, which are optimal when one player can commit to a (possibly randomized) strategy before the other player moves. For example, a defensive unit can commit to a randomized patrolling pattern to deter attacks. This project explores new approaches for efficiently computing Stackelberg strategies in realistic security domains with exponentially large strategy spaces. Potential impacts of this research include increased ability to compute optimal strategies for security and defense scenarios. Notable contributions of the project include: (1) New algorithms and complexity results for security games as well as unrestricted games. The algorithms allow us to solve new classes of games efficiently; the complexity results indicate that other methods are needed for richer classes of games. (2) A deeper understanding of the role of commitment and the assumption that the attacker can observe the defender's strategy. These results indicate that, in a sense, Stackelberg strategies are ``safe'' to play even when this assumption does not hold, in some security domains (but not all -- and to address this shortcoming, we also provide a methodology for other security games).
Document Details
- Document Type
- Technical Report
- Publication Date
- May 30, 2012
- Accession Number
- ADA580068
Entities
People
- Ronald Parr
- Vincent Conitzer
Organizations
- Duke University