Pith. sign in

REVIEW 2 major objections 5 minor 14 references

A convex surplus turns sequential route choice into a well-posed Markov model that allows zero flow on bad links and solves large asymmetric traffic equilibria by a dual variational inequality.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-13 02:04 UTC pith:X6NT3ZFK

load-bearing objection Clean dual-VI Markovian equilibrium that actually allows zero flows and asymmetric costs, with global MPI and safeguarded acceleration proofs that hold up. the 2 major comments →

arxiv 2607.09568 v1 pith:X6NT3ZFK submitted 2026-07-10 math.OC econ.GNecon.THq-fin.EC

Perturbed utility Markovian traffic equilibrium: theory and computation

Rui Yao , Kenan Zhang This is my paper
classification math.OC econ.GNecon.THq-fin.EC MSC 90C3390B2090C40
keywords Markovian traffic equilibriumperturbed utilityvariational inequalitymodified policy iterationmeta-algorithmcorner solutionsundiscounted MDP
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Large-scale traffic assignment needs models that look realistic and still run on big networks. This paper replaces the usual random-utility assumption in Markovian route choice with a convex surplus function whose gradient is the optimal link-choice policy. The resulting perturbed-utility Markovian choice model admits both interior and corner probabilities, so unattractive links can carry exactly zero flow without any a-priori pruning of the network. Under a mild strict-negativity condition on stage surplus, every policy consistent with the Bellman equation reaches the destination, the optimal value and demand map are unique and monotone, and modified policy iteration converges globally even when the MDP is undiscounted. Equilibrium is then written as a monotone variational inequality on the dual cost space; existence and uniqueness follow from standard coercivity and strict monotonicity of supply alone, and the formulation covers non-separable and asymmetric cost interactions that fall outside classic potential-based Markovian models. A safeguarded meta-algorithm that mixes first-order VI steps with acceleration oracles is proved globally convergent and shown to scale linearly on benchmark and synthetic grids.

Core claim

Under two standing assumptions on the surplus and a coercive strictly monotone supply map, there exists a unique cost vector that solves the dual variational inequality of excess supply; the induced demand map is continuous and monotone, admits corner solutions, and can be computed by globally convergent modified policy iteration for any fixed evaluation depth.

What carries the argument

The surplus function Hs whose gradient is the optimal policy: it turns the Bellman optimality operator into a convex conjugate, forces every admissible policy to be proper once stage surplus is strictly negative, and yields a monotone demand map that is the gradient of a convex potential.

Load-bearing premise

Stage surplus must be strictly negative at every non-terminal node (or made so by a constant translation that leaves choices unchanged); without it, zero-cost cycles can produce infinite or non-unique values and the whole well-posedness argument collapses.

What would settle it

Construct a network and surplus that satisfy all other hypotheses but admit a zero-cost cycle; if value iteration or modified policy iteration still converges to a unique finite value and the dual VI still has a unique solution, the necessity claim fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Unattractive links receive exactly zero flow without any ex-ante choice-set restriction, giving endogenous consideration sets inside a Markovian model.
  • Asymmetric multi-class or spillover cost interactions can be treated inside a single dual VI without requiring a potential function.
  • Network loading remains globally convergent for the entire surplus family, including the sparse α-entmax maps that produce corner solutions.
  • The same safeguarded meta-algorithm works for any acceleration oracle once a continuous merit function is available, so future first-order or quasi-Newton schemes can be swapped in without re-proving global convergence.

