Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games
Publication
, Conference
Korzhyk, D; Conitzer, V; Parr, R
Published in: Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010
July 15, 2010
Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (security personnel) can commit to a mixed strategy, a so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), in these applications, generally, multiple resources need to be assigned to multiple targets, resulting in an exponential number of pure strategies for the defender. In this paper, we study how to compute optimal Stackelberg strategies in such games, showing that this can be done in polynomial time in some cases, and is NP-hard in others.
Duke Scholars
Published In
Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010
Publication Date
July 15, 2010
Start / End Page
805 / 810
Citation
APA
Chicago
ICMJE
MLA
NLM
Korzhyk, D., Conitzer, V., & Parr, R. (2010). Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games. In Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010 (pp. 805–810).
Korzhyk, D., V. Conitzer, and R. Parr. “Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games.” In Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010, 805–10, 2010.
Korzhyk D, Conitzer V, Parr R. Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010. 2010. p. 805–10.
Korzhyk, D., et al. “Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games.” Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010, 2010, pp. 805–10.
Korzhyk D, Conitzer V, Parr R. Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games. Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010. 2010. p. 805–810.
Published In
Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010
Publication Date
July 15, 2010
Start / End Page
805 / 810