REVIEW 4 major objections 5 minor 27 references
Approximate solutions to games of ordered preference
T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper claims that a warm-started lexicographic best-response algorithm computes approximate-optimal solutions for receding-horizon games of ordered preference, cutting solve times by orders of magnitude in simulated traffic.
desk verdict A useful warm-starting trick for lexicographic trajectory games with real speedups, but the optimality evidence is self-referential and the convergence claim needs qualification before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the lexicographic IBR-over-time update: at each receding-horizon decision stage, the coupled game is split into per-agent single-player problems, each agent solves its preference levels in order from highest to lowest priority, and constraints introduced at each level preserve the optimal values already achieved at higher-priority levels. The key acceleration mechanism is the warm start: the first guess of every other agent's trajectory is the previous decision stage's trajectory, shifted by the turn length and padded to fill the horizon, which is available at no extra cost in receding-horizon operation. This initialization is what reduces the number of IBR iterations needed and keeps each subproblem small enough to be solved with standard optimization software; the per-agent problems can also be solved in parallel.
What would settle it
Run the same Monte Carlo traffic scenarios, solve the baseline coupled formulation to a reference generalized Nash equilibrium, and compute the L1 distance from the IBR-over-time trajectory to that reference; if the distance to the reference stays large even when consecutive IBR iterations are close, the reported stability metric is not evidence of approximate optimality.
Extended reading notes
Core claim
The central claim is that lexicographic IBR over time efficiently computes approximate-optimal solutions for receding-horizon games of ordered preference, converging toward generalized Nash equilibria—joint trajectories from which no agent can improve a higher-priority objective without violating constraints or sacrificing a lower-priority goal. In a receding-horizon setting, agents repeatedly re-optimize over a short horizon and execute only the first few decisions before re-planning. Rather than solving the fully coupled optimization once per decision stage, the algorithm decomposes the game into single-player lexicographic optimizations, one per agent, in which each agent optimizes its own ranked objectives while the other agents' trajectories are treated as fixed parameters. The first iteration's predictions come from the previous decision stage's solution, shifted in time and padded, so the algorithm starts close to where the equilibrium is expected to be; subsequent iterations refine those predictions. In the reported Monte Carlo experiments, solve times drop from 44.51 s to 0.36 s at two preference levels and from 2676 s to 0.32 s at three levels, and the L1 distance between one iteration's solution and the next stabilizes after a handful of iterations. The paper stops short of claiming exact convergence, noting that for some problems the iterates do not reach a stable equilibrium and the iteration limit terminates the algorithm.
Load-bearing premise
The experiments measure quality by the L1 distance between the solution at iteration L and the solution at iteration L+1, and assume this self-consistency is a proxy for proximity to a true equilibrium; no comparison to the baseline coupled solution or to an independent equilibrium certificate is reported.
Editorial extensions
If this is right
- Receding-horizon games of ordered preference become fast enough for real-time use: tested solve times drop from 44.51 s to 0.36 s at two preference levels and from 2676 s to 0.32 s at three levels.
- The computational advantage grows with the number of preference levels, because the per-agent subproblems are far smaller than the flattened coupled problem and each agent's optimization can be carried out independently.
- A small iteration limit (L=1 to L=5) already produces trajectories that stop changing appreciably, so operators can trade a little optimality for large compute savings.
- Because the warm start uses only the previous decision stage's solution, the algorithm is a natural fit for receding-horizon and model-predictive settings where that information is always available.
Reading between the lines
- Editorial inference: isolating the warm start by comparing it with a cold-start or constant-velocity initialization would show how much of the speedup comes from reusing past plans rather than from IBR itself.
- Editorial inference: benchmarking the IBR-over-time trajectories against the baseline coupled solution as a reference would turn the speed claim into a quantified suboptimality claim; the current self-consistency metric alone is not a certificate of equilibrium.
- Editorial inference: the same decomposition should transfer to other receding-horizon multi-agent domains—robot navigation, human-robot collaboration, intersection management—whenever objectives are strictly ranked and a previous plan is available to shift and pad.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes 'lexicographic IBR over time,' an iterated best-response scheme for receding-horizon games of ordered preference, in which each agent's previous solution is shifted and padded to warm-start the next decision stage. The authors claim that this method efficiently computes approximate-optimal solutions and converges toward generalized Nash equilibria, and they report large computational speedups over a monolithic MCP baseline in two simulated traffic scenarios. The paper includes qualitative demonstrations with different preference hierarchies and a Monte Carlo efficiency study summarized in Table I.
Significance. If the correctness claim were established, the proposed method would be practically valuable: it would make lexicographic trajectory games tractable in receding-horizon settings with much lower solve times, and it would enable larger numbers of preference levels and longer horizons. The paper also ships code and a benchmark package, which is commendable and aids reproducibility. However, the central claim of approximate optimality and convergence toward GNE is not supported by the current evidence, because the only quantitative quality metric measures the algorithm's own successive iterates rather than any externally defined notion of equilibrium error.
major comments (4)
- [§IV-C, Table I] The evaluation metric is the L1 distance between the solution at iteration L and the solution at iteration L+1. This is a self-consistency measure, not a distance to a generalized Nash equilibrium: a sequence with shrinking successive differences can remain far from any fixed point, and a converged trajectory could still have a nonzero gap to the next iterate if the best-response map is not a contraction. The manuscript's own data are non-monotonic (for K=2 the distance increases from 1.28e-6 at L=20 to 2.45e-6 at L=1000; for K=3 it increases from 3.03e-5 at L=10 to 8.51e-5 at L=20), and the text states that 'the final average L1 distance does not reach zero' and that 'IBR does not converge to a stable equilibrium for some problems.' Consequently, the abstract's claim that the method 'converges towards generalized Nash equilibria' and the term 'approximate-optimal' are not supported by the reported evidence. The authors should report an independent equilibrium-quality measure, such as distance to the baseline MCP solution or a KKT/equilibrium residual for the coupled game.
- [§IV-C, Baseline] The baseline MCP formulation is used only for timing comparisons; the paper never compares the trajectories produced by IBR over time with the baseline's trajectories for the same 20 Monte Carlo scenarios. Without such a comparison, 'approximate-optimal' has no external reference point. Since the baseline is already implemented and run, computing the L1 (or other) distance between IBR output and baseline output is feasible and would directly test the approximation claim. At minimum, a single representative scenario with both solutions overlaid, or a table of trajectory distances, would substantially strengthen the paper.
- [§III-B, reference [25]] The convergence argument rests on the sentence 'Under certain assumption that are true for games of ordered preference IBR converges to a Nash equilibrium [25],' but the required assumptions are neither stated nor verified. The games here involve lexicographic nested optimization, complementarity constraints, and shared coupling constraints, and the experiments themselves show non-convergence in some runs. The authors should either state the assumptions from [25], verify them for the specific problem class, and reconcile them with the observed non-convergence, or substantially weaken the convergence claim in the abstract and conclusion.
- [Algorithm 2, §IV-C] Algorithm 2 terminates when 'solution improvement < epsilon,' but 'solution improvement' is never defined and the value of epsilon is not reported. If the improvement is the L1 distance between successive IBR iterates, then the primary evaluation metric in Table I is exactly the algorithm's stopping criterion, making the quality assessment circular. The metric must be defined, epsilon reported, and ideally the evaluation should use a quantity that is not the termination condition.
minor comments (5)
- [Eq. (3)] Equation (3) sums the partial cost l^i over t = 0 to T_g - 1, but l^i is defined over the next T decisions, so terms like z_{t:t+T-1} exceed the game horizon for t > T_g - T; the sum should range over decision-making stages t = m*T_l, or the notation should be adjusted.
- [§II-C] The text says the optimal strategy is 'the solution computed for the first level of the lexicographic minimization problem, z_{K_i}.' Since K_i is the outermost/lowest-priority level and the hierarchy is defined with level 1 as the highest priority, 'first level' is misleading; it should say 'lowest-priority level' or 'outermost level.'
- [§III-B] There is a typo: 'For each each preference level k' should read 'For each preference level k.'
- [Table I] The table reports averages over 20 runs without standard deviations, confidence intervals, or the random seed used to generate the perturbations; adding these would materially improve the statistical reliability of the efficiency comparison.
- [§IV-D] The discussion states that 'the solution changes less with respect to the previous iteration L-1,' while Table I reports the distance between iteration L and iteration L+1; the indices should be reconciled.
Circularity Check
Approximate-optimality is measured only by the algorithm's own successive-iterate distance, so the central claim reduces to a self-consistency check; the theoretical convergence guarantee is imported from an unverified author self-citation.
-
self definitional
[Section IV-C, Evaluation metrics]
"Since there might be a continuum of equilibria, that is, multiple optimal solutions, we will evaluate the quality of the solutions by computing the L1 distance between the solution trajectory and what would be the solution at the next IBR iteration L+1."
The paper's central claim is that lexicographic IBR over time 'computes approximate-optimal solutions' and 'converges towards generalized Nash equilibria' (abstract, conclusion). The only quantitative evidence for this is Table I's L1 distance between the solution at iteration L and iteration L+1, which Section IV-C explicitly defines as the quality metric. That metric measures the algorithm's own fixed-point residual, not any distance to a true generalized Nash equilibrium or to the baseline MCP solution.
-
self citation load bearing
[Section III-B, paragraph beginning 'One way to mitigate...']
"Under certain assumption that are true for games of ordered preference IBR converges to a Nash equilibrium [25]."
The paper relies on this convergence result to justify that small successive L1 distances indicate approach to a generalized Nash equilibrium. Reference [25] is D. Fridovich-Keil, 'Smooth Game Theory' (2024), the author's own online course notes, not a peer-reviewed or machine-checked source. The paper neither states the 'certain assumption' nor verifies them for the proposed lexicographic IBR over time variant with shared constraints, warm-starting, and fixed iteration limits. Therefore the central theoretical premise that IBR converges to a Nash equilibrium in this setting is imported from an unverified, load-bearing self-citation, rather than established within the paper.
full rationale
The paper's efficiency claims involve time reductions compared to a baseline MCP solver in Table I, and these are not circular. However, the correctness claim that the method produces approximate-optimal solutions converging to generalized Nash equilibria is supported only by a self-referential metric: the L1 distance between successive IBR iterates is defined as the quality measure in Section IV-C, so 'approximate-optimal' is operationally defined as 'close to the algorithm's own next iterate.' This does not quantify distance to any true equilibrium, and no comparison is made to the baseline MCP solution or any KKT residual. The paper's own text acknowledges non-convergence for some problems and that the final average L1 distance does not reach zero. Additionally, the theoretical guarantee that IBR converges to a Nash equilibrium is attributed to the lead author's own unpublished course notes [25], with assumptions left unstated and unverified. These two issues jointly make the central claim reduce to a self-consistency check, meriting a score of 7: partial circularity where the prediction of approximate optimality is defined by the algorithm's own behavior.
Assumptions & free parameters
free parameters (4)
- Maximum IBR iterations L =
1, 2, 3, 5, 10, 20, 1000
- Convergence tolerance epsilon =
not stated
- Receding horizon T and turn length T_l =
not stated
- Warmstart padding action =
not stated (null action or previous action)
assumptions (4)
- domain assumption Standard IBR converges to a Nash equilibrium when assumptions on best-response continuity hold, as cited to [25].
- domain assumption The MCP relaxation of Lee et al. [4] correctly represents the lexicographic game and its generalized Nash equilibria.
- ad hoc to paper Shifted and padded previous trajectories are good predictors of other agents' future best responses.
- ad hoc to paper L1 distance between successive IBR iterations is a proxy for distance to a generalized Nash equilibrium.
Cite this review
Pith. "Pith review of Approximate solutions to games of ordered preference." pith.science (2026). https://pith.science/paper/A5TWWBTJ
@misc{pith2026250711021,
author = {Pith},
title = {Pith review of: Approximate solutions to games of ordered preference},
year = {2026},
howpublished = {\url{https://pith.science/paper/A5TWWBTJ}},
note = {Machine review of arXiv:2507.11021}
}
read the original abstract
Autonomous vehicles must balance ranked objectives, such as minimizing travel time, ensuring safety, and coordinating with traffic. Games of ordered preference effectively model these interactions but become computationally intractable as the time horizon, number of players, or number of preference levels increase. While receding horizon frameworks mitigate long-horizon intractability by solving sequential shorter games, often warm-started, they do not resolve the complexity growth inherent in existing methods for solving games of ordered preference. This paper introduces a solution strategy that avoids excessive complexity growth by approximating solutions using lexicographic iterated best response (IBR) in receding horizon, termed "lexicographic IBR over time." Lexicographic IBR over time uses past information to accelerate convergence. We demonstrate through simulated traffic scenarios that lexicographic IBR over time efficiently computes approximate-optimal solutions for receding horizon games of ordered preference, converging towards generalized Nash equilibria.
Figures
Reference graph
Works this paper leans on
-
[25]
Fridovich-Keil,Smooth Game Theory
D. Fridovich-Keil,Smooth Game Theory. 2024. [Online]. Available: https://clearoboticslab.github.io/documents/sm ooth_game_theory.pdf
work page 2024
-
[1]
Mistakes about preferences in the social sciences,
D. M. Hausman, “Mistakes about preferences in the social sciences,” Philosophy of the Social Sciences, 2011.DOI:10.1177/0048393 110387885
-
[2]
A. Zanardi, G. Zardini, S. Srinivasan, S. Bolognani, A. Censi, F. Dörfler, and E. Frazzoli, “Posetal games: Efficiency, existence, and refinement of equilibria in games with prioritized metrics,”IEEE Robotics and Automation Letters, 2022.DOI:10.1109/LRA.202 1.3135030
-
[3]
J. M. M. Filho, E. Lucet, and D. Filliat, “Real-time distributed receding horizon motion planning and control for mobile multi-robot dynamic systems,” inICRA, 2017.DOI: 10.1109/ICRA.2017.7 989081
-
[4]
You can’t always get what you want: Games of ordered preference,
D. H. Lee, L. Peters, and D. Fridovich-Keil, “You can’t always get what you want: Games of ordered preference,”IEEE Robotics and Automation Letters, 2025.DOI:10.1109/LRA.2025.3575324
arXiv 2025
-
[5]
Receding horizon games with coupling constraints for demand-side manage- ment,
S. Hall, G. Belgioioso, D. Liao-McPherson, and F. Dörfler, “Receding horizon games with coupling constraints for demand-side manage- ment,” inCDC, 2022.DOI: 10.1109/CDC51059.2022.99924 97
arXiv 2022
-
[6]
S. Hall, D. Liao-McPherson, G. Belgioioso, and F. Dörfler,Stability certificates for receding horizon games, arXiv:2404.12165 [eess.SY], 2024.DOI:10.48550/ARXIV.2404.12165
-
[7]
Liability, ethics, and culture-aware behavior specification using rulebooks,
A. Censi, K. Slutsky, T. Wongpiromsarn, D. S. Yershov, S. Pendleton, J. G. M. Fu, and E. Frazzoli, “Liability, ethics, and culture-aware behavior specification using rulebooks,” inICRA, 2019.DOI: 10.11 09/ICRA.2019.8794364
arXiv 2019
Show all 27 references
-
[8]
Minimum- violation planning for autonomous systems: Theoretical and practical considerations,
T. Wongpiromsarn, K. Slutsky, E. Frazzoli, and U. Topcu, “Minimum- violation planning for autonomous systems: Theoretical and practical considerations,” inACC, 2021.DOI: 10.23919/ACC50511.202 1.9483174
2021 doi
- [9]
-
[10]
Solving mathematical programs with complementarity constraints arising in nonsmooth optimal control,
A. Nurkanović, A. Pozharskiy, and M. Diehl, “Solving mathematical programs with complementarity constraints arising in nonsmooth optimal control,”Vietnam Journal of Mathematics, 2024.DOI: 10.1 007/s10013-024-00704-z
2024
-
[11]
Game theoretic application to intersection management: A literature review,
Z. Qin, A. Ji, Z. Sun, G. Wu, P. Hao, and X. Liao, “Game theoretic application to intersection management: A literature review,”IEEE Transactions on Intelligent Vehicles, 2024.DOI:10.1109/TIV.20 24.3379986
2024 doi
-
[12]
Multi- hypothesis interactions in game-theoretic motion planning,
F. Laine, D. Fridovich-Keil, C. Chiu, and C. J. Tomlin, “Multi- hypothesis interactions in game-theoretic motion planning,” inICRA, 2021.DOI:10.1109/ICRA48506.2021.9561695
2021
-
[14]
Maximum-entropy multi-agent dynamic games: Forward and inverse solutions,
N. Mehr, M. Wang, M. Bhatt, and M. Schwager, “Maximum-entropy multi-agent dynamic games: Forward and inverse solutions,”IEEE Transactions on Robotics and Automation, 2023.DOI: 10.1109 /TRO.2022.3232300
2023
-
[17]
Learning mixed strategies in trajectory games,
L. Peters, D. Fridovich-Keil, L. Ferranti, C. Stachniss, J. Alonso- Mora, and F. Laine, “Learning mixed strategies in trajectory games,” inRSS, 2022.DOI:10.15607/RSS.2022.XVIII.051
2022 doi
-
[18]
Learning to play trajectory games against opponents with unknown objectives,
X. Liu, L. Peters, and J. Alonso-Mora, “Learning to play trajectory games against opponents with unknown objectives,”IEEE Robotics and Automation Letters, 2023.DOI: 10.1109/LRA.2023.32808 09
2023
-
[19]
Game theory-based simultaneous prediction and planning for autonomous vehicle navigation in crowded environments,
K. Li, Y. Chen, M. Shan, J. Li, S. Worrall, and E. M. Nebot, “Game theory-based simultaneous prediction and planning for autonomous vehicle navigation in crowded environments,” inITSC, 2022.DOI: 10.1109/ITSC57777.2023.10422696
2022
-
[20]
An efficient game-theoretic planner for automated lane merging with multi-modal behavior understanding,
L. Zhang, S. Han, and S. Grammatico, “An efficient game-theoretic planner for automated lane merging with multi-modal behavior understanding,” inITSC, 2022.DOI: 10.1109/ITSC57777.2 023.10422316
2022 doi
-
[21]
Receding horizon planning with rule hierarchies for autonomous vehicles,
S. Veer, K. Leung, R. K. Cosner, Y. Chen, P. Karkus, and M. Pavone, “Receding horizon planning with rule hierarchies for autonomous vehicles,” inICRA, 2023.DOI: 10.1109/ICRA48891.2023.10 160622
2023
-
[22]
Hierarchical game-theoretic planning for autonomous vehicles,
J. F. Fisac, E. Bronstein, E. Stefansson, D. Sadigh, S. S. Sastry, and A. D. Dragan, “Hierarchical game-theoretic planning for autonomous vehicles,” inICRA, 2019.DOI: 10.1109/ICRA.2019.8794007
2019
-
[23]
Receding horizon control,
F. J. Christophersen, “Receding horizon control,” inOptimal Control of Constrained Piecewise Affine Systems. 2007.DOI:10.1007/97 8-3-540-72701-9_3
2007 doi
-
[24]
Peters,ParametricMCPs.jl2025,URL: https://github .com/JuliaGameTheoreticPlanning/ParametricMCPs .jl
[SW] L. Peters,ParametricMCPs.jl2025,URL: https://github .com/JuliaGameTheoreticPlanning/ParametricMCPs .jl
-
[26]
M. J. Kochenderfer and T. A. Wheeler,Algorithms for Optimization. The MIT Press, 2019
2019
-
[27]
Julia: A fresh approach to numerical computing,
J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,”SIAM Review, 2017.DOI: 10.1137/141000671
2017 doi
-
[28]
Peters and A.-C
[SW] L. Peters and A.-C. Papuc,TrajectoryGamesBase.jl2025,URL: https : / / github . com / JuliaGameTheoreticPlanning /TrajectoryGamesBase.jl
-
[29]
The path solver: A nommonotone stabi- lization scheme for mixed complementarity problems,
S. Dirkse and M. Ferris, “The path solver: A nommonotone stabi- lization scheme for mixed complementarity problems,”Optimization Methods and Software, 1995.DOI: 10.1080/10556789508805 606
1995 doi
-
[30]
de las Heras Molins, E
[SW] P. de las Heras Molins, E. Roy-Almonacid, D. H. Lee, L. Peters, D. Fridovich-Keil, and G. Bakirtzis,LEXIBROverTime.jl2025,DOI: 10.5281/zenodo.15825235
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.