Omer Tamuz (Theory Seminar)

In security games, a defender commits to a mixed strategy for protecting a set of n targets of values alpha_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; switching between targets takes unit time. Such games naturally model a number of real-world scenarios, including protecting computer networks from intruders, animals from poachers, etc.

We show that such security games, although played in continuous time, give rise to a combinatorial question regarding the existence of infinite sequences over a finite alphabet, with the following properties for each symbol i: (1) i constitutes a prescribed fraction p_i of the sequence, and (2) the occurrences of i are spread apart close to evenly, in that the ratio of the longest to shortest interval between consecutive occurrences is bounded by some small constant K. We call such sequences K-quasi-regular; 1-quasi-regular sequences are regular, in the sense that each symbol appears evenly spaced. We show that not only regular sequences over the set of targets lead to optimal strategies for the defender, but that, in fact, 2-quasi-regular sequences are sufficient for optimality.

It is easy to see that K-quasi-regular sequences do not always exist when K<2. We show that 2-quasi-regular random sequences always exist, and can be calculated efficiently. Using an ergodic theoretical approach, we show that deterministic 2-quasi-regular sequences always exist, and can likewise be calculated efficiently. We do not know if K<3 is possible deterministically, but give a sufficient condition on the p_i for the existence of a deterministic 2-quasi-regular sequence.  We prove that our deterministic 3-regular sequences give rise to a ~1.006-approximation algorithm for the defender's optimal strategy.

Joint work with David Kempe and Leonard Schulman.