Quasi-regular sequences and optimal schedules for security games
David Kempe, Leonard J. Schulman, Omer Tamuz · Society for Industrial and Applied Mathematics eBooks · 2018
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 · ai; 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 pi 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 0 for sufficiently small pi.