Tight Asymptotic Bounds for Fair Division with Externalities

1 Introduction

Fair division of indivisible items, including administrative tasks, laboratory equipment, or heritage between heirs, is an active research area that connects computer science and economics [Brams and Taylor, 1996; Thomson, 2016; Amanatidis et al., 2023; Nguyen and Rothe, 2023]. Traditionally, a fair division instance consists of a set of indivisible items and a set of agents, where each agent has a valuation function assigning a numerical utility to each possible bundle. Crucially, in the standard model, the utility of an agent depends solely on the items allocated to it. The goal is to partition the items among agents so that a given fairness criterion is satisfied. A prominent example is envy-freeness (EF) [Foley, 1967], which requires that each agent weakly prefers its own bundle over the bundle of any other agent. Since EF allocations are not guaranteed to exist (consider two agents and one positively-valued item), several relaxations have been studied, most notably envy-freeness up to one item (EF1) [Lipton et al., 2004; Budish, 2011; Caragiannis et al., 2019] and envy-freeness up to any item (EFX) [Caragiannis et al., 2019; Plaut and Roughgarden, 2020]. It is known that EF1 allocations always exist in the standard fair division model [Lipton et al., 2004].

Nevertheless, there are many scenarios where the utility an agent experiences cannot depend solely on its own bundle. Consider a dormitory allocating newly purchased equipment among students: a student benefits not only from items given directly to them, but also from items assigned to their roommate, with whom they can share. Conversely, when dividing resources among competing firms, such as exclusive licenses, patents, or territory rights, a firm may be harmed when a rival acquires a valuable asset, even if the firm's own allocation remains unchanged. Externalities can also be mixed: when distributing research grants among academics, a researcher may benefit if a collaborator receives funding for a joint project but suffer if a competitor in the same field does. All these examples have one aspect in common: the inherent externalities underlying the agents' valuations.

Although externalities are well studied in the broader economics literature on resource allocation [Ayres and Kneese, 1969; Katz and Shapiro, 1985; Velez, 2016], most prior work in fair division focuses on divisible items [Brˆanzei et al., 2013b; Li et al., 2015]. The model of fair division of indivisible items with externalities was formulated only recently [Seddighin et al., 2019; Mishra et al., 2022; Aziz et al., 2023; Deligkas et al., 2024]. Most relevant to our work are Aziz et al. [2023], who adapted the standard envy-based fairness notions to the externalities setting, and Deligkas et al. [2024], who investigated the computational complexity of deciding whether a fair allocation exists.

Despite this progress, perhaps the most fundamental question in this area has remained open:

Is an EF1 allocation guaranteed to exist for every instance of fair division with externalities?

Our current understanding of this question is limited. EF1 allocations are known to always exist for two agents, and for three agents with binary valuations and no chores 1 [Aziz et al., 2023]. Beyond these special cases, even the existence of EF-k allocations for any constant k was unknown. Aziz et al. [2023] explicitly state that:

An important open question that remains from our work is whether there always exists an EF1 allocation [...] If the answer is negative, it would be reasonable to ask for the optimal relaxation EF-k that can be attained.

Deligkas et al. [2024] further conjectured that EF1 allocations always exist for binary valuations, while acknowledging that a proof "seems highly non-trivial" given the extensive case analysis and computer verification required even for the case of three agents.

1.1 Our Contribution

We show that EF1 allocations do not always exist, even if agents' preferences are binary, hence resolving the open question posed by both Aziz et al. [2023] and Deligkas et al. [2024]. We supplement this by showing that the optimal relaxation EF-k that can be attained is for k = Θ(√n), where n is the number of agents in the instance, answering the second open question of Aziz et al. [2023].

After a formal definition of the model of fair division with externalities in Section 2, we introduce the technical tools that we use to prove our results in Section 3. There are two main ingredients. First, we introduce an asymmetric envy model and show its equivalence with the externalities model. Valuations in the asymmetric envy model are closer to the standard additive valuations than the valuations in the original externalities model. That said, this model is mostly of theoretical interest: the valuations are not easy to interpret, and even a social-welfare maximizing allocation is not welldefined with these valuations. The second key component of our work is the framework of multicolored discrepancy [Doerr and Srivastav, 2003; Manurangsi and Suksompong, 2022; Caragiannis et al., 2025; Manurangsi and Meka, 2026]. Importantly, we generalize some of the discrepancy bounds known from prior work to settings with a mixture of goods and chores, which may be of independent interest.

