An EF2X Allocation Protocol for Restricted Additive Valuations

1 Introduction

Fair allocation deals with the problem of allocating a resource to agents with diverse preferences. Due to the wide range of applications, this problem has received attention in different fields such as economics, mathematics, and computer science [Lipton et al., 2004; Brams and Taylor, 1996].

In the early studies, the resource was assumed to be a heterogeneous divisible cake. This case has been mostly considered by mathematicians and economists under the title of "Cake Cutting". In contrast, recent studies often focus on more practical cases where the resource is less divisible. Such instances arise in many real-world scenarios, e.g., dividing the inherited wealth among heirs, divorce settlements, etc [Endriss, 2017; Brandt et al., 2016]. In the indivisible case, the resource is a set M of indivisible goods that must be divided among n agents. Each agent i has a valuation function vi : 2M →R and the goal is to allocate the goods to the agents while satisfying a certain fairness objective.

∗Contact Author

Envy-freeness is one of the most well-studied fairness notions in the literature. Formally, let X = 〈X1,X2, . . . ,Xn〉 be an allocation that allocates bundle Xi to agent i. We say agent i envies agent j, if vi(Xi) < vi(Xj). An allocation is envy-free, if no agent envies another agent.

Perhaps one of the reasons that envy-freeness is widely accepted among economists is that, despite strict conditions, there are strong guarantees for this notion in the divisible setting. For example, there always exists an envy-free allocation of the cake such that each agent receives a connected piece [Stromquist, 1980]. However, beyond divisibility when dealing with a set of indivisible goods, this notion is too strong to be satisfied. For example, consider an instance with two agents and one good for which both agents have positive valuation. Such barriers have led to natural relaxations of envy-freeness that are more suitable for the case of indivisible goods. Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are among the most prominent relaxations of envy-freeness for indivisible goods. The idea behind these two notions is to allow a limited amount of envy among the agents. Formally, given allocation X = 〈X1, X2, . . . , Xn〉, we say X is

• EF1 (Budish [2011]): if for every agents i and j, there exists a good g ∈ Xj s.t. vi(Xi) ≥ vi(Xj \ {g}).
• EFX (Caragiannis et al. [2019b]): if for every agents i and j, and every good g ∈ Xj , vi(Xi) ≥ vi(Xj \ {g}).1

By definition, every envy-free allocation is also EFX, and every EFX allocation is also EF1. So far, we know that when the valuation functions are monotone, EF1 allocations always exist and can be found in polynomial time [Lipton et al., 2004]. In sharp contrast, it turns out that the EFX notion is much more challenging. Currently, the existence of an EFX allocation is only proved for very limited cases [Plaut and Roughgarden, 2020; Chaudhury et al., 2020a; Barman et al., 2018b; Amanatidis et al., 2021].

Recent findings on EFX suggest that avoiding a subset of goods may result in strong EFX guarantees. This subject (also known as EFX with charity) is pioneered by the work of Caragiannis et al. [2019a] wherein the authors show that there exists an allocation that discards a subset of goods and finds an EFX allocation for the rest of the goods such that the Nash welfare 2 of the allocation is at least half of the optimal Nash welfare. Several follow-up works have reduced the number and the total value of the discarded goods [Chaudhury et al., 2020b; Berger et al., 2021].

1 The original definition of EFX assumes that the removed good g has an additional property that vi(Xj \ {g}) < vi(Xj). However, our existential results in Sections 5 and 6 work for the more general case where vi(Xj \ {g}) ≤ vi(Xj).

In this paper, we focus on the EFX notion and its relaxations (including EFX with charity) when the valuation functions are restricted additive. The restricted additive setting is an important subclass of additive setting that has gained popularity in allocation problems during the past decade and particularly for maximin fairness notion [Asadpour et al., 2012; Svensson, 2012; Feige, 2008; Jansen and Rohwedder, 2017; Bansal and Sviridenko, 2006; Cheng and Mao, 2018; Annamalai et al., 2017; Cheng and Mao, 2019; Khot and Ponnuswami, 2007]. In the restricted additive setting, the assumption is that the valuation functions are additive, and furthermore, each good g has an inherent value v(g) so that for any agent i, we have vi(g)∈ {0, v(g)}.

