Answer: Polynomial-time solvable: \(\mathrm{P}\), with bit running time \((m+\tau+L)^{O(1)}\).
Theorem 4.1 — class: hardness
Given finitely many agent types \(T\) with rational masses \(\mu_t\) summing to \(1\), resource categories \(R\) with rational per-capita supplies \(b_r\), and explicitly represented bundle utilities \(u_t(B)\), is there an allocation of integral bundles to almost every agent such that each receives utility at least \(K\) and total use of each resource category stays within its supply? Equivalently, decide whether there are masses \(x_{tB}\ge 0\) satisfying \(\sum_{B\subseteq R}x_{tB}=\mu_t\), \(\sum_{t\in T,\,B\ni r}x_{tB}\le b_r\), and \(x_{tB}=0\) whenever \(u_t(B)<K\).
A society is atomless and given by its support: the list of \(\tau\) types \(T\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
There are \(m\) resource categories \(R\), with binary rational per-capita supplies \(b_r\ge0\). Each agent receives a bundle \(B\subseteq R\), consuming one unit of each category in \(B\); unused supply is permitted.
Each utility \(u_t:2^R\to\mathbb Q\) is represented by an explicit list of its nonzero bundle–value pairs; omitted bundles have utility zero. Values may be negative, and the empty bundle is allowed with its specified or default value. The threshold \(K\in\mathbb Q\) is binary encoded.
Feasibility means that real masses \(x_{tB}\ge0\) exist satisfying \(\sum_{B\subseteq R}x_{tB}=\mu_t\), \(\sum_{t\in T}\sum_{B\ni r}x_{tB}\le b_r\), and \(x_{tB}=0\) whenever \(u_t(B)<K\). A type's mass may be split among bundles.
Let \(L\) be the total input bit length, including the bundle lists; state running times in \(m,\tau,L\).
Is this continuous bundle-allocation feasibility problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finitely many agents and indivisible, nonshareable resources, deciding whether every agent can receive utility at least \(K\) under this bundle representation is \(\mathrm{NP}\)-complete; the Nash-product threshold problem is also \(\mathrm{NP}\)-complete. [Roos and Rothe](https://ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/13_05_FP_0328.pdf)
No result addressing exactly the mass model above was identified in the sources checked.
The problem is in \(\mathrm P\), including when utilities are negative and \({K\leq 0}\). Its running time is \((m+\tau+L)^{O(1)}\) in the binary bit model.
The main issue is that when \({K\leq 0}\), exponentially many omitted bundles may be acceptable. Nevertheless, a polynomial-size family of acceptable bundles suffices, because unused supply is permitted.
For a finite resource set \(R\), let \(\mathcal F\subseteq 2^R\) be a family of forbidden bundles. Define the candidate family
\(\displaystyle \mathcal C(\mathcal F) = \{\,\varnothing:\varnothing\notin\mathcal F\,\} \;\cup\; \{\,F\cup\{r\}:F\in\mathcal F,\ r\in R\setminus F,\ F\cup\{r\}\notin\mathcal F\,\}. \)
Lemma. Every bundle in \(\mathcal C(\mathcal F)\) is acceptable, and every acceptable bundle \(B\notin\mathcal F\) contains some \(C\in\mathcal C(\mathcal F)\). Moreover,
\(\displaystyle |\mathcal C(\mathcal F)|\leq 1+m|\mathcal F|.\)
Proof. Acceptability follows directly from the definition. To prove the containment property, choose a subset \(C\subseteq B\) of minimum cardinality among those outside \(\mathcal F\). Such a subset exists because \(B\notin\mathcal F\).
If \(C=\varnothing\), then \(C\) belongs to the first part of the candidate family. Otherwise, choose any \(r\in C\). Minimality implies \(F=C\setminus\{r\}\in\mathcal F\). Consequently, \(C=F\cup\{r\}\) belongs to the second part.
There is at most one empty-bundle candidate and at most \(m\) generated candidates for each forbidden bundle. Removing duplicates can only decrease the count. This proves the bound. \(\square\)
Let \(n_t\) be the number of explicitly listed bundle–value pairs for type \(t\), and let \(n=\sum_{t\in T}n_t\). Since every pair occupies input bits, \(n\leq L\).
Every omitted bundle has utility \(0<K\), so every acceptable bundle must be explicitly listed. Define
\(\displaystyle \mathcal C_t=\{\,B:\text{$B\) is explicitly listed for type \(t\) and }u_t(B)\geq K\,\}.\)
This is the complete acceptable family, and \(|\mathcal C_t|\leq n_t\).
Every omitted bundle has utility \(0\geq K\). Thus the forbidden family is exactly
\(\displaystyle \mathcal F_t=\{\,B:\text{$B\) is explicitly listed for type \(t\) and }u_t(B)<K\,\}.\)
In particular, \(|\mathcal F_t|\leq n_t\). Set \(\mathcal C_t=\mathcal C(\mathcal F_t)\), using the lemma. Then:
This includes the specified or default utility of the empty bundle. If every type accepts the empty bundle, feasibility is immediate; the construction also handles the cases in which some types forbid it.
Consider the following linear feasibility problem, with variables \(y_{tC}\) for \(t\in T\) and \(C\in\mathcal C_t\):
Proposition. This linear program is feasible if and only if the original allocation problem is feasible.
Proof. A feasible candidate allocation gives an original allocation by setting all variables for bundles outside the candidate families to zero. Every candidate is acceptable, and the mass and supply constraints are identical.
Conversely, suppose \(x_{tB}\) is an original feasible allocation. For every acceptable bundle \(B\) of type \(t\), choose a candidate \(\phi_t(B)\subseteq B\). Such a choice exists by Section 2: for \(K>0\), choose \(B\) itself; for \(K\leq 0\), use the lemma.
Define
\(\displaystyle y_{tC}= \sum_{\substack{B\subseteq R:\ u_t(B)\geq K\\\phi_t(B)=C}}x_{tB}. \)
These are finite sums of nonnegative real numbers. Every acceptable bundle is mapped to exactly one candidate, and unacceptable bundles have zero allocated mass. Hence
\(\displaystyle \sum_{C\in\mathcal C_t}y_{tC}=\sum_{B\subseteq R}x_{tB}=\mu_t.\)
For each resource \(r\), containment \(\phi_t(B)\subseteq B\) gives
\(\displaystyle \sum_{t\in T}\sum_{\substack{C\in\mathcal C_t\\r\in C}}y_{tC} = \sum_{t\in T}\sum_{\substack{B\subseteq R\\u_t(B)\geq K}} \mathbf 1_{\{r\in\phi_t(B)\}}x_{tB} \leq \sum_{t\in T}\sum_{\substack{B\subseteq R\\r\in B}}x_{tB} \leq b_r. \)
Thus the candidate allocation is feasible. This replacement uses precisely the permission to leave supply unused: replacing a bundle by a subset never increases consumption. \(\square\)
If any \(\mathcal C_t\) is empty, reject immediately: its mass constraint cannot hold because \(\mu_t>0\). Otherwise, let \(N=\sum_t|\mathcal C_t|\). The bounds above give
\(\displaystyle N\leq \begin{cases} n,&K>0,\\ \tau+mn,&K\leq 0. \end{cases} \)
The candidate families can be constructed deterministically in polynomial time. Represent bundles by their \(m\)-bit incidence vectors. For \(K\leq 0\), generate every one-resource extension of every forbidden bundle, test membership in the forbidden family, and remove duplicates. There are at most \(mn\) generated extensions in total. Binary tries permit each membership or insertion operation in \(O(m)\) steps. Rational comparisons with \(K\) also take polynomial bit time in \(L\).
The resulting linear program has \(N\) variables, \(\tau\) mass equalities, and \(m\) supply inequalities, besides nonnegativity. Its matrix entries are \(0\) or \(1\); its right-hand sides are the original binary rational masses and supplies. A dense encoding therefore has bit length
\(\displaystyle S=O\bigl(L+(m+\tau)N\bigr).\)
The standard polynomial-time theorem for rational linear programming decides feasibility over the reals in time polynomial in the total binary encoding length. It applies to equalities, inequalities, and nonnegative variables, including feasible sets of lower dimension. See [Goemans’s linear programming notes, Sections 11–13](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
All its hypotheses hold here. Since \(n\leq L\), construction and solution together take
\(\displaystyle \operatorname{poly}\!\left(L+(m+\tau)\bigl(\tau+(m+1)L\bigr)\right) =(m+\tau+L)^{O(1)} \)
bit time. Only the \(\tau\) supported types are used.
The continuous feasibility problem is polynomial-time solvable for the full stated representation. Splitting type masses yields a linear feasibility problem, and the lemma eliminates the apparent exponential obstacle caused by acceptable omitted bundles. The cited hardness for indivisible allocations therefore does not establish hardness for this mass model.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated problem correctly. The candidate-family lemma, the feasibility equivalence, and the polynomial bit-complexity argument all stand. I found no major or minor issues requiring repair.
The proof addresses the full representation in USER_TASK: supported types with positive rational masses, rational supplies, explicitly listed nonzero utilities, default utility zero, arbitrary rational threshold, and permission to leave supply unused.
The distinction between \(K>0\) and \(K\leq 0\) is exhaustive and correctly identifies when omitted bundles are acceptable. No nonnegativity or monotonicity assumption on utilities is introduced.
Every generated candidate lies outside \(\mathcal F\), by the explicit membership checks in its definition.
For any \(B\notin\mathcal F\), the minimum-cardinality choice exists because \(B\) has finitely many subsets and \(B\) itself is eligible. If the chosen \(C\) is nonempty, deleting any \(r\in C\) gives a strictly smaller subset of \(B\). Minimality therefore implies \(C\setminus\{r\}\in\mathcal F\). The resulting extension satisfies every condition in the definition of \(\mathcal C(\mathcal F)\).
The count \(1+m|\mathcal F|\) is valid: each forbidden bundle generates at most \(m\) extensions, and deduplication only reduces the size.
The lemma does not assume that acceptability is closed under taking subsets. It proves exactly the weaker containment property subsequently used.
For \(K>0\), every omitted bundle is unacceptable, so filtering the explicit list produces the entire acceptable family.
For \(K\leq 0\), every omitted bundle is acceptable. Consequently, the forbidden family consists exactly of explicitly listed bundles whose values are strictly below \(K\). This correctly handles negative values and the boundary \(u_t(B)=K\).
The empty bundle is treated according to its specified or default utility. The bounds \(|\mathcal C_t|\leq n_t\) and \(|\mathcal C_t|\leq 1+mn_t\) follow from the preceding arguments.
The forward implication is correct: a candidate allocation extends to the original variable set by assigning zero mass elsewhere.
For the reverse implication, the containment property supplies a choice \(\phi_t(B)\subseteq B\) for every acceptable bundle. There are finitely many bundles, so the aggregation defining \(y_{tC}\) involves finite sums.
The mass calculation is exact: every acceptable bundle contributes to exactly one candidate, and unacceptable bundles have zero mass.
The resource inequality is also correct. For each resource \(r\), containment gives
\[
\mathbf 1_{\{r\in\phi_t(B)\}}\leq \mathbf 1_{\{r\in B\}}.
\]
Multiplication by nonnegative allocated masses and summation preserve this inequality. Thus replacement cannot exceed any supply bound.
This argument uses the stated permission to leave resources unused and does not require preservation of utility values beyond meeting the threshold.
Since every listed pair occupies input bits, \(n\leq L\) is justified. Summing the per-type bounds yields the stated bounds on \(N\).
Enumerating one-resource extensions requires at most \(mn\) generated bundles. Incidence-vector construction, forbidden-family membership checks, and deduplication are all polynomial in \(m,\tau,L\). Exact comparisons between binary rationals also have polynomial bit complexity.
The linear program has the stated dimensions and rational data. Its dense encoding bound
\[
S=O\bigl(L+(m+\tau)N\bigr)
\]
accounts for the coefficient matrix and original right-hand sides; nonnegativity and dimension information do not invalidate this bound.
Substitution of \(n\leq L\) gives the claimed running time \((m+\tau+L)^{O(1)}\).
The prover states the needed theorem sufficiently precisely: feasibility of an explicitly encoded rational linear program over the reals is decidable in polynomial time in its binary encoding length, including equalities and nonnegative variables.
Its hypotheses hold here. All constraints are linear, all coefficients and right-hand sides are rational, and the system has polynomial encoding length. Lower-dimensional feasible sets do not introduce an extra hypothesis.
The cited [Goemans notes, Sections 11–13](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf) support the encoding-length framework, equivalent constraint forms, and polynomial-time solvability of linear programming.
An empty candidate family correctly forces rejection because its type has strictly positive mass. Zero supplies require no special treatment. If \(m=0\), the empty bundle is the only bundle, and the construction still gives the correct acceptance or rejection. No valid input has \(\tau=0\), because the masses must sum to one.
The proof establishes membership in \(\mathrm P\) for the complete stated model. Its final observation about indivisible-allocation hardness is justified: that cited result does not classify this different feasibility problem.
No additional clarification is needed.
⟨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.