Answer: Both exact revenue maximization and exact welfare maximization are polynomial-time solvable.
Theorem 14 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a multi-unit market with general valuations, it is NP-hard to compute a revenue-maximizing or social welfare-maximizing envy-free price and allocation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Input also includes an integer bundle cap \(K\geq1\), per-capita supply \(q\in\mathbb Q_{>0}\), budgets \(B_t\in\mathbb Q_{>0}\), explicitly tabulated values \(v_t(j)\in\mathbb Q_{\geq0}\) for \(j\in\{0,\ldots,K\}\), with \(v_t(0)=0\), and a nonempty explicit finite menu \(\mathcal P\subseteq\mathbb Q_{\geq0}\). No linearity or concavity is assumed.
For a uniform unit price \(p\), define \(D_t(p)=\arg\max\{v_t(j)-pj:j\in\{0,\ldots,K\},\ pj\leq B_t\}\).
An envy-free assignment consists of masses \(z_{t,j}\geq0\) satisfying \(\sum_jz_{t,j}=\mu_t\), \(z_{t,j}=0\) whenever \(j\notin D_t(p)\), and \(\sum_{t,j}jz_{t,j}\leq q\). Mass may split among tied demanded bundles; unsold supply is permitted.
For each objective separately, optimize over \(p\in\mathcal P\) and such assignments: revenue \(p\sum_{t,j}jz_{t,j}\), or welfare \(\sum_{t,j}v_t(j)z_{t,j}\). Report infeasibility if no menu price admits an assignment.
Is exact revenue maximization polynomial-time solvable or NP-hard, and is exact welfare maximization polynomial-time solvable or NP-hard? State running times in \(m:=K\), \(\tau\), \(|\mathcal P|\), and the total binary input length \(L\).
Discrete envy-free price-and-allocation optimization with general valuation schedules is stated to be NP-hard for both objectives in [Brânzei et al.](https://arxiv.org/pdf/1602.08719).
A related model with finitely many buyers, linear valuations, and divisible goods has a polynomial-time revenue algorithm in [Brânzei et al.](https://arxiv.org/pdf/1602.08719); it does not address the distributional problem above. No result settling this exact distributional problem was located.
Both exact revenue maximization and exact welfare maximization are polynomial-time solvable. With \(m:=K\), both optimal values and corresponding assignments can be computed together using
\(O\!\left(|\mathcal P|\tau(m+1)\right)\)
exact arithmetic operations. A conservative bound with schoolbook integer arithmetic is
\(O\!\left(|\mathcal P|\tau(m+1)L^2\right)\)
bit operations.
The proof uses the permission to split a type’s mass among tied demanded bundles. It requires no linearity, monotonicity, or concavity of the valuation schedules.
Fix \(p\in\mathcal P\). Define the maximum affordable utility of type \(t\) by
\(u_t(p):=\max\{v_t(j)-pj:0\leq j\leq m,\ pj\leq B_t\}.\)
The feasible set in this maximum is nonempty because \(j=0\) is affordable. Consequently, \(D_t(p)\) is nonempty. Define
\(a_t(p):=\min D_t(p),\qquad b_t(p):=\max D_t(p),\)
and the aggregate quantities
\(Q_-(p):=\sum_{t\in T}\mu_t a_t(p),\qquad Q_+(p):=\sum_{t\in T}\mu_t b_t(p).\)
For any assignment satisfying the type-mass and demand constraints, let
\(Q(z):=\sum_{t,j}jz_{t,j}.\)
Every bundle receiving positive mass for type \(t\) lies between \(a_t(p)\) and \(b_t(p)\). Since its assigned masses sum to \(\mu_t\),
\(\mu_t a_t(p)\leq\sum_jjz_{t,j}\leq\mu_t b_t(p).\)
Summing over types gives
\(Q_-(p)\leq Q(z)\leq Q_+(p).\)
Conversely, every quantity in this interval is attainable. To prove this, take any \(s\in[Q_-(p),Q_+(p)]\).
If \(Q_-(p)=Q_+(p)\), allocating all type-\(t\) mass to \(a_t(p)\) attains \(s=Q_-(p)\).
Otherwise, define
\(\theta:=\dfrac{s-Q_-(p)}{Q_+(p)-Q_-(p)}\in[0,1].\)
For each type with \(a_t(p)<b_t(p)\), set
\(z_{t,a_t(p)}=(1-\theta)\mu_t,\qquad z_{t,b_t(p)}=\theta\mu_t,\)
and set its other masses to zero. For a type with \(a_t(p)=b_t(p)\), put all its mass on that bundle. Both endpoints belong to the demand set, and the resulting quantity is
\(Q(z)=(1-\theta)Q_-(p)+\theta Q_+(p)=s.\)
Thus the attainable quantities, before imposing supply, are exactly \([Q_-(p),Q_+(p)]\), even when individual demand sets have gaps.
It follows that
\(p\text{ admits an envy-free assignment}\quad\Longleftrightarrow\quad Q_-(p)\leq q.\)
Necessity follows from the lower bound on \(Q(z)\). Sufficiency follows by assigning every type its smallest demanded bundle.
For a feasible price, the largest attainable quantity respecting supply is therefore
\(S(p):=\min\{q,Q_+(p)\}.\)
Indeed, feasibility ensures \(Q_-(p)\leq S(p)\leq Q_+(p)\), so the construction above attains \(S(p)\).
For revenue, every feasible assignment has value \(pQ(z)\). Because \(p\geq0\), this is maximized by attaining \(S(p)\). Hence
\(R^*(p)=pS(p).\)
For welfare, the defining property of demand gives, for every \(j\in D_t(p)\),
\(v_t(j)-pj=u_t(p),\qquad\text{hence}\qquad v_t(j)=u_t(p)+pj.\)
An envy-free assignment puts mass only on such bundles. Therefore its welfare satisfies
\(\displaystyle W(z)=\sum_{t,j}v_t(j)z_{t,j} =\sum_tu_t(p)\sum_jz_{t,j}+p\sum_{t,j}jz_{t,j} =\sum_t\mu_tu_t(p)+pQ(z).\)
Define
\(U(p):=\sum_t\mu_tu_t(p).\)
At the fixed price, \(U(p)\) is independent of the assignment. Since \(p\geq0\), welfare is also maximized by attaining \(S(p)\), giving
\(W^*(p)=U(p)+pS(p).\)
These formulas include \(p=0\): revenue is zero, and every feasible assignment has welfare \(U(0)\).
Thus one assignment attaining \(S(p)\) simultaneously maximizes both objectives at a fixed price, although the globally optimal menu prices may differ.
The algorithm processes every \(p\in\mathcal P\):
If every price is discarded, report infeasibility. Otherwise, independently select a feasible price maximizing each objective. Reconstruct its assignment using the interpolation in Section 1 with \(s=S(p)\).
The preceding proofs show that every discarded price is infeasible, every retained price has the computed optimum, and every reconstructed assignment attains it. Exhausting the explicit finite menu therefore yields both global optima.
Each price requires \(O(\tau(m+1))\) arithmetic operations and comparisons. Computing aggregates and reconstructing an assignment each require \(O(\tau)\) additional operations. The total arithmetic-operation bound is consequently
\(O\!\left(|\mathcal P|\tau(m+1)\right).\)
To justify polynomial bit complexity explicitly, represent each input rational by its binary numerator and positive denominator. Let \(D\) be the product of all input denominators. Their total encoded length is at most \(L\), so \(D\) has \(O(L)\) bits.
For every input rational \(r\), write \(\widehat r:=Dr\), an integer. At a fixed price, compute
\(\widehat u_t(p)=\max\{\widehat v_t(j)-j\widehat p:j\widehat p\leq\widehat B_t,\ 0\leq j\leq m\}.\)
This integer equals \(Du_t(p)\). Similarly, compute
\(\widehat Q_-=\sum_t\widehat\mu_t a_t,\qquad \widehat Q_+=\sum_t\widehat\mu_t b_t,\qquad \widehat S=\min\{\widehat q,\widehat Q_+\}.\)
Feasibility is the integer comparison \(\widehat Q_-\leq\widehat q\). The exact objective values are
\(\displaystyle R^*(p)=\frac{\widehat p\,\widehat S}{D^2},\qquad W^*(p)=\frac{\sum_t\widehat\mu_t\widehat u_t(p)+\widehat p\,\widehat S}{D^2}.\)
All menu prices use this same denominator, so objective comparisons reduce to integer comparisons.
Every integer in these computations has \(O(L)\) bits: scaling input rationals contributes \(O(L)\) bits, multiplication by bundle indices contributes \(O(\log(m+1))\), and summation contributes \(O(\log\tau)\). Both logarithmic terms are \(O(L)\).
For reconstruction, when \(\widehat Q_+>\widehat Q_-\), use
\(\displaystyle\theta=\frac{\widehat S-\widehat Q_-}{\widehat Q_+-\widehat Q_-}.\)
Its numerator and denominator have \(O(L)\) bits, as do the resulting rational assignment masses. A sparse assignment uses at most two bundles per type; an explicit table can also be output within the stated bound.
Schoolbook multiplication and division of these integers take \(O(L^2)\) bit operations. Constructing \(D\), scaling the inputs, scanning the menu, and reconstructing the outputs therefore fit within
\(O\!\left(|\mathcal P|\tau(m+1)L^2\right).\)
Because the valuation schedules and menu are explicit, this bound is polynomial in the total input length \(L\). It has no dependence on the number of possible types outside the support.
The cited paper defines allocations for finitely many buyers by an integer vector and states general-valuation hardness in Theorem 14. Those integer allocation constraints differ from the splittable masses permitted here. [Brânzei et al., *Walrasian Pricing in Multi-unit Auctions*, Preliminaries and Appendix B.4](https://arxiv.org/pdf/1602.08719)
For a concrete illustration, take one type of mass \(1\), with \(m=2\), \(B=2\), values \(v(0)=v(1)=0,\ v(2)=2\), menu \(\mathcal P=\{1\}\), and supply \(q=1\). At price \(1\), demand is exactly \(\{0,2\}\). Splitting mass equally between these bundles attains quantity \(1\), revenue \(1\), and welfare \(1\). Requiring the entire type mass to choose one demanded bundle would permit only bundle \(0\) under the supply constraint.
The interval-attainment argument proves why this distinction makes the stated distributional problem polynomial-time solvable.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly establishes polynomial-time exact optimization for both objectives under the specified explicit-menu, splittable-mass model. The feasibility test, objective formulas, assignment construction, and stated complexity bounds withstand verification. No mathematical gaps or false steps were found.
For every type and menu price, bundle \(0\) is affordable because \(p\cdot0=0\leq B_t\). The affordable set is finite and nonempty, so the maximum defining \(u_t(p)\) exists, and \(D_t(p)\), \(a_t(p)\), and \(b_t(p)\) are well-defined.
This argument also covers \(p=0\). It uses no unstated regularity of the valuation schedules.
Demand-supported masses for type \(t\) are assigned only to indices between \(a_t(p)\) and \(b_t(p)\). Nonnegativity and the type-mass constraint therefore justify
\[
\mu_t a_t(p)\leq\sum_j jz_{t,j}\leq\mu_t b_t(p).
\]
Summing gives the asserted interval bound on \(Q(z)\).
When \(Q_-(p)=Q_+(p)\), assigning every type its minimum demanded bundle attains the unique quantity in the interval.
Otherwise, the stated \(\theta\) belongs to \([0,1]\). For every type with distinct endpoints, its two assigned masses are nonnegative, sum to \(\mu_t\), and use demanded bundles. Types with coincident endpoints receive their entire mass at that endpoint.
The aggregate identity
\[
Q(z)=(1-\theta)Q_-(p)+\theta Q_+(p)=s
\]
remains valid for the coincident-endpoint types as well. Gaps inside individual demand sets cause no problem because the construction uses only their endpoints.
The interval statement permits real \(s\), consistent with the assignment definition. The algorithm later chooses rational \(s=S(p)\), so its output masses are rational.
If \(Q_-(p)>q\), the lower bound excludes every assignment. If \(Q_-(p)\leq q\), the minimum-demand assignment satisfies supply.
For a feasible price, \(S(p)=\min\{q,Q_+(p)\}\) lies in the attainable interval. It is attainable and is an upper bound on every supply-feasible quantity. Equality cases, including \(q=Q_-(p)\), are covered.
Revenue is \(pQ(z)\). Since menu prices are nonnegative, attaining the greatest feasible quantity maximizes revenue.
For welfare, every demanded bundle satisfies
\[
v_t(j)=u_t(p)+pj.
\]
Multiplication by the assigned masses and summation, using their support and type-mass constraints, gives exactly
\[
W(z)=U(p)+pQ(z).
\]
Thus attaining \(S(p)\) also maximizes welfare. At \(p=0\), both arguments still hold: revenue is zero and welfare is constant across feasible assignments.
The claim of a simultaneous optimizer is correctly restricted to a fixed price; the output explicitly allows different globally optimal prices.
Every menu price is evaluated. The discard rule is precisely the proved infeasibility condition, and each retained price receives its exact fixed-price optimum. Independent maximization of the two objective values therefore produces the respective global optima.
If all prices are discarded, reporting infeasibility is correct. Otherwise, the supplied interpolation reconstructs an assignment attaining each selected optimum.
Each demand scan examines \(\tau(m+1)\) entries per price. Aggregation takes \(O(\tau)\) operations. Reconstruction for at most two selected prices, including any necessary repeated scans, fits within
\[
O\!\left(|\mathcal P|\tau(m+1)\right)
\]
arithmetic operations and comparisons.
The denominator construction is valid: the product \(D\) has \(O(L)\) bits and is divisible by every input denominator. Consequently, each scaled input is an integer, and the stated scaled utility, feasibility, and objective formulas are exact. Both objectives have the common denominator \(D^2\), so integer comparisons suffice.
Input numerators, \(D\), bundle indices, and aggregate sums contribute only \(O(L)\) bits to each intermediate integer. Products of a fixed number of such integers retain \(O(L)\) bit length. The reconstruction fractions and resulting masses likewise have \(O(L)\)-bit numerators and denominators.
There are \(O(|\mathcal P|\tau(m+1))\) input rational entries and computational operations to handle. Schoolbook arithmetic therefore supports the claimed conservative bound
\[
O\!\left(|\mathcal P|\tau(m+1)L^2\right).
\]
Explicit valuation tables and the explicit menu make this polynomial in \(L\). Sparse or full-table assignment output fits within the bound.
The paper defines integer allocation vectors in its preliminaries and states general-valuation hardness in Theorem 14. The prover accurately describes those statements and does not invoke that theorem to establish its own algorithm. [Brânzei et al., *Walrasian Pricing in Multi-unit Auctions*](https://arxiv.org/pdf/1602.08719)
In the example, utilities at price \(1\) are \(0,-1,0\), and all three bundles are affordable. Hence demand is exactly \(\{0,2\}\). Equal splitting yields quantity, revenue, and welfare all equal to \(1\). Assigning the entire mass to bundle \(2\) violates supply, while assigning it to bundle \(0\) is feasible. The example therefore supports the stated distinction.
Repair feedback: None required. Both assigned questions are fully resolved as written.
⟨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.