| paper | Approximating competitive equilibrium by Nash welfare |
| authors | J. Garg, Yixin Tao, László A. Végh |
| venue | GEB 2026 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The typed continuum Fisher-market mirror is natural and the welfare inequality transfers cleanly by mass-weighting. However, Theorem 3.1 is a structural welfare bound rather than a computational result, and the proposed computation of Nash welfare is not analyzed by the paper. Therefore the mirror fails the mandatory computational-anchor gate.
fails bit a — no named computational result to mirror
The opponent correctly observes that the mass-weighted transfer is essentially a reindexing, while computing the Nash-welfare allocation or a competitive equilibrium is a newly posed computational problem.
fatal: True
The mirror covers Theorem 3.1's CE-versus-NSW welfare ratio. Mass-weighted analogues of the \(2\)-demand guarantee and \(1/2\) agentwise guarantee are also plausible, but the paper's Gale-substitute structure, generalized-network proofs, and equilibrium-computation complexity are not covered.
The strongest honest case is qualified: this paper has a very natural continuous-population mirror, but it does not contain a qualifying numbered complexity theorem. The PPAD-hardness of computing competitive equilibrium is stated only as background and attributed to Chen and Teng; it is not proved here. Likewise, the paper’s claims that Nash welfare is efficiently computable are not given as a numbered complexity result. I therefore would not present this as a fully compliant ChoCo positive case. The best substantive mirror is the following.
The lead anchor is Theorem 3.1, proved in this paper. It restates Theorem \(\ref{thm:4}\): for every Fisher market with concave utilities, every competitive equilibrium \(((x_i),p)\), and every Nash-welfare-maximizing allocation \((y_i)\),
\[ \left(\prod_i u_i(x_i)^{b_i}\right)^{1/\sum_i b_i} \ge \left(\frac{1}{\mathrm e}\right)^{1/\mathrm e} \left(\prod_i u_i(y_i)^{b_i}\right)^{1/\sum_i b_i}. \]
The factor \((1/\mathrm e)^{1/\mathrm e}>0.69\) is proved tight by Example 3.2.
A natural mirror is the following.
Continuum CE–NSW Certification. An instance consists of finitely many complete agent types \(\Theta=\{1,\ldots,\tau\}\), rational masses \(\mu_\theta\ge 0\) with \(\sum_\theta\mu_\theta=1\), divisible goods \(j\in M\) with per-capita supplies \(s_j\), budgets \(b_\theta>0\), and monotone concave utilities \(u_\theta\). A type includes the entire utility description and budget, so agents of one type are identical in every respect used by the market.
A type-level allocation is \(x=(x_\theta)_{\theta\in\Theta}\), with
\[ \sum_{\theta\in\Theta}\mu_\theta x_{\theta j}\le s_j \qquad\text{for every good }j. \]
Let \(B_\mu=\sum_\theta\mu_\theta b_\theta\). Its continuum Nash welfare is
\[ W_\mu(x)= \left( \prod_{\theta\in\Theta} u_\theta(x_\theta)^{\mu_\theta b_\theta} \right)^{1/B_\mu}. \]
A continuum competitive equilibrium is a type-level allocation \(x\) and price vector \(p\) such that every \(x_\theta\) maximizes \(u_\theta(z)\) subject to \(p\cdot z\le b_\theta\), no good is oversold, and every positively priced good is fully sold.
The task is: given a typed market and a certified continuum competitive equilibrium \((x,p)\), compute a Nash-welfare-maximizing allocation \(y\), and output the welfare ratio \(W_\mu(x)/W_\mu(y)\). With approximation parameter \(\varepsilon\), an \(\varepsilon\)-optimal \(y\) is acceptable.
This is a genuine population mirror, not merely a fractional-outcome reformulation. It describes, for example, millions of households belonging to a small number of repeated utility-and-budget classes. A rational mass vector with \(N\mu_\theta\) agents of type \(\theta\), together with \(Ns_j\) units of each good, reproduces the type-level instance exactly. The relevant regime is \(N\gg\tau\), not an election or market with one idiosyncratic type per individual. Example E.5 of the paper, with three explicitly repeated agent types and several repeated good types, is strong evidence that this is a scenario the authors themselves regard as meaningful.
Theorem 3.1 transfers exactly: replace the finite-agent sum in its proof by the mass-weighted sum \(\sum_\theta\mu_\theta b_\theta\). Thus every continuum CE satisfies
\[ W_\mu(x)\ge \left(\frac{1}{\mathrm e}\right)^{1/\mathrm e} \max_y W_\mu(y). \]
For the stated certification problem, I would expect Class A behavior. Nash welfare is a finite convex program over \(m\tau\) type-level bundles; for SPLC utilities, and more broadly for the paper’s generalized-network utilities, utility evaluation and subgradients can be obtained through finite flow or linear programs. Hence an \(\varepsilon\)-optimal continuum Nash-welfare allocation should be computable in time polynomial in the number of goods, types, utility-description length, and \(\log(1/\varepsilon)\), under standard boundedness assumptions.
The natural follow-up is more ambitious: remove the supplied equilibrium and ask the algorithm to find a continuum CE as well. That is the genuinely interesting ChoCo question. The paper does not settle whether the discrete PPAD-hardness of equilibrium computation survives when millions of agents collapse into \(\tau\) repeated types. It could dissolve through aggregation, or persist through the number of goods and utility segments. Further questions include the complexity of finding the worst-welfare CE, whether the \((1/\mathrm e)^{1/\mathrm e}\) bound remains tight for fixed \(\tau\), and whether the paper’s \(1/2\) agentwise guarantee for \(\Sigma\)-Gale-substitute utilities yields a polynomial-time continuum algorithm.
My weakest point is decisive: the lead mirror gives a natural continuous model and a clean theorem transfer, but Theorem 3.1 is an approximation guarantee, not a numbered complexity result. The paper’s actual computational claims are either informal or cited from elsewhere. Moreover, supplying the CE hides the hardest computational task. So the substantive case for a mirror is good; the formal case under ChoCo’s anchor rule is weak, and I would not claim otherwise.
The proponent’s anchor fails the programme’s decisive gate. Theorem 3.1 is a welfare inequality, not a computational result: it gives no complexity classification, algorithm, approximation scheme, or parameterized bound. Its proof uses only concavity, budgets, prices, and the log-sum inequality. Replacing the agent sum by
\[
\sum_{\theta}\mu_\theta b_\theta
\]
is therefore an immediate weighted reindexing, not a computational consequence of making the population continuous.
The proposed “certification” problem does not repair this. A competitive equilibrium is supplied, so the theorem merely certifies a ratio already bounded below by \((1/\mathrm e)^{1/\mathrm e}\). If the task is instead to compute the Nash-welfare allocation, that is a newly posed Eisenberg–Gale optimization problem, not a problem asserted by Theorem 3.1. For arbitrary concave utilities, the paper gives no finite input model at all; for SPLC or generalized-network utilities, the claimed polynomial solvability relies on standard convex or flow optimization and is not proved here. Finding the equilibrium, optimizing over equilibria, or studying fixed-type complexity could be worthwhile new research, but none is a mirror of the paper’s named result.
The proponent also overstates Example E.5 as evidence for a small repeated type space. Under the programme’s definition of type, the type-\(B\) agents indexed by \((s,t)\) have different utility maps because they refer to different \(P_s\) and \(R_{s,t}\) goods; the type-\(C\) agents indexed by \(s\) likewise differ. Calling them three “types” suppresses precisely the identity-bearing incidence structure that determines the market. Collapsing those agents would require quotienting the goods and their connectivity as well, which is a further continuization of the market structure rather than merely of the population.
The stronger possible anchors do not help. The \(2\)-demand-approximate-CE theorem and the \(1/2\) agentwise guarantee for \(\Sigma\)-Gale-substitute utilities also transfer by replacing finite sums with mass-weighted sums. They are meaningful continuous statements, but again they contain no complexity theorem. The generalized-network results supply finite optimization machinery for evaluating a fixed type’s utility; they do not establish the complexity of any continuous-population market problem.
There is one important weakness in this negative case: a Fisher market with genuinely repeated household types is perfectly sensible. One can construct a legitimate high-multiplicity regime with identical utilities and budgets, and the resulting continuum market may deserve independent algorithmic study. The cited PPAD-hardness of equilibrium computation could also motivate such a project, although it is background work by other authors, not a result of this paper.
Thus the strongest honest verdict is not that continuous Fisher markets are meaningless. It is that this paper supplies no qualifying computational anchor for them. The proposed mirror is a valid weighted restatement of its welfare theorems, followed by a new optimization problem that the paper does not analyze. Under ChoCo’s stated gate, that is not enough to make this paper a worthwhile continuous-computational mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.