Answer: Polynomial-time solvable in \(m\), \(\tau\), \(L\), and \(\log(k+1)\), with at most \(\tau(m+1)\) positive allocation entries.
Proposition 3.7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a single-category instance I and cardinality constraint k, the utilitarian-optimal cardinal al- location can be found in polynomial time, and has a utilitar- ian social welfare of at least 2 1+√ 1+ m−1 k · OPT-USW(I).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses over finitely many additive valuation types, rational per-capita supplies of finitely many good kinds, and a cardinality cap k, compute a mass allocation of each type to integral bundles of size at most k, meeting all supplies and maximizing total utilitarian welfare.
A society is given by its support: the list of \(\tau\) additive valuation types with positive binary-rational masses \(a_t\), where \(\sum_t a_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) good kinds with positive binary-rational per-capita supplies \(s_j\), and a binary-encoded integer cap \(k\geq1\), with \(\sum_j s_j\leq k\). Type \(t\) has nonnegative binary-rational values \(v_{tj}\), normalized by \(\sum_j s_jv_{tj}=1\).
An integral bundle is \(b\in\mathbb Z_{\geq0}^m\) with \(\sum_j b_j\leq k\); multiple copies of a kind and the empty bundle are allowed. Its value to type \(t\) is \(v_t\cdot b\).
A mass allocation assigns nonnegative rational masses \(x_{t,b}\), satisfying \(\sum_b x_{t,b}=a_t\) for every type and \(\sum_{t,b}b_jx_{t,b}=s_j\) for every kind. Its utilitarian welfare is \(W(x)=\sum_{t,b}x_{t,b}(v_t\cdot b)\). Represent allocations by listing only positive masses and their bundles.
Can an allocation maximizing \(W(x)\) be computed in polynomial time, or is this optimization problem NP-hard? State running times in \(m\), \(\tau\), the total input bit length \(L\), and \(k\), distinguishing polynomial dependence on \(\log k\) from dependence on \(k\).
For finitely many agents and explicitly listed indivisible goods, a utilitarian-optimal allocation under a common cardinality cap is computable in polynomial time. [Lam, Li, and Sun](https://arxiv.org/pdf/2501.01660).
The search identified no result settling this precise mass-allocation formulation.
The optimization problem is polynomial-time solvable, including when the cap \(k\) is binary encoded. An exact optimal allocation can be computed in \(\operatorname{poly}(m,\tau,L,\log(k+1))\) bit operations and represented using at most \(\tau(m+1)\) positive masses.
The decisive property is that multiple copies of a kind and the empty bundle are allowed.
For each type \(t\) and kind \(j\), let \(y_{tj}\) denote the total quantity of kind \(j\) assigned to type \(t\). Consider the following rational linear program:
\(\displaystyle \text{maximize }\sum_{t=1}^{\tau}\sum_{j=1}^{m}v_{tj}y_{tj}\)
subject to
\(\displaystyle \sum_{t=1}^{\tau}y_{tj}=s_j \qquad (j=1,\ldots,m),\)
\(\displaystyle \sum_{j=1}^{m}y_{tj}\leq k a_t \qquad (t=1,\ldots,\tau),\)
and \(y_{tj}\geq 0\).
It has \(m\tau\) variables, \(m\) supply equalities, and \(\tau\) capacity inequalities, in addition to nonnegativity.
It is feasible: set \(y_{tj}=a_t s_j\). The supply equalities follow from \(\sum_t a_t=1\), and each capacity inequality follows from
\(\displaystyle \sum_j a_t s_j=a_t\sum_j s_j\leq k a_t.\)
It is bounded: nonnegativity and the supply equalities imply \(0\leq y_{tj}\leq s_j\). Thus its feasible region is nonempty and compact, and its linear objective attains a maximum.
Given a feasible mass allocation \(x\), define
\(\displaystyle y_{tj}=\sum_b b_jx_{t,b}.\)
The original supply constraints give \(\sum_t y_{tj}=s_j\). Since every allowed bundle satisfies \(\sum_j b_j\leq k\), we have
\(\displaystyle \sum_j y_{tj} =\sum_b x_{t,b}\sum_j b_j \leq k\sum_b x_{t,b} =k a_t.\)
Thus \(y\) is LP-feasible. Additivity gives exact preservation of welfare:
\(\displaystyle W(x) =\sum_{t,b}x_{t,b}\sum_jv_{tj}b_j =\sum_{t,j}v_{tj}y_{tj}.\)
Consequently, the LP optimum is an upper bound on the welfare of every feasible mass allocation.
Let \(y\) be any rational feasible LP solution. Write \(e_j\) for the \(j\)-th standard unit vector. For each type \(t\), assign
\(\displaystyle x_{t,k e_j}=\frac{y_{tj}}{k}\qquad(j=1,\ldots,m)\)
and
\(\displaystyle x_{t,0}=a_t-\frac{1}{k}\sum_j y_{tj}.\)
Assign zero mass to all other bundles and omit zero entries from the representation.
These masses are nonnegative and rational. For the empty bundle, nonnegativity follows from the type-capacity inequality. Their sum for type \(t\) is exactly \(a_t\).
Every listed bundle is integral and respects the cap: \(0\) has cardinality zero, and \(k e_j\) has cardinality \(k\). This uses the hypothesis that multiple copies of a kind are permitted.
For every kind \(j\), the allocated supply is
\(\displaystyle \sum_{t,b}b_jx_{t,b} =\sum_t k\frac{y_{tj}}{k} =s_j.\)
Finally, the resulting welfare is
\(\displaystyle W(x) =\sum_{t,j}\frac{y_{tj}}{k}\bigl(v_t\cdot k e_j\bigr) =\sum_{t,j}v_{tj}y_{tj}.\)
Therefore the transformation preserves feasibility and objective value exactly. Applying it to an exact rational LP optimum produces an optimal mass allocation. Together with Section 2, this proves equality of the two optimization problems.
The algorithm is to construct the LP, solve it exactly over the rationals, and apply the formulas in Section 3.
The standard polynomial-time theorem for rational linear programming computes an exact rational optimum in time polynomial in the number of variables, constraints, and total coefficient encoding length, whenever the feasible region is nonempty and the optimum is finite. Both hypotheses were verified above. Rational data can be converted to integer data by clearing denominators with polynomial growth in encoding length; polynomial-time feasibility and optimization are described in [MIT’s ellipsoid-method lecture notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
For an explicit bound, let \(N=m\tau\). Even with a dense constraint matrix, the constructed LP has encoding length
\(\displaystyle B=O\!\left(L+\tau\log(k+1)+N(m+\tau+1)\right).\)
Indeed, its constraint coefficients are zero or one, and computing the right-hand sides \(k a_t\) adds at most \(O(\log(k+1))\) bits per type. Hence the complete algorithm takes
\(\displaystyle \left(L+\tau\log(k+1)+m\tau(m+\tau+1)\right)^{O(1)}\)
bit operations. Since \(L\) already includes the explicit valuation table and the binary encoding of \(k\), this is polynomial in the total input length.
The output contains at most \(\tau(m+1)\) positive entries. Each bundle is encoded as its integer coordinate vector; encoding \(k e_j\) requires \(O(m\log(k+1))\) bits, without enumerating its copies. Exact rational LP solutions have polynomial encoding length, and the divisions by \(k\) and subtractions used in reconstruction preserve polynomial encoding length.
Thus no polynomial dependence on the numerical value of \(k\) is needed. The potentially large set of integral bundles is never enumerated. The valuation normalization is compatible with the argument but is not needed for this tractability result.
⟨structured verdict parsed — rendered above⟩
The argument resolves the task: the stated linear program and reconstruction produce an exact welfare-maximizing mass allocation in polynomial time, with dependence on \(\log(k+1)\), rather than on the numerical value of \(k\). No major or minor mathematical issues were found.
The variables \(y_{tj}\) correctly represent aggregate quantities allocated to each type. The supply equalities and type-capacity inequalities are necessary conditions for a mass allocation.
The proposed feasible point \(y_{tj}=a_ts_j\) satisfies every constraint:
The boundedness argument is correct: each coordinate satisfies \(0\leq y_{tj}\leq s_j\). The feasible region is closed, nonempty, and bounded, so the linear objective attains a finite optimum.
Assessment: Correct.
For any feasible mass allocation, the definition
\[
y_{tj}=\sum_b b_jx_{t,b}
\]
preserves supplies and yields the asserted capacity inequality.
All sums are finite: for fixed finite integers \(m\) and \(k\), the set of nonnegative integral bundles with cardinality at most \(k\) is finite. Consequently, rearranging sums in the welfare identity introduces no convergence issue.
Additivity gives exact preservation of welfare. Therefore every feasible mass allocation has welfare at most the LP optimum.
Assessment: Correct.
The reconstruction is well-defined because \(k\geq1\). For each type, the bundles \(ke_j\) are distinct and different from the empty bundle.
Every reconstructed mass is rational and nonnegative. In particular,
\[
a_t-\frac{\sum_j y_{tj}}{k}\geq0
\]
follows directly from the capacity constraint. Summing the reconstructed masses gives exactly \(a_t\).
Every listed bundle is allowed. The use of \(ke_j\) is justified by the explicit permission to allocate multiple copies of a kind. There is no task requirement bounding an individual bundle by the per-capita supply.
For each kind, multiplication of its bundle quantity \(k\) by its assigned mass \(y_{tj}/k\) recovers \(y_{tj}\). The supply and welfare computations are therefore exact.
This establishes the required reverse direction for every rational feasible LP solution. The exact rational optimum supplied by the LP algorithm consequently reconstructs an optimal allocation.
Assessment: Correct.
The prover states the needed rational linear-programming theorem sufficiently precisely: exact optimization takes polynomial time in the dimensions and coefficient encoding length when feasibility and finiteness hold. Those hypotheses were verified, and all coefficients are rational.
The cited [MIT lecture notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) support polynomial-time LP feasibility and optimization, including polynomial bounds on arithmetic precision and intermediate encoding sizes. Clearing rational denominators has polynomial encoding cost.
The stated dense encoding bound
\[
B=O\!\left(L+\tau\log(k+1)+m\tau(m+\tau+1)\right)
\]
is valid. The constraint matrix has only zero and one entries; multiplying each \(a_t\) by \(k\) adds at most \(O(\log(k+1))\) bits per type.
The output-support bound is correct: each type contributes at most \(m\) nonempty bundles and one empty bundle. Bundle coordinates can be encoded in binary without enumerating individual copies.
In context, the assertion about polynomial encoding length of exact LP solutions refers to the optimum returned by the polynomial-time solver. The subsequent rational arithmetic preserves polynomial output length.
Assessment: Correct.
The argument covers \(m=1\), \(k=1\), zero valuation coordinates, zero reconstructed masses, and the saturated case \(\sum_j s_j=k\). It requires neither strict capacity slack nor positive values for every kind.
The valuation normalization is indeed unused. Omitting it from the proof does not weaken the result for the specified inputs.
No additional lemma or 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.