In Section 4, we use the technical toolbox developed in Section 3 to show that, for any fair division with externalities, there exists a deterministic polynomial-time mechanismM1 that finds an allocation that is envy-free up to O(√n) items. Importantly, in Section 5, we show that the mechanism is asymptotically optimal. Specifically, we show that there is an instance in the externalities model such that the best relaxation EF-k we can achieve is for k ∈ Ω(√n), even if the valuations are binary and there are no chores. This settles the question of the existence of EF1 in the negative and therefore refutes the conjecture of Deligkas et al. [2024]. Moreover, we show that the same lower bound holds for instances where the externalities are highly structured: even when all externalities are directed towards a single designated agent a1.

Before we conclude in Section 7 with open problems and future directions, in Section 6, we present an additional randomized mechanismM2. This mechanism always produces an allocation that is EF up to O(n) items, which is a worse guarantee than that of mechanismM1. However, unlikeM1, M2 produces a consensus allocation, which means that we can arbitrarily permute the bundles while maintaining the fairness guarantee. Consequently, M2 is truthful in expectation, i.e., no agent can improve its expected utility by misreporting its valuations. This extends the result of Bu and Tao [2025] to the setting of externalities, with a slightly weaker bound on the relaxation of fairness that we obtain.

1 See Section 2 for a formal definition of chores in this model.

1.2 RelatedWork

Apart from the papers directly studying externalities in fair division of divisible and indivisible items mentioned above, there are several streams of related models in the literature.

First, there is a model of fair division with allocator's preferences [Bu et al., 2023] or social impact [Flammini et al., 2025; Deligkas et al., 2026]. In both of these models, the goal is to find an allocation that is not only fair among agents, but also satisfies certain objectives of the allocator. This additional dimension of preferences can in principle be represented using externalities: the allocator is an additional agent with externalities towards all other agents. However, the crucial difference is that the allocator cannot receive any item and the original agents do not have any pairwise externalities. A more general model is fair division for groups [Manurangsi and Suksompong, 2017; Suksompong, 2018; Segal-Halevi and Nitzan, 2019; Manurangsi and Suksompong, 2024; G¨olz and Yaghoubizade, 2026; Dupr´e la Tour, 2026], where agents are partitioned into groups and share items allocated to their group, while each agent retains their own subjective valuations, and for which constant relaxations of envy-freeness are known to not exist in most settings.

In asymptotic fair division [Manurangsi and Suksompong, 2020; Manurangsi and Suksompong, 2021; Manurangsi and Suksompong, 2025; Manurangsi et al., 2025; Garg et al., 2026], the task is not to decide which relaxation of fairness we can guarantee (since EF1 allocations always exist in the standard model), but rather to identify conditions under which stronger guarantees such as envy-freeness or proportionality can be achieved. Many of these works provide tight bounds with respect to the number of items required and rely heavily on results from discrepancy theory, similarly to our approach.

Externalities in preferences also appear in contexts beyond fair division. Notable examples include combinatorial auctions [Funk, 1996; Jehiel and Moldovanu, 1996; Zhang et al., 2018], matching [Mumcu and Saglam, 2010; Brˆanzei et al., 2013a; Fisher and Hafalir, 2016; Anshelevich et al., 2017], facility location [Li et al., 2019; Wang et al., 2024; Li et al., 2025], and house allocation [Massand and Simon, 2019; Elkind et al., 2020; Agarwal et al., 2021; Gross-Humbert et al., 2022; Knop and Schierreich, 2023]. In these settings, an agent is typically assigned only one item (a partner, location, or house), and the solution concepts differ substantially from ours.

2 Preliminaries

In the fair division problem, the input is a set M of indivisible items and a set N of n agents. The items in M are to be allocated among the agents in N. Formally, an allocation of the items is a tuple of pairwise disjoint subsets of M: (A1, . . . , An), where each Ai ⊆ M is the bundle assigned to agent i. We say that allocation is complete if ⋃i∈[n] Ai = M. Unless stated otherwise, we consider only complete allocations. Let A be the set of all allocations. Additionally, we denote the set {1, . . . , n} by [n].

In the fair division with externalities model of [Aziz et al., 2023], each agent i ∈ N is associated with a function

