Balancing the Robustness and Convergence of Tatonnement

Richard Cole; Yixin Tao

REVIEW 4 major objections 3 minor 26 references

Balancing the Robustness and Convergence of Tatonnement

T0 review · 4 major / 3 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 Tatonnement, the classic price-update rule, converges at a linear rate to an approximate equilibrium in large Fisher markets—even with linear and CES buyer utilities—provided a spending-stability condition holds.

desk verdict A plausible extension of mirror descent to linear utilities, but the main theorem as stated is false because the contraction coefficient can be negative; the fix is a missing parameter condition. read the letter →

arxiv 1908.00844 v2 pith:QPZN2P6R submitted 2019-08-02 cs.GT

Richard Cole , Yixin Tao This is my paper · ORCID

classification cs.GT MSC 91B50

keywords tatonnementFishermarketCESutilitieslinearlargeassumptionapproximateequilibriumconvergencemirrordescent

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 show that tatonnement, the classic auctioneer-style price adjustment rule, is not inherently doomed to cycle even when buyers have linear or other CES utilities, once the market is large enough and one asks only for approximate equilibrium. The authors prove that under a spending-stability assumption, the discrete update p_j^(t+1)=p_j^t exp($\lambda$ min{z_j^t,1}) converges at a linear rate to a neighborhood of the equilibrium price vector, with the neighborhood size controlled by the large-market parameter epsilon. This matters because it reconciles the simplicity of tatonnement with fast, reliable behavior in realistic settings, including markets whose equilibrium drifts over time.

What carries the argument

The load-bearing object is the potential function F(p)=sum_j p_j + sum_i e_i log max_{x_i*p=e_i} u_i(x_i), the dual of the Eisenberg-Gale convex program, together with the multiplicative update p_j^(t+1)=p_j^t exp($\lambda$ min{z_j^t,1}) (with reserve-price floors). The analysis combines three ingredients: a progress lemma bounding the per-step decrease in F using the spending-change bound of Assumption 1; a strong-convexity-type inequality, with parameter C(kappa) inherited from prior mirror-descent analysis of tatonnement, that upper-bounds the distance to optimum by a multiple of sum_j p_j z_j Delta_j; and a price-sum invariant that keeps total prices within a bounded set M. Assumption 1 itself—that high-elasticity buyers' spending on each good changes by at most epsilon times current spending plus epsilon r_j per round—is what converts the non-Lipschitz linear-utility case into a tractable one.

What would settle it

Construct a Fisher market with many heterogeneous linear-utility buyers and unit supplies where, for some good, a price change of factor e^$\lambda$ causes a spending shift larger than epsilon times the good's total spending, and check whether tatonnement diverges or fails to reach the epsilon-ball predicted by Theorem 1; Example 1 is the degenerate two-good, one-buyer instance, but a many-buyer violation would be more informative.

Watch

Extended reading notes

Core claim

The paper's central claim is that for a Fisher market with CES buyer utilities (including linear utilities), the discrete tatonnement rule with reserve prices converges linearly to an approximate equilibrium provided Assumption 1 holds. Concretely, Theorem 1 gives F(p^t)-F(p*) <= (1-$\alpha$)^t(F($p^{0}$)-F(p*)) + 2 $\lambda$ $epsilon^{2}$ M/($\alpha$ $\theta$), with $\alpha$ a rate parameter depending on $\lambda$, $\sigma$, epsilon, and the reserve-price ratio kappa; once the objective gap falls below 4 $\lambda$ $epsilon^{2}$ M/($\alpha$ $\theta$), each subsequent step shrinks it by a constant factor (1-$\alpha$/2). The authors interpret the result as tatonnement behaving like mirror ascent on the concave dual of the Eisenberg-Gale program, whose strong convexity is restored in the large by the spending-stability assumption.

Load-bearing premise

The whole result rests on the large-market assumption that buyers with high elasticity change their spending on any one good by only a small amount, epsilon, from one round to the next; the paper gives a plausibility argument but no proof of this bound from market size or preference diversity.

Editorial extensions

If this is right

