Security is a critical concern around the world that arises in
protecting our ports, airports, transportation and other critical national infrastructure from adversaries, in protecting our wildlife
and forests from poachers and smugglers, and in curtailing the illegal flow of weapons, drugs and money; and it arises in problems
ranging from physical to cyber-physical systems. In all of these
problems, we have limited security resources which prevent full
security coverage at all times; instead, security resources must be
deployed intelligently taking into account differences in priorities of targets requiring security coverage, the responses of the attackers to the security posture, and potential uncertainty over the
types, capabilities, knowledge and priorities of attackers faced.
Game theory, which studies interactions among multiple selfinterested agents, is well-suited to the adversarial reasoning required for security resource allocation and scheduling problems.
Casting the problem as a Bayesian Stackelberg game, we have
developed new algorithms for efficiently solving such games that
provide randomized patrolling or inspection strategies. These algorithms have led to some initial successes in this challenging
problem arena, leading to advances over previous approaches in
security scheduling and allocation, e.g., by addressing key weaknesses of predictability of human schedulers. These algorithms
are now deployed in multiple applications: ARMOR has been
deployed at the Los Angeles International Airport (LAX) since
2007 to randomize checkpoints on the roadways entering the airport and canine patrol routes within the airport terminals ;
IRIS, a game-theoretic scheduler for randomized deployment of
the US Federal Air Marshals (FAMS) requiring significant scaleup in underlying algorithms, has been in use since 2009 ;
PROTECT, which schedules the US Coast Guard’s randomized
patrolling of ports using a new set of algorithms based on modeling bounded-rational human attackers, has been deployed in the port of Boston since April 2011 and is in use at the port of New
York since February 2012 , and is headed for nationwide deployment; another application for deploying escort boats to protect ferries has been deployed by the US Coast Guard since April
2013 ; GUARDS is under evaluation for national deployment
by the US Transportation Security Administration (TSA) ,
and TRUSTS  has been evaluated in field trials by the Los Angeles Sheriffs Department (LASD) in the LA Metro system and
a nation-wide deployment is now being evaluated at TSA. These
initial successes point the way to major future applications in a
wide range of security domains; with major research challenges
in scaling up our game-theoretic algorithms, in addressing human
adversaries’ bounded rationality and uncertainties in action execution and observation, as well as in multiagent learning.
This paper will provide an overview of the models and algorithms, key research challenges and a brief description of our successful deployments.