Quasi-regular sequences and optimal schedules for security games

David Kempe, Leonard J. Schulman, Omer TamuzSODA 2016 · DOI · OpenReview

TL;DR

This paper tackles the challenge of designing optimal defender schedules in security games where the defender must visit targets sequentially with travel time. They introduce the concept of "K-quasi-regular sequences" to model these schedules and prove that surprisingly, 2-quasi-regular sequences are sufficient for optimal play, even when deterministic sequences of lower regularity don't exist.

What Problem Does This Paper Address?

Imagine a security guard protecting a set of locations, each with a different value. The guard can't teleport; they need time to travel between locations. An attacker knows the guard's patrol strategy and aims to maximize their gain by attacking a target for as long as possible before the guard arrives. If the guard intercepts the attacker, both get nothing. The defender's goal is to minimize the attacker's maximum possible gain. This is a security game with a crucial timing component. Existing models often assume instantaneous travel or simpler attacker strategies. This paper addresses the complexity introduced by realistic travel times and the need for a predictable yet unpredictable defender schedule.

Methods

The core of the paper lies in translating the defender's optimal strategy into the language of sequences. They define "K-quasi-regular sequences" where occurrences of each target symbol are spread out within a factor of K. The key insight is that optimal defender play, even in continuous time, can be achieved by following such a sequence. They prove that 2-quasi-regular sequences are sufficient for optimality, even if deterministic sequences with K<2 don't exist. They also develop algorithms to construct these sequences efficiently. For a more relaxed optimality, they explore the "Golden Ratio Schedule," which is ergodic and provides a near-optimal (≈1.006 approximation) strategy, demonstrating the existence of 3-quasi-regular deterministic sequences.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Inspection Paradox" in Security: The paper leverages the intuition from the inspection paradox: longer gaps between defender visits make longer attacker stays more attractive. This highlights the importance of regularity in defender schedules.
  • 2-Quasi-Regularity is Sufficient: The most surprising finding is that even if perfectly regular (1-quasi-regular) or slightly less regular (K<2) sequences don't exist, a 2-quasi-regular sequence is enough for optimal defender play. This provides a practical sweet spot for designing schedules.
  • Randomized vs. Deterministic Schedules: While deterministic K-quasi-regular sequences might not always exist, randomized 2-quasi-regular sequences are guaranteed to exist and can be computed efficiently.
  • Golden Ratio as a Near-Optimal Heuristic: The Golden Ratio Schedule, a simple ergodic approach, yields a remarkably good approximation to the optimal strategy, showcasing the power of well-chosen irrational numbers in scheduling.

Key Results

  • Optimal defender strategies in these security games can be represented by K-quasi-regular sequences.
  • 2-quasi-regular sequences (deterministic or randomized) are sufficient for optimal defender play, regardless of target values.
  • Algorithms are provided to efficiently construct these 2-quasi-regular sequences.
  • Deterministic 3-quasi-regular sequences always exist and can be computed efficiently.
  • The Golden Ratio Schedule provides a ≈1.006 approximation to the optimal strategy, demonstrating a tight bound.

Limitations and Future Work

The authors acknowledge that their results for deterministic K-quasi-regular sequences are limited to K=3 and don't cover the 2 ≤ K < 3 range. They also note that their analysis relies on the assumption that no target value exceeds the sum of all other targets' values (a_i <= 1/2), and the game is zero-sum. Future work includes finding optimal ergodic schedules for all value vectors, exploring non-zero-sum games, and adapting to more complex defender constraints and non-uniform travel times.

Summary updated

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 $\alpha_i$, and if he leaves before the defender visits the target, his utility is $t \cdot \alpha_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 \leq K < 3$ we do not know whether deterministic $K$-quasi-regular sequences always exist.
BibTeX
@inproceedings{kempe2016quasi,
  author = {David Kempe and Leonard J. Schulman and Omer Tamuz},
  title = {{Quasi-regular sequences and optimal schedules for security games}},
  booktitle = {SODA},
  year = {2016},
  doi = {10.1137/1.9781611975031.106},
}
Figure