  Stackelberg Security Games (SSGs) have been adopted widely for modeling
adversarial interactions. With increasing size of the applications of SSGs,
scalability of equilibrium computation is an important research problem. While
prior research has made progress with regards to scalability, many real world
problems cannot be solved satisfactorily yet as per current requirements; these
include the deployed federal air marshals (FAMS) application and the threat
screening (TSG) problem at airports. Further, these problem domains are
inherently limited by NP hardness shown in prior literature. We initiate a
principled study of approximations in zero-sum SSGs. Our contribution includes
the following: (1) a unified model of SSGs called adversarial randomized
allocation (ARA) games that allows studying most SSGs in one model, (2)
hardness of approximation results for zero-sum ARA, as well as for the
sub-problem of allocating federal air marshal (FAMS) and threat screening
problem (TSG) at airports, (3) an approximation framework for zero-sum ARA with
provable approximation guarantees and (4) experiments demonstrating the
significant scalability of up to 1000x improvement in runtime with an
acceptable 5% solution quality loss.
