{"id":"89b6731e-13a0-440d-9ce5-d5e238779ad0","arxiv_id":"1908.00844","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Under a large-market assumption on buyer spending stability, discrete tatonnement converges at a linear rate to an approximate Fisher market equilibrium for CES utilities, including linear utilities.","lead":"This paper shows that a simple price-updating rule called tatonnement, which can fail to converge for buyers with linear preferences, converges at a fast linear rate to an approximate market equilibrium when the market is large and diverse. The result gives a theoretical reason why simple price adjustment can work in big markets even when exact convergence is impossible.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 omits the requirement α>0; for parameters satisfying its stated hypotheses, α can be negative, making the claimed t=0 bound false.","rationale":"The reader's weakest assumption was Assumption 1, and that is indeed unresolved: the validation is heuristic and no computable ε is given. However, the most load-bearing defect in the paper's central statement is that Theorem 1 is false as written for an admissible parameter region. The α positivity condition is not a cosmetic detail; without it the potential-gap bound is meaningless and the t=0 inequality is contradicted. Because the proof itself needs α>0 (dividing by α, using (1-α)^t as a decaying factor, and the second contraction claim all require α>0), the theorem must state this condition explicitly. This is independent of whether Assumption 1 can be derived from market primitives. I therefore keep the reader's CONDITIONAL verdict: the main idea is sound and fixable, but the theorem statement and parameter regime need correction. I partially agree with the reader's weakest_assumption because they noted this missing condition in their rationale but selected Assumption 1 as the weakest point.","tokens_in":16266,"tokens_out":19152,"duration_ms":189296,"concrete_test":"Evaluate α at the admissible parameter point (λ,σ,ε,θ)=(1/4,4/5,1/100,1/100): the numerator is 1-0.25-2·0.25·4-0.02-0.02=-1.29, so α<0. Then check the t=0 case of Theorem 1 for any Fisher market satisfying Assumption 1 with these parameters and F(p^0)>F(p^*): the theorem's right-hand side equals F(p^0)-F(p^*) + 2λε²M/(αθ) < F(p^0)-F(p^*), contradicting the inequality. This requires no simulation; it is an algebraic refutation of the stated theorem. A second useful check is to verify that the repaired condition 1-λ-2λ·max{σ/(1-σ),1}>2ε is added to Theorem 1 and that all subsequent uses of α>0 go through.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 reduces to the one-step inequality F(p^t)-F(p^{t+1}) ≥ α(F(p^t)-F(p^*)) - 2λε²M/θ, where α = N / D, with D>0 and N = 1-λ-2λ·max{σ/(1-σ),1}-2ε-2θ. For the claimed linear rate to be meaningful, and even for the t=0 bound to hold, one needs α>0. The theorem's stated hypotheses, 0<θ<1, λσ/(1-σ)≤1, λ≤1 and Assumption 1, do not imply N>0. Example: λ=1/4, σ=4/5, ε=1/100, θ=1/100 satisfy λσ/(1-σ)=1, yet N=1-0.25-2·0.25·4-0.02-0.02=-1.29<0, so α<0. At t=0 the theorem asserts F(p^0)-F(p^*) ≤ (F(p^0)-F(p^*)) + 2λε²M/(αθ), whose right side is strictly smaller than F(p^0)-F(p^*) because α<0. Thus the inequality is false for any instance with F(p^0)>F(p^*), independent of Assumption 1. The missing condition is N>0; since θ is arbitrary, this is equivalent to requiring 1-λ-2λ·max{σ/(1-σ),1} > 2ε, a constraint not stated anywhere. This is a theorem-level flaw, though easily repaired by adding the condition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":16666,"tokens_out":11415,"duration_ms":116620,"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":[{"comment":"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":"Section 2, Theorem 1 and definition of α"},{"comment":"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":"Section 2, Remark after Assumption 1"},{"comment":"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.","section":"Section 3, proof of Theorem 1, second claim"},{"comment":"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.","section":"Abstract and Theorem 1"}],"minor_comments":[{"comment":"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":"Section 4, proof of Lemma 1"},{"comment":"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":"Section 2, Theorem 1"},{"comment":"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.","section":"Section 6, Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The alpha-positivity gap in Theorem 1 is the most serious technical defect and must be fixed by adding a hypothesis. The deeper concern for the advertised scope is the heuristic validation of Assumption 1; a revision that proves the assumption for a nontrivial family of large markets would substantially strengthen the paper. The missing bridge from potential gap to approximate equilibrium should also be addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhere 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.\n\nThe 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.\n\nThird, 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.\n\nCredit 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.\n\nBottom 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.","headline":"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.","tokens_in":17122,"tokens_out":3724,"would_cite":false,"duration_ms":36908,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B50"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["tatonnement","Fisher market","CES utilities","linear utilities","large market assumption","approximate equilibrium","linear convergence","mirror descent"],"falsifier":"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.","tokens_in":16047,"feed_emoji":"📈","tokens_out":6844,"duration_ms":61437,"temperature":0.7,"pith_summary":"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.","feed_headline":"Tatonnement converges at linear rate in large markets","feed_subtitle":"Discrete tatonnement reaches approximate equilibrium quickly for linear and CES buyer utilities in large markets.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduces the mirror-descent interpretation of tatonnement and the C(kappa) strong-convexity bound that Lemma 2 relies on.","marker":"[5]"},{"why":"supplies the dynamic-market tracking model and the per-round potential-change bounds used in Section 6.","marker":"[9]"},{"why":"established the first fast-convergence results for discrete asynchronous tatonnement in weak-gross-substitutes Fisher markets, the regime this paper extends.","marker":"[11]"},{"why":"analyzes distributed updating (including proportional response) for CES utilities, providing the rate comparisons and the convex-potential framework this work builds on.","marker":"[8]"},{"why":"shows an O(1/T) convergence rate for linear-utility Fisher markets via gradient descent, the prior best rate that this paper improves to linear in large markets.","marker":"[1]"}],"fun_headline_variants":["Tatonnement gets approximate equilibrium fast in big markets","Large markets tame tatonnement's convergence woes","Robust tatonnement: linear convergence to approximate equilibrium","Tatonnement converges to near-equilibrium in large markets","Approximate equilibrium at linear rate: tatonnement's big-market fix"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tatonnement gets approximate equilibrium fast in big markets","Large markets tame tatonnement's convergence woes","Robust tatonnement: linear convergence to approximate equilibrium","Tatonnement converges to near-equilibrium in large markets","Approximate equilibrium at linear rate: tatonnement's big-market fix"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000729,"raw_usage":{"total_tokens":3210,"prompt_tokens":838,"completion_tokens":2372,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":2291}},"tokens_in":454,"tokens_out":2372,"duration_ms":15897,"temperature":1.0,"reasoning_tokens":2291,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:32:05.458638+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Taton nement beyond gross substitutes? Gradient descent to the rescue","cited_arxiv_id":null,"evidence_quote":"introduces the mirror-descent interpretation of tatonnement and the C(kappa) strong-convexity bound that Lemma 2 relies on."},{"cited_title":"Tracin g equilibrium in dynamic markets via distributed adaptation","cited_arxiv_id":null,"evidence_quote":"supplies the dynamic-market tracking model and the per-round potential-change bounds used in Section 6."},{"cited_title":"Fast-converging tato nnement algorithms for one-time and ongoing market problems","cited_arxiv_id":null,"evidence_quote":"established the first fast-convergence results for discrete asynchronous tatonnement in weak-gross-substitutes Fisher markets, the regime this paper extends."},{"cited_title":"Dynamics of distributed updating in Fisher markets","cited_arxiv_id":null,"evidence_quote":"analyzes distributed updating (including proportional response) for CES utilities, providing the rate comparisons and the convex-potential framework this work builds on."},{"cited_title":"Devanur, and Lin Xiao","cited_arxiv_id":null,"evidence_quote":"shows an O(1/T) convergence rate for linear-utility Fisher markets via gradient descent, the prior best rate that this paper improves to linear in large markets."}],"review_version":1}