Tatonnement achieves a linear convergence rate for linear and CES utilities in large markets, not just the O(1/T) rate previously known for linear utilities.
An approximate equilibrium, rather than an exact one, is the right target in dynamic settings: Theorem 2 shows the process can track a slowly moving equilibrium.
The dependence of the approximation quality on epsilon and on the reserve-price ratio kappa gives concrete guidance on how large a market must be for fast convergence.
The result extends beyond substitute goods to complementary CES utilities (excluding Leontief), for which tatonnement was thought to be fragile.
Reserve prices, often natural in markets, double as a device to keep prices bounded away from zero, which the strong-convexity argument requires.

Reading between the lines

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

This suggests a concrete empirical check: in a large linear market, measure the maximum spending shift of high-elasticity buyers when prices move by a factor of e^lambda; the theorem predicts linear tracking whenever that shift is small, and a testable version of Assumption 1 would make the result unconditional.
The mirror-descent viewpoint hints that a similar spending-stability condition might yield linear convergence for proportional response dynamics across the same CES family, since that dynamics also optimizes a convex potential.
Since Example 1 shows that one buyer with linear utility already defeats exact convergence, the large-market assumption is not a technical convenience but the dividing line between cycling and fast tracking; markets with few buyers or highly concentrated spending may need a different mechanism.

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.

Desk Editor's Note

read the letter

Read this one. The core claim is a linear rate for discrete tatonnement with linear CES utilities under a large-market assumption, and that is genuinely new. The paper extends the Cheung-Cole-Devanur mirror descent analysis and handles the rho=1 case that previously had only O(1/T) or cycling. The proof is mostly clean, and the dynamic-market section is a nice add-on.

Where it falls down: Theorem 1 as stated is false. The parameter alpha can be negative under the hypotheses; the stress-test example (lambda=1/4, sigma=4/5, epsilon=1/100, theta=1/100) gives numerator N = 1 - 0.25 - 2*0.25*4 - 0.02 - 0.02 = -1.29, so alpha < 0, and then the t=0 bound is false. The missing condition is alpha > 0, equivalently 1 - lambda - 2*lambda*max{sigma/(1-sigma), 1} > 2*epsilon + 2*theta. This is easily fixed, but it is a theorem-level gap, not a typo: the proof uses the geometric series sum with 1-alpha, so you need 0 < alpha < 1. Add the condition and the argument goes through.

The second soft spot is the abstract's claim of convergence to approximate equilibrium. The theorem only bounds the Eisenberg-Gale dual potential gap. That is not the same as being at an approximate equilibrium unless you add a conversion argument showing prices or allocations are close. That conversion is absent.

Third, Assumption 1 is doing heavy lifting, but its validation is heuristic. The large linear market argument is plausible, but it does not deliver a concrete epsilon from a market-size primitive; it is a condition on the realized spending changes. That weakens the "large market" interpretation. Still, the paper is explicit that the result holds modulo Assumption 1, so a reader can judge the limitation.

Credit where due: the lemmas seem internally consistent, the reserve-price trick for strong convexity is neat, and the proof structure is honest. The paper does not hide the assumption or the conditional nature of the result.

Bottom line: with the alpha condition added and the abstract reworded, the theorem stands. The contribution is significant enough for a theory venue. Send it to a serious referee; they will need to check details, but the approach is sound.

Referee Report

4 major / 3 minor

Summary. This paper studies discrete tatonnement in Fisher markets with CES utilities, with special attention to linear utilities, where exact tatonnement can cycle (Example 1). The authors introduce Assumption 1, a large-market condition requiring that the spending of high-elasticity buyers on each good changes little between rounds, and prove (Theorem 1) that the price update p_j^{t+1}=p_j^t exp(λ min{z_j^t,1}) with reserve prices drives the dual Eisenberg-Gale potential F(p^t) close to F(p*) at a linear rate, with a second phase of (1−α/2) contraction once the potential gap is small. Theorem 2 extends the argument to markets whose equilibria drift slowly over time. The proof is built on a progress lemma (Lemma 1), a strong-convexity distance bound (Lemma 2), and a uniform bound on total price (Lemma 3).

