# An $\mathsf{EF2X}$ Allocation Protocol for Restricted Additive Valuations

Hannaneh Akrami MPII, SIC, Graduate School of Computer Science, Saarbrücken
Rojin Rezvan University of Texas at Austin Masoud Seddighin School of Computer
Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

###### Abstract

We study the problem of fairly allocating a set of $m$ indivisible goods to a
set of $n$ agents. Envy-freeness up to any good ($\mathsf{EFX}$) criteria —
which requires that no agent prefers the bundle of another agent after removal
of any single good — is known to be a remarkable analogous of envy-freeness
when the resource is a set of indivisible goods [20]. In this paper, we
investigate $\mathsf{EFX}$ notion for the restricted additive valuations, that
is, every good has some non-negative value, and every agent is interested in
only some of the goods.

We introduce a natural relaxation of $\mathsf{EFX}$ called $\mathsf{EFkX}$
which requires that no agent envies another agent after removal of any $k$
goods. Our main contribution is an algorithm that finds a complete (i.e., no
good is discarded) $\mathsf{EF2X}$ allocation for the restricted additive
valuations. In our algorithm we devise new concepts, namely “configuration”
and “envy-elimination” that might be of independent interest.

We also use our new tools to find an $\mathsf{EFX}$ allocation for restricted
additive valuations that discards at most $\lfloor n/2\rfloor-1$ goods. This
improves the currently best known result of Chaudhury et al. [24] for the
restricted additive valuations by a factor of $2$.

##  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,
operations research, politics, and computer science [39, 43, 5, 30, 15, 31,
14, 13, 44].

In the early studies, the resource was assumed to be a single 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 or
indivisible. Such instances arise in many real-world scenarios, e.g., dividing
the inherited wealth among heirs, divorce settlements, border disputes, etc
[18, 16, 28]. In the indivisible case, the resource is a set $M$ of $m$
indivisible goods that must be divided among a set of $n$ agents. Each agent
$i$ has a valuation function $v_{i}:2^{M}\rightarrow\mathbb{R}$ and the goal
is to allocate the goods to the agents while satisfying a certain fairness
objective.

