MLN-EIGS: A multilayer network framework for solving Stackelberg escape interdiction games on dynamic transportation networks

Sukanya Samanta; Kei Kimura; Makoto Yokoo; Palash Dey

Source-linked AI summary

MLN-EIGS: A multilayer network framework for solving Stackelberg escape interdiction games on dynamic transportation networks

Sukanya Samanta, Kei Kimura, Makoto Yokoo, Palash Dey

arXiv:2609.10556v1Jul 11, 2026cs.GT

TL;DR

Dynamic escape interdiction on large transportation networks is challenging because attacker movement and defender deployment evolve over time. MLN-EIGS uses a multilayer Stackelberg framework and achieves defender utilities close to exact MILP results with substantially less computational time.

Problem
Escape interdiction on large-scale transportation networks is challenging because attacker movement and defender deployment are dynamic.
Method
MLN-EIGS models temporal network evolution and feasible movements in a multilayer Stackelberg framework with an approximation defender oracle.
Results
MLN-EIGS produces defender utilities that closely approximate the exact MILP benchmark while consistently requiring significantly less computational time.
Takeaways & Limitations
MLN-EIGS provides an effective, computationally efficient, and scalable alternative to exact MILP-based optimization for large-scale dynamic escape interdiction.
Takeaways & Limitations
Prior work does not simultaneously integrate multilayer network games, deterministic escape interdiction models, and computationally expensive MILP formulations.

Abstract

from arXiv · show

Interdicting an escaping criminal with limited police resources on large-scale transportation networks is a challenging problem due to the dynamic nature of both attacker movement and defender deployment. This paper proposes \emph{MLN-EIGS}, a multilayer network-based framework for solving dynamic escape interdiction problems formulated as a Stackelberg security game. A time-expanded multilayer network is constructed to explicitly model the temporal evolution of the transportation network and the feasible movements of both the attacker and the defenders. The attacker seeks to maximize the probability of successful escape, while the defenders aim to maximize the probability of interdiction. To efficiently compute the attacker's best response, the probabilistic escape formulation is transformed into an equivalent shortest-path problem through a logarithmic transformation, enabling the use of Dijkstra's algorithm. Since the defender best-response problem is computationally intractable, an approximation defender oracle is developed to generate high-quality defender strategies on the multilayer network. The proposed MLN-EIGS framework is benchmarked against an exact mixed-integer linear programming (MILP)-based Stackelberg formulation on a large real-world transportation network. Computational experiments demonstrate that MLN-EIGS consistently achieves defender utilities that closely match those of the exact MILP approach while substantially reducing computational time. These results demonstrate that the proposed MLN-EIGS framework provides an effective, computationally efficient, and scalable alternative to exact MILP-based Stackelberg optimization for large-scale dynamic escape interdiction problems.

1. Introduction

MLN-EIGS models dynamic escape interdiction as a Stackelberg game on a multilayer time-expanded transportation network. It combines exact shortest-path attacker responses with an approximate defender oracle to retain solution quality while improving scalability over MILP.

1. Introduction: The defender commits a mixed patrol strategy before the attacker selects a best-response escape route toward predefined exits.This leader–follower structure is intended to capture sequential interactions between law enforcement and escaping criminals.
1. Introduction: A logarithmic reformulation converts the attacker’s multiplicative escape-probability objective into an equivalent shortest-path problem solved exactly with Dijkstra’s algorithm.This exact attacker oracle operates on the multilayer network within a double-oracle framework.
1. Introduction: Because the defender best-response problem is computationally intractable, MLN-EIGS uses an approximation oracle to generate high-quality strategies while maintaining computational scalability.The paper also analyzes the attacker oracle’s complexity and the defender problem’s computational hardness.
1. Introduction: MLN-EIGS integrates temporal network expansion, probabilistic interdiction, and Stackelberg game theory for dynamic transportation networks.The framework represents attacker and defender movement across time layers while modeling interception probabilities along escape paths.
1. Introduction: MLN-EIGS achieves defender utilities comparable to benchmark MILP-EIGS while significantly reducing computational time.The framework is evaluated through computational experiments on a large real-world transportation network.

2. Related work

