Answer: Polynomial-time solvable: in \(\mathrm P\), with bit running time \(\bigl[L+(m+\tau)\tau 2^m+(k+\tau)\tau 2^k\bigr]^{O(1)}=L^{O(1)}\).
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor every partition π, rπ = max s(∆), where the maximum is taken over all families ∆that are feasible for π.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given item kinds \(A\), a partition \(\pi\), rational valuation types \(v_t:2^A\to\mathbb{Q}_{\ge 0}\), masses \(\mu_t\) summing to \(1\), per-capita supplies \(\rho_a\), and threshold \(q\), optimize mass allocations \(x_{t,B}\) with \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B\ni a}x_{t,B}\le\rho_a\), compare unrestricted welfare \(S^\star\) with \(\Sigma_\pi\)-restricted welfare \(S^\pi\), and decide whether \(S^\star/S^\pi\ge q\).
Let \(A\) contain \(m\ge1\) item kinds, and let \(\pi=\{A_1,\ldots,A_k\}\) partition \(A\) into nonempty parts. Define \(\Sigma_\pi=\{\bigcup_{j\in J}A_j:J\subseteq\{1,\ldots,k\}\}\).
A society is given by its support: the list of its \(\tau\ge1\) valuation types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(\sum_t\mu_t=1\).
Each \(v_t:2^A\to\mathbb Q_{\ge0}\) is supplied as a complete table, satisfies free disposal, and has \(v_t(\varnothing)=0\). Supplies \(\rho_a\in\mathbb Q_{\ge0}\) and threshold \(q\in\mathbb Q_{\ge1}\) are binary encoded; \(L\) is the total input bit length, including valuation tables.
An allocation consists of real masses \(x_{t,B}\ge0\), allowing each type to be split among bundles, with \(\sum_{B\subseteq A}x_{t,B}=\mu_t\) and \(\sum_t\sum_{B\ni a}x_{t,B}\le\rho_a\) for every \(a\in A\). Unused supply is allowed.
Let \(S^\star\) maximize \(\sum_t\sum_{B\subseteq A}x_{t,B}v_t(B)\) over these allocations, and let \(S^\pi\) maximize the same objective subject additionally to \(x_{t,B}=0\) for \(B\notin\Sigma_\pi\). Promise \(S^\pi>0\).
Is deciding whether \(S^\star/S^\pi\ge q\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,k,L\).
For finite buyers receiving disjoint bundles, the worst-case unrestricted-to-restricted welfare ratio equals the largest size of a multiset of nonempty, pairwise intersecting subsets of \(\{1,\ldots,k\}\), with each index \(j\) appearing at most \(|A_j|\) times; this is a characterization, not a complexity classification. [Holzman et al.](https://holzman.technion.ac.il/files/2012/09/gebrndm.pdf)
Related fractional bundle-allocation models are studied for combinatorial Walrasian equilibrium; no classification of the precise mass-and-supply ratio decision problem above was identified. [Feldman et al.](https://www.cs.tau.ac.il/~mfeldman/papers/FGLj16.pdf)
The decision problem is in \(\mathrm P\). Both welfare maxima can be computed exactly by rational linear programming, in total bit running time
\(\bigl[L+(m+\tau)\tau 2^m+(k+\tau)\tau 2^k\bigr]^{O(1)}=L^{O(1)}.\)
The exponent is an absolute constant. This is a polynomial bound in the binary input length; no strongly polynomial bound is asserted.
Introduce one real variable \(x_{t,B}\) for each supported type \(t\in\{1,\ldots,\tau\}\) and bundle \(B\subseteq A\). Maximize
\(\displaystyle \sum_{t=1}^{\tau}\sum_{B\subseteq A}v_t(B)x_{t,B}\)
subject to:
These constraints are precisely the unrestricted allocation requirements. Consequently, the program’s optimal value is \(S^\star\).
It has \(\tau2^m\) variables, \(\tau\) equality constraints, and \(m\) supply inequalities, together with variable nonnegativity.
The feasible set is nonempty: assigning \(x_{t,\varnothing}=\mu_t\) and all other variables zero satisfies every constraint. Moreover, nonnegativity and the type equalities imply \(0\le x_{t,B}\le\mu_t\). Thus the feasible set is closed and bounded, hence compact. The linear objective therefore attains a finite maximum.
For \(J\subseteq\{1,\ldots,k\}\), define
\(U_J=\bigcup_{j\in J}A_j,\qquad w_{t,J}=v_t(U_J).\)
Because the partition parts are nonempty and disjoint, the map \(J\mapsto U_J\) is injective. Its image is exactly \(\Sigma_\pi\), which therefore contains \(2^k\) bundles.
Define the effective supply of part \(j\) by
\(\displaystyle r_j=\min_{a\in A_j}\rho_a.\)
Introduce variables \(y_{t,J}\ge0\). Maximize
\(\displaystyle \sum_{t=1}^{\tau}\sum_{J\subseteq\{1,\ldots,k\}}w_{t,J}y_{t,J}\)
subject to:
To verify the supply constraints, fix a part \(A_j\). Every allowed bundle contains either all of \(A_j\) or none of it. Therefore each item kind \(a\in A_j\) has the same allocated mass,
\(\displaystyle z_j=\sum_{t=1}^{\tau}\sum_{J\ni j}y_{t,J}.\)
The original inequalities \(z_j\le\rho_a\) for all \(a\in A_j\) are equivalent to \(z_j\le r_j\). Hence this program describes exactly the restricted allocations, and its optimal value is \(S^\pi\).
It has \(\tau2^k\) variables, \(\tau\) equality constraints, and \(k\) supply inequalities. Assigning all mass to \(J=\varnothing\) proves feasibility; the type equalities again prove boundedness.
We use the standard exact rational linear programming theorem: a linear program with explicitly listed binary rational data can be solved in time polynomial in its encoding length, returning an exact rational optimum when the program is feasible and bounded. Equalities and variable nonnegativity are permitted. This follows from polynomial-time linear programming over integer data by clearing denominators; the resulting integers have polynomial encoding length. See [MIT’s lecture on the ellipsoid method](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
Both programs satisfy the theorem’s hypotheses:
Compute their exact optimal values. Write
\(S^\star=a/b,\qquad S^\pi=c/d,\qquad q=e/f,\)
with positive denominators. The promise \(S^\pi>0\) gives \(c>0\). Multiplication by the positive denominators proves
\(\displaystyle \frac{S^\star}{S^\pi}\ge q \quad\Longleftrightarrow\quad adf\ge bce.\)
The exact LP outputs have polynomial encoding length. Thus the final integer multiplications and comparison also take polynomial time, including when equality holds.
Let \(D_\star\) and \(D_\pi\) denote the binary encoding lengths of dense representations of the two programs. Their constraint matrices contain only zeros and ones. Their remaining numerical data are copied from the input, with the restricted supplies selected by taking minima. Consequently,
\(D_\star=O\bigl(L+(m+\tau)\tau2^m\bigr),\)
\(D_\pi=O\bigl(L+(k+\tau)\tau2^k\bigr).\)
Constructing these programs, including enumerating the allowed unions and retrieving their valuations, takes polynomial time in these bounds. Exact optimization therefore takes respectively
\(\bigl[L+(m+\tau)\tau2^m\bigr]^{O(1)}\)
and
\(\bigl[L+(k+\tau)\tau2^k\bigr]^{O(1)}.\)
Finally, the complete valuation tables contain \(\tau2^m\) explicitly encoded entries. Each entry occupies at least one bit, so \(\tau2^m\le L\). Also \(k\le m\), and \(m,\tau=O(L)\). Hence both program encodings have size \(O(L^2)\), proving the claimed total bound \(L^{O(1)}\).
The conclusion concerns the stated model with splittable type masses and complete valuation tables. It requires no computation of the finite-buyer worst-case characterization. Under polynomial-time many-one reductions, NP-hardness of this decision problem would therefore imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem. The decision problem is in \(\mathrm P\) under the specified complete-table encoding. Both LP formulations describe the intended allocations exactly, and their exact optimal values can be compared in polynomial bit time. No major or minor issues were found.
The variables \(x_{t,B}\) range over precisely the supported types and all bundles. The type equalities, supply inequalities, nonnegativity constraints, and objective agree with the definitions in the task. Thus the identification of the optimal value with \(S^\star\) is justified.
The feasibility witness is valid: allocating every type’s mass to the empty bundle consumes zero supply.
For every coordinate, nonnegativity and the corresponding type equality imply \(0\le x_{t,B}\le\mu_t\). The feasible set is therefore bounded and is closed because it is defined by finitely many linear equalities and weak inequalities. Compactness and continuity justify attainment of a finite optimum.
The stated counts—\(\tau2^m\) variables, \(\tau\) type equalities, and \(m\) supply inequalities—are correct.
The map \(J\mapsto U_J\) is injective because the partition parts are nonempty and disjoint. Its image is exactly \(\Sigma_\pi\), so there are exactly \(2^k\) permitted bundles.
The replacement of item supply constraints by part supply constraints is exact. For any fixed part \(A_j\), every permitted bundle contains either every item in \(A_j\) or none. Consequently, all items in that part have the same allocated mass \(z_j\). Requiring \(z_j\le\rho_a\) for every \(a\in A_j\) is equivalent to requiring \(z_j\le\min_{a\in A_j}\rho_a\).
The minimum exists because each part is nonempty. The argument remains valid when supplies are zero or differ within a part.
Together with the bijection between permitted bundles and index subsets, this verifies that the restricted program has optimal value \(S^\pi\). Its variable and constraint counts, feasibility witness, and boundedness argument are also correct.
The invoked theorem is stated with the necessary scope: explicitly encoded rational LPs admit polynomial bit-time solution, with an exact rational optimum for feasible, bounded instances.
Both programs satisfy these hypotheses. Equalities and nonnegativity do not invalidate the theorem, and no full-dimensionality assumption is needed for the general LP result. Clearing rational denominators preserves polynomial encoding length.
The cited [MIT lecture](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) supports polynomial-time integer LP feasibility and optimization, including polynomial bounds on intermediate numerical representations. The theorem application is justified.
With \(S^\star=a/b\), \(S^\pi=c/d\), and \(q=e/f\), the denominators can all be chosen positive. The promise gives \(c>0\). Therefore the stated equivalence is correct:
\[ \frac{S^\star}{S^\pi}\ge q \quad\Longleftrightarrow\quad adf\ge bce. \]
Exact arithmetic handles equality at the threshold. Polynomial output bit lengths and the input encoding length of \(q\) justify polynomial-time multiplication and comparison.
The dense matrix dimensions are correctly bounded. Matrix entries are zeros or ones; objective and right-hand-side data are copied or selected from the input. Nonnegativity may be encoded as variable bounds. Thus the stated bounds for \(D_\star\) and \(D_\pi\) are valid.
Enumerating bundles, constructing permitted unions, retrieving table entries, and selecting minimum supplies require polynomial time in these bounds.
The crucial input-size argument is correct: the complete valuation tables contain \(\tau2^m\) explicitly encoded entries, so \(\tau2^m\le L\). Also \(k\le m\) and \(m,\tau=O(L)\). Each displayed LP encoding bound is consequently \(O(L^2)\).
The total running time
\[ \bigl[L+(m+\tau)\tau2^m+(k+\tau)\tau2^k\bigr]^{O(1)} = L^{O(1)} \]
is justified. Its exponential dependence on \(m\) is compatible with polynomial dependence on the stated input length.
The proof covers real, splittable masses and unused supply exactly as requested. It does not rely on the finite-buyer characterization. The cases \(m=1\), \(\tau=1\), zero supplies, and \(q=1\) cause no failure. The positive-denominator promise is used where needed.
The final observation about NP-hardness implying \(\mathrm P=\mathrm{NP}\) is correct.
No repair or additional clarification is required.
⟨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.