Envy-freeness is one of the most well-established fairness notions studied in
the literature. An allocation is envy-free if each agent prefers her share
over other agents’ share. Formally, let $X=\langle
X_{1},X_{2},\ldots,X_{n}\rangle$ be an allocation that allocates bundle
$X_{i}$ to agent $i$. We say agent $i$ envies agent $j$, if
$v_{i}(X_{i})<v_{i}(X_{j}).$ 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 [45]. 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; the agent that receives no
good envies the other agent. 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
($\mathsf{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=\langle
X_{1},X_{2},\ldots,X_{n}\rangle$ that allocates set $X_{i}$ of goods to agent
$i$, we say $X$ is

  * •

EF1 (Budish [17]): if for every agent $i$ and $j$, there exists a good $g\in
X_{j}$ such that $v_{i}(X_{i})\geq v_{i}(X_{j}\setminus\\{g\\}).$

  * •

$\mathsf{EFX}$ (Caragiannis et al. [20]): if for every agent $i$ and $j$, and
every good $g\in X_{j}$ we have $v_{i}(X_{i})\geq
v_{i}(X_{j}\setminus\\{g\\}).$111The original definition of $\mathsf{EFX}$
[20], assumes that the removed good $g$ has an additional property that
$v_{i}(X_{j}\setminus\\{g\\})<v_{i}(X_{j})$. In Section 7, we denote this more
restricted definition by $\mathsf{EFX^{+}}$. However, our existential results
in Sections 5 and 6 work for the more general case where
$v_{i}(X_{j}\setminus\\{g\\})\leq v_{i}(X_{j})$.

By definition, every envy-free allocation is also $\mathsf{EFX}$, and every
$\mathsf{EFX}$ allocation is also $\mathsf{EF1}$. So far, we know that when
the valuation functions are monotone, $\mathsf{EF1}$ allocations always exist
and can be found in polynomial time [39]. In sharp contrast, it turns out that
$\mathsf{EFX}$ notion is much more challenging. For example, the only
currently known positive result for $\mathsf{EFX}$ is that for 3 agents with
additive valuations an $\mathsf{EFX}$ allocation always exists [22]. For
example, the only currently known positive results on existence of
$\mathsf{EFX}$ allocations are when the valuations are monotone and identical
[41], $n=2$ [41], or $n=3$ and agents have additive valuations [22].

Recent findings on $\mathsf{EFX}$ suggest that avoiding a subset of goods may
result in strong $\mathsf{EFX}$ guarantees. This subject (also known as
$\mathsf{EFX}$ with charity) is pioneered by the work of Caragiannis et al.
[19] wherein the authors show that there exists a procedure that discards a
subset of goods and finds an $\mathsf{EFX}$ allocation for the rest of the
goods such that the Nash welfare222The Nash welfare of an allocation is the
geometric mean of the values of agents. 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 [24, 12].

In this paper, we focus on the $\mathsf{EFX}$ notion and its relaxations
(including $\mathsf{EFX}$ with charity) when the valuation functions are
restricted additive. Restricted additive setting is an important subclass of
additive valuations that has gained popularity in allocation problems during
the past decade [7, 30, 5, 26, 27, 37, 42, 4, 35, 25, 46]. In Section 1.1 we
discuss the restricted additive valuations. Also, we refer to Section 1.2 for
the results and the techniques used in this paper.

###  1.1 Restricted Additive Valuations

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 $v_{i}(g)$$\in\\{0,v(g)\\}$. On the
practical side, this setting captures many real-life scenarios. For example,
when distributing food among people, the nutritious value received by each
person only depends on the food. However, due to allergies, ethics, etc.
people might have different diets and do not eat certain food. Thus, the
nutritious value each person receives by each food $g$ is $0$ if the person
refuses to eat it or is $v(g)$ which solely depends on the food.

On the theoretical side, the restricted additive class can be considered as a
promising middle ground between the identical setting (all the valuations are
similar) and the additive setting. For many allocation objectives, there is a
considerable discrepancy between the results pertaining to these two settings.
For example:

  1. 1.

Maximin-share fairness, or $\mathsf{MMS}$, can be guaranteed for the case of
identical valuations, while it is proved that guaranteeing $\mathsf{MMS}$ for
the additive setting is not always possible [38]. The best known approximation
guarantee for the additive case is $3/4-\epsilon$ [32].

  2. 2.

Guaranteeing EFX for identical additive valuations is easy [41], while whether
or not an EFX allocation exists for the additive setting is unknown. The best
known approximation guarantee for EFX in the additive setting is $0.618$ [3,
29].

  3. 3.

The best polynomial time approximation guarantee for the Nash welfare
objective with additive valuations is $1.45$ [9], while there is a greedy
algorithm with a factor of $1.061$ [10] and a PTAS [40] for the identical
additive setting.

  4. 4.

The best polynomial time approximation guarantee for max-min fairnees in the
additive setting is $O(n^{\epsilon})$ [21, 11], while there exists a PTAS for
the case that the valuations are identical and additive [47].

Considering this gap, it is expedient to study restricted sub-classes of
additive valuations that lie in between these two settings. What makes the
restricted additive setting interesting is that despite the simple and handy
appearance, its structure is fundamentally different from the identical
setting. Indeed, it is believed that for some fairness objectives, the
restricted additive setting is as hard as the general additive case [37].
Except for max-min fairness which has a very interesting and fruitful
literature for the restricted additive setting (termed as the Santa Claus
problem), very few studies consider this type of valuations for other notions.
For max-min fairness, the best known approximation factor for the additive
setting is improved in series of works to $O(\sqrt{n}(\log n)^{3})$[5],
$O(\sqrt{n\log n}/\log\log n)$ [43], and $O(n^{\epsilon})$ [21, 11]. Extensive
investigations on the restricted additive valuations for max-min fairness has
also resulted in constant factor approximation algorithms [4, 5, 27]. The
first breakthrough for this setting is the work of Bansal and Sviridenko [7],
who provide an $O(\log\log n/\log\log\log n)$-approximation solution based on
rounding a certain linear program called configuration LP. Based on an
impressive result of Haxel for hypergraph matchings [34], Asadpour et al. [5]
prove that the integrality gap of Configuration LP is within a factor $4$ for
the restricted additive setting. This bound is slightly improved to $3.84$ by
Jansen and Rohwedder [36] and Cheng and Mao [25]. Recently, Bamas et al. [6]
introduced a submodular version of restricted valuations for the Santa Claus
problem.

To the best of our knowledge, no previous work considers restricted additive
valuations for other objectives such as maximin-share fairness,
$\mathsf{EFX}$, and Nash social welfare. Recently, another class of valuations
called bi-valued is studied for Nash welfare ̵in which the value of each good
to each agent is either $p\in\mathbb{N}$ or $q\in\mathbb{N}$ [1].

In this paper, we initiate the study of $\mathsf{EFX}$ notation, when the
valuations are restricted additive. We refer to Section 1.2 for the results
and the techniques used in this paper.

###  1.2 Our Contribution

We start by introducing $\mathsf{EFkX}$ notion which is indeed a relaxation of
$\mathsf{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 $\mathsf{EF2X}$ allocation for restricted additive valuations. The
algorithm consists of 3 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 $\mathsf{EFX}$ property. In such situations, we execute the envy-
elimination process. This process restores the $\mathsf{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 at most as much as her
value beforehand.

##### A new Potential 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 $\Phi$ which maps a pair $\sigma=(X,R)$ of a
partial allocation $X$ and a partition $R$ of agents to a vector
$\Phi(\sigma)$ of rational numbers and show that after each update,
$\Phi(\sigma)$ increases lexicographically. This indicates that the updating
process terminates after a finite number of updates. Note that for a given
configuration $\sigma=(X,R)$, function $\Phi(\sigma)$ relies on both $X$ and
$R$.

We later turn our attention beyond $\mathsf{EF2X}$ to see whether our new
tools can be used to obtain better guarantees for the $\mathsf{EFX}$ notion.
Our second result is Algorithm 3 that finds a partial $\mathsf{EFX}$
allocation which discards at most $\lfloor n/2\rfloor-1$ number of goods. The
currently best known result in this direction is the work of Chaudhury et al.
[24] which proves the existence of a partial $\mathsf{EFX}$ allocation that
discards at most $n-1$ goods. In comparison to them, our algorithm reduces the
number of discarded goods for the restricted additive setting by a factor of
2.

Finally, in Section 7, we explore the possibility of achieving more efficient
allocations satisfying $\mathsf{EFkX}$. We show that for any integer $k$ and
any constant $c$, there are instances for which guaranteeing a
$c$-approximation of $\mathsf{EFkX}$ and Pareto efficiency at the same time is
not possible.

##  2 Related Work

Fair allocation of indivisible goods is a central problem in several
disciplines including computer science and economics [15], and envy-freeness
is a classic fairness notion studied in this context. A formal study of envy-
freeness can be traced back to over 70 years ago [31, 44]. The notion we study
in this paper is $\mathsf{EFX}$ which is a relaxation of envy-freeness for the
case that the resource is a set of indivisible goods.

$\mathsf{EFX}$ is among the most studied fairness notions in recent years and
“Arguably, the best fairness analog of envy-freeness for indivisible items”
[20]. This notion originates in the work of Caragiannis et al. [20] wherein
the authors provide some initial results on $\mathsf{EFX}$ and its relation to
other notions. However, despite extensive investigations, the existence of a
complete $\mathsf{EFX}$ allocation is only proved for very limited cases: when
the number of agents is $2$ or $3$ [41, 22], and when the valuations are
either identical [41], binary [10], or bi-valued [2]. Given this
impenetrability of $\mathsf{EFX}$, a growing strand of research started
considering its relaxations. These relaxations can be classified into three
categories:

  * •

Approximately $\mathsf{EFX}$ allocations: a natural approach is to find
allocations that are approximately $\mathsf{EFX}$. The first result in this
direction is a $1/2$-$\mathsf{EFX}$ allocation proposed by Plaut and
Roughgarden [41]. The approximation is later improved to $0.618$ by Amanitidis
et al. [3].

  * •

Weakening the fairness requirement: recall that in an $\mathsf{EFX}$
allocation, any possible envy is removed by eliminating the least valuable
good. Recently, Farhadi et al. [29] suggest a relaxed version of
$\mathsf{EFX}$ called EFR in which instead of eliminating the least valuable
good to evaluate fairness, eliminates a good uniformly at random. They also
show that a $0.74$-EFR allocation always exists. Another example is envy-
freeness up to one less preferred good $(\textsf{EFL})$ introduced by Barman
et al. [8] which limits the value of the eliminated good. The $\mathsf{EFkX}$
notion we introduced in Section 1.2 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. [19] wherein the authors prove the existence of
a partial $\mathsf{EFX}$ allocation whose Nash welfare is at least half of the
optimal Nash welfare. Following this work, Chaudhury et al. [24] proved the
existence of a partial $\mathsf{EFX}$ allocation that leaves at most $n-1$
goods unallocated. Berger et al. [12] decreased the number of discarded goods
to $n-2$. Recently, Chaudhury et al. [23] presented a framework to obtain a
partial $(1-\epsilon)$-$\mathsf{EFX}$ allocation with sub-linear number of
unallocated goods for any $\epsilon\in(0,\frac{1}{2}]$. Our second result in
Section 6 falls within this category.

Finally, we note that there are other fairness and efficiency criteria for the
allocation of indivisible goods. The most prominent examples are maximin-share
[5, 7, 11, 13, 21, 25, 26, 27, 30, 32, 33, 37, 38, 42] and its variants such
as pairwise maximin-share [3] and group-wise maximin-share [3, 8], envy-
freeness up to one good [9, 39], Nash welfare [9, 20, 29, 1, 2, 10], and
competitive equilibrium from equal incomes [18]. We also refer the reader to
[16, 15] for an overview on fair division, classic fairness notions, and
related results.

##  3 Preliminaries

We denote the set of agents by $N=\\{1,2,\ldots,n\\}$ and the set of goods by
$M$. Each agent $i$ has a valuation function
$v_{i}:2^{M}\rightarrow\mathbb{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=\langle X_{1},X_{2},\ldots,X_{n}\rangle$, where $X_{i}$ is the bundle
allocated to agent $i$. Allocation $X$ is complete if $\bigcup_{i}X_{i}=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 $P_{X}$. When $X$ is clear from the context, we simply use $P$
instead of $P_{X}$. 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 $\mathsf{EFX}$ notion. Here we define
a more general form of $\mathsf{EFX}$, namely, envy-freeness up to any $k$
goods or $\mathsf{EFkX}$.

######  Definition 3.1.

An allocation $X=\langle X_{1},...,X_{n}\rangle$ is $\mathsf{EFkX}$, if for
all $i\neq j$ and every collection of $\ell=\min(k,|X_{j}|)$ distinct goods
$g_{1},g_{2},\ldots,g_{\ell}\in X_{j}$ we have $v_{i}(X_{i})\geq
v_{i}(X_{j}\setminus\\{g_{1},g_{2},\ldots,g_{\ell}\\}).$

Roughly speaking, an allocation is $\mathsf{EFkX}$ if for every agents $i,j$,
agent $i$ does not envy agent $j$ provided that $k$ arbitrary goods are
removed from the bundle of agent $j$. In particular, an $\mathsf{EFX}$
allocation is $\mathsf{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 $\\{v_{1},v_{2},\ldots,v_{n}\\}$ of valuation functions is restricted
additive, if for every $1\leq i\leq n$, $v_{i}$ is additive, and furthermore,
for every good $g\in M$, we have $v_{i}(g)\in\\{0,v(g)\\}$333For ease of
notation, we use $v_{i}(g)$ instead of $v_{i}(\\{g\\})$. where $v(g)>0$.

For brevity, for a set $S$ of goods we define $v(S)$ as $\sum_{g\in S}v(g)$.
One desirable property of restricted additive valuations is stated in
Observation 3.1.

######  Observation 3.1.

Let $X$ be a partial $\mathsf{EFX}$ allocation, let $g$ be an unallocated
good, and let $i$ and $j$ be two different agents. If there exists two
different goods $g_{1},g_{2}\in X_{j}\cup\\{g\\}$ such that
$v_{i}((X_{j}\cup\\{g\\})\setminus\\{g_{1},g_{2}\\})>v_{i}(X_{i})$, then
$v_{i}(g)\neq 0$.

Proof. Assume $v_{i}(g)=0$. Since $g_{1}\neq g_{2}$, we have $g\neq g_{1}$ or
$g\neq g_{2}$. Without loss of generality, assume $g\neq g_{1}$. We have

$\displaystyle v_{i}((X_{j}\cup\\{g\\})\setminus\\{g_{1},g_{2}\\})$
$\displaystyle=v_{i}(X_{j}\setminus\\{g_{1},g_{2}\\})$ $\displaystyle\leq
v_{i}(X_{j}\setminus\\{g_{1}\\})$ $\displaystyle\leq v_{i}(X_{i}),$ $X$ is
$\mathsf{EFX}$

which is a contradiction. Therefore, $v_{i}(g)\neq 0$. Since $v_{i}$ is
restricted additive, we have $v_{i}(g)=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_ 444A partition of a
set is a grouping of its elements into non-empty subsets, in such a way that
every element is included in exactly one subset. $R$ of the agents. For a
partition $R$, we denote the $i$’th group of $R$ by $R_{i}$. Also, we denote
by $|R|$ the number of groups in $R$.

For brevity, we use the term configuration to refer to a pair of an allocation
and a partition. Therefore, at each step during our algorithms we take a
configuration $(X,R)$ as input and return another configuration
$(X^{\prime},R^{\prime})$. Our algorithms are developed in such a way that the
configurations satisfy three structural properties. The first and the most
important property is Property 1 which requires that the allocation satisfies
the $\mathsf{EFX}$ criteria.

######  Property 1 (EFX).

A configuration $\sigma=(X,R)$ is $\mathsf{EFX}$, if allocation $X$ is
$\mathsf{EFX}$.

Note that Property 1 is independent of the partition. The second property we
consider for configurations is envy-compatibility which we bring in the
following. This property incorporates both the allocation and the
configuration.

######  Property 2 (Envy-compatibility).

A configuration $(X,R)$ is envy-compatible, if for all $1\leq\ell\leq|R|$ we
have

$\forall_{i\in R_{\ell},g\in X_{i}}\qquad v_{i}(X_{i}\setminus\\{g\\})\leq
v_{r_{\ell}}(X_{r_{\ell}}),$

where

$r_{\ell}=\arg\min_{j\in R_{\ell}}v_{j}(X_{j}).$ (1)

For an envy-compatible configuration $(X,R)$, for every $1\leq\ell\leq|R|$ we
define $r_{\ell}$ as in Equation (1) and call $r_{\ell}$ the representative of
group $R_{\ell}$. Furthermore, we suppose that the groups in $R$ are sorted
according to the utility of their representatives, i.e.,

$v_{r_{1}}(X_{r_{1}})\leq v_{r_{2}}(X_{r_{2}})\leq\ldots\leq
v_{r_{|R|}}(X_{r_{|R|}}).$

Note that for an allocation $X$, there might be several different partitions
$R$ such that configuration $(X,R)$ is envy-compatible. For example, one
trivial such partitions is to put each agent into a separate group. However,
our interest is in configurations that are more specific. In addition to
Properties 1 and 2 our desired configurations admit another important
property. Before we introduce this property, we must define champion and
champion-graph. These two concepts were first introduced by Chaudhury et al.
[22]. In this paper, we revise their definition to incorporate configurations.

######  Definition 3.3.

Let $(X,R)$ be a configuration satisfying Property 2 and let $i\in R_{\ell}$
be an agent. Then, for every subset $S$ such that
$v_{i}(S)>v_{r_{\ell}}(X_{r_{\ell}})$, we define $[{S}\mid{i}]$ to be a subset
of $S$ with minimum number of elements such that
$v_{i}\left([{S}\mid{i}]\right)>v_{r_{\ell}}(X_{r_{\ell}})$. In case of
multiple options for $[{S}\mid{i}]$, we pick one arbitrarily.

######  Observation 3.2.

Let $(X,R)$ be a configuration satisfying Property 2, $S$ be a subset of goods
and $i\in R_{\ell}$ be an agent such that
$v_{i}(S)>v_{r_{\ell}}(X_{r_{\ell}})$. Then, we have
$v_{i}([{S}\mid{i}])=v([{S}\mid{i}])$.

Proof. By minimality of $S$, for any good $g\in[{S}\mid{i}]$, we have
$v_{i}([{S}\mid{i}]\setminus\\{g\\})\leq v_{r_{\ell}}(X_{r_{\ell}})$. Since by
definition, we have $v_{i}([{S}\mid{i}])>v_{r_{\ell}}(X_{r_{\ell}})$, no good
in $[{S}\mid{i}]$ has value $0$ to agent $i$. ∎

We now define champion as following.

######  Definition 3.4 (Champion and champion-graph).

Given a configuration $\sigma=(X,R)$ satisfying Property 2. We say $i\in
R_{\ell}$ is a champion of $S$ if $v_{i}(S)>v_{r_{\ell}}(X_{r_{\ell}})$ and
for every agent $j\neq i$ with $j\in R_{k}$ and $g\in[{S}\mid{i}]$ we have
$v_{r_{k}}(X_{r_{k}})\geq v_{j}([{S}\mid{i}]\setminus\\{g\\}).$ We also define
the champion-graph of $\sigma$, denoted by $H_{\sigma}$ as follows: for every
agent $i$ there is a vertex in $H_{\sigma}$. Edges of $H_{\sigma}$ are of two
types:

  * •

Regular edges: for every pair of agent $i,j$ with $i\in R_{\ell}$, there is an
edge from $i$ to $j$, if $v_{i}(X_{j})>v_{r_{\ell}}(X_{r_{\ell}})$.

  * •

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 $X_{j}\cup\\{g\\}$.

The last property we consider for configurations is based on the champion-
graph. Note that Property 3 is only defined on the configurations that are
envy-compatible.

######  Property 3 (Admissibility).

A configuration $\sigma=(X,R)$ satisfying Property 2 is admissible, if the
following properties hold:

  * •

For all $1\leq\ell\leq|R|$ and every $i\in R_{\ell}$, there is a path from
$r_{\ell}$ to $i$ in $H_{\sigma}$ using only regular edges.

  * •

For every agents $i\in R_{\ell}$ and $j\in R_{k}$ such that $\ell<k$,
$v_{r_{\ell}}(X_{r_{\ell}})\geq v_{i}(X_{j})$. I.e., there is no regular edge
from $R_{\ell}$ to $R_{k}$.

  * •

For all $i\notin\\{r_{1},\ldots,r_{|R|}\\}$, we have $v_{i}(X_{i})=v(X_{i}).$

We conclude this section by proving Lemma 3.5.

######  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 $\mathsf{EFX}$.

Proof. Consider two agents $i$ and $j$ such that $i\in R_{\ell}$ and $j\in
R_{k}$ for $1\leq\ell\leq k\leq|R|$. For all $g\in X_{i}$ we have,

$\displaystyle v_{j}(X_{j})$ $\displaystyle\geq v_{r_{k}}(X_{r_{k}})$ $j\in
R_{k}$ $\displaystyle\geq v_{r_{\ell}}(X_{r_{\ell}})$ $k\geq\ell$
$\displaystyle\geq v_{i}(X_{i}\setminus\\{g\\})$ $i\in R_{\ell}$
$\displaystyle=v(X_{i}\setminus\\{g\\})$ $X$ is non-wasteful
$\displaystyle\geq v_{j}((X_{i}\setminus\\{g\\}).$

Therefore, $j$ does not strongly envy $i$. If $\ell=k$, with a similar
argument, $i$ does not strongly envy $j$ either.

Now assume $\ell<k$. We have

$\displaystyle v_{i}(X_{i})$ $\displaystyle\geq v_{r_{\ell}}(X_{r_{\ell}})$
$i\in R_{\ell}$ $\displaystyle\geq v_{i}(X_{j}).$ $(X,R)$ is admissible

Thus, $i$ does not strongly envy $j$. Hence, $X$ is $\mathsf{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^{\prime},R^{\prime})$ satisfying Properties 1, 2
and 3. To do so, the process first makes the given allocation non-wasteful by
simply retaking all the wasted goods. Then, the process chooses an agent with
the minimum valuation, i.e.,

$\arg\min v_{i}(X_{i}).$

This agent is selected as the representative of set $R_{1}$ (thus we call her
$r_{1}$). Next, as long as there exists an agent $j\in R_{1}$ and an agent
$i\in N\setminus R_{1}$ such that $v_{j}(X_{i})>v_{r_{1}}(X_{r_{1}})$, we
modify the bundle of agent $i$ to $[{X_{i}}\mid{j}]$ and add agent $i$ to
$R_{1}$. Note that, the goods in $X_{i}\setminus[{X_{i}}\mid{j}]$ are returned
to the pool. When no more agent could be added to $R_{1}$, we repeat the same
process on the agents in $N\setminus R_{1}$ to construct $R_{2}$, $R_{3}$ and
so on. Finally, when all the agents are added to some partition $R_{i}$ we
terminate the process.

Algorithm 1 shows a pseudocode of the envy-elimination process. We denote the
allocation returned by this process by $X^{\prime}$ and denote the partition
by $R^{\prime}=\langle R_{1},R_{2},\ldots,R_{|R^{\prime}|}\rangle$. Note that,
by the way we construct $X^{\prime}$, 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^{\prime},R^{\prime})$
satisfies Properties 1, 2 and 3.

Algorithm 1 Envy-elimination

Input : instance $(N,M,(v_{1},\ldots,v_{n}))$, allocation $X$

Output: configuration $(X^{\prime},R^{\prime})$

1:while $\exists i\in N,g\in X_{i}$ s.t. $v_{i}(g)=0$ do

2: $X_{i}\leftarrow X_{i}\setminus\\{g\\}$

3:$\ell\leftarrow 1$

4:while $N\neq\emptyset$ do

5: $r_{\ell}\leftarrow\operatorname*{arg\,min}_{i\in N}v_{i}(X_{i})$

6: $X^{\prime}_{r_{\ell}}\leftarrow X_{r_{\ell}}$

7: $R_{\ell}\leftarrow\\{r_{\ell}\\}$

8: $N\leftarrow N\setminus\\{r_{\ell}\\}$

9: while $\exists j\in R_{\ell},i\in N$ s.t.
$v_{j}(X_{i})>v_{r_{\ell}}(X_{r_{\ell}})$ do

10: $X^{\prime}_{i}\leftarrow[{X_{i}}\mid{j}]$

11: $R_{\ell}\leftarrow R_{\ell}\cup\\{i\\}$

12: $N\setminus\\{i\\}$

13: $\ell\leftarrow\ell+1$

14:Return $(X^{\prime},\langle R_{1},R_{2},\ldots,R_{\ell-1}\rangle)$

######  Lemma 4.1.

Let $X$ be an allocation and let $\sigma=(X^{\prime},R^{\prime})$ be the
result of running the envy-elimination process on $X$. Then $\sigma$ satisfies
Properties 1, 2 and 3.

Proof. Let $\widetilde{X}$ be the result of removing wasted goods from
allocation $X$. Hence, $\widetilde{X}$ is non-wasteful. We prove each one of
the properties separately.

##### Property 2 (Envy-compatibility).

Note that when agent $i$ is added to $R_{\ell}$, there exists an agent $j$
such that $X^{\prime}_{i}=[{\widetilde{X}_{i}}\mid{j}]$. By Definition 3.3,

$\displaystyle v_{j}(X^{\prime}_{i})>v_{r_{\ell}}(X^{\prime}_{r_{\ell}})\geq
v_{j}(X^{\prime}_{i}\setminus\\{g\\}).$ (2)

Moreover,

$\displaystyle v_{j}(X^{\prime}_{i})$ $\displaystyle=v(X^{\prime}_{i})$
Observation 3.2 $\displaystyle=v_{i}(X^{\prime}_{i})$
$\displaystyle\hbox{$X^{\prime}_{i}\subseteq\widetilde{X}_{i}$ and
$\widetilde{X}$ is non-wasteful}.$

Thus by Equation (2) we have
$v_{i}(X^{\prime}_{i})>v_{r_{\ell}}(X^{\prime}_{r_{\ell}})\geq
v_{i}(X^{\prime}_{i}\setminus\\{g\\}).$ Since we have
$v_{r_{1}}(X^{\prime}_{r_{1}})\leq v_{r_{2}}(X^{\prime}_{r_{2}})\leq\ldots\leq
v_{r_{|R^{\prime}|}}(X^{\prime}_{r_{|R^{\prime}|}})$, $\sigma$ is envy-
compatible.

##### Property 3 (Admissibility).

First, we show that for all $1\leq\ell\leq|R^{\prime}|$ and all $i\in
R_{\ell}$, there is a path from $r_{\ell}$ to $i$ in $H_{\sigma}$ using only
regular edges. The proof is by induction on the order that agents are added to
$R_{\ell}$. For $i=r_{\ell}$, the property holds trivially. Now assume the
property holds just before agent $i$ is added to $R_{\ell}$ meaning that there
is a path from $r_{\ell}$ to $j$. We have

$\displaystyle v_{j}(X^{\prime}_{i})$
$\displaystyle=v_{j}([{\widetilde{X}_{i}}\mid{j}])$
$X^{\prime}_{i}=[{\widetilde{X}_{i}}\mid{j}]$
$\displaystyle>v_{r_{\ell}}(X^{\prime}_{r_{\ell}})$
$\displaystyle\hbox{Definition \ref{e-champion}}.$

Therefore, the regular edge $j\rightarrow i$ exists in $H_{\sigma}$ and there
is a path from $r_{\ell}$ to $i$.

We must also show that for every agents $i\in R_{\ell}$ and $j\in R_{k}$ such
that $\ell<k$, $v_{r_{\ell}}(X^{\prime}_{r_{\ell}})\geq
v_{i}(X^{\prime}_{j})$. Assume otherwise. Then there exist
$1\leq\ell<k\leq|R^{\prime}|$ and agents $i\in R_{\ell}$ and $j\in R_{k}$,
such that $v_{i}(X^{\prime}_{j})>v_{r_{\ell}}(X^{\prime}_{r_{\ell}})$. Thus,
before $R_{k}$ is created, $j$ must be added to $R_{\ell}$ which is a
contradiction. Also, since $\widetilde{X}$ is non-wasteful and for all agents
$i$, $X^{\prime}_{i}\subseteq\widetilde{X}_{i}$, $X^{\prime}$ is also non-
wasteful. In particular, for all $i\notin\\{r^{\prime}_{1},\ldots
r^{\prime}_{|R^{\prime}|}\\}$, $v_{i}(X^{\prime}_{i})=v(X^{\prime}_{i})$.
Hence, all properties in Definition 3 hold and $\sigma$ is admissible.

##### Property 1 ($\mathsf{EFX}$):

Currently, we know that after the envy-elimination process, the resulting
configuration $(X^{\prime},R^{\prime})$ satisfies Properties 2 and 3. Since
$X^{\prime}$ is non-wasteful, by Lemma 3.5 we conclude that $X^{\prime}$ is
also $\mathsf{EFX}$.

∎

##  5 An $\mathsf{EF2X}$ Allocation Algorithm

In this section, we present our algorithm for finding a complete
$\mathsf{EF2X}$ allocation. Our algorithm consists of four updating rules
$\mathsf{U}_{0}$, $\mathsf{U}_{1}$, $\mathsf{U}_{2}$, and $\mathsf{U}_{3}$. We
start with configuration $\sigma=(X,R)$, where $X$ is an empty allocation and
$R=\langle\\{1\\},\\{2\\},\ldots,\\{n\\}\rangle$. At each step, we take the
current configuration $\sigma=(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 $\Phi(\sigma)$, where

$\Phi(\sigma)=\bigg{[}v_{r_{1}}(X_{r_{1}}),v_{r_{2}}(X_{r_{2}}),\ldots,v_{r_{|R|}}(X_{r_{|R|}}),+\infty,\frac{1}{\sum_{i\notin\\{r_{1},r_{2},\ldots,r_{|R|}\\}}|X_{i}|},\sum_{i\in\\{r_{1},r_{2},\ldots,r_{|R|}\\}}|X_{i}|\bigg{]}.$

Therefore, after a finite number of updates we obtain a configuration to which
none of the updating rules is applicable. Afterwards, we show that the
remaining goods have a special property that allows us to allocate them to the
agents without violating the $\mathsf{EF2X}$ property. In other words, if for
an allocation $X$ during the algorithm none of the rules is applicable and
goods $g_{1},\ldots,g_{|P|}$ are not allocated, then we can find $|P|$
different agents $i_{1},i_{2},\ldots,i_{|P|}$ such that allocation
$X^{\prime}$ with

$\displaystyle X^{\prime}_{i_{\ell}}$
$\displaystyle=X_{i_{\ell}}\cup\\{g_{\ell}\\}$ for all $1\leq\ell\leq|P|$
$\displaystyle X^{\prime}_{j}$ $\displaystyle=X_{j}$ for all
$j\notin\\{i_{1},i_{2},\ldots,i_{|P|}\\}$

is $\mathsf{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 $\Phi$-improving. Finally, we describe how we
can allocate the remaining goods to maintain the $\mathsf{EF2X}$ property.

Throughout this section, we denote the configuration before and after each
update respectively by $\sigma=(X,R)$ and
$\sigma^{\prime}=(X^{\prime},R^{\prime})$. In what follows we describe the
updating rules and their properties.

Algorithm 2 Complete $\mathsf{EF2X}$ allocation

Input : instance $(N,M,(v_{1},\ldots,v_{n}))$

Output: allocation $X$

1:$X\leftarrow\langle\emptyset,\emptyset,\ldots,\emptyset\rangle$

2:$R\leftarrow\langle\\{1\\},\\{2\\},\ldots,\\{n\\}\rangle$

3:while $\mathsf{U}_{0}$ or $\mathsf{U}_{1}$ or $\mathsf{U}_{2}$ or
$\mathsf{U}_{3}$ is applicable do

4: Let $i$ be the minimum index s.t. $\mathsf{U}_{i}$ is applicable

5: Update $(X,R)$ via Rule $\mathsf{U}_{i}$

6:for $t\leftarrow|R|\text{ to }1$ do

7: while $\exists i\in R_{t}\cap N$ s.t. $v_{i}(P)>0$ do

8: Choose such $i$ with maximum distance from $R_{t}$

9: $g\leftarrow\operatorname*{arg\,max}_{h\in P}v_{i}(h)$

10: $X_{i}\leftarrow X_{i}\cup\\{g\\}$

11: $N\leftarrow N\setminus\\{i\\}$

12:Let $P_{X}=\\{g_{1},g_{2},\ldots,g_{|P_{X}|}\\}$

13:Let $i_{1},i_{2},\ldots,i_{|P_{X}|}$ be $|P_{X}|$ different agents in $N$

14:for $\ell\leftarrow 1\text{ to }|P_{X}|$ do

15: $X_{i_{\ell}}\leftarrow X_{i_{\ell}}\cup\\{g_{\ell}\\}$

16:Return $X$

#### Rule $\mathsf{U}_{0}$

We start with rule $\textsf{U}_{0}$ which is our most basic rule. This rule
allocates an unallocated good $g$ to a representative agent, such that the
resulting configuration satisfies Properties 1, 2 and 3. In the following, you
can find a schematic view of Rule $\mathsf{U}_{0}$.

Rule $\mathsf{U}_{0}$ Preconditions: • $\sigma=(X,R)$ satisfies Properties 1,
2 and 3. • There exists an unallocated good $g\in P$ and an index $\ell$ such
that $v_{r_{\ell}}(g)=0$ and for every $1\leq k\leq|R|$, $\forall_{i\in
R_{k}}\quad v_{i}(X_{r_{\ell}}\cup\\{g\\})\leq v_{r_{k}}(X_{r_{k}}).$ Process:
• Allocate $g$ to $r_{\ell}$. • Set $R^{\prime}=R$. Guarantees: •
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3. •
$\Phi(\sigma^{\prime}){\underset{\scriptscriptstyle\textsf{lex}}{\succ}}\Phi(\sigma)$.

######  Observation 5.1.

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of updating
$\sigma=(X,R)$ via Rule $\textsf{U}_{0}$. Then for every agent $i$ we have
$v_{i}(X^{\prime}_{i})=v_{i}(X_{i})$.

######  Lemma 5.1.

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of updating
$\sigma=(X,R)$ via Rule $\textsf{U}_{0}$. Then, $\sigma^{\prime}$ satisfies
Properties 1, 2 and 3.

Proof. We prove each one of the properties separately.

##### Property 1 ($\mathsf{EFX}$):

In order to prove that $X^{\prime}$ is $\mathsf{EFX}$, it suffices to prove
that no agent strongly envies $X^{\prime}_{r_{\ell}}$. For all $1\leq
k\leq|R|$ and $i\in R_{k}$,

$\displaystyle v_{i}(X^{\prime}_{i})$ $\displaystyle=v_{i}(X_{i})$ Observation
5.1 $\displaystyle\geq v_{r_{k}}(X_{r_{k}})$ $i\in R_{k}$ $\displaystyle\geq
v_{i}(X_{r_{\ell}}\cup\\{g\\}).$ Precondition of Rule $\mathsf{U}_{0}$

Thus, no agent envies $r_{\ell}$.

##### Property 2 (Envy-compatibility):

By Observation 5.1, for all $1\leq k\leq|R|$,

$r_{k}=\arg\min_{j\in R_{k}}v_{j}(X^{\prime}_{j}).$

Also, for all $1\leq k\leq|R|,i\in R_{k},i\neq r_{\ell}$ and $g\in X_{i}$ we
have

$\displaystyle v_{i}(X^{\prime}_{i}\setminus\\{g\\})$
$\displaystyle=v_{i}(X_{i}\setminus\\{g\\})$ $X^{\prime}_{i}=X_{i}$
$\displaystyle\leq v_{r_{k}}(X_{r_{k}})$ $\sigma$ is envy-compatible
$\displaystyle=v_{r_{k}}(X^{\prime}_{r_{k}})$ $\displaystyle\hbox{Observation
\ref{same-util}}.$

##### Property 3 (Admissibility):

Note that after the update, agent $r_{\ell}$ has received one additional good
and all other bundles are untouched. Since
$v_{r_{\ell}}(X^{\prime}_{r_{\ell}})=v_{r_{\ell}}(X_{r_{\ell}})$, the only
difference between $H_{\sigma^{\prime}}$ and $H_{\sigma}$ is that $r_{\ell}$
might have additional incoming edges. Also, since $\sigma$ is admissible, for
all $1\leq\ell\leq|R|$ and all $i\in R_{\ell}$, there is a path from
$r_{\ell}$ to $i$ in $H_{\sigma}$ using only regular edges. Hence, for all
$1\leq\ell\leq|R|$ and all $i\in R_{\ell}$, there is a path from $r_{\ell}$ to
$i$ in $H_{\sigma^{\prime}}$ which uses only regular edges.

Now we prove that for every agents $i\in R_{k}$ and $j\in R_{k^{\prime}}$ such
that $k<k^{\prime}$, $v_{r_{k}}(X^{\prime}_{r_{k}})\geq
v_{i}(X^{\prime}_{j})$. If $j=r_{\ell}$, we have

$\displaystyle v_{r_{k}}(X^{\prime}_{r_{k}})$
$\displaystyle=v_{r_{k}}(X_{r_{k}})$ Observation 5.1 $\displaystyle\geq
v_{i}(X_{r_{\ell}}\cup\\{g\\})$ Precondition of Rule $\mathsf{U}_{0}$
$\displaystyle=v_{i}(X^{\prime}_{j}).$ $j=r_{\ell}$

Also, if $j\neq r_{\ell}$, we have

$\displaystyle v_{r_{k}}(X^{\prime}_{r_{k}})$
$\displaystyle=v_{r_{k}}(X_{r_{k}})$ Observation 5.1 $\displaystyle\geq
v_{i}(X_{j})$ $\sigma$ is admissible $\displaystyle=v_{i}(X^{\prime}_{j}).$
$X^{\prime}_{j}=X_{j}$

Therefore, for every agents $i\in R_{k}$ and $j\in R_{k^{\prime}}$ such that
$k<k^{\prime}$, $v_{r_{k}}(X^{\prime}_{r_{k}})\geq v_{i}(X^{\prime}_{j})$.
Also, for all $i\notin\\{r_{1},\ldots,r_{|R|}\\}$, $X^{\prime}_{i}=X_{i}$. By
admissibility of $X$, $v_{i}(X_{i})=v(X_{i})$ and hence,
$v_{i}(X^{\prime}_{i})=v(X^{\prime}_{i})$. Thus, Property 3 holds. ∎

######  Lemma 5.2.

Rule $\textsf{U}_{0}$ is $\Phi$-improving.

Proof. Let $\\{r_{1},r_{2},\ldots,r_{|R|}\\}$ be the set of representatives
before the update. We have

$\displaystyle\Phi(\sigma^{\prime})$
$\displaystyle=\bigg{[}v_{r_{1}}(X^{\prime}_{r_{1}}),\ldots,v_{r_{|R|}}(X^{\prime}_{r_{|R|}}),+\infty,\frac{1}{\sum_{i\notin
A}|X^{\prime}_{i}|},\sum_{i\in A}|X^{\prime}_{i}|\bigg{]}$
$\displaystyle=\bigg{[}v_{r_{1}}(X_{r_{1}}),\ldots,v_{r_{|R|}}(X_{r_{|R|}}),+\infty,\frac{1}{\sum_{i\notin
A}|X^{\prime}_{i}|},\sum_{i\in A}|X^{\prime}_{i}|\bigg{]}$ Observation 5.1
Since for all $i\neq r_{\ell}$ we have $X^{\prime}_{i}=X_{i}$ and
$X^{\prime}_{r_{\ell}}=X_{r_{\ell}}\cup\\{g\\}$, we have
$\displaystyle\Phi(\sigma^{\prime})$
$\displaystyle=\bigg{[}v_{r_{1}}(X_{r_{1}}),\ldots,v_{r_{|R|}}(X_{r_{|R|}}),+\infty,\frac{1}{\sum_{i\notin
A}|X_{i}|},\sum_{i\in A}|X_{i}|+1\bigg{]}$
$\displaystyle\underset{\scriptscriptstyle\textsf{lex}}{\succ}\bigg{[}v_{r_{1}}(X_{r_{1}}),\ldots,v_{r_{|R|}}(X_{r_{|R|}}),+\infty,\frac{1}{\sum_{i\notin
A}|X_{i}|},\sum_{i\in A}|X_{i}|\bigg{]}$ $\displaystyle=\Phi(\sigma).$

∎

#### Rule $\mathsf{U}_{1}$

Our second updating rule updates the configuration using a special type of
cycle in the champion-graph called champion cycle.

######  Definition 5.3.

For a configuration $\sigma=(X,R)$, we call a cycle $C$ of $H_{\sigma}$ a
champion cycle, if for every champion edge $i\xrightarrow[]{g}j$ in $C$,
$j\in\\{r_{1},r_{2},\ldots,r_{|R|}\\}$. Additionally, for every two champion
edges of $C$ with labels $g$ and $g^{\prime}$, we have that $g\neq
g^{\prime}$.

In this rule, we first find a champion cycle in $H_{\sigma}$ and update the
allocation through this cycle. Next, we apply envy-elimination. In the
following, you can find a schematic view of Rule $\mathsf{U}_{1}$.

Rule $\mathsf{U}_{1}$ Preconditions: • $\sigma=(X,R)$ satisfies Properties 1,
2 and 3. • There exists a champion cycle $C$ in $H_{\sigma}$. Process: • For
every edge $i\rightarrow j\in C$, set $\widetilde{X}_{i}=X_{j}$. • For every
champion edge $i\xrightarrow[]{g}j\in C$, set
$\widetilde{X}_{i}=[{X_{j}\cup\\{g\\}}\mid{i}]$. • For every agent $j\notin
C$, set $\widetilde{X}_{j}=X_{j}$. • Apply envy-elimination on
$\widetilde{X}$. Guarantees: • $\sigma^{\prime}=(X^{\prime},R^{\prime})$
satisfies Properties 1, 2, and 3. •
$\Phi(\sigma^{\prime}){\underset{\scriptscriptstyle\textsf{lex}}{\succ}}\Phi(\sigma)$.

Since we apply envy-elimination in the last step of Rule $\mathsf{U}_{1}$,
Lemma 4.1 implies that the resulting configuration satisfies Properties 1, 2,
and 3.

######  Corollary 5.1 (of Lemma 4.1).

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of updating
$\sigma=(X,R)$ via Rule $\textsf{U}_{1}$. Then,
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3.

######  Lemma 5.4.

Rule $\textsf{U}_{1}$ is $\Phi$-improving.

Proof. We prove that the conditions of Lemma A.3 hold. Let $\ell$ be the
smallest index such that $r_{\ell}\in C$ and $\widetilde{X}$ be the allocation
just before applying envy-elimination. Then we have,

$\forall i\in R_{1}\cup\ldots\cup R_{\ell-1},\quad\widetilde{X}_{i}=X_{i}$.

Therefore, Condition 1 of Lemma A.3 holds.

Without loss of generality, we can assume for all $k>\ell$ such that
$r_{k}\notin C$,
$v_{r_{k}}(X_{r_{k}})>v_{r_{\ell}}(X_{r_{\ell}})$.666Otherwise, we can simply
reorder the groups in $R$ which their representative agents have value
$v_{r_{\ell}}(X_{r_{\ell}})$. Assume $i\in R_{k}$ and $k\geq\ell$. If $i\notin
C$, we have

$\displaystyle v_{i}(\widetilde{X}_{i})$ $\displaystyle=v_{i}(X_{i})$
$\widetilde{X}_{i}=X_{i}$ $\displaystyle\geq v_{r_{k}}(X_{r_{k}})$ $i\in
R_{k}$ $\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$

If $i\rightarrow j\in C$, we have

$\displaystyle v_{i}(\widetilde{X}_{i})$ $\displaystyle=v_{i}(X_{j})$
$\widetilde{X}_{i}=X_{j}$ $\displaystyle>v_{r_{k}}(X_{r_{k}})$ Regular edge
from $i$ to $j$ $\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$

If $i\xrightarrow[]{g}j\in C$, we have

$\displaystyle v_{i}(\widetilde{X}_{i})$
$\displaystyle=v_{i}([{X_{j}\cup\\{g\\}}\mid{i}])$
$\widetilde{X}_{i}=[{X_{j}\cup\\{g\\}}\mid{i}]$
$\displaystyle>v_{r_{k}}(X_{r_{k}})$ Definition 3.3
$\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$

Therefore, we have

$\displaystyle\forall i\in R_{\ell}\cup\ldots\cup R_{|R|},\quad
v_{i}(\widetilde{X}_{i})>v_{r_{\ell}}(X_{r_{\ell}}).$

Thus, Condition 2 of Lemma A.3 holds too and therefore,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.
∎

In Lemmas 5.5 and 5.6 we prove two properties of every admissible
configuration $\sigma$ on which neither of the Rules $\mathsf{U}_{0}$ or
$\mathsf{U}_{1}$ is applicable. We use these properties in Section 5.1 to
obtain a complete $\mathsf{EF2X}$ allocation.

######  Lemma 5.5.

For an admissible configuration $\sigma=(X,R)$, if neither of the Rules
$\textsf{U}_{0}$ and $\textsf{U}_{1}$ is applicable, then for every
$r_{\ell}\in\\{r_{1},r_{2},\ldots,r_{|R|}\\}$ and every unallocated good $g$
there exists an agent $j\notin R_{\ell}$ such that $j$ is a champion of
$X_{r_{\ell}}\cup\\{g\\}$.

Proof. Assume otherwise. If $v_{r_{\ell}}(g)=0$, then Rule $\mathsf{U}_{0}$ is
applicable which is a contradiction. Otherwise, $v_{r_{\ell}}(g)=v(g)$ and
$v_{r_{\ell}}(X_{r_{\ell}}\cup\\{g\\})>v_{r_{\ell}}(X_{r_{\ell}})$. If for an
agent $j\in R_{\ell}$, $j$ is a champion of $X_{r_{\ell}}\cup\\{g\\}$, then
$H_{\sigma}$ has a champion cycle and Rule $\mathsf{U}_{1}$ is applicable. If
for no other agent $j\neq r_{\ell}$, $j$ is a champion of
$X_{r_{\ell}}\cup\\{g\\}$, then $r_{\ell}$ is a champion of
$X_{r_{\ell}}\cup\\{g\\}$ and again Rule $\mathsf{U}_{1}$ is applicable.
Therefore, there always exists an agent $j\notin R_{\ell}$ such that the $j$
is a champion of $X_{r_{\ell}}\cup\\{g\\}$. ∎

######  Lemma 5.6.

For an admissible configuration $\sigma=(X,R)$, if neither of the Rules
$\textsf{U}_{0}$ and $\textsf{U}_{1}$ is applicable, then $|P_{X}|<|R|$.

Proof. Let $g_{1}$ be an arbitrary good in the pool and let $j_{1}\in
R_{t_{1}}$ be an arbitrary agent in $\\{r_{1},r_{2},\ldots,r_{|R|}\\}$. By
Lemma 5.5, there exists an agent $j^{\prime}_{1}\in R_{t_{2}}\neq R_{t_{1}}$
such that the edge $j^{\prime}_{1}\xrightarrow[]{g}j_{1}$ exists in
$H_{\sigma}$. Let $j_{2}$ be the agent in
$R_{t_{2}}\cap\\{r_{1},r_{2},\ldots,r_{|R|}\\}$. Let $g_{2}\neq g_{1}$ be
another good in the pool and let $j^{\prime}_{2}\in R_{t_{3}}$ for
$t_{3}\notin\\{t_{1},t_{2}\\}$ be the agent such that the edge
$j^{\prime}_{2}\xrightarrow[]{g_{2}}j_{2}$ exists in $H_{\sigma}$. We continue
repeating this process to obtain the sequence $j_{1},j_{2},\ldots,j_{|P|}$
such that for all $1\leq\ell\leq|P|$, $j^{\prime}_{\ell}\in R_{t_{\ell+1}}$.
Note that since Rule $\mathsf{U}_{1}$ is not applicable, there is no champion
cycle in $H_{\sigma}$ and hence for $\ell\neq\ell^{\prime}$, we have
$t_{\ell}\neq t_{\ell^{\prime}}$. Therefore, $R$ should partition agents into
at least $|P|+1$ different non-empty parts. Hence, $|P|<|R|$. ∎

#### Rule $\mathsf{U}_{2}$

In this updating rule, we check if there exists a representative agent such
that her value for at least one of the remaining goods is non-zero. If so, we
simply allocate it to that representative agent and apply envy-elimination. In
the following, you can find a schematic view of Rule $\mathsf{U}_{2}$.

Rule $\mathsf{U}_{2}$ Preconditions: • $\sigma=(X,R)$ satisfies Properties 1,
2 and 3. • There exists a representative agent $r_{\ell}$ and an unallocated
good $g$ such that $v_{r_{\ell}}(g)=v(g)$. • Rules $\mathsf{U}_{0}$ and
$\mathsf{U}_{1},$ are not applicable. Process: • Allocate $g$ to $r_{\ell}$. •
Apply envy-elimination. Guarantees: •
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3. •
$\Phi(\sigma^{\prime}){\underset{\scriptscriptstyle\textsf{lex}}{\succ}}\Phi(\sigma)$.

Since we apply envy-elimination in the last step of Rule $\mathsf{U}_{2}$,
Lemma 4.1 implies that the resulting configuration satisfies Properties 1, 2,
and 3.

######  Corollary 5.2 (of Lemma 4.1).

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of updating
$\sigma=(X,R)$ via Rule $\textsf{U}_{2}$. Then,
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3.

######  Lemma 5.7.

Rule $\textsf{U}_{2}$ is $\Phi$-improving.

Proof. We prove that the conditions of Lemma A.3 hold. We have,

$\forall i\in R_{1}\cup\ldots\cup R_{\ell-1},\quad\widetilde{X}_{i}=X_{i}$.

Therefore, Condition 1 of Lemma A.3 holds.

Without loss of generality, we can assume for all $k>\ell$,
$v_{r_{k}}(X_{r_{k}})>v_{r_{\ell}}(X_{r_{\ell}})$.777Otherwise, we can simply
reorder the groups in $R$ which their representative agents have value
$v_{r_{\ell}}(X_{r_{\ell}})$. For all $k>\ell$ and $i\in R_{k}$, we have

$\displaystyle v_{i}(\widetilde{X}_{i})$ $\displaystyle=v_{i}(X_{i})$
$\widetilde{X}_{i}=X_{i}$ $\displaystyle\geq v_{r_{k}}(X_{r_{k}})$ $i\in
R_{k}$ $\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$

For all $i\in R_{\ell}\setminus r_{\ell}$, we have

$\displaystyle v_{i}(\widetilde{X}_{i})$ $\displaystyle=v_{i}(X_{i})$
$\widetilde{X}_{i}=X_{i}$ $\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$ $i\in
R_{\ell}\setminus\\{r_{\ell}\\}$

Finally we have

$\displaystyle v_{r_{\ell}}(X^{\prime}_{r_{\ell}})$
$\displaystyle=v_{r_{\ell}}(X_{r_{\ell}})+v_{r_{\ell}}(g)$
$X^{\prime}_{r_{\ell}}=X_{r_{\ell}}\cup\\{g\\}$
$\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$ $v_{r_{\ell}}(g)=v(g)>0$

Therefore,

$\forall i\in R_{\ell}\cup\ldots\cup R_{|R|},\quad
v_{i}(\widetilde{X}_{i})>v_{r_{\ell}}(X_{r_{\ell}}).$

Thus, Condition 2 of Lemma A.3 holds too and hence,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.
∎

#### Rule $\mathsf{U}_{3}$

This updating rule is structurally different from Rules $\mathsf{U}_{0}$,
$\mathsf{U}_{1}$, and $\mathsf{U}_{2}$. Unlike the previous rules, in Rule
$\mathsf{U}_{3}$ the agent to whom we allocate a good is not a representative
in $\sigma$. Here we find an unallocated good $g$ and a non-representative
agent $i$ such that $v_{i}(g)=v(g)$ and allocating $g$ to agent $i$ violates
the $\mathsf{EF2X}$ property. Moreover, we require that if $i\in R_{\ell}$,
some agent $i^{\prime}\in R_{\ell^{\prime}}$ for $\ell^{\prime}\leq\ell$
envies $X_{i}\cup\\{g\\}$ even after removal of two goods. Basically,
$i^{\prime}\in R_{\ell^{\prime}}$ for $\ell^{\prime}\leq\ell$ is a reason for
the new allocation to not be $\mathsf{EF2X}$. Then, we allocate $g$ to $i$ and
perform envy-elimination on $X$. In the following, you can find a schematic
view of Rule $\mathsf{U}_{3}$.

Rule $\mathsf{U}_{3}$ Preconditions: • $\sigma=(X,R)$ satisfies Properties 1,
2 and 3. • Rules $\mathsf{U}_{0}$, $\mathsf{U}_{1}$, and $\mathsf{U}_{2}$ are
not applicable. • There exists $i\in R_{\ell}\setminus\\{r_{\ell}\\}$ with
distance $d$ from $r_{\ell}$ in $H_{\sigma}$ and another $i^{\prime}\in
R_{\ell^{\prime}}$ with distance $d^{\prime}$ from $r_{\ell^{\prime}}$ in
$H_{\sigma}$ such that
$(\ell,d)\underset{\scriptscriptstyle\textsf{lex}}{\succeq}(\ell^{\prime},d^{\prime})$
and there exists $g\in P$ such that $v_{i}(g)=v(g)$ and $i^{\prime}$ envies
$X_{i}\cup\\{g\\}$ even after removal of $2$ goods. Process: • Allocate $g$ to
$i$. • Apply envy-elimination on $X$. Guarantees: •
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3. •
$\Phi(\sigma^{\prime}){\underset{\scriptscriptstyle\textsf{lex}}{\succ}}\Phi(\sigma)$.

For the rest of this section, assume $(\ell^{\prime},d^{\prime})$ is
lexicographically smallest such that for some $i^{\prime}\in
R_{\ell^{\prime}}$ with distance $d^{\prime}$ from $r_{\ell^{\prime}}$,
$i^{\prime}$ envies $X_{i}\cup\\{g\\}$ even after removal of $2$ goods.

Since we apply envy-elimination in the last step of Rule $\mathsf{U}_{3}$,
Lemma 4.1 implies that the resulting configuration satisfies Properties 1, 2,
and 3.

######  Corollary 5.3 (of Lemma 4.1).

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of updating
$\sigma=(X,R)$ via Rule $\textsf{U}_{3}$. Then,
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3.

In order to prove that Rule $\mathsf{U}_{3}$ is $\Phi$-improving, first we
prove Lemma 5.8.

######  Lemma 5.8.

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of updating
$\sigma=(X,R)$ via Rule $\textsf{U}_{3}$. Then, for every $1\leq k\leq|R|$ and
every agent $j\in R_{k}$,

  * •

if $j\in R^{\prime}_{t}$, then
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})\leq v_{r_{k}}(X_{r_{k}})$,
and

  * •

if $j\notin\\{r_{1},r_{2},\ldots,r_{|R|}\\}$, then
$j\notin\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$.
In other words,
$\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}\subseteq\\{r_{1},r_{2},\ldots,r_{|R|}\\}$.

Proof. The proof is by induction on $(k,d)$ where $d$ is the distance of $j$
from $r_{k}$ for $j\in R_{k}$. We have $(k_{1},d_{1})<(k_{2},d_{2})$ if either
$k_{1}<k_{2}$ or $k_{1}=k_{2}$ and $d_{1}<d_{2}$.

Case 1 $j\neq i$:

If $j=r_{k}$, then either
$j\in\\{r^{\prime}_{1},\ldots,r^{\prime}_{|R^{\prime}|}\\}$ and
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})=v_{r_{k}}(X_{r_{k}})$ or,
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})<v_{r_{k}}(X^{\prime}_{r_{k}})\leq
v_{r_{k}}(X_{r_{k}})$.

Now assume $j\neq r_{k}$, and $j^{\prime}$ is the preceding node of $j$ in a
shortest path from $r_{k}$ to $j$ in $H_{\sigma}$. By induction assumption,
$j^{\prime}\in R^{\prime}_{t}$ for
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})\leq v_{r_{k}}(X_{r_{k}})$.
The bundle of $j$ is not changed before the envy-elimination. Also since $X$
is admissible and $j$ is not representative, $X_{j}$ has no wasted good.
Therefore, the bundle of $j$ is not changed even after the removal of wasted
goods in the envy-elimination process. We have
$v_{j}(X_{j})>v_{r_{k}}(X_{r_{k}})\geq
v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})$ and
$v_{j^{\prime}}(X_{j})=v(X_{j})$. Therefore, either $j$ is already added to
some $R^{\prime}_{t^{\prime}}$ for $t^{\prime}\leq t$ or $j$ gets added to
$R^{\prime}_{t}$.

