# GraphChase: A Platform and Benchmark for Urban Network Security Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 73 references that are in the map.
- First posted on arXiv 29 Jan 2025.

## Builds on (most cited first, 17 of 17)

- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Google Research Football: A Novel Reinforcement Learning Environment](https://mlsanity.com/paper/1907.11180/) (2019)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [Team-maxmin equilibrium: efficiency bounds and algorithms](https://mlsanity.com/paper/1611.06134/) (2016)
- [Solving Large-Scale Extensive-Form Network Security Games via Neural Fictitious Self-Play](https://mlsanity.com/paper/2106.00897/) (2021)
- [Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositions](https://mlsanity.com/paper/2109.05284/) (2021)
- [A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving](https://mlsanity.com/paper/2206.09161/) (2022)
- [Grasper: A Generalist Pursuer for Pursuit-Evasion Problems](https://mlsanity.com/paper/2404.12626/) (2024)
- [Dynamic Programming for One-Sided Partially Observable Pursuit-Evasion Games](https://mlsanity.com/paper/1606.06271/) (2016)
- [Computing Ex Ante Coordinated Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games](https://mlsanity.com/paper/2009.12629/) (2020)
- [Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization](https://mlsanity.com/paper/2202.00789/) (2022)
- [Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation](https://mlsanity.com/paper/2203.07181/) (2022)
- [CFR-MIX: Solving Imperfect Information Extensive-Form Games with Combinatorial Action Space](https://mlsanity.com/paper/2105.08440/) (2021)
- [NSGZero: Efficiently Learning Non-Exploitable Policy in Large-Scale Network Security Games with Neural Monte Carlo Tree Search](https://mlsanity.com/paper/2201.07224/) (2022)
- [Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games](https://mlsanity.com/paper/2301.02129/) (2023)

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

- [Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games](https://mlsanity.com/paper/2511.00811/) (2025)
- [R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability](https://mlsanity.com/paper/2511.17367/) (2025)

## Abstract (arXiv)

After the achievement of solving two-player zero-sum games, more AI researchers focus on solving multiplayer games. Urban Network Security Games (UNSGs) represent a class of such games, modeling real-world scenarios where law enforcement must strategically allocate limited resources to intercept criminals escaping within urban networks, and have gained considerable research attention. However, progress in this field has been limited by the absence of a standardized experimental platform and realistic benchmarks with heterogeneous travel costs. To address this limitation, we introduce GraphChase, an open-source platform designed to support the development and evaluation of algorithms for UNSGs. GraphChase offers a unified environment for modeling diverse UNSG variants on unweighted and weighted road networks across urban topologies. It also incorporates learning-based algorithms as baseline references for researchers. Furthermore, our experiments with GraphChase reveal that existing approaches to UNSGs still face challenges in terms of robustness and scalability, and suffer performance degradation when deployed under weighted edge costs, highlighting a sim-to-real generalization gap. GraphChase thus provides a realistic testbed for developing and validating UNSGs solvers under realistic travel-time heterogeneity.