1.1 Our Contribution

We start by introducing EFkX notion which is indeed a relaxation of EFX that allows an amount of envy up to the value of k least valuable goods of a bundle. Our main result is Algorithm 2 that finds a complete EF2X allocation for restricted additive valuations. The algorithm consists of 4 updating rules plus an additional final step. As long as it is possible, we update the allocation using one of the updating rules. When none of the rules is applicable, we perform the additional step to obtain a complete allocation. The rules are based on new concepts, namely configuration and envy-elimination which we describe in the following.

Configuration. One important point of departure of our method from the existing techniques is that alongside updating the allocation, we maintain a partitioning of the agents into several groups. This partitioning has the property that the value of the agents in the same group are close to each other. We use the term configuration to refer to a pair of an allocation and a partition. The updating process at each step takes a configuration as input and updates both the allocation and the partition. Well-established concepts such as champion and champion-graph are also revised in accordance with the definition of configuration.

Envy-elimination. At the heart of our updating rules we exploit a process called envy-elimination. Envy-elimination is designed to circumvent deadlocks. At several points during the algorithm we might allocate a good to an agent that violates the EFX property. In such situations, we execute the envy-elimination process. This process restores the EFX property by merely eliminating goods from the bundles of agents. Therefore, at the end of this process, the value of each agent for her bundle is not more than her value beforehand.

AnewPotential Function. Note that the fact that the social welfare strictly decreases after the envy-elimination process might question the termination of our algorithm. This brings us to another challenge: we must show that the algorithm ends after a finite number of updates. To prove the termination of the algorithm, we introduce a potential function Φ which maps a pair σ = (X, R) of a partial allocation X and a partition R of agents to a vector Φ(σ) of rational numbers and show that after each update, Φ (σ) increases lexicographically. This indicates that the updating process terminates after a finite number of updates. Note that for a given configuration σ, function Φ(σ) relies on both X and R.

2 The Nash welfare is the geometric mean of the values of agents.

We later turn our attention beyond EF2X to see whether our new tools can be used to obtain better guarantees for the EFX notion. Our second result is Algorithm 3 that finds a partial EFX allocation which discards less than ⌊n/2⌋ goods. The currently best known result in this direction is the work of Berger et al. [2021] which proves the existence of a partial EFX allocation that discards at most n - 2 goods when the valuation of agents are restricted to some superclass of additive valuations. This result was further improved to general valuations by Mahara [2021]. Compared to them, our algorithm reduces the number of discarded goods for the restricted additive setting by a factor of 2.

2 RelatedWork

We refer the reader to [Brams and Taylor, 1996] for an overview on fair division, classic fairness notions, and related results. The notion we study in this paper is EFX which is a relaxation of envy-freeness for the case that the resource is a set of indivisible goods. EFX is among the most studied fairness notions in recent years and "Arguably, the best fairness analog of envy-freeness for indivisible items" [Caragiannis et al., 2019b]. This notion originates in the work of Caragiannis et al. wherein the authors provide some initial results on EFX and its relation to other notions. However, despite extensive investigations, the existence of a complete EFX allocation is only proved for very limited cases: when the number of agents is 2 or 3 [Plaut and Roughgarden, 2020; Chaudhury et al., 2020a], and when the valuations are either identical [Plaut and Roughgarden, 2020], binary [Barman et al., 2018b], or bi-valued [Amanatidis et al., 2021]. Given this impenetrability of EFX, a growing strand of research started considering its relaxations. These relaxations can be classified into three categories:

Approximation. One approach is to find allocations that are approximately EFX. The first result in this direction is a 1/2-EFX allocation [Plaut and Roughgarden, 2020] which is later improved to 0.618 [Amanatidis et al., 2020].

