Quasi-regular sequences and optimal schedules for security games

2016/11/30 by David Kempe, Leonard J. Schulman, Omer Tamuz · 1 citation
Computer Science · #cs.GT #cs.DM #cs.DS

paper · pdf · doi:10.1137/1.9781611975031.106

to appear in Proc. of SODA 2018

arxiv created 2017/10/29 · arxiv updated 2018/04/24

Abstract

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 this continuous time security games 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 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. We show that, surprisingly, 2-quasi-regular sequences 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. The question of the least K for which deterministic K-quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we show that deterministic 3-quasi-regular sequences always exist. For 2 ≤ K < 3 we do not know whether deterministic K-quasi-regular sequences always exist.

Cited by

• Proof of the Density Threshold Conjecture for Pinwheel Scheduling

Related

• The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design
• Multi-defender Security Games with Schedules
• Strategy Synthesis in Adversarial Patrolling Games
• A Polynomial Time Algorithm for Spatio-Temporal Security Games
• Security Game with Non-additive Utilities and Multiple Attacker Resources