Significance. If the issues below are repaired, this is a meaningful contribution: it gives a linear-rate guarantee for a simple distributed price-adjustment rule in a setting where the previous best for linear utilities was O(1/T), and it makes the dependence of the final approximation quality on the large-market parameter ε explicit. The proof structure is transparent, the main lemmas are stated cleanly, and the paper is honest that the market condition is an assumption rather than a derived consequence. However, the advertised 'approximate equilibrium' conclusion is stronger than the formal potential-gap theorem as currently written, and the main theorem omits a necessary positivity condition on α.

major comments (4)

[Section 2, Theorem 1 and definition of α] The stated hypotheses do not ensure α>0, yet the proof divides by α and uses an infinite geometric series in (1−α). With α<0 the claimed t=0 inequality is false: F(p^0)−F(p*) ≤ F(p^0)−F(p*) + 2λε²M/(αθ) has a negative additive term and cannot hold when the initial gap is positive. For instance, λ=1/4, σ=4/5, ε=θ=0.01 satisfy 0<θ<1 and λσ/(1−σ)=1, but the numerator 1−λ−2λ·max{σ/(1−σ),1}−2ε−2θ equals −1.29, so α<0. The theorem must explicitly require 0<α<1, e.g., 1−λ−2λ max{σ/(1−σ),1} > 2ε+2θ together with a bound ensuring the denominator gives α<1. The same repair is needed in Theorem 2.
[Section 2, Remark after Assumption 1] The entire robustness result rests on Assumption 1, and its validation is heuristic. In the large linear market part, the text concludes only that 'it seems reasonable' that switching spending is small; it does not derive the ε bound from a primitive condition such as the number of buyers, a diversity separation, or an income distribution, and it gives no computable ε for a concrete market. Since Example 1 shows that tatonnement can cycle forever when the assumption fails, the paper should either prove Assumption 1 for a well-specified class of large markets or present the main results as strictly conditional on a non-constructive assumption.
[Section 3, proof of Theorem 1, second claim] The proof of the second claim says 'recall that we are assuming F(p^t)−F(p*) ≤ 4λε²M/(αθ)', but the theorem's second claim assumes the reverse inequality, and the subsequent algebra requires F(p^t)−F(p*) ≥ 4λε²M/(αθ) in order to bound the additive error by (α/2)(F(p^t)−F(p*)). As printed, the proof does not establish the stated implication; this is an easily corrected sign error, but it should be fixed.
[Abstract and Theorem 1] The paper advertises convergence to an approximate equilibrium, but no approximate equilibrium is defined and no theorem translates the potential-gap bound F(p^t)−F(p*) into a market-clearing guarantee such as a bound on ‖z^t‖ or on buyers' utility loss. Lemma 2 and inequality (10) give strong convexity and hence control of price distance, but the final bridge to excess demand is missing. The authors should either add a precise definition of approximate equilibrium together with a quantitative implication from the potential gap, or state the main result explicitly as a potential-gap guarantee.

minor comments (3)

[Section 4, proof of Lemma 1] In the bound for the C term, the displayed inequality '−c_i = −ρ_i/(ρ_i−1) ≤ −σ/(σ−1) = σ/(σ−1)' has a sign error: for 0<ρ_i<σ<1 one has −ρ_i/(ρ_i−1)=ρ_i/(1−ρ_i) ≤ σ/(1−σ). The later use of max{σ/(1−σ),1} is correct, but the intermediate displayed expression is not.
[Section 2, Theorem 1] The definition of M contains an ambiguous parenthesized expression, ((e^λ−2λ)1+2λ−e^λ)/λ + λ; please clarify the intended grouping, since the proof of Lemma 3 uses this quantity.
[Section 6, Theorem 2] The statement of Theorem 2 should repeat the explicit condition 0<α<1 (or an equivalent inequality on λ, σ, ε, θ), since the same geometric-series and division-by-α steps are used as in Theorem 1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is conditional on Assumption 1 and uses independent published strong-convexity results; no fitted input is renamed as a prediction.

full rationale

