Tutorials

8:30 – 11:10 December 2 (Friday), Room B: Cineraria


Tutorial: “Security and Game Theory”

Speaker: Milind Tambe

Abstract

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, to protect forests and wildlife, to reduce cyber crime 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, wildlife smuggling 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 them.

Game theory provides a sound mathematical approach for security resource optimization. More specifically, we have founded a new era of “security games” by focusing on massive games that could be solved by exploiting computational advances. Security games combine computational and behavioral game theory, machine learning, planning under uncertainty, and many insights from other fields including criminology and conservation biology. Our research on “security games” has led to a wide range of actual deployed applications of game theory for security, both nationally (within the United States) and internationally, by agencies such as the US Coast Guard and the Federal Air Marshals Service, by various police departments in Los Angeles, as well as by non-governmental organizations committed to wildlife conservation. Many research groups are now conducting research in security games.

This tutorial will provide an introduction to this important research area of security games. After a quick review of the applications of security games, we will cover (i) basic concepts from game theory; (ii) basic introduction to security games; (iii) introductory security game algorithms; (iv) a survey of research challenges, including scaling up security games to large-scale problems, handling significant adversarial uncertainty, dealing with bounded rationality of human adversaries, machine learning based on adversary behavior data in wildlife or urban crime, and many other interdisciplinary challenges.