| paper | d4-journals-ai-2023-0028 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Both exact revenue maximization and exact welfare maximization are polynomial-time solvable. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), per-capita supply \(q\), integral bundle sizes \(j\in\{0,\ldots,K\}\), budgets \(B_t\), valuation schedules \(v_t(j)\), and an explicit finite rational price menu \(\mathcal P\), choose \(p\in\mathcal P\) and masses \(z_{t,j}\ge 0\). Require \(\sum_j z_{t,j}=\mu_t\), \(z_{t,j}=0\) unless \(j\) maximizes \(v_t(j)-pj\) among bundles satisfying \(pj\le B_t\), and \(\sum_{t,j}jz_{t,j}\le q\). For either the revenue objective \(p\sum_{t,j}jz_{t,j}\) or welfare objective \(\sum_{t,j}v_t(j)z_{t,j}\), compute a maximizing price and assignment.
A nonatomic population has finitely many complete procurement types, each carrying mass \(\mu_t\). Individuals receive integral bundles, while each type’s mass may be split among its demanded bundles. With uniform price \(p\), total supply \(q\), and a finite price menu, maximize revenue or welfare subject to envy-free demand and supply.
The mirror covers Theorem 14’s general-valuation revenue and welfare optimization results. It does not cover the truthful-mechanism results or the linear-valuation results; the paper’s continuous-resource variant for linear valuations is not itself a continuous-population model.
The strongest mirror I see is for Theorem 14, in Appendix C.4. Proved in this paper by reduction from Subset Sum, it says that with general multi-unit valuation schedules, computing an envy-free price and allocation that maximizes revenue is NP-hard, and computing one that maximizes social welfare is also NP-hard. The reduction sets buyer \(i\)’s budget to \(s_i\) and values any bundle of at least \(s_i\) units at \(s_i\), with lower quantities valued at zero; at price \(1\), reaching the target objective is equivalent to finding a subset summing to \(K\). The authors explicitly say this does not establish hardness for the linear-valuation case.
A plausible regime is a large procurement market: many retailers or restaurants buy the same indivisible commodity from a seller whose supply grows with the size of the market. A type records the buyer’s complete procurement profile—its budget and its value for each possible quantity. Many buyers share each type, and the number of buyers is much larger than the number of types. The supply is \(q\) units per buyer, so the seller’s total inventory scales with the population. This preserves the paper’s uniform price, hard budgets, utility-maximizing demand, envy-freeness, and revenue or welfare objectives.
I would call the mirror Continuous-Type General Envy-Free Pricing, with revenue and welfare versions. An instance has a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a rational per-capita supply \(q\), and, for each type \(t\), a budget \(B_t\) and an explicitly given valuation schedule \(v_t(j)\) for integer quantities \(j=0,\ldots,K\). Keep the paper’s discrete rational price domain, represented by an explicit finite relevant menu \(\mathcal P\).
For a price \(p\in\mathcal P\), let \(D_t(p)\) be the quantities maximizing \(v_t(j)-pj\) among those with \(pj\le B_t\). The decision is to choose \(p\) and masses \(z_{t,j}\), where \(z_{t,j}\) is the fraction of the whole society of type \(t\) assigned the integral bundle \(j\). A solution must satisfy \(\sum_j z_{t,j}=\mu_t\), \(z_{t,j}=0\) unless \(j\in D_t(p)\), and \(\sum_{t,j}jz_{t,j}\le q\). The revenue version maximizes \(p\sum_{t,j}jz_{t,j}\); the welfare version maximizes \(\sum_{t,j}v_t(j)z_{t,j}\). Fractions arise in how a continuum of same-type buyers is assigned among demanded bundles; no individual receives a fractional bundle.
I expect both versions to be Class A for this explicit price-menu formulation. At each allowed price, the demand sets are determined, and the best allocation is a linear program over the \(z_{t,j}\). Solving one LP per price gives an exact algorithm polynomial in \(|\mathcal P|\), \(\tau\), \(K\), and the input bit length. This also pinpoints why the paper’s hardness reduction may dissolve: in its Subset-Sum construction, at price \(1\), type \(i\)’s demanded quantities include \(0\) and \(s_i\). A continuum cohort can assign any fraction of its mass to \(s_i\), replacing the whole-buyer subset choice with a fractional allocation variable. The reduction’s combinatorial choice is no longer required.
The mirror covers Theorem 14’s two optimization results. It does not claim anything about the paper’s truthful mechanisms or its linear-valuation results. The question it leaves for a prover is whether price search remains tractable when the paper’s discrete price grid is represented implicitly, or when prices range over all reals; the explicit-menu version isolates the population continuization cleanly. A second useful question is how to round a continuous allocation to a large finite cohort while preserving envy-freeness and bounding the per-capita loss.
The weakest point is the scenario assumption: arbitrary valuation schedules and known budgets shared by large cohorts may fit some procurement markets better than others. Also, the reduction uses buyer-specific numbers \(s_i\), so its finite hard instances are not themselves examples with few repeated types. Still, repeated procurement profiles are a sensible high-multiplicity regime, and the mirror retains the paper’s allocation rule and objectives while making the society the continuous object.
The strongest case against Theorem 14’s mirror is that its hardness construction has little high multiplicity structure: each Subset Sum item becomes a distinct buyer type, so \(\tau=n\). A procurement model with a small number of repeated profiles is sensible, but it studies a narrower regime than the one driving this reduction. At each allowed price, assigning mass among the types’ demanded integral bundles is a linear program; with a finite relevant price menu, enumeration gives an exact algorithm. That makes this a very generic convexification, with little need for specialized continuous optimization machinery, and may limit its value as a research direction.
That is a concern about the mirror’s scope and novelty, not a fundamental flaw. Keeping the original singleton types is still a valid distributional model, and replacing each cohort’s indivisible allocation choice with a split of its mass is precisely the permitted population continuization. The paper’s continuous-resource variant is not a prior continuous-population treatment, either. I can’t honestly defeat this anchor: the negative case is weak, and the procurement cohort mirror survives the stated standard.
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.