which assigns a value to every allocation A ∈ A. We assume that valuations are additive: for any agent i ∈ N and any allocation (A1, . . . , An) ∈ A,

where x(j) ∈ A denotes the allocation in which agent j receives the single item x and all other agents receive no items, that is,

To simplify the notation, we write Vi(j, x) for Vi (x(j) ) and therefore

Note that additivity implies, in particular, that valuations are normalized: for every agent i ∈ N, the empty allocation has value zero, i.e., Vi(∅, . . . , ∅) = 0.

We say that the valuation Vi of agent i ∈ N has no chores if, for every agent j ∈ N and every item x ∈ M, we have

That is, agent i weakly prefers receiving item x herself to another agent receiving x.

We say that Vi is binary if, for all j ∈ N and all x ∈ M,

2.1 Fairness in the Externalities Model

Given an allocation A ∈ A and two distinct agents i, j ∈ N, we denote by Ai↔j the allocation obtained from A by swapping the bundles of agents i and j, while the bundles of all other agents remain unchanged. In an allocation A, agent i envies agent j if

that is, agent i would prefer to swap her bundle with that of agent j. An allocation A is envy-free (EF) if no agent envies another agent. A is envy-free up to c items (EF-c) if, for every pair of distinct agents i, j ∈ N, there exists a set of items S ⊆ M with |S| ≤ c such that, defining B = (A1\S, . . . , An\S), we have

That is, for each pair of agents i and j, there exists a set of at most c items whose removal eliminates agent i's envy toward agent j.

Note that, since valuations are assumed to be additive, the set S used to eliminate agent i's envy toward agent j can always be chosen as a subset of Ai ∪Aj , as the items allocated to other agents contribute equally to Vi(B) and Vi(Bi↔j ). Moreover, if the valuation Vi has no chores, the set S can be chosen as a subset of Aj. Finally, in the absence of externalities (i.e. when Vi(j, x) = 0 for every item x and pair of agents i, j) this definition coincides with the standard definition of envy-freeness up to c items.

3 Technical Tools

In this section, we present some technical tools that we use in our proofs. First, we present an alternate model of fair division instances, the asymmetric envy model, and prove that this model is equivalent for our purposes. Next, we describe the multicolor discrepancy problem and its connections to fair division. Most of our results derive fair division bounds from bounds in multicolor discrepancy.

3.1 Asymmetric EnvyModel

We now introduce the asymmetric envy model, which is an alternate fair division model that allows for externalities among the agents' valuation functions. We will show that the asymmetric envy model is equivalent to the externalities model with respect to envy-based notions of fairness. We analyze most of our results using the asymmetric envy model, as the envy-based fairness notions in this model are easier to work with. This model does not assign a numerical value to each agent for a complete allocation; consequently, notions such as welfare maximization are not well defined. Instead, it specifies a notion of envy between pairs of distinct agents i, j ∈ N. The model is asymmetric in the sense that the function defining the envy of agent i toward agent j depends on the ordered pair (i, j). Envy from i towards j is captured by a valuation function vi,j, and the standard notions of envy-freeness and envy-freeness up to c items can be defined using these valuation functions. More precisely, for each pair of agents i, j ∈ N with i ̸= j, we are given a valuation function

We assume that these valuations are additive, that is, for every set S ⊆ M,

We say that vi,j has no chores if vi,j(x) ≥ 0 for all x ∈ M. We say that the instance is binary if vi,j(x) ∈ {0, 1} for all i ̸= j and all x ∈ M.

Fairness in the Asymmetric Envy Model

Given an allocation (A1, . . . , An) ∈ A, agent i is said to envy agent j if

An allocation A is envy-free in the asymmetric envy model (EFa) if no agent envies another agent. A is envy-free up to c items in the asymmetric envy model (EFa-c) if, for every pair of distinct agents i, j ∈ N, there exists a set of items S ⊆ Ai ∪ Aj with |S| ≤ c such that

Note that if vi,j has no chores, the set S can always be chosen as a subset of Aj .

Next, we show that the asymmetric envy model is equivalent to the externalities model with respect to envy-based fairness notions such as envy-freeness and EF-c. That is, there exists a natural reduction from instances of the externalities model to those of the asymmetric envy model, such that any envy bound in the asymmetric envy model implies an equivalent bound in the externalities model.

