Security at major locations of economic or political importance or transportation or other infrastructure is a key concern around the world, particularly given the threat of terrorism. Limited security resources prevent full security coverage at all times; instead, these limited resources must be deployed intelligently taking into account differences in priorities of targets requiring security coverage, the responses of the adversaries to the security posture and potential uncertainty over the types of adversaries faced.

Game theory is well-suited to adversarial reasoning for security resource allocation and scheduling problems because it suggests randomized policies that mitigate a key vulnerability of human plans: predictability. Casting the problem as a Bayesian Stackelberg game, we have developed new algorithms for efficiently solving such games to provide randomized patrolling or inspection strategies; our algorithms are now deployed in multiple applications. ARMOR (Assistant for Randomized Monitoring over Routes), our first game theoretic application, has been deployed at the Los Angeles International Airport (LAX) since August 2007 to randomizes checkpoints on the roadways entering the airport and canine patrol routes within the airport terminals. IRIS, our second application, is a game-theoretic scheduler for randomized deployment of the Federal Air Marshals (FAMS) requiring significant scale-up in underlying algorithms; IRIS was put into use to generate schedules in late 2009. Finally, GUARDS has been deployed by the TSA (Transportation Security Administration) at the Pittsburgh and LAX airports starting October 2009 for pilot evaluation with a goal of large-scale deployments across multiple airports. These applications are leading to real-world use-inspired research. This talk will outline our algorithms (often based on techniques borrowed from operations research), key research results and lessons learned.

(*) This is joint work with my PhD students (Manish Jain, James Pita, Jason Tsai, Zhengyu Yin, Praveen Paruchuri), postdoctoral researchers (Chris Kiekintveld, Erim Kardes), key faculty collaborators at USC(Fernando Ordonez, David Kempe) and at other universities (Sarit Kraus, Vince Conitzer), and a team of undergraduate and MS students.

http://teamcore.usc.edu/tambe