Prior work includes static, deterministic, and exact optimization approaches for security and escape interdiction. The paper identifies a gap in jointly modeling temporal movement feasibility, probabilistic interdiction, and scalable Stackelberg equilibrium computation.

2. Related work: Existing escape-interdiction studies improve computational performance through exact MILP, metaheuristic, or simulation-based methods, but primarily use static or deterministic formulations.These approaches do not explicitly model temporal network evolution within a Stackelberg framework.
2. Related work: Time-expanded and multilayer networks capture time-dependent movement constraints and have been used for dynamic transportation optimization.Layered representations model temporal evolution explicitly through multiple network layers.
2. Related work: Existing approaches often focus on static Stackelberg games, deterministic escape interdiction, or computationally expensive MILP formulations.These limitations constrain the applicability of exact optimization methods to large-scale transportation networks.
2. Related work: The paper states that prior work does not simultaneously integrate temporal feasibility, probabilistic escape and interdiction, and scalable Stackelberg equilibrium computation on large transportation networks.MLN-EIGS addresses this stated gap with a multilayer time-expanded representation and oracle-based solution framework.
2. Related work: MLN-EIGS combines an exact attacker oracle, an approximate defender oracle, and a double-oracle Stackelberg framework to address the identified gap.This design links multilayer temporal modeling with scalable equilibrium computation.

3. Problem description and modeling

The paper formulates escape interdiction as a two-player Stackelberg security game on a directed transportation network with time-indexed attacker and defender strategies. Defender utility is interception probability, while attacker utility is successful-escape probability.

3. Problem description and modeling: The defender acts as leader, commits to a mixed strategy over patrol schedules, and the attacker then selects an optimal escape route as follower.Multiple defenders cooperate as one decision-making team in the Stackelberg game.
3. Problem description and modeling: The transportation network is a directed graph whose nodes are intersections, edges are road segments, and designated nodes are possible exits.The game starts at time 0 and terminates at a finite horizon tmax.
3. Problem description and modeling: A pure attacker strategy is a time-ordered sequence of node–time pairs, while each defender strategy specifies patrol states over time.These representations encode feasible movement and occupancy for both sides.
3. Problem description and modeling: Defender utility equals the probability of intercepting the attacker, whereas attacker utility equals the probability of successfully escaping.Interception and escape are treated as complementary outcomes, so each player maximizes its corresponding probability.
3. Problem description and modeling: The solution concept is Strong Stackelberg Equilibrium, in which the follower breaks ties in favor of the leader.Given a defender mixed strategy, the attacker computes a best response, and the defender optimizes against that response.

4. Proposed MLN-EIGS framework

MLN-EIGS models dynamic escape interdiction on a time-expanded multilayer transportation network, combining an exact attacker oracle with an approximate defender oracle. Its logarithmic transformation enables shortest-path computation while the approximation supports scalable strategy generation.

MLN-EIGS combines an exact attacker oracle with an approximation defender oracle to compute approximate Stackelberg equilibria on large transportation networks.The defender oracle generates high-quality strategies, while the attacker best response is solved exactly.
Exact attacker oracle: The logarithmic transformation converts multiplicative escape probability into additive path cost, so Dijkstra’s algorithm returns the attacker’s exact optimal escape path.The transformed node weights are non-negative and assigned to incoming edges in the multilayer network.
Multilayer network construction: A time-expanded multilayer network preserves temporal feasibility by connecting successive layers according to transportation travel times.A conventional single-layer graph cannot distinguish visits to the same node at different times, whereas the multilayer representation converts dynamic path planning into an equivalent static shortest-path problem.
Double-oracle solution procedure: The framework iteratively solves a restricted Stackelberg linear program, adds improving attacker or defender strategies, and terminates when neither oracle finds another improvement.Because only the attacker oracle is exact, the returned solution is an approximate Strong Stackelberg equilibrium with corresponding defender utility U⋆.
Approximation defender oracle: The approximation defender oracle seeks a feasible patrol path that visits nodes associated with the maximum number of differently colored attacker strategies.Each attacker strategy receives a unique color, and covering more colors is used to maximize expected interdiction probability.
Computational scope: The defender best-response problem is computationally difficult, motivating the approximation oracle and avoiding repeated mixed-integer optimization on large networks.The Color-Covering Problem used in the approximation is stated to be NP-complete.