Proposition 1. There exists a function f that maps each instance I of the externalities model to an instance f(I) of the asymmetric envy model such that, for every allocation A ∈ A, the allocation A is EF (respectively, EF-c) in I if and only if it is EFa (respectively, EFa-c) in f(I). Moreover, if I has no chores then f(I) has no chores. Additionally:

• For any instance J in the asymmetric envy model with additive valuations, there is an instance I in the externalities model such that J = f(I) (i.e., f is surjective).
• For any instance J in the asymmetric envy model with binary additive valuations, there is a binary no-chores instance I in the externalities model such that J = f(I).

3.2 Multicolor Discrepancy and Fair Division

Manurangsi and Suksompong [2022] showed that tools from multicolor discrepancy can be leveraged to derive improved bounds for fairness notions of the form EF-c in models with groups of agents. In this section, we describe the particular definitions and discrepancy guarantee that we will use later. We also extend their statement from the "goods-only" case to instances that may contain both goods and chores.

We present a multicolor discrepancy in a formulation tailored to allocations of indivisible items. This is equivalent to the standard matrix-based definition, but is more convenient for our purposes. The version of multicolor discrepancy that we need is a recent generalization of Manurangsi and Meka [2026]; it is an asymmetric setting in which valuations depend on the color. For a broader introduction to the connection between discrepancy theory and fair division, we refer the interested reader, e.g., to [Manurangsi and Suksompong, 2022; Dupr´e la Tour and Fujii, 2025].

Let k ≥ 1 be an integer denoting the number of colors, and let M be a set of m items. Let n1 ≥ · · · ≥ nk be positive integers. For each ℓ ∈ [k], let Vℓ = {vℓ,1, . . . , vℓ,nℓ } be a collection of nℓ additive valuation functions, and define V = (V1, . . . , Vk).

A k-coloring of M is a map χ : M → [k], which induces a partition

The asymmetric discrepancy of V is defined as

In words, asymdisc(V, k) is the minimum, over all kcolorings of M, of the maximum (over colors and valuation functions) deviation between the value that vℓ,i assigns to its own color class and the proportional benchmark 1k vℓ,i(M).

Theorem 1 (Manurangsi and Meka [2026, Theorem 5.4]). Assume that for every ℓ ∈ [k], i ∈ [nℓ], and x ∈ M, we have vℓ,i(x) ∈ [0, 1]. Then

Moreover, a coloring achieving this bound can be found in deterministic polynomial time [Levy et al., 2017].

In the symmetric case where n = n1 = · · · = nk and where vℓ,i = vℓ′ ,i for all i ∈ [n] and all ℓ, ℓ′ ∈ [k], this result coincides exactly with Theorem A.1 of Manurangsi and Suksompong [2022].

We will use Theorem 1 together with the following lemma to obtain EFa-c guarantees. A related implication is implicit in the proof of the upper bound in Manurangsi and Suksompong [2022]; here, we prove an extension that allows for a mixture of goods and chores. The lemma shows that it suffices to control discrepancy with respect to four suitably chosen auxiliary valuations with item values in [0, 1]: if two bundles are approximately balanced under each of these auxiliary valuations, then any envy between them under the original valuation can be eliminated by discarding only a small number of items.

Lemma 1. Let k ≥ 1 and let T be a positive integer threshold. Let v : 2M → R be an additive valuation function that may assign both positive and negative values to items. Then there exist four auxiliary additive valuation functions v1 , v2 , v3 , v4 : 2M → R such that vj (x) ∈ [0, 1] for all j ∈ [4] and all x ∈ M, and with the following property: If A,B ⊆ M are two disjoint sets of items satisfying for all j ∈ [4] and all X ∈ {A, B}

then one can eliminate A's envy for B under the original valuation v by discarding at most 14T items from A ∪ B, and similarly, one can eliminate B's envy for A by discarding at most 14T items fromA∪B.

For the lower bound, we will use the closely related notion of p-weighted discrepancy. Given a set V = {v1, . . . , vn} of n additive valuation functions and a parameter p ∈ (0, 1), the p-weighted discrepancy is defined as

Theorem 3.2 of Manurangsi and Meka [2026] establishes the following lower bound.

Theorem 2 ([Manurangsi and Meka, 2026]). For every p ∈ (0, 1) and n ∈ N, there exist a set M of items and a collection V = {v1, . . . , vn} of n binary additive valuation functions such that

