Pith. sign in

REVIEW 3 major objections 4 minor 61 references

Contested Route Planning

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Contested route planning can be solved as a two-player zero-sum game: double-oracle iteration with shortest-path and knapsack best responses computes approximate equilibria on realistic networks in seconds, with randomized routes beating de

desk verdict The contested-routing game is a reasonable framework, but the Red best-response oracle as written optimizes the wrong objective and the throughput metric is disconnected from the modeled utility, so the empirical claims are currently unsupported. read the letter →

arxiv 2508.10189 v1 pith:Z3QJIDQD submitted 2025-08-13 cs.GT

Jakub Černý , Garud Iyengar , Christian Kroer This is my paper · ORCID
classification cs.GT MSC 91A1091A8090B06
keywords contestedrouteplanningnetworkinterdictionzero-sumgameNashequilibriumdoubleoracleshortestpathknapsackrandomizedrouting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies routing through territory where an adversary can interdict edges, and argues that the right model is a two-player zero-sum game: Blue randomizes over paths, Red chooses a budget-limited set of edges to attack. The authors claim that although exact equilibrium computation is NP-hard, a double-oracle algorithm—alternately adding Blue's best response (a shortest path) and Red's best response (a knapsack solution)—computes approximate Nash equilibria on realistic road networks in seconds to minutes. If this holds, operational planners can deploy randomized, adversary-aware routes that are far less predictable and far more survivable than deterministic ones. On three OpenStreetMap-derived scenarios, the game-theoretic solutions outperform deterministic fastest and Red-aware routes by large factors, for example by more than 22x and 7x in the first scenario.

What carries the argument

The central mechanism is the double-oracle algorithm fed by two best-response oracles. At each iteration it solves the linear-program equilibrium of the restricted game, then asks Blue for a shortest path against Red's current mixed strategy (using Dijkstra or A*, since edge lengths remain nonnegative and additive) and asks Red for its best interdiction set against Blue's mixed strategy (a 0/1 knapsack problem, since each edge is an item with weight $C(e)$ and value $\sum_f \tilde{x}_b(f)(T(e)f(e)+P(e)f(e))$). The key structural fact is that both best responses are additive over edges, so they reduce to two classic, well-solved problems even though the full strategy spaces are exponential. T

What would settle it

Re-solve one of the published scenarios with the payoff matrix replaced by the product-form throughput that the evaluation uses, and compare the equilibrium value to the double-oracle solution under the additive utility. If the product-game equilibrium achieves strictly higher expected throughput than the additive-game solution, or if on a small graph one can exhibit mixed strategies with better multiplicative survival than the additive equilibrium, the claimed operational advantage fails. The paper's own robustness tables (e.g., Scenario 1 diagonal vs off-diagonal entries) flag where such a d

Watch

Extended reading notes

Core claim

The paper introduces contested route planning as a simultaneous-move zero-sum game on a directed graph: Blue chooses a path $f$ from start to release, Red chooses an interdiction set $y$ under budget, and Blue's payoff is $u(f,y)=\sum_{e\in E} T(e)f(e)+P(e)f(e)y(e)$, the baseline traversal cost plus penalties for interdicted edges. It proves that finding a Nash equilibrium is NP-hard via a line-graph reduction from Knapsack, and that Red's best response is also NP-hard while Blue's best response is polynomial: against a fixed mixed Red strategy, Blue solves a shortest-path problem with edge lengths $\ell(e)=\sum_{y}\tilde{x}_r(y)(T(e)+P(e)y(e))$, and against a fixed mixed Blue strategy, Red

Load-bearing premise

The load-bearing premise is that the additive sum of penalties the game optimizes is a faithful proxy for the multiplicative survival/throughput metric the experiments actually report: if a route that minimizes expected additive cost does not also maximize expected probability of completing the trip against an optimal Red, the headline gains over deterministic baselines would not transfer to real operations.

Editorial extensions