Case 2 $j=i$:

There is an agent in $\\{R_{1}\cup\ldots\cup R_{\ell}\\}$ namely
$i^{\prime}\in R^{\prime}_{t^{\prime}}$ such that

$\displaystyle v_{i^{\prime}}(X^{\prime}_{i})$
$\displaystyle>v_{i^{\prime}}(X_{i^{\prime}})$ $i^{\prime}$ strongly envies
$X^{\prime}_{i}$ $\displaystyle\geq v_{i^{\prime}}(X^{\prime}_{i^{\prime}})$
$X^{\prime}_{i^{\prime}}\subseteq X_{i^{\prime}}$ $\displaystyle\geq
v_{r^{\prime}_{t^{\prime}}}(X_{r^{\prime}_{t^{\prime}}}).$ $i^{\prime}\in
R^{\prime}_{t^{\prime}}$

Now consider the moment $i^{\prime}$ is added to $R^{\prime}_{t^{\prime}}$. We
know,

$\displaystyle v_{i}(X_{i}\cup\\{g\\})$ $\displaystyle=v(X_{i}\cup\\{g\\})$
$X$ is admissible and $v_{i}(g)=v(g)$ $\displaystyle\geq
v_{i^{\prime}}(X_{i}\cup\\{g\\})$ $v_{i^{\prime}}(g)>0$ by Lemma 3.1
$\displaystyle>v_{i^{\prime}}(X_{i^{\prime}}).$