4 An O(√n) Upper Bound

We now combine Lemma 1 with the asymmetric discrepancy result of Manurangsi and Meka [2026] (Theorem 1) to obtain an O(√n) bound in the asymmetric envy model. This construction is non-consensus, i.e. it produces an allocation (A1, . . . ,An) tailored to the agent labels, and the guarantee does not necessarily hold under permutations of the bundles.

Theorem 3. Let M be a set of items and let (vi,j)i,j∈N, i̸=j be an instance of the asymmetric envy model with n agents, where each vi,j is additive and may assign both positive and negative values to items. Then there exists a partition

such that for every ordered pair of distinct agents i, j ∈ N, one can eliminate i's envy toward j (measured by vi,j) between Ai and Aj by discarding at most O(√n) items from Ai ∪ Aj. Equivalently, the allocation A = (A1, . . . ,An) is EFa-O(√n). Moreover, such an allocation can be computed in deterministic polynomial time.

Proof. Let k := n (the number of colors). Let T = O(√n) be the discrepancy bound promised by Theorem 1 when applied with

For every ordered pair i ̸= j, apply Lemma 1 to the valuation function vi,j with parameters k = n and T . This yields four additive valuation functions

with vt i,j (x) ∈ [0, 1] for all t ∈ {1, 2, 3, 4} and x ∈ M.

We now build an asymmetric discrepancy instance with k = n colors as follows. For each color ℓ ∈ [n], define the multiset of valuation functions

Thus |Vℓ| = 8(n-1) for every ℓ, and all functions in all Vℓ satisfy the boundedness condition of Theorem 1.

Applying Theorem 1 yields a coloring χ : M → [n] such that for every ℓ ∈ [n] and every u ∈ Vℓ,

Let Aℓ := χ-1 (ℓ). Then (A1, . . . , An) is a partition of M. Fix any ordered pair i ̸= j. By construction, the four functions v1 i,j , . . . , v4 i,j belong to both Vi and Vj, so for each t ∈ {1, 2, 3, 4} we have

and

Thus condition (1) of Lemma 1 holds for the disjoint sets Ai and Aj (with k = n), and Lemma 1 implies that i's envy toward j with respect to vi,j can be eliminated by discarding at most 14T = O(√n) items from Ai ∪ Aj .

Since this holds for every ordered pair i ̸= j, the allocation is EFa-O(√n). Deterministic polynomial-time computability follows from Theorem 1.

By combining Theorem 3 with repeated application of Proposition 1, we obtain the same upper-bound also for the externalities model.

Corollary 1. Given an instance of the externalities model with n agents, there exists a deterministic polynomial-time algorithm that outputs an allocation (A1, . . . ,An) that is EF-O(√n).

5 An Asymptotically Tight Lower Bound

In this section, we prove a matching lower bound, showing that Corollary 1 is asymptotically tight, even if the instance is binary additive and with no chores. For simplicity, we first prove our lower bound in the asymmetric envy model with binary valuations. We then use Proposition 1 to show that this result implies an equivalent lower bound in the externalities model with binary no-chores valuations.

Let n be any positive odd integer, q = (n - 1)/2, and S1, . . . , Sq be q subsets of a set of items M. For any S ⊆ M, let vS be the binary additive valuation function defined by vS (A) := |A∩ S| for all A ⊆M. Let V = {vS1 , . . . , vSq }.

Using the above valuation profile, we can construct an associated instance of the asymmetric envy model as follows.

For all j ≥ 2, we let v1,j(A) := |A|. For each i ∈ [q], we define ¯ Si := M \ Si. Then, for each i ∈ [q], for all j ∈ [n] \ {2i}, we let

and for all j ∈ [n] \ {2i + 1},

We show that if this instance admits an EFa-c allocation for some integer c, then its 1/n-weighted discrepancy is at most 6c.

Lemma 2. In the above instance, suppose there exists a partition M = A1 ⊔ · · · ⊔ An that is EFa-c for some integer c ≥ 1. Then

Proof. Fix an EFa-c allocationM = A1⊔· · ·⊔An and write m = |M|. By the definition of wdisc1/n(V), choosing the set A1 ⊆ M gives

Since vSi (X) = |Si ∩ X|, we have vSi (M) = |Si| and vSi (A1) = |Si ∩ A1|, hence it suffices to show that for every i ∈ [q],

