Security Games: Quasi-Regular Sequences, and a new version of TSP

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 target 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 for one of several natural objective functions.

Our work raises a wealth of interesting open questions.

[joint work with Leonard J. Schulman and Omer Tamuz (SODA 2018) and with Mark Klein (submitted)]