Computing Optimal Randomized Resource Allocations for Massive Security Games

Predictable allocations of security resources such as police offi-cers, canine units, or checkpoints are vulnerable to exploitation by attackers. Recent work has applied game-theoretic methods to find optimal randomized security policies, including a fielded application at the Los Angeles International Airport (LAX). This approach has promising applications in many similar domains, in-cluding police patrolling for subway and bus systems, randomized baggage screening, and scheduling for the Federal Air Marshal Ser-vice (FAMS) on commercial flights. However, the existing meth-ods scale poorly when the security policy requires coordination of many resources, which is central to many of these potential appli-cations. We develop new models and algorithms that scale to much more complex instances of security games. The key idea is to use a com-pact model of security games, which allows exponential improve-ments in both memory and runtime relative to the best known al-gorithms for solving general Stackelberg games. We develop even faster algorithms for security games under payoff restrictions that are natural in many security domains. Finally, introduce additional realistic scheduling constraints while retaining comparable perfor-mance improvements. The empirical evaluation comprises both random data and realistic instances of the FAMS and LAX prob-lems. Our new methods scale to problems several orders of magni-tude larger than the fastest known algorithm