Answer: NP-hard even when \(\tau=1\) and both value and demand oracles have polynomial-time implementations.
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet Γ be a market with a single buyer and combinatorial monotone valuations. The pricing problem PP = (Γ, MEF, REV) is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: a list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here \(\tau=1\): buyers have total mass \(1\) and share a monotone valuation \(v:2^M\to\mathbb{Q}_{\ge0}\), with \(v(\varnothing)=0\), for \(m=|M|\) items, each of supply \(1\).
Access to \(v\) consists of a value oracle returning \(v(S)\) and a demand oracle returning any member of \(D(p)=\arg\max_{S\subseteq M}\{v(S)-p(S)\}\), where \(p(S)=\sum_{j\in S}p_j\). Prices lie in \(\mathbb{Q}_{\ge0}\cup\{\infty\}\); bundles containing an infinitely priced item have utility \(-\infty\).
Choose prices and masses \(x_S\in\mathbb{R}_{\ge0}\) satisfying \(\sum_{S\subseteq M}x_S=1\), \(\sum_{S\ni j}x_S\le1\) for every \(j\in M\), and \(x_S>0\Rightarrow S\in D(p)\). The seller may distribute mass among tied demanded bundles, including ties with the empty bundle; unsold supply imposes no price restriction.
The optimization problem is to compute an outcome maximizing \(\sum_{S:x_S>0}x_Sp(S)\). Let \(L\) bound the binary encoding lengths of the support data and valuation answers; measure computation and oracle calls in \(m,\tau,L\), accounting also for query encoding lengths.
Is this continuous revenue maximization problem solvable in polynomial time in \(m,\tau,L\) with value and demand oracle access, or is it NP-hard even when both oracles have polynomial-time implementations?
For one discrete buyer with a normalized monotone combinatorial valuation, exact revenue maximization under market envy-freeness is NP-hard even with polynomial-time value and demand oracles ([Bilò et al., 2022](https://doi.org/10.1613/jair.1.13704)). No result settling this exact continuous formulation was identified in the literature search.
The problem is NP-hard even when \(\tau=1\) and both oracles have polynomial-time implementations. The key point is that, under the stated supplies and total buyer mass, distributing mass among tied bundles cannot improve optimal revenue.
Fix an allowed price vector \(p\). The empty bundle has utility zero, so every demanded bundle has finite payment and nonnegative utility.
The supply inequalities are redundant: for every item \(j\),
\(\displaystyle \sum_{S\ni j}x_S\le \sum_{S\subseteq M}x_S=1.\)
Thus the feasible distributions at these prices are exactly the probability distributions supported on \(D(p)\).
Since \(D(p)\) is a nonempty finite set, choose a bundle \(S^\star\in D(p)\) maximizing \(p(S^\star)\). Every feasible distribution satisfies
\(\displaystyle \sum_{S:x_S>0}x_Sp(S)\le \sum_{S:x_S>0}x_Sp(S^\star)=p(S^\star).\)
Assigning mass one to \(S^\star\) attains this upper bound. It satisfies every supply constraint because each item receives allocated mass either zero or one.
Consequently, the continuous problem has exactly the same optimal value as the following discrete problem:
Choose an allowed price vector \(p\) and one bundle \(S\in D(p)\), maximizing \(p(S)\).
This equivalence respects seller selection among ties, including ties with the empty bundle. It also imposes no condition on prices of unsold items.
For completeness, the discrete optimum is attained with rational prices; allowing real prices would not increase it.
Let \(V=v(M)\). In any feasible discrete outcome \((S,p)\), comparison with the empty bundle gives
\(\displaystyle p(S)\le v(S)\le V.\)
Raise the prices of all items outside \(S\) to infinity. This preserves the payment for \(S\) and its demanded status: utilities of bundles contained in \(S\) remain unchanged, while all other bundles become unavailable.
For a fixed bundle \(S\), write \(q\) for its finite item prices. Its demanded status is equivalent to the inequalities
\(\displaystyle q_j\ge0\quad(j\in S),\qquad q(S\setminus T)\le v(S)-v(T)\quad(T\subseteq S).\)
Indeed, the second inequality is precisely the rearrangement of
\(\displaystyle v(S)-q(S)\ge v(T)-q(T).\)
These inequalities define a nonempty rational polytope. Nonemptiness follows from monotonicity: \(q=0\) is feasible. Taking \(T=\varnothing\) gives \(q(S)\le v(S)\), so nonnegativity bounds every coordinate and makes the polytope compact.
A linear objective \(q(S)\) therefore attains its maximum. A nonempty bounded rational polytope has rational vertices, and a linear objective has a maximizing vertex. Hence the maximum for this fixed bundle is attained with rational prices. The empty bundle separately yields revenue zero.
There are finitely many bundles, so their attained maxima have an attained maximum. Together with Section 1, this proves that the continuous and discrete problems have identical attained optima under the question’s rational-price convention.
The applicable known result is Theorem 9 of Bilò, Flammini, Monaco, and Moscardelli (2022): revenue maximization under market envy-freeness is NP-hard for a single buyer with normalized monotone combinatorial valuation. Their proof supplies polynomial-time value and demand oracles. For one buyer, their feasibility condition is exactly \(S\in D(p)\), and revenue is \(p(S)\). See [Theorem 9 and its proof, pp. 1803–1804](https://www.jair.org/index.php/jair/article/download/13704/26842/31702).
The reduction to the present problem preserves the item set, valuation, and both oracles. It replaces the discrete buyer by one supported type of mass one and gives every item supply one. Thus \(\tau=1\).
Both directions of the optimization correspondence have already been proved:
In particular, a continuous maximizer yields a discrete maximizer. If its positive masses are explicitly listed, choose any supported bundle with largest payment. This requires only scanning the returned support and summing item prices; a polynomial-time algorithm necessarily has polynomial-length explicit output.
The cited hardness construction uses a formula with \(n\ge4\) variables, \(m=2n\) literal items, and valuation levels \(0,1,3+\varepsilon,n\). A fixed rational choice such as \(\varepsilon=1/4\) suffices. Its oracles use clause inspection, price comparisons, and price sums. The satisfying-case revenue witness uses prices \(1\) and infinity. These are details of the [proof of Theorem 9](https://www.jair.org/index.php/jair/article/download/13704/26842/31702).
Therefore all valuation answers have binary length \(O(\log n)\); the sole support mass is the rational number one. Oracle arithmetic takes polynomial time in the formula length and the encoded query length: sums contain at most \(m\) rational prices, and exact addition and comparison have polynomial bit complexity. Infinite prices can be handled symbolically by discarding bundles containing them.
Suppose an exact algorithm for the present problem ran in polynomial time in \(m,\tau,L\), including query encoding lengths. On these constructed instances, its running time and query lengths would be polynomial in the source formula length. Simulating its polynomial-time oracles and applying the outcome correspondence would then solve the NP-hard discrete problem in polynomial time.
Hence the stated continuous formulation is NP-hard, and a polynomial-time exact algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved with a minor output-representation clarification. The equivalence between continuous and discrete optimization is correct. The cited hardness theorem applies to the valuation and oracle model in the task. No false mathematical step or blocking gap was found.
The empty bundle has utility \(0\), including when some item prices are infinite. Since every valuation is finite, a bundle containing an infinitely priced item has utility \(-\infty\) and cannot be demanded. Thus every demanded bundle has finite payment and nonnegative utility.
The supply calculation is correct:
\[
\sum_{S\ni j}x_S\le \sum_{S\subseteq M}x_S=1.
\]
It uses precisely the task’s total mass and unit supplies. Consequently, at fixed prices, feasible allocations are exactly probability distributions on the demand set.
The demand set is finite and nonempty: there are finitely many bundles, and the empty bundle remains available. These claims also cover the case where every item has infinite price.
Assessment: correct.
A maximum-payment demanded bundle exists because the demand set is finite and every demanded payment is finite. The displayed revenue inequality is a valid weighted-average bound.
Assigning mass one to that bundle preserves demand feasibility and satisfies every supply constraint. Conversely, every discrete demanded-bundle outcome gives a feasible continuous outcome with the same revenue.
These two directions establish equality of optimal values. The argument respects seller selection among ties, including empty-bundle ties, and requires no restriction on unsold-item prices.
Assessment: correct. This establishes the central continuous-to-discrete correspondence.
The bound \(p(S)\le v(S)\le v(M)\) follows from comparison with the empty bundle and monotonicity.
Raising prices outside the allocated bundle to infinity preserves its payment and demanded status: its own utility and all subset utilities remain unchanged, while competing bundles using outside items become unavailable.
For a fixed nonempty bundle, the demand inequalities are correctly rearranged:
\[
q(S\setminus T)\le v(S)-v(T).
\]
They include every available competitor after outside items are priced infinitely.
The claimed polytope properties are verified:
The invoked polytope theorem is applicable: a nonempty bounded rational polyhedron has rational vertices, and a linear objective attains a maximum at a vertex. Full dimensionality is unnecessary. The empty allocated bundle is handled separately.
Taking the maximum over finitely many bundles therefore gives an attained rational optimum. The section proves existence, without claiming that these exponentially many constraints provide a polynomial-time algorithm.
Assessment: correct.
I checked [Theorem 9, its proof, and the paper’s market-envy-freeness definition](https://www.jair.org/index.php/jair/article/download/13704/26842/31702). The cited theorem concerns one buyer with monotone combinatorial valuations; its construction is normalized and explicitly provides efficient value and demand queries. Its price domain allows nonnegative prices and infinity. Market envy-freeness requires an allocated bundle to maximize utility, without a market-clearing requirement.
The construction’s valuation levels and item count match the prover’s description. The choice \(\varepsilon=1/4\) satisfies the needed inequalities for \(n\ge4\): the intermediate value is below \(n\), and the strict clause-utility obstruction remains positive. The satisfying witness uses the stated prices.
Assessment: the external theorem is correctly identified, and its relevant hypotheses match the task.
Replacing the discrete buyer by one supported type of mass one preserves the valuation, items, and oracle access. Section 1 establishes the required objective correspondence.
For an optimal continuous outcome, concentrating its mass cannot produce revenue strictly above the continuous optimum. Therefore a largest-payment bundle in its positive support yields a discrete optimum.
Minor issue — output representation: the recovery argument assumes the positive support is explicitly listed. Polynomial running time bounds output length, but does not itself imply that an output uses an explicit support representation; a succinct representation could encode many bundles.
This is an encoding clarification under the natural interpretation of “compute an outcome,” rather than a mathematical failure.
Minimum clarification: explicitly state that outcomes are returned as a price vector and a list of positive-mass bundle entries, using finite exact encodings. The stated scanning argument is then verifiable as written.
The valuation-answer length bound is correct for the stated valuation levels. The mass-one support contributes constant encoding length.
Exact sums and comparisons of finitely encoded rational prices have polynomial bit complexity in their aggregate query length. Symbolic handling of infinite prices is consistent with the task. Accounting for clause inspection makes oracle simulation polynomial in the source formula length and query encoding length.
Thus, under the clarified output convention, the hypothetical continuous algorithm would yield a polynomial-time algorithm for the cited NP-hard discrete problem.
Assessment: correct. The prover establishes hardness of exact optimization; it does not claim NP membership or approximation hardness.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.