Answer: \(\mathrm{NP}\)-complete for \(\tau=2\), even when \(\mu_1=\mu_2=1/2\), every \(q_g=1/2\), and \(s_{tg}\in\{0,1\}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any~$\mathcal{F}\in\{\text{tEF1},\text{EF1},\text{sEF1},\text{wEF1},\text{swEF1},\text{EFL}\}$, it is \NPc to decide whether a SIM and~$\mathcal F$-fair allocation exist, even if the social impact functions are binary and~$\numAgents = 2$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two agent types with rational masses μ_t, integral bundles of indivisible good types, rational per-capita supplies q_g, and additive valuations and social impacts, does there exist a distribution of each type’s mass over bundles that uses every supply, maximizes total social impact, and is EF1 between every pair of bundles receiving positive mass?
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here \(\tau=2\), with \(\mu_1+\mu_2=1\).
There are \(m\geq1\) good types, with binary rational per-capita supplies \(q_g\geq0\). Type \(t\) has binary-encoded nonnegative integer additive valuations \(v_{tg}\) and social impacts \(s_{tg}\).
An integral bundle is \(b\in\mathbb Z_{\geq0}^{m}\), including the empty bundle; write \(v_t(b)=\sum_g v_{tg}b_g\) and \(s_t(b)=\sum_g s_{tg}b_g\). Supplies constrain aggregate consumption, not individual bundle sizes.
An allocation assigns real masses \(x_{t,b}\geq0\), with \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\) for every good type. Countably supported distributions are allowed.
Its total social impact is \(\sum_{t,b}x_{t,b}s_t(b)\); social impact maximization is over all supply-feasible allocations, without imposing fairness.
Require EF1 for every ordered pair \((t,b),(u,c)\) with \(x_{t,b}>0\) and \(x_{u,c}>0\), including \(t=u\): either \(v_t(b)\geq v_t(c)\), or some \(g\) with \(c_g>0\) satisfies \(v_t(b)\geq v_t(c-e_g)\), where \(e_g\) is the unit vector for one copy of good type \(g\).
Is deciding whether such an EF1, globally social impact maximizing allocation exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau=2\), and the total input bit length \(L\).
For finite societies, this existence problem is NP-complete even with two agents and binary social impacts; a pseudopolynomial algorithm exists for every fixed number of agents. [Source](https://arxiv.org/html/2511.08160v2)
No result settling this exact mass-distribution problem was located in the literature search.
The problem is \(\mathrm{NP}\)-complete for \(\tau=2\). Hardness holds even when \(\mu_1=\mu_2=1/2\), every supply is \(q_g=1/2\), and all social impacts belong to \(\{0,1\}\).
The proof below handles unrestricted bundle multiplicities and countably supported allocations explicitly.
For each good \(g\), let \(S_g=\max\{s_{1g},s_{2g}\}\). Every supply-feasible allocation satisfies
\(\displaystyle \operatorname{SI}(x)\leq\sum_g S_gq_g.\)
This bound is attainable. Assign each good to a type attaining \(S_g\). Within that type, realize its required conditional mean \(q_g/\mu_t\) by mixing the floor and ceiling of this number. Taking the product of these finitely supported coordinate distributions gives a supply-feasible allocation attaining the bound.
Moreover, the difference from this bound equals
\(\displaystyle \sum_{t,b,g}x_{t,b}b_g(S_g-s_{tg}).\)
All summands are nonnegative. Consequently, an allocation is globally social impact maximizing if and only if every supported bundle uses only goods for which its recipient type maximizes social impact. These conclusions also hold for countable support: the sums are nonnegative, and finite supplies bound the objective.
For later use, define
\(\displaystyle h_t(c)=\max\bigl(\{v_{tg}:c_g>0\}\cup\{0\}\bigr).\)
The EF1 condition for an ordered pair \((t,b),(u,c)\) is exactly
\(\displaystyle v_t(b)\geq v_t(c)-h_t(c).\)
For a nonempty bundle, removing a copy with maximum value gives the smallest possible remaining value. For the empty bundle, the displayed inequality holds automatically.
We reduce from the \(\mathrm{NP}\)-complete PARTITION problem, also used in the supplied [finite-agent reduction](https://arxiv.org/html/2511.08160v2). Its input consists of positive integers \(a_1,\ldots,a_n\), with
\(\displaystyle \sum_{i=1}^n a_i=2A,\)
and asks whether some subset sums to \(A\). Restricting to even total preserves hardness: an odd-total instance can be mapped to the fixed no-instance \(1,3\).
Put \(a_{\max}=\max_i a_i\), and define
\(\displaystyle B=2n(a_{\max}+1)+2,\qquad H=B^{n+1}.\)
For each index \(i\), introduce two positive integer weights
\(\displaystyle w_i^+=H+B^i+a_i,\qquad w_i^-=H+B^i,\)
and set
\(\displaystyle T=nH+\sum_{i=1}^n B^i+A.\)
Their total is
\(\displaystyle \sum_i(w_i^++w_i^-)=2T.\)
Encoding lemma. Nonnegative integers \(c_i^+,c_i^-\) satisfy
\(\displaystyle \sum_i(w_i^+c_i^++w_i^-c_i^-)=T\)
if and only if
\(\displaystyle c_i^++c_i^-=1\quad\text{for every }i,\qquad \sum_i a_ic_i^+=A.\)
Proof. Write
\(\displaystyle N=\sum_i(c_i^++c_i^-),\quad k_i=c_i^++c_i^-,\quad P=\sum_i a_ic_i^+.\)
The assumed equation becomes
\(\displaystyle NH+\sum_i k_iB^i+P=nH+\sum_i B^i+A.\)
Because \(A<B\), the target’s terms below \(H\) form a valid base-\(B\) expansion and satisfy
\(\displaystyle \sum_i B^i+A<H.\)
Each weight is at least \(H\), so \(N\leq n\). Therefore
\(\displaystyle k_i\leq n<B,\qquad P\leq na_{\max}<B,\qquad N<B.\)
Thus the left side also has a base-\(B\) expansion with no carries: its leading digit is \(N\), its indexed digits are \(k_i\), and its units digit is \(P\). Uniqueness of base-\(B\) expansion gives \(N=n\), every \(k_i=1\), and \(P=A\).
Conversely, these conditions give the required weighted sum directly. \(\square\)
In particular, an integral bundle of encoded value \(T\) determines a PARTITION solution, even though repeated copies were initially permitted.
Create \(m=2n+2\) goods: common goods \(g_i^+,g_i^-\), and two anchor goods \(d_1,d_2\). Set
\(\displaystyle \mu_1=\mu_2=\frac12,\qquad q_g=\frac12\quad\text{for every good }g,\qquad C=2T+1.\)
The valuations and social impacts are:
| Good | \(v_{1g}\) | \(v_{2g}\) | \(s_{1g}\) | \(s_{2g}\) |
|---|---:|---:|---:|---:|
| \(g_i^+\) | \(w_i^+\) | \(w_i^+\) | \(1\) | \(1\) |
| \(g_i^-\) | \(w_i^-\) | \(w_i^-\) | \(1\) | \(1\) |
| \(d_1\) | \(0\) | \(C\) | \(1\) | \(0\) |
| \(d_2\) | \(C\) | \(0\) | \(0\) | \(1\) |
Since every common weight is positive and their total is \(2T\), each common weight is strictly smaller than \(C\).
Suppose an EF1, globally maximizing allocation exists.
By Section 1, only type \(1\) receives \(d_1\), and only type \(2\) receives \(d_2\). For any bundle \(b\), write its common-good value as
\(\displaystyle z(b)=\sum_i(w_i^+b_{g_i^+}+w_i^-b_{g_i^-}).\)
For a supported type-\(1\) bundle \(b\), let \(k_1(b)=b_{d_1}\). For a supported type-\(2\) bundle \(c\), let \(k_2(c)=c_{d_2}\). Anchor supplies imply
\(\displaystyle \sum_bx_{1,b}k_1(b)=\frac12,\qquad \sum_cx_{2,c}k_2(c)=\frac12.\)
Thus each type has at least one supported bundle containing its anchor.
Take any supported \(b,c\) with \(k_1(b)\geq1\) and \(k_2(c)\geq1\). From type \(1\)’s perspective, the most valuable removable copy in \(c\) is its anchor, worth \(C\). EF1 therefore gives
\(\displaystyle z(b)\geq z(c)+(k_2(c)-1)C.\)
The reverse ordered comparison gives
\(\displaystyle z(c)\geq z(b)+(k_1(b)-1)C.\)
Adding yields
\(\displaystyle 0\geq(k_1(b)+k_2(c)-2)C.\)
Both anchor counts are positive integers, so both equal \(1\). Pairing any bundle containing an anchor with an anchor-containing bundle of the other type shows that no supported bundle contains two or more anchors.
Each anchor count is consequently either \(0\) or \(1\). Its conditional mean within its owner type is \(1\), because both anchor supply and owner mass equal \(1/2\). Hence every supported bundle contains exactly one copy of its own anchor.
For arbitrary supported bundles \(b\) of type \(1\) and \(c\) of type \(2\), the two EF1 inequalities now reduce to
\(\displaystyle z(b)\geq z(c),\qquad z(c)\geq z(b).\)
All supported bundles therefore have one common value, say \(\lambda\). Supply feasibility gives
\(\displaystyle \sum_{t,b}x_{t,b}z(b)=\sum_i\frac{w_i^++w_i^-}{2}=T.\)
Since total population mass is \(1\), the left side equals \(\lambda\). Thus every supported bundle has common-good value \(T\).
The encoding lemma applies to any such bundle and yields a subset of the original numbers summing to \(A\).
This argument uses no finite-support assumption.
Conversely, suppose \(J\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in J}a_i=A\).
Let \(p\) contain one copy of \(g_i^+\) for \(i\in J\), and one copy of \(g_i^-\) otherwise. Let \(\bar p\) make the opposite choice at every index. Then
\(\displaystyle z(p)=z(\bar p)=T,\)
and together these bundles contain exactly one copy of every common good.
Assign mass \(1/4\) to each of
\(\displaystyle (1,p+e_{d_1}),\quad(1,\bar p+e_{d_1}),\quad(2,p+e_{d_2}),\quad(2,\bar p+e_{d_2}).\)
Each type has mass \(1/2\), and every good has aggregate consumption \(1/2\).
Within a type, all bundles have own value \(T\), so there is no envy. Across types, the compared bundle has value \(T+C\); removing its anchor leaves value \(T\). Thus every ordered comparison is EF1.
Every good is allocated to a social-impact maximizing type, so the allocation is globally maximizing.
The reduction is therefore correct in both directions.
We now prove membership in \(\mathrm{NP}\), including for general inputs admitting countably supported solutions.
Define
\(\displaystyle W_t=\sum_gv_{tg}q_g,\qquad M_t=\max_gv_{tg},\qquad U_t=\left\lfloor\frac{W_t}{\mu_t}\right\rfloor+M_t.\)
Suppose a fair optimal allocation exists. The own-type conditional mean valuation is at most \(W_t/\mu_t\). Since supported valuations are nonnegative integers, their minimum \(a_t\) exists and satisfies
\(\displaystyle a_t\leq\left\lfloor W_t/\mu_t\right\rfloor.\)
Comparing a type-\(t\) bundle attaining this minimum against any supported bundle \(c\), including bundles of the same type, gives
\(\displaystyle v_t(c)-h_t(c)\leq a_t.\)
Because \(h_t(c)\leq M_t\), every supported bundle satisfies
\(\displaystyle v_t(c)\leq U_t.\)
Consequently, if some type values good \(g\) positively, then its multiplicity in every supported bundle is at most \(\max\{U_1,U_2\}\).
Let \(Z=\{g:v_{1g}=v_{2g}=0\}\). Project the allocation onto goods outside \(Z\), aggregating masses with identical projected bundles. The multiplicity bounds make this projected support finite.
For each \(g\in Z\), choose a social-impact maximizing owner \(t(g)\). Within that type, independently append either
\(\displaystyle \left\lfloor q_g/\mu_{t(g)}\right\rfloor\quad\text{or}\quad\left\lceil q_g/\mu_{t(g)}\right\rceil\)
copies, with probabilities giving conditional mean \(q_g/\mu_{t(g)}\). Append zero copies to the other type.
This restores supplies and preserves optimality. Both types’ valuations and removable maximum values remain unchanged, so EF1 is preserved.
We have obtained a finite fair optimal allocation whose bundle coordinates are bounded by
\(\displaystyle K=\max\left\{1,U_1,U_2,\max_{g,t}\left\lceil q_g/\mu_t\right\rceil\right\}.\)
Under standard binary encoding of rational numerators and denominators,
\(\displaystyle \log K=O(L+\log(m+1)).\)
Indeed, \(\mu_t\geq2^{-L}\), while each valuation and supply is at most \(2^L\), giving \(U_t\leq m2^{3L}+2^L\).
Represent each supported pair by the integer column
\(\displaystyle a(t,b)=(\mathbf 1_{t=1},\mathbf 1_{t=2},b_1,\ldots,b_m).\)
Its masses satisfy
\(\displaystyle \sum_{t,b}x_{t,b}a(t,b)=(\mu_1,\mu_2,q_1,\ldots,q_m).\)
If these columns are linearly dependent, choose a nonzero dependence \(\delta\). The first two rows imply \(\sum_i\delta_i=0\), so \(\delta\) has both signs. Subtracting
\(\displaystyle \left(\min_{\delta_i>0}x_i/\delta_i\right)\delta\)
preserves all balances and nonnegativity while eliminating at least one positive mass. Repeating leaves at most \(m+2\) linearly independent columns. Restricting support preserves both EF1 and optimality.
Let their number be \(r\leq m+2\). Select \(r\) rows forming a nonsingular integer matrix \(A'\). Let \(D\) be the product of the denominators of the input masses and supplies; then \(D\leq2^L\).
Cramer’s rule shows that all remaining masses are rational, with reduced denominators dividing \(D|\det A'|\). Since matrix entries are at most \(K\),
\(\displaystyle |\det A'|\leq r!K^r.\)
Each mass is at most \(1\), so its numerator and denominator require
\(\displaystyle O\bigl(L+r(\log K+\log r)\bigr)=O\bigl(m(L+\log(m+1))\bigr)\)
bits.
Thus a yes-instance has a certificate consisting of at most \(m+2\) bundles and rational masses, with total length
\(\displaystyle O\bigl(m^2(L+\log(m+1))\bigr).\)
A verifier checks exact mass and supply balances, social-impact eligibility of every consumed good, and every ordered EF1 comparison in polynomial time. Hence the problem belongs to \(\mathrm{NP}\).
For the reduction, let \(\ell\) be the PARTITION input length. The constructed instance has
\(\displaystyle \tau=2,\qquad m=2n+2,\qquad L=O(n^2\log B).\)
Computing successive powers of \(B\) and writing the instance takes polynomial time; schoolbook arithmetic gives, for example, \(O(\ell+n^2(\log B)^2)\) bit operations.
For general instances with \(\tau=2\):
Therefore the stated mass-distribution existence problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The output establishes \(\mathrm{NP}\)-completeness for the exact mass-distribution problem with \(\tau=2\), including the stated restricted supplies, masses, and social impacts. I found no major or minor issues requiring repair.
The proof addresses the specified allocation model directly: integral bundles may contain repeated copies, masses may be real, and support may be countable. It does not infer hardness merely from the finite-agent result in the [cited paper](https://arxiv.org/html/2511.08160v2).
The global social-impact upper bound is correct. For every good \(g\), assigning its consumption a coefficient at most \(S_g\) gives total impact at most \(\sum_g S_gq_g\). Finite supplies and finitely many finite impact coefficients ensure that this quantity is finite.
The attainment construction is valid. Every supported type has positive mass, so the conditional means \(q_g/\mu_t\) are defined. The floor–ceiling mixtures have the required means, and their finite product produces integral bundles satisfying all supplies.
The displayed deficit identity is also correct for countable support. All its terms are nonnegative, and the relevant sums are finite. Consequently, zero deficit is equivalent to every consumed good in every positive-mass bundle going to a social-impact maximizing type. This establishes the eligibility characterization used later.
The EF1 reformulation is exact. Removing a present good with maximum per-copy value minimizes the remaining valuation. For the empty bundle, both its valuation and \(h_t(c)\) are zero, and nonnegative valuations make the inequality automatic.
The lemma correctly excludes repeated copies in bundles of encoded value \(T\).
The selected base satisfies the bounds used in the proof:
Since each weight is at least \(H\), an encoded sum equal to \(T<(n+1)H\) has \(N\leq n\). Thus every indexed coefficient \(k_i\) and the units coefficient \(P\) is smaller than \(B\). There are no carries in either displayed base expansion.
Uniqueness of base expansion therefore gives precisely the asserted conclusions: \(N=n\), every \(k_i=1\), and \(P=A\). The converse follows directly by substitution.
The restriction to even-total PARTITION inputs is valid. Odd-total inputs are no-instances, and the proposed replacement \(1,3\) is an even-total no-instance. The source problem is stated with the positive, binary-encoded integers needed by the reduction.
Global optimality assigns each anchor exclusively to its designated owner. Each anchor has positive supply, so each owner has a positive-mass bundle containing that anchor. This remains valid with countable support.
For any two anchor-containing bundles belonging to opposite types, the other type’s anchor has per-copy value \(C\), exceeding every common-good per-copy value. Hence the two EF1 inequalities are exactly those displayed in the output.
Adding them forces both anchor counts to equal one. Pairing every anchor-containing bundle with a fixed anchor-containing bundle of the opposite type therefore rules out all larger anchor counts.
The subsequent mean argument is valid: anchor counts are now either zero or one, while their conditional mean equals one. Any supported anchor-free bundle would have positive mass and make that mean strictly smaller than one. Thus every supported bundle contains exactly one own anchor.
With these anchor counts, cross-type EF1 forces equality of common-good values for every opposite-type pair. Both types have nonempty support, so all supported bundles share one value \(\lambda\).
Supply feasibility gives total common-good valuation \(T\). Since the total population mass is one, \(\lambda=T\). Applying the encoding lemma to any supported bundle then yields the required PARTITION solution.
No step here presupposes finite support or bounds bundle multiplicities by supplies.
The two complementary bundles have encoded value \(T\). For the complement, the selected original numbers sum to \(2A-A=A\), so the stated equality holds for both bundles.
The four masses of \(1/4\) correctly satisfy:
Within a type, all allocated bundles have own valuation \(T\). Across types, the compared bundle has valuation \(T+C\), and removing its anchor leaves \(T\). Thus every required ordered EF1 comparison holds, including comparisons within the same type.
All consumed goods satisfy social-impact eligibility. The allocation is therefore globally maximizing.
The reduction establishes both directions and respects all claimed input restrictions.
For each type \(t\), its total own valuation is at most \(W_t\), since its consumption of each good is at most the aggregate supply. Its conditional mean is consequently at most \(W_t/\mu_t\).
The minimum supported own valuation exists: support is nonempty and bundle valuations are nonnegative integers. Its bound by the floor of the conditional mean is correct.
Comparing a bundle attaining this minimum against every supported bundle gives the stated upper bound \(v_t(c)\leq U_t\). This uses the task’s inclusion of same-type EF1 comparisons.
If either type values a good positively, that integer value is at least one. Its multiplicity in every supported bundle is therefore bounded as claimed.
Projection onto the other coordinates yields finite support because those coordinates have finite integer bounds.
The proposed reconstruction of zero-valued goods is valid:
Thus the construction produces a finite fair optimal allocation, with the stated coordinate bound \(K\). It also covers zero supplies and instances in which every valuation is zero.
The estimate \(\log K=O(L+\log(m+1))\) is valid under the stated binary rational encoding. The displayed coarse bounds on masses, supplies, and valuations suffice.
The linear-dependence elimination is correct. The two type rows imply that any nonzero dependence has coefficients summing to zero, hence has both signs. The chosen subtraction preserves balances and nonnegativity and removes at least one supported column.
The process terminates with at most \(m+2\) linearly independent columns. Deleting support cannot introduce an EF1 violation, and the surviving bundles retain social-impact eligibility.
Selecting a nonsingular square submatrix is justified by column independence. Its unique solution is the surviving mass vector, so Cramer’s rule applies even though the original masses were real.
Clearing the input denominators gives the claimed denominator divisibility. The determinant bound \(r!K^r\) is valid, and each surviving mass is at most one. The resulting individual mass bit bound and total certificate-length bound follow.
The verifier’s listed checks suffice. Exact balances establish supply feasibility, eligibility establishes global optimality, and checking every ordered pair establishes EF1 for the entire finite support. All operate on polynomially many polynomial-length integers and rationals.
This establishes membership in \(\mathrm{NP}\) for the full problem, including instances initially admitting only a countably supported witness.
The reduction’s output-length bound \(L=O(n^2\log B)\) is correct: there are linearly many goods, and each constructed valuation has \(O(n\log B)\) bits.
The example construction-time bound is also consistent with schoolbook arithmetic. Successive multiplication by the \(O(\log B)\)-bit base has total cost \(O(n^2(\log B)^2)\); forming and writing the remaining quantities fits this bound together with input reading.
For fixed \(\tau=2\), the stated verification and nondeterministic running times are polynomial in \(m,L\). Exhaustive enumeration of certificates of the established bounded length gives the stated deterministic exponential upper bound.
Combining the valid reduction and certificate argument proves \(\mathrm{NP}\)-completeness. The qualification concerning a polynomial deterministic algorithm and \(\mathrm P=\mathrm{NP}\) is correct.
Required clarification: 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.