Security - Teamcore Research Group

Research on game theory for security

Motivation

Security at major locations of economic or political importance is a key concern around the world, particularly given the threat of terrorism. Limited security resources prevent full security coverage at all times, which allows adversaries to observe and exploit patterns in selective patrolling or monitoring, e.g. they can plan an attack avoiding existing patrols. Hence, randomized patrolling or monitoring is important, but randomization must provide distinct weights to different actions based on their complex costs and benefits, as well as adversary reactions.

Game theory provides us a framework to take all the costs and benefits into consideration, including adversary reactions, and provide a randomized schedule. While our ARMOR program, based on game theoretic foundations has been deployed at LAX international airport since August 2007, IRIS provides randomized schedules for the Federal Air Marshals and is in use as of October 2009 (for some sectors of international destinations). We have successfully demonstrated PROTECT at the Port of Boston and next we plan to apply PROTECT in the Port of New York. In addition, our GUARDS program is being evaluated by the Transportation Security Administration (TSA) at the Pittsburgh and LAX airports. Also we have started working on TRUSTS which would be used for LA Metro subway system to design randomized patrol strategies.

Fundamentally, we are focused on the research challenges in these efforts, marrying these applications with research on topics such as (i) fast algorithms for solving massive-scale games; (ii) behavioral game theory research for addressing human adversaries who may act with bounded rationality and imperfect observations; (iii) understanding the impact of players' limited observations on solution approaches adopted. We list the main research papers below and also some of our project application areas.

Overview of security research projects

PROTECT is planned to be used by the
Coast Guard Sector Boston

Research Challenges

Overview

Security and Game Theroy
Algorithms, Deployed Systems, Lessons Learned

By Milind Tambe

Tutorial at the International Conference on Uncertainty in Artificial Intelligence

Security and Game Theory: A challenge problem for multiagent researchers

Overview challenge paper :

Game Theory for Security: A Real-World Challenge Problem for Multiagent Systems and Beyond
By Milind Tambe, Bo An

Current Projects

IRIS: Agent Security for the Federal Air Marshals (In use by FAMS since October 2009)

With approximately 29,000 commercial flights per day in United States airspace, the Federal Air Marshal Service (FAMS) prioritizes allocation of resources based on risk. The current process follows the FAMS Concept of Operations and the DHS risk methodology by assigning FAM deployments based on consequence, vulnerability and threat. FAMS continually looks for process improvements to most efficiently mitigate the risks from the highest risk flights. One process improvement FAMS is currently examining is the ARMOR application. This application could aid FAMS in applying randomness in selection of a set of high risk flights to increase terrorist uncertainty of FAMS deployments.

IRIS is in use in limited international sectors by the Federal Air Marshal Service.

Please visit the project page for more details.

GUARDS: Transportation Security Administration (Currently in Pilot evaluation phase)

The Transportation Security Administration (TSA) is currently evaluating the application of GUARDS game theoretic scheduler for use in scheduling airport security operations. TSA has begun to evaluate application of GUARDS.

PROTECT: Port Resilience Operational / Tactical Enforcement to Combat Terrorism Model (In use by US Coast Guard since 2011)

We have successfully demonstrated PROTECT at the Port of Boston and next we plan to apply PROTECT in the Port of New York.

TRUSTS: Tactical Randomization for Urban Security in Transit Systems

In many urban transit networks including the LA Metro subway system, there are no ticket-checking gates at the stations. With approximately 80,000 riders using the LA Metro subway system daily, fare evasion can potentially lead to large amount of revenue loss. The LA Sheriffs Department deploys patrol units on board trains and at stations for fare-checking and crime-prevention. Our goal is to design randomized patrol strategies that efficiently utilize limited resources to deter fare-evasion.

ARMOR: Assistant for Randomized Monitoring Over Routes (In use at LAX since 2007)

The ARMOR software casts the above patrolling/monitoring problem as a Bayesian Stackelberg game, allowing the agent to appropriately weigh the different actions in randomization, as well as uncertainty over adversary types. ARMOR combines three key features:

It uses the fastest known solver for Bayesian Stackelberg games called DOBSS (Decomposed Optimal Bayesian Stackelberg Solver, where the dominant mixed strategies enable randomization
Its mixed-initiative based interface allows users to occasionally adjust or override the automated schedule based on their local constraints
It alerts users if mixed-initiative overrides appear to degrade the overall desired randomization

ARMOR has been sucessfully deployed since August 2007 at the Los Angeles International Airport (LAX) to randomize checkpoints on the roadways entering the airport and canine patrol routes within the airport terminals.

Please visit the project page for more details.

FOX coverage of ARMOR Security at the Los Angeles International Airport

FOX coverage of ARMOR at the Los Angeles International Airport

Publications

Title	Author	Published At	Year
An Overview of Recent Application Trends at the AAMAS conference: Security, Sustainability and Safety	Manish Jain, Bo An, Milind Tambe	AI Magazine (to appear)	2012
Deployed Security Games for Patrol Planning	Fernando Ordonez, Milind Tambe, Juan F. Jara, Manish Jain, Christopher Kiekintveld, Jason Tsai	Handbook on Operations Research for Homeland Security (Book chapter)(edited by J. Herrmann)	2012
Adversarial Patrolling Games	Yevgeniy Vorobeychik, Bo An, Milind Tambe	AAAI Spring Symposium on Security, Sustainability and Health	2012
Game Theory and Human Behavior: Challenges in Security and Sustainability	Rong Yang, Milind Tambe, Manish Jain, Jun-young Kwak, James Pita, and Zhengyu Yin	Algorithmic Decision Theory (ADT)	2011
Refinement of Strong Stackelberg Equilibria in Security Games	Bo An, Milind Tambe, Fernando Ordonez, Eric Shieh and Christopher Kiekintveld	Conference on Artificial Intelligence (AAAI)	2011
Addressing Execution and Observation Error in Security Games	Manish Jain, Zhengyu Yin, Milind Tambe and Fernando Ordonez	AAAI'11 Workshop on Applied Adversarial Reasoning and Risk Modeling (AARM)	2011
Toward Addressing Human Behavior with Observational Uncertainty in Security Games	James Pita, Rong Yang, Milind Tambe, Richard John	AAAI'11 Workshop on Applied Adversarial Reasoning and Risk Modeling (AARM)	2011
Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned	Milind Tambe	Cambridge University Press	2011
Game Theory and Human Behavior: Challenges in Security and Sustainability	Rong Yang, Milind Tambe, Manish Jain, Jun-young Kwak, James Pita, and Zhengyu Yin	Algorithmic Decision Theory (ADT)	2011
Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness	Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe	Journal of AI Research (JAIR)	2011
Risk-Averse Strategies for Security Games with Execution and Observational Uncertainty	Zhengyu Yin, Manish Jain, Milind Tambe and Fernando Ordonez	Conference on Artificial Intelligence (AAAI)	2011
Improving Resource Allocation Strategy Against Human Adversaries in Security Games	Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe and Richard John	International Joint Conference on Artificial Intelligence (IJCAI)	2011
GUARDS - Innovative Application of Game Theory for National Airport Security	James Pita, Milind Tambe, Christopher Kiekintveld, Shane Cullen and Erin Steigerwald	International Joint Conference on Artificial Intelligence (IJCAI)	2011
GUARDS - Game Theoretic Security Allocation on a National Scale	James Pita, Milind Tambe, Chris Kiekintveld, Shane Cullen and Erin Steigerwald	AAMAS, Best paper for Innovative Application Track	2011
A Double Oracle Algorithm for Zero-Sum Security Games on Graphs	Manish Jain, Dmytro Korzhyk, Ondrej Vanek, Vincent Conitzer, Michal Pechoucek and Milind Tambe	International Conference on Autonomous Agents and Multiagent Systems	2011
GUARDS and PROTECT: Next Generation Applications of Security Games	Bo An, James Pita, Eric Shieh, Milind Tambe, Christopher Kiekintveld and Janusz Marecki	ACM SIGecom	2011
Improved Computational Models of Human Behavior in Security Games	Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe and Richard John	International Conference on Autonomous Agents and Multiagent Systems	2011
Quality-bounded Solutions for Finite Bayesian Stackelberg Games: Scaling up	Manish Jain, Milind Tambe and Christopher Kiekintveld	International Conference on Autonomous Agents and Multiagent Systems	2011
Mixed-Initiative Optimization in Security Games: A Preliminary Report	Bo An, Manish Jain, Milind Tambe, Christopher Kiekintveld	AAAI Spring Symposium on Help me help you:Bridging the Gaps in Human-Agent Collaboration	2011
Software Assistants for Randomized Patrol Planning for the LAX Airport Police and the Federal Air Marshals Service	Manish Jain, Jason Tsai, James Pita, Christopher Kiekintveld, Shyamsunder Rathi, Fernando Ordonez, Milind Tambe	Interfaces, Nominated for European Excellence in Practice Award, EURO 2010	2010
Security Games with Arbitrary Schedules: A Branch and Price Approach	Manish Jain, Erim Kardes, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe	National Conference on Artificial Intelligence (AAAI)	2010
Stackelberg vs. Nash in Security Games: Interchangeability, Equivalence, and Uniqueness	Zhengyu Yin, Dmytro Korzhyk, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe	International Conference on Autonomous Agents and Multiagent Systems (AAMAS)	2010
Urban Security: Game-Theoretic Resource Allocation in Networked Physical Domains	Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe, Christopher Kiekintveld, Milind Tambe	National Conference on Artificial Intelligence (AAAI)	2010
Effective Solutions for Real-World Stackelberg Games: When Agents Must Deal with Human Uncertainties	James Pita, Manish Jain, Fernando Ordóñez, Milind Tambe	AAMAS	2009
Computing Optimal Randomized Resource Allocations for Massive Security Games	Christopher Kiekintveld, Manish Jain, Jason Tsai,James Pita, Fernando Ordóñez, and Milind Tambe	AAMAS	2009
Efficient Algorithms to solve Bayesian Stackelberg Games for Security Applications	Praveen Paruchuri, Jonathan P. Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, Sarit Kraus	AAAI	2008
Playing Games for Security: An Efficient Exact Algorithm for Solving Bayesian Stackelberg Game	Jonathan P. Pearce,Janusz Marecki, Milind Tambe, Fernando Ordonez, Praveen Paruchuri and Sarit Kraus	AAMAS	2008
Robust Solutions in Stackelberg Games: Addressing Boundedly Rational Human Preference Models	Manish Jain, Fernando Ord´o˜ nez, James Pita, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, Sarit Kraus	AAAI	2008
An Efficient Heuristic Approach for Security Against Multiple Adversaries	Praveen Paruchuri, Jonathan P. Pearce, Milind Tambe, Fernando Ordonez, Sarit Kraus	AAMAS	2007
Security in Multiagent Systems by Policy Randomization	Praveen Paruchuri, Milind Tambe, Fernando Ordonez, Sarit Kraus	AAMAS	2006

Key personnel

Principal Investigator:

Milind Tambe

Current team working on Game Theory and Security Projects:

Bo An, James Pita, Manish Jain, Zhengyu Yin, Eric Shieh, Rong Yang, Matthew Johnson, Andrew Jiang, Fei Fang, Thanh Nguyen, Parth Shah, Rajiv Maheswaran, Dana Li, Andrew Deeds

Alumni Collaborators:

Praveen Paruchuri, Janusz Marecki, Christopher Portway, Shyamsunder Rathi, Harish Kumar Bellamane,

Bharat Patel, Craig Western, Chris Kiekintveld, Mohit Goenka

Other Collaborators at USC and Elsewhere:

Fernando Ordonez (USC), Vincent Conitzer (Duke), Richard John (USC), Sarit Kraus (Bar Ilan), Michal Pechoucek (CTU),
Dima Korzhyk (Duke), Ondra Vanek (CTU)

These projects are funded by the USC Homeland Security Center (CREATE).

[If you have any questions about the contents of this page, please contact Parth Shah at parthpas@usc.edu ]