Therefore, $i$ could not be considered for being a representative before
$i^{\prime}$ is added to $R^{\prime}_{t^{\prime}}$. Thus, either $i$ is
already added to some $R^{\prime}_{t}$ for $t\leq t^{\prime}$ or $i$ gets
added to $R^{\prime}_{t^{\prime}}$ and $t=t^{\prime}$. Hence, we have

$\displaystyle v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})$
$\displaystyle\leq
v_{r^{\prime}_{t^{\prime}}}(X^{\prime}_{r^{\prime}_{t^{\prime}}})$ $t\leq
t^{\prime}$ $\displaystyle\leq v_{r_{\ell^{\prime}}}(X_{r_{\ell^{\prime}}})$
Induction hypothesis $\displaystyle\leq v_{r_{\ell}}(X_{r_{\ell}}).$
$\ell^{\prime}\leq\ell$

∎

######  Lemma 5.9.

Rule $\textsf{U}_{3}$ is $\Phi$-improving.

Proof. Let $A=\\{r_{1},r_{2},\ldots,r_{|R|}\\}$ and
$A^{\prime}=\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$.
By Lemma 5.8, $A^{\prime}\subseteq A$. Also note that for all the
representative agents $r^{\prime}_{k}$ in $\sigma^{\prime}$,
$X^{\prime}_{r^{\prime}_{k}}\geq X_{r^{\prime}_{k}}$. If $A^{\prime}\subsetneq
A$, by Lemma A.1,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.
Otherwise, $A^{\prime}=A$. Note that

