| paper | d4-conf-aaai-2018-0891 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{R3SAT}\)-hard to approximate within \(O((\log(2+\tau))^{\epsilon_0})\) for some constant \(\epsilon_0>0\), even when \(s=B\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given \(\tau\) types with rational masses \(\mu_t\) summing to \(1\), valuation schedules \(v_t(j)\) for integral bundle sizes \(j\in\{0,\ldots,B\}\), and rational per-capita supply \(s\), choose a common item price \(p\ge0\) and mass shares \(q_{t,j}\ge0\). Require \(\sum_j q_{t,j}=1\), \(\sum_t\mu_t\sum_j j q_{t,j}\le s\), \(q_{t,j}>0\Rightarrow v_t(j)-pj\ge0\), and \(v_t(j)-pj\ge v_t(k)-pk\) whenever \(q_{t,j}>0\) and \(q_{u,k}>0\). Maximize \(p\sum_t\mu_t\sum_j j q_{t,j}\). What is the complexity, in \(B,\tau\), and input bit length \(L\), of finding an optimum; in particular, is approximation within \(O((\log\tau)^\epsilon)\) R3SAT-hard for some \(\epsilon>0\)?
Use complete valuation schedules as types, with rational population mass \(\mu_t\) per type. Each individual receives an integral bundle, while the mass of a type may be distributed across bundles; the seller chooses one item price under a rational per-capita supply limit and maximizes revenue subject to individual rationality and envy-freeness.
The mirror covers Theorem 11’s classical general-valuation item-pricing approximation-hardness result; it leaves the other pricing cases, social-graph results, and price-of-envy-freeness bounds outside this mirror.
The strongest mirror I see is for Theorem 11, proved in this paper: for some \(\epsilon>0\), approximating classical \((\mathrm{GENERAL},\mathrm{ITEM})\)-pricing within \(O(\log^\epsilon n)\) is R3SAT-hard. The authors prove this by an approximation-preserving reduction from Maximum Expanding Sequence; the hardness of the relevant separable instances of that problem is cited from Briest (2008).
My lead mirror is Continuous High-Multiplicity General-Item Pricing. It models a large commodity market in which many buyers share the same complete valuation schedule. A type \(t\) is that schedule, \(v_t(j)\), for bundles of \(j\) identical units. The input gives \(\tau\) types with positive rational population masses \(\mu_t\) summing to \(1\), a rational supply density \(s\) per unit of population, and valuations \(v_t(j)\) for integer bundle sizes \(j=0,\ldots,B\), with \(v_t(0)=0\). This fits a plausible regime of recurring procurement classes: the number of buyers is large, while the number of distinct demand schedules is moderate.
The seller chooses one item price \(p\ge 0\). Let \(q_{t,j}\) be the fraction of type \(t\)'s mass that receives a bundle of \(j\) units, with \(\sum_{j=0}^{B}q_{t,j}=1\). Thus each person receives an integral bundle; only the type-level mass can be split. Supply requires \(\sum_t\mu_t\sum_j j q_{t,j}\le s\). Individual rationality requires \(v_t(j)-pj\ge0\) whenever \(q_{t,j}>0\). Because the paper’s classical problem is the complete-social-graph case, envy-freeness requires that whenever \(q_{t,j}>0\) and \(q_{u,k}>0\), type \(t\) weakly prefers its assigned bundle: \(v_t(j)-pj\ge v_t(k)-pk\). The objective is to maximize revenue per unit of population, \(p\sum_t\mu_t\sum_j j q_{t,j}\). The question for a prover is: given this rational, finite-support instance, is finding an optimal outcome—or achieving the paper’s R3SAT-hard approximation threshold—still hard when complexity is measured in \(B,\tau\), and the input bit length?
This is close to the authors’ problem in a direct way: it retains general valuations, one non-discriminatory item price, a finite supply constraint, revenue maximization, and the classical envy condition. The continuous object is the population distribution. Normalizing total mass to one makes supply a per-capita quantity, while the allocation still gives each infinitesimal person an integer-sized bundle. It does not make outcomes, probabilities, or time continuous instead.
The reduction gives a concrete reason to expect Class B: hardness transfers. For each set \(S_y\) in its Maximum Expanding Sequence instance, the paper creates a cohort \(I_y\) of \(2^k\) buyers with the same valuation function. Those cohorts are already valuation types. Replace each by mass \(2^k/n\), and divide the market’s item supply and revenue by \(n\); the reduction’s ratios are unchanged. With the paper’s choice \(\kappa=\log m\), the cohort sizes and named-buyer count are polynomially related to the number of set-types, so the logarithmic hardness parameter has a natural support-size counterpart. Moreover, at the reduction’s normalized price \(p=1\), the selected bundles have positive surplus. Complete-graph envy then prevents serving only part of an identical cohort while leaving the rest with the empty bundle. That is evidence that the reduction’s combinatorics live in the distinct demand types, not in the ability to target named individuals.
The mirror covers only Theorem 11’s classical general-valuation, item-pricing result. It does not claim a continuous analogue for the paper’s social-graph results, its single-minded cases, bundle-pricing, or price-of-envy-freeness.
The soft spot is the adaptation of the proof’s price-normalization steps to divisible cohort masses. At prices other than \(1\), zero-surplus buyers can coexist with unserved buyers without envy, so a continuous allocation may split a type in ways that the reduction’s later extraction argument does not immediately cover. A prover would need to re-establish those steps for rational masses and show that this fractionality does not weaken the gap. If that check succeeds, the cohort structure and the reduction’s support-size scaling make the hardness-transfer case substantial. Further questions include whether the continuous problem has an exact algorithm for small \(\tau\), and how its complexity changes when the complete envy relation is replaced by a structured social relation.
The strongest case against this anchor is that the paper does not prove Theorem 11 for a continuum: the reduction builds a market of named buyers, and the proposed lift assumes that replacing each cohort by rational mass preserves the approximation gap. A continuous allocation can split a type across bundles or leave part of its mass unserved. The proof’s extraction from a stable allocation back to an expanding sequence needs to rule out those possibilities.
That is a real proof obligation, but it looks narrow. In the reduction, buyers in a cohort share a valuation function, and at price \(1\) the utility of its valued bundles decreases with bundle size. Envy-freeness therefore appears to prevent that type’s mass from being split across distinct positively valued bundle sizes. The remaining issue is a possible tie with the empty bundle at zero surplus; a strict-surplus adjustment may handle it. The cohort sizes are also polynomially related to the number of set types in the stated construction, so normalizing masses does not obviously erase the hardness parameter.
I cannot make a credible universal negative case here. The mirror describes a plausible high-multiplicity commodity market, keeps the population as the continuous object, and asks a named computational question. Theorem 11 is a particularly strong anchor because the reduction already groups buyers into identical valuation cohorts. Whether the hardness proof transfers is worth checking, but that uncertainty weakens the claimed hardness result; it does not make the continuous question unworthy.
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.