A Caltech Library Service

Quasi-regular sequences and optimal schedules for security games

Kempe, David and Schulman, Leonard J. and Tamuz, Omer (2018) Quasi-regular sequences and optimal schedules for security games. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, pp. 1625-1644. ISBN 978-1-6119-7503-1.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Schulman, Leonard J.0000-0001-9901-2797
Tamuz, Omer0000-0002-0111-0418
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).
Funding AgencyGrant Number
Marie Curie FellowshipUNSPECIFIED
Simons Foundation419427
Record Number:CaltechAUTHORS:20180410-145958889
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:85735
Deposited By: Tony Diaz
Deposited On:11 Apr 2018 14:45
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page