If this is right

  • Tactical replanning becomes operationally viable: a new randomized route plan can be recomputed in seconds to a few minutes when a bridge, tunnel, or threat changes the map.
  • Randomized equilibrium routes remove the predictability vulnerability of deterministic routing: repeated trips draw from a support of paths, so Red cannot concentrate attacks on one known route.
  • Explicitly modeling Red's budget is a dial: the reported robustness tables show that planning for the wrong adversary strength can cost roughly half the throughput in some cases, so adversary modeling is not a cosmetic extra.
  • The modular oracle structure means vehicle-specific constraints (turn restrictions, forbidden edge sequences, timing) can be added without redesigning the equilibrium loop, as long as Blue's best response remains a shortest-path-style flow problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct testable extension the authors leave implicit is to solve the same scenarios with payoffs replaced by log survival probabilities per edge, so that realized log-throughput is additive and the same shortest-path and knapsack oracles apply; the equilibrium concept would become expected log-throughput rather than expected throughput, and comparing operational throughput would reveal whether t
  • The double-oracle decomposition is not tied to single-vehicle routing: any higher-level logistics scheme that decomposes into point-to-point legs can pass each leg to this solver, and the resulting randomization can de-synchronize convoys—something the paper gestures toward but does not demonstrate.
  • A practical deployment diagnostic would be to report the support size and entropy of Blue's mixed strategy as a function of Red budget; the paper reports iteration counts but not support sizes, and its observation that support grows only in some scenarios suggests this metric would predict where randomization matters most.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces a two-player zero-sum game for contested route planning: Blue chooses a path in a graph, while Red chooses a budget-constrained set of edges to interdict. The utility is additive: traversal cost plus an additional penalty on interdicted edges. The authors state existence via minimax, prove NP-hardness of equilibrium computation and of Red's best response, cast Blue's best response as a shortest-path problem and Red's as a knapsack problem, and propose a double-oracle algorithm. They evaluate the algorithm on OpenStreetMap-derived networks for Southern California and Ukraine, reporting runtimes on the order of seconds and large throughput improvements over deterministic baselines. The central claim is that the double-oracle framework computes approximate Nash equilibria at realistic scale and that these equilibria yield robust, randomized routing plans.

Significance. If correct, the paper offers a practical tool for adversarial route planning, with a clean game-theoretic formulation and a modular double-oracle design. The connection to shortest path and knapsack oracles is appealing, and the experimental setup is realistic. A notable strength is that the solution concept is defined independently of the experimental results, so there is no parameter fitting to a target outcome. However, the correctness of the algorithm depends crucially on the Red best-response oracle, and the manuscript contains a concrete error in the derivation of that oracle. In addition, the evaluation metric (multiplicative throughput) is not formally connected to the additive utility for which equilibria are computed. These issues are load-bearing for the paper's central claims, so the significance is conditional on their resolution.

major comments (3)
  1. [Section 4, Eq. (Red-BR) and p(e)] The knapsack reduction for Red's best response is incorrect. In (Red-BR), the term T(e)f(e) is independent of y and cannot contribute to the marginal value of interdicting e. The item value should be p(e)=Σ_f \tilde x_b(f) P(e) f(e). The stated p(e)=Σ_f \tilde x_b(f)(T(e)f(e)+P(e)f(e)) adds T(e)·Pr_f(e∈f), which changes the optimization. Example: e1,e2 with T(e1)=100,P(e1)=1 and T(e2)=1,P(e2)=100; Blue mixes 50/50 over paths {e1},{e2}; budget 1. Correct values are (0.5,50), so Red should select e2 with payoff 100.5. The paper's values are (50.5,50.5), so a tie-break can select e1 with payoff only 51. Since Section 5 says the Red oracle is implemented with dynamic programming for knapsack, the double oracle may use a suboptimal Red best response and terminate at a non-equilibrium profile.
  2. [Section 5 vs Section 3.3] The game is solved for the additive utility u(f,y)=Σ_e T(e)f(e)+P(e)f(e)y(e), but the headline evaluation uses multiplicative throughput. In Section 5, P(e)=1 for low-risk edges and 3 for high-risk edges, while throughput is computed as a product over interdicted edges of factors 0.2 (low) and 0.5 (high). If these factors are survival probabilities, then an additive objective for expected log-throughput would require P(e) proportional to −log(survival), giving a high/low ratio of about 2.32, not 3. No derivation connects the additive game solution to the multiplicative throughput metric. Consequently, the reported equilibria are not shown to maximize expected survival probability, and the claims such as 'improves throughput by more than 22 and 7 times' are not grounded in the solved game.
  3. [Section 4.1, Algorithm 1] The termination condition ∇ = u(\tilde x_b^*, y^{BR}) − u(f^{BR}, \tilde x_r^*) is a valid certificate of a 2ε-approximate Nash equilibrium only if both oracles return exact best responses. With the incorrect Red knapsack item values from Section 4, y^{BR} can be suboptimal, making u(\tilde x_b^*, y^{BR}) an underestimate of Red's true value. The algorithm can therefore stop with a large true equilibrium gap even when the reported gap is below ε. The statement immediately before Section 5 that the returned pair 'forms a 2ε-approximate Nash equilibrium' does not follow from the oracle as described.