5. MILP-EIGS benchmarking algorithm

MILP-EIGS is the exact benchmark for MLN-EIGS, using the same leader–follower framework but solving both attacker and defender best responses with MILP formulations. The approaches are compared on defender utility, computational time, and optimality.

Benchmark formulation: MILP-EIGS benchmarks MLN-EIGS by using exact MILP-based best-response oracles for both the attacker and defender.Its attacker oracle is bestAo, and its defender oracle is bestDo.
Iterative algorithm: The benchmark iteratively solves the restricted Stackelberg game, adds newly identified improving strategies, and stops when neither player can generate another improving strategy.Termination yields a Stackelberg equilibrium of the restricted game.
Computational limitation: Repeated MILP solution creates substantial computational overhead for large transportation networks because vehicle escape interdiction is NP-hard.This overhead motivates replacing the exact defender oracle in MLN-EIGS with an approximation.
Evaluation design: MILP-EIGS provides the exact benchmark for comparing defender equilibrium utility, computational time, and optimality with MLN-EIGS.The comparison is designed to evaluate the proposed framework’s effectiveness.

6. Results and discussion

The experiments illustrate exact attacker and approximate defender oracles on multilayer networks, then benchmark MLN-EIGS against MILP-EIGS on Central Kolkata instances. MLN-EIGS maintains comparable defender utilities while substantially reducing computational time.

Defender oracle: On the defender example, the approximation oracle generates patrol strategies that collectively cover all attacker strategies while satisfying temporal constraints.Three equally probable attacker strategies are encoded by colors on the multilayer network, and the resulting patrols are shown in Fig. 4.
Real-world benchmark: The Central Kolkata benchmark uses a 461-node, 1,020-edge directed network and varies defender locations, crime node, speeds, and response time across 25 instances.The network was extracted from OpenStreetMap and imported into SUMO.
Real-world benchmark: For all feasible instances, the largest observed defender-utility gap is 0.385, while some instances have zero utility gap.The fractional utilities reflect cumulative interdiction probabilities, unlike MILP-EIGS’s deterministic binary utilities.
Real-world benchmark: MLN-EIGS reduces runtime because it uses polynomial-time shortest-path computation for the attacker and a greedy approximation for the defender.The attacker oracle applies Dijkstra’s algorithm after logarithmic transformation, while the defender oracle uses an efficient greedy algorithm.
Real-world benchmark: Across feasible instances, MLN-EIGS consistently achieves defender utilities close to MILP-EIGS while requiring substantially less computational time.The benchmark evaluates solution quality and runtime on 25 Central Kolkata test instances.

7. Conclusion

MLN-EIGS combines multilayer time-expanded modeling with exact attacker and approximate defender oracles to solve dynamic escape interdiction problems. Experiments show comparable defender utilities to MILP-EIGS with substantially lower computational time, while future work targets richer uncertainty and stronger defender-oracle guarantees.

7. Conclusion: The framework represents attacker movements on a multilayer time-expanded network and integrates probabilistic interdiction modeling with Stackelberg game theory.This provides a unified optimization framework for dynamic transportation networks.
7. Conclusion: A logarithmic transformation reduces the attacker’s multiplicative escape-probability best response to an equivalent shortest-path problem solvable with Dijkstra’s algorithm.The transformation enables efficient exact attacker-oracle computation.
7. Conclusion: Because the defender best-response problem is computationally intractable, MLN-EIGS uses a polynomial-time approximation defender oracle within a double-oracle framework.The approximation oracle supports scalable computation of approximate Stackelberg equilibria.
7. Conclusion: MLN-EIGS achieves defender equilibrium utilities close to benchmark MILP-EIGS solutions while consistently requiring substantially lower computational time.Experiments on 25 Central Kolkata transportation-network instances support the comparison.
7. Conclusion: Future extensions include stochastic travel times, real-time traffic information, uncertain environments, heterogeneous resources, and adaptive or learning-based attacker behavior.The conclusion also identifies exact or theoretically guaranteed approximation defender oracles as an open direction.
7. Conclusion: The framework provides a scalable and computationally efficient approach for approximate Stackelberg equilibria in large-scale dynamic escape interdiction networks.Its reported solution quality remains comparable to exact MILP-based methods.