Pith. sign in

REVIEW 3 major objections 5 minor 43 references

PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper claims that a GPU-accelerated restarted primal-dual hybrid conjugate gradient method converges linearly to Fisher market equilibrium and scales to ten-million-buyer instances, with the same engine solving Arrow-Debreu…

desk verdict Impressive scale and a clever row-solver, but the linear-convergence theorem leans on an unpublished quadratic-growth bridge that the paper never states or checks. read the letter →

arxiv 2506.06258 v1 pith:FYJW7W7P submitted 2025-06-06 math.OC

Huikang Liu , Yicheng Huang , Hongpei Li , Dongdong Ge , Yinyu Ye This is my paper
classification math.OC MSC 90C2590C3391B5090C0665K05
keywords Fishermarketequilibriumcompetitiveprimal-dualhybridgradientGPUaccelerationlinearconvergenceArrow-DebreuquadraticgrowthEisenberg-Galeprogram
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that competitive market equilibrium can be computed at a scale traditional solvers cannot reach: the authors propose a restarted primal-dual hybrid conjugate gradient method for the Eisenberg-Gale program that solves Fisher markets with linear utilities, prove it converges linearly under a quadratic-growth condition, and show the same routine can drive an Arrow-Debreu fixed-point loop. The motivation is practical: Fisher equilibria underlie fair allocation mechanisms such as course allocation and recommendation systems, but interior-point and projection-based solvers stall at a few thousand variables. The key structural move is to solve each buyer's bundle update separately by finding the root of one monotone scalar equation per row, so every iteration is matrix-free and parallelizes naturally on a GPU. If the claims hold, the method solves synthetic Fisher markets with ten million buyers and roughly four hundred million nonzero utility entries in about 590 seconds, and real transaction data from a large e-commerce platform in about 1,223 seconds.

What carries the argument

The central object is the restarted primal-dual hybrid conjugate gradient (PDHCG) update for the saddle-point formulation of the Eisenberg-Gale program, together with a row-wise subproblem solver. Each inner iteration updates prices $p$ by a closed-form dual step, then solves each buyer's row subproblem by finding the root $s>0$ of the monotonically increasing equation $\phi(s)=s-\sum_j u_{ij}\,\max(0,\,x^k_{ij}-\tau p^{k+1}_j+\tau w_i/s)$, which is handled by an enhanced bisection search or, in the GPU implementation, a 32-section search that lets all threads in a warp work on the same interval. The convergence engine is the quadratic-growth property of the smoothed duality gap $G_\xi(z;\dot z)=\max_{\hat z}\,[Q(z,\hat z)-(\xi/2)\lVert \hat z-\dot z\rVert^2]$, obtained through a scaled KKT error bound for the perturbed Eisenberg-Gale system, which turns the sublinear inner bound into a per-restart $1/2$ contraction. For Arrow-Debreu markets, the machinery is the fixed-point iteration $w\leftarrow E\,p(w)$, with contraction derived from Lipschitz continuity of the Fisher price map and a matrix Bernstein concentration bound on the random endowment matrix.

What would settle it

Run Algorithm 2 with $\sigma=\tau=1/(2\sqrt{n})$ and $K=\max(4\sqrt{n}/\xi,4\sqrt{n}/\alpha_\xi)$ on a small Fisher market with a known equilibrium and measure $\mathrm{dist}(z^{n+1,0},Z^\star)$ after each restart; any restart that fails to halve this distance refutes Eq. (19). A second check is to solve the row subproblems to tolerances $10^{-6}$, $10^{-8}$, and $10^{-10}$ and test whether the contraction ratio approaches $1/2$ only in the exact limit.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for the saddle-point formulation (9) of the Fisher market, choosing step sizes $\sigma=\tau=1/(2L)$ with $L=\sqrt{n}$, and restarting every $K\ge \max(4L/\xi,4L/\alpha_\xi)$ inner iterations, makes each restart block contract the distance to the saddle-point set by a factor of $1/2$, so the restarted PDHCG method converges linearly to the Fisher equilibrium. The proof obtains this by combining the standard $O(1/K)$ sublinear bound on the smoothed duality gap of the inner PDHG iterates with a quadratic-growth property of that same gap, which the authors derive from a scaled KKT error bound for the Eisenberg-Gale program. The same error-bound analysis covers both the $t$-augmented PDHG formulation (3) and the reduced PDHCG formulation (9). For Arrow-Debreu markets, the paper claims that the fixed-point iteration $w\leftarrow E\,p(w)$ converges linearly with high probability when utilities and endowments are random and the endowment variance is small; numerically it reports stable convergence in about 9 to 33 iterations on synthetic instances up to ten million agents.