Fix i and abbreviate ¯ Si = M \ Si.

Step 1: all bundles have almost the same size. Recall that agent 1 values every item at 1, so for every bundle X and every j ≥ 2 we have v1,j(X) = |X|. Since the allocation is EFa-c, for every j ≥ 2,

Moreover, by the definition of the valuation profile (for this fixed i), agent 2i counts Si-items when comparing to agent 1 and counts ¯ Si-items when comparing to agent 2i + 1, and agent 2i + 1 behaves symmetrically. Applying EFa-c along these comparisons yields

and

Combining,

The same argument gives |A2i+1| ≥ |A1| - 3c.

Summing ∑nj=1 |Aj| = m and using these inequalities gives

hence

Step 2: discrepancy for Si. We distinguish two cases.

Case 1: |Si ∩A1| ≤ |Si|/n. Since Si = ⊔nj=1 (Si ∩Aj), by averaging there exists some j ̸= 1 with |Si ∩Aj | ≥ |Si|/n. If j ̸= 2i +1, then EFa-c for agent 2i +1 gives |Si ∩A2i+1| ≥ |Si ∩ Aj | - c ≥ |Si|/n - c; if j = 2i + 1 this is immediate.

Thus

Together with | ¯ Si ∩ A2i+1| ≥ | ¯ Si ∩ A1| - c we obtain

Using |A1| ≥ |A2i+1| - c yields

Since |A1| = |Si ∩ A1| + | ¯ Si ∩ A1|, we conclude

and therefore in Case 1,

Case 2: |Si ∩ A1| ≥ |Si|/n. We first claim that

Indeed, if | ¯ Si∩A1| ≥ | ¯ Si|/n there is nothing to prove. Otherwise, by averaging there exists some j ̸= 1 with | ¯ Si ∩ Aj | ≥ | ¯ Si|/n, and repeating the argument of Case 1 with ¯ Si in place of Si (using agent 2i instead of 2i + 1) gives the bound.

Using the claim and the bound |A1| ≤ m/n + 3c from Step 1,

Since Case 2 assumes |Si ∩ A1| ≥ |Si|/n, we get

In both cases we have shown ∣∣|Si ∩ A1| - |Si|/n∣∣ ≤ 6c. Taking the maximum over i ∈ [q] and recalling vSi (X) = |Si ∩X| yields

and therefore wdisc1/n(V) ≤ 6c.

We now formally present our lower bound for the case of binary no-chores valuations in the externalities model.

Theorem 4. There is a binary no-chores instance of the externalities model with n agents for which every EF-c allocation requires c = Ω(√n).

Proof. The proof of this theorem follows by combining the above lemma with Theorem 2. The instance of Manurangsi and Meka [2026] consists of Θ(n) horizontallystacked copies of 12 (1q×q +H), where 1q×q is a q ×q all-1s matrix and H is a q × q Hadamard matrix. Clearly, this instance is binary. If we let the sets S1, . . . , Sq be given by the hyperedges in this instance (i.e., Si contains the elements whose index in the ith row of the instance of Manurangsi and Meka [2026] contains a 1), then the corresponding valuation profile V consists of q binary additive functions. Taking p = 1/n, Theorem 2 gives us the following bound:

Since q = (n - 1)/2, combining this with Lemma 2 we get

and thus c = Ω(√n) and the corresponding instance in the asymmetric envy model admits no EFa-c allocation for any c ∈ o(√n). Finally, by Proposition 1, there exists a binary no-chores instance in the externalities model for which every EF-c allocation requires c = Ω(√n).

As stated previously, an important implication of this result is that EF1 allocations do not always exist when the agents have externalities, even when the valuations are binary nochores, which refutes a conjecture of Deligkas et al. [2024] and resolves the open question of Aziz et al. [2023].

Theorem 5 (Corollary of Theorem 4). There is a binary nochores instance of the externalities model that admits no EF1 allocation.

Interestingly, the above example in the asymmetric envy model can also be used to construct an instance in the externalities model that is not binary, but instead has the property that agent 1 has no externalities and every other agent in the instance only has externalities towards agent 1. Together, Theorems 4 and 6 show that even highly structured instances with externalities do not allow for EF1 allocations.

Theorem 6. There is an instance in the externalities model with n agents in which every agent has externalities towards only agent 1, and for which every EF-c allocation requires c = Ω(√n).

