Pith. sign in

REVIEW 3 major objections 5 minor 23 references

Proportional Response Dynamics in Gross Substitutes Markets

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 proves that a natural generalization of proportional response — bidding in proportion to $x_j\nabla_j u(x)$ — makes prices and allocations converge to equilibrium in Fisher markets with gross-substitutes utilities, with average…

desk verdict Real Fisher-market advance with a fixable hypothesis bug and a sketchy Arrow-Debreu half. read the letter →

arxiv 2506.02852 v1 pith:AIUSEXY6 submitted 2025-06-03 cs.GT econ.TH

Yun Kuen Cheung , Richard Cole , Yixin Tao This is my paper
classification cs.GTecon.TH MSC 91B2691B50
keywords proportionalresponsegrosssubstitutesFishermarketcompetitiveequilibriumconvergenceratedynamicsArrow-Debreulazy
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 proposes a natural generalization of proportional response (PR), the distributed bidding protocol in which buyers split their money among goods in proportion to how much utility the previous round's allocation delivered per dollar. The new rule makes each buyer bid in proportion to $x_j \nabla_j u(x)$, the marginal-utility-weighted demand of the bundle she just received. The paper proves that in Fisher markets where every buyer has a gross-substitutes (GS) utility — a preference property meaning a price rise for one good never reduces demand for others — the price sequence converges to a competitive equilibrium price, the time-averaged price error decays as $O(1/T)$, and the allocation sequence converges to an equilibrium allocation. If correct, this is the first convergence guarantee for a PR-style dynamic in Fisher markets beyond the homogeneous utilities captured by the Eisenberg–Gale convex program. The same rule, in a lazy form, is also shown to converge to equilibrium allocations in Arrow–Debreu exchange markets.

What carries the argument

The engine of the proof is Lemma 12, a new inequality for GS utilities with personalized prices. If each buyer $i$ faces her own price vector $q_i$ and demands $x^D_i(q_i,e_i)$, and the aggregate demand is feasible ($\sum_i x^D_{ij}=1$ for all goods $j$), then $\sum_{ij} x^*_{ij} p^*_j \log p^*_j \le \sum_{ij} x^*_{ij} p^*_j \log q_{ij}$, where $(x^*,p^*)$ is an equilibrium. This says the equilibrium price vector minimizes a weighted log-potential over all feasible personalized price systems. Lemma 12 is derived from Lemma 13, a per-buyer inequality proved by a stepwise price-adjustment argument (Lemma 14) that moves a price vector from $q$ to $p$ one ratio-level at a time. Summing the per-round KL-divergence identity with Lemma 12 gives the monotone potential and the $O(1/T)$ rate.

What would settle it

Simulate the proposed PR dynamics on a two-buyer, two-good Fisher market with a non-homogeneous gross-substitutes utility that has a boundary equilibrium — for example a separable concave utility such as $u(x)=\log(1+x_1)+\sqrt{x_2}$ — and check whether the price sequence converges to an equilibrium price and whether the time-averaged error decays as $O(1/T)$. A single instance where prices fail to converge, or where the Lemma 12 inequality fails for a feasible set of personalized prices, would refute the paper's central claim.

Watch

Extended reading notes

Core claim

