Game Theory for Security: Large-scale Data-driven Approaches

Principal Investigator: Milind Tambe


Our proposed research will address the following fundamental research challenges. Though we describe each of these challenges in isolation, this project will produce a comprehensive theory that addresses all of these research challenges simultaneously. (a) Large-scale Implementation: We have successfully applied our work to many real-world security games in the past, the issue of scaling up our methods to multi-stage games has not been resolved. In particular, both the LA Sheriff’s Dept and US Coast Guard are looking for patrols over long time horizons, over large areas. (b) Learning and Data-Driven Optimization: We are exploring new domains on combating everyday crimes, this type of crime differs from the strategic crimes faced in counter-terrorism applications. A terrorist attack is carefully planned and implemented, while everyday crimes are unplanned and opportunistic. Our work on the protection of fishery and marine resources, mass transit systems such as trains and roads, and crime hot spots around cities, all falls under the heading of opportunistic crime. In cooperation with law enforcement, it is possible to collect abundant data on this class of security problem. In current research, we have developed a Bayesian game representation of the LASD’s metro problem that allows for learning about the underlying parameters of the game. In our proposed work, we will incorporate online learning into many other security games, and search for data-driven strategies. (c) Robust optimization: Behavioral game theory experiments have revealed that players often deviate from perfectly rational play. While we can use data and repeated interaction to learn about our adversaries, in life-critical security games we need strong robustness guarantees on our policies. Certainly, one could argue that many terrorists are not perfectly rational decision makers because of the high cost of their attacks to themselves. So, we need strong and tractable models that can handle uncertainty in attacker behavior. Our work on robust Stackelberg games is promising and we can extend these methods to incorporate multiple types of uncertainty in a dynamic setting. (d) Coordination: In many cases we are faced with highly heterogeneous defender units, potentially belonging to different agencies. For example, in New York we may potentially need to coordinate US Coast Guard boats, helicopter patrols, and NYPD boat patrols. Most of the patrol problems we have discussed so far are very large-scale and difficult to solve for even a single patroller unit. To effectively coordinate between patrol units, we need a theory for decomposing the game into computationally manageable pieces, in a way that still gives strong performance guarantees.