Weakening the fairness requirement. Recall that in an EFX allocation, any possible envy is removed by eliminating the least valuable good. Recently, Farhadi et al. [2021] suggest a relaxed version of EFX called EFR in which instead of eliminating the least valuable good to evaluate fairness, it eliminates a good uniformly at random. They show that a 0.73-EFR allocation always exists. Another example is envyfreeness up to one less preferred good (EFL) [Barman et al., 2018a] which limits the value of the eliminated good. The EFkX notion we introduced in Section 1.1 also falls within this category.

Discarding a subset of goods. Another approach is to relax the assumption that the final allocation must allocate all the goods. This line is initiated by the work of Caragiannis et al. [2019a] wherein the authors prove the existence of a partial EFX allocation whose Nash welfare is at least half of the optimal Nash welfare. Following this work, Chaudhury et al. [2020b] proved the existence of a partial EFX allocation that leaves at most n - 1 goods unallocated. Berger et al. [2021] decreased the number of discarded goods to n - 2 for a super class of additive valuations and Mahara [2021] extended this result to general valuations. Recently, Chaudhury et al. [2021] presented a framework to obtain a (1 - ϵ)-EFX allocation with sub-linear number of unallocated goods for ϵ ∈ (0, 12 ]. Our result in Section 6 falls within this category.

3 Preliminaries

We denote the set of agents by N = {1, 2, . . . , n} and the set of goods by M. Each agent i has a valuation function vi : 2M → R+ which represents the value of that agent for each subset of the goods. An allocation is a specification of how goods in M are divided among the agents. We denote an allocation by X = 〈X1, X2, . . . , Xn〉, where Xi is the bundle allocated to agent i. Allocation X is complete if ⋃i Xi = M, and is partial otherwise. For a partial allocation X, we refer to the set of goods that are not allocated to any agent as the pool of unallocated goods and denote it by PX. When X is clear from the context, we simply use P instead of PX. We say a good g is wasted, if it is allocated to an agent that has zero value for g. Typically, non-wasteful allocations refer to allocations that admit no wasted good.

In this paper, we are interested in allocations that satisfy certain fairness properties. In Section 1, we defined the EFX notion. Here we define a more general form of EFX, namely, envy-freeness up to any k goods or EFkX.

Definition 3.1. An allocation X = 〈X1, ...,Xn〉 is EFkX, if for all i ̸= j and every collection of ℓ = min(k, |Xj|) distinct goods g1, g2, . . . , gℓ ∈ Xj we have vi(Xi) ≥ vi(Xj \ {g1, g2, . . . , gℓ}).

In particular, an EFX allocation is EFkX with k = 1. Our main results are related to the cases where k = 1 and k = 2.

Restricted Additive Valuations. We consider a special case of valuation functions in which each good g has an inherent value v(g) and the contribution of g to any set of goods for any agent is either 0 or v(g). Under this restriction, when the valuations are also additive, we call them restricted additive.

Definition 3.2. A set {v1, v2, . . . , vn} of valuation functions is restricted additive, if for every 1 ≤ i ≤ n, vi is additive, and for every good g ∈ M, we have vi(g) ∈ {0, v(g)}. 3

For a set S of goods we define v(S) as ∑g∈S v(g).

3.1 Configurations

In this work, we represent the status of our algorithm at each step via two ingredients: a partial allocation X and a partition R of the agents. A partition of a set is a grouping of its elements into non-empty subsets such that every element is included in exactly one subset. For a partition R, we denote the i'th group of R by Ri.

3 For ease of notation, we use vi(g) instead of vi({g}).

For brevity, we use the term configuration to refer to a pair of an allocation and a partition. At each step during our algorithms we take a configuration (X, R) as input and return another configuration (X′ ,R′ ). Our algorithms are developed in such a way that the configurations satisfy three structural properties. Property 1 requires that the allocation is EFX.

Property 1 (EFX). A configuration σ = (X,R) is EFX, if allocation X is EFX.

Note that Property 1 is independent of the partition. The second property we consider for configurations incorporates both the allocation and the configuration.

Property 2 (Envy-compatibility). A configuration (X,R) is envy-compatible, if for all 1 ≤ ℓ ≤ |R| we have

where