$\displaystyle|X_{i}|>|X_{i}\cup\\{g\\}|-2\geq|X^{\prime}_{i}|,$

and for all agents $j\neq i$,

$\displaystyle|X_{j}|\geq|X^{\prime}_{j}|.$

Therefore,

$\displaystyle\sum_{j\notin A}|X_{j}|>\sum_{j\notin
A^{\prime}}|X^{\prime}_{j}|.$ (3)

Hence,

$\displaystyle\Phi(\sigma^{\prime})$
$\displaystyle=\bigg{[}v_{r^{\prime}_{1}}(X^{\prime}_{r^{\prime}_{1}}),v_{r^{\prime}_{2}}(X^{\prime}_{r^{\prime}_{2}}),\ldots,v_{r^{\prime}_{|R^{\prime}|}}(X^{\prime}_{r^{\prime}_{|R^{\prime}|}}),+\infty,\frac{1}{\sum_{j\notin
A^{\prime}}|X^{\prime}_{j}|},\sum_{j\in A^{\prime}}|X^{\prime}_{j}|\bigg{]}$
$\displaystyle=\bigg{[}v_{r_{1}}(X_{r_{1}}),v_{r_{2}}(X_{r_{2}}),\ldots,v_{r_{|R|}}(X_{r_{|R|}}),+\infty,\frac{1}{\sum_{j\notin
A^{\prime}}|X^{\prime}_{j}|},\sum_{j\in A^{\prime}}|X^{\prime}_{j}|\bigg{]}$
$\displaystyle\underset{\scriptscriptstyle\textsf{lex}}{\succeq}\bigg{[}v_{r_{1}}(X_{r_{1}}),v_{r_{2}}(X_{r_{2}}),\ldots,v_{r_{|R|}}(X_{r_{|R|}}),+\infty,\frac{1}{\sum_{j\notin
A}|X_{j}|},\sum_{j\in A}|X_{j}|\bigg{]}$ Inequality (3)
$\displaystyle=\Phi(\sigma).$

∎

###  5.1 Allocating the Remaining Goods

As we mentioned, our algorithm continues to update the allocation as long as
one of the rules is applicable. Note that, since there are finitely many
possible allocations and the potential function $\Phi$ increases after each
update, we eventually end up with a configuration $\sigma=(X,R)$ such that
none of the rules can be applied on $\sigma$. 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 consider the latter case; we show
how to allocate these goods so that the final allocation preserves the
$\mathsf{EF2X}$ property. We denote the configuration at this step by
$\sigma=(X,R)$ and the final complete allocation by $X^{\prime}$.

Generally, our strategy is to find $|P|$ different agents and allocate one
good to each one of them. Recall that by Lemma 5.6, we have $|N|>|P|$ and
therefore selecting $|P|$ different agents from $N$ is possible. The process
of allocating the remaining goods is illustrated in Algorithm 2. In this
algorithm, we start by $\ell=|R|$ and as long as there is an agent $i\in
R_{\ell}\cap N$ such that $v_{i}(P)>0$, we give $i$ with maximum distance from
$r_{\ell}$ her most desirable good from the pool888If there were multiple such
goods, we select an arbitrary one and remove $i$ from $N$. Then, we decrease
$\ell$ by one and repeat the same process. The process goes on until either no
good remains in the pool, or $\ell=0$. Let us call the set of agents that
receive one good in this process by $N_{1}$. Let us denote the set of
unallocated goods at this stage by $M_{2}$. In case that $\ell=0$ and the pool
is still not empty (i.e., $M_{2}\neq\emptyset$), we allocate each remaining
good to an arbitrary agent in $N\setminus N_{1}$ (one good to each agent). We
denote the agents that receive some good in $M_{2}$ by $N_{2}$.

Let $X^{\prime}$ be the allocation after this step. By definition, we know
that $X^{\prime}$ is complete. In the rest of this section, we prove Theorem
5.10 which shows that $X^{\prime}$ is also $\mathsf{EF2X}$.

######  Theorem 5.10.

Assuming that the valuation functions are restricted additive, Algorithm 2
returns a complete $\mathsf{EF2X}$ allocation.