Load-bearing premise

The linear-rate theorem depends on an unpublished result asserting that being close to satisfying the market-clearing and optimality conditions forces the gap-measure used in the proof to grow at least quadratically, and on the assumption that each buyer's bundle update is solved exactly rather than to a finite tolerance; if either premise fails, the factor-1/2 contraction guarantee is not established.

Editorial extensions

If this is right

  • Synthetic Fisher markets with ten million buyers, 4,000 goods, and roughly 400 million nonzero utilities can be solved to a relative KKT error below $10^{-4}$ in about 590 seconds on a GPU, where interior-point and conic solvers exceed time or memory limits.
  • The same algorithm solves a one-month transaction dataset from a large e-commerce platform (about 2.56 million users and 27,000 products) in about 1,223 seconds, while the comparison solvers fail on the largest instances.
  • The linear convergence guarantee applies to both the $t$-augmented PDHG formulation and the reduced PDHCG formulation, because the same KKT error bound and quadratic-growth argument covers both saddle problems (3) and (9).
  • The Arrow-Debreu fixed-point iteration converges linearly with high probability under random utilities and endowments with small variance, and the reported experiments use roughly 9 to 33 iterations on synthetic instances up to ten million agents.
  • Because each per-row subproblem reduces to a monotone scalar root-finding problem, every PDHCG iteration is matrix-free and parallelizable, which is the property that allows the method to run at this scale.

Reading between the lines

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

  • Editorial inference: if the KKT-error-bound-to-quadratic-growth template survives scrutiny, the same proof route may apply to other convex programs with logarithmic objectives and linear constraints, such as fair-division or resource-allocation problems with CES or Leontief utilities, which the paper does not analyze.
  • Editorial inference: the reported advantage of 32-section search over bisection suggests a transferable GPU design principle: for row-wise scalar root-finding, evaluating multiple candidate points in lockstep reduces warp divergence and repeated memory traffic, a trade-off that could be tested in other primal-dual solvers with separable subproblems.
  • Editorial inference: the exactness assumption on the row subproblems can be stress-tested by running Algorithm 2 with subproblem tolerances $10^{-6}$, $10^{-8}$, and $10^{-10}$ and measuring whether the per-restart contraction ratio stays at or below $1/2$; evidence that the ratio degrades with looser tolerances would show that Theorem 1's guarantee depends on the exact-solution idealization flagg
  • Editorial inference: for Arrow-Debreu markets the contraction theorem is probabilistic and specifically requires small variance in random endowments, so the practical reach of the fixed-point method is large random markets rather than all possible endowment structures; a deterministic counterexample in the cited literature already shows the fixed-point map can diverge.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. This paper proposes PDHCG, a restarted primal-dual hybrid gradient method with row-separable subproblem solves, for large-scale Fisher market equilibrium problems with linear utilities, together with a GPU implementation and a fixed-point extension to Arrow-Debreu markets. The theoretical section claims linear convergence of the restarted method by establishing a KKT error bound (Proposition 1) and then invoking an unpublished result [28] to obtain quadratic growth of the smoothed duality gap (Corollary 1), from which contraction of each restart block is derived (Theorem 1). The experimental section reports strong scaling results on synthetic instances with up to 10^7 buyers and on JD.com transaction data, comparing favorably with MOSEK, PDCS, PDHG, and PGLS.

Significance. If the linear-convergence claim were fully proved, the paper would be a meaningful advance: it combines row-separable subproblem solves with GPU parallelism to scale Fisher and Arrow-Debreu equilibrium computation well beyond prior first-order methods, and the fixed-point treatment of Arrow-Debreu markets under random endowments is a useful contribution. Strengths include the matrix-free algorithmic design, the 32-section GPU search, reproducible code, and extensive experiments on both synthetic and real data. The main caveat is that the central contraction theorem currently rests on an unstated, unpublished quadratic-growth bridge, so the theoretical guarantee is conditional; the numerical work, however, is substantial and convincing as a practical contribution.

