Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2018 | Published + Submitted
Book Section - Chapter Open

Quasi-regular sequences and optimal schedules for security games


We study security games in which a defender commits to a mixed strategy for protecting a finite set of targets of different values. An attacker, knowing the defender's strategy, chooses which target to attack and for how long. If the attacker spends time t at a target i of value α_i, and if he leaves before the defender visits the target, his utility is t · α_i; if the defender visits before he leaves, his utility is 0. The defender's goal is to minimize the attacker's utility. The defender's strategy consists of a schedule for visiting the targets; it takes her unit time to switch between targets. Such games are a simplified model of a number of real-world scenarios such as protecting computer networks from intruders, crops from thieves, etc. We show that optimal defender play for such security games, although played in continuous time, reduces to the solution of 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 limiting fraction p_i of the sequence. (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 a parameter K. We call such sequences K-quasi-regular; a 1-quasi-regular sequence is one in which the occurrences of each symbol form an arithmetic sequence. As we show, a 1-quasi-regular sequence ensures an optimal defender strategy for these security games: the intuition for this fact lies in the famous "inspection paradox." However, as we demonstrate, for K < 2 and general p_i, K-quasi-regular sequences may not exist. Fortunately, this does not turn out to be an obstruction: we show that, surprisingly, 2-quasi-regular sequences also suffice for optimal defender play. What is more, even randomized 2-quasi-regular sequences suffice for optimality. We show that such sequences always exist, and can be calculated efficiently. Thus, we can ensure optimal defender play for these security games. The question of the least K for which deterministic K-quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we proceed to show that deterministic 3-quasi-regular sequences always exist (and can be calculated efficiently). We also show that these deterministic 3-regular sequences give rise to a ≈ 1.006-approximation algorithm for the defender's optimal strategy. For 2 ≤ K < 3 we do not know whether deterministic K-quasi-regular sequences always exist; however, when the pi are all small, improved bounds are possible, and in fact, (1 + ∊)-quasi-regular deterministic sequences exist for any ∊ > 0 for sufficiently small p_i.

Additional Information

© 2018 SIAM. Supported in parts by NSF grants 1619458 and 1423618. Supported in part by NSF grants 1319745, 1618795, and a EURIAS Senior Fellowship co-funded by the Marie Skłodowska-Curie Actions under the 7th Framework Programme. This work was supported by a grant from the Simons Foundation (#419427, Omer Tamuz).

Attached Files

Published - p1625-kempe.pdf

Submitted - 1611.07169.pdf


Files (1.3 MB)
Name Size Download all
972.8 kB Preview Download
376.5 kB Preview Download

Additional details

August 19, 2023
October 18, 2023