minor comments (4)
  1. [Section 5, throughput definition] The expression E_{y∼xr} ∏_{e∈y} p(e) does not depend on Blue's path f. It should presumably be ∏_{e∈f∩y} p(e) or similar. Please clarify the notation and also whether p(e) denotes kill probability or survival probability; the text says 'p-k' but the numerical values behave like survival probabilities.
  2. [Section 3.1, cycle handling] The MILP (F) allows cyclic flows, and the assertion that the additive utility 'implicitly eliminates cycles' is informal. For positive T(e), any optimal path under the utility is simple, but the strategy space as defined is a flow polytope and includes cycles. This should be stated more carefully.
  3. [Section 5, baselines] The 'Red-aware deterministic path' is not formally defined. Its construction and optimality status are unclear, which makes the headline improvement factors difficult to interpret as a comparison against a well-specified baseline.
  4. [Tables 3, 5, 7] The header 'Exp.' is not expanded; it appears to mean the Red budget for which the game-theoretic solution was computed. Please rename for clarity, e.g., 'Solution budget'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation is self-contained.

full rationale

The contested route planning game is defined independently: the utility u(f,y) is a stated modeling choice, and equilibrium existence follows from von Neumann's minimax theorem. The double-oracle framework is used in its standard form; its correctness depends on exact best-response oracles, not on any fitted parameter or on the target result being assumed. Blue's best response reduces to a shortest-path problem and Red's to a knapsack problem; these reductions do not import the equilibrium being computed as an input. The citation of [13,14,35] for the observation that equilibria often have small support is a motivational remark and is not load-bearing: the algorithm would still produce an approximate equilibrium with exact best responses even if supports were large, and the experiments independently demonstrate convergence. The paper does not fit parameters to the reported throughput values; the additive utility is the model, and throughput is an external evaluation metric. A formal concern exists in the Red best-response reduction where the stated item value p(e)=Σ_f x̃_b(f)(T(e)f(e)+P(e)f(e)) includes the traversal term, which is constant in the Red-BR objective; that is a correctness issue in the reduction, not a circularity, and it does not make any prediction equivalent to its inputs by construction. No circular step is present.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard game-theoretic machinery plus domain assumptions about small-support equilibria and additive interdiction effects. The hand-tuned cost and penalty parameters are model inputs, not fitted to the target result. No new physical or mathematical entities are postulated.

free parameters (3)
  • Cost normalization constants in C(e) = 0.8, 1.3, floor scaling
    Hand-selected coefficients in the interdiction cost normalization formula in Section 5. They shape Red's action space and can change the equilibrium.
  • Penalty weights P(e) = 1 (regular), 3 (bridge)
    Hand-assigned edge penalties in utility u, Section 5. The relative values determine the trade-off between base cost and interdiction penalty; no data calibration is given.
  • Throughput survival probabilities p(e) = 0.5 (high p-k), 0.2 (low p-k)
    Used only in the evaluation metric, Section 5. The values are not linked to P(e) used in the game, and 0.2 appears to be a typo for 0.8 if p(e) means survival probability.
assumptions (5)
  • standard math Von Neumann minimax theorem for finite zero-sum games
    Used in Section 4 to assert existence of equilibrium and a well-defined game value.
  • standard math 0/1 knapsack is NP-hard and solvable in pseudo-polynomial time
    Basis for Proposition 1 and Corollary 1, Section 4.
  • standard math Network flow polytope is integral (total unimodularity)
    Used in Proposition 2 to show Blue's best response reduces to an LP and to a shortest path problem, Section 4.
  • domain assumption Nash equilibria of contested route planning games have small support
    Assumed in Section 4.1, citing refs [13,14,35], but not proved for this game. The scalability claim of the double oracle depends on this assumption.
  • domain assumption Interdiction effects are additive and edge-independent in Blue's utility
    The utility u(f,y) in Section 3.3 adds penalties per interdicted edge traversed; correlated, capacity, or route-avoidance effects are excluded. This makes Red's best response a knapsack but limits model fidelity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Contested Route Planning." pith.science (2026). https://pith.science/paper/Z3QJIDQD