major comments (3)
  1. [§3.2, Corollary 1] The statement that the smoothed duality gap satisfies quadratic growth for saddle problems (3) and (9) is the only route from the KKT error bound of Proposition 1 to the contraction in Theorem 1, and it is imported from Theorem 1 of [28], an unpublished manuscript that is neither stated nor verified here. The sentence 'follows directly from Proposition 1, (34), and Theorem 1 in [28]' is not a proof: the reader cannot check that the hypotheses of [28, Thm. 1] cover the non-smooth logarithmic term -w_i log(u_i^T x_i) in (9) or the unbounded dual domain p in R^m. Because the first inequality in the proof of Theorem 1, dist(z^{n+1,0},Z*)^2 <= (1/alpha_xi) G_xi(z^{n+1,0}; z*), requires (14), Corollary 1 is load-bearing. Please either state and prove the relevant result from [28] in this paper, or give a self-contained proof of Corollary 1 (or a direct quadratic-growth/cost-error-bound proof for (9)).
  2. [§3.1, Remark 2] The proof of Theorem 1 assumes the KKT conditions (10) of the row subproblem are solved exactly, whereas Algorithm 3 and the 32-section variant used in the experiments stop at finite tolerance epsilon. Remark 2 asserts that this is harmless in practice, but no statement quantifies the effect of the inner residual on the outer contraction. As written, the convergence guarantee applies to an idealized exact-arithmetic algorithm rather than to the implemented solver. Please add an inexact-perturbation analysis showing, for example, that if each row solve returns x_i with KKT residual bounded by epsilon, then the contraction factor in (19) becomes (1/2 + C*epsilon) or the iteration count K is adjusted accordingly; otherwise state Theorem 1 for the inexact oracle and prove it.
  3. [§3.1, proof of Theorem 1] The boundedness argument is circular as written. The main contraction (19) is first derived under the assumption that the whole sequence {z^{n,0}} lies in a bounded set S, and then (19) is used in the induction that establishes boundedness. This can be repaired by proving simultaneously, by induction on n, that dist(z^{n,0},Z*) <= 2 dist(z^{0,0},Z*) and that all iterates up to block n lie in a fixed ball (using Lemma 2(1) to control the next block), but the current text does not carry out that induction and should be rewritten.
minor comments (5)
  1. [§3.2, proof of Proposition 1] The assertion that 'the l2 norm of ~F_xi is a sharp function' is stated without argument; since ~F_xi is piecewise linear with zero set X*, this can be proved by a finite-piece analysis, but the proof should be included for completeness.
  2. [§3.2, Eq. (34)] The equality in (34) should read F_xi(x,p) = F_xi(x,t,p,y), not G_xi(x,p) = F_xi(x,t,p,y); G_xi denotes the smoothed duality gap in Definition 2, not the KKT residual.
  3. [§5.1, Table 2] The solver names are inconsistent: the text and the reference list refer to PGLS, while Table 2 and the note use 'PDLS'; please unify the notation.
  4. [§5.1, first paragraph] The sentence describing small-scale problems says 'e.g., m=10^3, n=400', but Table 2 gives n=10^3 and m=400 for that row; the roles of n and m appear swapped.
  5. [§5.1, Table 2 heading] There is a typo in the table caption: 'synchetic' should be 'synthetic'.

Circularity Check

1 steps flagged · score 4.0 of 10

The central contraction theorem's quadratic-growth premise is delegated to an unpublished self-citation ([28]); the rest of the derivation is self-contained.

  1. self citation load bearing [Section 3.2, paragraph between Eq. (34) and Corollary 1; also Reference [28]]
    "Finally, the quadratic growth property for both the problem (3) and the problem (9) follows directly from Proposition 1, (34), and Theorem 1 in [28]. This leads to the following corollary: Corollary 1."

    Theorem 1's contraction bound (19) is obtained by applying quadratic growth (Definition 3, Eq. (14)) to the smoothed duality gap; the paper's only argument for that property is the sentence above, which cites Theorem 1 of [28]. [28] is an unpublished manuscript by the lead author (H. Liu and J. Li, 2025) hosted on the author's webpage, and its theorem and hypotheses are not stated or checked against the non-smooth Fisher saddle problem (9) (logarithmic term -w_i log(u_i^T x_i), unbounded p in R^m). Thus the decisive step converting the self-contained KKT error bound (Proposition 1) into the quadratic growth used by Theorem 1 is a load-bearing self-citation, not an argument present in the paper.