For an envy-compatible configuration (X,R), for every 1 ≤ ℓ ≤ |R| we define rℓ as in Equation (1) and call rℓ the representative of group Rℓ. Furthermore, we suppose that the groups in R are sorted according to the utility of their representatives, i.e., vr1 (Xr1 ) ≤ vr2 (Xr2 ) ≤ . . . ≤ vr|R| (Xr|R| ). Note that for an allocation X, there might be several different partitions R such that configuration (X,R) is envycompatible. For example, one trivial such partition is to put each agent into a separate group. However, our interest is the configurations that are more specific. In addition to Properties 1 and 2 our desired configurations admit another important property. Before introducing this property, we must define the notions of champion and champion-graph. These concepts were first introduced in [Chaudhury et al., 2020a]. We revise their definition to incorporate configurations.

Definition 3.3. Let (X,R) be a configuration satisfying Property 2 and let i ∈ Rℓ be an agent. Then, for every subset S such that vi(S) > vrℓ (Xrℓ ), we define [S | i] to be a smallest subset of S such that vi ([S | i]) > vrℓ (Xrℓ ). In case of multiple options for [S | i], we pick one arbitrarily.

We now define champion and champion-graph as follows.

Definition 3.4 (Champion and Champion-graph). Given a configuration σ = (X,R) satisfying Property 2, we say i ∈ Rℓ is a champion of S if vi(S) > vrℓ (Xrℓ ) and for every agent j ̸= i with j ∈ Rk and g ∈ [S | i] we have vrk (Xrk ) ≥ vj([S | i] \ {g}). We also define the championgraph of σ, denoted by Hσ as follows: for every agent i there is a vertex in Hσ. Edges of Hσ are of two types:

• Regular edges: for every pair of agent i, j with i ∈ Rℓ, there is a directed edge from i to j, if vi(Xj) > vrℓ (Xrℓ ).
• Champion edges: for every pair of agents i, j and every unallocated good g, there is a directed edge from i to j with label g, if i is a champion of Xj ∪ {g}.

The last property we consider for configurations is based on the champion-graph.

Algorithm 1 Envy-elimination

Input : instance (N,M, (v1, . . . , vn)), allocation X Output: configuration (X′ ,R′ ) 1: while ∃i ∈ N, g ∈ Xi s.t. vi(g) = 0 do 2: Xi ←Xi \ {g} 3: ℓ ← 1 4: while N ̸= ∅ do 5: rℓ ← arg mini∈N vi(Xi) 6: X′rℓ ←Xrℓ 7: Rℓ ← {rℓ} 8: N ←N \ {rℓ} 9: while ∃j ∈ Rℓ, i ∈ N s.t. vj(Xi) > vrℓ (Xrℓ ) do 10: X′ i ← [Xi | j] 11: Rℓ ← Rℓ ∪ {i} 12: N \ {i} 13: ℓ ← ℓ + 1 14: Return (X′ , 〈R1,R2, . . . ,Rℓ-1〉)

Property 3 (Admissibility). A configuration σ = (X, R) satisfying Property 2 is admissible if the following hold:

• For all 1 ≤ ℓ ≤ |R| and i ∈ Rℓ, there is a path from rℓ to i in Hσ using only regular edges.
• For all ℓ < k, i ∈ Rℓ and j ∈ Rk, vrℓ (Xrℓ ) ≥ vi(Xj) holds. I.e., there is no regular edge fromRℓ to Rk.

Lemma 3.5. Let X be a non-wasteful allocation, and let (X,R) be a configuration satisfying Properties 2 and 3. Then, X is EFX.

4 Envy-elimination

One important part of our algorithm is an auxiliary process which we call envy-elimination. This process is designed to bypass possible deadlocks in the updating processes. This process takes an allocation X as input and returns a configuration (X′ ,R′ ) satisfying Properties 1, 2 and 3. To do so, the process first retakes all the wasted goods. Then, the process chooses an agent with the minimum valuation, i.e., argminvi(Xi). This agent is selected as the representative of set R1 (thus we call her r1). Next, as long as there exists an agent j ∈ R1 and an agent i ∈ N \ R1 such that vj(Xi) > vr1 (Xr1 ), we modify the bundle of agent i to [Xi | j] and add agent i to R1. Note that, the goods in Xi \ [Xi | j] are returned to the pool. When no more agent could be added to R1, we repeat the same process on the agents in N \R1 to construct R2, R3 and so on. We terminate the process when all agents are added to some partition Ri.

