Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read An ascending-price auction computes 4ε-approximate market equilibria for every weak gross substitute demand system.

desk verdict The WGS auction algorithm is a genuine contribution, but the NSW price-bound proof has a gap that needs fixing before the main application is credible. read the letter →

arxiv 1908.07948 v4 pith:P6KRPYAU submitted 2019-08-21 cs.GT

Jugal Garg , Edin Husić , László A. Végh This is my paper · ORCID
classification cs.GT MSC 91B5091B2668Q2590C27
keywords marketequilibriumauctionalgorithmweakgrosssubstitutesspending-restrictedNashsocialwelfarebudget-additiveSPLCutilitiesGaledemandsystemsexchange
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 shows that the weak gross substitutes (WGS) property—if some prices rise, demand for goods whose prices did not move cannot fall—is enough to make a simple auction algorithm work: prices only increase, each agent queries only its own demand information, and the process ends at a 4ε-approximate market equilibrium. The algorithm runs in O(nmT_F/$ε^{2}$ log(pmax/pmin)) calls to a FindNewPrices subroutine. The same ascending-price mechanism, adapted to spending-restricted Fisher markets, computes approximate spending-restricted equilibria for WGS demands. For budget-additive separable piecewise-linear concave utilities this yields a polynomial-time 2.404-approximation to Nash social welfare, the first polynomial-time constant-factor guarantee for that setting, where only a pseudopolynomial algorithm was known.

What carries the argument

The load-bearing mechanism is the pair of invariants (individual prices plus dominated bundles), made operational by the FindNewPrices oracle and the Outbid procedure. FindNewPrices returns new prices p̃ and a bundle y∈D_i(p̃,b_i) with y≥c(i), and p̃_j=(1+ε)p_j whenever y_j>(1+ε)c_j; in words, an agent never loses what it already bought and only pays the higher price when it wants strictly more of a good. Outbid moves goods from agents paying the lower price to agents paying the higher price, and a price increase happens exactly when a good is sold entirely at the higher price. The WGS property is what guarantees that the old owned bundle remains dominated after every price rise, which is why the entire class admits the auction.

What would settle it

Run the spending-restricted auction on the paper's Cobb-Douglas example with t_k=1 and β_k>1/b_i: no SR-equilibrium exists, so the price-bound hypothesis is essential and without it the algorithm must not terminate. For the exchange-market theorem, implement Algorithm 1 with a WGS demand system whose unique equilibrium price ratio pmax/pmin is known and very large, and check whether the number of FindNewPrices calls matches O(m/ε log(pmax/pmin)); a mismatch would refute the stated bound.

Watch

Extended reading notes

Core claim

The central claim is that an agent-driven ascending-price auction finds a 4ε-approximate equilibrium for every WGS demand system, provided one has an oracle FindNewPrices that raises an agent's individual prices and returns a demand bundle containing everything the agent already owns. Each agent i keeps individual prices p(i) between the market prices p and (1+ε)p, and buys at the higher price exactly when its desired amount exceeds what it already holds. The WGS property guarantees the oracle's output exists; the auction then transfers goods by outbidding, and multiplies a market price by (1+ε) once a good is fully sold at the higher price. For spending-restricted Fisher markets the same invariant is modified to sell exactly min{1,t_j/p_j} of each good, and for Gale demand systems—maximizing b log u(x) − p·x—FindNewPrices is implemented by convex programming; for budget-additive SPLC utilities a greedy segment algorithm implements it in O(K) time. These pieces assemble into the stated running times and into the 2.404-approximation for Nash social welfare.

Load-bearing premise

The running-time guarantee assumes a finite bound on log(pmax/pmin); absent a known price bound, the dummy-agent construction, or the hypotheses of the paper's Lemmas 5.6–5.7, the auction may need unboundedly many price increases, and for spending-restricted equilibria the equilibrium itself may not exist.

Editorial extensions