full rationale

Apart from the Corollary 1 bridge, the paper's derivation is self-contained and not definitionally circular: (9) is the Eisenberg-Gale reformulation, Lemma 1/Lemma 2 are standard PDHG bounds with the stated choices sigma=tau=1/(2L), K>=..., and Proposition 1 is proved in the text (up to the assertion about sharpness of the modified residual, which is a correctness gap rather than a circularity). No fitted parameter is relabeled as a prediction, and the numerical experiments compare against independent solvers. However, the central linear-convergence claim (Theorem 1, Eq. (19)) rests on the quadratic-growth conclusion of Corollary 1, and that conclusion is delegated to Theorem 1 of [28], an unpublished self-citation by a current author. Because this is the sole bridge from the KKT error bound to the contraction factor, the central theoretical result is partially dependent on a self-citation chain. This justifies a moderate score rather than 0, but not a high score, since the bulk of the analysis and the algorithmic contribution remain independent content.

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

The central claim rests on (i) standard results: Chambolle-Pock, Eisenberg-Gale, Ye's price uniqueness, Hoeffding and matrix Bernstein inequalities, and the sharpness property of piecewise-linear functions; and (ii) three non-standard inputs: Theorem 1 of the unpublished manuscript [28], which supplies the entire error-bound-to-quadratic-growth bridge; the Taylor-modified problem device inside Proposition 1, which is asserted rather than fully proved; and Assumptions 2-3 plus the unquantified kappa condition, which make the Arrow-Debreu contraction statement non-effective. Algorithmic hyperparameters (restart thresholds, step-size bounds, 32-section count, tolerances) affect empirical speed but not the theoretical claims. No new physical or mathematical entities are postulated.

free parameters (5)
  • Adaptive restart thresholds (beta_sufficient, beta_necessary, beta_artificial) = 0.2, 0.8, 0.2
    Hand-tuned hyperparameters of the adaptive restart strategy (Section 5, Algorithmic Enhancements). They affect empirical iteration counts and runtimes but do not enter the convergence theorem.
  • Step-size and primal-weight adaptation parameters (theta, eta bounds) = theta = 0.2; 0.01*eta_initial <= eta <= 3*eta_initial
    Acceleration heuristics inherited from PDHCG for QP [23]; used to improve practical convergence and not part of the analyzed algorithm.
  • Section count for the GPU inner search = 32
    Selected empirically from the runtime comparison in Table 1; the convergence theory only covers exact bisection.
  • Inner and outer termination tolerances = 1e-8 inner; 1e-4 relative KKT outer
    The 1e-8 inner tolerance is invoked in Remark 2 to justify the exact-subproblem assumption; the 1e-4 outer tolerance defines the reported runtimes.
  • Smoothing parameter xi and restart length K = unspecified; K >= max(4L/xi, 4L/alpha_xi)
    Degrees of freedom in Theorem 1. The constant alpha_xi is existential and depends on xi and on the bounded set, so the theorem yields no computable restart length.
assumptions (8)
  • standard math Chambolle-Pock PDHG bounds (Lemma 1, from [10, Theorem 1]): bounded iterates and an O(1/K) ergodic duality gap under tau*sigma*L^2 < 1.
    Starting point of the convergence analysis in Section 3.1; a published result that is not re-derived here.
  • standard math Sharpness (lower Lipschitz) property of the l2 norm of continuous piecewise-linear residual functions on bounded sets.
    Invoked in the proof of Proposition 1 with the phrase 'the l2 norm of F~_xi is a sharp function', without proof or citation. Standard in error-bound theory, but not demonstrated here.
  • ad hoc to paper Theorem 1 of Liu and Li [28]: KKT error bounds imply quadratic growth of the smoothed duality gap for convex linearly constrained problems.
    Unpublished manuscript hosted on the lead author's personal webpage. Corollary 1 and therefore Theorem 1 depend on it entirely; the load-bearing external input of the paper.
  • domain assumption Fact 1: uniqueness of t* and p*, boundedness of X*, and sum_j p*_j = sum_i w_i (attributed to Ye [41]).
    Used in Fact 1 and throughout Section 3.2; price uniqueness also keeps the Fisher map p(w) well-defined for the Arrow-Debreu fixed-point loop.
  • domain assumption The Eisenberg-Gale program (1) characterizes competitive equilibria of the Fisher market with CCNH utilities.
    The formulation foundation of the entire paper, introduced in Section 1.
  • domain assumption Arrow-Debreu equilibrium reduces to the fixed point w = E p(w), with p(w) the unique Fisher equilibrium price.
    From Ye [41]; the basis of Algorithm 4 and the whole of Section 4.
  • ad hoc to paper Assumptions 2 and 3: i.i.d. random utilities and endowments with positive probability mass bounded away from zero, endowments of variance delta^2.
    Introduced specifically to make the Arrow-Debreu mapping T contractive with high probability; the contraction condition delta <= gamma/(2 kappa sqrt((m+n) log(m+n))) involves the unquantified Lipschitz constant kappa.
  • standard math Hoeffding's inequality and the matrix Bernstein inequality [38].
    Used in Lemma 3 and Theorem 2 to obtain the high-probability invariance and contraction statements.

