pith. sign in

arxiv: 2406.14514 · v4 · submitted 2024-06-20 · 💻 cs.AI

Solving a Stackelberg Game on Transportation Networks in a Dynamic Crime Scenario: A Mixed Approach on Multi-Layer Networks

Sukanya Samanta , Kei Kimura , Makoto Yokoo , Palash Dey This is my paper

Pith reviewed 2026-05-24 00:08 UTC · model grok-4.3

classification 💻 cs.AI
keywords Stackelberg gamelayered networksapproximation algorithmcrime interdictiontransportation networksdynamic pursuitMILP comparisonDijkstra algorithm
0
0 comments X

The pith

An approximation algorithm on layered networks computes near-optimal defender strategies for interdicting a moving criminal faster than MILP while preserving solution quality.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper models police interdiction of a time-varying criminal on a large transportation network as a Stackelberg game. It builds a layered graph with one copy of the network per time step so that defender resource placements can be evaluated against the attacker's best escape route, which is found by Dijkstra's algorithm. An approximation method is developed to select defender strategies without solving the full mixed-integer linear program. Experiments show the approximation delivers interdiction probabilities comparable to the exact MILP solver but finishes in far less time on sizable instances.

Core claim

Given a fixed defender strategy, the attacker's optimal path is the minimum-cost path on the layered graph; the approximation algorithm searches over defender placements to maximize the resulting interdiction probability and returns solutions whose quality is close to the MILP optimum but whose running time is substantially smaller.

What carries the argument

The time-layered graph in which each layer is an identical copy of the transportation network at one discrete time step; defender strategies assign limited resources across layers and the attacker's response is computed as a shortest path that minimizes capture probability.

If this is right

  • Defender planning on networks with hundreds of nodes becomes feasible within operational time limits.
  • The same layered construction and approximation can be reused for other dynamic pursuit-evasion problems on graphs.
  • Solution quality remains stable as the number of time steps or network size increases, provided the approximation parameters are held constant.
  • Police agencies can trade a small loss in guaranteed capture probability for orders-of-magnitude faster computation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the criminal can choose routes based on partial observations of police positions, the Dijkstra computation would no longer give the true best response.
  • The approach assumes the transportation network is fully known and static across days; real-world road closures or construction would require rebuilding the layers each time.
  • Extending the model to allow the attacker to wait or backtrack between layers would change the shortest-path computation and might require a different approximation guarantee.

Load-bearing premise

The attacker's optimal response is exactly the shortest path found by Dijkstra once any defender placement is fixed.

What would settle it

An instance on which the approximation returns an interdiction probability at least 10 percent lower than the MILP optimum on the same layered graph.

Figures

Figures reproduced from arXiv: 2406.14514 by Kei Kimura, Makoto Yokoo, Palash Dey, Sukanya Samanta.