6 An Ex-Ante Truthful Mechanism

In this section, we present a consensus version of our upper bound, in which the bundles of the resulting allocation can be permuted arbitrarily amongst the agents while maintaining the fairness guarantee. This allows us to implement the resulting construction as a mechanism that is truthful in expectation, i.e., in which no agent can improve its expected value (ex-ante) by misreporting its valuation. Here, the expectation is over the randomness of the mechanism, and truthfulness follows directly from the fact that the agents can be matched to the bundles uniformly at random.

Specifically, we combine Lemma 1 and a symmetric application of Theorem 1 to obtain a generalization of the consensus upper bound of Manurangsi and Suksompong [2022, Theorem 1.3] to a mixture of goods and chores.

Theorem 7. Let v1, . . . , vn be additive valuation functions that may assign both positive and negative values to items, and let k be a number of colors. There exists a partition of the items into k bundles M = A1 ⊔· · ·⊔Ak such that for any ℓ, ℓ′ ∈ [k] and any i ∈ [n], one can eliminate envy (with respect to vi) between Aℓ and Aℓ′ by discarding at most O(√n) items. Moreover, such a partition can be computed in deterministic polynomial time.

The corollary below follows by combining an application of Theorem 7 with the simple mechanism described in [Bu and Tao, 2025] that assigns the bundles uniformly at random.

Corollary 2. Given n agents with additive valuation functions that may assign both positive and negative values to items, there exists a randomized ex-ante truthful mechanism running in polynomial time that outputs an allocation (A1, . . . ,An) that is EF-O(√n).

Proof. The corollary follows from using Theorem 7 with k = n colors, together with the simple mechanism described in [Bu and Tao, 2025], which assigns the bundles uniformly at random. The expected value received by agent i is 1n vi(M), regardless of the reports of the agents. In fact, this guarantee is much stronger than truthfulness: no coalition of agents can influence an agent's expected value.

In the externalities model, we get the following corollary by applying Theorem 7 to the n(n-1) asymmetric envy valuations (vi,j)i̸=j produced by Proposition 1. This yields a consensus bound of order O(√n(n - 1)) = O(n).

Corollary 3. Given an instance of the externalities model, there exists a randomized ex-ante truthful mechanism running in polynomial time that outputs an allocation (A1, . . . ,An) that is EF-O(n).

7 Conclusions

For the fair division of indivisible items amongst agents with externalities, we find asymptotically tight bounds on the optimal relaxation EF-k that can always be attained. Specifically, for the general case of additive valuations, we show that an EF-O(√n) allocation always exists, and give a matching Ω(√n) lower bound even for the special case of binary valuations with no chores. In the process, we answer two open questions of Aziz et al. [2023], and resolve a conjecture of Deligkas et al. [2024], showing that EF1 allocations do not always exist when the agents have externalities. We also present an ex-ante-truthful consensus-based mechanism that finds an EF-O(n) allocation when the agents have externalities. Our work raises interesting new directions for research.

• Small explicit counterexample: Our proof technique shows how to reduce a known lower bound from discrepancy into a collection of lower bound instances for the externalities model. Nonetheless, we leave open the question of describing a small explicit counterexample, and of determining the largest value of n for which an EF1 allocation exists for additive/binary valuations with or without the no-chores condition.
• Closing the constant-factor gap: While our work establishes asymptotically tight bounds of Θ(√n) on the achievable relaxation of envy-freeness with externalities, it leaves a constant-factor gap between the exact values of the upper and lower bounds. A natural resulting open problem is to close this gap.
• Consensus lower-bound: We give an ex-ante-truthful consensus-based mechanism that finds an EF-O(n) allocation when the agents have externalities. Another natural follow-up question is whether there exist a matching lower bound in this setting.
• Other settings: Can our approach be applied to find similar bounds in other settings that are related to fair division with externalities, such as fair division with social impact [Flammini et al., 2025; Deligkas et al., 2026]?

Acknowledgments

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 101002854) and by the European Union under the project Robotics and advanced industrial production (reg. no. CZ.02.01.01/00/22 008/0004590). The first author has been supported by NSERC Discovery Grant 2022-04191.

We are grateful to Adrian Vetta for useful discussions and to the anonymous reviewers of IJCAI '26, whose comments helped us improve the presentation of our results.