The Complexity of Fair Division of Indivisible Items with Externalities

The strongest honest case is that the paper admits a good continuous mirror in a typed, high-multiplicity workforce regime. The mirror should not pretend that every named-agent externality instance has a meaningful continuum limit: identity-specific relationships are precisely what high multiplicity removes.

Take a finite set \(R\) of complete agent types. A type records an agent’s item values, team or role, and how that agent values an item when it is assigned to each recipient type. Let \(\mu_r\) be the fraction of the workforce of type \(r\). Let \(A\) be a finite set of item types, with \(\beta_a\) copies of item type \(a\) per unit population. At scale \(N\), the instance has \(N\mu_r\) agents of type \(r\) and \(N\beta_a\) indivisible copies of item type \(a\).

An allocation is not a fractional item allocation. It is a finite-support distribution \(\lambda_{r,B}\), where \(B\in\mathbb Z_{\ge 0}^{A}\) is an integer bundle and \(\lambda_{r,B}\) is the mass of type-\(r\) agents receiving that bundle:

\[ \sum_B\lambda_{r,B}=\mu_r,\qquad \sum_{r,B}B_a\lambda_{r,B}=\beta_a. \]

Thus mass describes how many otherwise indistinguishable agents receive each discrete bundle. Every individual item remains indivisible.

For an observer of type \(r\), let \(w_{r,a}\) be the value when the observer receives item \(a\), and \(u_{r,s,a}\) the value when an agent of recipient type \(s\) receives it. If a type-\(r\) agent with bundle \(B\) swaps with a type-\(s\) agent with bundle \(B'\), the envy difference is

\[ D_{r,s}(B,B') =\sum_a (u_{r,s,a}-w_{r,a})(B_a-B'_a). \]

The allocation law is EF1 if every positive \(D\) can be reduced to at most zero by deleting one item from either bundle. It is EFX if every deletion that strictly reduces \(D\) reduces it to at most zero. This is exactly the paper’s swap-bundle definition, expressed at the level of positive-mass bundle configurations.

My lead anchor is Corollary 11, proved in this paper. It states that for team-based valuations, an EF1 allocation always exists and can be found in polynomial time. The paper’s own motivating picture—large teams of faculty or workers receiving tasks—is already a credible high-multiplicity setting: many agents share a small number of team/role/preference types, and their externality depends on whether work goes to themselves, a teammate, or another team.

The corresponding continuous problem is:

“Given rational type masses \(\mu\), rational per-capita supplies \(\beta\), and team-based values
\[ u_{r,s,a}= \begin{cases} c\,w_{r,a} & \text{if }s\text{ is a teammate of }r,\\ 0 & \text{otherwise}, \end{cases} \qquad 0\le c<1, \]
does there exist a finite-support allocation law \(\lambda\) satisfying EF1?”

If yes, the solution is the allocation law \(\lambda\). I would expect this problem to be Class A. Theorem 10, proved here, transforms agent/item-correlated externalities into an equivalent ordinary fair-division instance; Corollary 11 then supplies polynomial-time EF1 existence and construction for the team case. In the high-multiplicity version, identical agents can be grouped and the resulting allocation handled by a configuration LP, high-multiplicity integer program, or related typed-allocation method. The natural complexity question is whether this can be made polynomial in the number of types and the encoding length, rather than in the number \(N\) of workers.

This mirror is particularly plausible because it preserves the paper’s central phenomenon. Agents still care about who receives items, and EF1 is still defined by swapping bundles and removing actual indivisible items. The only homogenisation is that two workers with the same role and team relationships are treated as one type—exactly the high-multiplicity interpretation of “same type.”

A second, more general anchor is Theorem 4, proved here: \(\varphi\)-FAIR DIVISION WITH EXTERNALITIES, for \(\varphi\in\{\mathrm{EF},\mathrm{EF1},\mathrm{EFX}\}\), is fixed-parameter tractable in the number of item types \(\Upsilon\) and agents \(|N|\). Its continuous counterpart asks:

“Given \(r\) agent types, \(q\) item types, rational masses and supplies, and arbitrary typed externality values \(u_{r,s,a}\), does there exist an EF, EF1, or EFX allocation law?”

The expected classification is again Class A for fixed \(r+q\), although this would be a new theorem rather than an immediate consequence of Theorem 4. The paper’s proof already points toward the method: guess which item types occur in each bundle pattern and solve a low-dimensional integer program. In the population mirror, one replaces named agents by finitely many agent types and uses a high-multiplicity configuration formulation. Further questions include whether EFX remains FPT in \(r+q\), whether support size can be bounded by a function of those parameters, and whether one can obtain approximation algorithms when the number of types is moderate but not fixed.

The paper’s negative result should be treated as a boundary, not as a reason to reject the mirror. Theorem 2, proved here, shows that EFX-FAIR DIVISION WITH EXTERNALITIES is NP-complete even with three agents and no weak chores. The unrestricted continuous problem above should therefore be expected to contain a Class B region: the hardness is driven by the combinatorics of assigning item bundles and comparing externalities, not by a large population. A precise boundary question is whether the theorem’s reduction survives after every one of the three roles is replaced by a positive-mass cohort of identical agents. If it does, EFX remains hard even with a fixed number of agent types; if it does not, that failure would identify a genuinely continuum-specific tractable regime.

I would not use Theorem 3 as a main anchor. Although it has only three item types and six values, its agents encode graph-edge identities and therefore need not form a small set of complete agent types. It is useful evidence about the boundary, but not a clean high-multiplicity success story.

The scope here is population continuization. Item copies remain indivisible; \(\lambda\) records the mass of agents receiving each integer bundle. No outcome-space lottery, divisible-resource allocation, noise model, or analytic mean-field limit is being smuggled in.

The weakest point is the EFX definition itself. In a nonatomic population, swapping one individual has zero aggregate mass, so EFX must be defined through tagged representative agents and their integer bundles, as above. A referee who insists that continuum fairness must be expressed only through aggregate utility may reject this formulation. The answer is that the paper’s fairness notion is inherently individual and bundle-based; preserving that local comparison is necessary for a faithful mirror. Within that interpretation, the team-based EF1 problem is a strong positive case, while the general EFX problem offers a meaningful tractability/hardness boundary rather than a reason to abandon continuization.