Skip to main content

Solving security games on graphs via marginal probabilities

Publication ,  Conference
Letchford, J; Conitzer, V
Published in: Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013
December 1, 2013

Security games involving the allocation of multiple security resources to defend multiple targets generally have an exponential number of pure strategies for the defender. One method that has been successful in addressing this computational issue is to instead directly compute the marginal probabilities with which the individual resources are assigned (first pursued by Kiekintveld et al. (2009)). However, in sufficiently general settings, there exist games where these marginal solutions are not implementable, that is, they do not correspond to any mixed strategy of the defender. In this paper, we examine security games where the defender tries to monitor the vertices of a graph, and we show how the type of graph, the type of schedules, and the type of defender resources affect the applicability of this approach. In some settings, we show the approach is applicable and give a polynomial-time algorithm for computing an optimal defender strategy; in other settings, we give counterexample games that demonstrate that the approach does not work, and prove NP-hardness results for computing an optimal defender strategy. Copyright © 2013, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Duke Scholars

Published In

Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013

ISBN

9781577356158

Publication Date

December 1, 2013

Start / End Page

591 / 597
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Letchford, J., & Conitzer, V. (2013). Solving security games on graphs via marginal probabilities. In Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013 (pp. 591–597).
Letchford, J., and V. Conitzer. “Solving security games on graphs via marginal probabilities.” In Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013, 591–97, 2013.
Letchford J, Conitzer V. Solving security games on graphs via marginal probabilities. In: Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013. 2013. p. 591–7.
Letchford, J., and V. Conitzer. “Solving security games on graphs via marginal probabilities.” Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013, 2013, pp. 591–97.
Letchford J, Conitzer V. Solving security games on graphs via marginal probabilities. Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013. 2013. p. 591–597.

Published In

Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013

ISBN

9781577356158

Publication Date

December 1, 2013

Start / End Page

591 / 597