Note that by Observation 5.1 and Corollaries 5.1, 5.2, and 5.3, at the time
when none of the updating rules is applicable, $X$ is $\mathsf{EFX}$. Now we
prove that after allocating the remaining goods by Algorithm 2, the resulting
allocation $X^{\prime}$ is $\mathsf{EF2X}$.

We start by a simple observation.

######  Observation 5.2.

For all $i\in N\setminus N_{1}$ and $g\in M_{2}$, we have $v_{i}(g)=0$.

Since the partial allocation before the last step was $\mathsf{EFX}$, and no
good is allocated to the agents in $N\setminus(N_{1}\cup N_{2})$ in the last
step, to show that the final allocation is $\mathsf{EF2X}$ it is enough to
prove that no agent envies any agent $j\in N_{1}\cup N_{2}$ after removal of
any two goods from the bundle of agent $j$.

As a contradiction suppose that for an agent $i$ and some agent $j\in
N_{1}\cup N_{2}$, there exists two goods $g_{1},g_{2}\in X^{\prime}_{j}$ such
that agent $i$ envies the bundle of agent $j$ after eliminating goods $g_{1}$
and $g_{2}$. Let $g$ be the last good which is allocated to agent $j$ (via
Algorithm 2). By Observation 3.1, we have $v_{i}(g)=v(g)$. Let $\ell$ and
$\ell^{\prime}$ be such that $i\in R_{\ell}$ and $j\in R_{\ell^{\prime}}$. Let
$d$ be the distance of $i$ from $r_{\ell}$ and $d^{\prime}$ be the distance of
$j$ from $r_{\ell^{\prime}}$ in $H_{\sigma}$. If $j\in N_{1}$ and $j$ is a
representative, then the preconditions of Rule $\mathsf{U}_{2}$ hold for
$\sigma$. If $j\in N_{1}$ and
$(\ell^{\prime},d^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succeq}(\ell,d)$,
then the preconditions of Rule $\mathsf{U}_{3}$ hold for $\sigma$. Therefore
in either of these cases, Rule $\mathsf{U}_{2}$ or Rule $\mathsf{U}_{3}$ is
applicable on $\sigma$ which is a contradiction. Thus, we have
$(\ell,d)\underset{\scriptscriptstyle\textsf{lex}}{\succ}(\ell^{\prime},d^{\prime})$
or $j\in N_{2}$. This means that in the last stage of the algorithm, some good
$g^{\prime}$ should be allocated to $i$ before $g$ is allocated to $j$ with
the property that

$\displaystyle v_{i}(g^{\prime})$ $\displaystyle\geq v_{i}(g).$ (4)

Without loss of generality, we can assume $g\neq g_{1}$. Thus, we have,

$\displaystyle v_{i}(X^{\prime}_{j}\setminus\\{g_{1},g_{2}\\})$
$\displaystyle=v_{i}((X_{j}\cup\\{g\\})\setminus\\{g_{1},g_{2}\\})$
$\displaystyle=v_{i}(X_{j}\setminus\\{g_{1}\\})+v_{i}(g)-v_{i}(g_{2})$
$\displaystyle\leq
v_{i}(X_{j}\setminus\\{g_{1}\\})+v_{i}(g^{\prime})-v_{i}(g_{2})$ Inequality
(4) $\displaystyle\leq v_{i}(X_{i})+v_{i}(g^{\prime})$ $X$ is $\mathsf{EFX}$
$\displaystyle=v_{i}(X^{\prime}_{i}),$

which contradicts our assumption that agent $i$ envies
$X^{\prime}_{j}\setminus\\{g_{1},g_{2}\\}$. This completes the proof.

##  6 An $\mathsf{EFX}$ Allocation with at most $\lfloor n/2\rfloor-1$
Discarded Goods