Algorithm 1 shows a pseudocode of the envy-elimination process. We denote the allocation returned by this process by X′ and denote the partition by R′ = 〈R1, R2, . . . , R|R′ |〉. Note that, by the way we construct X′ , after the process, the valuation of each agent for her bundle is at most her valuation before the process. However, as we show in Lemma 4.1, the output of this process (X′ , R′ ) satisfies Properties 1, 2 and 3.

Lemma 4.1. Let X be an allocation and σ = (X′ ,R′ ) be the result of running envy-elimination process on X. Then σ satisfies Properties 1, 2 and 3.

5 An EF2X Allocation Algorithm

In this section, we present our algorithm for finding a complete EF2X allocation. Our algorithm consists of four updating rules U0, U1, U2, and U3. We start with configuration σ = (X,R), where X is an empty allocation and R = 〈{1}, {2}, . . . , {n}〉. At each step, we take the current configuration σ = (X,R) as input and update it using one of these rules. These rules are designed in a way that they always (lexicographically) increase the value of Φ(σ), where

Therefore, after a finite number of updates we obtain a configuration to which none of the updating rules is applicable. Note that, Since we guarantee that σ is envy-compatible, Φ(σ) is well-defined. Recall that r1, r2, . . . , r|R| are the representative agents of partition R.

Afterwards, we show that the remaining goods have a special property that allows us to allocate them to the agents without violating the EF2X property. In other words, if for an allocation X during the algorithm none of the rules is applicable and goods g1, . . . , g|P | are not allocated, then we can find |P| different agents i1, i2, . . . , i|P| such that allocation X′ with

is EF2X. Algorithm 2 shows a pseudocode of our algorithm. In the rest of this section, we first describe the updating rules. For each rule, we prove that the resulting configuration satisfies Properties 1, 2, and 3. Also, we prove that all the rules are Φ-improving. Finally, we describe how we can allocate the remaining goods to maintain the EF2X property.

5.1 Rule U0

We start with rule U0 which is our most basic rule. This rule allocates an unallocated good g to a representative, such that the resulting configuration satisfies Properties 1, 2 and 3. In the following, you can find a schematic view of Rule U0.

Preconditions:

• σ = (X, R) satisfies Properties 1, 2 and 3.
• There exists a good g ∈ P and an index ℓ s.t. vrℓ (g) = 0 and for every 1 ≤ k ≤ |R| and i ∈ Rk, vi(Xrℓ ∪ {g}) ≤ vrk (Xrk ).

Process:

• Allocate g to rℓ.
• Set R′ = R.

Guarantees:

• σ′ = (X′ ,R′ ) satisfies Properties 1, 2, and 3.
• Φ(σ′ )≻lex Φ(σ).

Algorithm 2 Complete EF2X allocation

Input : instance (N,M, (v1, . . . , vn)) Output: allocation X 1: X ← 〈∅, ∅, . . . , ∅〉 2: R ← 〈{1}, {2}, . . . , {n}〉 3: while U0 or U1 or U2 or U3 is applicable do 4: Let i be the minimum index s.t. Ui is applicable 5: Update (X,R) via Rule Ui 6: for t ← |R| to 1 do 7: while ∃i ∈ Rt ∩N s.t. vi(P) > 0 do 8: Choose such i with maximum distance from Rt 9: g ← arg maxh∈P vi(h) 10: Xi ← Xi ∪ {g} 11: N ← N \ {i} 12: Let PX = {g1, g2, . . . , g|PX|} 13: Let i1, i2, . . . , i|PX| be |PX| different agents in N 14: for ℓ ← 1 to |PX| do 15: Xiℓ ←Xiℓ ∪ {gℓ} 16: Return X

