{"id":"8bcc7c9c-daa2-4f07-b963-ad3b8b8f382b","arxiv_id":"2505.11791","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Local linear tolls designed under small resource-cost misspecification do not introduce new Nash equilibria, and a linear program bounds the worst-case price of anarchy under larger misspecification.","lead":"This paper studies what happens when traffic tolls are designed using an estimated, not exact, model of road congestion. It proves that small estimation errors do not make the worst-case system efficiency worse, and gives a linear programming bound on how much larger errors can degrade it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 2's equality is the weak spot: aggregate Nash inequality (11b) and the abridged tightness construction do not establish an actual game attaining 1/p*(δ), so (8) may be only an upper bound without a complete proof.","rationale":"I read the paper in good faith. Prop. 1 and its corollaries are elementary and sound: a non-Nash allocation has a strict improvement, so the deviation gap is positive at γ and continuous in the toll parameters, giving a uniform radius over the finite set of non-equilibria. The experiments for the local sensitivity claim are consistent with the theory and would have detected obvious contradictions. The only load-bearing concern is the exact worst-case characterization in Prop. 2. The proof is abridged and the equality rests on two unverified assertions: that the aggregate Nash constraint (11b) is lossless, and that a game with at most n agents can be constructed from any feasible LP solution whose proposed allocation is actually a pure Nash equilibrium with the claimed PoA. The paper itself flags these as omitted, saying the proof is abridged and referencing prior work. The transition from a feasible LP point to a concrete game is especially under-specified: action sets are described only as \"designed in such a way,\" with no verification of individual equilibrium constraints or of the worst-case PoA status. Because both the LP relaxation and the realization step are needed for equality, not just for an upper bound, the current text establishes at most sup PoA ≤ 1/p*(δ). This is exactly the reader's weakest_assumption, so I agree with the CONDITIONAL verdict. I do not claim Prop. 2 is false; I claim it is not yet proved. The concrete test above targets the construction directly and would either close the gap or expose a lossy step.","tokens_in":10828,"tokens_out":12045,"duration_ms":132741,"concrete_test":"Reconstruct the promised tightness construction for a minimal instance: n=2, m=1, affine basis b_1(x)=x, toll T(b_1)=0 (and separately the optimal local toll from [3]), for δ in {0, 0.1, 0.5}. Solve LP (9), take an optimal (θ*, θhat*), and explicitly define the claimed game following the last paragraph of Sec. IV: one resource per label with coefficient θ*/n, toll coefficient θhat*/n, and a specified binary action set for each agent. Then brute-force enumerate all pure Nash equilibria of the tolled game and compute its PoA. If the proposed aNE is not a pure Nash equilibrium, or its PoA is strictly less than 1/p*(δ), the equality in (8) fails; verifying this across δ would settle whether the proof gap is real.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The local-robustness result, Prop. 1 and its corollaries, is correct: a non-equilibrium allocation has a strict profitable deviation, so continuity of the affine deviation gap gives the claimed neighborhood, and the finite minimum over non-equilibria is positive. The central quantitative claim is the equality in Prop. 2, and its proof is explicitly abridged: \"Due to space constraints, we present an abridged proof with literature references for omitted portions.\" The critical step is the claim that replacing (10) by (11) is lossless. In particular, (11b) is only the sum over agents of their unilateral-deviation inequalities; a pure Nash equilibrium requires each individual summand to be nonpositive, not merely the sum. The cited prior work may contain a canonical construction where aggregate constraints imply individual equilibrium, but no such construction is supplied here for the misspecified-toll setting. The final paragraph of Sec. IV asserts that one constructs n resources per label and designs action sets \"in such a way\" that labels remain, then claims the feasible LP solution yields a Nash equilibrium with PoA 1/p*(δ); the action sets are never defined, and neither the Nash property nor the worst-case status of the proposed allocation is demonstrated. The LP also aggregates the per-resource misspecification bound into per-label constraints (16), another relaxation. If any of these steps is strict, (8) provides only the upper bound sup PoA ≤ 1/p*(δ), and the claimed exact worst-case degradation is unproved. The experiments in Sec. V solve (9) and sample random perturbations; they do not search over games and therefore cannot certify tightness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies atomic congestion games with local linear tolls computed from a possibly misspecified system model. The true game has resource costs parameterized by γ, while the toll designer uses parameters γ̃; the deployed mechanism is T(γ̃). The main theoretical results are: (i) Proposition 1, which states that for sufficiently small perturbations of γ the Nash equilibrium set of the tolled game does not expand, so the price of anarchy does not increase (Corollaries 2 and 3); and (ii) Proposition 2, which claims that the worst-case price of anarchy over a class of games with relative parameter error δ is exactly 1/p⋆(δ), where p⋆(δ) is the value of a linear program. The paper also reports Monte-Carlo simulations on a simplified Sioux Falls network and LP-based numerical evaluations for affine congestion games.","tokens_in":11154,"tokens_out":5494,"duration_ms":63113,"significance":"If Proposition 1 and Proposition 2 are correct, the paper makes a useful contribution: it gives an elementary continuity-based robustness guarantee for local linear tolls and provides a computationally tractable LP for the worst-case degradation of the price of anarchy under a structured misspecification model. The proof of Proposition 1 is clean and self-contained, and the local-robustness corollaries follow immediately from the finite-set argument. The LP framework builds on the authors' prior work [3,9], which is peer-reviewed independent support; the manuscript does not appear circular. However, the exactness claim in Proposition 2 is not established in the submitted text, and without it the central quantitative result reduces to an upper bound. Because this gap is explicitly acknowledged by the authors in Sec. IV and is likely fixable by supplying the omitted construction, the appropriate outcome is major revision rather than rejection.","major_comments":[{"comment":"The equality sup_{G(γ)} PoA(G(γ),T(γ̃)) = 1/p⋆(δ) is not proven by the abridged proof. The text states that steps 1-4 are lossless and cites [3,9], but for the misspecified-toll setting no full demonstration is provided. In particular, the aggregate equilibrium inequality (11b) only requires the sum over agents of unilateral-deviation costs to be nonpositive; a pure Nash equilibrium requires each individual summand to be nonpositive. A feasible solution of (11) or (9) need not correspond to any actual game, because the per-resource constraint |γ̃_e,j − γ_e,j| ≤ δγ_e,j is replaced in (16) by the per-label aggregate constraint (1−δ)θ ≤ θ̃ ≤ (1+δ)θ, which is necessary but not sufficient for the existence of a per-resource decomposition. The final paragraph of Sec. IV sketches a construction with 'n resources per label' but never defines the agents' action sets, never shows that the labels remain as claimed, and never proves that the proposed allocation is a Nash equilibrium or that its PoA equals 1/p⋆(δ). As written, (8) is therefore only an upper bound. The authors should supply a complete proof of the attaining-game construction, or explicitly restate the result as an upper bound.","section":"Sec. IV, Proposition 2, Eq. (8)"},{"comment":"The proofs of Corollaries 1 and 3 define δ := max{ε/γ_e,j : γ_e,j > 0}. This is the wrong extremum: with the maximum, for every positive γ_e,j we have δγ_e,j ≥ ε, so the condition |γ̃_e,j − γ_e,j| ≤ δγ_e,j does not imply γ̃ lies in the ε-ball used in Proposition 1. The correct definition is δ := min{ε/γ_e,j : γ_e,j > 0}, with a separate convention for zero coefficients. The statements of the corollaries are true with the corrected choice, but the proofs as written are invalid. Since these corollaries are the multiplicative-perturbation versions of the paper's central local-robustness claim, this needs to be fixed.","section":"Sec. III, Corollary 1 and Corollary 3"},{"comment":"The paper asserts that aggregating the Nash-equilibrium inequalities and aggregating the per-resource misspecification bounds into per-label constraints do not change the optimal value. This is a load-bearing point for Proposition 2. Even if the individual-deviation issue were resolved, the per-label constraint (1−δ)θ ≤ θ̃ ≤ (1+δ)θ is strictly weaker than the original per-resource constraints: given aggregate θ and θ̃ satisfying the former, there may be no assignment of γ_e,j and γ̃_e,j to the individual resources in the label that satisfies the latter. A proof of the converse is needed. The citations to [3,9] cover the noiseless case, but the misspecified case introduces the additional variable θ̃ and the coupling constraint (16), so the losslessness does not carry over automatically.","section":"Sec. IV, from Eq. (10) to Eq. (11) and Eq. (16)"}],"minor_comments":[{"comment":"The quantifier in the statement 'For any δ ≥ 0 and eγ satisfying ... sup_{G(γ)} PoA(G(γ),T(eγ)) = 1/p⋆(δ)' is ambiguous: the left-hand side depends on the arbitrary fixed eγ while the right-hand side depends only on δ. The proof's Eq. (10) indicates the intended meaning is a supremum over both G(γ) and eγ subject to the misspecification bound; the proposition should be reworded accordingly.","section":"Sec. IV, Proposition 2 statement"},{"comment":"There is a notation inconsistency: the text uses 'NSF' in the sentence 'the maximum and average PoA realized in NSF generally increase with δ' while the game is named GSF. Also, the sentence 'E = [10], I = [7]' appears to use I for the node set, while I is later used for the label set; a different symbol for the node set would avoid confusion.","section":"Sec. V-A"},{"comment":"The proposed construction states that 'for each resource labeled (x,y,z,j), we construct n resources with cost function ℓ(·)=θ⋆(x,y,z,j)b_j(·)/n'. If θ⋆ already aggregates coefficients over all resources of that label, it is unclear why each of the n constructed resources has coefficient θ⋆/n rather than a decomposition into n individual coefficients; this affects the label verification. The construction should specify the actual resources and action sets explicitly.","section":"Sec. IV, construction paragraph"},{"comment":"The proof writes δ := max{ ... } without addressing coefficients γ_e,j = 0; since the expression divides by γ_e,j, a separate treatment is required. With the corrected minimum choice, zero coefficients force γ̃_e,j = 0 through the constraint (1−δ)γ_e,j ≤ γ̃_e,j ≤ (1+δ)γ_e,j, which is consistent but should be stated.","section":"Sec. III, Corollary 1 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper's main gap is the proof of Proposition 2, which is explicitly abridged. I would ask the authors to provide a complete proof, even if in an appendix, because the equality in (8) is the quantitative centerpiece of the paper. The max/min error in Corollaries 1 and 3 is easy to fix and is not a sign of a deeper flaw. The local-robustness result is sound and well presented, so substantial revision is appropriate rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this paper proves one small, clean robustness fact and then pushes a bigger claim that is not yet fully supported. If you need the local-robustness result (Prop. 1), it is solid. If you need the exact worst-case degradation (Prop. 2), wait for a complete proof.\n\nProp. 1 says that for a fixed game, tolls designed from slightly noisy cost parameters cannot introduce new pure Nash equilibria, so the price of anarchy cannot strictly increase. The proof is a finite-minimum continuity argument and it is correct. The corollaries for multiplicative error and for PoA follow. That is a genuinely useful result for toll designers: small estimation error is not a reason to panic.\n\nThe bigger contribution is Prop. 2, an LP whose optimum is claimed to equal the worst-case PoA over all games in the class when tolls are designed with relative error delta. The LP extends the authors' earlier PoA-LP framework, and the setup is plausible. But the proof is explicitly abridged. The critical steps—that aggregating the Nash inequalities into one sum is lossless, that the per-label constraint (16) captures the per-resource misspecification, and that a game with at most n agents attains the LP value—are all asserted rather than demonstrated. In particular, aggregate deviation inequality (11b) is weaker than requiring every agent's deviation to be nonpositive, and the construction at the end of Sec. IV never defines the action sets. As written, equation (8) gives at best an upper bound. This is the load-bearing gap.\n\nThe experiments are honest but light: they solve the LP and sample random perturbations, which illustrates the bound but cannot certify tightness. The citation pattern is fine—the earlier LP machinery is peer-reviewed, and the paper is explicit about borrowing it.\n\nBottom line: Prop. 1 deserves publication. Prop. 2 is a valuable target, and I suspect it is true, but the current manuscript does not prove it. I would send this to a serious referee with instructions to require a complete proof or a verified tightness construction for Prop. 2. It is close, but not there.","headline":"Prop. 1 is a clean, correct local-robustness result; Prop. 2 is a promising LP bound whose equality claim currently rests on an abridged proof that needs to be completed before it can be taken as exact.","tokens_in":11698,"tokens_out":2192,"would_cite":false,"duration_ms":23031,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Small model errors add no new equilibria to tolled congestion games.","keywords":["congestion games","price of anarchy","toll design","model misspecification","local linear tolls","atomic congestion games","linear programming","Nash equilibrium robustness"],"falsifier":"Enumerate all atomic congestion games with three agents and two affine basis functions, compute the true worst-case price of anarchy under $\\delta$-perturbed tolls by exhaustive search, and compare it with $1/p^*(\\delta)$ from the linear program; any gap would falsify the equality in Proposition 2. A single instance where an arbitrarily small perturbation creates a new pure Nash equilibrium would similarly falsify Proposition 1.","tokens_in":10612,"feed_emoji":"🚗","tokens_out":8293,"duration_ms":70201,"temperature":0.7,"pith_summary":"This paper studies what happens to tolls in atomic congestion games when the designer's model of resource costs (for example, road latencies) is slightly wrong. It proves that for small enough errors in the cost parameters used to set tolls, the tolled game admits no new pure Nash equilibria compared with correct tolls, so the price of anarchy cannot worsen. It then provides a linear program whose value, for any fixed relative error level, gives the worst-case price of anarchy over all atomic congestion games with at most n agents and resource costs spanned by a given set of basis functions. This yields a computable worst-case degradation guarantee for local linear toll mechanisms under system misspecification.","feed_headline":"Small model errors add no new equilibria to tolled congestion games","feed_subtitle":"A linear program gives the worst-case efficiency loss from larger latency-parameter misspecification","key_machinery":"The load-bearing device is the resource-labeling aggregation that converts the worst-case PoA question into a linear program. Each resource $e$ is labeled $(x_e, y_e, z_e, j)$, where $x_e$ is the number of agents using $e$ in both the equilibrium and the optimal allocation, $y_e$ in the equilibrium only, $z_e$ in the optimal allocation only, and $j$ indexes the basis function; the LP variables $\\theta$ and $\\hat{\\theta}$ sum the true and misspecified cost coefficients over all resources sharing a label. Proposition 1 is carried by an even simpler mechanism: the function $h_a(\\hat{\\gamma})$ measuring an agent's benefit from deviating to an alternative action is continuous in $\\hat{\\gamma}$, and the joint-action space is finite, so a strictly profitable deviation remains profitable in a whole neighborhood of $\\gamma$. Proposition 2's LP extends the standard PoA-computation method for atomic congestion games, encoding the misspecification through the box constraint $(1-\\delta)\\theta \\le \\hat{\\theta} \\le (1+\\delta)\\theta$ and recovering the noise-free case at $\\delta=0$.","core_discovery":"The paper's central claim is that misspecified local linear tolls are robust at small error scales: for any true cost parameters $\\gamma$, there is an $\\epsilon$ such that any toll parameters $\\tilde{\\gamma}$ within $\\epsilon$ of $\\gamma$ satisfy $ANE(G(\\gamma), T(\\tilde{\\gamma})) \\subseteq ANE(G(\\gamma), T(\\gamma))$, meaning no new pure Nash equilibria appear. Because the price of anarchy is the worst system cost over the equilibrium set, this inclusion implies $PoA(G(\\gamma), T(\\tilde{\\gamma})) \\le PoA(G(\\gamma), T(\\gamma))$ for all such $\\tilde{\\gamma}$; the same holds for multiplicative perturbations. For larger errors, the paper claims that over the class of atomic congestion games with at most $n$ agents and costs spanned by a fixed basis, the worst-case PoA under relative parameter error $\\delta$ is exactly $1/p^*(\\delta)$, where $p^*(\\delta)$ is the optimal value of an explicit linear program. The LP aggregates resources by how many agents use them in the worst-case equilibrium and in the optimal allocation, and couples true coefficients $\\theta$ with misspecified coefficients $\\hat{\\theta}$ through the box constraint $(1-\\delta)\\theta \\le \\hat{\\theta} \\le (1+\\delta)\\theta$.","pith_inferences":["If the equality in Proposition 2 holds, a toll designer could use $1/p^*(\\delta)$ as a certificate: given an estimation-error budget $\\delta$, the mechanism is guaranteed, over the entire model class, not to degrade efficiency beyond this ratio.","The same inclusion-of-equilibria argument would apply to any finite game with continuous payoff parameters, so the local robustness may extend to subsidies, nonlinear taxes, and other smoothly parameterized incentives beyond local linear tolls.","The simulations' relation between toll magnitude and robustness suggests that deliberately regularizing or shrinking toll values could produce designs that are less sensitive to misspecification; the paper does not make this design claim.","One could probe the LP's tightness computationally by solving (9) for small $n$ and comparing with exhaustive enumeration of all games and all $\\delta$-perturbed tolls, which would also reveal whether the abridged construction really attains the bound."],"forward_implications":["For a fixed game, small additive or multiplicative errors in the cost parameters used to set local linear tolls cannot introduce new pure Nash equilibria, so the price of anarchy does not increase.","Setting $\\delta=0$ in the linear program recovers the known worst-case price-of-anarchy results for local linear tolls under perfect information.","For any specified error level $\\delta$ and basis $B$, the linear program produces a number $1/p^*(\\delta)$ that upper-bounds the price of anarchy over every atomic congestion game with at most $n$ agents whose costs lie in the basis span.","Numerical experiments on the Sioux Falls network show the fraction of toll realizations that create new equilibria rises with the noise level, matching the predicted existence of a robustness threshold.","In the affine-cost simulations, the nominally optimal congestion-dependent toll is less robust than the nominally optimal constant toll, which matters for mechanism selection."],"supporting_citations":[{"why":"Supplies the local linear toll framework, the noiseless price-of-anarchy analysis, and the game construction that Proposition 2 extends.","marker":"[3]"},{"why":"Provides the LP-based exact PoA characterization and the relaxation steps used to formulate the linear program in Proposition 2.","marker":"[9]"},{"why":"Prior study of toll misspecification of agent price sensitivities, the comparison point for this paper's resource-cost misspecification.","marker":"[6]"},{"why":"Rosenthal's existence theorem guarantees pure Nash equilibria exist in these games, so the equilibrium sets and PoA are well-defined.","marker":"[16]"},{"why":"Supplies the Sioux Falls traffic network data used for the experimental validation in Section V.","marker":"[15]"},{"why":"Defines the marginal-cost toll mechanism used as a benchmark in the LP simulations.","marker":"[18]"}],"fun_headline_variants":["Slight toll errors don't add new equilibria in congestion games","Small model misspecification leaves tolled game equilibria unchanged","Worst-case efficiency loss from mistaken tolls: exact LP bound","Toll robustness to system error: local equilibrium stability","Misspecified tolls: for small errors, no new Nash equilibria"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper asserts, with an abridged proof, that its linear-programming relaxation is lossless and that a game with at most the allowed number of agents attains the worst-case bound; if that assertion fails, the formula gives only an upper bound on the price of anarchy rather than the exact worst case.","fun_headline_variants_meta":{"raw":{"variants":["Slight toll errors don't add new equilibria in congestion games","Small model misspecification leaves tolled game equilibria unchanged","Worst-case efficiency loss from mistaken tolls: exact LP bound","Toll robustness to system error: local equilibrium stability","Misspecified tolls: for small errors, no new Nash equilibria"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00077,"raw_usage":{"total_tokens":3436,"prompt_tokens":995,"completion_tokens":2441,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":2353}},"tokens_in":611,"tokens_out":2441,"duration_ms":19807,"temperature":1.0,"reasoning_tokens":2353,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:48:21.823069+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all atomic congestion games with three agents and two affine basis functions, compute the true worst-case price of anarchy under $\\delta$-perturbed tolls by exhaustive search, and compare it with $1/p^*(\\delta)$ from the linear program; any gap would falsify the equality in Proposition 2. A single instance where an arbitrarily small perturbation creates a new pure Nash equilibrium would similarly falsify Proposition 1.","supporting_citations":[{"cited_title":"Optimal Taxes in Atomic Congestion Games","cited_arxiv_id":null,"evidence_quote":"Supplies the local linear toll framework, the noiseless price-of-anarchy analysis, and the game construction that Proposition 2 extends."},{"cited_title":"Utility Design for Distributed Resource Allocation—Part I: Characterizing and Optimizing the Exact Price of Anarchy","cited_arxiv_id":null,"evidence_quote":"Provides the LP-based exact PoA characterization and the relaxation steps used to formulate the linear program in Proposition 2."},{"cited_title":"The Effectiveness of Subsidies and Taxes in Atomic Congestion Games","cited_arxiv_id":null,"evidence_quote":"Prior study of toll misspecification of agent price sensitivities, the comparison point for this paper's resource-cost misspecification."},{"cited_title":"A Class of Games Possessing Pure-strategy Nash Equilibria","cited_arxiv_id":null,"evidence_quote":"Rosenthal's existence theorem guarantees pure Nash equilibria exist in these games, so the equilibrium sets and PoA are well-defined."},{"cited_title":"Transportation Networks for Research","cited_arxiv_id":null,"evidence_quote":"Supplies the Sioux Falls traffic network data used for the experimental validation in Section V."},{"cited_title":"When are marginal congestion tolls optimal?","cited_arxiv_id":null,"evidence_quote":"Defines the marginal-cost toll mechanism used as a benchmark in the LP simulations."}],"review_version":1}