how reviews work

0 comments
Cite this review

Pith. "Pith review of PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation." pith.science (2026). https://pith.science/paper/FYJW7W7P

@misc{pith2026250606258,
  author       = {Pith},
  title        = {Pith review of: PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FYJW7W7P}},
  note         = {Machine review of arXiv:2506.06258}
}
read the original abstract

Large-scale competitive market equilibrium problems arise in a wide range of important applications, including economic decision-making and intelligent manufacturing. Traditional solution methods, such as interior-point algorithms and certain projection-based approaches, often fail to scale effectively to large problem instances. In this paper, we propose an efficient computational framework that integrates the primal-dual hybrid conjugate gradient (PDHCG) algorithm with GPU-based parallel computing to solve large-scale Fisher market equilibrium problems. By exploiting the underlying mathematical structure of the problem, we establish a theoretical guarantee of linear convergence for the proposed algorithm. Furthermore, the proposed framework can be extended to solve large-scale Arrow-Debreu market equilibrium problems through a fixed-point iteration scheme. Extensive numerical experiments conducted on GPU platforms demonstrate substantial improvements in computational efficiency, significantly expanding the practical solvable scale and applicability of market equilibrium models.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 30 canonical work pages

  1. [28]

    https://huikang2019.github.io/NonLinear_PDHCG.pdf (2025)

    Liu, H., Li, J.: Bridging primal and primal-dual analyses: From error bounds to quadratic growth. https://huikang2019.github.io/NonLinear_PDHCG.pdf (2025)

    work page 2025

  2. [1]

    SIAM Journal on Optimization32(2), 1288–1318 (2022)

    Alacaoglu, A., Fercoq, O., Cevher, V.: On the convergence of stochastic primal-dual hybrid gradient. SIAM Journal on Optimization32(2), 1288–1318 (2022)

    work page 2022

  3. [2]

    Advances in Neural Information Processing Systems34, 20243–20257 (2021)

    Applegate, D., Díaz, M., Hinder, O., Lu, H., Lubin, M., O’Donoghue, B., Schudy, W.: Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems34, 20243–20257 (2021)

    work page 2021

  4. [3]

    Mathematical Programming201(1), 133–184 (2023)

    Applegate, D., Hinder, O., Lu, H., Lubin, M.: Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming201(1), 133–184 (2023)

    work page 2023

  5. [4]

    Econometrica22(3), 265–290 (1954)

    Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica22(3), 265–290 (1954)

    1954

  6. [5]

    The Review of Economic Studies86(1), 81–116 (2019)

    Azevedo, E.M., Budish, E.: Strategy-proofness in the large. The Review of Economic Studies86(1), 81–116 (2019)

    work page 2019

  7. [6]

    Operations Research70(1), 288–308 (2022)

    Bateni, M., Chen, Y., Ciocan, D.F., Mirrokni, V.: Fair resource allocation in a volatile marketplace. Operations Research70(1), 288–308 (2022)

    work page 2022

  8. [7]

    American Journal of Economics and Sociology64(1), 57–83 (2005)

    Brainard, W.C., Scarf, H.E.: How to compute equilibrium prices in 1891. American Journal of Economics and Sociology64(1), 57–83 (2005)

    work page 2005

