Answer: —
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe ϕ-FAIR DIVISION WITH EXTERNALITIES problem, where ϕ ∈{EF, EF1, EFX}, is fixed-parameter tractable when parameterized by the number of different item types Υ and the number of agents |N| combined.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(R\), item types \(A\), rational agent masses \(\mu\), rational per-capita supplies \(\beta\), and rational typed additive externality values distinguishing self from recipient types, decide whether there exists a finite-support allocation law \(\lambda_{r,B}\) over integer bundles satisfying the supply constraints and the paper's EFX swap-bundle condition for every positive-mass type/bundle pair; study this problem parameterized by \(|R|+|A|\).
Definitions. Let \(R\) be a finite set of agent types, \(A=\{1,2,3\}\), rational masses \(\mu_r\), supplies \(\sigma_a\), and values \(v_r(s,a)\), where a type-\(r\) agent values a type-\(a\) item assigned to type \(s\) by \(v_r(s,a)\). Assume \(v_r(r,a)\ge v_r(s,a)\) for all \(r,s,a\). A configuration is \(x_{r,\mathbf b}\in\mathbb Q_{\ge0}\) of finite support, with \(\sum_{\mathbf b}x_{r,\mathbf b}=\mu_r\) and \(\sum_{r,\mathbf b}x_{r,\mathbf b}b_a=\sigma_a\).
For bundles \(\mathbf b,\mathbf c\), let \(D_{r,s}(\mathbf b,\mathbf c)=\sum_a(c_a-b_a)(v_r(r,a)-v_r(s,a))\). The configuration is EFX if, whenever \(x_{r,\mathbf b},x_{s,\mathbf c}>0\) and \(D_{r,s}(\mathbf b,\mathbf c)>0\), every removal of one present item from either \(\mathbf b\) or \(\mathbf c\) that strictly lowers \(D_{r,s}\) lowers it to at most \(0\).
Target. Is deciding whether such a rational finite-support EFX configuration exists NP-hard, or solvable in polynomial time?
Nearest known results. For finite agents and indivisible items with additive externalities, deciding EFX existence is NP-complete even with three item types, at most six valuation values, and no weak chores. No result is stated here for exactly the distributional problem above.
Assume that bundles are integral vectors \(\mathbf b\in\mathbb Z_{\ge 0}^{3}\). Without this assumption, if rational bundles are permitted, the problem is trivial: for \(M=\sum_r\mu_r>0\), assign every type the single bundle \(\mathbf q=\boldsymbol\sigma/M\). Then every comparison has \(D_{r,s}(\mathbf q,\mathbf q)=0\), so the configuration is EFX.
Under the intended integral-bundle interpretation, I do not obtain a complete polynomial-time algorithm or an NP-hardness proof. I prove below:
These results leave one specific support-selection problem unresolved.
For \(r,s\in R\), define the nonnegative gap vector
\[ \mathbf w^{rs}=\bigl(w^{rs}_a\bigr)_{a\in A}, \qquad w^{rs}_a=v_r(r,a)-v_r(s,a)\ge 0. \]
For an integral bundle \(\mathbf c\), define
\[ h_{rs}(\mathbf c)= \begin{cases} \min\{w^{rs}_a:c_a>0,\ w^{rs}_a>0\},&\text{if this set is nonempty},\\ 0,&\text{otherwise}. \end{cases} \]
A supported pair \((r,\mathbf b),(s,\mathbf c)\) satisfies the stated EFX requirement for envy from \(r\) toward \(s\) if and only if
\[ \mathbf w^{rs}\mathbin{\cdot}(\mathbf c-\mathbf b)\le h_{rs}(\mathbf c). \]
Removing an item of type \(a\) from \(\mathbf b\) changes the envy difference to
\[ D_{r,s}(\mathbf b-\mathbf e_a,\mathbf c) = D_{r,s}(\mathbf b,\mathbf c)+w^{rs}_a. \]
Because \(w^{rs}_a\ge 0\), such a removal never strictly lowers \(D_{r,s}\).
Removing a present item of type \(a\) from \(\mathbf c\) changes the difference to
\[ D_{r,s}(\mathbf b,\mathbf c-\mathbf e_a) = D_{r,s}(\mathbf b,\mathbf c)-w^{rs}_a. \]
This strictly lowers the difference exactly when \(w^{rs}_a>0\). If \(D_{r,s}(\mathbf b,\mathbf c)>0\), EFX therefore requires
\[ D_{r,s}(\mathbf b,\mathbf c)-w^{rs}_a\le 0 \]
for every \(a\) with \(c_a>0\) and \(w^{rs}_a>0\). This is equivalent to
\[ D_{r,s}(\mathbf b,\mathbf c)\le h_{rs}(\mathbf c). \]
If no such item is present in \(\mathbf c\), then \(\mathbf w^{rs}\cdot\mathbf c=0\), and hence
\[ D_{r,s}(\mathbf b,\mathbf c) = -\mathbf w^{rs}\cdot\mathbf b\le 0. \]
Thus the same inequality, with \(h_{rs}(\mathbf c)=0\), remains valid. ∎
Let \(B_r\) denote the support of type \(r\). Lemma 1 gives
\[ \max_{\mathbf c\in B_s} \bigl(\mathbf w^{rs}\cdot\mathbf c-h_{rs}(\mathbf c)\bigr) \le \min_{\mathbf b\in B_r}\mathbf w^{rs}\cdot\mathbf b. \]
Consequently, EFX is equivalent to the existence, for every ordered pair \(r\ne s\), of a rational threshold \(\theta_{rs}\) satisfying
\[ \mathbf w^{rs}\cdot\mathbf b\ge\theta_{rs} \quad\text{for every }\mathbf b\in B_r, \]
and
\[ \mathbf w^{rs}\cdot\mathbf c-h_{rs}(\mathbf c)\le\theta_{rs} \quad\text{for every }\mathbf c\in B_s. \]
For a threshold vector \(\boldsymbol\theta\), define
\[ C_r(\boldsymbol\theta)= \left\{ \mathbf b\in\mathbb Z_{\ge0}^{3}: \begin{array}{l} \mathbf w^{rs}\cdot\mathbf b\ge\theta_{rs}\text{ for every }s\ne r,\\ \mathbf w^{sr}\cdot\mathbf b-h_{sr}(\mathbf b)\le\theta_{sr} \text{ for every }s\ne r \end{array} \right\}. \]
An EFX configuration exists if and only if there are rational thresholds \(\boldsymbol\theta\) and rational vectors
\[ \mathbf y_r\in\operatorname{conv}\bigl(C_r(\boldsymbol\theta)\bigr) \]
such that
\[ \sum_{r\in R}\mu_r\mathbf y_r=\boldsymbol\sigma. \]
Given an EFX configuration, choose
\[ \theta_{rs} = \max_{\mathbf c\in B_s} \bigl(\mathbf w^{rs}\cdot\mathbf c-h_{rs}(\mathbf c)\bigr). \]
Lemma 1 shows that every \(\mathbf b\in B_r\) satisfies the required lower bound. Thus \(B_r\subseteq C_r(\boldsymbol\theta)\). Taking
\[ \mathbf y_r=\frac1{\mu_r}\sum_{\mathbf b}x_{r,\mathbf b}\mathbf b \]
gives the desired convex-hull and supply conditions.
Conversely, choose rational finite convex representations of the \(\mathbf y_r\) using points of \(C_r(\boldsymbol\theta)\). For \(\mathbf b\in C_r(\boldsymbol\theta)\) and \(\mathbf c\in C_s(\boldsymbol\theta)\),
\[ \mathbf w^{rs}\cdot\mathbf c-h_{rs}(\mathbf c) \le\theta_{rs} \le\mathbf w^{rs}\cdot\mathbf b. \]
Hence Lemma 1 applies to every supported pair. Scaling the convex coefficients by \(\mu_r\) produces an EFX configuration satisfying the supply equations. ∎
This is an exact configuration formulation. Its unresolved part is the simultaneous choice of \(\boldsymbol\theta\): the sets \(C_r(\boldsymbol\theta)\) change discontinuously when an integer bundle enters or leaves them.
If an EFX configuration exists, then one exists in which every positive-mass type supports at most four bundles.
Fix a feasible configuration and a type \(r\) with \(\mu_r>0\). Its mean bundle
\[ \mathbf y_r=\frac1{\mu_r}\sum_{\mathbf b}x_{r,\mathbf b}\mathbf b \]
belongs to the convex hull of \(B_r\subseteq\mathbb R^3\). By Carathéodory’s theorem, \(\mathbf y_r\) is a convex combination of at most four points of \(B_r\).
The selected points and \(\mathbf y_r\) are rational. A basic feasible solution of the corresponding rational system gives rational convex coefficients. Replace the distribution of type \(r\) by this combination.
This preserves \(\mu_r\mathbf y_r\), and therefore preserves all supply equations. It only deletes support points, so it cannot introduce a new unsupported-pair EFX violation. Applying this independently to all types proves the claim. ∎
Thus support size itself is not the obstruction to membership in \(\mathrm{NP}\). The remaining certificate issue is whether bundle coordinates and rational masses always have polynomial encoding length.
Clear denominators in the masses, supplies, and configuration variables.
A rational finite-support EFX configuration exists if and only if there is a positive integer \(N\) such that the following finite replicated instance has an EFX allocation:
Given a rational configuration, choose \(N\) so that every \(N\mu_r\), \(N\sigma_a\), and \(Nx_{r,\mathbf b}\) is integral. Create \(N\mu_r\) clones of type \(r\), assigning bundle \(\mathbf b\) to exactly \(Nx_{r,\mathbf b}\) of them.
Pairs of distinct types satisfy EFX because their bundles occur in the configuration support. For two clones of the same type \(r\), the relevant gap vector is \(\mathbf w^{rr}=\mathbf0\), so their envy difference is zero.
Conversely, aggregate any EFX allocation of the replicated instance by setting
\[ x_{r,\mathbf b} = \frac{\#\{\text{type-$r$ clones receiving }\mathbf b\}}{N}. \]
The mass and supply equations follow by counting, and every supported pair is realized by a pair of clones. ∎
The cited finite-agent hardness theorem concerns existence at one fixed population and supply vector [Deligkas–Eiben–Korchemna–Schierreich](https://arxiv.org/abs/2308.08869). Proposition 4 shows that the present problem instead asks whether an EFX allocation exists at *some common replication scale* \(N\). Hence the finite theorem alone does not prove NP-hardness here: type splitting is exactly the possibility of using different bundles for different clones at a larger scale.
Assume all zero-mass types have been deleted. Let
\[ S=\sum_{a\in A}\sigma_a. \]
Consider the following condition:
For every \(r\in R\), there exists \(s(r)\ne r\) such that \(w^{s(r)r}_a>0\) for all \(a\in A\).
Define
\[ \delta_r=\min_a w^{s(r)r}_a, \qquad W_r=\max_a w^{s(r)r}_a. \]
Under strict observability, the decision problem belongs to \(\mathrm{NP}\).
Let \(\mathbf b\) be any supported bundle of type \(r\), and let \(\mathbf c\) be any supported bundle of type \(s=s(r)\). Applying Lemma 1 to envy from \(s\) toward \(r\) gives
\[ \mathbf w^{sr}\cdot(\mathbf b-\mathbf c) \le h_{sr}(\mathbf b)\le W_r. \]
Since every coordinate of \(\mathbf w^{sr}\) lies between \(\delta_r\) and \(W_r\),
\[ \delta_r\lVert\mathbf b\rVert_1 \le W_r\lVert\mathbf c\rVert_1+W_r. \]
Average this inequality over the type-\(s\) distribution. The average total number of items held by type \(s\) is at most \(S/\mu_s\). Therefore every supported \(\mathbf b\) of type \(r\) satisfies
\[ \lVert\mathbf b\rVert_1 \le \frac{W_r}{\delta_r} \left(\frac{S}{\mu_s}+1\right). \]
The binary encoding length of this bound is polynomial in the input length. Proposition 3 now gives at most four polynomial-bit bundles per type.
After fixing these bundles, the masses satisfy a rational linear system consisting of the type-mass and supply equations. If it is feasible, it has a basic feasible solution whose numerators and denominators have polynomial bit length by the standard determinant bound for rational linear systems. Taking such a solution can only delete support points and therefore preserves EFX.
Thus a polynomial-size certificate consists of at most four bundles per type and their rational masses; all conditions are verifiable in polynomial time. ∎
This does not establish membership in \(\mathrm{NP}\) for completely arbitrary zero patterns in the valuation gaps.
Suppose that for every ordered pair \(r,s\),
\[ \mathbf w^{rs}=\lambda_{rs}(1,1,1) \]
for some rational \(\lambda_{rs}\ge0\). Thus an agent’s loss from giving an item to type \(s\) rather than keeping it depends on \(r,s\), but not on the item type.
Under this condition, an EFX configuration always exists and can be computed in polynomial time.
Let
\[ M=\sum_r\mu_r, \qquad \mathbf q=\frac{\boldsymbol\sigma}{M}, \qquad t=\lVert\mathbf q\rVert_1, \qquad k=\lfloor t\rfloor. \]
Consider the integral bundles whose total cardinality is either \(k\) or \(k+1\). Their convex hull is
\[ P_k= \{\mathbf z\in\mathbb R_{\ge0}^{3}:k\le\lVert\mathbf z\rVert_1\le k+1\}. \]
Indeed, the vertices of this polytope are integral: they are \(k\mathbf e_a\) and \((k+1)\mathbf e_a\), with the evident modification when \(k=0\). Since \(\mathbf q\in P_k\), it has a rational convex decomposition into such integral bundles.
Use this same bundle distribution for every agent type. Then the total mean supply is \(M\mathbf q=\boldsymbol\sigma\).
For any two supported bundles \(\mathbf b,\mathbf c\),
\[ \lVert\mathbf c\rVert_1-\lVert\mathbf b\rVert_1\le1. \]
If \(\lambda_{rs}=0\), the envy difference is zero. If \(\lambda_{rs}>0\), then
\[ D_{r,s}(\mathbf b,\mathbf c) = \lambda_{rs} \bigl(\lVert\mathbf c\rVert_1-\lVert\mathbf b\rVert_1\bigr) \le\lambda_{rs}. \]
Whenever \(\mathbf c\ne\mathbf0\), one has \(h_{rs}(\mathbf c)=\lambda_{rs}\); when \(\mathbf c=\mathbf0\), the envy difference is nonpositive. Lemma 1 therefore proves EFX. ∎
A still simpler always-YES case occurs when \(\boldsymbol\sigma/M\in\mathbb Z_{\ge0}^{3}\): assigning this identical bundle to every type is envy-free.
The general target is not settled by the preceding results. Proposition 2 reduces it exactly to finding thresholds \(\boldsymbol\theta\) such that
\[ \boldsymbol\sigma \in \sum_{r\in R} \mu_r\operatorname{conv}\bigl(C_r(\boldsymbol\theta)\bigr). \]
For fixed thresholds, each \(C_r(\boldsymbol\theta)\) is a union of at most eight fixed-support-pattern integer polyhedra in dimension three. The unresolved difficulty is that changing \(\boldsymbol\theta\) changes which integer bundles may have positive mass, and positive mass activates all cross-support EFX constraints.
Therefore either of the following would settle the target:
The known finite-agent reduction supplies neither fact directly.
⟨structured verdict parsed — rendered above⟩
The output contains several correct structural results, but it expressly does not answer the target complexity question for the general integral-bundle problem. The appropriate status is therefore partial.
The threshold lemma, support reduction, replication characterization, conditional NP-membership result, and tractable valuation subclass are substantively sound after minor qualifications. The main concrete defect is that Proposition 2 is false as stated when zero-mass types are retained.
The problem statement does not explicitly declare the domain of bundles. The prover reasonably distinguishes:
The degenerate case \(M=0\) is not handled in the introductory discussion. It must be separated according to whether all supplies vanish.
This lemma is correct.
Removing an item from \(\mathbf b\) changes the difference by \(+w^{rs}_a\), so it cannot strictly lower the difference because \(w^{rs}_a\ge 0\). Removing a present item of type \(a\) from \(\mathbf c\) changes it by \(-w^{rs}_a\). Consequently, when the difference is positive, the strongest requirement is exactly
\[ D_{r,s}(\mathbf b,\mathbf c)\le \min\{w^{rs}_a:c_a>0,\ w^{rs}_a>0\}. \]
When the minimum is over the empty set, \(\mathbf w^{rs}\cdot\mathbf c=0\), giving \(D_{r,s}\le0\). No missing case remains.
The threshold equivalence is correct when all types under consideration have positive mass. It is not correct as stated for arbitrary zero-mass types.
A concrete failure can be embedded in the first of the three item coordinates. Take types \(z,p_1,p_2\) with masses \(0,1,1\), supported bundles \(\mathbf0\) for \(p_1\) and \(100\mathbf e_1\) for \(p_2\), and supply \(100\mathbf e_1\). Let the mutual gaps between \(p_1\) and \(p_2\) be zero, while
\[ \mathbf w^{p_1z} =\mathbf w^{p_2z} =\mathbf w^{zp_1} =\mathbf w^{zp_2} =\mathbf e_1. \]
This is an EFX configuration because the zero-mass type has no supported bundle and the two positive types have zero mutual gap.
In the claimed threshold formulation:
Thus \(C_z(\boldsymbol\theta)=\varnothing\), contradicting Proposition 2’s requirement that a vector \(\mathbf y_z\) belong to its convex hull.
Deleting all zero-mass types before stating Proposition 2 repairs this edge case. The proof also divides by \(\mu_r\), so positivity is already implicitly required.
In the converse direction, the assertion that a rational point in the convex hull has a rational finite convex representation needs a short rational-linear-algebra justification. It is true, but not established in the text.
The four-bundle support theorem is correct for positive-mass types.
Carathéodory’s theorem applies in \(\mathbb R^3\), and the convex coefficients can be chosen rational because the selected bundles and the mean are rational. Replacing a distribution only by points already in its support cannot create new pairwise EFX constraints.
The replication correspondence is correct under the natural clone interpretation
\[ V_i(j,a)=v_r(s,a) \]
when clone \(i\) has type \(r\) and clone \(j\) has type \(s\).
Clearing denominators converts rational masses into clone counts, and aggregation gives the converse. Comparisons between clones of the same type have zero gap.
The cited paper’s EFX definition is indeed based on bundle swaps and removals that strictly reduce envy, and its Theorem 3.2 gives NP-completeness with six values, three item types, and no weak chores. Thus the output correctly explains why hardness at one fixed scale does not by itself prove hardness when some replication scale may be chosen. See the [paper’s definitions and theorem](https://arxiv.org/html/2308.08869v2).
The conditional NP-membership argument is correct.
Strict positivity of every coordinate of \(\mathbf w^{s(r)r}\) gives
\[ \delta_r\lVert\mathbf b\rVert_1 \le W_r\lVert\mathbf c\rVert_1+W_r. \]
Averaging over type \(s(r)\) and using the global supply gives the asserted bound. Its binary encoding length is polynomial in the rational input length. Proposition 3 then bounds support size, and standard determinant bounds give polynomial-size rational masses.
This proposition does not establish NP membership for the unrestricted problem, as the output correctly acknowledges.
For \(M>0\) and nonnegative supplies, the construction is correct.
The polytope
\[ \{\mathbf z\ge0:k\le\lVert\mathbf z\rVert_1\le k+1\} \]
has the stated integral vertices, with the additional origin interpretation when \(k=0\). All supported bundles therefore have cardinalities differing by at most one, which verifies Lemma 1 for uniform gap vectors.
Two qualifications are missing:
The observation that fixed \(C_r(\boldsymbol\theta)\) is a union over at most eight coordinate-support patterns is correct: after fixing which coordinates are positive, \(h_{sr}\) is a fixed rational constant and the remaining conditions are linear integer constraints.
However, this reformulation does not supply either a polynomial-time threshold-selection procedure or a scale-robust hardness reduction. Hence it does not settle the requested dichotomy.
The minimum repairs to make the established partial results verifiable are:
⟨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.