If this is right

  • With bounded price elasticities (at least −f), one call to FindNewPrices costs O(mf) demand-oracle calls, so an ε-approximate equilibrium can be found in O(nm^2 f T_D/ε^2 log(pmax/pmin)) time.
  • Auction algorithms now cover the whole WGS class, settling the open problem left by earlier algorithms that worked only for separable or uniformly separable utilities.
  • Approximate spending-restricted equilibria can be computed for WGS demands whenever a finite price bound holds, replacing the non-satiation assumption with the weaker Assumption 3.
  • For budget-additive SPLC utilities, the O(K) FindNewPrices subroutine yields an ε-SR equilibrium and, after rounding, a polynomial-time 2.404-approximation for Nash social welfare, improving on the pseudopolynomial algorithm.
  • The convex-programming implementation for Gale demand systems makes the auction applicable to concave homogeneous utilities where agents may not spend their entire budget.

Reading between the lines

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

  • If the converse suggested in the paper holds—that only WGS demands admit such auctions—then complementarities should force richer price dynamics; testing the auction on a small non-WGS economy would show where ascending prices first break.
  • The dummy-agent price-bound construction could be built into the algorithm itself, yielding bounds that depend only on n, m, ε and the data, and might remove the Vmax/tmax conditions from the SR theorems.
  • The 2.404 approximation factor comes from rounding, not from the auction; sharper rounding of approximate SR-equilibria could lower the constant without changing the algorithmic core.
  • FindNewPrices implementations for other WGS families, such as nested CES, would let the same auction serve more general production and exchange economies.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper develops an auction algorithm for computing approximate Arrow-Debreu market equilibria when all agents' demand systems satisfy the weak gross substitutes (WGS) property. The main exchange-market algorithm (Algorithm 1) assumes a FindNewPrices oracle and is shown to run in time O(nm T_F/ε^2 · log(pmax/pmin)), returning a 4ε-approximate equilibrium (Theorem 3.1). Concrete oracle implementations are given for demands with bounded price elasticity (Section 3.2) and for Gale demand systems via convex programming (Section 6). A modified auction algorithm is then developed for spending-restricted Fisher markets, with price-bound lemmas in Section 5.2. As the main application, the paper claims a polynomial-time algorithm for finding an approximate spending-restricted equilibrium for budget-additive separable piecewise-linear concave (SPLC) utilities (Theorem 7.3), and a 2.404-approximation for Nash social welfare in this setting (Theorem 7.7), improving on the previously known pseudopolynomial algorithms.

Significance. If the claims are fully established, the paper makes a substantial contribution: it largely settles the open question of whether auction-style algorithms can handle the entire class of WGS demands, and it gives the first polynomial-time constant-factor approximation for NSW with budget-additive SPLC utilities. The exchange-market algorithm is elegant, the invariant structure is convincing, and the oracle model cleanly separates the auction framework from demand-specific implementations. The paper is also careful to state its assumptions and to acknowledge the nontrivial dependence on the pmax/pmin ratio. However, two load-bearing points in the current manuscript need attention: the price-bound argument for the NSW application relies on a strict Hall condition that is never verified and can fail, and the elasticity implementation in Lemma 3.7 uses a property of the demand oracle that Definition 2.3 does not provide.

major comments (2)
  1. [Section 7.1, proof of Theorem 7.3] The claimed running time relies on the assertion 'By Lemma 5.6 and/or Lemma 5.7 we have pSR_max ≤ (1+ε)^n Dmax Vmax^{n-1}.' This is not justified for the dummy-augmented market. Lemma 5.7(ii) requires the strict Hall condition (6), ∑_{i∈S} b_i < ∑_{j∈Γ(S)} t_j for all nonempty S⊆A, but the paper never verifies this condition for the augmented market, and it can fail for valid NSW instances. For example, take n original agents with budget 1, m=n goods with D_j=1, and suppose each original agent is interested only in a distinct single good; add the dummy agent with budget ε and additive utility rate 1 on all goods. For S equal to all original agents, Γ(S)=all goods, and ∑_{i∈S} b_i = n equals ∑_{j∈Γ(S)} t_j = n, so strict inequality fails. Lemma 5.6(i) and Lemma 5.7(i) are also inapplicable because original agents are not interested in every good. Thus the bound on pSR_max, and with it the polynomial termination guarantee in Theorems 7.3 and 7.7, is not established by the argument given. This is a concrete gap in the proof of the central NSW application, not merely a restatement of the general price-ratio caveat.
  2. [Section 3.2, Lemma 3.7 and Theorem 3.2] The proof of Lemma 3.7 asserts that when the price p̃_j is increased in Algorithm 2, 'y_j may decrease only by a factor (1+ε)' and hence the invariant y_j > c^{(i)}_j is maintained. This is not a consequence of the demand oracle as defined in Definition 2.3: for the changed good j, the oracle only returns some bundle in D_i(p̃,b_i) satisfying the WGS lower bounds for goods whose price is unchanged; it does not promise the elasticity lower bound for good j. The elasticity assumption guarantees existence of some bundle with x'_j ≥ x_j/(1+ε), but the oracle is not required to return such a bundle. Consequently, invariant (A) is not proven after repeated price increases, and the running-time and correctness claims of Theorem 3.2 are unsupported as written. The proof can likely be repaired by strengthening the oracle's output specification or by modifying Algorithm 2, but this must be stated explicitly.
