Answer: Polynomial-time solvable 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 even if the sharing graph is a clique.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\), finite resource-class set \(\mathcal R\), rational society distribution \(\mu\), integral initial bundle \(B_\theta\) and additive utility vector \(u_\theta\) for each type, fixed \(b\ge2\), and threshold \(k\), with per-capita resource supply \(q_r=\sum_{\theta\in\Theta}\mu_\theta b_{\theta r}\), decide whether there is a measurable mass assignment to integral local sharing configurations such that every individual retains its initial bundle, participates in at most \(b\) sharings, each resource token is shared with at most one recipient, any two types may share, and final utility is at least \(k\) for \(\mu\)-almost every agent; equivalently, maximize the essential minimum final utility.
A society is given by its support: the list of the \(\tau\) types \(\Theta\) with positive masses \(\mu_\theta\) encoded as binary rationals, with \(\sum_\theta\mu_\theta=1\). Each type represents an atomless population; \(\tau\) is the support size, not the number of possible types.
There are \(m=|\mathcal R|\) resource classes. Each type has an initial bundle \(B_\theta=(b_{\theta r})_{r\in\mathcal R}\in\mathbb N_0^m\) of distinct tokens and additive utilities \(u_{\theta r}\in\mathbb N_0\). Bundle counts, utilities, and threshold \(k\in\mathbb N_0\) are binary encoded; \(L\) is the total input bit length. Fix an integer \(b\ge2\).
A sharing gives one initially owned token to one other individual's access, while its owner retains access; both obtain their full utility. Tokens cannot be shared again or relayed. Any distinct individuals may share, including individuals of the same type. Each individual may give and receive at most \(b\) tokens in total; multiple tokens shared with one partner count separately. There are no sharing costs.
An integral local configuration \(C=(D,I)\) for type \(\theta\) specifies nonnegative integer counts \(D_{\phi r}\) of owned class-\(r\) tokens shared to type \(\phi\), and \(I_{\phi r}\) of class-\(r\) tokens received from owners of type \(\phi\), with \(\sum_\phi D_{\phi r}\le b_{\theta r}\) and \(\sum_{\phi,r}(D_{\phi r}+I_{\phi r})\le b\). Its final utility is \(U_\theta(C)=\sum_r u_{\theta r}(b_{\theta r}+\sum_\phi I_{\phi r})\).
A mass assignment consists of nonnegative real masses \(x_{\theta C}\) on these implicitly defined configurations, satisfying \(\sum_C x_{\theta C}=\mu_\theta\) and, for every \(\theta,\phi,r\), \(\sum_C x_{\theta C}D_{\phi r}(C)=\sum_C x_{\phi C}I_{\theta r}(C)\). These equalities match outgoing and incoming sharing incidences; all tokens are initially owned, with per-capita supply \(q_r=\sum_\theta\mu_\theta b_{\theta r}\). Feasibility requires \(U_\theta(C)\ge k\) whenever \(x_{\theta C}>0\), so the bound holds almost everywhere, rather than merely in expectation.
For each fixed \(b\ge2\), is deciding whether such a feasible mass assignment exists solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
The finite-agent counterpart is NP-hard for every fixed \(b\ge2\), even with unrestricted pairwise sharing; with \(b=1\), it is polynomial-time solvable by matching. [Source](https://www.jair.org/index.php/jair/article/download/15001/26992/37188).
No result settling this exact atomless, integral-local-configuration problem was located in the literature search.
For every fixed \(b\ge 2\), the decision problem is solvable in time polynomial in \(m,\tau,L\).
The proof enumerates all integral local configurations and then solves an exact rational linear feasibility problem. The number of configurations is polynomial because \(b\) is fixed.
For a fixed type \(\theta\), a configuration has \(2\tau m\) nonnegative integer coordinates: the outgoing counts \(D_{\phi r}\) and incoming counts \(I_{\phi r}\). Their total is at most \(b\).
Let \(d=2\tau m\). The number of nonnegative integer vectors with \(d\) coordinates and coordinate sum at most \(b\) is
\(\displaystyle \binom{d+b}{b}.\)
Indeed, adjoining a slack coordinate equal to \(b\) minus the coordinate sum gives a bijection with the nonnegative integer vectors having \(d+1\) coordinates and sum exactly \(b\); stars and bars gives the stated count. This also covers \(d=0\), when there is one empty vector.
For fixed \(b\), this count is polynomial in \(m,\tau\). An explicit enumeration procedure lists all multisets of size \(b\) over the \(d\) coordinate labels and one slack label. The multiplicity of each coordinate label gives its count.
For each type \(\theta\), retain precisely the candidates satisfying both:
Denote the resulting set by \(\mathcal C_\theta\). By construction, it contains exactly the integral local configurations that obey the incidence bound, the ownership restrictions, and the required utility threshold.
Consequently, the total number of retained configurations satisfies
\(\displaystyle N:=\sum_{\theta\in\Theta}|\mathcal C_\theta|\le \tau\binom{2\tau m+b}{b}.\)
No enumeration up to the numerical values of the bundle counts or utilities is needed.
Introduce a nonnegative real variable \(x_{\theta C}\) for every \(\theta\in\Theta\) and \(C\in\mathcal C_\theta\). Impose the type-mass equations
\(\displaystyle \sum_{C\in\mathcal C_\theta}x_{\theta C}=\mu_\theta \qquad(\theta\in\Theta),\)
and the incidence-balance equations
\(\displaystyle \sum_{C\in\mathcal C_\theta}x_{\theta C}D_{\phi r}(C)=\sum_{C\in\mathcal C_\phi}x_{\phi C}I_{\theta r}(C)\qquad(\theta,\phi\in\Theta,\ r\in\mathcal R).\)
There are \(N\) variables and \(\tau+\tau^2m\) equations, together with nonnegativity constraints. If some \(\mathcal C_\theta\) is empty, its mass equation is impossible because \(\mu_\theta>0\), so the algorithm may immediately reject.
Equivalence. Suppose first that the original instance has a feasible mass assignment. Every configuration receiving positive mass satisfies the ownership restrictions, incidence bound, and utility threshold; hence it belongs to \(\mathcal C_\theta\). Restricting the assignment to the retained configurations therefore satisfies the displayed linear program.
Conversely, suppose the linear program has a feasible solution. Assign its values to the retained configurations and assign zero mass to every other configuration. The displayed equations are exactly the required mass and incidence-balance equations. Every configuration assigned positive mass belongs to \(\mathcal C_\theta\), so its utility is at least \(k\). Thus this is a feasible mass assignment in the sense of the question.
In particular, the utility guarantee holds configuration by configuration. The linear program does not replace it with an expected-utility constraint.
The per-capita token supply also requires no additional constraint. For each resource class \(r\), the total outgoing incidence mass satisfies
\(\displaystyle \sum_{\theta\in\Theta}\sum_{C\in\mathcal C_\theta}x_{\theta C}\sum_{\phi\in\Theta}D_{\phi r}(C)\le \sum_{\theta\in\Theta}\mu_\theta b_{\theta r}=q_r.\)
This follows from the ownership restriction in each retained configuration and the type-mass equations. Summing the balance equations shows that the total incoming incidence mass equals this outgoing mass.
Configuration enumeration and filtering take polynomial time for fixed \(b\). Each coordinate is at most \(b\). Ownership checks compare such small counts against binary-encoded bundle counts.
Utility checks use exact integer arithmetic. Each product \(u_{\theta r}b_{\theta r}\) has bit length at most the sum of the bit lengths of its factors. Summing over the resource classes adds at most a logarithmic number of bits. The incoming utility contribution contains at most \(b\) incidences. Thus every utility check uses numbers of bit length polynomial in the input length, even when the numerical bundle counts and utilities are large.
All linear-program coefficients are integers of absolute value at most \(b\), apart from the rational right-hand sides \(\mu_\theta\). To check the coefficient bound explicitly, in the balance row indexed by \((\theta,\phi,r)\), the coefficient of \(x_{\gamma C}\) is
\(\displaystyle \mathbf 1_{\gamma=\theta}D_{\phi r}(C)-\mathbf 1_{\gamma=\phi}I_{\theta r}(C).\)
For \(\theta=\phi=\gamma\), this becomes \(D_{\theta r}(C)-I_{\theta r}(C)\), which still has absolute value at most \(b\). Thus same-type sharing is included without changing the size bound.
The matrix dimensions and its total rational encoding length are consequently polynomial in \(m,\tau,L\) for fixed \(b\).
We now apply the standard polynomial-time theorem for rational linear programming: feasibility of a finite system of non-strict linear inequalities with rational coefficients can be decided in time polynomial in its total binary encoding length. Equalities are replaced by pairs of inequalities. The theorem decides feasibility over the reals and applies also to systems whose feasible set has empty interior. See [Khachiyan, “Polynomial algorithms in linear programming”](https://doi.org/10.1016/0041-5553(80)90061-0).
All its hypotheses hold here: the system is explicit, finite, rational, and of polynomial encoding length. Solving it therefore decides the original problem in polynomial time.
The argument preserves the integrality of every individual's local configuration. Only the masses assigned to configurations are real-valued, exactly as the problem specifies.
For a finite population, assigning integral numbers of individuals to configurations would impose additional integrality restrictions on those masses. The present linear program permits an atomless type population to split among configurations. Therefore the polynomial-time result does not imply a polynomial-time algorithm for the stated finite-agent counterpart.
The same proof works for every fixed nonnegative incidence bound; the requested cases \(b\ge 2\) are fully settled.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time decidability for every fixed \(b\ge 2\). The enumeration is polynomial, the linear program is exactly equivalent to the mass-assignment problem stated in USER_TASK, and its binary encoding length is polynomial. No mathematical gaps or false steps were found.
For each type, the prover correctly identifies \(d=2\tau m\) nonnegative integer coordinates. The incidence constraint bounds their combined sum by \(b\), including both outgoing and incoming incidences.
The slack-coordinate argument is valid: adjoining the uniquely determined slack \(b-\sum_{\phi,r}(D_{\phi r}+I_{\phi r})\) gives a bijection with nonnegative integer vectors of length \(d+1\) and sum exactly \(b\). The resulting count \(\binom{d+b}{b}\) is correct, including \(d=0\).
For fixed \(b\), this count is polynomial in \(m,\tau\). The proposed multiset enumeration produces every candidate and can be performed within polynomial time.
The two filtering conditions are precisely the remaining configuration requirements:
Consequently, the assertion that \(\mathcal C_\theta\) contains exactly the admissible configurations meeting the threshold is justified. The total bound \(N\le\tau\binom{2\tau m+b}{b}\) follows.
The type-mass equations reproduce the required population masses.
The balance equation indexed by \((\theta,\phi,r)\) correctly matches tokens sent by type \(\theta\) to type \(\phi\) with tokens received by type \(\phi\) from type \(\theta\). Its indices agree with USER_TASK.
Both directions of the equivalence are valid:
The threshold is enforced individually for each supported configuration; there is no substitution of an expected-utility condition.
The requested decision object is explicitly a mass assignment satisfying these equations. Accordingly, no additional theorem constructing individual sharing partners is needed to establish the stated target.
The supply inequality is correctly derived from configuration-level ownership constraints and the type-mass equations. Summing the incidence-balance equations correctly equates total incoming and outgoing incidence mass.
Thus no separate aggregate supply constraint is missing.
The coefficient formula
\(\mathbf 1_{\gamma=\theta}D_{\phi r}(C)-\mathbf 1_{\gamma=\phi}I_{\theta r}(C)\)
is correct. When all three type indices coincide, the coefficient is \(D_{\theta r}(C)-I_{\theta r}(C)\). Its absolute value is at most \(b\), so same-type sharing introduces neither an indexing error nor a larger coefficient.
Enumeration depends on the fixed incidence bound, rather than on the numerical magnitudes of binary-encoded bundle counts or utilities. This distinction is essential and is handled correctly.
Ownership checks use polynomial-length integers. Utility calculations also have polynomial bit complexity: multiplication adds the operand bit lengths up to a constant, and summing the resource contributions increases the necessary length by at most a logarithmic amount in the number of terms. Zero operands cause no difficulty.
The LP has polynomially many variables and equations. Its integer coefficients have absolute value at most \(b\), including the type-mass coefficients because \(b\ge2\). The rational right-hand sides are supplied in the input. Hence the explicit rational system has polynomial total encoding length.
The prover states the required theorem precisely: feasibility of finite non-strict rational linear inequalities is decidable in polynomial time in their total binary encoding length, including feasible systems with empty interior.
This is the applicable standard rational linear-programming theorem. The cited [Khachiyan publication](https://www.sciencedirect.com/science/article/pii/0041555380900610) is correctly identified; a contemporaneous research article also explicitly presents polynomial-time satisfiability testing for linear inequalities. [“Khachiyan's linear programming algorithm”](https://www.sciencedirect.com/science/article/pii/0196677480900024)
Every hypothesis is satisfied as written. Replacing equalities by two inequalities preserves feasibility and polynomial encoding length. Nonnegativity constraints are non-strict rational inequalities. There is therefore no unverified theorem application.
The proof preserves integral local configurations while allowing real configuration masses, exactly as required. Its explanation of why this does not settle the finite-agent counterpart is consistent with the argument.
The requested fixed bounds are fully covered. The extension to other fixed nonnegative incidence bounds does not undermine the conclusion.
Required clarification or repair: none.
⟨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.