Where Pith is reading between the lines

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

  • The same surplus construction should transfer to other undiscounted sequential discrete-choice settings (dynamic discrete choice, inventory routing) where corner solutions and non-contractive Bellman operators appear.
  • Because the demand map is the gradient of a convex potential, standard sensitivity and comparative-static arguments for monotone operators become available for Markovian traffic equilibria.
  • The strict-negativity translation trick suggests a practical pre-processing step that can be applied to any existing recursive-logit codebase before switching to a sparse surplus.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper develops a perturbed utility Markovian equilibrium (PUME) for large-scale traffic assignment. Route choice is modeled as an undiscounted absorbing MDP regularized by a convex surplus function (PUMCM), so that the Bellman optimality operator is the surplus of the state-action values and its gradient is the optimal policy. Under Standing Assumptions 1–2 the MDP is well posed, admits corner solutions, and induces a continuous monotone demand map. Equilibrium is cast as a dual variational inequality on the cost space that allows non-separable and asymmetric supply; existence and uniqueness follow from coercivity and strict monotonicity of supply. Network loading is solved by modified policy iteration with a global convergence guarantee and a local linear rate controlled by evaluation depth; the outer VI is solved by a safeguarded meta-algorithm that preserves global convergence for any acceleration oracle. Numerical experiments on Sioux Falls, Anaheim, Chicago Sketch and synthetic grids illustrate scalability and robustness across surplus families and potential/non-potential supply.

Significance. If the claims hold, the paper supplies a single link-based framework that simultaneously (i) admits zero-flow links without ex-ante choice-set restrictions, (ii) handles undiscounted network loading with a convergent algorithm, and (iii) accommodates asymmetric multi-class cost interactions via a dual VI. These three extensions address well-known limitations of existing Markovian traffic equilibrium models. The theoretical package is complete: well-posedness (Props. 1–3), existence/uniqueness (Thms. 1–2), MPI global and local rates (Thms. 4–5), and meta-algorithm convergence (Thm. 6) are proved with standard convex-analysis and monotone-operator tools, and the appendices contain the deferred arguments. The numerical section shows linear scaling with problem size and stable performance across demand and supply specifications. The contribution is therefore both theoretically coherent and practically relevant for large-scale assignment.

major comments (2)
  1. Standing Assumption 2(B2) (strictly negative stage surplus) is load-bearing for well-posedness (Prop. 1) and for the MPI guarantees (Thms. 4–5). Remark 1 correctly notes that a constant translation of stage rewards leaves the choice map invariant and can enforce the condition, and Figure 3 demonstrates divergence when it is violated. The manuscript should state more explicitly, preferably already in the introduction or in §3.3, that the translation is always available under the usual sign convention of traffic costs and that the subsequent theory is therefore not restricted by the assumption in applications. Without that clarification a reader may overestimate the restrictiveness of (B2).
  2. Theorem 3 establishes equivalence of the dual (cost-space) and primal (flow-space) formulations only for interior equilibria. Remark 3 acknowledges that boundary costs require a constrained inverse supply, but the paper never develops that object or the corresponding VI. Because PUMCM is expressly designed to produce corner solutions, boundary equilibria are not pathological; a short statement of the constrained-inverse VI (or an explicit deferral with a pointer to future work) would close the gap between the modeling ambition and the equivalence result.
minor comments (5)
  1. Table 1 claims that α-entmax for α∈(1,2) yields a C² surplus and a Lipschitz choice map; the argument in Appendix D.3 is correct but terse. A one-sentence reminder that the power 1/(α−1)>1 implies C¹ of the thresholded map would help readers who skip the appendix.
  2. In §5.2 the ST line-search condition (25) and the aGRAAL step-size rule (27) are stated without recalling the precise references for global convergence under mere monotonicity versus local Lipschitz continuity. Adding the theorem numbers from Solodov–Tseng and Malitsky would make the claims self-contained.
  3. Figure 5 uses ε for coupling strength while the surrounding text uses ι; the notation should be unified.
  4. The synthetic-grid generation formula (99) appears only in the appendix; a brief mention in §7.3 that demand follows a gravity model with free-flow shortest-path impedance would improve reproducibility of the main text.
  5. A few typographical slips remain (e.g., “aperturbed”, “the the”, inconsistent spacing around γ=1). A careful proof-reading pass is warranted.

