Solving security games on graphs via marginal probabilities


Conference Paper

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 ( All rights reserved.

Duke Authors

Cited Authors

  • Letchford, J; Conitzer, V

Published Date

  • December 1, 2013

Published In

  • Proceedings of the 27th Aaai Conference on Artificial Intelligence, Aaai 2013

Start / End Page

  • 591 - 597

International Standard Book Number 13 (ISBN-13)

  • 9781577356158

Citation Source

  • Scopus