Answer: The continuous revenue-threshold problem is in \(\mathrm P\), with an exact algorithm using \(O(\tau\log(\tau+1)L^2)\) bit operations.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen buyers have single-minded valuations with free disposal, envy-free item pricing multi-unit (EFIP- MUL) problem is NP-hard but there exists an FPTAS.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support distribution μ over single-minded buyer types \(t=(k_t,w_t)\), with rational masses \(μ_t\) summing to \(1\), and a rational supply \(β\) of units per unit mass, choose a uniform item price \(p\ge 0\) and allocation masses \(x_{t,q}\ge 0\) to maximize revenue \(p\sum_{t,q}q x_{t,q}\). Require Σ_q x_{t,q}=μ_t\), Σ_{t,q}q x_{t,q}\le\beta\), and every quantity \(q\) assigned positive mass to maximize \(v_t(q)-pq\) over integral \(q\ge 0\), where \(v_t(q)=0\) for \(q<k_t\) and \(v_t(q)=w_t\) for \(q\ge k_t\).
A society is given by its support: the list of \(\tau\ge 1\) distinct buyer types \(t=(k_t,w_t)\) with positive binary rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each \(k_t\) is a positive binary integer and each \(w_t\) is a nonnegative binary rational. Let \(m=\max_t k_t\), and let \(L\) be the total input bit length.
Supply \(\beta\ge 0\) and a revenue threshold \(R\ge 0\) are binary rationals. Quantities are integral: \(q\in\mathbb Z_{\ge 0}\). Define \(v_t(q)=0\) for \(q<k_t\) and \(v_t(q)=w_t\) for \(q\ge k_t\).
An outcome consists of a uniform real price \(p\ge 0\) and nonnegative real allocation masses \(x_{t,q}\), satisfying \(\sum_q x_{t,q}=\mu_t\) and \(\sum_{t,q}q x_{t,q}\le\beta\).
Envy-freeness requires \(x_{t,q}>0\Rightarrow q\in\operatorname*{arg\,max}_{a\in\mathbb Z_{\ge 0}}(v_t(a)-pa)\). The seller may split a type's mass among tied maximizers. Zero allocations are permitted, buyers have no budgets, and supply may remain unsold.
Revenue is \(p\sum_{t,q}q x_{t,q}\). The decision problem asks whether an envy-free outcome has revenue at least \(R\).
Is this continuous revenue-threshold problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(\tau\), \(\log m\), and \(L\), with polynomial time measured in the binary input length.
For finitely many indivisible buyers, revenue-maximizing envy-free uniform item pricing with single-minded valuations and free disposal is \(\mathrm{NP}\)-hard and admits an FPTAS under binary quantity encoding. [Source](https://ricerca.univaq.it/retrieve/e2188bfa-63a3-f28d-e053-d805fe0ac2bb/envyfree-944-revised.pdf)
No result settling the exact distribution-over-types problem above was identified in the searches performed.
The decision problem is in \(\mathrm P\). In fact, its maximum revenue is attained and can be computed exactly in
\(O\!\left(\tau\log(\tau+1)L^2\right)\)
bit operations using elementary integer arithmetic. The dependence on the quantities is through their binary encodings, including \(\log m\); there is no enumeration of quantities up to \(m\).
The essential feature is the permission to split a type’s mass among tied maximizers.
Define the value per required unit and the full demand mass of type \(t\) by
\(r_t=w_t/k_t,\qquad d_t=k_t\mu_t.\)
Fix \(p>0\). For \(0<a<k_t\), utility is \(-pa<0\), whereas quantity zero gives utility zero. For \(a\ge k_t\), utility is \(w_t-pa\), which strictly decreases with \(a\). Therefore the only possible maximizers are zero and \(k_t\), and
\(\operatorname*{arg\,max}_{a\in\mathbb Z_{\ge0}}(v_t(a)-pa)= \begin{cases} \{k_t\},&r_t>p,\\ \{0,k_t\},&r_t=p,\\ \{0\},&r_t<p. \end{cases}\)
Consequently, define
\(A(p)=\sum_{t:r_t>p}d_t,\qquad B(p)=\sum_{t:r_t=p}d_t.\)
Every envy-free allocation at price \(p\) must allocate \(k_t\) to the entire mass of types with \(r_t>p\). Types with \(r_t=p\) may split their mass between zero and \(k_t\). Thus \(A(p)\) is mandatory demand, and \(B(p)\) is optional demand.
Claim. A positive price \(p\) is feasible exactly when \(A(p)\le\beta\). When feasible, its maximum revenue is
\(F(p)=p\min\{\beta,A(p)+B(p)\}.\)
Proof. Necessity follows because mandatory demand alone consumes \(A(p)\) units.
For sufficiency and the revenue formula, set
\(Q=\min\{\beta,A(p)+B(p)\},\qquad \delta=Q-A(p).\)
The assumed inequality \(A(p)\le\beta\) implies \(0\le\delta\le B(p)\).
List the tied types as \(t_1,\ldots,t_s\). Starting with residual \(\delta_0=\delta\), assign buying mass
\(y_i=\min\{\mu_{t_i},\delta_{i-1}/k_{t_i}\},\qquad \delta_i=\delta_{i-1}-k_{t_i}y_i.\)
Inductively,
\(\delta_i=\max\{0,\delta-\sum_{j=1}^{i}k_{t_j}\mu_{t_j}\}.\)
Since \(\delta\le B(p)\), we have \(\delta_s=0\). Allocate \(k_{t_i}\) to mass \(y_i\) and zero to its remaining mass. Allocate \(k_t\) to all strictly demanding types and zero to all other types.
Every allocated quantity maximizes the corresponding type’s utility, and total consumption is exactly \(Q\le\beta\). This proves feasibility and achieves revenue \(pQ\).
Conversely, no envy-free allocation can consume more than either \(\beta\) or \(A(p)+B(p)\). Since \(p>0\), the constructed allocation maximizes revenue. \(\square\)
This construction splits at most one type strictly between its two maximizers.
Let
\(\mathcal C=\{r_t:r_t>0\}.\)
Claim. Every feasible outcome with positive revenue is weakly dominated in revenue by a feasible outcome whose price belongs to \(\mathcal C\).
Proof. Positive revenue requires a positive price and positive consumption.
If the outcome’s price \(p\) belongs to \(\mathcal C\), the fixed-price result already gives its optimal revenue.
Otherwise no type is tied at \(p\), so the outcome’s consumption is necessarily
\(D=\sum_{t:r_t>p}d_t>0.\)
In particular, the set of types with \(r_t>p\) is nonempty. Let
\(r=\min\{r_t:r_t>p\}.\)
By this definition,
\(\{t:r_t>p\}=\{t:r_t\ge r\}.\)
At price \(r\), allocate \(k_t\) to all types in this set and zero to all other types. Types with \(r_t>r\) strictly demand \(k_t\); types with \(r_t=r\) are indifferent and may receive \(k_t\). Hence this allocation is envy-free. Its consumption remains \(D\le\beta\), and its revenue is \(rD>pD\). \(\square\)
Zero revenue is always attainable: take \(p=1+\max_t r_t\) and allocate zero to every type. This also handles instances with no positive values or with zero supply; feasibility at price zero is unnecessary.
It follows that the exact global maximum is
\(V^*=\max\!\left(\{0\}\cup \left\{ r\min\!\left(\beta,\sum_{t:r_t\ge r}d_t\right): r\in\mathcal C,\ \sum_{t:r_t>r}d_t\le\beta \right\}\right).\)
Every nonzero candidate included in this expression is attainable by Section 2, and Section 3 bounds every positive-revenue outcome by an included candidate. Thus this is a maximum, not merely a supremum.
The answer to the decision problem is “yes” exactly when \(V^*\ge R\).
Sort the types with positive \(r_t\) into groups of equal ratios, in decreasing order:
\(r_1>r_2>\cdots>r_s>0,\qquad s\le\tau.\)
Let the demand mass of group \(i\) be
\(D_i=\sum_{t:r_t=r_i}k_t\mu_t,\)
and maintain the demand from preceding groups,
\(S_i=\sum_{j<i}D_j.\)
At price \(r_i\), mandatory demand is \(S_i\), and total available demand is \(S_i+D_i\). Therefore, whenever \(S_i\le\beta\), evaluate
\(r_i\min\{\beta,S_i+D_i\}.\)
Take the maximum of these values and zero. Sorting takes \(O(\tau\log(\tau+1))\) exact comparisons, and grouping and scanning take \(O(\tau)\) arithmetic operations.
To verify that these operations have polynomial bit cost, write the input rationals as
\(\mu_t=a_t/b_t,\quad w_t=c_t/e_t,\quad \beta=u/v,\quad R=z/h,\)
with positive denominators. Use the common denominator
\(H=v\prod_t b_t.\)
Its bit length is \(O(L)\). The scaled demand of type \(t\) and scaled supply are the integers
\(C_t=k_ta_t(H/b_t),\qquad U=u(H/v).\)
The divisions are exact. All these integers have \(O(L)\) bits. In particular, normalization gives
\(\sum_t C_t=H\sum_t k_t\mu_t\le Hm,\)
so every cumulative demand has \(O(L+\log m)=O(L)\) bits.
Ratio comparisons use cross multiplication of
\(r_t=c_t/(e_tk_t).\)
For a feasible group, let \(T\) be its scaled mandatory demand and \(G\) its scaled group demand. Set
\(Q'=\min\{U,T+G\}.\)
Using any representative type \(t\) of that group, its candidate revenue is
\(\frac{c_tQ'}{e_tk_tH}.\)
Comparison with the threshold is the exact integer comparison
\(c_tQ'h\ge z e_tk_tH.\)
All operands and intermediate products have \(O(L)\) bits. Common-denominator construction, scaling, sorting, and scanning together require \(O(\tau\log(\tau+1))\) integer operations. Elementary multiplication and division on these operands cost \(O(L^2)\) bit operations each, giving the stated bound
\(O\!\left(\tau\log(\tau+1)L^2\right).\)
Equivalently, an explicit bound retaining the quantity parameter is \(O(\tau\log(\tau+1)(L+\log m)^2)\). Since \(\log m\le L\), this is polynomial in the binary input length.
The allocation construction also produces a rational optimal witness of polynomial size, with at most one partially served type.
For indivisible buyers, tied buyers must be selected as whole bundles; the cited paper identifies the resulting knapsack step and proves hardness in its Theorem 2. [Monaco, Sankowski, and Zhang, Section 3.2](https://ricerca.univaq.it/retrieve/e2188bfa-63a3-f28d-e053-d805fe0ac2bb/envyfree-944-revised.pdf)
Here, a tied type contributes any real quantity in the interval \([0,k_t\mu_t]\). Section 2 proves that these contributions fill every quantity between mandatory and total demand, eliminating that discrete selection step.
For example, take one type with \(k=2\), \(w=2\), mass \(1\), and supply \(1\). At price \(1\), allocating two units to half the mass and zero to the other half yields revenue \(1\). The corresponding single indivisible buyer cannot receive its two-unit bundle under supply \(1\) and yields no positive feasible revenue.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly resolves the continuous revenue-threshold problem in \(\mathrm P\), with the claimed binary running time. No major or minor mathematical issues were found.
The positive-price demand characterization is correct.
Because \(k_t\ge 1\), quantity zero has utility zero. For every integer quantity \(0<a<k_t\), utility is \(-pa<0\). Among quantities \(a\ge k_t\), utility \(w_t-pa\) strictly decreases when \(p>0\), so its unique maximum on that range occurs at \(k_t\).
Comparing the utilities at zero and \(k_t\) gives exactly the three stated cases according to whether \(r_t=w_t/k_t\) is greater than, equal to, or less than \(p\). This also correctly covers \(w_t=0\): at every positive price, such a type uniquely demands zero.
Consequently, \(A(p)\) is mandatory consumption, and \(B(p)\) is the maximum additional consumption available from tied types. The argument respects the distinction between integral quantities received by each buyer and real masses of buyers receiving those quantities.
The necessity of \(A(p)\le\beta\) follows directly from mandatory demand.
For sufficiency, the definitions
\(Q=\min\{\beta,A(p)+B(p)\}\) and \(\delta=Q-A(p)\) correctly imply \(0\le\delta\le B(p)\).
The greedy construction is valid:
The empty tied set also causes no difficulty: then \(B(p)=0\) and \(\delta=0\).
Every feasible allocation consumes at most both \(\beta\) and \(A(p)+B(p)\). Since \(p>0\), maximizing consumption maximizes revenue. Thus the formula
\(F(p)=p\min\{\beta,A(p)+B(p)\}\) is established.
The statement that at most one type is strictly partially served follows from the stated greedy rule: once a type absorbs a residual smaller than its full demand, that residual becomes zero.
The candidate-price argument is correct and covers every positive-revenue outcome.
Positive revenue implies positive price and positive consumption. If \(p\notin\mathcal C\), no type is tied at that positive price, so consumption must equal the stated \(D\). Since \(D>0\), the finite set of ratios above \(p\) is nonempty and has the minimum \(r\).
The identity
\(\{t:r_t>p\}=\{t:r_t\ge r\}\)
follows from the definition of that minimum. At price \(r\), the same buying types can all retain their bundles: those at ratio \(r\) become indifferent, and those above it continue strictly demanding their bundles. Consumption remains feasible, and revenue strictly increases because \(r>p\) and \(D>0\).
The zero-revenue fallback is also valid. At \(p=1+\max_t r_t\), every type uniquely demands zero, producing a feasible outcome for every nonnegative supply.
Therefore every outcome is bounded by one of finitely many attainable candidate revenues or by zero. The displayed expression for \(V^*\) is correct, and attainment is proved rather than assumed.
The grouped scan implements the optimization formula exactly. At group \(i\), \(S_i\) is mandatory demand and \(D_i\) is tied demand. The test \(S_i\le\beta\) and the evaluated revenue therefore match Section 2.
The bit-complexity justification is sound:
Comparing candidate revenues to retain the maximum likewise uses cross multiplication of the displayed rational candidates and preserves the same bit bound.
Constructing the common denominator and scaling requires \(O(\tau)\) integer operations; sorting requires \(O(\tau\log(\tau+1))\) comparisons; grouping and scanning require \(O(\tau)\) further operations. Elementary integer multiplication and division justify the claimed total
\(O(\tau\log(\tau+1)L^2)\)
bit-operation bound.
The alternative bound retaining \(\log m\) is consistent because \(\log m\le L\). No step enumerates quantities up to \(m\).
The rational-witness claim is also supported: the finite greedy construction uses rational arithmetic on the displayed input-derived quantities and assigns at most two quantities per type, with at most one strictly partial type.
The proof handles all specified boundary cases:
The algorithm depends on the listed support size \(\tau\), as requested, rather than on an implicit population size.
The cited attribution is accurate: Section 3.2 and Theorem 2 state hardness and an FPTAS for envy-free item pricing with finitely many single-minded buyers and free disposal, and discuss the remaining knapsack allocation step. [Referenced paper](https://ricerca.univaq.it/retrieve/e2188bfa-63a3-f28d-e053-d805fe0ac2bb/envyfree-944-revised.pdf)
That theorem is contextual; the continuous algorithm does not rely on transferring any external complexity result.
The illustrative example is correct under the task’s demand definition. Half the continuous mass can receive quantity two at price one, consuming one unit and earning revenue one. A single indivisible buyer requiring two units cannot generate positive feasible revenue with supply one.
None. The output establishes the claimed exact polynomial-time result.
⟨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.