Circularity Check

0 steps flagged

No significant circularity; all existence, uniqueness, and convergence claims are derived from standing assumptions plus standard VI/MDP arguments with fully written proofs.

full rationale

The paper's load-bearing results (PUMCM well-posedness under Standing Assumptions 1–2, unique fixed point of the Bellman operator, monotone demand map via the surplus potential, dual-VI existence/uniqueness under coercive strictly monotone supply, global MPI convergence for any fixed m, and safeguarded meta-algorithm convergence) are obtained by direct arguments from the stated definitions and assumptions. Proofs appear in the appendices and invoke only classical tools (Fenchel–Young, Brouwer, implicit-function theorem, spectral-radius criteria for proper policies, standard monotone-VI theory). Self-citations to the authors’ prior PURC/SUE papers serve as motivational building blocks whose independent statements are clear; none is used as an unexamined uniqueness theorem that forces the present claims. No parameters are fitted to data and then re-labeled as predictions, no ansatz is smuggled via citation, and no known empirical pattern is merely renamed. Algorithm hyperparameters affect only numerical speed. The derivation chain is therefore self-contained against the paper’s own equations and external mathematical facts.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 2 invented entities

The central existence, uniqueness and convergence claims rest on two standing assumptions about the surplus and the MDP, standard monotonicity/coercivity of supply, and the linear cost-utility map. Algorithm hyperparameters are free but do not enter the theorems. No new physical entities are postulated; PUMCM/PUME are modeling constructs whose properties are derived.

free parameters (4)
  • MPI evaluation depth m
    Integer ≥1 chosen by the user; controls local linear rate of network loading but is not fitted to data.
  • α in α-entmax surplus family
    Behavioral sparsity parameter (α=1 recovers logit; α=2 sparsemax); selected by modeler, not estimated in the paper.
  • meta-algorithm safeguard factors η, τ and restart period R
    User-chosen constants that only affect practical speed of the outer loop; theorems hold for any 0<η<τ<1 and R∈ℕ.
  • scale parameters μ_s (and nested scales in NRL)
    Dispersion parameters of the surplus; treated as given inputs, sampled or fixed in experiments.
axioms (5)
  • domain assumption Standing Assumption 1: surplus Hs is convex, C1, has simplex gradient, and is translation-equivariant.
    Core modeling hypothesis that turns the Bellman operator into a well-defined choice-probability generating function (§3.2).
  • domain assumption Standing Assumption 2: at least one proper admissible policy exists and stage surplus is strictly negative.
    Ensures every policy consistent with the Bellman equation reaches the destination almost surely (§3.3).
  • domain assumption Supply z is continuous, coercive and (strictly) monotone on the cost domain Ω.
    Standard traffic-assignment regularity that transfers to the excess-supply operator E (Assumption 3, Theorems 1–2).
  • domain assumption Linear (or more generally gradient-of-convex) cost-to-utility map uk(c)=−Bk c.
    Sign convention and incidence structure that make aggregate demand the negative gradient of a convex potential (Assumption 2, Prop. 4).
  • standard math Standard results on monotone variational inequalities, Fenchel–Young duality, and spectral radius of substochastic matrices.
    Used throughout the existence, uniqueness and convergence proofs; cited to Rockafellar, Facchinei–Pang, Bertsekas, Horn–Johnson.
invented entities (2)
  • Perturbed utility Markovian choice model (PUMCM) no independent evidence
    purpose: Behavioral demand model that generalizes ARUM recursive logit and admits corner solutions via a convex surplus.
    Defined by the surplus-regularized Bellman operator; its well-posedness and demand properties are proved from the standing assumptions.
  • Perturbed utility Markovian equilibrium (PUME) no independent evidence
    purpose: Equilibrium concept coupling PUMCM demand with general supply via a dual cost-space VI.
    Existence/uniqueness and primal–dual equivalence are derived; no external empirical validation beyond numerical illustrations.

