| paper | d4-conf-wine-2020-0023 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\text{NP-hard}\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Lemma 5.1
statement extracted from the paper’s text layer
Given \(m\) divisible goods, \(\rho\in(0,1]\), a common homogeneity degree \(r\), and \(\tau\) valuation types with positive rational masses \(\mu_t\) summing to \(1\), compute an \(\varepsilon\)-optimal allocation and an \(\varepsilon\)-accurate dual certificate for maximizing \(\frac{1}{\rho}\sum_t\mu_t v_t(x_t)^\rho\), subject to \(x_t\ge 0\) and \(\sum_t\mu_t x_{tj}\le 1\) for every good \(j\), assuming each valuation has an efficient finite-precision gradient-oracle representation.
A finite-support continuum of consumers: each type \(t\) is a complete valuation function \(v_t\), its mass is \(\mu_t\), and \(x_t\) is its per-consumer bundle. Goods have per-capita supply \(1\); optimize the mass-weighted CES objective over mass-weighted allocations and return supporting prices from the optimal multipliers.
The opponent's strongest remaining point is that the type-weighted program follows directly from the finite-agent program, so its support-sensitive algorithm may add little beyond compression; the proponent acknowledges this possibility but does not establish a distinct computational challenge.
fatal: False
Covers CES welfare optimization and its convex-pricing equilibrium interpretation; leaves the truthful mechanism, uniqueness, and Sybil-attack results aside.
The strongest honest mirror is finite-support CES welfare optimization for a continuum of water consumers. A type \(t\) is a complete valuation function \(v_t\), including its intensity; \(\mu_t\) is the fraction of households with that valuation. For example, a water utility might model a large population using a modest number \(\tau\) of shared household-demand profiles. Each \(x_t\) is the bundle received per household of type \(t\), and supplies are measured per capita, so one unit of each good is available per unit of population.
My computational anchor is Lemma 5.1, cited from Bubeck (2015), not proved by Goel and Plaut. It states that for minimizing a convex function \(f\) over a convex set \(\mathcal X\), if a ball contains a minimizer and \(\mathcal X\) has a polynomial-time separation oracle, the ellipsoid method needs only oracle access to \(f\) and \(\nabla f\), and converges to a minimum in polynomial time. The paper uses this result in Section 5 to compute its CES allocation: it gives a separation oracle for the feasibility constraints and obtains the objective and gradient from valuation-gradient queries. This is a narrow anchor: the lemma is generic, and the paper does not give a separate numbered complexity theorem for its market-allocation problem.
The mirror problem is: given \(m\) goods, \(\rho\in(0,1]\), a common homogeneity degree \(r\), and \(\tau\) types with positive rational masses \(\mu_t\) summing to \(1\), find a CES-optimal allocation and supporting prices. Each \(v_t\) is nonzero, normalized, monotone, concave, differentiable, and homogeneous of degree \(r\). The goods and valuations have the same assumptions as in the paper; in a computational version, valuation oracles must have an efficient finite-precision representation. The allocation solves
\[ \max_{x_t\ge 0}\ \frac{1}{\rho}\sum_{t}\mu_t v_t(x_t)^\rho \qquad\text{subject to}\qquad \sum_t\mu_t x_{tj}\le 1\quad\text{for every good }j. \]
Equivalently, it maximizes \(\Phi_\mu=(\sum_t\mu_t v_t(x_t)^\rho)^{1/\rho}\). A solution is a feasible maximizing allocation and optimal multipliers \(q_j\ge0\); at finite precision, the corresponding deliverable is an \(\varepsilon\)-optimal allocation and an \(\varepsilon\)-accurate dual certificate. The supporting price schedule is
\[ p(x)=\rho r^{(\rho-1)/\rho} \left(\sum_j q_jx_j\right)^{1/\rho}. \]
The expected answer is tractable, Class A, under the stated oracle and precision assumptions. The program has \(\tau m\) allocation variables, and its type-weighted gradients can be computed with one valuation-gradient query per type per iteration. The mass factor \(\mu_t\) appears both in the objective and in the resource constraint, so it cancels from each type’s individual stationarity condition. Thus the same price rule supports each type’s demand, while the mass-weighted constraints give market clearing. This is the continuous analogue of the paper’s computation and of the equilibrium characterization in Theorem 1. Theorem 1 is central context, but I do not count it as an anchor: it characterizes welfare-maximizing allocations and equilibria rather than asserting a computational complexity class.
This seems recognizable to the authors as their problem: it preserves CES welfare, individual demand, convex pricing, and the same valuation assumptions, while making the population a distribution over types. It does not merely make outcomes divisible; goods are already divisible in their model. I would cover the CES optimization and its convex-pricing equilibrium interpretation, not the paper’s truthful-mechanism or Sybil results. The paper supplies no named hardness result to anchor a hardness-transfer question.
The main weakness is that the computational claim rests on a general oracle lemma, without a fully specified bit-complexity model for the valuation functions and numerical precision. Also, when \(\tau\) is small, the mirror largely compresses repeated agents into weighted types; the resulting optimization may be a natural extension of the paper’s existing algorithm rather than a new computational phenomenon. Further questions are whether one can state a clean finite-precision complexity bound in terms of \((m,\tau,L,\varepsilon)\), and how well a large or continuous distribution of valuation types can be approximated by finite support.
The only anchor the proponent raises, Lemma 5.1, is generic ellipsoid machinery cited from Bubeck; it is not a computational result about Goel and Plaut’s market problem. The paper’s own algorithm already applies that machinery to the agent-indexed CES program. In the proposed mirror, the program becomes
\[ \max \frac{1}{\rho}\sum_t \mu_t v_t(x_t)^\rho \quad\text{subject to}\quad \sum_t \mu_t x_{tj}\le 1. \]
For agents grouped by identical valuation, this is an aggregation of the paper’s program: symmetry lets them share a type-level allocation, and the mass factor \(\mu_t\) cancels from each type’s stationarity condition. The pricing rule and optimization method carry over directly. There is no new pricing problem, separation problem, or structural insight for the continuous model to uncover.
The best version of the mirror would encode each valuation once and multiplicities as binary rationals, then give a complexity bound in \((m,\tau,L,\varepsilon)\). That could save work when \(n\) is enormous and \(\tau\) is small. But the gain comes from compressing duplicate agents in a program the paper already solves, rather than from a new computational phenomenon created by continuization. If the question instead asks for bit complexity, it needs a finite encoding and precision model for the valuation functions; if it asks about a genuinely continuous distribution of valuations, it needs additional representation and approximation assumptions. Either extension moves beyond the paper’s stated algorithm.
So the strongest negative case is that this mirror is mathematically sensible but too immediate to justify a substantial ChoCo investigation: its tractability follows by weighting the existing convex program, and its most concrete benefit is a support-sensitive implementation of the paper’s existing method. That case is not airtight. A high-multiplicity implementation bound could be useful, and the proposed water-consumer scenario is plausible. I cannot honestly rule out every worthwhile continuous mirror here; I can only argue that this particular anchor offers limited new computational substance.
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.