Solving Urban Network Security Games: Learning Platform, Benchmark, and Challenge for AI Research

Shuxin Zhuang, Shuxin Li, Tianji Yang, Muheng Li, Xianjie Shi, Bo An, Youzhi Zhang · 2025

Read Solving Urban Network Security Games: Learning Platform, Benchmark, and Challenge for AI Research by Shuxin Zhuang, Shuxin Li, Tianji Yang, Muheng Li, Xianjie Shi, Bo An, Youzhi Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17559.txt.

Introduction

Shuxin Zhuang and six colleagues introduce GraphChase, an open platform for research on urban network security games, in a 2025 paper. These games model police allocating scarce patrols to intercept fleeing criminals on city street networks. The field has lacked a shared test bed, especially one with realistic, uneven travel costs across roads.

GraphChase lets researchers model many game variants on both simple and weighted road networks and ships with learning-based algorithms as baselines. Experiments on the platform showed current solvers lose robustness and scale poorly once travel times vary by street. The authors frame that gap between simulation and reality as the challenge their benchmark is built to expose.

Catalog record

CREATORShuxin Zhuang, Shuxin Li, Tianji Yang, Muheng Li, Xianjie Shi, Bo An, Youzhi Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-17559

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving Urban Network Security Games: Learning Platform, Benchmark, and Challenge for AI Research Shuxin Zhuang, Shuxin Li, Tianji Yang, Muheng Li, Xianjie Shi, Bo An, Youzhi Zhang Abstract After the great achievement of solving two-player zero-sum games, more and more AI researchers focus on solving multiplayer games. To facilitate the development of designing efficient learning algorithms for solving multiplayer games, we propose a multiplayer game platform for solving Urban Network Security Games ( UNSG ) that model real-world scenarios. That is, preventing criminal activity is a highly significant responsibility assigned to police officers in cities, and police officers have to allocate their limited security resources to interdict the escaping criminal when a crime takes place in a city. This interaction between multiple police officers and the escaping criminal can be modeled as a UNSG. The variants of UNSGs can model different real-world settings, e.g., whether real-time information is available or not, and whether police officers can communicate or not. The main challenges of solving this game include the large size of the game and the co-existence of cooperation and competition. While previous efforts have been made to tackle UNSGs, they have been hampered by performance and scalability issues. Therefore, we propose an open-source UNSG platform ( GraphChase ) for designing efficient learning algorithms for solving UNSGs. Specifically, GraphChase offers a unified and flexible game environment for modeling various variants of UNSGs, supporting the development, testing, and benchmarking of algorithms. We believe that GraphChase not only facilitates the development of efficient algorithms for solving real-world problems but also paves the way for significant advancements in algorithmic development for solving general multiplayer games. 1 Introduction In the field of AI research, a lot of focus has been placed on computing a Nash equilibrium ( Nash 1951 ; Shoham & Leyton-Brown 2008 ) in two-player zero-sum extensive-form games, where both players receive opposing payoffs ( Zinkevich et al. 2008 ; Moravčík et al. 2017 ; Brown & Sandholm 2018 ) . In this scenario, a Nash equilibrium can be computed in polynomial time based on the size of the extensive-form game ( Shoham & Leyton-Brown 2008 ) . Recent significant achievements, such as achieving superhuman performance in the heads-up no-limit Texas hold’em poker game ( Moravčík et al. 2017 ; Brown & Sandholm 2018 ) , demonstrate that researchers have a good understanding of the problem of computing a Nash equilibrium in two-player zero-sum extensive-form games, both in theory and in practice. However, the problem of computing a Nash equilibrium in multiplayer games is not as well understood, as it is generally a challenging task ( Chen & Deng 2005 ; Zhang et al. 2023b ) . Therefore, more and more AI researchers focus on solving multiplayer games ( Brown & Sandholm 2019 ; FAIR et al. 2022 ; Carminati et al. 2022 ; Zhang et al. 2023a ; McAleer et al. 2023 ; Zhang et al. 2024 ) To facilitate the development of designing efficient learning algorithms for solving multiplayer games, we propose a multiplayer game platform for solving Urban Network Security Games ( UNSGs ) that model the following real-world situations. In urban areas, ensuring public safety and security is crucial for law enforcement agencies. One significant challenge they face is the high number of innocent bystanders who are injured or killed during police pursuits ( Rivara & Mack 2004 ) . It’s essential to develop effective strategies that allow multiple officers to apprehend fleeing criminals while minimizing risks to civilians and property damage. This paper focuses on responding to major incidents such as terrorist attacks or bank robberies, where police officers need to swiftly intercept the attackers during their escape. This requires efficient strategies for apprehending fleeing criminals, which can be analyzed and developed using structured approaches like UNSGs. Figure 1: The blueprint of our GraphChase platform. However, solving UNSGs is NP-hard ( Jain et al. 2011 ; Zhang et al. 2017 ; Zhang et al. 2019 ) . More specifically, the strategy space of players in UNSGs cannot be enumerated due to the memory constraint of computers ( Jain et al. 2011 ; Zhang et al. 2019 ) . Moreover, if players do not have real-time information, they have to make decisions with imperfect information. In addition, if police officers cannot communicate during the game play, they have to make decisions independently. Finally, UNSGs incorporate cooperation between police officers and competition between the criminal and team of police officers. To address the above challenges, previous efforts have been made to tackle UNSGs. That is, they extended the Counterfactual Regret Minimization (CFR) ( Zinkevich et al. 2008 ) to CFR-MIX algorithm ( Li et al. 2021 ) , incorporating deep learning enhancements from Deep CFR ( Brown et al. 2019 ) . Additionally, they utilized the Neural Fictitious Self-Play (NFSP) approach ( Heinrich & Silver 2016 ) , further developed into NSG-NFSP ( Xue et al. 2021 ) and NSGZero ( Xue et al. 2022 ) , which are tailored to solving UNSGs under the NFSP framework. Moreover, they extended the learning framework, Policy-Space Response Oracles (PSRO) ( Lanctot et al. 2017 ) , to an advanced variant Pretrained PSRO ( Li et al. 2023a ) to speed up. Finally, they developed Grasper ( Li et al. 2024 ) based on Pretrained PSRO, an innovative algorithm that can generalize across different game settings. All of them are based on the state-of-the-art game-theoretical algorithm frameworks. However, these efforts are still hampered by performance and scalability issues, as shown in our experiments. To foster the development of scalable algorithms capable of addressing city-scale UNSGs, we propose the creation of an open-source platform, GraphChase , specifically tailored for UNSG. The architecture of GraphChase is depicted in Figure 1 , designed to provide researchers with a comprehensive UNSG platform and facilitate the development and evaluation of scalable strategy for pursuers. Specifically, we made the following contributions: i) Development of a unified and flexible UNSG environment: We developed a versatile platform designed to support various configurations of UNSGs. Specifically, this environment allows for modifying game parameters, enabling researchers to simulate different real-world UNSG scenarios under various conditions. The inherent flexibility of GraphChase supports a wide range of experimental setups, from small-scale laboratory experiments to city-wide simulations. All these make GraphChase a suitable tool for theoretical research and practical application testing. ii) Implementation of learning algorithms: GraphChase is designed to facilitate the execution of a wide range of algorithms. Based on the standardized platform, we successfully implement several advanced deep learning-based algorithms, enabling the consistent comparison of different strategic approaches. By efficiently integrating algorithms within the platform, it reduces the time overhead of the simulation resulting in faster convergence from the perspective of wall-clock time. And iii) Benchmark results: We conduct experiments on UNSGs with synthetic and real-world graphs to evaluate the performance of the different algorithms implemented on the GraphChase platform. The results from these experiments are recorded and compiled into comprehensive benchmarks. Our results show that, although previous algorithms can achieve reasonable performance, they still suffer performance and scalability issues in real-world settings. These results suggest that substantial efforts are still required to develop effective and efficient algorithms for solving real-world UNSGs. We believe

Read the complete text