minor comments (4)
  1. [Theorem 7.3 proof, initialization] The text says the dummy agent's prices are initialized by setting 'each price pj to ε∑_j Dj' and assigning all goods to the dummy agent. If taken literally, the dummy's budget ε cannot pay for all goods, whose total value would be ε(∑_j D_j)^2 at those prices. This is presumably a typo for p_j = ε/(∑_j D_j) or a similar normalization; the later statement 'pmin = ε∑_j Dj' should be corrected accordingly.
  2. [Lemma 7.2, proof of FindNewPrices for SPLC] The proof claims the procedure runs in O(K) time, where K is the total number of segments, but the event selection in Stage II requires repeatedly finding the smallest α at which some good not in A reaches the threshold β. The paper does not describe the data structure or the accounting needed to achieve O(K) rather than O(Km); this should be spelled out.
  3. [Lemma 5.6, statement of part (ii)] Part (ii) says 'Assume condition (6) holds with strict inequality for all S⊆B', but the set B has not been defined; the intended statement is presumably for all nonempty S⊆A. Please clarify.
  4. [General presentation] There are a number of typographical slips, including 'age nts'' in the abstract, 'Jounal' in references [31] and [58], and 'marginal' missing in one place. These do not affect the technical content.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the auction algorithm is derived from the stated WGS and oracle assumptions, and the cited rounding results are external.

full rationale

The claimed derivation chain is not circular. The main theorem (Theorem 3.1) is conditional on explicitly stated assumptions: each demand system satisfies WGS and a FindNewPrices oracle with properties (A) and (B) is available. The invariant proof shows how these local properties imply a 4ε-approximate equilibrium; no fitted parameter is introduced, and no conclusion is used as an input. The implementations of FindNewPrices in Sections 3.2, 6, and 7.1 are each proved from their respective hypotheses (bounded elasticity, concavity/Gale structure, budget-additive SPLC KKT conditions) and do not assume the equilibrium they are used to compute. The NSW application's upper bound and rounding follow the external framework of Cole-Gkatzelis and the extension in [2,38]; [38] is published independent work, and the reduction is to budget-additive linear utilities rather than to a claim of the present paper. The paper itself flags the real limitations - SR equilibria may not exist (Cobb-Douglas example after Definition 4.2) and pSR_max can be infinite in Theorem 5.2 - so the burden in Theorem 7.3 is to establish the price bound via Lemma 5.6/5.7. Whether the hypotheses of those lemmas are always satisfied in the dummy-augmented SPLC market (the strict Hall-condition issue raised by the skeptical reader) is a correctness or completeness gap in the running-time proof, not a circular step: it does not make any derived quantity equal to an input by construction. Hence the circularity score is 0.

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

The paper is purely theoretical. The central claims rest on standard market axioms (WGS, scale invariance, non-satiation in exchange markets, monotone spending in SR markets) plus the oracle model and price-bound conditions. No ad hoc entities or fitted constants are introduced.

