# Layered Graph Security Games

arXiv: https://arxiv.org/abs/2405.03070 · HTML: https://mlsanity.com/paper/2405.03070/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2024.

## Built on by (most cited first, 2 of 2)

- [DDPS: Discrete Diffusion Posterior Sampling for Paths in Layered Graphs](https://mlsanity.com/paper/2504.20754/) (2025)
- [DiffNash: Finding Nash Equilibrium in High-Dimensional Continuous Action Spaces with Diffusion Policies](https://mlsanity.com/paper/2610.15932/) (2026)

## Abstract (arXiv)

Security games model strategic interactions in adversarial real-world applications. Such applications often involve extremely large but highly structured strategy sets (e.g., selecting a distribution over all patrol routes in a given graph). In this paper, we represent each player's strategy space using a layered graph whose paths represent an exponentially large strategy space. Our formulation entails not only classic pursuit-evasion games, but also other security games, such as those modeling anti-terrorism and logistical interdiction. We study two-player zero-sum games under two distinct utility models: linear and binary utilities. We show that under linear utilities, Nash equilibrium can be computed in polynomial time, while binary utilities may lead to situations where even computing a best-response is computationally intractable. To this end, we propose a practical algorithm based on incremental strategy generation and mixed integer linear programs. We show through extensive experiments that our algorithm efficiently computes ε-equilibrium for many games of interest. We find that target values and graph structure often have a larger influence on running times as compared to the size of the graph per se.