Answer: Polynomial-time solvable (\(\mathrm{P}\)), with running time polynomial in \(m,\tau,L\).
Theorem 3 — class: hardness
Given a finite type set \(T\), rational distribution \(\mu\), \(m\) resource kinds, common values \(\alpha>\beta>\gamma\ge0\), type utilities \(u_t(o)\in\{\alpha,\beta,\gamma\}\), and initial bundles \(e_t\in\{0,1\}^m\), define \(u_t(B)=\sum_o u_t(o)B_o\) and \(s_o=\sum_{t\in T}\mu_t e_t(o)\). Decide whether there exist masses \(x_{t,B}\ge0\), for \(B\in\{0,1\}^m\), satisfying \(\sum_B x_{t,B}=\mu_t\), \(\sum_{t,B}x_{t,B}B_o=s_o\), \(u_t(B)\ge u_t(e_t)\) whenever \(x_{t,B}>0\), and \(u_t(B)>u_t(e_t)\) for positive total mass.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) resource kinds. The input includes common binary rational values \(\alpha>\beta>\gamma\ge0\), utilities \(u_t(o)\in\{\alpha,\beta,\gamma\}\), and initial bundles \(e_t\in\{0,1\}^m\). Let \(L\) be the total input bit length.
Each individual receives a bundle \(B\in\{0,1\}^m\), with utility \(u_t(B)=\sum_{o=1}^m u_t(o)B_o\); bundle sizes may change. Resource supplies are exactly \(s_o=\sum_t\mu_t e_t(o)\).
A mass reallocation consists of real numbers \(x_{t,B}\ge0\) satisfying \(\sum_Bx_{t,B}=\mu_t\) for every type and \(\sum_{t,B}x_{t,B}B_o=s_o\) for every resource kind.
It is a Pareto improvement if \(x_{t,B}>0\) implies \(u_t(B)\ge u_t(e_t)\), and \(\sum_{(t,B):\,u_t(B)>u_t(e_t)}x_{t,B}>0\).
Is deciding whether such a mass Pareto improvement exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite agents and indivisible objects, testing Pareto optimality is strongly \(\mathrm{coNP}\)-complete even with three common utility values; equivalently, deciding whether a Pareto improvement exists is strongly \(\mathrm{NP}\)-complete. [Aziz et al.](https://www.lamsade.dauphine.fr/~lang/papers/ABLLM19.pdf)
No result settling the exact mass problem above was identified in the literature search.
The stated mass Pareto-improvement problem belongs to \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
The key is that a bundle’s utility is determined by three counts. For each count triple, the possible resource marginals have an exact polynomial-size linear description. Thus we can optimize over mixtures while ensuring that every bundle used, rather than merely the average bundle, meets its type’s initial utility.
For each type \(t\) and value \(v\in\{\alpha,\beta,\gamma\}\), define
\(G_{t,v}=\{o:u_t(o)=v\}\) and \(n_{t,v}=|G_{t,v}|\).
These three sets partition the resource kinds.
Write \(U_t=u_t(e_t)\). For a count triple \(k=(k_\alpha,k_\beta,k_\gamma)\), define
\(V(k)=\alpha k_\alpha+\beta k_\beta+\gamma k_\gamma\).
Let
\(K_t=\{k\in\mathbb Z_{\ge0}^3:k_v\le n_{t,v}\text{ for every }v,\ V(k)\ge U_t\}\).
A binary bundle \(B\) is admissible for type \(t\) precisely when its counts
\(k_v=\sum_{o\in G_{t,v}}B_o\)
form a triple in \(K_t\). Every bundle with that triple has utility \(V(k)\), so it strictly improves utility precisely when \(V(k)>U_t\).
There are at most
\(|K_t|\le(n_{t,\alpha}+1)(n_{t,\beta}+1)(n_{t,\gamma}+1)\le(m+1)^3\)
triples. They can be enumerated and classified using exact rational arithmetic in polynomial time.
Lemma. Let \(G_1,\ldots,G_d\) partition a finite coordinate set, and let \(k_1,\ldots,k_d\) be integers. Every vector \(p\) satisfying
\(0\le p_o\le1\) and \(\sum_{o\in G_i}p_o=k_i\) for every \(i\)
is a convex combination of binary vectors satisfying the same group-sum equalities.
Proof. Induct on the number of fractional coordinates of \(p\). If there are none, the assertion holds.
Otherwise, choose a fractional coordinate \(a\). Its group contains another fractional coordinate \(b\): exactly one fractional coordinate would make that group’s sum nonintegral.
Let \(h\) have coordinate \(1\) at \(a\), coordinate \(-1\) at \(b\), and zeros elsewhere. Define
\(r=\min\{1-p_a,p_b\}>0\) and
\(s=\min\{p_a,1-p_b\}>0\).
The vectors \(p^+=p+rh\) and \(p^-=p-sh\) remain in the coordinate bounds and preserve every group sum. Each has fewer fractional coordinates, because at least one of the two selected coordinates reaches a bound. Moreover,
\(p=\frac{s}{r+s}p^++\frac{r}{r+s}p^-\).
Apply the induction hypothesis to both vectors and combine their decompositions. This proves the lemma. \(\square\)
Consequently, for fixed \(t,k\), the conditions
\(0\le p_o\le1\) and
\(\sum_{o\in G_{t,v}}p_o=k_v\)
describe exactly the convex hull of binary bundles with count triple \(k\). This also covers empty groups.
For every \(t\) and \(k\in K_t\), introduce:
Impose the following linear constraints:
| Purpose | Constraint |
|---|---|
| Nonnegative class mass | \(z_{t,k}\ge0\) |
| Binary-bundle marginal bounds | \(0\le y_{t,k,o}\le z_{t,k}\) |
| Fixed counts within a class | \(\sum_{o\in G_{t,v}}y_{t,k,o}=k_vz_{t,k}\), for every \(v\in\{\alpha,\beta,\gamma\}\) |
| Preserve each type’s mass | \(\sum_{k\in K_t}z_{t,k}=\mu_t\) |
| Preserve each resource supply | \(\sum_t\sum_{k\in K_t}y_{t,k,o}=s_o\) |
Maximize
\(F(z)=\sum_t\sum_{\substack{k\in K_t\\V(k)>U_t}}z_{t,k}\).
The objective counts the mass receiving strictly better bundles.
Take any reallocation \(x\) whose positively assigned bundles satisfy their types’ utility thresholds. Let \(\mathcal B_{t,k}\) denote the binary bundles with count triple \(k\), and set
\(z_{t,k}=\sum_{B\in\mathcal B_{t,k}}x_{t,B}\),
\(y_{t,k,o}=\sum_{B\in\mathcal B_{t,k}}x_{t,B}B_o\).
Nonnegativity and the binary coordinates give
\(0\le y_{t,k,o}\le z_{t,k}\).
Every bundle in \(\mathcal B_{t,k}\) has exactly \(k_v\) coordinates in group \(G_{t,v}\), giving
\(\sum_{o\in G_{t,v}}y_{t,k,o}=k_vz_{t,k}\).
The remaining equalities follow from the reallocation’s type-mass and resource-supply equalities. Its strictly improved mass is exactly \(F(z)\).
Conversely, take any feasible LP solution. Whenever \(z_{t,k}>0\), define
\(p_{t,k,o}=y_{t,k,o}/z_{t,k}\).
The constraints give
\(0\le p_{t,k,o}\le1\) and
\(\sum_{o\in G_{t,v}}p_{t,k,o}=k_v\).
By the lemma, there are coefficients \(\lambda_{t,k,B}\ge0\), summing to \(1\), such that
\(p_{t,k}=\sum_{B\in\mathcal B_{t,k}}\lambda_{t,k,B}B\).
Assign mass \(z_{t,k}\lambda_{t,k,B}\) to bundle \(B\). Classes with \(z_{t,k}=0\) contribute nothing; their marginals are also zero by the upper bounds.
This construction preserves type mass. For every resource kind, its assigned mass is
\(\sum_t\sum_{k:z_{t,k}>0}z_{t,k}p_{t,k,o}
=\sum_t\sum_k y_{t,k,o}=s_o\).
Every assigned bundle belongs to a class \(k\in K_t\), hence has utility at least \(U_t\). Within each class, all bundles have utility \(V(k)\), so the strictly improved mass is exactly \(F(z)\).
Thus the two formulations are equivalent, including their strict-improvement criterion.
The LP has
\((m+1)\sum_t|K_t|\le\tau(m+1)^4\)
variables and \(O(\tau(m+1)^4)\) constraints.
Its coefficients are integers bounded in magnitude by \(m\), together with the rational right-hand sides \(\mu_t\) and \(s_o\). Computing supplies, initial utilities, and count-triple comparisons uses rational arithmetic with polynomial bit length. Therefore the entire LP has encoding length polynomial in \(m,\tau,L\); its size does not depend on the numerical magnitudes of the utility values.
The initial allocation supplies a feasible solution: put each type’s entire mass on the count triple of \(e_t\), with marginals \(\mu_te_t(o)\). Every feasible solution satisfies \(0\le z_{t,k}\le\mu_t\) and \(0\le y_{t,k,o}\le\mu_t\), so the feasible region is bounded.
We now apply the standard rational linear-programming theorem: a feasible, bounded LP with binary-encoded rational coefficients can be optimized exactly in time polynomial in its encoding length. Its hypotheses have all been verified here.
Let \(F^\star\) be the resulting rational optimum. The equivalence above proves
\(\text{a mass Pareto improvement exists}\Longleftrightarrow F^\star>0\).
Exact rational optimization permits this comparison directly, even if the positive optimum is very small.
The finite-agent hardness in [Aziz et al., Theorem 3](https://www.lamsade.dauphine.fr/~lang/papers/ABLLM19.pdf) requires assigning whole bundles to whole agents. The stated mass model permits splitting each type’s mass among several admissible bundles. The convex-decomposition lemma makes that permitted splitting exactly representable by the LP.
Hence the mass problem is polynomial-time solvable, despite the cited finite-agent hardness.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated mass problem correctly: it establishes polynomial-time solvability in \(m,\tau,L\). No major or minor mathematical issues were found.
The three sets \(G_{t,\alpha},G_{t,\beta},G_{t,\gamma}\) partition the resource kinds because the three utility values are distinct and every resource has one of those values.
For each binary bundle, its utility is exactly \(V(k)\), where \(k\) is its count triple. Consequently:
The bound \(|K_t|\le(m+1)^3\) is correct. Enumeration and threshold comparisons require polynomially many exact rational operations on numbers of polynomial bit length. No assumption that the utility values are small integers is needed.
The induction is valid.
The induction therefore yields a finite convex decomposition. The reverse convex-hull inclusion follows directly because binary vectors with the prescribed counts satisfy the bounds and equalities, which convex combinations preserve.
Empty groups are covered: their prescribed counts in \(K_t\) are zero, and their equalities impose no additional restriction.
Every constraint has the stated interpretation.
In particular, \(0\le y_{t,k,o}\le z_{t,k}\) correctly expresses binary-resource marginals within a class of mass \(z_{t,k}\). The group equalities enforce its prescribed counts after normalization.
The objective correctly measures strictly improved mass because every bundle in a class has the same utility. It does not substitute an average-utility condition for the required condition on every positively assigned bundle.
Reallocation to LP. Aggregating bundle masses and their resource incidences gives all stated LP constraints. Bundles outside \(K_t\) have zero mass under the assumed utility-threshold condition, so restricting the aggregation to admissible classes loses no mass. The objective equals the original strictly improved mass.
LP to reallocation. For every positive-mass class, normalization produces a vector satisfying the decomposition lemma. Its resulting bundle masses preserve the class mass and all resource marginals.
Zero-mass classes cause no division problem: their marginals are forced to zero by the bounds. Each bundle has a unique count triple for its type, so the class constructions define a consistent allocation.
All positively assigned bundles meet their utility thresholds, and their strictly improved mass is exactly \(F(z)\). Thus both directions preserve the precise improvement criterion in the task.
The decomposition is used only to establish existence. The decision algorithm does not need to enumerate its potentially large bundle representation.
The variable count
\[
(m+1)\sum_t|K_t|\le\tau(m+1)^4
\]
is correct, as is the stated asymptotic constraint count.
The LP coefficients have polynomial bit length. Summing binary rational masses to compute supplies, and computing utility thresholds and comparisons, also produces numbers of polynomial bit length. The explicit LP consequently has polynomial encoding length.
The initial allocation proves feasibility. The type-mass equations and nonnegativity give \(z_{t,k}\le\mu_t\), and the marginal bounds then bound every \(y_{t,k,o}\). The feasible region is closed and bounded, so the objective attains its optimum.
The rational linear-programming theorem is stated sufficiently precisely for this application, and its hypotheses are verified. Exact polynomial-time rational optimization supports the comparison \(F^\star>0\); numerical tolerances are not being used to decide strict positivity.
The argument handles \(m=1\), empty utility groups, \(\gamma=0\), zero or full resource supplies, and instances with no strictly improving admissible classes. None invalidates the construction or equivalence.
The cited finite-agent hardness statement matches Theorem 3 of [Aziz et al.](https://www.lamsade.dauphine.fr/~lang/papers/ABLLM19.pdf). It is contextual rather than a premise of the algorithm. The proof correctly distinguishes whole-agent assignments from the mass splitting allowed in the task.
No mathematical repair or additional clarification is required. The claimed polynomial-time classification is established for the exact support-based input and mass-reallocation model given.
⟨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.