In this section we present an algorithm that leaves aside at most $\lfloor
n/2\rfloor-1$ many goods and finds an $\mathsf{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 the empty allocation $X$ and partition
$R=\langle\\{1\\},\\{2\\},\ldots,\\{n\\}\rangle$. Our algorithm consists of
four updating rules $\mathsf{U}_{0}$, $\mathsf{U}_{1}$, $\mathsf{U}_{2}$ and
$\mathsf{U}_{4}$. At each step, we take the current configuration as input and
update it using one of these updating rules. Rule $\mathsf{U}_{0}$,
$\mathsf{U}_{1}$, and $\mathsf{U}_{2}$ are already defined in Section 5.
Similar to these rules, Rule $\mathsf{U}_{4}$ is designed in a way that the
value of $\Phi(\sigma)$ increases after each update. When none of the rules
$\mathsf{U}_{0}$, $\mathsf{U}_{1}$, $\mathsf{U}_{2}$ or $\mathsf{U}_{4}$ is
applicable, the algorithm terminates.

Algorithm 3 $\mathsf{EFX}$ allocation with $\leq\lfloor n/2\rfloor-1$
discarded goods

Input : instance $(N,M,(v_{1},\ldots,v_{n}))$

Output: allocation $X$

1:$X\leftarrow\langle\emptyset,\emptyset,\ldots,\emptyset\rangle$

2:$R\leftarrow\langle\\{1\\},\\{2\\},\ldots,\\{n\\}\rangle$

3:while $\mathsf{U}_{0}$ or $\mathsf{U}_{1}$ or $\mathsf{U}_{2}$ or
$\mathsf{U}_{4}$ is applicable do

4: Let $i$ be the minimum index s.t. $\mathsf{U}_{i}$ is applicable

5: Update $(X,R)$ via Rule $\mathsf{U}_{i}$

6:Return $X$

In the rest of this section, we describe the new updating rule, namely
$\mathsf{U}_{4}$ and its properties. Next, based on the properties of these
rules we prove Theorem 6.3 which states that the final allocation is
$\mathsf{EFX}$ and discards less than $\lfloor n/2\rfloor$ goods.

#### Rule $\mathsf{U}_{4}$

In this rule, we consider the whole set of the goods in the pool to update the
input $\sigma=(X,R)$. This rule states that if the set of the goods in the
pool has a champion $i\in R_{\ell}$, we update the allocation as follows: we
find a path from $r_{\ell}$ to $i$ and update the allocation through this
path. Next, we allocate a subset of the goods in the pool to $i$ and return
all the goods that belonged to $r_{\ell}$ before the update to the pool. Then
we apply envy-elimination to obtain $\sigma^{\prime}=(X^{\prime},R^{\prime})$.
In the following, you can find a schematic view of Rule $\mathsf{U}_{4}$.

Rule $\mathsf{U}_{4}$ Preconditions: • $\sigma=(X,R)$ satisfies Properties 1,
2 and 3. • There exists an agent who envies $P_{X}$. Process: Let $i\in
R_{\ell}$ be a champion of $P$ and let $r_{\ell}=j_{1}\rightarrow
j_{2}\dots\rightarrow j_{p}=i$ be a path in $H_{\sigma}$. • For all $1\leq
t\leq p-1$, set $\widetilde{X}_{j_{t}}=X_{j_{t+1}}$. • Set
$\widetilde{X}_{i}=[{P}\mid{i}]$. • For all
$k\notin\\{j_{1},j_{2},\ldots,j_{p}\\}$, set $\widetilde{X}_{k}=X_{k}$. •
Apply envy-elimination on $\widetilde{X}$. Guarantees: •
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3. •
$\Phi(\sigma^{\prime}){\underset{\scriptscriptstyle\textsf{lex}}{\succ}}\Phi(\sigma)$.

Since we apply envy-elimination in the last step of Rule $\mathsf{U}_{4}$,
Lemma 4.1 implies that the resulting configuration satisfies Properties 1, 2,
and 3.

######  Corollary 6.1 (of Lemma 4.1).

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of updating
$\sigma=(X,R)$ via Rule $\textsf{U}_{4}$. Then,
$\sigma^{\prime}=(X^{\prime},R^{\prime})$ satisfies Properties 1, 2, and 3.

######  Lemma 6.1.

Rule $\textsf{U}_{4}$ is $\Phi$-improving.

Proof. We prove that the conditions of Lemma A.3 hold. We have

$\forall j\in R_{1}\cup\ldots\cup R_{\ell-1}$, $\widetilde{X}_{j}=X_{j}$.

Therefore, Condition 1 of Lemma A.3 holds.

Without loss of generality, we can assume for all $k>\ell$,
$v_{r_{k}}(X_{r_{k}})>v_{r_{\ell}}(X_{r_{\ell}})$.999Otherwise, we can simply
reorder the groups in $R$ which their representative agents have value
$v_{r_{\ell}}(X_{r_{\ell}})$. For $k>\ell$ and $j\in R_{k}$ we have

$\displaystyle v_{j}(\widetilde{X}_{j})$ $\displaystyle=v_{j}(X_{j})$
$\widetilde{X}_{j}=X_{j}$ $\displaystyle\geq v_{r_{k}}(X_{r_{k}})$ $j\in
R_{k}$ $\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$

Also if $j\in R_{\ell}\setminus\\{j_{1},j_{2},\ldots,j_{t-1}\\}$, we have

$\displaystyle v_{j}(\widetilde{X}_{j})$ $\displaystyle=v_{j}(X_{j})$
$\widetilde{X}_{j}=X_{j}$ $\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$ $j\in
R_{\ell}$

Now assume $j=j_{t}$ for some $1\leq t\leq p-1$. We have

$\displaystyle v_{j_{t}}(\widetilde{X}_{j_{t}})$
$\displaystyle=v_{j_{t}}(X_{j_{t+1}})$ $\widetilde{X}_{j}=X_{j_{t+1}}$
$\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$ Regular edge from $j_{t}$ to
$j_{t+1}$

Finally if $j=i$, we have

$\displaystyle v_{i}(\widetilde{X}_{i})$ $\displaystyle=v_{i}([{P}\mid{i}])$
$\widetilde{X}_{i}=[{P}\mid{i}]$ $\displaystyle>v_{r_{\ell}}(X_{r_{\ell}}).$
Definition 3.3

Therefore,

$\forall j\in R_{\ell}\cup\ldots\cup R_{|R|}$,
$v_{j}(\widetilde{X}_{j})>v_{r_{\ell}}(X_{r_{\ell}})$.

Thus, Condition 2 of Lemma A.3 holds too and hence,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.
∎

###  6.1 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 Lemma 5.1 and Corollaries 5.1, 5.2, and 6.1,
the allocation after each update is $\mathsf{EFX}$. Therefore, the final
allocation preserves the $\mathsf{EFX}$ property as well. Also, since by
Lemmas 5.2, 5.4, 5.7, and 6.1 the value of $\Phi(\sigma)$ increases after each
update, Algorithm 3 terminates after a finite number of updates. It remains to
prove that the number of remaining goods in the pool is less than $\lfloor
n/2\rfloor$ and no agent envies the pool. We prove this 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|<\lfloor n/2\rfloor$. Also, no agent envies $P$.

Proof. Since Rule $\textsf{U}_{3}$ is not applicable, for every agent $i\in
R_{\ell}$ we have $v_{i}(X_{i})\geq v_{r_{\ell}}(X_{r_{\ell}})\geq v_{i}(P)$.
Now, we show that $|P|<\lfloor n/2\rfloor$ also holds. Towards a
contradiction, assume that $|P|\geq\lfloor n/2\rfloor$. If $|R|\leq\lfloor
n/2\rfloor$, by Lemma 5.6 at least one of Rules $\mathsf{U}_{0}$ or
$\mathsf{U}_{1}$ is applicable which contradicts the termination of the
algorithm. Therefore, we have $|R|>\lfloor n/2\rfloor$. Let
$S\subseteq\\{1,2,\ldots,|R|\\}$ be the set with the following properties:

  * •

for all agents $i$ with $v_{i}(P)>0$, if $i\in R_{\ell}$ then $\ell\in S$, and

  * •

$|S|$ is minimum.

Note that $R_{i}\cap R_{j}=\emptyset$ for all different $i$ and $j$ and
$\cup_{\ell\in S}|R_{\ell}|\leq n$. Hence, by the Pigeonhole principle, if
$|R|>\lfloor n/2\rfloor$, there is an index $i\in S$ such that $|R_{i}|=1$,
that is, $R_{i}=\\{r_{i}\\}$. Since $|S|$ is minimum, we have
$v_{r_{i}}(P)>0$; otherwise we could remove $i$ from $S$ which contradicts the
minimality of $S$. But this means that $\mathsf{U}_{4}$ is applicable, which
contradicts the termination assumption. ∎

Finally, Lemma 6.2 together with the fact that the final allocation is
$\mathsf{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 $\mathsf{EFX}$, and

  * •

$v_{i}(X_{i})\geq v_{i}(P)$ for every agent $i$, and

  * •

$|P|<\lfloor n/2\rfloor$.

##  7 Optimality of $\mathsf{EFX}$ Allocations

In Section 6, we presented an algorithm that finds a partial $\mathsf{EFX}$
allocation. When it comes to efficiency, it is not difficult to see that at
the end of this algorithm only representative agents can own wasted goods and
all other agents have no wasted good in their bundle. A natural question that
arises is whether there exists $\mathsf{EFkX}$ allocations that are more
efficient. In this section, we address this question: can we find an
allocation that is Pareto efficient and satisfies $\mathsf{EFkX}$?

Our answer to this question is negative. We show that for some instances
guaranteeing both Pareto efficiency and $\mathsf{EFkX}$ is not possible.
Indeed, our result is stronger; we show that for any constant $c<1$ and any
integer $k$, there are instances in which guaranteeing Pareto efficiency and a
$c$-approximation of $\mathsf{EFkX}$ is not possible. We start by defining
$c$-$\mathsf{EFkX}$ allocations.

######  Definition 7.1.

An allocation $X=\langle X_{1},...,X_{n}\rangle$ is $c$-$\mathsf{EFkX}$, if
for all $i\neq j$ and every collection of $\ell=min(k,|X_{j}|)$ distinct goods
$g_{1},g_{2},\ldots,g_{\ell}\in X_{j}$ we have $v_{i}(X_{i})\geq
cv_{i}(X_{j}\setminus\\{g_{1},g_{2},\ldots,g_{\ell}\\}).$

Roughgarden and Plaut [41] gave an example in which no $\mathsf{EFX}$ and
Pareto efficient allocation exists. We generalize this example and for any
integer $k$ and any constant $c\leq 1$, we present an instance which admits no
$c$-$\mathsf{EFkX}$ and Pareto efficient allocation.

######  Example 1.

Let $N=\\{1,2\\}$ and
$M=\\{g,g_{1},\dots,g_{k},g^{\prime}_{1},\dots,g^{\prime}_{k}\\}$. Also let
$v_{1}(g)=v_{2}(g)=(\frac{1}{c}+1)^{k}$,
$v_{1}(g_{i})=v_{2}(g^{\prime}_{i})=(\frac{1}{c}+1)^{i-1}$ for all $i\in[k]$
and $v_{1}(g^{\prime}_{i})=v_{2}(g_{i})=0$ (see Table 1). In any Pareto
efficient allocation, $g_{i}$ must be allocated to agent $1$ and
$g^{\prime}_{i}$ must be allocated to agent $2$ for all $i\in[k]$. Without
loss of generality (by symmetry), assume agent $1$ receives $g$. We have,

$\displaystyle v_{2}(X_{1})$ $\displaystyle=v_{2}(g)$
$\displaystyle=v_{2}(X_{1}\backslash\\{g_{1},g_{2},\dots,g_{k}\\}\\})$
$\displaystyle=(\frac{1}{c}+1)^{k}.$ Also, $\displaystyle v_{2}(X_{2})$
$\displaystyle=1+(\frac{1}{c}+1)+\dots+(\frac{1}{c}+1)^{k-1}$
$\displaystyle=c((\frac{1}{c}+1)^{k}-1).$ Therefore, $\displaystyle
cv_{2}(X_{1}\backslash\\{g_{1},g_{2},\dots,g_{k}\\})$
$\displaystyle>v_{2}(X_{2}).$

Thus, the allocation is not $c$-$\mathsf{EFkX}$.

| $g$ | $g_{1}$ | $g_{2}$ | $\dots$ | $g_{k}$ | $g^{\prime}_{1}$ | $g^{\prime}_{2}$ | $\dots$ | $g^{\prime}_{k}$ |
---|---|---|---|---|---|---|---|---|---|---
$v_{1}$ | $(\frac{1}{c}+1)^{k}$ | $1$ | $\frac{1}{c}+1$ | $\dots$ | $(\frac{1}{c}+1)^{k-1}$ | $0$ | $0$ | $\dots$ | $0$ |
$v_{2}$ | $(\frac{1}{c}+1)^{k}$ | $0$ | $0$ | $\dots$ | $0$ | $1$ | $\frac{1}{c}+1$ | $\dots$ | $(\frac{1}{c}+1)^{k-1}$ |
Table 1: Counter example for $c$-$\mathsf{EFkX}$ and Pareto efficiency

In the last part of this section, we define $\mathsf{EFX^{+}}$ (which is in
fact the original definition of $\mathsf{EFX}$ introduced by Caragiannis et
al.[20]) which is a relaxation of $\mathsf{EFX}$ and present an algorithm that
guarantees $\mathsf{EFX^{+}}$ and Pareto efficiency at the same time when the
valuations are restricted additive.

######  Definition 7.2.

An allocation $X=\langle X_{1},...,X_{n}\rangle$ is $\mathsf{EFX^{+}}$ if for
all agents $i$ and $j$ and all goods $g\in X_{j}$ such that
$v_{i}(X_{j})>v_{i}(X_{j}\setminus\\{g\\})$, $v_{i}(X_{i})\geq
v_{i}(X_{j}\setminus\\{g\\})$.

Algorithm 4 shows a pseudocode of our algorithm for finding an
$\mathsf{EFX^{+}}$ and Pareto efficient allocation. The algorithm is quite
simple. We start with an empty allocation and allocate the goods in non-
increasing order of their values. For each good $g$, we allocate it to agent
$i$ such that $v_{i}(X_{i})$ is minimum and $v_{i}(g)=v(g)$. It is easy to see
that the algorithm runs in polynomial time. The sorting of $m$ goods can be
done in $\mathcal{O}(m\log m)$ and then for each good $g$ we need to find
$\operatorname*{arg\,min}_{j:v_{j}(g_{\ell})=v(g_{\ell})}(v_{j}(X_{j}))$ which
can be done in $\mathcal{O}(n)$. Thus in total the running time of Algorithm 4
is $\mathcal{O}(m\log m+mn)$.

In Definition 3.2, we have $v(g)>0$ for all goods $g$. Note that if for a good
$g$ we have that $v_{i}(g)=0$ for all agents $i$, we can assume any value for
$v(g)$ since it is irrelevant. In order to prevent some unnecessary case
distinctions, in this section we assume $v(g)=0$ for all goods $g$ such that
for all agents $i$, $v_{i}(g)=0$.

Algorithm 4 Complete $\mathsf{EFX^{+}}$ allocation

Input : instance $(N,M,(v_{1},\ldots,v_{n}))$

Output: allocation $X=\langle X_{1},...,X_{n}\rangle$

1:Let $X=\langle\emptyset,\emptyset,...,\emptyset\rangle$

2:Let $v(g_{1})\geq v(g_{2})\geq\ldots\geq v(g_{m})$

3:for $\ell\leftarrow 1$ to $m$ do

4: Let
$i=\operatorname*{arg\,min}_{j:v_{j}(g_{\ell})=v(g_{\ell})}(v_{j}(X_{j}))$

5: $X_{i}\leftarrow X_{i}\cup\\{g_{\ell}\\}$

######  Observation 7.1.

Let $X$ be the allocation returned by Algorithm 4. Then $X$ is non-wasteful
and therefore, Pareto efficient.

Finally, we show that the allocation returned by Algorithm 4 is
$\mathsf{EFX^{+}}$. The proof is by induction. We start with the empty
allocation which is $\mathsf{EFX^{+}}$. Let us assume allocation $X$ is
$\mathsf{EFX^{+}}$ before allocating $g_{\ell}$ to agent $i$ (induction
hypothesis). It suffices to prove for all agents $j$ and $h\in
X_{i}\cup\\{g_{\ell}\\}$ such that $v_{j}(h)=v(h)$,

$v_{j}(X_{j})\geq v_{j}((X_{i}\cup\\{g_{\ell}\\})\setminus\\{h\\}).$

If $v_{j}(g_{\ell})=0$, we have

$\displaystyle v_{j}(X_{j})$ $\displaystyle\geq v_{j}(X_{i}\setminus\\{h\\})$
induction hypothesis
$\displaystyle=v_{j}(X_{i}\cup\\{g_{\ell}\\}\setminus\\{h\\}).$
$v_{j}(g_{\ell})=0$

Otherwise, we have

$\displaystyle v_{j}(X_{j})$ $\displaystyle\geq v_{i}(X_{i})$ by the choice of
$i$ $\displaystyle=v(X_{i})$ Observation 7.1 $\displaystyle\geq
v(X_{i})+v(g_{\ell})-v(h)$ $h=g_{\ell^{\prime}}$ for $\ell^{\prime}\leq\ell$
$\displaystyle=v((X_{i}\cup\\{g_{\ell}\\})\setminus\\{h\\})$
$\displaystyle\geq v_{j}((X_{i}\cup\\{g_{\ell}\\})\setminus\\{h\\}).$

This concludes that the output of Algorithm 7.1 is both $\mathsf{EFX^{+}}$ and
Pareto efficient.

######  Theorem 7.3.

Assuming that the valuations are restricted additive, there exists a
polynomial-time algorithm that returns an $\mathsf{EFX^{+}}$ and Pareto
efficient allocation.

## References

  * [1] Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, and Ernest van Wijland.  Maximizing nash social welfare in 2-value instances.  2021\.
  * [2] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A Voudouris.  Maximum nash welfare and other stories about EFX.  TCS, 863:69–85, 2021.
  * [3] Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos.  Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.  TCS, 841:94–109, 2020.
  * [4] Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson.  Combinatorial algorithm for restricted max-min fair allocation.  TALG, 13(3), 2017.
  * [5] Arash Asadpour, Uriel Feige, and Amin Saberi.  Santa claus meets hypergraph matchings.  TALG, 8(3), 2012.
  * [6] Etienne Bamas, Paritosh Garg, and Lars Rohwedder.  The submodular santa claus problem in the restricted assignment case.  arXiv preprint arXiv:2011.06939, 2020.
  * [7] Nikhil Bansal and Maxim Sviridenko.  The santa claus problem.  In STOC, pages 31–40, 2006.
  * [8] Siddharth Barman, Arpita Biswas, Sanath Krishnamurthy, and Yadati Narahari.  Groupwise maximin fair allocation of indivisible goods.  In AAAI, 2018.
  * [9] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In EC, pages 557––574, 2018.
  * [10] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Greedy algorithms for maximizing nash social welfare.  In AAMAS, pages 7–13, 2018.
  * [11] MohammadHossein Bateni, Moses Charikar, and Venkatesan Guruswami.  Maxmin allocation via degree lower-bounded arborescences.  In STOC, pages 543–552, 2009.
  * [12] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat.  (almost full) efx exists for four agents (and beyond).  arXiv preprint arXiv:2102.10654, 2021.
  * [13] Ivona Bezáková and Varsha Dani.  Allocating indivisible goods.  ACM SIGecom, 5(3):11–18, 2005.
  * [14] Steven J Brams and Alan D Taylor.  An envy-free cake division protocol.  American Mathematical Monthly, 102(1):9–18, 1995.
  * [15] Steven J Brams and Alan D Taylor.  Fair Division: From cake-cutting to dispute resolution.  Cambridge University Press, 1996.
  * [16] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia.  Handbook of Computational Social Choice.  Cambridge University Press, 2016.
  * [17] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [18] Eric Budish, Gérard P. Cachon, Judd B. Kessler, and Abraham Othman.  Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation.  Operations Research, 65(2):314–336, 2017.
  * [19] Ioannis Caragiannis, Nick Gravin, and Xin Huang.  Envy-freeness up to any item with high nash welfare: The virtue of donating items.  In EC, pages 527–545, 2019.
  * [20] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  TEAC, 7(3):1–32, 2019.
  * [21] Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna.  On allocating goods to maximize fairness.  In IEEE, pages 107–116, 2009.
  * [22] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn.  Efx exists for three agents.  In EC, pages 1––19, 2020.
  * [23] Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra.  Improving EFX guarantees through rainbow cycle number.  In EC, pages 310––311, 2021.
  * [24] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa.  A little charity guarantees almost envy-freeness.  In SODA, pages 2658–2672, 2020.
  * [25] Siu-Wing Cheng and Yuchen Mao.  Integrality gap of the configuration lp for the restricted max-min fair allocation.  arXiv preprint arXiv:1807.04152, 2018.
  * [26] Siu-Wing Cheng and Yuchen Mao.  Restricted max-min allocation: Approximation and integrality gap.  arXiv preprint arXiv:1905.06084, 2019.
  * [27] Sami Davies, Thomas Rothvoss, and Yihao Zhang.  A tale of santa claus, hypergraphs and matroids.  In SODA, pages 2748–2757, 2020.
  * [28] Ulle Endriss.  Trends in Computational Social Choice.  Lulu.com, 2017.
  * [29] Alireza Farhadi, MohammadTaghi Hajiaghayi, Mohamad Latifian, Masoud Seddighin, and Hadi Yami.  Almost envy-freeness, envy-rank, and nash social welfare matchings.  pages 5355–5362, 2021.
  * [30] Uriel Feige.  On allocations that maximize fairness.  In SODA, pages 287––293, 2008.
  * [31] Duncan K Foley.  Resource allocation and the public sector.  YALE ECON ESSAYS, 7(1):45–98, 1967.
  * [32] Jugal Garg and Setareh Taki.  An improved approximation algorithm for maximin shares.  AIJ, 300:103547, 2021.
  * [33] Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami.  Fair allocation of indivisible goods: Improvements and generalizations.  In EC, pages 539–556, 2018.
  * [34] Penny E Haxell.  A condition for matchability in hypergraphs.  Graphs and Combinatorics, 11(3):245–248, 1995.
  * [35] Klaus Jansen and Lars Rohwedder.  On the Configuration-LP of the Restricted Assignment Problem, pages 2670–2678.  2017\.
  * [36] Klaus Jansen and Lars Rohwedder.  Compact LP relaxations for allocation problems.  In SOSA, pages 1–19, 2018.
  * [37] Subhash Khot and Ashok Kumar Ponnuswami.  Approximation algorithms for the max-min allocation problem.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 204–217, 2007.
  * [38] David Kurokawa, Ariel D. Procaccia, and Junxing Wang.  Fair enough: Guaranteeing approximate maximin shares.  JACM, 65(2), 2018.
  * [39] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In EC, pages 125––131, 2004.
  * [40] Trung Thanh Nguyen and Jörg Rothe.  Minimizing envy and maximizing average nash social welfare in the allocation of indivisible goods.  Discrete Applied Mathematics, 179:54–68, 2014.
  * [41] Benjamin Plaut and Tim Roughgarden.  Almost envy-freeness with general valuations.  SIDMA, 34(2):1039–1068, 2020.
  * [42] Lukáš Poláček and Ola Svensson.  Quasi-polynomial local search for restricted max-min fair allocation.  TALG, 12(2), 2015.
  * [43] Barna Saha and Aravind Srinivasan.  A new approximation technique for resource-allocation problems.  Random Structures & Algorithms, 52(4):680–715, 2018.
  * [44] Hugo Steinhaus.  The problem of fair division.  Econometrica, 16(1):101–104, 1948.
  * [45] Walter Stromquist.  How to cut a cake fairly.  The American Mathematical Monthly, 87(8):640–644, 1980.
  * [46] Ola Svensson.  Santa claus schedules jobs on unrelated machines.  SICOMP, 41(5):1318–1341, 2012.
  * [47] Gerhard J Woeginger.  A polynomial-time approximation scheme for maximizing the minimum machine completion time.  Operations Research Letters, 20(4):149–154, 1997.

##  Appendix A Useful Lemmas on Comparing Vectors Lexicographically

######  Lemma A.1.

Let $\sigma=(X,R)$ and $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be two envy-
compatible configurations and let $\\{r_{1},r_{2},\ldots,r_{|R|}\\}$ and
$\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$ be the
sets of their representative agents respectively. If
$\\{r^{\prime}_{1},\ldots,r^{\prime}_{|R^{\prime}|}\\}\subsetneq\\{r_{1},\ldots,r_{|R|}\\}$
and for all $i\in\\{r^{\prime}_{1},\ldots,r^{\prime}_{|R^{\prime}|}\\}$,
$v_{i}(X^{\prime}_{i})\geq v_{i}(X_{i})$,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

Proof. Note that $|R|>|R^{\prime}|$. If
$v_{r_{\ell}}(X_{r_{\ell}})=v_{r^{\prime}_{\ell}}(X^{\prime}_{r^{\prime}_{\ell}})$
for all $1\leq\ell\leq|R^{\prime}|$, then since
$v_{r_{|R^{\prime}|+1}}(X_{r_{|R^{\prime}|+1}})<+\infty$, we have
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

Otherwise, let $\ell$ be the smallest index such that

$\displaystyle v_{r_{\ell}}(X_{r_{\ell}})\neq
v_{r^{\prime}_{\ell}}(X^{\prime}_{r^{\prime}_{\ell}}).$

If
$v_{r^{\prime}_{\ell}}(X^{\prime}_{r^{\prime}_{\ell}})>v_{r_{\ell}}(X_{r_{\ell}})$,
then
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

Now assume otherwise. We have

$\displaystyle
v_{r_{\ell}}(X_{r_{\ell}})>v_{r^{\prime}_{\ell}}(X^{\prime}_{r^{\prime}_{\ell}}).$
(5)

For all $1\leq k\leq\ell$, we have

$\displaystyle v_{r^{\prime}_{k}}(X_{r^{\prime}_{k}})$ $\displaystyle\leq
v_{r^{\prime}_{k}}(X^{\prime}_{r^{\prime}_{k}})$ Condition of Lemma A.1
$\displaystyle\leq v_{r^{\prime}_{\ell}}(X^{\prime}_{r^{\prime}_{\ell}})$
$k\leq\ell$ $\displaystyle<v_{r_{\ell}}(X_{r_{\ell}})$
$\displaystyle\mbox{Inequality \eqref{ineq}}.$

Therefore, we have $r^{\prime}_{k}\in\\{r_{1},\ldots,r_{\ell-1}\\}$ for all
$1\leq k\leq\ell$ which is a contradiction since
$|\\{r_{1},\ldots,r_{\ell-1}\\}|=\ell-1$. ∎

######  Lemma A.2.

Let $\sigma=(X,R)$ and $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be two envy-
compatible configurations and let $\\{r_{1},r_{2},\ldots,r_{|R|}\\}$ and
$\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$ be the
sets of their representative agents respectively. Assume there exists
$1\leq\ell\leq|R|$ such that the following properties hold:

  1. 1.

for all $i\in R_{1}\cup\ldots\cup R_{\ell-1}$, if
$i\notin\\{r_{1},r_{2},\ldots,r_{|R|}\\}$ then
$i\notin\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$,
and

  2. 2.

for all $i\in R_{1}\cup\ldots\cup R_{\ell-1}$, if
$i\in\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$,
$v_{i}(X^{\prime}_{i})=v_{i}(X_{i})$, and

  3. 3.

for all $i\in R_{\ell}\cup\ldots\cup R_{k}$, if
$i\in\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$,
$v_{i}(X^{\prime}_{i})>v_{r_{\ell}}(X_{r_{\ell}})$.

Then,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

Proof. Let $k$ be the largest index such that
$v_{r^{\prime}_{k}}(X^{\prime}_{r^{\prime}_{k}})\leq
v_{r_{\ell}}(X_{r_{\ell}})$. Property $3$ implies that
$\\{r^{\prime}_{1},\ldots,r^{\prime}_{k}\\}\subseteq R_{1}\cup\ldots\cup
R_{\ell-1}$ and Property $1$ implies that
$\\{r^{\prime}_{1},\ldots,r^{\prime}_{k}\\}\subseteq\\{r_{1},\ldots,r_{\ell-1}\\}$.

  * •

Case 1:
$\\{r^{\prime}_{1},\ldots,r^{\prime}_{k}\\}\subsetneq\\{r_{1},\ldots,r_{\ell-1}\\}$

Note that $\ell-1>k$. If
$v_{r_{i}}(X_{r_{i}})=v_{r^{\prime}_{i}}(X^{\prime}_{r^{\prime}_{i}})$ for all
$1\leq i\leq k$ and $|R^{\prime}|>k$, we have

$\displaystyle v_{r^{\prime}_{k+1}}(X_{r^{\prime}_{k+1}})$
$\displaystyle>v_{r_{\ell}}(X_{r_{\ell}})$ choice of $k$ $\displaystyle\geq
v_{r_{k+1}}(X_{r_{k+1}}).$ $\ell>k+1$

Thus,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.
Also if $|R^{\prime}|=k$, since $+\infty>v_{r_{k+1}}(X_{r_{k+1}})$,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

Now let $i\leq k$ be the smallest index such that

$\displaystyle v_{r_{i}}(X_{r_{i}})\neq
v_{r^{\prime}_{i}}(X^{\prime}_{r^{\prime}_{i}}).$

If $v_{r^{\prime}_{i}}(X^{\prime}_{r^{\prime}_{i}})>v_{r_{i}}(X_{r_{i}})$,
then

$(v_{r^{\prime}_{1}}(X^{\prime}_{r^{\prime}_{1}}),\ldots,v_{r^{\prime}_{k}}(X^{\prime}_{r_{k}}))\underset{\scriptscriptstyle\textsf{lex}}{\succ}(v_{r_{1}}(X_{r_{1}}),\ldots,v_{r_{\ell-1}}(X_{r_{\ell-1}})),$

and hence
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

So assume we have

$\displaystyle
v_{r_{i}}(X_{r_{i}})>v_{r^{\prime}_{i}}(X^{\prime}_{r^{\prime}_{i}}).$ (6)

For all $1\leq j\leq i$, we have

$\displaystyle v_{r^{\prime}_{j}}(X_{r^{\prime}_{j}})$
$\displaystyle=v_{r^{\prime}_{j}}(X^{\prime}_{r^{\prime}_{j}})$ Condition of
Lemma A.2 $\displaystyle\leq v_{r^{\prime}_{i}}(X^{\prime}_{r^{\prime}_{i}})$
$j\leq i$ $\displaystyle<v_{r_{i}}(X_{r_{i}})$ $\displaystyle\mbox{Inequality
\eqref{ineq-prim}}.$

Therefore, we have $r^{\prime}_{j}\in\\{r_{1},\ldots,r_{i-1}\\}$ for all
$1\leq j\leq i$ which is a contradiction since
$|\\{r_{1},\ldots,r_{i-1}\\}|=i-1$.

  * •

Case 2:
$\\{r^{\prime}_{1},\ldots,r^{\prime}_{k}\\}=\\{r_{1},\ldots,r_{\ell-1}\\}$

Note that by Property 2, for all
$i\in\\{r^{\prime}_{1},\ldots,r^{\prime}_{k}\\}$,
$v_{i}(X^{\prime}_{i})=v_{i}(X_{i})$. If $|R^{\prime}|=k$, since
$+\infty>v_{r_{\ell}}(X_{r_{\ell}})$,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.
If $|R^{\prime}|>k$, by the choice of $k$ we have
$v_{r^{\prime}_{k+1}}(X^{\prime}_{r^{\prime}_{k+1}})>v_{r_{\ell}}(X_{r_{\ell}})$.
Thus,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

∎

######  Lemma A.3.

Let $\sigma=(X,R)$ be an admissible configuration. Assume we modify $X$ to
$\widetilde{X}$ such that there exists $1\leq\ell\leq|R|$ for which the
following properties hold:

  1. 1.

for all $i\in R_{1}\cup\ldots\cup R_{\ell-1}$, $\widetilde{X}_{i}=X_{i}$, and

  2. 2.

for all $i\in R_{\ell}\cup\ldots\cup R_{|R|}$,
$v_{i}(\widetilde{X}_{i})>v_{r_{\ell}}(X_{r_{\ell}})$.

Let $\sigma^{\prime}=(X^{\prime},R^{\prime})$ be the result of applying envy-
elimination on $\widetilde{X}$. Then
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.

Proof. We prove that the properties of Lemma A.2 hold. First we prove that

for all $i\in R_{1}\cup\ldots\cup R_{\ell-1}$, if
$i\notin\\{r_{1},r_{2},\ldots,r_{|R|}\\}$ then
$i\notin\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$.

We use the following claim.

######  Claim A.1.

For every $1\leq k<\ell$ and every agent $i\in R_{k}$,

  * •

if $i\in R^{\prime}_{t}$, then
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})\leq v_{r_{k}}(X_{r_{k}})$,
and

  * •

