Answer: Polynomial-time computable for every fixed \(T\) and \(\epsilon\in(0,1]\); the algorithm also works without a fixed bound on \(\tau\).
Theorem 3 — class: algorithmic
For fixed \(T\) and fixed \(\epsilon>0\), given rational type masses \(\mu_t>0\) summing to \(1\), integer additive values \(v_{tj}\), and rational per-capita supplies \(\rho_j\), can one compute in time polynomial in the binary input length a polynomially encoded list of feasible plans? A plan assigns mass \(x_{t,b}\geq 0\) of type \(t\) to integral bundles \(b\in\mathbb Z_{\geq 0}^{q}\), with \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_jx_{t,b}=\rho_j\). Writing \(u_t(b)=\sum_jv_{tj}b_j\), \(E(x)=\min_{t,b:x_{t,b}>0}u_t(b)\), and \(W(x)=\sum_{t,b}x_{t,b}u_t(b)\), the list must contain, for every finite-support feasible plan \(y\), a plan \(x\) with \(E(x)\geq(1-\epsilon)E(y)\) and \(W(x)\geq(1-\epsilon)W(y)\).
A society is given by its support: a list of \(\tau\geq1\) distinct valuation types with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types, and \(\tau\leq T\) for a fixed constant \(T\).
There are \(m\geq1\) item types, with nonnegative integer additive values \(v_{tj}\) and nonnegative binary-rational per-capita supplies \(\rho_j\). Let \(L\) be the total binary input length; the number of item types is unrestricted.
A feasible plan has finite support and assigns real masses \(x_{t,b}\geq0\) to integral bundles \(b\in\mathbb Z_{\geq0}^{m}\), satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}b_jx_{t,b}=\rho_j\) for every \(j\). Empty bundles are allowed; there is no individual bundle-size bound.
Define \(u_t(b)=\sum_jv_{tj}b_j\), \(E(x)=\min_{t,b:x_{t,b}>0}u_t(b)\), and \(W(x)=\sum_{t,b}x_{t,b}u_t(b)\).
For \(\epsilon\in(0,1]\), an \(\epsilon\)-Pareto list is a finite list of feasible plans such that every finite-support feasible plan \(y\) has a listed plan \(x\) satisfying \(E(x)\geq(1-\epsilon)E(y)\) and \(W(x)\geq(1-\epsilon)W(y)\). Output plans are encoded explicitly by their positive entries, using binary integers for bundles and binary rationals for masses.
For every fixed \(T\) and fixed \(\epsilon\in(0,1]\), can an \(\epsilon\)-Pareto list of total encoding length polynomial in \(m,\tau,L\) be computed in time polynomial in \(m,\tau,L\), or is achieving this approximation guarantee NP-hard for some fixed \(T,\epsilon\)?
For finitely many agents and explicitly listed indivisible goods with nonnegative integer additive values, an \(\epsilon\)-Pareto set for egalitarian and utilitarian welfare is computable in polynomial time when the number of agent types and \(\epsilon\) are fixed. [Nguyen–Rothe](https://www.ijcai.org/proceedings/2020/0041.pdf)
No result settling the precisely defined mass-plan approximation problem was identified in the literature search.
Result. An \(\epsilon\)-Pareto list can be computed in polynomial time for every fixed \(\epsilon\in(0,1]\). In fact, the algorithm does not require a bound on \(\tau\), and its guarantee for utilitarian welfare is stronger:
For every finite-support feasible plan \(y\), some listed plan \(x\) satisfies
\[
E(x)\geq(1-\epsilon)E(y),
\qquad
W(x)\geq W(y).
\]
Here and below, output plans have integral bundles, rational masses, and polynomial total encoding length.
1. Bounds and an elementary rounding construction
Define \(V_j=\max_t v_{tj}\) and \(B=\sum_j\rho_jV_j\). Every feasible plan satisfies \(W(x)\leq B\): each unit of item \(j\) contributes at most \(V_j\). Since the total population mass is \(1\), also \(E(x)\leq W(x)\leq B\).
Moreover, \(E(x)\) is a nonnegative integer. Indeed, finite support makes it the minimum of finitely many integer bundle utilities. Consequently, \(E(x)>0\) implies \(E(x)\geq1\).
We will repeatedly use the following construction.
Rounding lemma. Given a nonnegative rational vector \(s\in\mathbb Q_{\geq0}^{m}\), one can compute a rational distribution on at most \(m+1\) integral vectors \(c\) such that:
To prove this, write \(s_j=\lfloor s_j\rfloor+\theta_j\), where \(\theta_j\in[0,1)\). For \(r\in[0,1)\), set \(c_j(r)=\lfloor s_j\rfloor+\mathbf1_{\{r<\theta_j\}}\). Partition \([0,1)\) at the distinct positive numbers \(\theta_j\). On each resulting interval, \(c(r)\) is constant. Give that vector mass equal to the interval length.
There are at most \(m+1\) intervals, all masses are rational, and the mean of coordinate \(j\) is \(\lfloor s_j\rfloor+\theta_j=s_j\). Sorting the breakpoints and constructing the vectors takes polynomial time. Their encoding lengths are polynomial in the encoding length of \(s\).
This lemma already gives an explicit plan with welfare \(B\). Assign the aggregate supply of each item to a type attaining \(V_j\). If type \(t\) receives aggregate vector \(z_t\), apply the lemma to \(z_t/\mu_t\), and multiply its distribution masses by \(\mu_t\). The resulting plan is feasible and has welfare \(B\).
Include this plan in the output list. It covers every plan \(y\) with \(E(y)=0\). For \(\epsilon=1\), it alone suffices.
2. The threshold subproblem
For the remaining argument, fix a rational constant \(\eta\) satisfying \(0<\eta\leq\min\{1/4,\epsilon/4\}\).
We prove the following threshold guarantee:
Given a positive rational threshold \(H\), a polynomial-time procedure either returns a feasible plan \(x_H\) or declares its auxiliary linear program infeasible. Whenever a finite-support feasible plan \(y\) satisfies \(E(y)\geq H\), the procedure returns a plan satisfying \(E(x_H)\geq(1-2\eta)H\) and \(W(x_H)\geq W(y)\).
Set \(H'=(1-\eta)H\), \(a=\eta H/m\), \(d=\eta^2H/(2m)\), and \(K=\lceil H'/d\rceil\). Thus \(K=\lceil2m(1-\eta)/\eta^2\rceil\), independent of the magnitude of \(H\).
For each type \(t\), call item \(j\) small if \(v_{tj}<a\), and large otherwise. For a large item, define \(k_{tj}=\min\{K,\lfloor v_{tj}/d\rfloor\}\).
Every large-item coefficient is positive. More precisely, before capping,
\[ \left\lfloor\frac{v_{tj}}d\right\rfloor \geq\frac{2}{\eta}-1 \geq\frac1\eta. \]
For each type, construct a directed graph with states \(0,\ldots,K\). From each state \(q<K\), a large item \(j\) creates an arc to \(\min\{K,q+k_{tj}\}\), labelled by one copy of item \(j\). Every arc strictly increases the state, so the graph is acyclic.
A path ending at state \(q\) represents an integral bundle of large items with actual utility at least \(qd\). To verify this, each item has actual value at least \(dk_{tj}\), while saturation of the state at \(K\) can only reduce the accumulated state.
3. The linear program
For each type \(t\), use these nonnegative variables:
Flow conservation at every state is
\[ \mu_t\mathbf1_{\{q=0\}} +\sum_{\text{arcs entering }q}f = A_{tq}+\sum_{\text{arcs leaving }q}f. \]
There are no arcs leaving state \(K\). Summing these equations gives \(\sum_q A_{tq}=\mu_t\).
At each terminal state impose
\[ \sum_{j:\,v_{tj}<a}v_{tj}z_{tqj} \geq A_{tq}\max\{0,H'-qd\}. \]
Define the aggregate base quantity of item \(j\) assigned to type \(t\) by
\[ C_{tj}= \begin{cases} \sum_{q=0}^{K-1}f_{tqj},&v_{tj}\geq a,\\ \sum_{q=0}^{K}z_{tqj},&v_{tj}<a. \end{cases} \]
Enforce exact supplies: \(\sum_t(C_{tj}+r_{tj})=\rho_j\) for every \(j\). Maximize
\[ \sum_{t,j}v_{tj}(C_{tj}+r_{tj}). \]
This is a rational linear program of polynomial size. Its number of variables and constraints is polynomial in \(\tau,m,K\), and \(K=O(m/\eta^2)\).
Its feasible region is bounded. Every flow, small-item quantity, and additional quantity is bounded by its item’s supply; every terminal mass is bounded by its type’s population mass. Thus, if feasible, the program has an attained optimum. Standard polynomial-time rational linear programming yields an optimal rational solution of polynomial encoding length.
4. Every plan meeting the threshold gives a feasible LP solution
Let \(y\) be a finite-support feasible plan with \(E(y)\geq H\). Consider a supported bundle \(b\) of type \(t\).
Process its large items in any fixed order through the graph. Stop upon reaching state \(K\), if that occurs. Assign any remaining large items to the variables \(r_{tj}\). Assign all small items to the terminal quantities \(z_{tqj}\).
If the path reaches \(K\), the terminal utility constraint requires no small-item utility because \(Kd\geq H'\).
Otherwise, let \(q<K\) be its final state and \(n\) its number of large items. No coefficient used on this path was capped: a coefficient equal to \(K\) would have reached state \(K\). Therefore
\[ q=\sum_{\text{large items in }b}\left\lfloor\frac{v_{tj}}d\right\rfloor. \]
The large-item utility exceeds \(qd\) by less than \(nd\). The coefficient bound gives \(n\leq\eta q\). Also, \(q\leq K-1\) implies \(qd<H'\). Consequently,
\[ nd\leq\eta qd<\eta H'<\eta H. \]
Writing \(u_{\mathrm{small}}(b)\) for the small-item utility, we obtain
\[ qd+u_{\mathrm{small}}(b) \geq u_t(b)-nd >H-\eta H =H'. \]
Thus this bundle satisfies the required terminal inequality.
Weight these paths, terminal quantities, and additional quantities by the masses in \(y\), and sum. Flow conservation and supply equalities follow directly. The terminal inequalities remain valid because they are linear.
No item changes its recipient type, so the LP objective equals \(W(y)\). Hence the optimal LP value is at least \(W(y)\).
This argument applies even when the masses in \(y\) are irrational: it establishes real feasibility of the rational LP, whose rational optimum is then computed by the algorithm.
5. Converting the LP optimum to an explicit feasible plan
Take an optimal rational LP solution.
For each type, decompose its flow into paths from state \(0\), each terminating at some state \(q\). A constructive decomposition repeatedly selects a positive-flow path to a positive terminal mass and subtracts the minimum flow or terminal mass on that path. Each iteration eliminates a positive arc or terminal variable. Therefore the number of paths is polynomial, and their masses are rational.
Consider a terminal state with \(A_{tq}>0\). Define its mean small-item vector by \(s_{tqj}=z_{tqj}/A_{tq}\) for small items and \(s_{tqj}=0\) for large items.
For every path ending at \(q\), split its mass using the rounding lemma for \(s_{tq}\), adding each resulting integral small-item vector to that path’s large-item bundle. Because the path masses ending at \(q\) sum to \(A_{tq}\), this realizes exactly the aggregate small-item quantities \(z_{tqj}\).
Every resulting bundle has utility at least
\[ qd+\sum_{j:\,v_{tj}<a}v_{tj}s_{tqj} -\sum_{j:\,v_{tj}<a}v_{tj}. \]
The terminal constraint implies that the first two terms sum to at least \(H'\). There are at most \(m\) small items and each has value less than \(a\), so the final sum is less than \(ma=\eta H\). Every resulting bundle therefore has utility at least
\[ H'-\eta H=(1-2\eta)H. \]
Small-item quantities attached to terminal states with \(A_{tq}=0\) have not yet been realized. Combine those quantities with the additional quantities \(r_{tj}\), obtaining an aggregate residual vector \(R_t\) for each type.
Since \(\mu_t>0\), type \(t\) has at least one positive-mass bundle in the constructed base plan. Select one such entry, with bundle \(b\) and mass \(p>0\). Apply the rounding lemma to \(R_t/p\), and replace this entry by the resulting distribution of bundles \(b+c\), with masses multiplied by \(p\). This realizes exactly \(R_t\). Nonnegative valuations ensure that every replacement bundle has utility at least that of \(b\).
The final plan consequently:
The last property makes its welfare exactly the LP objective. By Section 4, this is at least \(W(y)\) whenever \(E(y)\geq H\). This proves the threshold guarantee.
6. Constructing and verifying the Pareto list
In addition to the welfare-\(B\) plan from Section 1, run the threshold procedure for every number \(H=(1+\eta)^k\), where \(k\) is a nonnegative integer and \(H\leq B\). Include every returned plan.
If \(B<1\), no threshold runs are needed: every feasible plan has \(E=0\).
Otherwise, let \(y\) have \(E(y)>0\). Since \(1\leq E(y)\leq B\), the grid contains some \(H\) satisfying \(H\leq E(y)<(1+\eta)H\). The corresponding LP is feasible by Section 4, and the returned plan satisfies \(W(x_H)\geq W(y)\) and
\[ E(x_H)\geq(1-2\eta)H > \frac{1-2\eta}{1+\eta}E(y). \]
The approximation factor obeys
\[ \frac{1-2\eta}{1+\eta}\geq1-3\eta\geq1-\epsilon. \]
For the first inequality, multiplying by \(1+\eta>0\) reduces it to \(1-2\eta\geq1-2\eta-3\eta^2\). The second follows from \(3\eta\leq\epsilon\).
Plans with \(E(y)=0\) are covered by the welfare-\(B\) plan. Thus the list has the required guarantee for every finite-support feasible plan.
7. Running time and output encoding
The rational number \(B\) has polynomial binary encoding length, so the grid has polynomially many thresholds for fixed \(\eta\). Each threshold also has polynomial encoding length.
Each LP has polynomial dimension and coefficient encoding length. Its optimal rational solution has polynomial encoding length. Path decomposition produces polynomially many paths, each containing at most \(K\) large items. Each small-item rounding produces at most \(m+1\) bundles per path. Residual insertion adds at most \(m\) entries per type.
All subsequent operations—rational sums, divisions, floors, breakpoint sorting, and products of masses—preserve polynomial encoding length. In particular, a small terminal mass can produce a large bundle coordinate, but its binary length remains polynomial. Coincident entries can be merged.
Therefore both the computation time and the total explicit output length are polynomial in \(m,\tau,L\), for every fixed \(\epsilon\). No step assumes that \(\tau\) is bounded.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed polynomial-time approximation, including its stronger utilitarian guarantee and its extension to unrestricted support size. I found one minor edge-case error in the wording of the rounding estimate; it does not undermine the conclusion.
1. Bounds and the rounding lemma
The bounds \(E(x)\leq W(x)\leq B\) are valid. Total population mass is \(1\), and every positively supported bundle has utility at least \(E(x)\). Each item contributes at most its maximum valuation \(V_j\), giving the upper bound \(B\).
Finite support and integer valuations imply that \(E(x)\) is a nonnegative integer. Thus the restriction to thresholds starting at \(1\) is justified.
The rounding lemma is correct. Its intervals give rational positive masses summing to \(1\), its supported vectors are integral and coordinatewise at least the floors, and each coordinate has the stated mean. Zero fractional parts and repeated breakpoints cause no problem.
Assigning every item’s aggregate supply to a maximizing type and applying this lemma gives an explicit feasible plan with welfare \(B\). This covers all plans with \(E(y)=0\), including the cases \(B=0\) and \(\epsilon=1\).
2. Threshold parameters and the graph
The identity
\(K=\lceil 2m(1-\eta)/\eta^2\rceil\)
is correct, so graph size is independent of the numerical magnitude of \(H\).
For large items, the stated uncapped coefficient bound follows from \(v_{tj}\geq a\) and \(a/d=2/\eta\). Since \(\eta\leq 1/4\), the comparison \(2/\eta-1\geq 1/\eta\) is valid. Capped coefficients remain positive.
All arcs strictly increase the state. The graph is therefore acyclic, and the claimed lower bound \(qd\) on the utility of a path ending at \(q\) is valid even when the state saturates at \(K\).
3. Linear-program formulation
The variables and constraints correctly distinguish large-item path quantities, small-item terminal quantities, and residual quantities.
Summing flow conservation gives the required type mass \(\mu_t\). Supply equalities account for every item quantity exactly once. The objective equals aggregate welfare for the recipient-type assignments encoded by the variables.
The boundedness assertion is valid: nonnegative quantities contributing to an item’s supply equality are individually bounded by that supply, and terminal masses are bounded by \(\mu_t\). The program has polynomially many variables and constraints and rational coefficients of polynomial encoding length.
The rational linear-programming result invoked here applies: a feasible bounded rational LP can be optimized in polynomial time, with an optimal rational solution of polynomial encoding length. The necessary hypotheses are established in the write-up.
4. Embedding a threshold-feasible plan
The construction correctly handles both possibilities:
The estimates \(n\leq\eta q\), \(qd<H'\), and \(nd<\eta H\) are valid. Together with the rounding-error bound used in the subsequent non-strict inequality, they imply the terminal requirement.
There is one minor issue:
Issue — minor, Section 4, “The large-item utility exceeds \(qd\) by less than \(nd\).”
This strict estimate fails when \(n=0\). Then \(q=0\), and both the discrepancy and \(nd\) equal zero.
This case can occur for a bundle meeting the threshold. For example, take one type and one item, with valuation \(1\), mass \(1\), supply \(16\), \(H=16\), and \(\eta=1/8\). Then \(a=2\), so the item is small, and the bundle containing \(16\) copies meets the threshold with no large items.
The subsequent displayed inequality uses a non-strict estimate that remains valid in this case, so the conclusion survives. The minimum clarification needed is to state a discrepancy bound valid also for \(n=0\), or explicitly separate that case.
Weighting the bundle constructions by the masses in \(y\) preserves the linear constraints and welfare. Irrational masses in \(y\) are harmless: they establish real feasibility, while the algorithm computes a rational optimum.
5. Reconstruction of an explicit plan
The flow decomposition is valid for this acyclic graph. Conservation ensures that remaining positive flow can be traced from the source to a positive terminal mass. Each subtraction eliminates a positive arc or terminal variable, giving polynomially many paths. Empty paths ending at state \(0\) are allowed.
For \(A_{tq}>0\), the small-item mean vector is well-defined and rational. Applying the same rounding distribution to every path ending at \(q\) realizes exactly the terminal small-item quantities.
The utility estimate is correct. The terminal constraint guarantees utility at least \(H'\) before the small-item rounding loss, and that loss is bounded by the sum of the small-item valuations, which is less than \(\eta H\). This yields the stated lower bound \((1-2\eta)H\).
The treatment of quantities at zero-mass terminal states is also valid. They are included in the residual vector and subsequently inserted into a positive-mass entry of the same type. Such an entry exists because \(\mu_t>0\). Residual insertion preserves exact supplies and type masses, and nonnegative valuations preserve the utility lower bound.
Consequently, the reconstructed plan has welfare exactly equal to the LP objective. The stronger guarantee \(W(x_H)\geq W(y)\) follows.
6. Pareto-list coverage
The geometric grid covers every possible positive egalitarian value because \(1\leq E(y)\leq B\).
The selected threshold satisfies \(H\leq E(y)<(1+\eta)H\). Its LP is feasible by the embedding argument, and reconstruction gives the claimed welfare guarantee.
The approximation-factor computation is correct:
\((1-2\eta)/(1+\eta)\geq 1-3\eta\geq 1-\epsilon\).
The assumption \(\eta\leq\epsilon/4\) is sufficient for the last inequality.
The argument therefore covers every finite-support feasible plan, including plans with irrational masses.
7. Running time and output length
The encoding-length claims are consistent with the construction:
The arithmetic occurs in a fixed sequence of reconstruction stages. Dividing by a positive rational mass may create numerically large bundle coordinates, but their binary lengths remain polynomial. No argument requires \(\tau\) to be bounded.
Adjudication
The output settles the intended complexity question in substance. The sole identified issue is a routine zero-large-item edge case in an intermediate strict estimate. No new mathematical argument is required to clarify it.
⟨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.