The central claim is that the update rule $b^{t+1}_{ij} = e_i \frac{x^t_{ij}\nabla_j u_i(x^t_i)}{\sum_{j'} x^t_{ij'}\nabla_{j'}u_i(x^t_i)}$ — equivalently, each buyer spends as if the personalized 'corresponding price' $q_i(x^t_i)$ were the true price — drives the market to equilibrium. For GS utilities, the paper proves Theorem 9: the price vector $p^t$ converges to an equilibrium price $p^*$, with the time-averaged price error bounded by $O(1/T)$, and Theorem 10: the allocation vector $x^t$ converges to an equilibrium allocation $x^*$. The argument works by showing that the KL divergence between equilibrium spending and current spending decreases every round, making the dynamics a descent method on a potential anchored at the equilibrium. The Arrow–Debreu result (Theorem 24) extends the allocation-convergence argument to a lazy variant in which each agent spends only a fixed fraction of her accumulated budget.

Load-bearing premise

The load-bearing premise is that the new inequality Lemma 12 holds for all gross-substitutes utilities, including boundary allocations where the corresponding price may be undefined, and that utilities are differentiable so the update rule's gradient is defined.

Editorial extensions

If this is right

  • The dynamics provides a parameter-free distributed algorithm for computing competitive equilibria in Fisher markets with GS utilities, with no step size to tune.
  • The $O(1/T)$ bound on average price error is the first quantitative convergence rate for a PR-style dynamics beyond homogeneous utilities.
  • The monotone KL potential implies the dynamics is globally stable: prices and spending never diverge from equilibrium, even when some goods have zero equilibrium allocation.
  • The lazy PR variant extends the allocation-convergence guarantee to Arrow–Debreu exchange markets with GS utilities.
  • The new update rule gives a template for defining PR for general differentiable utilities, not just CES or homogeneous ones.

Reading between the lines

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

  • If Lemma 12 is as robust as claimed, the same KL-potential argument may also yield convergence rates for asynchronous or networked variants of PR, since the descent identity does not rely on synchronous global updates.
  • The $O(1/T)$ rate is for time-averaged prices; a natural next question, which the paper leaves open, is whether linear convergence — known for CES utilities with the substitutability parameter bounded away from 1 — can be recovered for subclasses of GS utilities.
  • The rule $b_{ij} \propto x_{ij}\nabla_j u_i(x_i)$ can be read as bidding proportional to a marginal-weighted allocation; testing it on non-GS utilities such as complementary or Leontief preferences would delineate the boundary of PR convergence.
  • The boundary case in Theorem 10, handled by an epsilon-projection argument, suggests a regularization strategy that could turn the proof into a fully explicit algorithm with a stopping criterion.
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. The paper proposes a new proportional-response (PR) update rule for Fisher markets in which each buyer updates next-round bids in proportion to x_{ij}∇_j u_i(x_i), the goods received times the marginal utility. For CES and homogeneous utilities this reduces to the standard PR rule. Under assumptions of strict concavity, strict monotonicity, gross substitutes, and normal goods, the authors prove (Theorem 9) that prices converge to a competitive equilibrium and that the time-averaged price converges at rate O(1/T) in KL divergence, and (Theorem 10) that allocations converge to the equilibrium allocation. A lazy variant with savings fractions α_i is analyzed for Arrow-Debreu exchange markets, where Theorem 24 asserts convergence of allocations to equilibrium. The core Fisher-market proof introduces a personalized-price inequality (Lemma 12), proved via a price-adjustment argument (Lemmas 13–14), and uses it as a potential to monotonically decrease a KL divergence.

Significance. If the technical gaps are repaired, this is a solid and significant contribution: it appears to be the first PR-style convergence result in Fisher markets that does not require homogeneity or CES utilities, and Lemma 12 is a new inequality for gross-substitutes markets that may be reusable. The Fisher-market proof is largely self-contained, the update rule is parameter-free, and the O(1/T) bound on the KL divergence to equilibrium prices is explicit. The main caveats are that the formal assumptions do not guarantee the dynamics is defined (differentiability is missing) and that the Arrow-Debreu theorem is only sketched.

major comments (3)
  1. [Section 2, Assumption 1; Section 3, Eq. (3)] Assumption 1 requires only strict concavity and strict monotonicity, but Definition 4 and the update rule (3) use the gradient ∇u_i, so the dynamics is not defined for all utilities allowed by the theorem statements. The gap is real: separable strictly concave, strictly increasing utility functions are gross substitutes and satisfy Assumptions 1 and 2, yet they need not be differentiable. For example, u(x,y)=f(x)+f(y) with f(t)=a t−(t−1/2)^2 for t≤1/2 and f(t)=b t−(t−1/2)^2+(a−b)/2 for t≥1/2, where 0<b<a and b>1, has a kink at t=1/2; choosing symmetric initial bids gives a buyer x=1/2 in round 1, so (3) cannot be executed. Please add differentiability to Assumption 1 (the introduction already says the rule extends to differentiable utilities), or replace gradients by a fixed subgradient selection and verify that Lemmas 12–14 and Theorems 9–10 remain valid for that selection.
  2. [Section 4.2, Theorem 24] The proof of Theorem 24 is a sketch. The final sentence, 'the result follows by applying the argument in Section 3.4,' is not enough: the exchange-market KL(t) contains additional budget terms ((1−α_i)/α_i)e_i^* log(e_i^*/e_i^t), and the paper does not spell out how the strict-decrement argument of Section 3.4 transfers to this KL. In particular, the proof should explicitly show that the term S_t=Σ_{ij} b_{ij}^* log(p_j^*/(e_i^*∇_j u_i(x_i^t)/Σ_{j'} x_{ij'}^t∇_{j'}u_i(x_i^t))) is bounded above by a negative constant along a non-convergent subsequence and that the budget terms cannot offset this decrement (as the displayed inequality preceding the last sentence suggests, KL(t+1)≤KL(t)+S_t). Please provide the complete reduction.
  3. [Section 3.4, Proof of Theorem 10, Case 2] The boundary case is under-specified. The projection argument asserts q_{ij}(x^{t_k})≥\tilde q^{t_k}_{ij} for all j; this requires first showing that the lower projection bound is eventually inactive, which is only gestured at via '\tilde q^+_i>2εp^* by Lemma 18'. The application of Lemma 20 to \tilde q^{t_k} also needs the convergence x_i^D(\tilde q^{t_k},e_i)→x_i^* to be established, including when components of \tilde q^{t_k} are clipped. Because Theorem 10 is a central claim, please expand Case 2 into a complete proof with all limit interchanges justified.
minor comments (5)
  1. [Section 4, Step 3 of Lazy PR] In the budget-update step, '(1−α_j)B_i^t' should read '(1−α_i)B_i^t'.
  2. [Section 4.2, Theorem 24 proof] The definitions '\tilde B_j^*=1/α_j \tilde p_j^*' and '\tilde e_i^*=\tilde p_i^*' appear to contain index errors; they should presumably be '\tilde B_i^*=(1/α_i)\tilde e_i^*' and '\tilde e_i^*=Σ_{j∈G_i}\tilde p_j^*'.
  3. [Section 3.2, proof of Theorem 9; Introduction] The O(1/T) claim in Theorem 9 and the introduction should specify the metric: the proof bounds D_KL(p^*∥\bar p^T) by O(1/T). A statement in Euclidean or L1 distance requires an additional (standard) local strong-convexity argument, since Pinsker's inequality alone gives O(1/√T) in L1.
  4. [Section 3.4, Proof of Theorem 10, Case 1; Lemma 18] The phrase 'the LHS of equation (4) is always positive' is inaccurate; equation (4) is an identity, and the nonnegative quantity is the KL divergence appearing in it. Also, in the proof of Lemma 18, 'x_i^*' should be 'x_i' in the final sentence.
  5. [Abstract] The phrase 'empirical convergence rate' is likely intended to mean 'time-averaged (ergodic) convergence rate'; as written it may be read as an experimental claim. Please reword.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: convergence proof is self-contained, with no fitted inputs or load-bearing self-citations.

full rationale

The paper introduces a new proportional response update rule and proves convergence via a newly constructed potential-based inequality, Lemma 12, which is derived in the paper from the gross substitutes property through the price-adjustment arguments of Lemmas 13 and 14. The main theorems do not fit parameters to data, rename a known result, or import a load-bearing uniqueness theorem from the authors' prior work. Citations to earlier work, including the authors' own papers, are used only for background, for the special case of CES utilities, and for the origin of the lazy PR idea; none of these citations carries the burden of the convergence proof. The derivation chain is therefore self-contained: Theorem 9 and Theorem 10 follow from the paper's own lemmas, and Theorem 24 adapts the Fisher-market argument to the exchange setting. The only notable gap is that Assumption 1 omits differentiability while the update rule in equation (3) uses gradients; this is an assumption-statement mismatch that makes some admissible utility functions ill-defined for the dynamics, but it is a correctness gap, not a circularity, because the proof does not define its conclusion in terms of its inputs. No equation in the paper reduces by construction to a fitted quantity or to a prior self-cited result.

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

The only free parameter is the savings fraction alpha_i, which is a design choice and not fitted. The paper relies on standard domain assumptions about utilities and existence of equilibrium. No new entities are invented.

free parameters (1)
  • alpha_i (savings fraction in lazy PR) = any value in (0,1)
    Parameter of the lazy proportional response dynamics; the convergence theorem holds for all values in the open interval, so it is not fitted to data or chosen to make a specific result work.
assumptions (5)
  • domain assumption Strictly concave and strictly increasing utility functions (Assumption 1)
    Required for demand to be single-valued and for the corresponding-price construction (Lemma 2).
  • domain assumption Gross substitutes and normal goods (Assumption 2)
    The proofs of Lemmas 13, 14, and the main theorems all rely on these properties.
  • domain assumption Differentiability of utilities to define marginal utilities
    The PR rule (eq. 1) uses gradients of u_i, but Assumption 1 does not explicitly state differentiability.
  • domain assumption Market equilibrium exists in the Arrow-Debreu setting (Theorem 24)
    The theorem is conditional on existence; existence follows from standard results for GS utilities but is not proved here.
  • standard math Standard mathematical facts (KKT conditions, GS property, KL divergence, Euler's theorem)
    Used throughout the proofs without explicit proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Proportional Response Dynamics in Gross Substitutes Markets." pith.science (2026). https://pith.science/paper/AIUSEXY6

@misc{pith2026250602852,
  author       = {Pith},
  title        = {Pith review of: Proportional Response Dynamics in Gross Substitutes Markets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AIUSEXY6}},
  note         = {Machine review of arXiv:2506.02852}
}
abstract

Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various sub-families of homogeneous utilities, including linear and constant elasticity of substitution utilities. We propose a natural generalization of proportional response for gross substitutes utilities, and prove that it converges to competitive equilibria in Fisher markets. This is the first convergence result of a proportional response style dynamics in Fisher markets for utilities beyond the homogeneous utilities covered by the Eisenberg-Gale convex program. We show an empirical convergence rate of $O(1/T)$ for the prices. Furthermore, we show that the allocations of a lazy version of the generalized proportional response dynamics converge to competitive equilibria in Arrow-Debreu markets.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 12 canonical work pages

  1. [8]

    doi: 10.1145/3465456. 3467644. URLhttps://doi.org/10.1145/3465456.3467644. Xi Chen and Shang-Hua Teng. Spending is not easier than trading: on the computational equivalence of fisher and arrow-debreu equilibria. InInternational Symposium on Algorithms and Computation (ISAAC), pages 647–656. Springer,

    arXiv

  2. [12]

    URL https://doi.org/10.4230/LIPIcs.ESA.2018.18

    doi: 10.4230/LIPICS.ESA.2018.18. URL https://doi.org/10.4230/LIPIcs.ESA.2018.18. Yun Kuen Cheung, Richard Cole, and Ashish Rastogi. Tatonnement in ongoing markets of comple- mentary goods. InProceedings of the 13th ACM Conference on Electronic Commerce (EC), pages 337–354. ACM,

    doi:10.4230/lipics.esa.2018.18 2018

  3. [15]

    URLhttps: //doi.org/10.24963/ijcai.2021/16

    doi: 10.24963/ijcai.2021/16. URLhttps: //doi.org/10.24963/ijcai.2021/16. Bruno Codenotti, Sriram Pemmaraju, and Kasturi Varadarajan. The computation of market equilibria. Acm Sigact News, 35(4):23–37,

    work page doi:10.24963/ijcai.2021/16 2021

  4. [18]

    doi: 10.1145/1402946.1402987

    ISSN 0146-4833. doi: 10.1145/1402946.1402987. Juncheng Li and Pingzhong Tang. Proportional dynamics in linear fisher markets with auto-bidding: Convergence, incentives and fairness.The 20th Conference on Web and Internet Economics (WINE),

    work page arXiv

  5. [19]

    URLhttps://www.jstor.org/stable/ 1907539

    doi: 10.2307/1907539. URLhttps://www.jstor.org/stable/ 1907539. Lionel W. McKenzie. On the existence of general equilibrium for a competitive market.Econometrica, 27(1):54–71,

    work page doi:10.2307/1907539

  6. [20]

    URLhttps://www.jstor.org/stable/1907777

    doi: 10.2307/1907777. URLhttps://www.jstor.org/stable/1907777. Paul Samuelson. Foundations of economic analysis,

    work page arXiv

  7. [23]

    Stability and efficiency of personalised cultural markets

    Haiqing Zhu, Yun Kuen Cheung, and Lexing Xie. Stability and efficiency of personalised cultural markets. InProceedings of the ACM Web Conference 2023 (WWW), pages 3447–3455. ACM,

    work page 2023

  8. [1874]

    Fang Wu and Li Zhang

    (Translated as:Elements of Pure Economics.Homewood, IL: Irwin, 1954.). Fang Wu and Li Zhang. Proportional response dynamics leads to market equilibrium. InProceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 354–363. ACM,

    work page 1954

Show all 23 references
  1. [1954]

    Kenneth J

    doi: 10.2307/1907353. Kenneth J. Arrow and Leonid Hurwicz. On the stability of competitive equilibrium, i.Econometrica, 26(4):522–552,

    doi

  2. [1958]

    URLhttps://www.jstor.org/stable/1907515

    doi: 10.2307/1907515. URLhttps://www.jstor.org/stable/1907515. 15 Kenneth J. Arrow, H. D. Block, and Leonid Hurwicz. On the stability of competitive equilibrium, ii. Econometrica, 27(1):82–109,

  3. [2004]

    Market equilibrium via the excess demand function

    Bruno Codenotti, Benton McCune, and Kasturi Varadarajan. Market equilibrium via the excess demand function. InProceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 74–83. ACM, 2005a. ISBN 1-58113-960-8. URLhttp://doi.acm.org/10.1145/ 1060590.1060601...

  4. [2007]

    doi: 10.1145/1250790.1250844

    ISBN 978-1-59593-631-8. doi: 10.1145/1250790.1250844. Yinyu Ye. A path to the arrow–debreu competitive market equilibrium.Mathematical Programming, 111(1):315–348,

  5. [2008]

    doi: 10.1145/1374376.1374422

    ISBN 978-1-60558-047-0. doi: 10.1145/1374376.1374422. Richard Cole and Yixin Tao. Balancing the robustness and convergence of tatonnement.arXiv preprint arXiv:1908.00844,

    1908

  6. [2009]

    Xi Chen, Dimitris Paparas, and Mihalis Yannakakis

    doi: 10.1109/FOCS.2009.29. Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. The complexity of non-monotone markets.Journal of the ACM, 64(3):20:1–20:56,

    2009 doi

  7. [2011]

    doi: 10.1145/1993574.1993594

    ISBN 978-1-4503-0261-6. doi: 10.1145/1993574.1993594. William C Brainard and Herbert E Scarf. How to compute equilibrium prices in 1891.American Journal of Economics and Sociology, 64(1):57–83,

  8. [2012]

    doi: 10.1145/2229012.2229039

    ISBN 978-1-4503-1415-2. doi: 10.1145/2229012.2229039. Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. Tatonnement beyond gross substitutes?: Gradi- ent descent to the rescue. InProceedings of the 45th Annual ACM Symposium on Theory of Comput- ing (STOC), pages 191–200. ACM,

  9. [2013]

    doi: 10.1145/2488608.2488633

    ISBN 978-1-4503-2029-0. doi: 10.1145/2488608.2488633. 16 Yun Kuen Cheung, Richard Cole, and Yixin Tao. Dynamics of distributed updating in fisher markets. InProceedings of the 19th ACM Conference on Economics and Computation (EC), pages 351–368, Ithaca, NY, USA,

  10. [2014]

    Xiaohui Bei, Jugal Garg, and Martin Hoefer

    URLhttp://arxiv.org/abs/1401.6637. Xiaohui Bei, Jugal Garg, and Martin Hoefer. Ascending-price algorithms for unknown markets.ACM Transactions on Algorithms, 15(3):1–33, 2019a. Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Earning and utility limits in fisher mark...

    arXiv

  11. [2017]

    Yukun Cheng, Xiaotie Deng, Yuhao Li, and Xiang Yan

    doi: 10.1145/3064810. Yukun Cheng, Xiaotie Deng, Yuhao Li, and Xiang Yan. Tight incentive analysis of sybil attacks against the market equilibrium of resource exchange over general networks.Games and Economic Behavior, 148:566–610,

    doi

  12. [2018]

    Simina Brˆ anzei, Nikhil R

    URLhttps://proceedings.neurips.cc/paper/2018/hash/ 692f93be8c7a41525c0baf2076aecfb4-Abstract.html. Simina Brˆ anzei, Nikhil R. Devanur, and Yuval Rabani. Proportional dynamics in exchange economies. In P´ eter Bir´ o, Shuchi Chawla, and Federico Echenique, editors,Proceedings ...

    2018

  13. [2021]

    URLhttps://doi.org/10.1145/3505156

    doi: 10.1145/3505156.3505161. URLhttps://doi.org/10.1145/3505156. 3505161. Simina Brˆ anzei, Ruta Mehta, and Noam Nisan. Universal growth in production economies. InProceedings of the 32nd International Conference on Neural Information Processing Sys- tems (NeurIPS), page 1975,

  14. [2023]

    URLhttps://doi.org/10.1145/3543507.3583315

    doi: 10.1145/3543507.3583315. URLhttps://doi.org/10.1145/3543507.3583315. 19

  15. [2024]

    Amortized analysis of asynchronous price dynamics

    Yun Kuen Cheung and Richard Cole. Amortized analysis of asynchronous price dynamics. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors,26th Annual European Symposium on Algo- rithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 ofLIPIcs, pages 18:1–18:15....

    2018

Pith tools

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