if $i\notin\\{r_{1},r_{2},\ldots,r_{|R|}\\}$, then
$i\notin\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$.

The proof of the claim is by induction on the distance of $i$ from $r_{k}$. If
$i=r_{k}$, then either
$i\in\\{r^{\prime}_{1},\ldots,r^{\prime}_{|R^{\prime}|}\\}$ and
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})=v_{r_{k}}(X_{r_{k}})$ or,
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})<v_{r_{k}}(X^{\prime}_{r_{k}})\leq
v_{r_{k}}(X_{r_{k}})$. Now assume $i\neq r_{k}$, and $j$ is the preceding node
of $i$ in a shortest path from $r_{k}$ to $i$ in $H_{\sigma}$. By induction
assumption, $j\in R^{\prime}_{t}$ for
$v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})\leq v_{r_{k}}(X_{r_{k}})$.
The bundle of $i$ is not changed before the envy-elimination. Also since $X$
is admissible and $i$ is not a representative, $X_{i}$ has no wasted good.
Therefore, the bundle of $i$ is not changed even after the removal of wasted
goods in the envy-elimination process. We have
$v_{i}(X_{i})>v_{r_{k}}(X_{r_{k}})\geq
v_{r^{\prime}_{t}}(X^{\prime}_{r^{\prime}_{t}})$. Therefore, either $i$ is
already added to some $R^{\prime}_{t^{\prime}}$ for $t^{\prime}\leq t$ or we
set $X^{\prime}_{i}:=[{X_{i}}\mid{j}]$ and $i$ gets added to $R^{\prime}_{t}$.
Thus, the claim holds.

For the second property, note that when running envy-elimination, the bundles
of the agents in
$\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$ do not
change except for the removal of wasted goods. Therefore,

for all $i\in R_{1}\cup\ldots\cup R_{\ell-1}$, if
$i\in\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}$,
$v_{i}(X^{\prime}_{i})=v_{i}(\widetilde{X}_{i})=v_{i}(X_{i})$.

We know that for all
$j\in\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}\cap(R_{\ell}\cup\ldots\cup
R_{k})$,

$\displaystyle v_{j}(\widetilde{X}_{j})>v_{r_{\ell}}(X_{r_{\ell}}).$ (7)

Hence, for all
$j\in\\{r^{\prime}_{1},r^{\prime}_{2},\ldots,r^{\prime}_{|R^{\prime}|}\\}\cap(R_{\ell}\cup\ldots\cup
R_{k})$,

$\displaystyle v_{j}(X^{\prime}_{j})$ $\displaystyle=v_{j}(\widetilde{X}_{j})$
$\displaystyle>v_{i_{\ell}}(X_{i_{\ell}}).$ Inequality (7)

Therefore, by Lemma A.2,
$\Phi(\sigma^{\prime})\underset{\scriptscriptstyle\textsf{lex}}{\succ}\Phi(\sigma)$.
∎