In Proceedings of the Twelfth International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2013).
This is the author's version of the work.
Download
Abstract
Security games provide a framework for allocating limited security
resources in adversarial domains, and are currently used in deployed
systems for LAX, the Federal Air Marshals, and the U.S.
Coast Guard. One of the major challenges in security games is finding
solutions that are robust to uncertainty about the game model.
Bayesian game models have been used to model uncertainty, but algorithms
for these games do not scale well enough for many applications.
We take an alternative approach based on using intervals to
model uncertainty in security games. We present a fast polynomial
time algorithm for security games with interval uncertainty, which
represents the first viable approach for computing robust solutions
to very large security games. We also introduce a methodology for
using intervals to approximate solutions to infinite Bayesian games
with distributional uncertainty. Our experiments show that intervals
can be an effective approach for these more general Bayesian
games; our algorithm is faster and results in higher quality solutions
than previous methods.