assumptions (8)
  • domain assumption Each agent's demand system satisfies the weak gross substitutes property (Definition 2.2): if p'≥p and b'≥b, then for x∈D(p,b) there exists y∈D(p',b') with y_j≥x_j whenever p'_j=p_j.
    Central assumption; used in all invariants and in the WGS proof for SPLC Gale demands.
  • domain assumption Scale invariance: D_i(p, b_i) = D_i(αp, αb_i) for all α>0 (Assumption 1).
    Lets the exchange algorithm initialize all prices at 1 and guarantees existence of clearing prices with all prices ≥1.
  • domain assumption Non-satiation: for every x∈D(p,b), p^T x = b (Assumption 2).
    Used in Claim 3.6 via p̃^T y = b_i to bound the increase of φ in each step.
  • domain assumption Monotone spending: for q≥p, x∈D(p,b), y∈D(q,b), q^T y ≥ p^T x (Assumption 3).
    Replaces non-satiation in the spending-restricted Fisher market analysis; claimed to hold for budget-additive utilities.
  • domain assumption A demand oracle as in Definition 2.3 is available, returning a bundle in D(p',b') that dominates the input bundle on goods with unchanged prices.
    The algorithmic model is oracle-based; the oracle exists for WGS systems by definition but is assumed to be efficiently implementable.
  • ad hoc to paper For SR markets, there exist initial prices p̄ < t and bundles x(i)∈D_i(p̄, b_i) with ∑_i x(i) ≥ 1 (Section 5, initialization).
    Required to start the modified auction; for the SPLC application the paper provides a dummy-agent construction that ensures it.
  • domain assumption Utility functions used in price-bound and Gale-demand arguments are monotone concave (and often differentiable or strictly concave) with well-defined derivatives or segment rates (Lemma 5.6, Section 6).
    Needed for KKT-based price bounds and for the convex programming implementation of FindNewPrices.
  • domain assumption For the convex-programming implementation of FindNewPrices, the utility is strictly concave so the Gale demand is unique (Section 6).
    Uniqueness is used in the contradiction argument of Lemma 6.1 to show y*≥c.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands." pith.science (2026). https://pith.science/paper/P6KRPYAU

@misc{pith2026190807948,
  author       = {Pith},
  title        = {Pith review of: Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P6KRPYAU}},
  note         = {Machine review of arXiv:1908.07948}
}
read the original abstract

We consider the Arrow--Debreu exchange market model under the assumption that the agents' demands satisfy the weak gross substitutes (WGS) property. We present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands assuming the availability of a price update oracle. We exhibit specific implementations of such an oracle for WGS demands with bounded price elasticities and for Gale demand systems. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for the NSW problem with capped additive separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.

Figures

Figures reproduced from arXiv: 1908.07948 by the authors.

Figure 1
Figure 1. Agent i’s utility for good j. Proof. Since all constraints are linear, strong duality holds for (4) as well as for (7). Let us start with (B’). First note that (ii) implies that ˜pj = qj whenever y ∗ j > cj . Moreover, from (i), (ii), and (iv) it follows that ˜pj ≤ qj . For (A’), let us start by showing y ∗ ∈ Gu (˜p, b). By the KKT conditions this is equivalent to that b∂ju(y ∗) u(y ∗) ≤ p˜j and equality holds whene… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. On the Theoretical Foundations of Data Exchange Economies

    cs.GT 2024-12 conditional novelty 7.0 of 10

    Defines reciprocal fair and core-stable data exchanges, proves exact existence for monotone continuous utilities, and places approximate computation in the complexity class CLS for submodular settings.

Reference graph

Works this paper leans on

62 extracted references · 60 canonical work pages · cited by 1 Pith paper

  1. [1]

    Anari, S

    N. Anari, S. O. Gharan, A. Saberi, and M. Singh. Nash socia l welfare, matrix permanent, and stable polynomials. In Proceedings of the 8th Innovations in Theoretical Computer Science Conf erence (ITCS) , volume 67, page 36. Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik, 2017

    work page 2017

  2. [2]

    Anari, T

    N. Anari, T. Mai, S. O. Gharan, and V. V. Vazirani. Nash soc ial welfare for indivisible items under separable, piecewi se-linear concave utilities. In Proceedings of the 29th annual ACM-SIAM Symposium on Discre te Algorithms (SODA) , pages 2274–2290. SIAM, 2018

    work page 2018

  3. [3]

    K. J. Arrow, H. D. Block, and L. Hurwicz. On the stability o f the competitive equilibrium, II. Econometrica: Journal of the Econometric Society , pages 82–109, 1959

    work page 1959

  4. [4]

    K. J. Arrow and G. Debreu. Existence of an equilibrium for a competitive economy. Econometrica: Journal of the Econometric Society, pages 265–290, 1954

    work page 1954

  5. [5]

    K. J. Arrow and L. Hurwicz. On the stability of the competi tive equilibrium, I. Econometrica: Journal of the Econometric Society, pages 522–552, 1958

    work page 1958

  6. [6]

    Euclidean distance

    K. J. Arrow and L. Hurwicz. Competitive stability under w eak gross substitutability: The “Euclidean distance” appr oach. International Economic Review , 1(1):38–49, 1960

    work page 1960

  7. [7]

    Avigdor-Elgrabli, Y

    N. Avigdor-Elgrabli, Y. Rabani, and G. Yadgar. Converge nce of tˆ atonnement in Fisher markets.arXiv preprint arXiv:1401.6637 , 2014. 31

    arXiv 2014

  8. [8]

    Barman, S

    S. Barman, S. K. Krishnamurthy, and R. Vaish. Finding fai r and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC) , pages 557–574. ACM, 2018

    work page 2018

