Provide students an in-depth understanding of the area of “Security Games?or use of
game theory for security.
Security remains a global challenge: limited security resources must be deployed to
protect ports, airports, and other critical national infrastructure, to suppress crime in
urban areas as well as to protect forests and wildlife, and to curtail the illegal flow of
drugs, weapons and money. Security challenges also include protection of networks
including cyber, rail, road or maritime transportation networks, blocking contagion of
radicalism in social networks, and others. Yet, given limited security resources, these
resources cannot be everywhere all the time, raising a crucial question of how to best use
Game theory provides a sound mathematical approach to deploy limited security
resources to maximize their effectiveness. There has thus been a very significant focus on
game theory for security and publications focused on this topic have seen a very rapid
increase. This course is intended to provide students an introduction to this growing area
of game theory for security, including an in-depth understanding of key research
My research group has been at the forefront of this research, and we are the first and
currently the only research group that has led to a wide range of actual deployed
applications of game theory for security. Our first application, ARMOR, deployed game
theory in practice at the Los Angeles International Airport (LAX) since August 2007; in
particular, it uses game theory to randomize allocation of police checkpoints and canine
units. Our second application, IRIS, is used by the Federal Air Marshal Service to deploy
air marshals on US air carriers and has been in use since 2009. A third application,
PROTECT, for the US Coast Guard is in use in the ports of Boston and New York for
planning patrols, and getting evaluated for a national deployment across all ports. There
are many other applications being deployed by a variety of security agencies including
the LA Sheriff’s department, the TSA and others.
This set of applications and associated algorithms has caused an explosion of interest in
applying game theory for security. Indeed, these applications are leading to real-world
use-inspired research in the emerging research area of “security games? specifically, the
research challenges posed by these applications include scaling up security games
to large-scale problems, handling significant adversarial uncertainty, dealing with
bounded rationality of human adversaries, and other interdisciplinary challenges. Several
research groups in many different universities in the US and elsewhere are now pursuing
this research, as evidenced by the increasing numbers of papers focused on game theory
for security over the past 6 years. “Security games?is now a thriving area of research.
This CS599 course is intended to provide students with an in-depth understanding of
“Security games?--- this growing, thriving area of research.
The syllabus will include a combination of:
“Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned?
By Milind Tambe, Cambridge University Press, 2011
Key papers will be emailed out in advance.
Some notes handed out during class
Schedule of Classes
CS 599: Security and Game Theory
Italics indicates homework reading for students. Chapter numbers refer to chapters of
“Security and Game Theory?
Lecture 1: Course intro, syllabus, goals, key concepts: basic decision theory, basic
Handout: Basic decision theory
Lecture 2: Chapter 1: Introduction and overview of security games
Lecture 3: Chapter 2: Introduction to problems of security: Erroll Southers or
Handout: Introduction to game theory
Lecture 4: Normal form games, Dominance, iterative dominance, Nash
equilibrium; Mixed strategy Nash equilibrium, Stackelberg games, security games
Handout: Linear programming
Lecture 5: Chapter 8 (up to 8.4): Introduction to Linear Programming, Integer
programming, solving security games, marginals, ERASER, Sampling
Homework: Excel solver; other tools
Handout: Bayesian games; games of incomplete and imperfect information
Lecture 6: Extensive form games,
Subgame perfect Nash equilibrium, Bayesian
games, games of incomplete information and imperfect information, Harsanyi
Lecture 7: Continued with Bayesian games
Students form teams to read the following chapters and present in class:
Chapter 4: J. Pita, M. Jain, C. Western, P. Paruchuri, J. Marecki, M. Tambe, F.
Ordonez, S. Kraus Deployed ARMOR Protection: The Application of a Game
Theoretic Model for Security at the Los Angeles International Airport
Chapter 5: J. Tsai, S. Rathi, C. Kiekintveld, M. Tambe, F. Ordonez IRIS: A tool
for strategic security allocation in transportation networks
Chapter 6: J. Pita, C. Kiekintveld, M. Tambe, E. Steigerwald, S. Cullen GUARDS
- Game Theoretic Security Allocation on a National Scale
Papers on other new applications developed for the US Coast Guard and the LA
Sheriff’s Dept respectively
Lecture 8: Student presentations in class (multiple teams).
Lecture 11: Chapter 10: Emotions, behavioral game theory research
R. Yang, C. Kiekintveld, R. John, F. Ordonez, M. Tambe Improving Resource
Allocation Strategy Against Human Adversaries in Security Games In
Proceedings of the International Joint Conference on Artificial Intelligence
(IJCAI), July 2011
J. Pita, R. Maheswaran, M. Tambe, S. Kraus A Robust Approach to Addressing
Human Adversaries in Security Games In Proceedings of the European
Conference on Artificial Intelligence (ECAI), August 2012.
Lecture 12: Yang et al IJCAI?1, Pita et al ECAI 12, Quantal response
Lecture 13: Chapter 3: Guest lecture: US Coast Guard
R. Yang, M. Tambe, F. Ordonez Computing Optimal Strategy against Quantal
Response in Security Games In Proceedings of the International Conference on
Autonomous Agents and Multiagent Systems
(AAMAS), June 2012.
E. Shieh, R. Yang, B. An, M. Tambe, C. Baldwin, J. DiRenzo, B. Maule, G. Meyer
PROTECT: A Deployed Game Theoretic System to Protect the Ports of the United
States In Proceedings of the International Conference on Autonomous Agents and
Multiagent Systems (AAMAS)(Innovative applications track), June 2012.
Lecture 14: PROTECT, latest research on game theory for security US Coast
Lecture 15: Chapter 12: Frontiers of security game theory research: Stackelberg
Chapter 13: M.E. Taylor, C.Kiekintveld, M. Tambe Evaluating Deployed Decision
Support Systems for Security: Challenges, Analysis and Approaches
Lecture 16: Student project ideas presentation, discussion and feedback
Lecture 17: Chapter 9: Column generation, application in solving large scale
games such as for the FAMS
M.P. Johnson, F. Fang, M. Tambe, H.J. Albers Patrol Strategies to Maximize
Pristine Forest Area In Proceedings of the Conference on Artificial Intelligence
(AAAI) (Computational Sustainability Track), July 2012.
Lecture 18: Spatio-temporal game theory: Protecting multiple mobile targets and
with multiple patrollers; forest protection
Lecture 19: Results of Homework, Review before midterm
Lecture 20: Midterm I
Lecture 21: Cybersecurity (Guest lecture)
O. Vanek, Z. Yin, M. Jain, B. Bosansky, M. Pechoucek, M. Tambe Game-theoretic
Resource Allocation for Malicious Packet Detection in Computer Networks In
Proceedings of the International Conference on Autonomous Agents and
Multiagent Systems (AAMAS), June 2012.
Lecture 22: Cyber applications, contagion:
Lecture 23: Double oracle approach for solving large scale games
J. Tsai, T. Nguyen, M. Tambe Security Games for Controlling Contagion In
Proceedings of the Conference on Artificial Intelligence (AAAI), July 2012.
Lecture 24: Security games for controlling contagion of beliefs, ideas, with
applications in health and security; Tsai et al, AAAI?2
Lecture 25: Invited lecture: Richard John (human behavior and game theory)
Lecture 26: Final project presentations
Lecture 27: Invited lecture: LA Sheriff’s dept or LAX airport
Lecture 28: Final Quiz
Schedule of Assignments and Exams
Paper presentation, discussion:(5%)
Homework I: (15%)
Midterm project ideas and discussion: (5%)
Homework II: (10%)
Final quiz: (10%)
Homework assignments must be done individually; only the project can be done in a team.
Statement for Students with Disabilities
Any student requesting academic accommodations based on a disability is required to
register with Disability Services and Programs (DSP) each semester. A letter of
verification for approved accommodations can be obtained from DSP. Please be sure the
letter is delivered to me (or to TA) as early in the semester as possible.
DSP is located in STU 301 and is open 8:30 a.m.?:00 p.m., Monday through Friday. Website and contact
information for DSP:
(213) 740-0776 (Phone), (213) 740-6948 (TDD only), (213) 740-8216 (FAX) firstname.lastname@example.org.
Statement on Academic Integrity
USC seeks to maintain an optimal learning environment. General principles of academic
honesty include the concept of respect for the intellectual property of others, the
expectation that individual work will be submitted unless otherwise allowed by an
instructor, and the obligations both to protect one’s own academic work from misuse by
others as well as to avoid using another’s work as one’s own. All students are expected to
understand and abide by these principles. SCampus, the Student Guidebook,
(http://www.usc.edu/scampus or http://scampus.usc.edu) contains the University Student
Conduct Code (see University Governance, Section 11.00), while the recommended
sanctions are located in Appendix A.
Emergency Preparedness/Course Continuity in a Crisis
In case of a declared emergency if travel to campus is not feasible, USC executive
leadership will announce an electronic way for instructors to teach students in their
residence halls or homes using a combination of Blackboard, teleconferencing, and other