During the last decade, the main focus of the fair division literature has been on allocating a set M of indivisible goods, and one of the main fairness goals within this line of work is to limit the amount of envy between any two agents. Since it is well-known that some amount of envy is inevitable when allocating indivisible goods (e.g., one of the goods could be more valuable than all other goods combined, so any agent who receives it is bound to be envied), a vast amount of work has focused on relaxations of "envy-freeness" and the extent to which they can be achieved or approximated.
A central problem within this literature is regarding the existence of allocations satisfying the EFX property, introduced by Caragiannis et al. (2019). An allocation is EFX if removing any good from the bundle allocated to an agent would ensure that no agent envies the remaining bundle. Despite a plethora of attempts to prove the existence (or nonexistence) of EFX allocations in general, this problem remains open. Plaut and Roughgarden (2020) proved the existence of EFX allocations for two agents with general monotone valuations. For instances with three agents, Chaudhury, Garg, and Mehlhorn (2024) were able to prove the existence of EFX allocations for additive valuations, and this was subsequently extended to nice-cancelable valuations (a special case of cancelable valuations) by Berger et al. (2022) and even more general (e.g., MMS-feasible) valuations by (Akrami et al. 2023). The existence of EFX allocations for instances involving four agents remains a very challenging open problem, even in the case of additive valuations.
Our work focuses on an interesting relaxation of EFX, namely EF2X. An allocation is EF2X if removing any two goods from the bundle allocated to an agent would ensure that no agent envies the remaining bundle. This notion was introduced by Akrami, Rezvan, and Seddighin (2022), who proved that an EF2X allocation exists for instances involving any number of agents, but with restricted additive valuations: an agent's value for a bundle equals the sum of their value for each good, but their value for each good g is restricted to be either 0 or v(g), where the latter value is the same for all agents. In a very recent work, Kaviani, Seddighin, and Shahrezaei (2024) proved the same result for a different class of valuations ((∞, 1)-bounded valuations). This class defines a good to be relevant for an agent if its marginal value is not always zero, and the crucial restriction is that any two agents share at most one relevant good.
Rather than significantly restricting the valuations that the agents may have, we focus on valuations that are much more expressive, and we study the existence of EF2X allocations for instances involving four agents. Specifically, we consider cancelable valuations, introduced by Berger et al. (2022), which strictly generalize the well-studied class of additive valuations. A valuation v is cancelable if for any two bundles S, T ⊂ M and any good g ∈ M \ (S ∪ T ), we have that v(S ∪ {g}) > v(T ∪ {g}) implies v(S) > v(T ).
Our main result uses a constructive argument to prove that EF2X allocations always exist for any instance involving
The Thirty-Ninth AAAI Conference on Artificial Intelligence four agents with cancelable valuations.
Theorem: For every instance involving four agents with cancelable valuation functions and any number of goods there exists an EF2X allocation.
In fact, we only require three of these agents to have cancelable valuations; our result holds even if one agent has arbitrary monotone valuations. Furthermore, we show that we can compute such an allocation in pseudopolynomial time.
Proving this result is quite demanding, as it inherits a lot of the complexity of the EFX problem. Note that proofs of EFX existence for three agents tend to be quite long, requiring non-trivial techniques and careful case analysis. As a result, extending those arguments to instances with four agents becomes rather intractable. We overcome this obstacle by introducing some new notions and techniques that are likely to be useful more broadly, e.g., for solving the EFX problem; in fact, the allocation that we compute is often EFX, not just EF2X. These contributions allow us to make the problem more tractable, but our algorithm and its analysis are still quite long and technically demanding.
As a secondary result, we apply the same tools to instances involving three agents, leading to an algorithm that computes an EF2X allocation in polynomial time.
Theorem: For every instance involving three agents with cancelable valuations and any number of goods we can compute an EF2X allocation in polynomial time.
Due to space limitations, we provide only an overview of our results and defer most of the technical content to the full version of the paper (Ashuri, Gkatzelis, and Sgouritsa 2024).
EFX allocations have been shown to exist for any number of agents when these agents have identical valuations (Plaut and Roughgarden 2020), lexicographic preferences (Hosseini et al. 2021), additive valuations with at most two types of goods (Gorantla, Marwaha, and Velusamy 2023), as well as binary valuations (Halpern et al. 2020), subsequently extended to bi-valued valuations (Amanatidis et al. 2021). Christodoulou et al. (2023) proved EFX allocations exist when the agent's valuations are captured by a graph.
Another line of research has aimed to achieve multiplicative approximations of EFX. Plaut and Roughgarden (2020) showed the existence of 1/2-EFX allocations for subadditive valuations (subsequently derived in poly-time by Chan et al. (2019)), and Amanatidis, Markakis, and Ntokos (2020) proved the existence of 1/ϕ ≈ 0.618-EFX allocations for additive valuations. For more restrictive valuation functions, Markakis and Santorinaios (2023) and Amanatidis, Filos-Ratsikas, and Sgouritsa (2024) proved the existence of 2/3-EFX allocations. Barman, Kar, and Pathak (2024) achieved improved EFX approximations for restricted settings.
For more general settings, a lot of work has focused on relaxations of EFX. One such relaxation has focused on "partial allocations," donating some of the goods to charity and achieving EFX with the rest. This was first studied by Caragiannis, Gravin, and Huang (2019) who showed the exis-tence of a partial allocation that satisfies EFX and its Nash social welfare is half of the maximum possible. Chaudhury et al. (2021) proved that EFX allocations exist for n agents if up to n -1 goods can be donated; moreover, no agent envies the donated bundle. Berger et al. (2022) improved this number to n -2 goods with nice cancelable valuations, and Mahara (2024) extended this to monotone valuations. Berger et al. (2022) further showed that an EFX allocation exists for 4 agents with at most one donated good. The number of donated goods was subsequently improved at the expense of achieving (1ε)-EFX, instead of exact EFX (Chaudhury et al. 2023;Akrami et al. 2023;Berendsohn, Boyadzhiyska, and Kozma 2022;Jahan et al. 2023).
The existence of (approximate) EFX has also been studied along with Nash social welfare (NSW) guarantees. Amanatidis et al. (2021) showed that for additive bi-valued preferences, maximizing the NSW is always EFX. The tradeoff between EFX and NSW was recently studied by Feldman, Mauras, and Ponitka (2024).
Another well-studied relaxation of EFX is envy freeness up to one good (EF1), introduced by Budish ( 2010). An allocation is EF1 if for every pair of agents i and j, there exists some good in j's bundle whose removal would ensure that i does not envy j. Lipton et al. (2004) showed that EF1 allocations always exist, even for general monotone valuations, and can be computed efficiently. There have been several other relaxations for EFX that are stronger than EF1, like EFL (Barman et al. 2018), EFR (Farhadi et al. 2021), EEFX and MXS (Caragiannis et al. 2023), and their combinations (e.g., MXS and EFL (Ashuri and Gkatzelis 2024))).
For the case of chore allocation, recently Christoforidis and Santorinaios (2024) showed that the existence of EFX is not guaranteed even for instances with just 3 agents and 6 chores. The non-existence of EFX was also known for mixed goods and chores (mixed manna), where the valuations are not monotone (Bérczi et al. 2024;Hosseini et al. 2023).
A broader overview of discrete fair division can be found in a recent survey by Amanatidis et al. (2023).
An instance of discrete fair division is a tuple ⟨N, M, V ⟩, where N = [n] = {1, 2, . . . , n} is a set of agents, M is a set of m indivisible goods, and V = (v 1 , v 2 , . . . , v n ) is a profile of valuation functions, where v i : 2 M → R ≥0 for each agent i ∈ N determines i's value for each subset of goods. Whenever v i (S) < v i (T ), agent i strictly prefers set T to set S, and we denote this preference by S ≺ i T ; similarly, we use S ⪯ i T to denote weak preference, meaning that v i (S) ≤ v i (T ). For notational simplicity, we sometimes use v(g) to denote v({g}), i.e., the value for a single good, S ∪ g to denote S ∪ {g}, and S \ g to denote S \ {g}. Moreover, when we perform a union over disjoint sets, we sometimes use ⊔ instead of ∪ to emphasize their disjointness.
Types of valuation functions. We consider valuation functions that are monotone, i.e., for any
for any two different bundles S, T . For convenience, throughout the paper, we assume that the valua-tion function of agent 1 is non-degenerate (in the full version of the paper (Ashuri, Gkatzelis, and Sgouritsa 2024) we show that this is without loss of generality). One of the most well-studied classes of valuation functions is additive: a valuation function v is additive if the value for any bundle S ⊆ M is equal to the sum of the values of its goods, i.e., v(S) = g∈S v(g). In this paper, we focus on the more general class of cancelable valuations: a valuation function v is cancelable (Berger et al. 2022) if for any two bundles S, T ⊂ M and any good g ∈ M \ (S ∪ T ), if v(S ∪ g) > v(T ∪ g), then v(S) > v(T ), i.e., removing the same good from two different bundles would not change the relative preference between the two. It is easy to verify that for any cancelable valuation v and bundles S, T, R such that R ⊆ M \ (S ∪ T ) we have the following two properties, which we heavily use throughout the paper:
A class of valuations that is even more general than cancelable valuationsfoot_0 is MMS-feasible valuations: a valuation function v is MMS-feasible if for every bundle S ⊆ M and any two bipartitions of
). Sets of bundles and notation. Throughout the paper, we use X = (X 1 , X 2 , . . . , X k ) and variants such as X ′ and X to denote a partition of all goods M into k (pairwise disjoint) bundles, i.e. i∈[k] X i = M . If the union of the bundles does not need to be equal to the set of all goods, we instead use
to be a most valuable bundle. In the extreme case where v i (Y j ) is the same for all j ∈ [k] (and k ≥ 2), we assign different bundles to L i (Y) and H i (Y), so it always holds that L i (Y) ̸ = H i (Y). For simplicity we write
and similarly for H i .
Given an ordering g 1 ⪯ i g 2 ⪯ i . . . ⪯ i g |S| of the goods of some bundle S induced by the preferences of some agent i, we use ℓ k i (S) for some natural number k ≤ |S| to denote the k-th least valued good in bundle S from agent i's perspective, i.e., ℓ k i (S) = g k . We also denote by h k i (S) the k-th highest valued good in S from agent i's perspective, i.e., h k i (S) = g |S|+1-k . In the extreme case that v i (g) is the same for all g ∈ S (and |S| ≥ 2), we assign different goods to ℓ 1 i (S) and h 1 i (S), so we always have ℓ 1 i (S) ̸ = h 1 i (S). {EF, EFX, EF2X}-envy. We say that an agent i envies some bundle T relative to bundle S ,if S ≺ i T . We say that agent i EFX-envies T relative to S if there exists some g ∈ T such that S ≺ i T \ g, and we denote this by S Î i T . We further write S ̸ Î i T if agent i does not EFX-envy T relative to S. For simplicity, we use (Y 1 , ..., Y p ) ̸ Î i (Y ′ 1 , ..., Y ′ q ) if i does not EFX-envy any of the bundles Y ′ 1 , ..., Y ′ q relative to any of the bundles Y 1 , ..., Y p . We say that agent i EF2X-envies T relative to S if there exist two distinct goods
{EFX, EF2X}-feasibility. Given a set of disjoint bundles of goods Y = (Y 1 , ..., Y k ), we say that bundle Y j is EFXfeasible for agent i (or for valuation v i ) in Y if agent i does not EFX-envy any other bundle in Y relative to Y j . Similarly, we say that Y j is EF2X-feasible for agent i (or for valuation v i ) in Y if agent i does not EF2X-envy any bundle in Y relative to Y j . We say that partition X = X 1 , ..., X n is EFX-feasible (respectively EF2X-feasible) if there is a way to assign each bundle in X to a distinct agent in N , such that each bundle is EFX-feasible (respectively EF2Xfeasible) for the agent it is assigned to in X.
{EFX, EF2X}-best sets. Given a bundle S ⊆ M and some natural number k ≤ |S|, we use G k (S) = {T ⊆ S : |T | = k} to denote the set of subsets of S of size k. Then, if T * ∈ arg max T ∈G k (S) v i (S \ T ), we refer to S \ T * , i.e., the best subset of S that one can get after removing k of its goods, as the best-k-remaining goods of S w.r.t. agent i's valuation. We refer to w k i (S) = v i (S \ T * ) as the best-k-value of a set S for agent i; if k > |S|, we define the best-k-value of a set S for any agent i to be 0. We say that bundle X j is EFX-best and EF2X-best for agent i in X, if it has the maximum best-1-value and best-2-value, respectively, among all bundles in X. We write EFXF i (X), EF2XF i (X), and EFXBest i (X) to denote the set of EFXfeasible, EF2X-feasible, and EFX-best bundles for agent i in partition X, respectively.
e., all of its bundles are EFX-feasible in Y ′ ). If Y j is the least valuable bundle in Y w.r.t. valuation v, the algorithm checks whether Y j is EFX-feasible w.r.t. v in Y. If it is, the algorithm terminates and returns Y. On the other hand, if Y j is not EFX-feasible in Y, then there must exist another bundle Y i such that v(Y j ) < v(Y i \g) for some good g ∈ Y i . The PR algorithm then removes g from Y i , adds g to Y j , and repeats the same sequence of steps until it reaches an EFX-feasible set of bundles.
Our main result (Theorem 1) proves the existence of an EF2X allocation for instances involving an arbitrary number of goods and four agents with cancelable valuations; in fact, one of them can have an arbitrary monotone valuation.
Theorem 1. For every instance involving four agents with cancelable valuation functions and any number of goods, there exists an EF2X allocation and we can compute one in pseudo-polynomial time.
As the theorem statement suggests, instead of a purely existential argument, we provide a constructive proof using an algorithm that computes an EF2X allocation in pseudopolynomial time. The algorithm starts with some arbitrary initial partition of the goods into four bundles and it gradually manipulates this until it reaches a partition that is EF2Xfeasible. Given the complexity of the problem, the ways in which the algorithm gradually transforms a partition aiming to achieve EF2X-feasibility are quite non-trivial and technical. Therefore, to be able to clearly present this algorithm, we define a sequence of stages (formally defined later on), each of which determines a list of structural properties that a partition in that stage needs to satisfy. Given these stages, we can provide a high-level description of this complicated algorithm using the simple diagram of Figure 1.
Our algorithm follows a sequence of steps, each of which takes as input some partition X = (X 1 , X 2 , X 3 , X 4 ) and returns a partition X = ( X1 , X2 , X3 , X4 ). The way in which each step transforms X into X depends on the stage that X is in, i.e., on the structural properties that X satisfies. Using these properties, our algorithm carefully re-arranges the goods across bundles, and our proof shows that the resulting partition, X, satisfies all of the corresponding properties of a new stage. The diagram of Figure 1 illustrates the high-level structure of the algorithm by providing a node for each stage that a partition X may be in, and a directed edge between two stages for each step that transforms a partition X to X. E.g., the edge from stage B1 to stage B2 corresponds to a transformation that takes as input a partition X in stage B1 and returns a partition X in stage B2 (see Theorem 22).
The algorithm starts with an arbitrary initial partition and it uses the PR algorithm to get a partition whose bundles are all EFX-feasible for agent 1. It then turns this into an instage partition (the first stage in Figure 1). From that point onward, at the end of every step (i.e., after using each edge of Figure 1), any bundle in the resulting partition X will have at least one agent for whom it is EFX-feasible in X. If we can match the agents to bundles that are EF2X-feasible for them, then the algorithm terminates. If not, then we essentially identify an "under-demanded" bundle (one that is EFX-feasible for agent 1, but not EF2X-feasible for any other agent) and some "over-demanded" bundles. Each step then carefully re-distributes goods across these bundles to make the under-demanded bundle more appealing.
To ensure that the algorithm is "making progress" toward its goal of reaching an EF2X allocation, we use a potential function that weakly increases after each step. Specifically, we set aside one agent (Agent 1), who plays a special role throughout the algorithm, and we use that agent's value for the first bundle of the partition as the potential of that partition. Definition 2 (potential function). The potential of a partition X is ϕ(X) = v 1 (X 1 ).
Note that the bold edges in Figure 1 (all edges going upward) correspond to steps of the algorithm that guarantee a strict increase of the potential. All other edges ensure that the potential does not drop. Using this observation, combined with the fact that the number of potential increases can be at most pseudo-polynomial and that each step takes pseudopolynomial time, we can conclude that the overall running time of this algorithm is pseudo-polynomial (details deferred to full version (Ashuri, Gkatzelis, and Sgouritsa 2024)).
We now provide the formal definitions of the stages.
i) X 4 is EFX-best for at least one agent j ̸ = 1 and
for some agent i ̸ = 1, and X 4 ∈ EFXF j (X) for some agent j / ∈ {1, i}.
Definition 5 (in-stage partition). We say that a partition is in-stage if it is either in stage A or in stage B.
Definition 6 (stage B1). We say partition X is in stage B1 if it is in stage B, X 4 ∈ EFXBest j (X), and also:
2 ) Definition 7 (swap-optimal sets). We say that two sets (S, T ) are swap-optimal w.r.t. the agents i and j if there exist no g ∈ S, h ∈ T such that g ⪯ i h, h ⪯ j g and at least one of these two preferences is strict.
Definition 8 (stage B2). We say partition X is in stage B2 if it is in stage B1 and (X 3 , X 4 ) are swap-optimal w.r.t. the agents i and j that satisfy the conditions of stage B.
Definition 9 (stage B2i). We say partition X is in stage B2i if it is in stage B2 and also the following conditions hold:
) Definition 10 (stage B2ii). We say partition X is in stage B2ii, if it is in stage B2 and also:
Outline of the Paper. Given the multiple subtleties that our algorithm needs to address, it is infeasible to fit it all within the page limit. In Section 4, we provide some useful lemmas. Then, as a warm-up, Section 5 provides the transformations applied to partitions that are either in stage A or in stage B. Section 6 discusses the swap-optimization process, and Section 7 provides a sample of some more technical arguments required for dealing with partitions in stage B1. The even more technical arguments used for partitions in stage B2, stage B2i, stage B2ii, as well as the process for computing EF2X allocation for three agents in polynomial time are deferred to (Ashuri, Gkatzelis, and Sgouritsa 2024). We conclude with Section 8, providing a high-level description of some of the broader technical contributions.
We now provide some lemmas and observations that we use repeatedly in subsequent proofs. Due to space limitations we defer their proofs to (Ashuri, Gkatzelis, and Sgouritsa 2024), where we also include additional lemmas and observations. Lemma 11. Given a bundle S and an agent i with a cancelable valuation function, if g 1 , . . . , g k are the k least valued goods in S w.r.t. agent i, then w k i (S) = v i (S \{g 1 , . . . , g k }). The following lemma establishes an important property of EFX-best bundles: if some bundle X j is not EFX-feasible for some agent i in some partition, then this agent EFXenvies the EFX-best bundle in the partition relative to X j .
. Similar statement holds for EF2X-feasible and EF2X-best bundles.
The following three lemmas are related to some processes for redistributing goods, which we will be using repeatedly.
Lemma 13. Given any partition X, we can construct a new partition X that is either EF2X-feasible or in-stage with ϕ( X)
Lemma 14. Given any partition X such that X 4 is EFXfeasible for some agent j ̸ = 1, we can construct a new partition X that is either EF2X-feasible or in-stage with ϕ( X) ≥ min r∈
The following is one of the most important lemmas of the paper. The algorithm starting with a partition X in stage B will aim to either find an EF2X-feasible partition or satisfy the following lemma's conditions, so it can ensure progress. Lemma 16. Given a partition X in stage B, suppose that Y is a set of disjoint bundles such that
pose further, that there exists some agent i ̸ = 1, such that Y 3 ∈ EFXF i (Y), and some agent j / ∈ {1, i}, such that Y 4 ∈ EFXF j (Y). Then we can construct a new partition X that is either EF2X-feasible or in-stage with ϕ( X) > ϕ(X).
We now prove that if we start with a partition X in Stage A, then we either construct an EF2X-feasible partition, or we construct another in-stage partition with higher potential. We further prove (Theorem 18) that a partition X that is in stage B is either EF2X-feasible or in stage B1. Theorem 17. Given any partition X in stage A, we can construct a new partition X that is either EF2X-feasible or instage with ϕ( X) > ϕ(X).
Proof. We first address the case where X satisfies the condition i of stage A, and then the condition ii.
Stage Ai (X 4 is EFX-best for some agent j ̸ = 1, X 4 \ ℓ 1 j (X 4 ) ⪰ j X 1 ∪ ℓ 1 j (X 4 )): We define X ′ = (X 1 ∪ ℓ 1 j (X 4 ), X 2 , X 3 , X 4 \ ℓ 1 j (X 4 )). Since X 4 ∈ EFXBest j (X), agent j does not EFX-envy bundles X 2 , X 3 relative to bundle X 4 \ ℓ 1 j (X 4 ). Also, since X 1 ∪ℓ 1 j (X 4 ) ⪯ j X 4 \ℓ 1 j (X 4 ), we get that X ′ 4 ∈ EFXF j (X ′ ). Additionally, we have that min r∈
, since agent 1's valuation is non-degenerate. Therefore, by Lemma 14, we can construct a new partition X that is either EF2Xfeasible or in-stage with ϕ( X) ≥ min r∈[3] v 1 (X ′ r ) > ϕ(X), and the theorem follows for this case.
Stage Aii (X 4 is EFX-best for at least two distinct agents i, j ̸ = 1): We consider the case that X is not in stage Ai, otherwise we would show the theorem as in the previous case. Therefore, for any u ∈ {i, j}, we have
. By rearranging the bundles we define
), and so it also holds that
Then, by Lemma 15, we can construct a new partition X that is either EF2X-feasible or in-stage with ϕ( X) ≥ min(v 1 (X 2 ), v 1 (X 3 )) > v 1 (X 1 ) = ϕ(X), since agent 1's valuation is non-degenerate, which concludes the proof.
EFX-best bundle in X ′′ , which is different from X ′′ 3 . Let this bundle be X4 , and the two remaining bundles among X ′′ 1 , X ′′ 2 , X ′′ 4 be X1 , X2 such that X1 ≺ 1 X2 . We finally define the partition X = ( X1 , X2 , X ′′ 3 , X4 ) .
Note that since X1 , X2 ∈ EFXF 1 ( X), X ′′ 3 ∈ EFXF i ( X) and X4 is EFX-feasible for both agents other than 1 and i, if for any of the agents j / ∈ {1, i}, X1 or X2 is EFXfeasible in X, this partition would be EFX-feasible, so assume otherwise. So for any agent j / ∈ {1, i}, ( X1 , X2 ) ̸ ∈ EFXF j ( X), and therefore, by Lemma 12, X4 \ ℓ
By setting X = X and repeatedly transforming the partition as above, we reach a partition that satisfies the conditions of the theorem since we strictly increase the cardinality of the third set in each round.
We conclude with a high-level summary of some of the new notions and techniques that can be of independent interest.
EFkX-Best-Bundle. One concept that we introduce is the EFkX-best bundle in a set of bundles Y for some agent i (see Section 2 for a definition). This satisfies the very useful property that any bundle that is EFkX-best (and, hence, also EFkX-feasible) for some agent i, remains EFkX-feasible even if we remove i's k least valued goods from it (and keep those goods unallocated). This holds since the remaining bundle is, by definition, at least as valuable for i as any other bundle T , after the removal of any k goods from T . This is a property that we leverage when, during some reallocation process, we remove goods from some bundle, temporarily leading to a partial partition.
To extract useful conditions for full partitions, we combine the above idea with the following observation: Given a partition, let S be the EF2X-best bundle for some agent i and T be another bundle that is not EF2X-feasible for i. Then, if i received T , she would EF2X-envy S; even if we removed i's two least valuable goods from S, she would still prefer S to T . However, the trick here is to instead remove just the one least valuable good of S and add it to T . This gives a (full) partition where agent i still prefers the new bundle S to the new bundle T (this is due to cancelable valuations). Moreover, since S was EF2X-best for i before, it remains at least EF2X-feasible for i after this change. This way, some "underdemanded" bundle has gained a new good, and the one that was EF2X-best for i is still at least EF2X-feasible for her, even though it lost a good. Such re-allocations allow us to make progress toward the final allocation.
Although this procedure will eventually increase the number of bundles that are EF2X-feasible for an agent, we cannot use it by itself: it may compromise EF2X-feasibility for other agents, who may end up EF2X-envying the bundle that gained a good. To avoid this, we require conditions for other agents (one example is achieved by the swap-optimization that we discuss next) and possibly some case analysis.
Swap-Optimization. We also introduce a procedure we call swap-optimization, in which two bundles, each associated with a different agent, swap items in such a way that those agents are more satisfied with their new bundles.
Swap-Optimization is useful to overcome some issues discussed at the end of the EFkX-Best-Bundle paragraph. Specifically, consider a partition of the goods such that three bundles, S, T , and Q, satisfy that S is EF2X-best for agent i, T is EF2X-best for agent j, and Q is not EF2X-feasible for either of them. Given such conditions, the EFkX-Best-Bundle paragraph suggested moving to Q either i's least valued good from S or j's least valued good from T . To ensure that this does not cause any envy, we can first perform swap-optimization between S, T w.r.t. i, j, which maintains these initial conditions (by Lemmas 21 and 12). If g is i's least valuable good in S and h is j's least valuable good in T after the swap-optimization, we move to Q i's least valuable good in {g, h}. This guarantees that neither i nor j will envy the resulting bundle Q. To see this, suppose i weakly prefers h to g. Then, j also weakly prefers h to g, since S and T were swap-optimized. As we argued in the EFkX-Best-Bundle paragraph, i will not envy the resulting bundle Q after adding g to it. Similarly, agent j would not envy Q even if we were to move h from T to Q, so she will not envy Q if we add g to it, which she values less, and keep T unchanged. Similar arguments apply if the moved good is h.
Maintaining EFX-feasibility for 2 agents & more goods. The following fact also plays a crucial role in our algorithm. Suppose i, j are two agents with MMS-feasible valuations, and Y = (Y 1 , Y 2 ) are two disjoint bundles such that Y 1 and Y 2 are EFX-feasible for agents i, j, respectively, in Y. Suppose now that we want to introduce a set S of additional goods and re-allocate, so that the above conditions are preserved. In the full version of the paper (Ashuri, Gkatzelis, and Sgouritsa 2024) we show that it is possible to rearrange all those goods and derive a set of two disjoint bundles
1 and Y ′ 2 are EFX-feasible for agents i, j, respectively, in Y ′ , and moreover, both agents are weakly more satisfied than before, i.e., Y ′ 1 ⪰ i Y 1 and Y ′ 2 ⪰ j Y 2 . This tool is useful in cases where two agents are EFXfeasible with one distinct bundle each, and in our attempt to satisfy another agent (agent 1), we need to remove some goods from another bundle and then add them to the bundles associated with these two agents without breaking the condition that those bundles are EFX-feasible for them.
The fact that every cancelable valuation is MMS-feasible is shown in Lemma
ofAkrami et al. (2023). They claim that "nice" cancelable valuation are MMS-feasible, but their definition of nice cancelable coincides with our definition of a cancelable function, which is also the one originally used byBerger et al. (2022).