Show all 62 references
  1. [9]

    X. Bei, J. Garg, and M. Hoefer. Ascending-price algorith ms for unknown markets. ACM Transactions on Algorithms (TALG) , 15(3):37:1–37:33, 2019

    2019

  2. [10]

    X. Bei, J. Garg, M. Hoefer, and K. Mehlhorn. Earning and u tility limits in Fisher markets. ACM Trans. Economics and Comput., 7(2):10:1–10:35, 2019

    2019

  3. [11]

    D. P. Bertsekas. A new algorithm for the assignment prob lem. Mathematical Programming, 21(1):152–171, 1981

    1981

  4. [12]

    D. P. Bertsekas. The auction algorithm for assignment a nd other network flow problems: A tutorial. Interfaces, 20(4):133–149, 1990

    1990

  5. [13]

    Birnbaum, N

    B. Birnbaum, N. Devanur, and L. Xiao. Distributed algor ithms via gradient descent for Fisher markets. In Proceedings of the 12th Conf. Electronic Commerce (EC) , pages 127–136, 2011

    2011

  6. [14]

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

    2005

  7. [15]

    Brˆ anzei, N

    S. Brˆ anzei, N. R. Devanur, and Y. Rabani. Proportional dynamics in exchange economies. CoRR, abs/1907.05037, 2019

    1907 arXiv

  8. [16]

    Brˆ anzei, R

    S. Brˆ anzei, R. Mehta, and N. Nisan. Universal growth in production economies. In Advances in Neural Information Process- ing Systems 31: Annual Conference on Neural Information Pro cessing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montr´ eal, Canada, page 1975, 2018

    2018

  9. [17]

    B. R. Chaudhury, Y. K. Cheung, J. Garg, N. Garg, M. Hoefer , and K. Mehlhorn. On fair division for indivisible items. In Proceedings of the 38th IARCS annual Conference on Foundati ons of Software Technology and Theoretical Computer Scienc e (FSTTCS), pages 25:1–25:17. Springer, 2018

    2018

  10. [18]

    X. Chen, D. Dai, Y. Du, and S. Teng. Settling the complexi ty of Arrow-Debreu equilibria in markets with additively se parable utilities. In Proceedings of the 50th Symposium Foundations of Computer S cience (FOCS) , pages 273–282. IEEE, 2009

    2009

  11. [19]

    Y. K. Cheung, R. Cole, and N. R. Devanur. Tˆ atonnement be yond gross substitutes? Gradient descent to the rescue. Games and Economic Behavior , 2019

    2019

  12. [20]

    Y. K. Cheung, R. Cole, and A. Rastogi. Tatonnement in ong oing markets of complementary goods. In Proceedings of the 2012 ACM Conference on Electronic Commerce (EC) , 2012

    2012

  13. [21]

    Y. K. Cheung, R. Cole, and Y. Tao. Dynamics of distribute d updating in Fisher markets. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, J une 18-22, 2018 , pages 351–368, 2018

    2018

  14. [22]

    Y. K. Cheung, M. Hoefer, and P. Nakhe. Tracing equilibri um in dynamic markets via distributed adaptation. In Proceedings of the 18th International Conference on Autonomous Agents a nd MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019 , pages 1225–1233, 2019

    2019

  15. [23]

    Codenotti, B

    B. Codenotti, B. McCune, and K. Varadarajan. Market equ ilibrium via the excess demand function. In Proceedings of the 37th ACM symposium on Theory of Computing (STOC) , pages 74–83. ACM, 2005

    2005

  16. [24]

    Codenotti, S

    B. Codenotti, S. Pemmaraju, and K. Varadarajan. The com putation of market equilibria. Acm Sigact News , 35(4):23–37, 2004

    2004

  17. [25]

    Codenotti, S

    B. Codenotti, S. Pemmaraju, and K. Varadarajan. On the p olynomial time computation of equilibria for certain excha nge economies. In Proceedings of the 16th annual ACM-SIAM Symposium on Discre te Algorithms (SODA) , pages 72–81. SIAM, 2005

    2005

  18. [26]

    R. Cole, N. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. V. V azirani, and S. Yazdanbod. Convex program duality, Fisher m arkets, and Nash social welfare. In Proceedings of the 2017 ACM Conference on Economics and Comp utation (EC) , pages 459–460. ACM, 2017

    2017

  19. [27]

    Cole and L

    R. Cole and L. Fleischer. Fast-converging tatonnement algorithms for one-time and ongoing market problems. In Proceedings of the 40th ACM symposium on Theory of Computing (STOC) , pages 315–324. ACM, 2008

    2008

  20. [28]

    Cole and V

    R. Cole and V. Gkatzelis. Approximating the Nash social welfare with indivisible items. SIAM J. Comput. , 47(3):1211–1236, 2018

    2018

  21. [29]

    V. P. Crawford and E. M. Knoer. Job matching with heterog eneous firms and workers. Econometrica: Journal of the Econometric Society, pages 437–450, 1981

    1981

  22. [30]

    Demange, D

    G. Demange, D. Gale, and M. Sotomayor. Multi-item aucti ons. Journal of Political Economy , 94(4):863–872, 1986

    1986

  23. [31]

    Devanur, C

    N. Devanur, C. Papadimitriou, A. Saberi, and V. Vaziran i. Market equilibrium via a primal–dual algorithm for a conv ex program. Jounal of the ACM , 55(5), 2008. 32

    2008

  24. [32]

    N. R. Devanur and V. V. Vazirani. An improved approximat ion scheme for computing Arrow-Debreu prices for the linear case. In Proceedings of the 23rd IARCS annual Conference on Foundati ons of Software Technology and Theoretical Computer Scienc e (FSTTCS), pages 149–155. Sprin...

    2003

  25. [33]

    N. R. Devanur and V. V. Vazirani. The spending constrain t model for market equilibrium: Algorithmic, existence and uniqueness results. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), volume 36, pages 519–528. ACM, 2004

    2004

  26. [34]

    Duan and K

    R. Duan and K. Mehlhorn. A combinatorial polynomial alg orithm for the linear Arrow-Debreu market. Information and Computation, 243:112–132, 2015

    2015

  27. [35]

    Eisenberg

    E. Eisenberg. Aggregation of utility functions. Management Science , 7(4):337–350, 1961

    1961

  28. [36]

    Eisenberg and D

    E. Eisenberg and D. Gale. Consensus of subjective proba bilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30(1):165–168, 1959

    1959

  29. [37]

    Fleischer, R

    L. Fleischer, R. Garg, S. Kapoor, R. Khandekar, and A. Sa beri. A fast and simple algorithm for computing market equil ibria. In Proceedings of the 4th International Workshop on Internet a nd Network Economics (WINE) , pages 19–30. Springer, 2008

    2008

  30. [38]

    J. Garg, M. Hoefer, and K. Mehlhorn. Approximating the N ash social welfare with budget-additive valuations. In Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithm s (SODA) , pages 2326–2340. SIAM, 2018

    2018

  31. [39]

    Garg and P

    J. Garg and P. McGlaughlin. Improving Nash social welfa re approximations. In Proceedings of the 28th International Joint Conferences on Artificial Intelligence (IJCAI) , 2019

    2019

  32. [40]

    J. Garg, R. Mehta, V. V. Vazirani, and S. Yazdanbod. Sett ling the complexity of Leontief and PLC exchange markets und er exact and approximate equilibria. In Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), pages 890–901. ACM, 2017

    2017

  33. [41]

    Garg and L

    J. Garg and L. A. V´ egh. A strongly polynomial algorithm for linear exchange markets. In Proceedings of the 51st Symp. Theory of Computing (STOC) , 2019

    2019

  34. [42]

    Garg and S

    R. Garg and S. Kapoor. Auction algorithms for market equ ilibrium. Mathematics of Operations Research , 31(4):714–729, 2006

    2006

  35. [43]

    Garg and S

    R. Garg and S. Kapoor. Price roll-backs and path auction s: An approximation scheme for computing the market equilib rium. In Proceedings of the 2nd International Workshop on Internet a nd Network Economics (WINE) , pages 225–238. Springer, 2006

    2006

  36. [44]

    Garg and S

    R. Garg and S. Kapoor. Market equilibrium using auction s for a class of gross-substitute utilities. In Proceedings of the 3rd International Workshop on Web and Internet Economics (WINE ), pages 356–361. Springer, 2007

    2007

  37. [45]

    R. Garg, S. Kapoor, and V. Vazirani. An auction-based ma rket equilibrium algorithm for the separable gross substit utability case. In Approximation, Randomization, and Combinatorial Optimiz ation. Algorithms and Techniques , pages 128–138. Springer, 2004

    2004

  38. [46]

    Ghiyasvand and J

    M. Ghiyasvand and J. B. Orlin. A simple approximation al gorithm for computing Arrow-Debreu prices. Operations Research, 60(5):1245–1248, 2012

    2012

  39. [47]

    Jain and K

    K. Jain and K. Varadarajan. Equilibria for economies wi th production: Constant-returns technologies and product ion planning constraints. In Proceedings of the 17th annual ACM-SIAM Symposium on Discre te Algorithms (SODA) , pages 688–697. SIAM, 2006

    2006

  40. [48]

    Kapoor, A

    S. Kapoor, A. Mehta, and V. Vazirani. An auction-based m arket equilibrium algorithm for a production model. Theoretical Computer Science , 378(2):153–164, 2007

    2007

  41. [49]

    W. J. Keller. A nested CES-type utility function and its demand and price-index functions. European Economic Review , 7:175–186, 1976

    1976

  42. [50]

    A. S. Kelso Jr and V. P. Crawford. Job matching, coalitio n formation, and gross substitutes. Econometrica: Journal of the Econometric Society , pages 1483–1504, 1982

    1982

  43. [51]

    R. P. Leme. Gross substitutability: An algorithmic sur vey. Games and Economic Behavior , 106:294–316, 2017

    2017

  44. [52]

    Mas-Colell, M

    A. Mas-Colell, M. D. Whinston, J. R. Green, et al. Microeconomic theory, volume 1. Oxford university press New York, 1995

    1995

  45. [53]

    Matsuyama and P

    K. Matsuyama and P. Ushchev. Beyond CES: Three alternat ive cases of flexible homothetic demand systems. Buffett Inst itute Global Poverty Research Lab Working Paper No. 17-109, 2017

    2017

  46. [54]

    Nesterov and V

    Y. Nesterov and V. Shikhman. Computation of Fisher–Gal e equilibrium by auction. Journal of the Operations Research Society of China , 6(3):349–389, 2018

    2018

  47. [55]

    Nisan, T

    N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic game theory . Cambridge University Press, 2007

    2007

  48. [56]

    J. B. Orlin. Improved algorithms for computing Fisher’ s market clearing prices: Computing Fisher’s market cleari ng prices. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 291–300. ACM, 2010. 33

    2010

  49. [57]

    H. Scarf. Some examples of global instability of the com petitive equilibrium. International Economic Review , 1(3):157–172, 1960

    1960

  50. [58]

    Vazirani and M

    V. Vazirani and M. Yannakakis. Market equilibrium unde r separable, piecewise-linear, concave utilities. Jounal of the ACM , 58(3):10, 2011

    2011

  51. [59]

    L. Walras. ´El´ ements d’´ economie politique pure, ou, Th´ eorie de la richesse sociale . F. Rouge, 1896

  52. [60]

    Wu and L

    F. Wu and L. Zhang. Proportional response dynamics lead s to market equilibrium. In Proceedings of the 39th Symp. Theory of Computing (STOC) , pages 354–363, 2007

    2007

  53. [61]

    Y. Ye. A path to the Arrow-Debreu competitive market equ ilibrium. Mathematical Programming, 111(1-2):315–348, 2008

    2008

  54. [62]

    L. Zhang. Proportional response dynamics in the Fisher market. Theoretical Comput. Sci. , 412(24):2691–2698, 2011. 34

    2011

Pith tools

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