The derivation chain is self-contained once Assumption 1 is granted: Assumption 1 bounds high-elasticity spending changes, Lemma 1 gives a one-step potential decrease, Lemma 2 upper-bounds the potential gap using the strong-convexity inequality (4) imported from Cheung-Cole-Devanur [5], Lemma 3 bounds total prices, and Theorem 1 assembles these into a linear-rate bound. The parameter epsilon enters only as the premise of Assumption 1, not as a value fitted to the conclusion, and the approximation error and rate are derived rather than imposed. The citations to [5,6] are to published, derived results whose assumptions do not include the present theorem, so the self-citations are real evidence, not load-bearing circularity. Two non-circular defects should be flagged. First, as stated, Theorem 1's hypotheses do not imply alpha>0 (e.g., lambda=1/4, sigma=4/5, epsilon=1/100, theta=1/100 satisfy the stated conditions but give numerator 1-lambda-2lambda*max{sigma/(1-sigma),1}-2epsilon-2theta = -1.29), so the displayed bound and geometric-series step implicitly require an added positivity condition on alpha. This makes the theorem as stated false for such parameters, but the failure is a missing hypothesis/correctness flaw, not an equivalence of the conclusion with the inputs. Second, the remark's validation of Assumption 1 in the large linear market is heuristic ('it seems reasonable that their purchasing power be much larger...'), so the range of epsilon is not proven from primitive market-size conditions; this is a support gap, but not a circularity.

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

The central result is conditional on Assumption 1, which is a new postulate in this paper. The strong convexity and demand formulas are imported from Cheung-Cole-Devanur [5]. No new physical or market entities are introduced.

free parameters (4)

ε (large market parameter)
Introduced in Assumption 1 to bound spending changes of high-elasticity buyers. The additive accuracy of the approximate equilibrium is O(ε²), but the paper provides only a heuristic validation, not a formula for ε from market primitives.
σ (CES threshold)
Separates close-to-linear buyers (ρ_i ≥ σ) who must satisfy the large-market bound. The rate and the assumption's applicability depend on σ; no guidance is given for choosing it.
κ (price ratio bound)
An upper bound on max_j p*_j/r_j is assumed in Theorem 1. Since p* is unknown, κ is a non-constructive input; C(κ) in the rate depends on it.
θ (auxiliary bound parameter)
A free parameter in Theorem 1, used in inequality (6). The theorem holds for any θ∈(0,1), but the rate and accuracy trade-off depends on it.

assumptions (5)

standard math Strong convexity bound (4): F(p*) - F(p) - ⟨∇F(p), p* - p⟩ ≥ Σ_j C(κ) x_j (p*_j - p_j)² / p_j, from Cheung-Cole-Devanur [5].
Used in Lemma 2 to upper-bound the potential gap by a multiple of Σ p z Δ. The paper cites [5] for this bound and does not prove it here.
standard math CES demand and value formulas (14)-(15) from [5].
Used in Lemmas 5-7 and Claim 10 to compute buyer utilities and best responses.
ad hoc to paper Assumption 1 (large market): for buyers with ρ_i ≥ σ, Σ_{i:ρ_i≥σ} |b^t_ij - b^{t+1}_ij| ≤ ε Σ_i b^t_ij + ε r_j, and E ≥ max_j r_j.
The central new postulate; carries the robustness result. Its validation is heuristic.
domain assumption Reserve prices r_j exist, prices are restricted to p ≥ r, and κ ≥ max_j p*_j/r_j.
Needed to keep prices bounded away from zero and to apply the strong convexity bound with finite C(κ).
standard math Eisenberg-Gale dual F(p) is finite and prices p* solve the market.
Standard Fisher market equilibrium existence and strong duality.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Balancing the Robustness and Convergence of Tatonnement." pith.science (2026). https://pith.science/paper/QPZN2P6R

@misc{pith2026190800844,
  author       = {Pith},
  title        = {Pith review of: Balancing the Robustness and Convergence of Tatonnement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QPZN2P6R}},
  note         = {Machine review of arXiv:1908.00844}
}

read the original abstract

A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify robust natural distributed algorithms that converge quickly to an equilibrium. This paper addresses a lack of robustness in existing convergence results for discrete forms of tatonnement, including the fact that it need not converge when buyers have linear utility functions. This work achieves greater robustness by seeking approximate rather than exact convergence in large market settings. More specifically, this paper shows that for Fisher markets with buyers having CES utility functions, including linear utility functions, tatonnement will converge quickly to an approximate equilibrium (i.e. at a linear rate), modulo a suitable large market assumption. The quality of the approximation is a function of the parameters of the large market assumption.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages

[1]

Devanur, and Lin Xiao

Benjamin Birnbaum, Nikhil R. Devanur, and Lin Xiao. Dist ributed algorithms via gradient descent for Fisher markets. In Proceedings of the 12th ACM conference on Electronic commerce, pages 127–136. ACM, 2011

work page 2011
[2]

Settling the complexity of Arrow- Debreu equilibria in markets with additively separable uti lities

Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng. Settling the complexity of Arrow- Debreu equilibria in markets with additively separable uti lities. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 273–282. IEEE, 2009

work page 2009
[3]

The c omplexity of non-monotone markets

Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. The c omplexity of non-monotone markets. In Proceedings of the forty-ﬁfth annual ACM symposium on Theory o f com- puting, pages 181–190. ACM, 2013

work page 2013
[4]

Amortized analysis of a synchronous price dy- namics

Yun Kuen Cheung and Richard Cole. Amortized analysis of a synchronous price dy- namics. In 26th European Symposium on Algorithms, ESA 2018 . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018

work page 2018
[5]

Taton nement beyond gross substitutes? Gradient descent to the rescue

Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. Taton nement beyond gross substitutes? Gradient descent to the rescue. In Proceedings of the forty-ﬁfth annual ACM symposium on Theory of computing , pages 191–200. ACM, 2013

work page 2013
[6]

Yun Kuen Cheung, Richard Cole, and Nikhil R. Devanur. Tat onnement beyond gross substitutes? Gradient descent to the rescue. Games and Economic Behavior , 2019

work page 2019
[7]

Taton nement in ongoing markets of complementary goods

Yun Kuen Cheung, Richard Cole, and Ashish Rastogi. Taton nement in ongoing markets of complementary goods. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 337–354. ACM, 2012

work page 2012
[8]

Dynamics of distributed updating in Fisher markets

Yun Kuen Cheung, Richard Cole, and Yixin Tao. Dynamics of distributed updating in Fisher markets. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 351–368. ACM, 2018

work page 2018

Show all 26 references

[9]

Tracin g equilibrium in dynamic markets via distributed adaptation

Yun Kuen Cheung, Martin Hoefer, and Paresh Nakhe. Tracin g equilibrium in dynamic markets via distributed adaptation. In Proceedings of the 18th International Confer- ence on Autonomous Agents and MultiAgent Systems , pages 1225–1233. International Foundation for Autonomous Ag...
[10]

Varadar ajan

Bruno Codenotti, Benton McCune, and Kasturi R. Varadar ajan. Market equilibrium via the excess demand function. In STOC, pages 74–83, 2005

2005
[11]

Fast-converging tato nnement algorithms for one-time and ongoing market problems

Richard Cole and Lisa Fleischer. Fast-converging tato nnement algorithms for one-time and ongoing market problems. In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 315–324. ACM, 2008

2008
[12]

Nikhil R. Devanur. The spending constraint model for ma rket equilibrium: algorith- mic, existence and uniqueness results. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , pages 519–528. ACM, 2004. 14

2004
[13]

A combinatorial polynomial algorithm for the linear Arrow–Debreu market

Ran Duan and Kurt Mehlhorn. A combinatorial polynomial algorithm for the linear Arrow–Debreu market. Information and Computation , 243:112–132, 2015

2015
[14]

Vazirani, and Sadra Yaz danbod

Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yaz danbod. Settling the com- plexity of Leontief and PLC exchange markets under exact and approximate equilibria. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Co mputing, pages 890–901. ACM, 2017

2017
[15]

Jugal Garg and L´ aszl´ o A. V´ egh. A strongly polynomialalgorithm for linear exchange markets. arXiv preprint arXiv:1809.06266 , 2018

2018 arXiv
[16]

Mehdi Ghiyasvand and James B. Orlin. A simple approxima tion algorithm for com- puting Arrow-Debreu prices. Operations research, 60(5):1245–1248, 2012

2012
[17]

Stability

Frank Hahn. Stability. volume 2 of Handbook of Mathematical Economics , pages 745 – 793. Elsevier, 1982

1982
[18]

Plott, and Brian W