5.2 Rule U1

This updating rule updates the allocation using a special type of cycle in the champion-graph called champion cycle.

Definition 5.2. For a configuration σ = (X, R), a cycle C in Hσ is a champion cycle, if for every champion edge i g-→ j in C, j ∈ {r1, r2, . . . , r|R|}. Moreover, for every two champion edges of C with labels g and g′ , we have that g ̸= g′ .

In U1, we find a champion cycle in Hσ and update the allocation through this cycle. Then, we apply envy-elimination.

Preconditions:

• σ = (X, R) satisfies Properties 1, 2 and 3.
• There exists a champion cycle C in Hσ.

Process:

• For every edge i → j ∈ C, set ˜Xi =Xj.
• For every champion edge i g-→ j ∈ C, set ˜Xi = [Xj ∪ {g} | i].
• For every agent j /∈ C, let ˜Xj =Xj.
• Apply envy-elimination on ˜X.

Guarantees:

• σ′ = (X′ ,R′ ) satisfies Properties 1, 2, and 3.
• Φ(σ′ )≻lex Φ(σ).

Since we apply envy-elimination in the last step of Rule U1, Lemma 4.1 implies that the resulting configuration satisfies Properties 1, 2, and 3.

Lemma 5.3. Rule U1 is Φ-improving and preserves Properties 1, 2, and 3..

5.3 Rule U2

In this updating rule, we check if there is exists a representative such that her value for at least one of the remaining goods is non-zero. If so, we simply allocate it to that representative and apply envy-elimination.

Preconditions:

• σ = (X, R) satisfies Properties 1, 2 and 3.
• There exists a representative rℓ and an unallocated good g s.t. vrℓ (g) = v(g).
• Rules U0 and U1, are not applicable.

Process:

• Allocate g to rℓ.
• Apply envy-elimination.

Guarantees:

• σ′ = (X′ ,R′ ) satisfies Properties 1, 2, and 3.
• Φ(σ′ )≻lex Φ(σ).

Lemma 5.4. Rule U2 is Φ-improving and preserves Properties 1, 2, and 3.

5.4 Rule U3

Unlike the previous rules, in Rule U3 the agent to whom we allocate a good is not a representative in σ. Here we find an unallocated good g and a non-representative agent i such that vi(g) = v(g) and allocating g to agent i violates the EF2X property.

Preconditions:

• σ = (X, R) satisfies Properties 1, 2 and 3.
• Rules U0, U1, and U2 are not applicable.
• There exists i ∈ Rℓ \ {rℓ} with distance d from rℓ in Hσ and another i′ ∈ Rℓ′ with distance d′ (ℓ′ , d′ ) and
• from rℓ′ in Hσ such that (ℓ, d) ⪰lex there exists g ∈ P such that vi(g) = v(g) and i′ envies Xi ∪ {g} even after removal of 2 goods.

Process:

• Allocate g to i.
• Apply envy-elimination on X.

Guarantees:

• σ′ = (X′ ,R′ ) satisfies Properties 1, 2, and 3.
• Φ(σ′ )≻lex Φ(σ).

Lemma 5.5. Rule U3 is Φ-improving and preserves Properties 1, 2, and 3.

Algorithm 3 EFX allocation with ≤ n/2 discarded goods

• Input : instance (N,M, (v1, . . . , vn)) Output: allocation X 1: X ← 〈∅, ∅, . . . , ∅〉 2: R ← 〈{1}, {2}, . . . , {n}〉 3: while U0 or U1 or U2 or U4 is applicable do 4: Let i be the minimum index s.t. Ui is applicable 5: Update (X,R) via Rule Ui

• 6: Return X

5.5 Allocating the Remaining Goods

As we mentioned, our algorithm continues to update the allocation as long as one of the rules is applicable. Since there are finitely many possible allocations and the potential function Φ increases after each update, we eventually end up with a configuration σ = (X,R) s.t. none of the rules can be applied on σ. At that moment, if allocation X allocates all the goods, we are done. Otherwise, there are some goods remaining in the pool. In this section, we show how to allocate these goods so that the final allocation preserves the EF2X property.

