| paper | d4-journals-jair-2022-0045 |
| 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: NP-hard even when \(\tau=1\) and both value and demand oracles have polynomial-time implementations. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given a finite item set \(M\) and a monotone valuation \(v:2^M\to\mathbb{Q}_{\ge 0}\) represented by the paper’s value-and-demand oracles, consider a unit-mass population of buyers all having type \(v\), with one unit of each item available per unit of population. Choose item prices \(p_j\in\mathbb{Q}_{\ge 0}\cup\{\infty\}\) and bundle masses \(x_S\ge 0\), for \(S\subseteq M\), maximizing \(\sum_{S\subseteq M}x_S p(S)\), where \(p(S)=\sum_{j\in S}p_j\), subject to \(\sum_S x_S=1\), \(\sum_{S\ni j}x_S\le 1\) for every item \(j\), and \(x_S>0\) only when \(S\) is demanded at prices \(p\). Compute an outcome attaining the maximum revenue.
A unit-mass cohort with type distribution \(\mu_v=1\), where each type is a complete valuation function; bundle masses \(x_S\) assign the cohort, common item prices determine demand, and the seller maximizes total revenue. Inventory is one unit per item per unit of population.
The mirror covers Theorem 9’s exact hardness for one-buyer, market-envy-free revenue pricing with a monotone combinatorial valuation; the paper-cited \(O(\log m)\) approximation also carries over. It leaves the multi-buyer preselection, agent-envy-free, and multi-unit results outside this mirror.
My lead is Single-Type Continuum Revenue Pricing. Picture a large cohort of customers who share the same complete valuation \(v\) over a seller’s item catalog. The type is \(v\); mass is the fraction of the cohort with that valuation. Take total mass \(1\), and scale inventory so there is one copy of each item per unit of population. A mass \(x_S\) assigned bundle \(S\) represents that fraction of customers receiving the bundle. This is plausible for a large customer segment buying digital goods or other products whose supply grows with the market.
Precisely, the instance is a finite item set \(M\) and a monotone valuation \(v:2^M\to\mathbb{Q}_{\ge 0}\), with \(v(\emptyset)=0\), given in the paper’s value-and-demand-oracle model. Choose prices \(p_j\in\mathbb{Q}_{\ge0}\cup\{\infty\}\) and masses \(x_S\ge0\) to maximize
\[
\sum_{S\subseteq M}x_S p(S),\qquad p(S)=\sum_{j\in S}p_j,
\]
subject to \(\sum_S x_S=1\), \(\sum_{S\ni j}x_S\le1\) for each item \(j\), and \(x_S>0\) only if \(S\) maximizes \(v(S)-p(S)\) over all bundles. Thus every member of the cohort receives a market envy-free bundle; the output is a price vector and a mass allocation.
The anchor is Theorem 9, proved in this paper by a reduction from 3SAT. It states that computing a maximum-revenue market envy-free outcome is NP-hard even when the market has one buyer and that buyer has a monotone combinatorial valuation. The reduction constructs the valuation so that its value and demand queries are polynomial-time computable; for a formula with \(\nu\) variables, a market-envy-free outcome reaching revenue \(\nu\) exists exactly when the formula is satisfiable. This is an exact hardness result for the underlying pricing problem, not for an encoding.
The continuous problem preserves this anchor exactly. For any fixed \(p\), every assigned bundle is demanded, so the cohort’s revenue per unit mass cannot exceed the revenue from its best-revenue demanded bundle. Conversely, assigning the whole mass to that bundle is feasible with one copy per item per capita. Therefore the continuous optimum equals the one-buyer optimum:
\[
\operatorname{OPT}_{\mathrm{cont}}(v)
=\max_p\max_{S\in D_v(p)}p(S)
=\operatorname{OPT}_{\mathrm{1buyer}}(v).
\]
The reduction’s revenue threshold carries over unchanged. I expect Class B: hardness transfers. Here the combinatorics live in the catalog and the valuation, not in the number of distinct types; the mirror has \(\tau=1\) even as the cohort grows. The paper also reports an \(O(\log m)\)-approximation for the one-buyer revenue problem from Balcan et al. (2008), so useful follow-up questions include closing that approximation gap and determining whether richer type support or buyer preselection changes the picture.
The authors should recognize this as their market-envy-free revenue-pricing problem: it retains their valuation, common item prices, demand condition, and seller objective, while aggregating identical buyers as mass. Its weakest point is also clear: proportional inventory deliberately removes competition for scarce stock, and this mirror covers Theorem 9 only—not the paper’s headline preselection results. That restriction is appropriate for this anchor: the paper itself isolates the one-buyer problem, and the continuous question asks whether its hardness persists for a high-multiplicity cohort of identical buyers.
Theorem 9 is the sole anchor, and the proposed mirror’s weakness is that its population does no computational work. With one valuation type and one copy of every item per unit of population, the capacity constraints are redundant: \(\sum_{S\ni j}x_S\le\sum_Sx_S=1\). For any fixed prices, revenue is a linear average over demanded bundles, so assigning all mass to a highest-revenue demanded bundle is optimal. The mass allocation adds no choice beyond the one-buyer problem. This is a coherent clone interpretation, but it is proportional replication of Theorem 9’s market, not a new high-multiplicity pricing problem with population-level competition.
Keeping inventory scarce gives a more substantive population model, but it changes the anchor. If a large cohort shares one valuation and some mass receives nothing, market envy-freeness requires \(\emptyset\) to be demanded. Any sold bundle must then also give utility zero, so its price must equal its value. That is a different pricing question, shaped by rationing and mass allocation, rather than the one-buyer revenue problem of Theorem 9. Allowing preselection by mass could make a worthwhile continuous analogue of buyer preselection, but it adds that population-level selection problem; it does not rescue this anchor.
This is the strongest case against the proponent’s specific construction: its continuum is formally present but computationally redundant. The case is weak as a universal argument. A one-type population is admissible under the programme’s definition, and a richer type distribution or mass-based preselection with scarce supply could be a sensible mirror. I cannot honestly conclude that no worthwhile continuous scenario exists.
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.