@misc{pith2026250810189,
  author       = {Pith},
  title        = {Pith review of: Contested Route Planning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z3QJIDQD}},
  note         = {Machine review of arXiv:2508.10189}
}
read the original abstract

We consider the problem of routing for logistics purposes, in a contested environment where an adversary attempts to disrupt the vehicle along the chosen route. We construct a game-theoretic model that captures the problem of optimal routing in such an environment. While basic robust deterministic routing plans are already challenging to devise, they tend to be predictable, which can limit their effectiveness. By introducing calculated randomness via modeling the route planning process as a two-player zero-sum game, we compute immediately deployable plans that are diversified and harder to anticipate. Although solving the game exactly is intractable in theory, our use of the double-oracle framework enables us to achieve computation times on the order of seconds, making the approach operationally viable. In particular, the framework is modular enough to accommodate specialized routing algorithms as oracles. We evaluate our method on real-world scenarios, showing that it scales effectively to realistic problem sizes and significantly benefits from explicitly modeling the adversary's capabilities, as demonstrated through ablation studies and comparisons with baseline approaches.

Figures

Figures reproduced from arXiv: 2508.10189 by the authors.

Figure 1
Figure 1. The line graph described Proposition 1, serving as physical graph for [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Typical scenery and fastest and red-aware routes in Scenario 1. [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Computed game-theoretic solutions in Scenario 1. [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The game-theoretic solutions for this scenario are presented in Fig [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: Computed game-theoretic solutions in Scenario 2. [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: The corresponding game-theoretic solutions are presented in Figure 7. [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]
Figure 6
Figure 6. Figure 6: Typical scenery and fastest and red-aware routes in Scenario 3. [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: Computed game-theoretic solutions in Scenario 3. [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 55 canonical work pages

  1. [1]

    Computers & operations research 40(3), 856–866 (2013)

    Agra, A., Christiansen, M., Figueiredo, R., Hvattum, L.M., Poss, M., Requejo, C.: The robust vehicle routing problem with time windows. Computers & operations research 40(3), 856–866 (2013)

    work page 2013

  2. [2]

    Computers & In- dustrial Engineering 115, 190–205 (2018)

    Alotaibi, K.A., Rosenberger, J.M., Mattingly, S.P., Punugu, R.K., Visoldilokpun, S.: Unmanned aerial vehicle routing in the presence of threats. Computers & In- dustrial Engineering 115, 190–205 (2018)

    work page 2018

  3. [3]

    Improving Homeland Security Decisions p

    An, B., Tambe, M., Sinha, A.: Stackelberg security games (ssg) basics and appli- cation overview. Improving Homeland Security Decisions p. 485 (2017)

    work page 2017

  4. [4]

    IBM Journal of Research and Development51(3.4), 391–407 (2007) Contested Route Planning 19

    Barahona, F., Chowdhary, P., Ettl, M., Huang, P., Kimbrel, T., Ladanyi, L., Lee, Y.M., Schieber, B., Sourirajan, K., Sviridenko, M.I., et al.: Inventory allocation and transportation scheduling for logistics of network-centric military operations. IBM Journal of Research and Development51(3.4), 391–407 (2007) Contested Route Planning 19

    work page 2007

  5. [5]

    Algorithm engineering: Selected results and surveys pp

    Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route planning in transportation networks. Algorithm engineering: Selected results and surveys pp. 19–80 (2016)

    work page 2016

  6. [6]

    Beaumont, P.: Ukraine attacks key russian held bridge in kher- son (2022), https://www.theguardian.com/world/live/2022/jul/27/ russia-ukraine-live-news-ukraine-attacks-key-kherson-bridge-in-bid-to-isolate-russian-forces, accessed: 2025-06-05

    work page 2022

  7. [7]

    Applications of location analysis pp

    Bell, J.E., Griffis, S.E.: Military applications of location analysis. Applications of location analysis pp. 403–433 (2015)

    work page 2015

  8. [8]

    Computers & Industrial Engineering115, 520–531 (2018)

    Bidgoli, M.M., Kheirkhah, A.: An arc interdiction vehicle routing problem with information asymmetry. Computers & Industrial Engineering115, 520–531 (2018)

    work page 2018

Show all 61 references
  1. [9]

    The Journal of Defense Modeling and Simulation17(1), 55–81 (2020)

    Blom, M., Shekh, S., Gossink, D., Miller, T., Pearce, A.R.: Inventory routing for defense: Moving supplies in adversarial and partially observable environments. The Journal of Defense Modeling and Simulation17(1), 55–81 (2020)

    2020

  2. [10]

    arXiv preprint arXiv:1408.6127 (2014)

    Boidot, E., Marzuoli, A., Feron, E.: A complete framework for ambush avoidance in realistic environments. arXiv preprint arXiv:1408.6127 (2014)

    2014 arXiv

  3. [11]

    American Mathematical Soc

    Bonato, A.: The game of cops and robbers on graphs. American Mathematical Soc. (2011)

    2011

  4. [12]

    IEEE Transactions on Robotics24(6), 1429–1439 (2008)

    Bopardikar, S.D., Bullo, F., Hespanha, J.P.: On discrete-time pursuit-evasion games with sensing limitations. IEEE Transactions on Robotics24(6), 1429–1439 (2008)

    2008

  5. [13]

    In: International Conference on Decision and Game Theory for Security

    Černý, J., Ling, C.K., Chakrabarti, D., Zhang, J., Farina, G., Kroer, C., Iyengar, G.: Contested logistics: A game-theoretic approach. In: International Conference on Decision and Game Theory for Security. pp. 124–146. Springer (2024)

    2024

  6. [14]

    In: Proceedings of the Thirty-third International Joint Conference on Artificial Intel- ligence, IJCAI-24

    Černý, J., Ling, C.K., Kroer, C., Iyengar, G.: Layered graph security games. In: Proceedings of the Thirty-third International Joint Conference on Artificial Intel- ligence, IJCAI-24. International Joint Conferences on Artificial Intelligence Orga- nization (2024)

    2024

  7. [15]

    Mathematical programming73(2), 129–174 (1996)

    Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: Theory and experimental evaluation. Mathematical programming73(2), 129–174 (1996)

    1996

  8. [16]

    Annals of the Association of American Geographers94(3), 491–502 (2004)

    Church, R.L., Scaparra, M.P., Middleton, R.S.: Identifying critical infrastructure: the median and covering facility interdiction problems. Annals of the Association of American Geographers94(3), 491–502 (2004)

    2004

  9. [17]

    Annals of the Association of American Geographers100(3), 600–620 (2010)

    Cowen, D.: A geography of logistics: Market authority and the security of supply chains. Annals of the Association of American Geographers100(3), 600–620 (2010)

    2010

  10. [18]

    Springer Science & Business Media (2005)

    Daganzo, C.: Logistics systems analysis. Springer Science & Business Media (2005)

    2005

  11. [19]

    In: Algorithmics of large and complex networks: design, analysis, and simulation, pp

    Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering route planning algorithms. In: Algorithmics of large and complex networks: design, analysis, and simulation, pp. 117–139. Springer (2009)

    2009

  12. [20]

    In: Edsger Wybe Dijkstra: his life, work, and legacy, pp

    Dijkstra, E.W.: A note on two problems in connexion with graphs. In: Edsger Wybe Dijkstra: his life, work, and legacy, pp. 287–290 (2022)

    2022

  13. [21]

    Courier Corporation (2013)

    Friedman, A.: Differential games. Courier Corporation (2013)

    2013

  14. [22]

    Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 29. wh freeman New York (2002)

    2002

  15. [23]

    John Wiley & Sons (2004)

    Ghiani, G., Laporte, G., Musmanno, R.: Introduction to logistics systems planning and control. John Wiley & Sons (2004)

    2004

  16. [24]

    In: SODA

    Goldberg, A.V., Harrelson, C.: Computing the shortest path: A search meets graph theory. In: SODA. vol. 5, pp. 156–165 (2005)

    2005

  17. [25]

    Naval Research Logistics (NRL)64(2), 139–153 (2017) 20 J

    Goldberg, N.: Non-zero-sum nonlinear network path interdiction with an appli- cation to inspection in terror networks. Naval Research Logistics (NRL)64(2), 139–153 (2017) 20 J. Černý et al

    2017

  18. [26]

    IEEE transactions on Systems Science and Cybernet- ics 4(2), 100–107 (1968)

    Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determina- tion of minimum cost paths. IEEE transactions on Systems Science and Cybernet- ics 4(2), 100–107 (1968)

    1968

  19. [27]

    Handbook of military industrial engineering (2009)

    Hill,R.,Pohl,E.:Anoverviewofmeta-heuristicsandtheiruseinmilitarymodeling. Handbook of military industrial engineering (2009)

    2009

  20. [28]

    Mathemat- ical Programming Computation10(1), 119–142 (2018)

    Huangfu, Q., Hall, J.J.: Parallelizing the dual revised simplex method. Mathemat- ical Programming Computation10(1), 119–142 (2018)

    2018

  21. [29]

    com/article/bombing-burmas-bridges/, accessed: 2025-06-05

    Huntington, T.: Bombing burma’s bridges (2021), https://warfarehistorynetwork. com/article/bombing-burmas-bridges/, accessed: 2025-06-05

    2021

  22. [30]

    Courier Corporation (1999)

    Isaacs, R.: Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Courier Corporation (1999)

    1999

  23. [31]

    Networks: An Inter- national Journal 40(2), 97–111 (2002)

    Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks: An Inter- national Journal 40(2), 97–111 (2002)

    2002

  24. [32]

    In: Moving Target Defense II: Application of Game Theory and Adversarial Modeling

    Jain, M., An, B., Tambe, M.: Security games applied to real-world: Research contri- butions and challenges. In: Moving Target Defense II: Application of Game Theory and Adversarial Modeling. pp. 15–39. Springer (2013)

    2013

  25. [33]

    In: The 10th In- ternational Conference on Autonomous Agents and Multiagent Systems-Volume 1

    Jain, M., Korzhyk, D., Vaněk, O., Conitzer, V., Pěchouček, M., Tambe, M.: A double oracle algorithm for zero-sum security games on graphs. In: The 10th In- ternational Conference on Autonomous Agents and Multiagent Systems-Volume 1. pp. 327–334. Citeseer (2011)

    2011

  26. [34]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Korzhyk, D., Conitzer, V., Parr, R.: Complexity of computing optimal stackel- berg strategies in security resource allocation games. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 24, pp. 805–810 (2010)

    2010

  27. [35]

    arXiv preprint arXiv:2505.14547 (2025)

    Krever, N., Čern` y, J., Blanchard, M., Kroer, C.: Guard: Constructing realistic two- player matrix and security games for benchmarking game-theoretic algorithms. arXiv preprint arXiv:2505.14547 (2025)

    2025 arXiv

  28. [36]

    Journal of the Operational Research Society 63(9), 1294–1306 (2012)

    Lee, C., Lee, K., Park, S.: Robust vehicle routing problem with deadlines and travel time/demand uncertainty. Journal of the Operational Research Society 63(9), 1294–1306 (2012)

    2012

  29. [37]

    In: MATEC web of conferences

    Lee, J.M.y., Wong, E.Y.c.: Suez canal blockage: an analysis of legal impact, risks and liabilities to the global supply chain. In: MATEC web of conferences. vol. 339, p. 01019. EDP Sciences (2021)

    2021

  30. [38]

    John Wiley & Sons, Inc

    Martello, S., Toth, P.: Knapsack problems: algorithms and computer implementa- tions. John Wiley & Sons, Inc. (1990)

    1990

  31. [39]

    McMahon, C.J.: Maritime trade warfare: a strategy for the twenty-first century? Naval War College Review70(3), 14–38 (2017)

    2017

  32. [40]

    Neumann, J.: Zur theorie der gesellschaftsspiele

    v. Neumann, J.: Zur theorie der gesellschaftsspiele. Mathematische annalen100(1), 295–320 (1928)

    1928

  33. [41]

    In: Risk and optimization in an uncertain world, pp

    Ordóñez, F.: Robust vehicle routing. In: Risk and optimization in an uncertain world, pp. 153–178. INFORMS (2010)

    2010

  34. [42]

    In: Theory and Applications of Graphs: Proceedings, Michigan May 11–15, 1976, pp

    Parsons, T.D.: Pursuit-evasion in a graph. In: Theory and Applications of Graphs: Proceedings, Michigan May 11–15, 1976, pp. 426–441. Springer (2006)

    1976

  35. [43]

    The faculty of ILiM, Poznań (1998)

    Pfohl, H.C.: Logistics systems. The faculty of ILiM, Poznań (1998)

    1998

  36. [44]

    Operations Re- search 45(5), 758–767 (1997)

    Pisinger, D.: A minimal algorithm for the 0-1 knapsack problem. Operations Re- search 45(5), 758–767 (1997)

    1997

  37. [45]

    Discrete Applied Mathematics 89(1-3), 197–212 (1998)

    Pisinger, D.: A fast algorithm for strongly correlated knapsack problems. Discrete Applied Mathematics 89(1-3), 197–212 (1998)

    1998

  38. [46]

    In: AAAI

    Pita, J., Jain, M., Ordónez, F., Portway, C., Tambe, M., Western, C., Paruchuri, P., Kraus, S.: Armor security for los angeles international airport. In: AAAI. pp. 1884–1885 (2008) Contested Route Planning 21

    2008

  39. [47]

    Operations Research24(2), 314–324 (1976)

    Ruckle, W., Fennell, R., Holmes, P.T., Fennemore, C.: Ambushing random walks i: Finite models. Operations Research24(2), 314–324 (1976)

    1976

  40. [48]

    International transactions in operational research 27(2), 835–866 (2020)

    Sadati, M.E.H., Aksen, D., Aras, N.: The r-interdiction selective multi-depot ve- hicle routing problem. International transactions in operational research 27(2), 835–866 (2020)

    2020

  41. [49]

    Journal of Transportation Security3, 41–55 (2010)

    Salani, M., Duyckaerts, G., Swartz, P.G.: Ambush avoidance in vehicle routing for valuable delivery. Journal of Transportation Security3, 41–55 (2010)

    2010

  42. [50]

    Military Operations Research pp

    Salmeron, J., Wood, R.K., Morton, D.P.: A stochastic program for optimizing military sealift subject to attack. Military Operations Research pp. 19–39 (2009)

    2009

  43. [51]

    John Wiley & Sons (1998)

    Schrijver, A.: Theory of linear and integer programming. John Wiley & Sons (1998)

    1998

  44. [52]

    In: Proceedings of the 11th international conference on autonomous agents and multiagent systems-volume 1

    Shieh, E., An, B., Yang, R., Tambe, M., Baldwin, C., DiRenzo, J., Maule, B., Meyer, G.: Protect: A deployed game theoretic system to protect the ports of the united states. In: Proceedings of the 11th international conference on autonomous agents and multiagent systems-volume ...

    2012

  45. [53]

    Pareto optimality, game theory and equilibria pp

    Smith, J.C., Lim, C.: Algorithms for network interdiction and fortification games. Pareto optimality, game theory and equilibria pp. 609–644 (2008)

    2008

  46. [54]

    European Journal of Operational Research283(3), 797–811 (2020)

    Smith, J.C., Song, Y.: A survey of network interdiction models and algorithms. European Journal of Operational Research283(3), 797–811 (2020)

    2020

  47. [55]

    Iie Transactions 40(5), 509–523 (2008)

    Sungur, I., Ordónez, F., Dessouky, M.: A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. Iie Transactions 40(5), 509–523 (2008)

    2008

  48. [56]

    Operations research 43(2), 243–251 (1995)

    Washburn, A., Wood, K.: Two-person zero-sum games for network interdiction. Operations research 43(2), 243–251 (1995)

    1995

  49. [57]

    In: 2020 American Control Conference (ACC)

    Weintraub, I.E., Pachter, M., Garcia, E.: An introduction to pursuit-evasion differ- ential games. In: 2020 American Control Conference (ACC). pp. 1049–1066. IEEE (2020)

    2020

  50. [58]

    Operations Research12(6), 934–940 (1964)

    Wollmer, R.: Removing arcs from a network. Operations Research12(6), 934–940 (1964)

    1964

  51. [59]

    In: Proceedings of the 2016 ACM Conference on Eco- nomics and Computation

    Xu, H.: The mysteries of security games: Equilibrium computation becomes com- binatorial algorithm design. In: Proceedings of the 2016 ACM Conference on Eco- nomics and Computation. pp. 497–514 (2016)

    2016

  52. [60]

    https://github.com/radualexandrub/knapsack-library (2020), ac- cessed: 2025-06-09

    Yaneva, M., Marinov, P., Alexandru-Bucur, R.: Kpym: A c++ knapsack problem solver. https://github.com/radualexandrub/knapsack-library (2020), ac- cessed: 2025-06-09

    2020

  53. [61]

    Zhang, Y., An, B., Tran-Thanh, L., Wang, Z., Gan, J., Jennings, N.R.: Optimal escape interdiction on transportation networks (2017)

    2017

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.