AAMAS2011

security games tutorial

 
 

Overview

Game theory is an increasingly important paradigm for modeling and decision-making in security domains, including homeland security resource allocation decisions, robot patrolling strategies, and computer network security. Several deployed real-world systems use game theory to randomize critical security decisions to prevent terrorist adversaries from exploiting a predictable security schedule. The ARMOR system deployed at the LAX airport and the IRIS system deployed by the Federal Air Marshals Service were first presented at the AAMAS conference.

This tutorial will introduce a wide variety of game-theoretic modeling techniques and algorithms that have been developed in recent years for security problems. Introductory material on game theory and mathematical programming (optimization) will be included in the tutorial, so there is no prerequisite knowledge for participants. After introducing the basic security game framework, we will describe algorithms for scaling to very large games, methods for modeling uncertainty and attacker observation capabilities in security games, and applications of these techniques for randomized resource allocation and patrolling problems.  At the end we will highlight the many opportunities for future work in this area, including exciting new domains and fundamental theoretical and algorithmic challenges.


Target audience

Our primary target audience is students and other novices who will benefit from an extensive introduction to one of the most important areas of applied multi-agent systems research. We also anticipate that this tutorial will appeal to industry participants interested in applied work, and to game theory practitioners who may be interested in learning more about the specific techniques employed in this important class of games.


Syllabus

  1. Motivations: Resource allocation and patrolling in security problems

  2. Motivating domains: LAX, FAMS, robot patrolling, TSA, Coast Guard, Border security, etc.

  3. Goal: provide algorithms to make good (optimal) security decisions

  4. Why use game theory?

  5. Weaknesses of conventional risk analysis/decision theory

  6. Introduction to game theory and solutions

  7. Mechanisms and strategies

  8. Strategic form games

  9. Dominance

  10. Maxmin and minmax strategies and their computation

  11. Zero-sum games

  12. General-sum games and Nash equilibrium

  13. Bayesian games and Bayes-Nash equilibrium

  14. Extensive-form games and subgame perfect equilibrium

  15. Leader-follower (Stackelberg) games

  16. Leader-follower equilibrium and its computation

  17. Bayesian leader-follower games

  18. Tools for operational research

  19. Security games

  20. Definition and examples

  21. Multiple resources

  22. Scheduling constraints

  23. Algorithms: ORIGAMI, ERASER

  24. Complexity results

  25. Relationship between Stackelberg and Nash equilibrium for security games

  26. Branch and Price Algorithms for Large Security Games

  27. Arbitrary scheduling case

  28. Column generation techniques

  29. Branch and bound techniques

  30. ASPEN algorithm

  31. Bayesian Stackelberg Games

  32. DOBSS

  33. Hierarchical decomposition of types

  34. Approximate algorithms for infinite Bayesian games

  35. Patrolling security games

  36. Basic model; graphical representation

  37. Solution concepts (deterministic and non-deterministic)

  38. Perimeter case

  39. Arbitrary topologies case

  40. Solution algorithms/complexity results

  41. Modeling and Evaluation

  42. Building game models from expert opinions

  43. Evaluating real-world systems

  44. Additional discussion of related work

  45. General Discussion/Questions


Tutors

Christopher Kiekintveld is currently an assistant professor at the University of Texas at El Paso, USA. He has done extensive work recently in applications of game theory for Homeland Security, including work on deployed software tools for the Federal Air Marshals service and Transportation Security Administration. He has co-authored several paper on the subject of security games that have been presented at previous AAMAS conferences, in both the main track and industry track (including the winner of the 2009 industry track best paper award). He has given numerous presentations at conferences, workshops, seminars, and guest lectures for courses, including many on the topic of security games. He is currently teaching an undergraduate course on data structures and algorithms, and was previously a teaching assistant in three different courses.


Nicola Gatti is currently assistant professor with tenure at the Politecnico di Milano, Italy. His research topics are artificial intelligence, multi-agent systems, and specifically algorithmic game theory. Currently, he is lecturer of Informatics Systems (undergraduate course) and Algorithmic Game Theory (PhD course), and assistant of the graduate courses of Artificial Intelligence and of Autonomous Agents and Multi-Agent Systems in Computer Engineering, at Politecnico di Milano.  He has co-authored more than ten papers on the subject of security games that have been presented at several conferences (e.g., AAAI, AAMAS, IAT, GAMESEC), receiving two best paper awards at IAT and ICUMT, respectively.


Manish Jain is currently a PhD candidate at the University of Southern California, USA. He is a part of the Teamcore Research group. His work is on the applications of game theoretic and large scale optimization techniques for Homeland Security, including deployed software tools for the Federal Air Marshals Service and Los Angeles World Airports police. He has co-authored papers on the subject of security games that have been presented at AAMAS and AAAI conferences, in both the main track and the industry track. He has given presentations at AAMAS, AAAI and IJCAI conferences, and several other workshops. He  has been a teaching assistant for courses on multi-agent systems at both the graduate and the under-graduate level. His work published at the Operations Research venue Interfaces was recently nominated as a finalist for the EURO excellence in Practice award. In addition to many presentations at technical conferences and workshops, he has been a teaching assistant for Milind Tambe.