Figure 1
Figure 1. Figure 1: Flowchart of Stackelberg game model. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Sample network for designing the optimal attacker strategy. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Design of a multi-layer network for attacker considering a sample network ( [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Sample network for designing near-optimal defender strategy [PITH_FULL_IMAGE:figures/full_fig_p027_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Design of a multi-layer network for defender considering a sample network ( [PITH_FULL_IMAGE:figures/full_fig_p028_5.png] view at source ↗
read the original abstract

Interdicting a criminal with limited police resources is a challenging task as the criminal changes location over time. The size of the large transportation network further adds to the difficulty of this scenario. To tackle this issue, we consider the concept of a layered graph. At each time stamp, we create a copy of the entire transportation network to track the possible movements of both players, the attacker and the defenders. We consider a Stackelberg game in a dynamic crime scenario where the attacker changes location over time while the defenders attempt to interdict the attacker on his escape route. Given a set of defender strategies, the optimal attacker strategy is determined by applying Dijkstra's algorithm on the layered networks. Here, the attacker aims to minimize while the defenders aim to maximize the probability of interdiction. We develop an approximation algorithm on the layered networks to find near-optimal strategy for defenders. The efficacy of the developed approach is compared with the adopted MILP approach. We compare the results in terms of computational time and solution quality. The quality of the results demonstrates the need for the developed approach, as it effectively solves the complex problem within a short amount of time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript models a dynamic Stackelberg interdiction game on transportation networks by constructing a layered graph (one copy of the network per time step) to track attacker and defender movements. For any fixed defender strategy the attacker's best response is obtained by running Dijkstra's algorithm on the layered graph; an approximation algorithm is then proposed to compute near-optimal defender placements. The approach is compared to an MILP formulation on computational time and solution quality, with the claim that the approximation solves the problem efficiently while preserving comparable quality.

Significance. If the layered-graph reduction and the Dijkstra best-response assumption are valid, the work would supply a scalable heuristic for time-dependent network interdiction problems that arise in security applications. The explicit comparison to MILP and the use of a standard shortest-path routine are positive features that could make the method reproducible and easy to implement.

major comments (1)
  1. [Abstract] Abstract (and the central modeling claim): the statement that 'the optimal attacker strategy is determined by applying Dijkstra's algorithm' treats the attacker's escape probability as an additive shortest-path cost on the layered graph. No aggregation rule (e.g., -log(1-p) transform) or independence assumption across layers or shared defender resources is stated. Because both the approximation algorithm and the MILP benchmark rely on this exact best-response oracle, any violation of the additive-probability model would invalidate the reported time/quality comparisons.
minor comments (1)
  1. [Abstract] The abstract asserts that the approximation 'outperforms MILP in time and quality' yet supplies no network sizes, run-time tables, solution-quality metrics, or error bars. These quantitative details are needed to evaluate the practical advantage.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for the opportunity to respond to the referee's report. We have carefully considered the major comment regarding the modeling assumptions in the abstract and provide our point-by-point response below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and the central modeling claim): the statement that 'the optimal attacker strategy is determined by applying Dijkstra's algorithm' treats the attacker's escape probability as an additive shortest-path cost on the layered graph. No aggregation rule (e.g., -log(1-p) transform) or independence assumption across layers or shared defender resources is stated. Because both the approximation algorithm and the MILP benchmark rely on this exact best-response oracle, any violation of the additive-probability model would invalidate the reported time/quality comparisons.

    Authors: We acknowledge that the referee's observation is correct: the abstract does not explicitly state the aggregation rule or independence assumptions underlying the use of Dijkstra's algorithm for the attacker's best response. This omission could affect the clarity of how the probability of interdiction is computed on the layered graph. We will revise the abstract and add a dedicated paragraph in the modeling section of the revised manuscript to specify that edge escape probabilities are assumed independent, that the path-level escape probability is their product, and that a negative-log transformation is applied to obtain additive costs suitable for shortest-path computation. The MILP benchmark will be described with the same explicit transformation to ensure consistency. These changes will not alter the algorithmic approach or the reported computational comparisons but will address the concern directly. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained against stated modeling assumptions.

full rationale

The paper models the dynamic interdiction problem via an explicit layered-graph construction and states that, for any fixed defender strategy, the attacker's optimal response is obtained by running Dijkstra on that graph. This is presented as a direct consequence of the chosen probability model rather than a derived claim. The approximation algorithm is then developed on top of this model and benchmarked against a separately formulated MILP solver; neither the runtime nor quality metrics are obtained by fitting parameters to the same data or by renaming a self-citation. No load-bearing step reduces by construction to an input that was itself obtained from the target result. The Dijkstra assumption is an explicit modeling choice whose validity can be checked externally; it does not create circularity within the paper's own derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on standard graph and game-theoretic assumptions without introducing new free parameters or invented entities visible in the abstract.

axioms (2)
  • domain assumption Transportation networks can be represented as directed graphs with time-expanded layers.
    Invoked when constructing the multi-layer network to track movements over time.
  • standard math Dijkstra's algorithm computes the minimum-interdiction-probability path for the attacker given fixed defender placements.
    Used to determine the optimal attacker strategy on the layered graph.

pith-pipeline@v0.9.0 · 5746 in / 1172 out tokens · 26845 ms · 2026-05-24T00:08:20.621347+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. CREST: Curvature-Regulated Event-Centric Sampling for Efficient Long-Video Understanding

    cs.CV 2026-05 unverdicted novelty 7.0

    CATS uses temporal curvature of query-frame relevance to select informative frames, achieving 93-95% of heavy multi-stage accuracy at 3-4% of the preprocessing cost on long-video benchmarks.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [1]

    A VNS-based metaheuristic approach for escape interdiction on transportation net- works

    Samanta, Sukanya, Mohandass Tushar, Sen Goutam, and Ghosh Soumya Kanti. “A VNS-based metaheuristic approach for escape interdiction on transportation net- works.” Computers & Industrial Engineering 169, (2022): 108253

    work page 2022

  2. [2]

    Vehicle Interdiction Strategy in Complex Road Networks-A Simulation Based Approach

    Samanta, Sukanya, Sen Goutam, and Ghosh Soumya Kanti. “Vehicle Interdiction Strategy in Complex Road Networks-A Simulation Based Approach.” 2021 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) (2021): 1299-1302

    work page 2021

  3. [3]

    Optimal escape interdiction on transportation networks

    Zhang, Youzhi, An Bo, Tran-Thanh Long, Wang Zhen, Gan Jiarui, and Jennings, Nicholas R. “Optimal escape interdiction on transportation networks.” Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (2017): 3936-3944. 34

    work page 2017

  4. [4]

    Coevolution of players strategies in se- curity games

    ˙Zychowski, Adam and Ma ´ndziuk Jacek. “Coevolution of players strategies in se- curity games.” Journal of Computational Science 68, (2023): 101980

    work page 2023

  5. [5]

    Computing the optimal strategy to com- mit to

    Conitzer, Vincent and Sandholm Tuomas. “Computing the optimal strategy to com- mit to.” Proceedings of the 7th ACM conference on Electronic commerce (2006): 82-90

    work page 2006

  6. [6]

    Playing games for security: An efficient exact algorithm for solving Bayesian Stackelberg games

    Paruchuri, Praveen, Pearce Jonathan P, Marecki Janusz, Tambe Milind, Ordonez Fernando, and Kraus Sarit. “Playing games for security: An efficient exact algorithm for solving Bayesian Stackelberg games.” Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-V olume 2, (2008): 895- 902

    work page 2008

  7. [7]

    Sequence-form algorithm for computing stackelberg equilibria in extensive-form games

    Bosansky, Branislav and Cermak Jiri. “Sequence-form algorithm for computing stackelberg equilibria in extensive-form games.” Proceedings of the AAAI Confer- ence on Artificial Intelligence 29, no. 1 (2015)

    work page 2015

  8. [8]

    Discovering influential nodes for SIS models in social networks

    Saito, Kazumi, Kimura Masahiro, and Motoda Hiroshi. “Discovering influential nodes for SIS models in social networks.” International Conference on Discovery Science (2009): 302-316

    work page 2009

  9. [9]

    Leader-follower strategies for robotic patrolling in environments with arbitrary topologies

    Basilico, Nicola, Gatti Nicola, Amigoni Francesco, and others. “Leader-follower strategies for robotic patrolling in environments with arbitrary topologies.” Proceed- ings of the International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS) (2009): 57-64

    work page 2009

  10. [10]

    Simpli- fying urban network security games with cut-based graph contraction

    Iwashita, Hiroaki, Ohori Kotaro, Anai Hirokazu, and Iwasaki Atsushi. “Simpli- fying urban network security games with cut-based graph contraction.” Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (2016): 205-213

    work page 2016

  11. [11]

    Solving security games on graphs via 35 marginal probabilities

    Letchford, Joshua and Conitzer Vincent. “Solving security games on graphs via 35 marginal probabilities.” Proceedings of the AAAI Conference on Artificial Intelli- gence 27, no. 1 (2013): 591-597

    work page 2013

  12. [12]

    PROTECT: An application of computational game theory for the security of the ports of the United States

    Shieh, Eric, An Bo, Yang Rong, Tambe Milind, Baldwin Craig, DiRenzo Joseph, Maule Ben, and Meyer Garrett. “PROTECT: An application of computational game theory for the security of the ports of the United States.” Proceedings of the AAAI Conference on Artificial Intelligence 26, no. 1 (2012): 2173-2179

    work page 2012

  13. [13]

    Urban security: Game-theoretic resource allocation in networked domains

    Tsai, Jason, Yin Zhengyu, Kwak Jun-young, Kempe David, Kiekintveld Christo- pher, and Tambe Milind. “Urban security: Game-theoretic resource allocation in networked domains.” Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (2010): 881-886

    work page 2010

  14. [14]

    Stackelberg security games: Looking beyond a decade of success

    Sinha, Arunesh, Fang Fei, An Bo, Kiekintveld Christopher, and Tambe Milind. “Stackelberg security games: Looking beyond a decade of success.” Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI- 18 (2018): 5494-5501

    work page 2018

  15. [15]

    Bayesian Stackelberg games for cyber- security decision support

    Zhang, Yunxiao and Malacaria Pasquale. “Bayesian Stackelberg games for cyber- security decision support.” Decision Support Systems 148, (2021): 113599

    work page 2021

  16. [16]

    Using correlated strategies for computing stackelberg equilibria in extensive-form games

    Cermak, Jiri, Bosansky Branislav, Durkota Karel, Lisy Viliam, and Kiekintveld Christopher. “Using correlated strategies for computing stackelberg equilibria in extensive-form games.” Proceedings of the AAAI Conference on Artificial Intel- ligence 30, no. 1 (2016)

    work page 2016

  17. [17]

    Incremental strategy generation for Stackelberg equilibria in extensive-form games

    ˇCern`y, Jakub, Bo `yansk`y Branislav, and Kiekintveld Christopher. “Incremental strategy generation for Stackelberg equilibria in extensive-form games.” Proceed- ings of the 2018 ACM Conference on Economics and Computation (2018): 151- 168

    work page 2018

  18. [18]

    A Monte Carlo Tree Search approach to 36 finding efficient patrolling schemes on graphs

    Karwowski, Jan and Ma ´ndziuk Jacek. “A Monte Carlo Tree Search approach to 36 finding efficient patrolling schemes on graphs.” European Journal of Operational Research 277, no. 1 (2019): 255-268

    work page 2019

  19. [19]

    Multidefender security games

    Lou, Jian, Smith Andrew M, and V orobeychik Yevgeniy. “Multidefender security games.” IEEE Intelligent Systems 32, no. 1 (2017): 50-60

    work page 2017

  20. [20]

    On Stackelberg mixed strategies

    Conitzer, Vincent. “On Stackelberg mixed strategies.” Synthese 193, no. 3 (2016): 689-703

    work page 2016

  21. [21]

    Lecture Note 16: Stackelberg equilibrium and Security Games

    Kroer, Christian. “Lecture Note 16: Stackelberg equilibrium and Security Games.” 2022

    work page 2022

  22. [22]

    Coordinating resources in stackelberg security games

    Bucarey, V ´ıctor, Casorr ´an Carlos Labb ´e Martine, Ordo ˜nez Fernando, and Figueroa Oscar. “Coordinating resources in stackelberg security games.” European Journal of Operational Research 291, no. 3 (2021): 846-861

    work page 2021

  23. [23]

    A review of attacker-defender games: Current state and paths forward

    Hunt, Kyle and Zhuang Jun. “A review of attacker-defender games: Current state and paths forward.” European Journal of Operational Research 313, no. 2 (2024): 401-417

    work page 2024

  24. [24]

    A study of general and security Stackelberg game formulations

    Casorr ´an, Carlos, Fortz Bernard, Labb´e Martine, and Ord´o˜nez Fernando. “A study of general and security Stackelberg game formulations.” European journal of oper- ational research 278, no. 3 (2019): 855-868

    work page 2019

  25. [25]

    A literature review on police patrolling problems

    Samanta, Sukanya, Sen Goutam, and Ghosh Soumya Kanti. “A literature review on police patrolling problems.” Annals of Operations Research 316, no. 2 (2022): 1063-1106. 37

    work page 2022