pith-pipeline@v1.1.0-grok45 · 43701 in / 3045 out tokens · 33866 ms · 2026-07-13T02:04:37.460538+00:00 · methodology

0 comments
read the original abstract

Large-scale traffic assignment requires equilibrium models that are both behaviorally plausible and computationally tractable. This paper develops a perturbed utility Markovian equilibrium (PUME) framework that preserves the scalability of link-based Markovian traffic equilibrium models and extends their applicability to settings with boundary choice probabilities, undiscounted network loading, and general link interactions. As the behavioral basis of PUME, we first develop the perturbed utility Markovian choice model (PUMCM) in which the Bellman optimality operator is defined through a convex surplus function whose gradient directly yields the optimal policy. The model generalizes existing additive random utility (ARUM) Markovian choice models and admits both interior and boundary choice probabilities. Accordingly, unattractive links can receive zero flow without imposing ex ante choice-set restrictions as in existing ARUM models. We establish conditions under which the corresponding Markov decision problem is well posed and yields a proper demand mapping. We then formulate the equilibrium as a variational inequality (VI) problem on the dual cost space and establish its existence and uniqueness. Particularly, the VI formulation of PUME accommodates non-separable and asymmetric cost structures and thus offers a more flexible modeling framework than existing Markovian traffic equilibrium (MTE) models. For computation, we develop a modified policy iteration method for network loading and a safeguarded accelerated meta-algorithm for computing equilibrium. Both algorithms are proven to be globally convergent and have demonstrated satisfactory numerical performances. Experiments on benchmark and synthetic networks further show that the proposed framework is highly scalable and robust towards a wide variety of demand-supply settings.

Figures

Figures reproduced from arXiv: 2607.09568 by Kenan Zhang, Rui Yao.

