Answer: \(\mathrm{NP}\)-hard for every fixed \(b\ge 2\)
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateb-EWSA is NP-hard for any constant b ≥2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types Θ with rational masses μ\(_\theta\), finite resource classes \(R\) with rational masses ρ\(_{\theta r}\) of repeated indivisible copies initially owned by type θ, additive utilities \(u_\theta(r)\), a typed relation ℐ specifying allowable owner-recipient pairs, fixed \(b\ge2\), and rational threshold \(q\), decide whether a mass distribution over legal sharing configurations exists in which initial ownership is preserved, each copy is shared with at most one neighbor while its owner keeps access, each agent has at most \(b\) sharing incidences, and \uoperatorname*{ess\,inf}\(_a\) \(u_{\operatorname{type}(a)}(B_a)\ge q\).
Let \(\Theta\) be finite agent types with rational masses \(\mu_\theta\), and let \(R\) be finite resource classes. Type \(\theta\) initially owns mass \(\rho_{\theta r}\) of indivisible copies of class \(r\), and has additive utility \(u_\theta(r)\).
A typed relation \(\mathcal I\subseteq\Theta\times\Theta\) permits a copy owned by type \(\theta\) to be shared with a recipient of type \(\phi\) only when \( (\theta,\phi)\in\mathcal I\). A legal configuration preserves ownership; each copy is shared with at most one recipient while its owner retains access; and each agent has at most \(b\) sharing incidences.
For an agent \(a\), let \(B_a\) be its access bundle after sharing. A feasible mass distribution of legal configurations must use the stated type-level resource masses and satisfy \(\operatorname*{ess\,inf}_a u_{\operatorname{type}(a)}(B_a)\ge q\).
For every fixed \(b\ge2\), is deciding whether such a feasible mass distribution exists solvable in polynomial time, or is it NP-hard?
For finite agents and indivisible resources, the corresponding \(b\)-bounded egalitarian-welfare sharing problem is NP-hard for every constant \(b\ge2\).
No verified result for precisely the typed mass formulation above is recorded here.
For every fixed \(b\ge 2\), the typed mass feasibility problem is \(\mathrm{NP}\)-hard. In fact, hardness already holds with:
Thus the finite-agent sharing reduction is unnecessary: the difficulty already arises from distributing indivisible ownership bundles among a continuous mass of identical agents.
Because ownership is specified only through the aggregate masses \(\rho_{\theta r}\), a no-sharing configuration of a type-\(\theta\) agent is an integral vector \(x\in\mathbb Z_{\ge 0}^{R}\), where \(x_r\) is the number of class-\(r\) copies owned by that agent.
For a single type of mass \(1\), a feasible mass distribution is therefore a probability distribution on integral bundle vectors satisfying
\[ \mathbb E[x_r]=\rho_{\theta r} \]
for every resource class \(r\), with utility at least \(q\) almost surely. This is exactly the type-level aggregate-ownership interpretation in the question.
We reduce from the standard \(\mathrm{NP}\)-complete problem \(\mathrm{PARTITION}\), whose input is a list of positive integers \(w_1,\ldots,w_n\) and whose question is whether some \(S\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in S}w_i=\frac12\sum_{i=1}^n w_i\). Its \(\mathrm{NP}\)-completeness is classical; see [Karp’s original paper](https://doi.org/10.1007/978-1-4684-2001-2_9).
Put
\[ W=\sum_{i=1}^n w_i,\qquad M=\max_i w_i,\qquad B=n+1. \]
For each \(i\in\{1,\ldots,n\}\), introduce two resource classes \(r_i^0,r_i^1\). Define
\[ T=\sum_{i=1}^n B^{i-1}, \qquad D=nM+W+1, \]
and
\[ L=DB^{n-1}+M, \qquad A=nL+DT+W+1. \]
There is one type \(\theta\), with mass
\[ \mu_\theta=1. \]
For every \(i\) and \(s\in\{0,1\}\), set
\[ \rho_{\theta,r_i^s}=\frac12 \]
and
\[ u_\theta(r_i^s)=A+DB^{i-1}+s w_i. \]
Finally, set
\[ q=nA+DT+\frac W2. \]
Take the typed sharing relation to be empty. Hence every legal configuration has zero sharing incidences and satisfies every fixed bound \(b\ge 0\).
All constructed numbers have polynomial binary encoding length: \(B^{n-1}\) has \(O(n\log n)\) bits, and all subsequent arithmetic increases the encoding length only polynomially.
Let \(x=(x_i^s)_{i,s}\in\mathbb Z_{\ge0}^{2n}\) be any integral bundle satisfying
\[ \sum_{i=1}^n\sum_{s=0}^1 u_\theta(r_i^s)x_i^s=q. \]
Then there is a set \(S\subseteq\{1,\ldots,n\}\) satisfying
\[ \sum_{i\in S}w_i=\frac W2. \]
Let
\[ k=\sum_{i=1}^n\sum_{s=0}^1x_i^s \]
be the total number of copies in the bundle. Each utility coefficient equals \(A\) plus a nonnegative quantity of at most \(L\).
First suppose \(k\ge n+1\). Then the bundle utility is at least \((n+1)A\). Because \(A>DT+W/2\),
\[ (n+1)A>nA+DT+\frac W2=q, \]
contradicting equality.
Now suppose \(k\le n-1\). Its utility is at most
\[ kA+kL\le kA+nL<kA+A\le nA<q, \]
where \(nL<A\) follows from the definition of \(A\). This again contradicts equality. Consequently,
\[ k=n. \]
Define
\[ c_i=x_i^0+x_i^1. \]
After cancelling the contribution \(nA\), the utility equality becomes
\[ D\left(\sum_{i=1}^n B^{i-1}c_i-T\right) + \left(\sum_{i=1}^n w_i x_i^1-\frac W2\right) =0. \]
Because the bundle contains exactly \(n\) copies,
\[ 0\le \sum_{i=1}^n w_i x_i^1\le nM. \]
Therefore
\[ \left|\sum_{i=1}^n w_i x_i^1-\frac W2\right|<D. \]
The first parenthesized expression is an integer. If it were nonzero, its contribution would have absolute value at least \(D\), too large to be cancelled by the second term. Hence
\[ \sum_{i=1}^n B^{i-1}c_i=T \]
and
\[ \sum_{i=1}^n w_i x_i^1=\frac W2. \]
Moreover, \(\sum_i c_i=n\), so each \(c_i\) lies in \(\{0,\ldots,n\}=\{0,\ldots,B-1\}\). Thus \((c_1,\ldots,c_n)\) is a valid base-\(B\) digit vector. Since \(T\) has base-\(B\) digits all equal to \(1\), uniqueness of base-\(B\) expansion gives
\[ c_i=1 \]
for every \(i\). Therefore each \(x_i^1\) belongs to \(\{0,1\}\). Taking
\[ S=\{i:x_i^1=1\} \]
gives \(\sum_{i\in S}w_i=W/2\), as required. \(\square\)
Suppose \(S\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in S}w_i=W/2\).
Define a bundle \(x^S\) that contains \(r_i^1\) when \(i\in S\), and \(r_i^0\) when \(i\notin S\). Its utility is exactly
\[ nA+DT+\sum_{i\in S}w_i=q. \]
Define \(x^{\overline S}\) by making the opposite choice for every \(i\). Since the complement also has total weight \(W/2\), this second bundle also has utility exactly \(q\).
Assign mass \(1/2\) to each of these two configurations. Every class \(r_i^s\) then has expected multiplicity \(1/2\), exactly matching its prescribed mass. Every agent obtains utility \(q\), and there are no sharing incidences. Thus the constructed instance is feasible.
Conversely, suppose a feasible mass distribution exists. Let \(X\) be the integral ownership bundle of a randomly selected type-\(\theta\) agent.
Resource balance gives
\[ \mathbb E[X_i^s]=\frac12 \]
for every \(i,s\). By additivity and the finiteness of the resource-class set,
\[ \mathbb E[u_\theta(X)] = \sum_{i=1}^n\sum_{s=0}^1 u_\theta(r_i^s)\mathbb E[X_i^s] = \frac12\sum_{i=1}^n\sum_{s=0}^1u_\theta(r_i^s) =q. \]
Feasibility gives \(u_\theta(X)\ge q\) almost surely. Hence the nonnegative random variable \(u_\theta(X)-q\) has expectation zero, so
\[ u_\theta(X)=q \]
almost surely.
Applying the encoding lemma to any bundle in this full-measure set yields a subset \(S\) with total weight \(W/2\). Therefore the original \(\mathrm{PARTITION}\) instance is affirmative.
The construction is a polynomial-time many-one reduction from \(\mathrm{PARTITION}\). It uses no sharing, so it is valid independently of the fixed incidence bound. Consequently, for every fixed \(b\ge2\), deciding feasibility in the stated typed mass formulation is \(\mathrm{NP}\)-hard.
The proof establishes weak \(\mathrm{NP}\)-hardness. It does not claim strong \(\mathrm{NP}\)-hardness or membership in \(\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes a polynomial-time many-one reduction from \(\mathrm{PARTITION}\) to the typed mass feasibility problem. The argument proves weak \(\mathrm{NP}\)-hardness for every fixed \(b\ge 2\), and in fact for every fixed \(b\ge 0\).
No substantive logical gap or false assertion was found.
With one type of mass \(1\) and no sharing, representing a mass distribution by a probability distribution over integral ownership vectors is consistent with the stated type-level aggregate-mass formulation:
\[ \mathbb E[x_r]=\rho_{\theta r}. \]
The incidence bound is vacuous because the sharing relation is empty. Ownership access is still retained, as required.
The stated version of \(\mathrm{PARTITION}\), with positive integer weights encoded in binary, is NP-complete. The cited Karp paper is bibliographically appropriate and includes Partition among its NP-complete problems. [Karp, “Reducibility Among Combinatorial Problems”](https://doi.org/10.1007/978-1-4684-2001-2_9)
Using \(\mathrm{PARTITION}\) establishes weak rather than strong NP-hardness, which the prover explicitly acknowledges.
The largest exponential-looking quantity is \(B^{n-1}\), whose binary length is
\[ (n-1)\log_2(n+1)=O(n\log n). \]
The quantities \(D,L,A,q\) are obtained through polynomially many arithmetic operations on polynomial-bit-length integers. Thus the reduction has polynomial output length and can be computed in polynomial time.
The threshold \(q\) may be half-integral when \(W\) is odd, but rational thresholds are allowed. This causes no problem.
Every coefficient has the form
\[ A+DB^{i-1}+s w_i, \]
with the non-\(A\) part lying between \(0\) and \(L\).
If \(k\ge n+1\), the utility is at least \((n+1)A\). Since
\[ A=nL+DT+W+1>DT+\frac W2, \]
one obtains
\[ (n+1)A>nA+DT+\frac W2=q. \]
If \(k\le n-1\), the utility is at most
\[ kA+kL\le kA+nL<kA+A\le nA<q. \]
All inequalities used here follow from the definitions. Therefore equality with \(q\) forces \(k=n\).
After cancelling \(nA\), the displayed equality is correct:
\[ D\left(\sum_i B^{i-1}c_i-T\right) + \left(\sum_i w_i x_i^1-\frac W2\right)=0. \]
Since the bundle contains \(n\) copies,
\[ 0\le \sum_i w_i x_i^1\le nM. \]
Moreover,
\[ \left|\sum_i w_i x_i^1-\frac W2\right|<nM+W+1=D. \]
Thus a nonzero integer value of the first parenthesis would contribute absolute value at least \(D\), which the second term cannot cancel. Both terms must therefore vanish.
This reasoning remains valid when \(W\) is odd: in that case the equality premise is simply impossible because the bundle utility is integral while \(q\) is half-integral.
The values \(c_i\) are nonnegative integers satisfying
\[ \sum_i c_i=n. \]
Consequently \(0\le c_i\le n=B-1\), so they are valid base-\(B\) digits. The equality
\[ \sum_i B^{i-1}c_i=\sum_i B^{i-1} \]
and uniqueness of base-\(B\) representation imply \(c_i=1\) for every \(i\). Hence \(x_i^1\in\{0,1\}\), and the vanishing of the weight term yields a valid partition.
Given a partition \(S\), the two complementary bundles each contain exactly one of \(r_i^0,r_i^1\) for every \(i\). Both have utility \(q\), because both \(S\) and its complement have weight \(W/2\).
Assigning mass \(1/2\) to each bundle gives expected multiplicity \(1/2\) for every resource class. Thus all aggregate masses, utility requirements, and incidence bounds are satisfied.
Resource balance implies
\[ \mathbb E[X_i^s]=\frac12. \]
Linearity of expectation gives
\[ \mathbb E[u_\theta(X)] = \frac12\sum_{i,s}u_\theta(r_i^s) = nA+DT+\frac W2 = q. \]
The finite number of resource classes and their finite expected multiplicities ensure that this expectation is well-defined and finite.
Since feasibility gives \(u_\theta(X)\ge q\) almost surely, the nonnegative integrable variable \(u_\theta(X)-q\) has expectation zero and must vanish almost surely. The encoding lemma then yields a partition.
The target is fully resolved as stated: the continuous typed mass feasibility problem is weakly NP-hard for every fixed \(b\ge2\). The proof does not establish membership in \(\mathrm{NP}\) or strong NP-hardness, but neither is required by the target.
⟨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.