Generally, our strategy is to find |P| different agents and allocate one good to each one of them. The process of allocating the remaining goods is illustrated in Algorithm 2. In this algorithm, we start by ℓ = |R| and as long as there is an agent i ∈ Rℓ ∩ N such that vi(P) > 0, we give i her most desirable good from the pool 4 and remove i from N. Then we decrease ℓ by one and repeat the same process. The process goes on until either no good remains in the pool, or ℓ = 0. Let us call the set of agents that receive one good in this process by N1. Let us denote the set of unallocated goods at this stage by M2. In case that ℓ = 0 and the pool is still not empty (i.e., M2 ̸= ∅), we allocate each remaining good to an arbitrary agent in N \ N1 (one good to each agent). We denote the agents that receive some good in M2 by N2.

Theorem 5.6. Given restricted additive valuations, Algorithm 2 returns a complete EF2X allocation.

6 An EFX Allocation with at most ⌊n/2⌋ - 1 Discarded Goods

In this section we present an algorithm that leaves aside at most ⌊n/2⌋ - 1 many goods and finds an EFX allocation for the rest of the goods. Algorithm 3 shows a pseudocode of our allocation method. Similar to Algorithm 2, Algorithm 3 starts with empty allocation X and partition R = 〈{1}, {2}, . . . , {n}〉. Our algorithm consists of four updating rules U0, U1, U2 and U4. At each step, we take the current configuration as input and update it using one of these updating rules. Rule U0, U1, and U2 are already defined in Section 5. Similar to these rules, Rule U4 is designed in a way that the value of Φ(σ) increases after each update. When none of these rules is applicable, the algorithm terminates.

In the rest of this section, we describe the new updating rule, namely U4 and its properties. Next, based on these properties we prove Theorem 6.3 which states that the final allocation is EFX and discards less than ⌊n/2⌋ goods.

4 If there were multiple such goods, we select one arbitrarily.

6.1 Rule U4

In this rule, we consider the whole set of the goods in the pool to update the input σ = (X,R). This rule states that if the set of the goods in the pool has a champion i ∈ Rℓ, we update the allocation as follows: we find a path from rℓ to i and update the allocation through this path. Then we apply envy-elimination to obtain σ′ = (X′ , R′ ).

Preconditions:

• σ = (X, R) satisfies Properties 1, 2 and 3.
• There exists an agent who envies PX.

Process: Let i ∈ Rℓ be a champion of P and let rℓ = j1 → j2 · · · → jp = i be a path in Hσ.

• For all 1 ≤ t ≤ p-1, set ˜Xjt =Xjt+1 .
• Set ˜Xi = [P | i].
• Apply envy-elimination on ˜X.

Guarantees:

• σ′ = (X′ ,R′ ) satisfies Properties 1, 2, and 3.
• Φ(σ′ )≻lex Φ(σ).

Lemma 6.1. Rule U4 is Φ-improving and preserves Properties 1, 2, and 3.

6.2 Bounding the Number of Discarded Goods

As we mentioned, when none of the updating rules is applicable, we terminate the algorithm. As we proved in Lemmas 5.1, 5.3, 5.4 and 6.1, the allocation after each update is EFX. Therefore, the final allocation preserves the EFX property as well. Also, since the value of Φ(σ) increases after each update, Algorithm 3 terminates after a finite number of updates. It only remains to prove that the number of remaining goods in the pool is less than ⌊n/2⌋, which we prove in Lemma 6.2.

Lemma 6.2. Let P be the pool of unallocated goods at the end of Algorithm 3. Then, we have |P| < ⌊n/2⌋. Also, no agent envies P .

Finally, Lemma 6.2 together with the fact that the final allocation is EFX yields Theorem 6.3.

Theorem 6.3. Assuming that the valuations are restricted additive, Algorithm 3 returns an allocation X and a pool P of unallocated goods such that

• X is EFX, and
• vi(Xi) ≥ vi(P) for every agent i, and
• |P| < ⌊n/2⌋.