On the Convergence of Tâtonnement for Linear Fisher Markets

There is a credible mirror, and the strongest one is an exact high-multiplicity compression of the paper’s linear Fisher market. It would be Class A: the continuous population makes the aggregate computation independent of the number of cloned buyers, while the paper’s convex-duality argument supplies the convergence theorem. This is not a claim that the paper discovered a new population limit; its novelty is that its tâtonnement result can be stated and analyzed directly on a distribution of buyer types.

My lead anchor is Theorem 1, together with Corollary 1, both proved in this paper. Theorem 1 proves linear convergence of additive tâtonnement to a stepsize-dependent neighborhood of the equilibrium price vector. Corollary 1 gives the explicit \(O\!\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)\) iteration bound for obtaining an \(\epsilon\)-accurate price vector.

The natural regime is a large advertising or resource marketplace. There are many buyer units—campaigns, recurring buyer-days, or standardized advertiser cohorts—but only a small number \(m\) of item classes, such as impression or inventory classes. Buyers in the same cohort have the same budget density and the same value vector over item classes. A complete type is therefore \(t=(b_t,v_t)\), where \(b_t>0\) is budget per unit population mass and \(v_t\in\mathbb{Q}_{\ge0}^m\) is the normalized valuation vector. A society is a rational mass vector \(\mu\in\mathbb{Q}_{\ge0}^{\tau}\) with \(\sum_t\mu_t=1\), where \(\tau\ll n\). The supply of every item is one per unit population mass; equivalently, one may scale both supplies and budgets with the population size.

The important point is exact clone consistency. Let \(\beta_t=\mu_t b_t\) be the total budget mass of type \(t\). Since linear demand is homogeneous in budget, the aggregate demand of \(\mu_t\) identical buyers with budget \(b_t\) is exactly the demand of one compressed buyer with budget \(\beta_t\). If \(\mu_t=a_t/A\), clearing denominators produces \(a_t\) identical clones, with the usual homogeneous normalization of supplies and budgets. Thus this is not an arbitrary fractional relaxation: it is the high-multiplicity form of the original market.

I would call the resulting problem Continuum-LFM Tâtonnement:

Given \(m\), a finite type set \(T\), rational masses \(\mu_t\), budgets \(b_t\), valuations \(v_t\), an initial price vector \(p^0\), a stepsize \(\eta\), and an accuracy parameter \(\epsilon\), define the type-\(t\) demand set at prices \(p\) by \(D_t(p)=\arg\max\{v_t\cdot x:p\cdot x\le b_t,\ x\ge0\}\). At iteration \(k\), choose \(x_t^k\in D_t(p^k)\) for every type, form the mass-weighted excess demand \(z_j^k=\sum_t\mu_t x_{tj}^k-1\), and update \(p_j^{k+1}=p_j^k+\eta z_j^k\). The task is to output a price vector \(p^K\), together with a type-level demand selection, such that \(p^K\) is within \(\epsilon\) of the unique equilibrium price vector \(p^*\), or equivalently yields an \(\epsilon\)-approximate market-clearing allocation.

The compressed dual objective is \(\Phi_\mu(p)=\sum_jp_j-\sum_t\beta_t\log\!\left(\min_{j:v_{tj}>0}\frac{p_j}{v_{tj}}\right)\). It is precisely the paper’s Eisenberg–Gale dual after replacing the buyer list by weighted types. The paper’s Lemma 1 supplies the positive price lower bound, and Lemma 3 supplies quadratic growth. With \(\beta_{\min}=\min_{t:\mu_t>0}\beta_t\), the corresponding initialization uses the paper’s lower-bound vector \(\tilde p\), with \(\tilde p_j=\frac{\beta_{\min}}{4m}\max_t\frac{v_{tj}}{\lVert v_t\rVert_\infty}\), and a sufficiently small \(\eta\). Theorem 1 and Corollary 1 then apply to the compressed market with \(\tau\) buyers rather than \(n\).

I expect this problem to be tractable. Each iteration requires only the \(\tau\) type demands and a mass-weighted sum, so the population size disappears from the running time. The complexity should be polynomial in \(m\), \(\tau\), the input bit length, and the requested accuracy, with the paper’s stated \(O\!\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)\) iteration guarantee. This is a genuine population continuization: the divisible goods are inherited from the paper, but the new continuous object is the buyer society \(\mu\).

A second, independently defensible anchor is Theorem 2 and Corollary 2, also proved here, for quasi-linear Fisher markets. The QLFM version is especially recognizable because the paper connects it to first-price pacing equilibria in online advertising.

The corresponding problem, Continuum-QLFM Tâtonnement, has the same input \((T,\mu,b,v)\), but type \(t\)'s demand is \(D_t^q(p)=\arg\max\{(v_t-p)\cdot x:p\cdot x\le b_t,\ x\ge0\}\); the subtraction by \(p\) represents the buyer’s outside value for unspent money. The mass-weighted update remains \(p_j^{k+1}=p_j^k+\eta(\sum_t\mu_t x_{tj}^k-1)\). The task is again to compute an \(\epsilon\)-approximate equilibrium price and allocation. Its dual is \(\Phi_\mu^q(p)=\sum_jp_j-\sum_t\beta_t\log\!\left(\min\{\min_{j:v_{tj}>0}p_j/v_{tj},1\}\right)\). Theorem 2 gives the linear convergence bound, and Corollary 2 gives the same \(O\!\left(\frac{1}{\epsilon}\log\frac{1}{\epsilon}\right)\)-type iteration guarantee under a sufficiently small stepsize. This is also Class A, by the same finite-support convex-optimization argument.

These mirrors cover only the paper’s LFM and QLFM convergence results: Theorem 1, Corollary 1, Theorem 2, and Corollary 2, with Lemmas 1 and 3 as supporting structural results. I would not claim to mirror the numerical experiments, the cited convergence results for other market models, or the fixed-stepsize cycling example as a separate anchor. The cycling example does, however, generate a useful further question: whether adaptive stepsizes give exact convergence for the continuum market rather than convergence to a stepsize-dependent neighborhood.

The main open questions are whether one can select the stepsize without using unknown equilibrium quantities, whether the dependence on rare types through \(\beta_{\min}\) can be improved, how to round a continuum equilibrium back to a finite market with controlled error, and whether the same theory works for a genuinely continuous valuation distribution accessed through an oracle rather than a finite type list.

The weakest point is the regime itself. Real advertisers often have idiosyncratic budgets and valuation vectors; if every such distinction is included in the type, then \(\tau\) approaches \(n\) and the high-multiplicity gain vanishes. The mirror is therefore strongest for recurring campaign templates or standardized buyer cohorts, not for arbitrary named advertisers. A second limitation is that the original Fisher equilibrium problem is already convex and tractable, so this mirror does not demonstrate a dramatic discrete-to-continuous hardness collapse. Its honest contribution is narrower: it turns the paper’s large-population aggregate dynamics into an exact finite-type population problem, with convergence and computation depending on the number of economically meaningful types rather than on the number of individual buyers.