Figure 1
Figure 1. Figure 1: α-entmax choice map against utility gap. Specifically, the well-posed case uses the free-flow times shown in [PITH_FULL_IMAGE:figures/full_fig_p022_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Stylized network [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Value iteration on the stylized network. [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Link flows on the stylized network under recursive logit ( [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: PUME subject to asymmetric link interactions. [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example of synthetic grid network (k = 2). 26 [PITH_FULL_IMAGE:figures/full_fig_p026_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Sensitivity results on grid networks with varying sizes. [PITH_FULL_IMAGE:figures/full_fig_p027_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Sensitivity results on grid networks at k = 5, 10, 15 with varying demand levels. 0 20 40 60 80 100 120 PUMCM iteration 10 −12 10 −9 10 −6 10 −3 10 0 10 3 ‖ Vk + 1 − Vk ‖ ∞ m=1 m=2 m=5 m=10 m=20 m=inf 1 2 5 10 20 ∞ MPI depth m 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 PUMCM solve time (s) 1 2 5 10 20 ∞ MPI depth m 0 2 4 6 8 10 12 PUME wall-clock time (s) [PITH_FULL_IMAGE:figures/full_fig_p028_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Sensitivity results with varying MPI evaluation steps. [PITH_FULL_IMAGE:figures/full_fig_p028_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Outer gap trajectories for different solver configurations. [PITH_FULL_IMAGE:figures/full_fig_p048_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Iteration trajectories on Sioux Falls. 0 100 200 300 400 500 Operator evaluations (Eval.) 10 −5 10 −4 10 −3 10 −2 10 −1 10 0 ‖ rn a ‖t ∞ / m a x ( 1, ‖ c ‖ ∞ ) Potential α-entmax Logit NRL AA1 NGMRES 0 100 200 300 400 500 Operator evaluations (Eval.) Non-potential (ε=0.1) [PITH_FULL_IMAGE:figures/full_fig_p049_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Convergence trajectories on Anaheim. 0 200 400 600 800 Operator evaluations (Eval.) 10 −5 10 −4 10 −3 10 −2 10 −1 ‖ rn a ‖t ∞ / m a x ( 1, ‖ c ‖ ∞ ) Potential α-entmax Logit NRL AA1 NGMRES 0 200 400 600 800 1000 Operator evaluations (Eval.) Non-potential (ε=0.1) [PITH_FULL_IMAGE:figures/full_fig_p049_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Iteration trajectories on Chicago Sketch. [PITH_FULL_IMAGE:figures/full_fig_p049_13.png] view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

14 extracted references · 4 canonical work pages

  1. [1]

    doi: 10.1016/0191-2615(95)00005-X. 29 M. Ben-Akiva, D. McFadden, T. G ¨arling, D. Gopinath, J. Walker, D. Bolduc, A. B ¨orsch-Supan, P . Delqui´e, O. Larichev, T. Morikawa, et al. Extended framework for modeling choice behavior. Marketing letters, 10(3):187–203,

    work page doi:10.1016/0191-2615(95)00005-x

  2. [2]

    G. M. Correia, V . Niculae, and A. F. T. Martins. Adaptively sparse transformers. InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2174– 2184,

    2019

  3. [3]

    Fosgerau, E

    30 M. Fosgerau, E. Frejinger, and A. Karlstrom. A link based network route choice model with unrestricted choice set.Transportation Research Part B: Methodological, 56:70–80, 2013a. M. Fosgerau, D. McFadden, and M. Bierlaire. Choice probability generating functions.Journal of Choice Modelling, 8:1–18, 2013b. ISSN 1755-5345. doi: https://doi.org/10.1016/j....

    work page doi:10.1016/j.jocm.2013.05 2013

  4. [4]

    doi: 10.1007/0-306-48332-7

    ISBN 978-0-306-48332-5. doi: 10.1007/0-306-48332-7

    work page doi:10.1007/0-306-48332-7

  5. [5]

    doi: 10.3141/1645-17. H. F. Walker and P . Ni. Anderson acceleration for fixed-point iterations.SIAM Journal on Numer- ical Analysis, 49(4):1715–1735,

    work page doi:10.3141/1645-17

  6. [6]

    33 A Deferred proofs from Section 3 A.1 Proof of Lemma 1 The weak duality is directly proved by rearranging Eq. (4). SinceH s is convex and continuously differentiable, for anyQ ′ ∈R |As|, Hs(Q′)≥H s(Q) +∇H s(Q) ⊤(Q′ −Q), (46) which can be rearranged as ∇Hs(Q) ⊤Q′ −H s(Q′)≤ ∇H s(Q) ⊤Q−H s(Q). (47) The inequality can be further expanded as ∇Hs(Q) ⊤Q′ −H s(...

    2012

  7. [7]

    B.2 Proof of Theorem 1 Consider the anchor point ˆcintroduced in Assumption 3(i)

    Following the same reasoning, we haveΦis convex andC 2 inc, which further yields∇x(c) =−∇ 2Φ(c)⪯0. B.2 Proof of Theorem 1 Consider the anchor point ˆcintroduced in Assumption 3(i). As per Proposition 4, the monotone link demand satisfies ⟨x(c)−x( ˆc),c− ˆc⟩ ≤0,⇒ ⟨x(c),c− ˆc⟩ ≤ ⟨x( ˆc),c− ˆc⟩,∀c∈Ω. (63) 37 Accordingly, forc̸= ˆc, we have ⟨E(c),c− ˆc⟩ ∥c− ˆ...

    2001

  8. [8]

    Hence, there exists a matrix norm with||P π∗ ||<1(Horn and Johnson, 2012, Lemma 5.6.10), and further||P m π∗ || ≤ ||P π∗ ||m <1

    Since the optimal policyπ ∗ is proper (Proposition 1 (iii)), its spectral radius satisfiesρ(P π∗ )<1. Hence, there exists a matrix norm with||P π∗ ||<1(Horn and Johnson, 2012, Lemma 5.6.10), and further||P m π∗ || ≤ ||P π∗ ||m <1. Plugging the result of Lemma 6, the convergence gap can be rewritten as Om(V)−V ∗ =O m(V)−O m(V∗) =∇O m(V∗)(V−V ∗) +o(||V−V ∗|...

    2012

  9. [9]

    (23)–(26) is a special variant of Algorithm 3.2 of Solodov and Tseng (1996) with preconditioning matrixI

    Proof.With continuous monotone operatorEand closed convex setΩ, the ST method imple- mented in Eqs. (23)–(26) is a special variant of Algorithm 3.2 of Solodov and Tseng (1996) with preconditioning matrixI. The proof of the ST method (Solodov and Tseng, 1996, Theorem 3.2, Eq. (3.11)) gives ∥cB n+1 −c ∗∥2 ≤ ∥c B n −c ∗∥2 −θ(2−θ)(1−δ) 2 ∥cn − ˆcn∥4 ∥(cn − ˆc...

    1996

  10. [10]

    Its convergence analysis (Malitsky, 2020, Eq

    43 Proof.SinceEis monotone, aGRAAL (27)–(29) coincides with the metric golden-ratio method of Malitsky (2020, Algorithm 2). Its convergence analysis (Malitsky, 2020, Eq. (70)) shows that, for any solutionc ∗, there is a non-decreasing energyW n over iterations: Wn := φ φ−1 ∥ ˆcn −c ∗∥2 M + φλn−1 2λn−2 ∥cn −c n−1∥2 M (89) Initializingc 1 =c 0 and ˆc0 =c 0 ...

    2020

  11. [11]

    (93) Proof.We prove thatH s constructed from Eq

    Besides, the maximizer of(92)is unique for every Q and coincides with ∇Hs(Q), that is, ∇Hs(Q) =arg max π∈∆ s π⊤Q−H ∗ s (π) ∈∆ s. (93) Proof.We prove thatH s constructed from Eq. (92) satisfies each condition in Standing Assump- tion 1, along with the uniqueness of maximizer and its correspondence to∇H s, as follows: (i) Convexity (A1): As a pointwise supr...

    1970

  12. [12]

    (40) can is easily shown to be interior and smooth

    D.1 Logit/Softmax The logit/softmax choice map Eq. (40) can is easily shown to be interior and smooth. The Hessian of surplus is derived as ∇2Hs(Q) = 1 µ s diag(∇H s(Q))− ∇H s(Q)∇H s(Q) ⊤ , (95) which is smooth inQ. Thus,H s defined in Eq. (39) satisfies Assumption 1 and yields a Lipschitz choice map. D.2 Sparsemax The sparsemax choice map Eq. (43) is pie...

    2016

  13. [13]

    (96) leads to an optimal choice map that isC 1 inQ

    Pluggingτ(Q)back to Eq. (96) leads to an optimal choice map that isC 1 inQ. Given its equivalence to∇H s,H s isC 2 and satisfies Assumption 1 and generates a Lipschitz choice map. D.3.1 Solution method ofα-entmax choice map Solving the choice map Eq. (96) is equivalent to a root finding problem of Eq. (97). While de- pending on the value ofα, it may or ma...

    2008

  14. [14]

    (96) has no closed-form solution but the monotone property of F(Q,τ)makes the root finding easily done via bisection search (Blondel et al., 2020)

    •α=1.2: In this case, Eq. (96) has no closed-form solution but the monotone property of F(Q,τ)makes the root finding easily done via bisection search (Blondel et al., 2020). Let zmax =max a za withz a =Q a/µ s. The lower bound can be easily found asF(Q,z max) = −1<0. While the upper bound is constructed asF(Q,z max − 1 α−1 ) = ∑a[(α−1)(z a − zmax) +1] 1/(...

    2020