Theory of Computing Seminar

 In security games, a defender commits to a mixed strategy for protecting a set of n targets with different values; an attacker, knowing the defender's strategy, chooses which target to attack, when to attack it, and for how long.

We show that such security games give rise to 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, and (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 some small constant K. We call such sequences K-quasi-regular; 1-quasi-regular sequences are regular, in the sense that each symbol appears evenly spaced.

We show that 2-quasi-regular random sequences always exist, and can be calculated efficiently. Using an ergodic theoretical approach, we show that deterministic 3-quasi-regular sequences always exist, and can likewise be calculated efficiently. We do not know if K < 3 is possible deterministically, but give a sufficient condition on the p_i for the existence of a deterministic 2-quasi-regular sequence. We prove that 2-quasi regular sequences give rise to an optimal defender strategy, and that our deterministic 3-regular sequences give rise to a strategy is a 1.006-approximation to the optimum.