Quality-bounded Solutions for Finite Bayesian Stackelberg
Games: Scaling up
M Jain, C Kiekintveld, and M Tambe
In Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011).
This is the author's version of the work.
It is posted here by permission of IFAAMAS for personal use, not for redistribution.
Download
Abstract
The fastest known algorithm for solving General Bayesian Stackelberg
games with a finite set of follower (adversary) types have seen
direct practical use at the LAX airport for over 3 years; and currently,
an (albeit non-Bayesian) algorithm for solving these games
is also being used for scheduling air marshals on limited sectors
of international flights by the US Federal Air Marshals Service.
These algorithms find optimal randomized security schedules to allocate
limited security resources to protect targets. As we scale up
to larger domains, including the full set of flights covered by the
Federal Air Marshals, it is critical to develop newer algorithms that
scale-up significantly beyond the limits of the current state-of-theart
of Bayesian Stackelberg solvers. In this paper, we present a
novel technique based on a hierarchical decomposition and branch
and bound search over the follower type space, which may be applied
to different Stackelberg game solvers. We have applied this
technique to different solvers, resulting in: (i) A new exact algorithm
called HBGS that is orders of magnitude faster than the best
known previous Bayesian solver for general Stackelberg games;
(ii) A new exact algorithm called HBSA which extends the fastest
known previous security game solver towards the Bayesian case;
and (iii) Approximation versions of HBGS and HBSA that show
significant improvements over these newer algorithms with only 1-
2% sacrifice in the practical solution quality.
