Answer: \(\mathrm{NP\text{-}hard}\)
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWhen parameterized by p plus the number mt of item types, REFAE and FEFAE are fixed-parameter tractable and XP-tractable, respectively. An overview of our complete complexity-theoretic clas- sification of ENVY-FREE ALLOCATION EXTENSION under the considered restrictions is provided in Table 1. While not part of our main technical contributions, in the final section of the article, we also make a few observations about the behavior of relaxed variants of envy-freeness in the extension setting that may be of general interest to the com- munity.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite complete agent types \(H\) with rational masses \(\mu_h\), additive valuations over item types \(U\), integral fixed endowments \(e_h\), rational per-capita supplies \(\sigma_u\) of open item copies, and a given set \(R\) of at most \(p\) recipient cohorts, decide whether there are integral bundle vectors \(b_h\) uniform within each cohort, with \(b_h = 0\) outside \(R\), such that the aggregate supply constraints \(\sum_h \mu_h b_{h,u} = \sigma_u\) hold for every item type \(u\) and \(v_h(e_h+b_h) \ge v_h(e_{h'}+b_{h'})\) for every pair of population types \(h,h'\).
Given finite \(\Theta\), masses \(\mu_\theta\in\mathbb Q_{\ge0}\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), additive valuations \(v_\theta\), integral baseline bundles \(\gamma_\theta\), open item types \(A\), and supplies \(\lambda_a\in\mathbb Q_{\ge0}\), an allocation is nonnegative mass \(x_{\theta,b}\) for \(b\in\mathbb Z_{\ge0}^{A}\).
It is feasible if \(\sum_bx_{\theta,b}=\mu_\theta\) for every \(\theta\), \(\sum_{\theta,b}b_ax_{\theta,b}=\lambda_a\) for every \(a\), and at most two types have \(\sum_{b\ne0}x_{\theta,b}>0\). It is envy-free if, whenever \(x_{\theta,b}>0\) and \(x_{\theta',b'}>0\), \(v_\theta(\gamma_\theta+b)\ge v_\theta(\gamma_{\theta'}+b')\).
Is deciding whether a feasible envy-free allocation exists solvable in polynomial time, or is it NP-hard?
For finite societies of individual agents with additive valuations, FREE ENVY-FREE ALLOCATION EXTENSION is strongly NP-hard even when at most two agents receive open items. This is the discrete analogue of the problem above.
Deciding whether a feasible envy-free allocation exists is \(\mathrm{NP}\)-hard, even when every feasible allocation can have only one type receiving open items.
The reduction permits arbitrary real allocation masses \(x_{\theta,b}\); thus the hardness does not result from imposing rationality or finite-support restrictions on the allocation.
Consider a \(\mathrm{PARTITION}\) instance consisting of positive integers \(s_1,\ldots,s_d\) with total value
\[ \sum_{i=1}^d s_i=2B. \]
This restriction loses no generality: multiplying every number in an arbitrary instance by \(2\) produces an equivalent instance whose total is even.
We construct a mass-allocation instance.
There is one open item type \(a_i\) for every integer \(s_i\). Thus
\[ A=\{a_1,\ldots,a_d\}. \]
Every open type has supply
\[ \lambda_{a_i}=\frac14. \]
There is one distinguished type \(r\), intended to receive all open items, with mass
\[ \mu_r=\frac12. \]
For every \(i\in\{1,\ldots,d\}\), introduce three guard types
\[ g_{i,1},g_{i,2},g_{i,3}. \]
Each guard has mass
\[ \mu_{g_{i,j}}=\frac{1}{6d}. \]
There are \(3d\) guards, so their total mass is \(1/2\). Hence all masses sum to \(1\).
For every population type \(\theta\), introduce a distinct baseline item \(p_\theta\), not belonging to \(A\), and let
\[ \gamma_\theta=\{p_\theta\}. \]
The distinguished type values every baseline item at zero:
\[ v_r(p_\theta)=0 \]
for every \(\theta\).
A guard \(h\) has baseline-item values
\[ v_h(p_r)=0, \qquad v_h(p_\theta)=1\quad\text{for every }\theta\ne r. \]
In particular, every guard values its own baseline bundle at \(1\).
The distinguished type has
\[ v_r(a_i)=s_i. \]
A guard \(g_{i,j}\) values only open type \(a_i\):
\[ v_{g_{i,j}}(a_i)=1, \qquad v_{g_{i,j}}(a_k)=0\quad\text{for }k\ne i. \]
All valuations are additive and nonnegative.
The construction has \(O(d)\) types and items and can be encoded in polynomial time.
Suppose an envy-free feasible allocation exists, and suppose some type \(k\ne r\) receives a nonzero bundle \(b\) with positive mass. Choose a coordinate \(i\) for which \(b_i\ge 1\).
At most two types may receive nonzero bundles. Among the three guards \(g_{i,1},g_{i,2},g_{i,3}\), therefore, at least one guard \(h\) receives no open items. For this guard,
\[ x_{h,0}=\mu_h>0. \]
Because \(k\ne r\), guard \(h\) values \(k\)'s baseline bundle at \(1\). It also values the \(b_i\) copies of \(a_i\) at \(b_i\). Consequently,
\[ v_h(\gamma_k+b)=1+b_i\ge 2, \]
whereas
\[ v_h(\gamma_h)=1. \]
Thus \(h\) envies the positive-mass cell \((k,b)\), contradicting envy-freeness.
Hence no type other than \(r\) can receive open items. Since all open supplies are positive, \(r\) must receive them.
Let \(b\) and \(c\) be any two bundles with
\[ x_{r,b}>0 \quad\text{and}\quad x_{r,c}>0. \]
Applying envy-freeness first from cell \((r,b)\) to \((r,c)\), and then in the opposite direction, gives
\[ v_r(\gamma_r+b)=v_r(\gamma_r+c). \]
Because \(v_r(\gamma_r)=0\), there is a common number \(q\) such that every supported bundle of type \(r\) satisfies
\[ \sum_{i=1}^d s_i b_i=q. \]
Using the mass and supply equations,
\[ q\mu_r = \sum_b\left(\sum_{i=1}^d s_i b_i\right)x_{r,b} = \sum_{i=1}^d s_i\lambda_{a_i}. \]
Substituting \(\mu_r=1/2\), \(\lambda_{a_i}=1/4\), and \(\sum_i s_i=2B\), we obtain
\[ \frac q2=\frac14(2B)=\frac B2, \]
and hence
\[ q=B. \]
Therefore every bundle \(b\) in the support of type \(r\) satisfies
\[ \sum_{i=1}^d s_i b_i=B. \]
Fix \(i\) and a supported bundle \(b\) of type \(r\). Every guard is inactive by the structural lemma. In particular, guard \(g_{i,1}\) occupies its zero-open-item cell.
That guard values its own baseline at \(1\), while it values type \(r\)'s cell at
\[ v_{g_{i,1}}(\gamma_r+b)=b_i. \]
Envy-freeness therefore implies
\[ 1\ge b_i. \]
Since \(b_i\) is a nonnegative integer, \(b_i\in\{0,1\}\). This holds for every coordinate. Thus every bundle in the support of \(r\) is the incidence vector of a subset \(S\subseteq\{1,\ldots,d\}\), and the preceding equality gives
\[ \sum_{i\in S}s_i=B. \]
Consequently, existence of an envy-free feasible allocation implies that the original \(\mathrm{PARTITION}\) instance is positive.
Conversely, suppose there is a subset \(S\subseteq\{1,\ldots,d\}\) satisfying
\[ \sum_{i\in S}s_i=B. \]
Its complement also has value \(B\). Let \(\mathbf 1_S\) and \(\mathbf 1_{\overline S}\) denote their incidence vectors. Define
\[ x_{r,\mathbf 1_S}=\frac14, \qquad x_{r,\mathbf 1_{\overline S}}=\frac14, \]
and, for every guard \(h\), define
\[ x_{h,0}=\mu_h. \]
All other allocation masses are zero.
Each open item belongs to exactly one of \(S\) and \(\overline S\), so its total allocated supply is \(1/4\). All population-mass constraints are also satisfied, and only type \(r\) receives open items.
It remains to verify envy-freeness:
Thus the constructed allocation is feasible and envy-free.
The reduction proves
\[ \mathrm{PARTITION} \ \le_{\mathrm p}\ \text{mass envy-free allocation existence}. \]
Therefore the target decision problem is \(\mathrm{NP}\)-hard. In particular, it cannot be polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
The argument proves ordinary \(\mathrm{NP}\)-hardness, not strong \(\mathrm{NP}\)-hardness. The stated strong hardness of the finite-agent analogue does not automatically transfer, because a positive-mass type may split across several integral bundles. The guard construction above handles that splitting directly.
⟨structured verdict parsed — rendered above⟩
The reduction correctly establishes ordinary \( \mathrm{NP} \)-hardness of the requested continuous mass-allocation problem. It accommodates arbitrary real allocation masses and does not assume finite support.
There is one false strengthening in the theorem statement: the construction does not ensure that every feasible allocation has only one type receiving open items. What is proved is that every feasible envy-free allocation has only one such type. This wording error does not affect the answer to the user’s target question.
The reduction starts from \( \mathrm{PARTITION} \) with positive integers \(s_1,\ldots,s_d\) and total \(2B\).
The even-total normalization is valid. Doubling every number preserves whether the multiset has an equal-sum partition, including when the original total is odd.
The construction uses rational masses and supplies of polynomial encoding length. Although there are \(O(d)\) types and baseline items, the valuation table may contain \(O(d^2)\) entries; this remains polynomial and does not invalidate the stated encoding claim.
The distinguished mass is \(1/2\). There are \(3d\) guards, each of mass \(1/(6d)\), so their total mass is
\[ 3d\cdot\frac{1}{6d}=\frac12. \]
Thus the population masses sum to \(1\).
Every open item type has supply \(1/4\), as required by the later construction.
Suppose a type \(k\ne r\) receives a nonzero bundle \(b\), and choose \(i\) with \(b_i\ge1\).
Since at most two population types can receive nonzero bundles, at least one of the three guards \(g_{i,1},g_{i,2},g_{i,3}\) receives no open items. For such a guard \(h\), the mass equation indeed forces \(x_{h,0}=\mu_h>0\).
Because \(k\ne r\), guard \(h\) values \(k\)'s baseline at \(1\), and because it is associated with coordinate \(i\), it values \(b\)'s open items at least \(b_i\ge1\). Hence it values \(k\)'s cell at least \(2\), while its own cell has value \(1\). This contradicts envy-freeness.
Therefore, in every feasible envy-free allocation, no type other than \(r\) receives open items. This step is correct.
For any two supported cells \((r,b)\) and \((r,c)\), envy-freeness in both directions gives equality of their utilities. Therefore all supported bundles of \(r\) have a common weighted value \(q\).
The identity
\[ q\mu_r=\sum_i s_i\lambda_{a_i} \]
follows from the mass and supply equations. It remains valid with infinite support because only finitely many coordinates \(i\) occur and all summands are nonnegative.
Substitution yields
\[ \frac q2=\frac14\sum_i s_i=\frac B2, \]
so \(q=B\). This calculation is correct.
For a supported bundle \(b\) of \(r\), guard \(g_{i,1}\) has utility \(1\) from its own baseline and values \(r\)'s cell at \(b_i\). Envy-freeness therefore gives \(1\ge b_i\).
Since \(b_i\in\mathbb Z_{\ge0}\), it follows that \(b_i\in\{0,1\}\). Thus every supported bundle is the incidence vector of a subset whose \(s_i\)-sum is \(B\). This correctly proves the soundness direction.
Given a subset \(S\) of value \(B\), assigning mass \(1/4\) to each of \(\mathbf 1_S\) and \(\mathbf 1_{\overline S}\) gives \(r\) total mass \(1/2\). Each coordinate occurs in exactly one of these bundles, so its allocated supply is \(1/4\).
All guards receive their full masses at the zero bundle, and only \(r\) receives open items.
The envy checks cover every ordered pair of supported cell types:
Thus completeness is correctly established.
The theorem’s phrase “even when every feasible allocation can have only one type receiving open items” is false under the problem’s definition of feasibility, which does not include envy-freeness.
For example, choose one guard and assign all open supplies through that guard while placing every other type at its zero bundle. If \(d\) is even, assigning that guard its full mass \(1/(6d)\) at the bundle with every coordinate \(3d/2\) supplies \(1/4\) of each item. If \(d\) is odd, splitting its mass equally between the two constant bundles with coordinates \((3d-1)/2\) and \((3d+1)/2\) has the same effect. These are feasible allocations with a guard receiving open items.
The argument establishes only the corresponding statement about feasible envy-free allocations. Correcting that wording requires no new mathematical argument and leaves the target \( \mathrm{NP} \)-hardness result intact.
⟨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.