Security Games: Quasi-Regular Sequences, and a New Version of TSP
[joint work with Leonard J. Schulman and Omer Tamuz (SODA 2018) and with Mark Klein (submitted)]
In security games, a defender commits to a mixed strategy for protecting a set of n targets of values v_i; an attacker, knowing the defender's strategy, chooses which target to attack and for how long. We study a natural version in which the attacker's utility grows linearly with the time he spends at the target, but drops to 0 if he is caught. The defender's goal is to minimize the attacker's utility. The defender's strategy consists of a schedule for visiting the targets; a metric space determines how long it takes to travel between targets. Such games naturally model a number of real-world scenarios, including protecting computer networks from intruders, animals from poachers, etc. We study this problem in two scenarios:
1. When all the distances between targets are the same, then optimal and near-optimal strategies naturally correspond to sequences in which each character occupies a prescribed fraction p_i of the sequence, and appears "close to evenly spread."
We formalize these notions, and give efficient algorithms for finding sequences whose properties are strong enough to provide optimal or near-optimal strategies in the corresponding security game.
2. When distances between targets are arbitrary, the problem subsumes the well-known Traveling Salesman Problem (TSP), but generalizes it in novel and interesting ways. We give a polynomial-time O(log n) approximation algorithm for finding the best strategy for the defender.
David Kempe received his Ph.D. from Cornell University in 2003, and has been on the faculty in the computer science department at USC since the Fall of 2004, where he is currently an Associate Professor. His primary research interests are in computer science theory and the design and analysis of algorithms, with a particular emphasis on social networks, algorithms related to online and other learning models, and game-theoretic and pricing questions. He is a recipient of the NSF CAREER award, the VSoE Junior Research Award, the ONR Young Investigator Award, a Sloan Fellowship, and an Okawa Fellowship, in addition to several USC mentoring awards and Best Paper awards.