{"id":"ab5d266c-a25a-416e-bbc3-4cb1143ca356","arxiv_id":"2507.11021","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A warm-started iterated best response algorithm computes approximate equilibria for lexicographic preference games about 100 to 1000 times faster than the baseline MCP solver in small traffic simulations, but optimality is only measured as agreement between successive iterations.","lead":"This paper proposes a faster way to solve multi-agent traffic games where each vehicle ranks its goals by priority, for example safety before speed before reaching the destination. The method reuses each vehicle's previous plan as a warm start in a loop of best responses, and the authors report orders-of-magnitude speedups in small simulated road scenarios.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Approximate-optimality is measured only by L1 distance between successive IBR iterates, which does not quantify distance to a true GNE; the paper's own data show non-convergence for some runs, so the central claim needs an independent equilibrium-quality check.","rationale":"The reader identified the same load-bearing concern: the L1 distance between successive IBR iterations is not a valid proxy for distance to a true generalized Nash equilibrium. My reading of the paper confirms this. The abstract claims convergence toward GNE and approximate-optimal solutions, but the only numerical evidence in Table I is the successive-iteration L1 distance. No comparison to the baseline MCP solution appears anywhere in Table I or the surrounding text; the baseline is used only for timing. The paper's own Section IV-C admits that IBR does not converge for some problems, and the L=1000 row shows distances that are not uniformly smaller than L=20, which further weakens the convergence narrative. A separate concern is that experiment-defining hyperparameters (T, T_l, epsilon, padding choice) are not fully specified, and Table I has no error bars, but those issues are secondary; the primary unsupported step is the interpretation of self-consistency as optimality. The efficiency result is plausible and independently useful: decomposing the coupled MCP into single-player lexicographic problems does reduce dimensionality, and the reported speedups are large. The paper deserves conditional publication, requiring either a convergence theorem or an independent equilibrium-quality evaluation. Since the reader already recommended CONDITIONAL, my verdict is unchanged. I would strengthen the recommendation by making the concrete equilibrium-distance comparison an explicit condition for the approximate-optimality claim to stand.","tokens_in":12175,"tokens_out":2523,"duration_ms":33436,"concrete_test":"For each of the 20 Monte Carlo scenarios in Section IV-C, compute the IBR solution at L=20 and L=1000, and also solve the baseline coupled MCP formulation from Section II-C for the same scenario. Then evaluate two quantities: (1) the L1 distance between the IBR trajectory and the baseline MCP trajectory, and (2) the residual of the coupled KKT conditions (or the shared-constraint complementarity residual) evaluated at the IBR trajectory. If both quantities are small compared to the baseline solution's own KKT residual, the approximate-optimality and convergence claims are supported; if the IBR trajectory has a large KKT residual while successive L1 gaps are small, the current quality metric is misleading and the claim should be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that lexicographic IBR over time computes approximate-optimal solutions and converges toward generalized Nash equilibria. The only quantitative evidence for this claim is Table I, which reports the L1 distance between the solution at iteration L and the solution at iteration L+1, as stated in Section IV-C. This is a self-consistency measure, not a distance to a generalized Nash equilibrium. A sequence can have small successive differences while remaining far from any fixed point, e.g., a slowly converging sequence whose successive gaps shrink. Conversely, a trajectory that is already at a different but equally valid equilibrium can have a larger gap to the next IBR iterate. The paper never compares the IBR output to the baseline MCP solution, nor does it report any KKT residual or other equilibrium certificate for the coupled game. This matters because the abstract claims convergence toward GNE, yet Section IV-C explicitly states that 'the final average L1 distance does not reach zero' and that 'IBR does not converge to a stable equilibrium for some problems.' Table I also shows non-monotonic behavior: for K=3, the L1 distance at L=20 is 8.51e-5, but at L=1000 it is 4.14e-5, and for K=2, it increases from 1.28e-6 at L=20 to 2.45e-6 at L=1000. Thus the empirical metric does not establish convergence, and the approximate-optimality claim is unsupported as stated. The computational speedup side of the claim is credible, but the correctness side requires an independent check.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12370,"tokens_out":4148,"duration_ms":56195,"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":[{"comment":"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.","section":"§IV-C, Table I"},{"comment":"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.","section":"§IV-C, Baseline"},{"comment":"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.","section":"§III-B, reference [25]"},{"comment":"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.","section":"Algorithm 2, §IV-C"}],"minor_comments":[{"comment":"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.","section":"Eq. (3)"},{"comment":"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.'","section":"§II-C"},{"comment":"There is a typo: 'For each each preference level k' should read 'For each preference level k.'","section":"§III-B"},{"comment":"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.","section":"Table I"},{"comment":"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.","section":"§IV-D"}],"recommendation":"major_revision","confidential_remarks":"The main concern is not the algorithmic idea but the absence of an externally grounded equilibrium-quality metric; this is fixable because the baseline solver is already in place and the 20-run Monte Carlo design makes a direct trajectory-distance comparison inexpensive. I would encourage the editor to require that comparison or an equivalent equilibrium certificate before further consideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe thing to know: this paper applies iterated best response with shift-and-pad warmstarting from the previous receding-horizon stage to games of ordered preference. That is a legitimate and practical engineering idea, and the reported speedups (roughly 100x or more over the MCP baseline) are plausible. The second thing: the paper's central claim—that these are approximate-optimal solutions converging toward GNE—is not supported by the evidence as presented. The only quality metric is the L1 distance between the solution at iteration L and the solution at iteration L+1, which measures the algorithm's self-consistency, not its distance to any true equilibrium. The paper never compares against the baseline MCP solution, and it admits some runs do not converge. So the computational half is credible; the correctness half needs work.\n\nWhat's genuinely new is the combination of lexicographic IBR with temporal warmstarting. The shift-and-pad prediction scheme is simple and reasonably motivated, and the decomposition into single-player lexicographic problems avoids the dimensionality blowup of the flattened MCP. The code is packaged with a Zenodo DOI, and the qualitative experiments show that different preference relations yield distinct behaviors, which is a nice sanity check. I give credit for that.\n\nSoft spots, in proportion. The biggest is the evaluation of optimality. Section IV-C explicitly says they use the L1 distance to the next IBR iterate because there may be a continuum of equilibria. But that doesn't justify it: a slowly converging sequence has small successive gaps while still far from any fixed point. They could have compared to the MCP baseline for these small instances, or reported a KKT residual for the coupled game. They didn't. Table I also shows non-monotonic behavior: for K=2 the L1 distance goes from 1.28e-6 at L=20 up to 2.45e-6 at L=1000. So the numbers themselves undercut the convergence story. The abstract's \"converging towards generalized Nash equilibria\" is stronger than what Section IV-C admits. That mismatch should be fixed.\n\nMinor: Table I has no error bars; several hyperparameters (T, T_l, epsilon, padding choice) are not fully specified; no commit hash for the code. These are easy fixes.\n\nBottom line: this is a useful engineering contribution for the trajectory-game subfield, and the speedup result is worth taking seriously. But it is not ready as a full convergence claim. It deserves a serious referee who can ask for the missing equilibrium check and a qualified abstract. I'd engage with it.\n\nRecommendation: send to peer review, conditional on revision. If they add a real comparison to the MCP baseline or an equilibrium certificate, and tone down the convergence claim, this could be a solid paper.","headline":"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.","tokens_in":13078,"tokens_out":1800,"would_cite":true,"duration_ms":19670,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["games of ordered preference","lexicographic optimization","iterated best response","generalized Nash equilibrium","receding horizon","trajectory games","autonomous driving","approximate solutions"],"falsifier":"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.","tokens_in":11818,"feed_emoji":"🚗","tokens_out":10932,"duration_ms":123290,"temperature":0.7,"pith_summary":"Autonomous vehicles often have to respect strictly ranked goals—safety before lane-keeping before travel time—and games of ordered preference model that ranking, but the resulting coupled optimization grows quickly with horizon, player count, and preference levels. This paper claims that a receding-horizon version of iterated best response, which it calls 'lexicographic IBR over time,' can compute approximate-optimal solutions by letting each agent optimize its own ranked objectives against fixed guesses of the others, and by warm-starting those guesses with the shifted and padded trajectories from the previous decision stage. In simulated traffic scenarios the method solves the tested games in under a second, while the baseline coupled formulation takes tens of seconds to more than forty minutes, and the repeated solutions stabilize after a few iterations. The paper presents this as evidence that games of ordered preference can become practical for real-time multi-agent planning, with approximate optimality measured by the distance between consecutive IBR iterations rather than by an independent equilibrium certificate.","feed_headline":"Reusing past plans cuts traffic-game solve time 100x","feed_subtitle":"Warm-started best responses solve ranked-preference traffic games in under a second in simulation.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the baseline formulation of games of ordered preference and the relaxation scheme that the experiments compare against.","marker":"[4]"},{"why":"provides the trajectory-game software used to instantiate and solve the receding-horizon games in the experiments.","marker":"[24]"},{"why":"provides the parametric mixed-complementarity wrapper used to solve the single-player subproblems.","marker":"[28]"},{"why":"supplies the iterated best-response convergence background behind the claim that IBR reaches Nash equilibria.","marker":"[25]"},{"why":"supplies the technique of adding inequality constraints to preserve optimality of higher-priority levels during lower-priority optimization.","marker":"[26]"}],"fun_headline_variants":["Warm-started IBR solves ranked traffic games in under a second","Reusing plans cuts traffic-game solve time from 44s to 0.36s","Past-plan warm starts speed ordered-preference game solves","Lexicographic IBR over time approximates Nash equilibria"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Warm-started IBR solves ranked traffic games in under a second","Reusing plans cuts traffic-game solve time from 44s to 0.36s","Past-plan warm starts speed ordered-preference game solves","Lexicographic IBR over time approximates Nash equilibria"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001097,"raw_usage":{"total_tokens":4588,"prompt_tokens":966,"completion_tokens":3622,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":3545}},"tokens_in":582,"tokens_out":3622,"duration_ms":33052,"temperature":1.0,"reasoning_tokens":3545,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:18:46.249253+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Peters,ParametricMCPs.jl2025,URL: https://github .com/JuliaGameTheoreticPlanning/ParametricMCPs .jl","cited_arxiv_id":null,"evidence_quote":"provides the trajectory-game software used to instantiate and solve the receding-horizon games in the experiments."},{"cited_title":"Peters and A.-C","cited_arxiv_id":null,"evidence_quote":"provides the parametric mixed-complementarity wrapper used to solve the single-player subproblems."},{"cited_title":"Fridovich-Keil,Smooth Game Theory","cited_arxiv_id":null,"evidence_quote":"supplies the iterated best-response convergence background behind the claim that IBR reaches Nash equilibria."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the technique of adding inequality constraints to preserve optimality of higher-priority levels during lower-priority optimization."}],"review_version":1}