Masayoshi Hirota, Ming Hsu, Charles R. Plott, and Brian W. Rogers. Divergence, closed cycles and convergence in Scarf environments: Exper iments in the dynamics of general equilibrium systems. Working Papers 1239, Califor nia Institute of Technology, Division of the Humanities...
[19]

A polynomial time algorithm for computing a n Arrow–Debreu market equilibrium for linear utilities

Kamal Jain. A polynomial time algorithm for computing a n Arrow–Debreu market equilibrium for linear utilities. SIAM Journal on Computing , 37(1):303–318, 2007

2007
[20]

Whinston, and Jerry R

Andreu Mas-Collel, Michael D. Whinston, and Jerry R. Gr een. Microeconomic Theory. Oxford University Press, 1995

1995
[21]

James B. Orlin. Improved algorithms for computing Fish er’s market clearing prices. In Proceedings of the forty-second ACM symposium on Theory of com puting, pages 291–300. ACM, 2010

2010
[22]

Vadim I. Shmyrev. An algorithm for ﬁnding equilibrium i n the linear exchange model with ﬁxed budgets. Journal of Applied and Industrial Mathematics , 3(4):505, 2009

2009
[23]

Equity, envy, and eﬃciency

Hal R Varian. Equity, envy, and eﬃciency. Journal of Economic Theory , 9(1):63 – 91, 1974

1974
[24]

Proportional response dynamics le ads to market equilibrium

Fang Wu and Li Zhang. Proportional response dynamics le ads to market equilibrium. In Proceedings of the thirty-ninth annual ACM symposium on Theor y of computing , pages 354–363. ACM, 2007

2007
[25]

A path to the Arrow–Debreu competitive market equilibrium

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

2008
[26]

Proportional response dynamics in the Fisher market

Li Zhang. Proportional response dynamics in the Fisher market. Theoretical Computer Science, 412(24):2691–2698, 2011. 15 A Missing Proofs Proof of Lemma 3: ∑ j pt+1 j = ∑ j pt je∆ t j = ∑ j pt j ( e∆ t j − 1 − ∆ t j ) + ∑ j pt j ( 1 + ∆ t j ) . If pt+1 j = rj, then pt j ( 1 + ...

2011

Pith tools

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

[1] [1]

Devanur, and Lin Xiao

Benjamin Birnbaum, Nikhil R. Devanur, and Lin Xiao. Dist ributed algorithms via gradient descent for Fisher markets. In Proceedings of the 12th ACM conference on Electronic commerce, pages 127–136. ACM, 2011

work page 2011

[2] [2]

Settling the complexity of Arrow- Debreu equilibria in markets with additively separable uti lities

Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng. Settling the complexity of Arrow- Debreu equilibria in markets with additively separable uti lities. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 273–282. IEEE, 2009

work page 2009

[3] [3]

The c omplexity of non-monotone markets

Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. The c omplexity of non-monotone markets. In Proceedings of the forty-ﬁfth annual ACM symposium on Theory o f com- puting, pages 181–190. ACM, 2013

work page 2013

[4] [4]

Amortized analysis of a synchronous price dy- namics

Yun Kuen Cheung and Richard Cole. Amortized analysis of a synchronous price dy- namics. In 26th European Symposium on Algorithms, ESA 2018 . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018

work page 2018

[5] [5]

Taton nement beyond gross substitutes? Gradient descent to the rescue

Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. Taton nement beyond gross substitutes? Gradient descent to the rescue. In Proceedings of the forty-ﬁfth annual ACM symposium on Theory of computing , pages 191–200. ACM, 2013

work page 2013

[6] [6]

Yun Kuen Cheung, Richard Cole, and Nikhil R. Devanur. Tat onnement beyond gross substitutes? Gradient descent to the rescue. Games and Economic Behavior , 2019

work page 2019

[7] [7]

Taton nement in ongoing markets of complementary goods

Yun Kuen Cheung, Richard Cole, and Ashish Rastogi. Taton nement in ongoing markets of complementary goods. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 337–354. ACM, 2012

work page 2012

[8] [8]

Dynamics of distributed updating in Fisher markets

Yun Kuen Cheung, Richard Cole, and Yixin Tao. Dynamics of distributed updating in Fisher markets. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 351–368. ACM, 2018

work page 2018