Show all 43 references
  1. [8]

    Journal of Political Economy119(6), 1061–1103 (2011)

    Budish, E.: The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy119(6), 1061–1103 (2011)

    2011

  2. [9]

    National Bureau of Economic Research (2016)

    Budish, E., Kessler, J.B., et al.: Bringing real market participants’ real preferences into the lab: An experiment that changed the course allocation mechanism at Wharton. National Bureau of Economic Research (2016)

    2016

  3. [10]

    Journal of mathematical imaging and vision40, 120–145 (2011)

    Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision40, 120–145 (2011)

    2011

  4. [11]

    Mathematical Programming159(1), 253–287 (2016)

    Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal–dual algorithm. Mathematical Programming159(1), 253–287 (2016)

    2016

  5. [12]

    arXiv preprint arXiv:2408.12179 (2024)

    Chen, K., Sun, D., Yuan, Y., Zhang, G., Zhao, X.: Hpr-lp: An implementation of an hpr method for solving linear programming. arXiv preprint arXiv:2408.12179 (2024)

    2024 arXiv

  6. [13]

    Theory of Computing Systems pp

    Chen, P.A., Lu, C.J., Lu, Y.S.: An alternating algorithm for finding linear arrow-debreu market equilibria. Theory of Computing Systems pp. 1–18 (2022)

    2022

  7. [14]

    SIAM Journal on Optimization24(4), 1779–1814 (2014)

    Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM Journal on Optimization24(4), 1779–1814 (2014)

    2014

  8. [15]

    ACM Trans- actions on Economics and Computation (TEAC)5(1), 1–13 (2016)

    Devanur, N.R., Garg, J., Végh, L.A.: A rational convex program for linear arrow-debreu markets. ACM Trans- actions on Economics and Computation (TEAC)5(1), 1–13 (2016)

    2016

  9. [16]

    In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002

    Devanur, N.R., Papadimitriou, C.H., Saberi, A., Vazirani, V.V.: Market equilibrium via a primal-dual-type algorithm. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. pp. 389–395. IEEE (2002)

    2002

  10. [17]

    Mathematics of Operations Research43(3), 919–948 (2018)

    Drusvyatskiy, D., Lewis, A.S.: Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research43(3), 919–948 (2018)

    2018

  11. [18]

    The Annals of Mathe- matical Statistics30(1), 165–168 (1959)

    Eisenberg, E., Gale, D.: Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathe- matical Statistics30(1), 165–168 (1959)

    1959

  12. [19]

    arXiv preprint arXiv:2206.03041 (2022)

    Fercoq, O.: Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient. arXiv preprint arXiv:2206.03041 (2022)

    2022 arXiv

  13. [20]

    Advances in Neural Information Processing Systems33, 21738–21750 (2020)

    Gao, Y., Kroer, C.: First-order methods for large-scale market equilibrium computation. Advances in Neural Information Processing Systems33, 21738–21750 (2020)

    2020

  14. [21]

    arXiv preprint arXiv:2403.09133 (2024) PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation 21

    Han, Q., Li, C., Lin, Z., Chen, C., Deng, Q., Ge, D., Liu, H., Ye, Y.: A low-rank admm splitting approach for semidefinite programming. arXiv preprint arXiv:2403.09133 (2024) PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation 21

    2024 arXiv

  15. [22]

    arXiv preprint arXiv:2407.15049 (2024)

    Han, Q., Lin, Z., Liu, H., Chen, C., Deng, Q., Ge, D., Ye, Y.: Accelerating low-rank factorization-based semidef- inite programming algorithms on gpu. arXiv preprint arXiv:2407.15049 (2024)

    2024 arXiv

  16. [23]

    arXiv preprint arXiv:2405.16160 (2024)

    Huang, Y., Zhang, W., Li, H., Ge, D., Liu, H., Ye, Y.: Restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming. arXiv preprint arXiv:2405.16160 (2024)

    2024 arXiv

  17. [24]

    SIAM Journal on Computing37(1), 303–318 (2007)

    Jain, K.: A polynomial time algorithm for computing an arrow–debreu market equilibrium for linear utilities. SIAM Journal on Computing37(1), 303–318 (2007)

    2007

  18. [25]

    arXiv preprint arXiv:1909.10925 (2019)

    Kroer, C., Peysakhovich, A.: Scalable fair division for’at most one’preferences. arXiv preprint arXiv:1909.10925 (2019)

    2019 arXiv

  19. [26]

    Mathematical Program- ming159, 403–434 (2016)

    Liang, J., Fadili, J., Peyré, G.: Convergence rates with inexact non-expansive operators. Mathematical Program- ming159, 403–434 (2016)

    2016

  20. [27]

    arXiv preprint arXiv:2505.00311 (2025)

    Lin, Z., Xiong, Z., Ge, D., Ye, Y.: Pdcs: A primal-dual large-scale conic programming solver with gpu enhance- ments. arXiv preprint arXiv:2505.00311 (2025)

    2025

  21. [29]

    jl: A gpu implementation of restarted primal-dual hybrid gradient for linear program- ming in julia

    Lu, H., Yang, J.: cupdlp. jl: A gpu implementation of restarted primal-dual hybrid gradient for linear program- ming in julia. arXiv preprint arXiv:2311.12180 (2023)

    2023 arXiv

  22. [30]

    arXiv preprint arXiv:2311.07710 (2023)

    Lu, H., Yang, J.: A practical and optimal first-order method for large-scale convex quadratic programming. arXiv preprint arXiv:2311.07710 (2023)

    2023 arXiv

  23. [31]

    arXiv preprint arXiv:2407.19689 (2024)

    Lu, H., Yang, J.: Pdot: A practical primal-dual algorithm and a gpu-based solver for optimal transport. arXiv preprint arXiv:2407.19689 (2024)

    2024 arXiv

  24. [32]

    arXiv preprint arXiv:2407.16144 (2024)

    Lu, H., Yang, J.: Restarted halpern pdhg for linear programming. arXiv preprint arXiv:2407.16144 (2024)

    2024 arXiv

  25. [33]

    arXiv preprint arXiv:2312.14832 (2023)

    Lu, H., Yang, J., Hu, H., Huangfu, Q., Liu, J., Liu, T., Ye, Y., Zhang, C., Ge, D.: cupdlp-c: A strengthened implementation of cupdlp for linear programming by c language. arXiv preprint arXiv:2312.14832 (2023)

    2023 arXiv

  26. [34]

    In: Proceedings of the 21st ACM Conference on Economics and Computation

    McElfresh, D.C., Kroer, C., Pupyrev, S., Sodomka, E., Sankararaman, K.A., Chauvin, Z., Dexter, N., Dickerson, J.P.: Matching algorithms for blood donation. In: Proceedings of the 21st ACM Conference on Economics and Computation. pp. 463–464 (2020)

    2020

  27. [35]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Nan, T., Gao, Y., Kroer, C.: Fast and interpretable dynamics for fisher markets via block-coordinate updates. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 37, pp. 5832–5840 (2023)

    2023

  28. [36]

    ACM Transactions on Economics and Computation (TEAC)3(1), 1–22 (2015)

    Parkes, D.C., Procaccia, A.D., Shah, N.: Beyond dominant resource fairness: Extensions, limitations, and indi- visibilities. ACM Transactions on Economics and Computation (TEAC)3(1), 1–22 (2015)

    2015

  29. [37]

    com: Transaction-level data for the 2020 msom data driven research challenge

    Shen, M., Tang, C.S., Wu, D., Yuan, R., Zhou, W.: Jd. com: Transaction-level data for the 2020 msom data driven research challenge. Manufacturing & Service Operations Management26(1), 2–10 (2024)

    2024

  30. [38]

    Tropp, J.A.: An introduction to matrix concentration inequalities. No. 1 (2015)

    2015

  31. [39]

    Algorithmic game theory pp

    Vazirani, V.V.: Combinatorial algorithms for market equilibria. Algorithmic game theory pp. 103–134 (2007)

    2007

  32. [40]

    Walras, L.: Éléments d’économie politique pure: ou, Théorie de la richesse sociale. F. Rouge (1900)

    1900

  33. [41]

    Mathematical Programming111(1), 315– 348 (2008)

    Ye, Y.: A path to the arrow–debreu competitive market equilibrium. Mathematical Programming111(1), 315– 348 (2008)

    2008

  34. [42]

    arXiv preprint arXiv:2501.17996 (2025)

    Zhang, F., Boyd, S.: Solving large multicommodity network flow problems on gpus. arXiv preprint arXiv:2501.17996 (2025)

    2025 arXiv

  35. [43]

    IEEE Transactions on Pattern Analysis and Machine Intelligence (2025)

    Zhang, G., Gu, Z., Yuan, Y., Sun, D.: Hot: An efficient halpern accelerating algorithm for optimal transport problems. IEEE Transactions on Pattern Analysis and Machine Intelligence (2025)

    2025

Pith tools

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