Mitigating the Curse of Correlation in Security Games by Entropy Maximization

Haifeng Xu, Milind Tambe, Shaddin Dughmi, Venil Loyd Noronha

TL;DR

Patrolling strategies in security games often contain hidden correlations that allow attackers to predict future movements by observing just a single target—a phenomenon the authors call the Curse of Correlation (CoC). To fix this, the researchers propose maximizing the Shannon entropy of defender strategies, creating "most random" schedules that are significantly more robust against surveillance and strategic manipulation.

What Problem Does This Paper Address?

In a Stackelberg security game, a defender (like a park ranger or an air marshal) randomly allocates limited resources to protect multiple targets. Standard models assume the attacker only knows the defender's average strategy. However, in the real world, attackers can watch a patroller at one location and use that "leakage" to infer where the patroller will be next.

The authors identify the Curse of Correlation (CoC): because resources are limited, protecting one target often mathematically implies that another is left unguarded. If an attacker knows these correlations, monitoring one "bit" of information can compromise the entire security schedule. This is especially dangerous in spatio-temporal settings, where a patroller’s current position is highly correlated with their future path.

Figure 1: Marginal Probabilities and Their Implementation.

Methods

The authors argue that instead of trying to build a perfect (but likely inaccurate) model of what the attacker sees, defenders should adopt the "most random" strategy possible. They propose Entropy Maximization: finding a mixed strategy that meets the required coverage probabilities while maximizing Shannon entropy.

Key technical contributions include:

  • Complexity Analysis: They prove that sampling from a max-entropy strategy is #P-hard in general.
  • Exact Algorithms: They develop efficient polynomial-time algorithms for two critical scenarios:
  • Small Number of Patrollers: A dynamic programming approach for cases with a constant number of resources.
  • Air Marshal Scheduling: Exploiting "ordered matching" structures in bipartite graphs to solve round-trip scheduling.
  • CARD Heuristic: They introduce CArathéodory Randomized Decomposition (CARD), a scalable heuristic for general security games. CARD uses randomized linear objectives to sample vertices of the strategy polytope, inheriting the high entropy of the random objectives.
Figure 2: Structure of a Spatio-Temporal Security Game

Datasets

The paper evaluates its algorithms using:

  • Synthetic Zero-Sum Games: Randomly generated games with up to 300 targets and varying numbers of patrollers.
  • Spatio-Temporal Grids (STST): Simulated $T \times N$ grid graphs representing movement constraints.
  • FAMS Simulations: Bipartite graph structures modeled after Federal Air Marshal Service round-trip flight constraints.

Key Insights and Ideas

  • Correlation is Inevitable: The authors formally prove (Proposition 3.1) that in any non-trivial randomized strategy, monitoring one target always reduces the uncertainty (entropy) of others.
  • The Flaw of "Small Support": Traditional algorithms favor strategies that use only a few patrol routes to save on computation. The authors show these "small support" strategies are the most vulnerable to CoC because they are highly predictable.
  • Robustness over "Rigor": While one could theoretically calculate a "rigorously optimal" strategy against a specific surveillance model, such strategies are brittle. If the defender's belief about what the attacker knows is even slightly off, the "optimal" strategy can perform worse than doing nothing. Max-entropy strategies provide a "safety net" by being difficult to predict regardless of the attacker's specific observations.

Key Results

  • Scalability: The max-entropy approach is far more scalable than previous state-of-the-art "leakage-aware" algorithms (RigorOPT). While RigorOPT struggles beyond 30 targets, the new algorithms handle 300 targets in under two minutes.
  • Superior Performance: In simulations of the Federal Air Marshal Service (FAMS) scheduling, the max-entropy approach significantly outperformed traditional column-generation methods (ColG), especially as the "deployment-to-saturation" ratio increased.
  • Real-World Impact: A scalable version of their algorithm reached pre-deployment testing for integration into the software used to schedule US federal air marshals.

Limitations and Future Work

  • General Complexity: While the authors found efficient solutions for specific structures, the general problem remains computationally daunting (#P-hard).
  • Zero-Sum Assumption: Much of the experimental evaluation focuses on zero-sum games. While many security scenarios fit this, extending the analysis to general-sum games—where "leaking" information might occasionally benefit the defender—remains an open area for exploration.
  • Alternative Mitigations: The authors suggest that while entropy maximization is a powerful tool, other methods for addressing CoC in security games should be investigated.

Summary updated

Abstract

In Stackelberg security games, a defender seeks to randomly allocate limited security resources to protect critical targets from an attack. In this paper, we study a fundamental, yet underexplored, phenomenon in security games, which we term the \emph{Curse of Correlation} (CoC). Specifically, we observe that there are inevitable correlations among the protection status of different targets. Such correlation is a crucial concern, especially in \emph{spatio-temporal} domains like conservation area patrolling, where attackers can surveil patrollers at certain areas and then infer their patrolling routes using such correlations. To mitigate this issue, we propose to design entropy-maximizing defending strategies for spatio-temporal security games, which frequently suffer from CoC. We prove that the problem is \#P-hard in general. However, it admits efficient algorithms in well-motivated special settings. Our experiments show significant advantages of max-entropy algorithms over previous algorithms. A scalable implementation of our algorithm is currently under pre-deployment testing for integration into FAMS software to improve the scheduling of US federal air marshals.
BibTeX
@inproceedings{xu2018mitigating,
  author = {Haifeng Xu and Milind Tambe and Shaddin Dughmi and Venil Loyd Noronha},
  title = {{Mitigating the Curse of Correlation in Security Games by Entropy Maximization}},
  booktitle = {AAMAS},
  year = {2018},
}
Figure