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 deploy our limited security resources, taking into account factors such as target weights and adversary reactions, and provides "intelligently randomized" schedules. 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). Similarly PROTECT is in use by the US Coast Guard in the Ports of Boston and New York for generating intelligently randomized patrol strategies since 2011. Also we have started working on TRUSTS which is being evaluated by the LA Sheriff's department to design randomized patrol strategies for checking for fare evaders on LA's metro trains. In addition, our GUARDS program is being evaluated by the Transportation Security Administration (TSA).

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

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.

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.

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 ARMOR program to appropriately weigh the different actions in randomization taking into account different target weights, as well as the fact that the adversary will conduct surveillance, and the that there is uncertainty over adversary types.

According to Dr Milind Tambe, a tenured Professor at USC and the prime developer of ARMOR, the program was based on the fastest known solver for Bayesian Stackelberg games at that time called DOBSS (Decomposed Optimal Bayesian Stackelberg Solver), where the dominant mixed strategies enables the weighted randomization mentioned above. (Since the deployment of ARMOR, the USC CREATE team led by Dr. Tambe has continued to scale up their algorithms beyond DOBSS so the algorithms can handle much larger domains such as those presented by the US Coast Guard as well as address more of the uncertainties presented in such domains.)

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 for Security: A Real-World Challenge Problem for Multiagent Systems and Beyond	Milind Tambe, Bo An	AAAI Spring Symposium on Game Theory for Security, Sustainability and Health	2012
Challenges in Patrolling to Maximize Pristine Forest Area (Position Paper)	Matthew P. Johnson, Fei Fang, Rong Yang, Milind Tambe, Heidi Jo Albers	AAAI Spring Symposium on Game Theory for Security, Sustainability and Health	2012
Security Games with Limited Surveillance: An Initial Report	Bo An, David Kempe, Christopher Kiekintveld, Eric Shieh, Satinder Singh, Milind Tambe, Yevgeniy Vorobeychik	AAAI Spring Symposium on Game Theory for Security, Sustainability and Health	2012
PROTECT: A Deployed Game Theoretic System to Protect the Ports of the United States	Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer	International Conference on Autonomous Agents and Multiagent Systems (AAMAS)	2012
Towards Optimal Patrol Strategies for Fare Inspection in Transit Systems	Albert Xin Jiang, Zhengyu Yin, Matthew P. Johnson, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, Milind Tambe	AAAI Spring Symposium on Game Theory for Security, Sustainability and Health	2012
Multi-Objective Optimization for Security Games	Matthew Brown, Bo An, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe	International Conference on Autonomous Agents and Multiagent Systems (AAMAS)	2012
A Unified Method for Handling Discrete and Continuous Uncertainty in Bayesian Stackelberg Games	Zhengyu Yin, Milind Tambe	International Conference on Autonomous Agents and Multiagent Systems (AAMAS)	2012
Computing Optimal Strategy against Quantal Response in Security Games	Rong Yang, Fernando Ordonez, Milind Tambe	International Conference on Autonomous Agents and Multiagent Systems (AAMAS)	2012
Adversarial Patrolling Games: Extended Abstract	Yevgeniy Vorobeychik, Bo An, Milind Tambe	International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (Short paper)	2012
A Robust Approach to Addressing Human Adversaries in Security Games: Extended Abstract	James Pita, Richard John, Rajiv Maheswaran, Milind Tambe, Rong Yang, Sarit Kraus	International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (Short paper)	2012
Designing Better Strategies against Human Adversaries in Network Security Games: Extended Abstract	Rong Yang, Fei Fang, Albert Xin Jiang, Karthik Rajagopal, Milind Tambe, Rajiv Maheswaran	International Conference on Autonomous Agents and Multiagent Systems (AAMAS)(Short paper)	2012
Multi-Objective Optimization for Security Games	Matthew Brown, Bo An, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe	International Conference on Autonomous Agents and Multiagent Systems (AAMAS)	2012
Detection of Suspicious Behavior from a Sparse Set of Multiagent Interactions	Bostjan Kaluza, Gal Kaminka, Milind Tambe	International Confernce on Autonomous Agents and Multiagent Systems (AAMAS)	2012
Which Security Games are Hard to Solve?	Manish Jain, Kevin Leyton-Brown, Milind Tambe	AAAI Spring Symposium on Game Theory for Security, Sustainability and Health	2012
TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems	Zhengyu Yin, Albert Jiang, Matthew Johnson, Milind Tambe, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, John Sullivan	Conference on Innovative Applications of Artificial Intelligence (IAAI)	2012
Game Theory for Security: An Important Challenge for Multiagent Systems	Bo An, Milind Tambe	Proceedings of the European Workshop on Multiagent Systems (EUMAS) 2011 workshop (Invited)	2012
Security Games with Limited Surveillance	Bo An, David Kempe, Christopher Kiekintveld, Eric Shieh, Satinder Singh, Milind Tambe, Yevgeniy Vorobeychik	Conference on Artificial Intelligence (AAAI)	2012
PROTECT: An Application of Computational Game Theory for the Security of the Ports of the United States	Eric Shieh, Bo An, Rong Yang, Milind Tambe, Craig Baldwin, Joseph DiRenzo, Ben Maule, Garrett Meyer	Conference on Artificial Intelligence (AAAI) Spotlight Track	2012
Security Games for Controlling Contagion	Jason Tsai, Thanh H. Nguyen, Milind Tambe	Conference on Artificial Intelligence (AAAI)	2012
The Deployment-to-Saturation Ratio in Security Games	Manish Jain, Kevin Leyton-Brown, Milind Tambe	Conference on Artificial Intelligence (AAAI)	2012
Patrol Strategies to Maximize Pristine Forest Area	Matthew P. Johnson, Fei Fang, and Milind Tambe	Conference on Artificial Intelligence (AAAI)	2012
Modeling Human Bounded Rationality to Improve Defender Strategies in Network Security Games	Rong Yang, Fei Fang, Albert Xin Jiang, Karthik Rajagopal, Milind Tambe, Rajiv Maheswaran	Workshop on Human-Agent Interaction Design and Models (HAIDM) at AAMAS	2012
Designing Patrol Strategies to Maximize Pristine Forest Area	Matthew P Johnson, Fei Fang, Milind Tambe, H. J. Albers	Workshop on Optimization in Multiagent Systems (OPTMAS) at AAAMS	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 ]