|
| Publications [#236184] of Vincent Conitzer
Conference articles PUBLISHED
- Letchford, J; Conitzer, V, Solving security games on graphs via marginal probabilities, edited by desJardins, M; Littman, ML,
Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013
(December, 2013),
pp. 591-597, AAAI Press, ISBN 9781577356158 [php]
(last updated on 2024/04/23)
Abstract:
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.
|
