Game theory has played an important role in security decisions. Recent work using
Stackelberg games [Fudenberg and Tirole 1991] to model security domains has been
particularly influential [Basilico et al. 2009; Kiekintveld et al. 2009; Paruchuri et al.
2008; Pita et al. 2008; Pita et al. 2009]. In a Stackelberg game, a leader (in this case
the defender) acts first and commits to a randomized security policy. The follower
(attacker) optimizes its reward considering the strategy chosen by the leader. These
games are well-suited to representing the problem security forces face in allocating
limited resources, such as officers, canine units, and checkpoints. In particular, the
fact that the attacker is able to observe the policy reflects the way real terrorist
organizations plan attacks using extensive surveillance and long planning cycles.
Stackelberg game models are not just theoretical models; they are at the heart of
deployed decision-support software now in use the the Los Angeles World Airport
(LAWA) police and the United States Federal Air Marshals Service (FAMS). A new
application is under development for the Transportation Security Administration
(TSA), also using game-theoretic analysis. Moving from theoretical analysis to
applying game theory in real applications posed many new challenged, and there
remain many open questions to be solved in this exciting area of work. In this
article we will highlight several of the main issues that have come up, including
(i) developing efficient algorithms to solve large-scale Stackelberg Security Games,
(ii) evaluating deployed security systems, (iii) knowledge acquisition from security
experts to specify the game models, and (iv) handling mixed-initiative interactions.
We begin with an overview of the deployed systems and then discuss these issues