# Improving EFX Guarantees through Rainbow Cycle Number

Bhaskar Ray Chaudhury
<EMAIL_ADDRESS>MPI for Informatics, Saarland Informatics Campus,
Graduate School of Computer Science, Saarbrücken, Germany Jugal Garg
<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign. Supported by
NSF Grant CCF-1942321 (CAREER) Kurt Mehlhorn
<EMAIL_ADDRESS>MPI for Informatics, Saarland Informatics Campus,
Germany Ruta Mehta
<EMAIL_ADDRESS>University of Illinois at Urbana-Champaign. Supported by
NSF Grant CCF-1750436 (CAREER) Pranabendu Misra
<EMAIL_ADDRESS>MPI for Informatics, Saarland Informatics Campus,
Germany

###### Abstract

We study the problem of fairly allocating a set of indivisible goods among $n$
agents with additive valuations. Envy-freeness up to _any_ good (EFX) is
arguably the most compelling fairness notion in this context. However, the
existence of EFX allocations has not been settled and is one of the most
important problems in fair division [36]. Towards resolving this problem, many
impressive results show the existence of its relaxations. In particular, [6]
shows the existence of $0.618$-EFX allocations, and [19] shows that EFX
allocation exists if we do not allocate at most $n-1$ goods. The latter result
was recently improved for three agents in [18], in which the two unallocated
goods are allocated through an involved procedure. Reducing the number of
unallocated goods for an arbitrary number of agents is a systematic way to
settle the big question.

In this paper, we develop a new approach, and show that for every
$\varepsilon\in(0,1/2]$, there always exists a $(1-\varepsilon)$-EFX
allocation with _sublinear_ number of unallocated goods and high Nash welfare.
For this, we reduce the EFX problem to a novel problem in extremal graph
theory. We introduce the notion of _rainbow cycle number_
${\mathit{R}}(\cdot)$. For all $d\in\mathbb{N}$, ${\mathit{R}}(d)$ is the
largest $k$ such that there exists a $k$-partite graph
$G=(\cup_{i\in[k]}V_{i},E)$, in which

  * •

each part has at most $d$ vertices, i.e., $|V_{i}|\leq d$ for all $i\in[k]$,

  * •

for any two parts $V_{i}$ and $V_{j}$, each vertex in $V_{i}$ has an incoming
edge from some vertex in $V_{j}$ and vice-versa, and

  * •

there exists no cycle in $G$ that contains at most one vertex from each part.

We show that any upper bound on ${\mathit{R}}(d)$ directly translates to a
sublinear bound on the number of unallocated goods. We establish a polynomial
upper bound on ${\mathit{R}}(d)$, yielding our main result. Furthermore, our
approach is constructive, which also gives a polynomial-time algorithm for
finding such an allocation.

##  1 Introduction

Fair division of resources is a fundamental problem in many disciplines,
including computer science, economics, and social choice theory. The objective
is to distribute resources among agents in a _fair_ (no agent is significantly
unhappy with her allocation) and _efficient_ (there is no other _fair
allocation_ that can achieve better total welfare) manner. Mentions of such
problems date back to the Bible and ancient Greek mythology. Today the issue
of fair division arises in division of labor, inheritance, or computing
resources, divorce settlements, partnership dissolutions, splitting rent among
tenants, splitting taxi fare among passengers, dividing household tasks, air
traffic management, frequency allocation, and so on. In the internet age, the
existence of several centralized platforms and more computational power has
triggered substantial interest from the economics and computer science
community to find computationally tractable protocols to allocate resources
fairly; see Spliddit [1] and Fair Outcomes [2] for more details on fair
division protocols used in real-life scenarios.

#### Discrete Fair Division.

In this paper, we focus on one of the most important open problems in discrete
fair division. To this end, we first describe a typical setup of a problem
instance: Given a set $N$ of $n$ agents and a set $M$ of $m$ _indivisible_
goods, the goal is to determine a partition $X=\langle
X_{1},X_{2},\dots,X_{n}\rangle$ of the good set $M$ such that agent $i\in N$
receives the bundle $X_{i}$ and the allocation is _fair_. Depending on the
notion of fairness, there are plethora of problems in this setting.

#### EFX Allocations.

A quintessential notion of fairness is that of envy-freeness (EF): an
allocation $X$ is said to be envy-free if and only if for every pair of agents
$i$ and $j$ we have $v_{i}(X_{i})\geq v_{i}(X_{j})$, i.e., each agent $i$,
values her own bundle at least as much as she values the bundles of other
agents. However, such allocations may not always exist: consider a simple
example with two agents having a positive valuation towards a single good. The
agent that gets this good is envied by the one that does not. Therefore,
several relaxations of envy-freeness have been proposed and studied over the
last fifteen years [31, 15, 17]. The most compelling relaxation is _envy-
freeness up to any good (EFX)_ , where no agent envies the other agent
following the removal of _any_ single good from the other’s bundle; that is,
an allocation $X$ is said to be EFX if and only if for every pair of agents
$i$ and $j$ we have $v_{i}(X_{i})\geq v_{i}(X_{j}\setminus\left\\{g\right\\})$
for all $g\in X_{j}$. It is also regarded as the best analogue of envy-
freeness in discrete fair division: Caragiannis et al. [16] remarked that,

> “Arguably, EFX is the best fairness analog of envy-freeness for indivisible
> items.”

Unfortunately, it is not known whether EFX allocations always exist, even when
there are only four agents with additive valuations despite significant
efforts by many researchers, e.g., see [17, 33]. Indeed, only recently was
this question resolved affirmatively for three agents with additive valuations
[18]111Recipient of the Exemplary Theory Paper Award and the Best Paper with a
Student Lead Author Award at ACM EC 2020. In fact, Procaccia [37] remarked
that,

> “This fundamental and deceptively accessible question is open. In my view,
> it is the successor of envy-free cake cutting as fair division’s biggest
> problem.”

There has been a substantial study on the existence of EFX allocation in
special cases and its relaxations. For instance, EFX allocations exist when
agents’ valuations are identical [35], binary [23, 11], and bi-valued [4]. The
two primary relaxations of EFX are approximate-EFX allocations and partial-EFX
allocations:

  * •

Approximate-EFX Allocation: An allocation $X=\langle
X_{1},X_{2},\dots,X_{n}\rangle$ is an $\alpha$-EFX allocation for some scalar
$\alpha\in(0,1]$, if for every pair of agents $i$ and $j$, we have
$v_{i}(X_{i})\geq\alpha\cdot v_{i}(X_{j}\setminus\left\\{g\right\\})$ for all
$g\in X_{j}$. Plaut and Roughgarden [35] showed the existence of
$\tfrac{1}{2}$-EFX allocations. A clever modification of the same approach
leads to a $0.618$-EFX allocation [6].

  * •

Partial-EFX Allocation: An allocation $X=\langle
X_{1},X_{2},\dots,X_{n}\rangle$ is called a partial-EFX allocation if $X$ is
EFX and not all goods are necessarily allocated, i.e.,
$\cup_{i\in[n]}X_{i}\subseteq M$. There is always a trivial partial EFX
allocation where each $X_{i}$ is empty. Therefore, a good partial EFX
allocation is the one which has good _qualitative_ and _quantitative_
guarantees on the unallocated goods. Caragiannis et al. [16] showed that there
exists a partial EFX allocation where every agent gets a bundle that she
values at least as much as half of her value for the bundle she receives in a
_Nash welfare_ maximizing allocation. Here, the Nash welfare of an allocation
$\mathit{NW}(X)=(\prod_{i\in[n]}v_{i}(X_{i}))^{\nicefrac{{1}}{{n}}}$ is
another popular measure of fairness and economic efficiency. Following the
same line of work, Chaudhury et al. [19] showed that there always exists a
partial EFX allocation $X$ and a set of unallocated goods $P$ such that

    * –

_nobody envies the set of unallocated items:_ $v_{i}(X_{i})\geq v_{i}(P)$ for
all $i\in N$, and

    * –

_at most $n-1$ goods are unallocated:_ $\lvert P\rvert\leq n-1$.

We remark that studying relaxations (of EFX allocations) is a systematic and
promising direction to investigate the existence of EFX allocations. It has
been suspected in Plaut and Roughgarden [35] that EFX allocations may not
exist in the general setting:

> “We suspect that at least for general valuations, there exist instances
> where no EFX allocation exists, and it may be easier to find a
> counterexample in that setting.”

However, finding counter-examples, at least in the additive setting, seems to
be a very challenging task; quite recently Manurangsi and Suksompong [32]
showed that when agents valuations for individual items are drawn at random
from a probability distribution, then EFX allocations exist with high
probability. This demands a non brute-force approach to find counter-examples,
if any. Thus finding better relaxations (improving the approximation factor or
reducing the number of unallocated goods in a partial EFX allocation) is a
crucial step to find the right answer to this big open question. We achieve
exactly this by our first main result,

######  Theorem 1.

For all $\varepsilon\in(0,1/2]$ we can determine a partial allocation $X$ and
a set of unallocated goods $P$ in polynomial time such that

  * •

$X$ is $(1-\varepsilon)$-EFX,

  * •

$|P|\leq 64(n/\varepsilon)^{4/5}$.

We remark that reducing the number of unallocated goods could be quite
challenging: Indeed, a corollary from the main result in [19] already
establishes that there exists a partial EFX allocation with at most two goods
unallocated when there are three agents and at most three goods when there are
four agents. However, removing the last two goods to obtain an EFX allocation
for three agents turns out to be highly non-trivial task and the proof in [18]
requires careful and cumbersome case analysis. Quite recently, Berger et al.
[12] overcome similar challenges and show the existence of EFX allocations
with at most $n-2$ unallocated goods, and the existence of EFX allocations
with at most one unallocated good when there are four agents.222Their proof
also works for a broader class of valuation functions called _nice cancellable
valuations_. A valuation $v$ is a nice cancellable valuation if (i) $v(A)\neq
v(B)$ for all $A\neq B$ and (ii) for all $A,B\subseteq M$ and $g\in
M\setminus(A\cup B)$, $v(A\cup\\{g\\})>v(B\cup\\{g\\})$ implies that
$v(A)>v(B)$. Their proof is also very involved and spans over 18 pages.
Furthermore, in Section 7 of this paper, we show that the techniques in [18,
12] does not extend to four agents with additive valuations for finding a
$(1-\varepsilon)$-EFX allocation.

_In this paper, we develop a novel method that reduces the problem of
determining good relaxations of EFX allocations to a combinatorial problem in
graph theory._ We call it the _rainbow cycle number_ of an integer, defined as
follows.

######  Definition 2.

For any positive integer $d$, the rainbow cycle number or ${\mathit{R}}(d)$ is
the largest $k$ such that there exists a directed $k$-partite graph
$G=(\cup_{i\in[k]}V_{i},E)$ such that

  1. 1.

$|V_{i}|\leq d$ for all $i\in[k]$,

  2. 2.

for any two distinct parts $V_{i}$ and $V_{j}$ in $G$, every vertex in $V_{i}$
has an incoming edge from a vertex in $V_{j}$, and

  3. 3.

there exists no cycle in $G$ that intersects each part at most once.

Let us deduce that ${\mathit{R}}(1)=1$: It is clear that $G$ can be a single
vertex and satisfy all the conditions in Definition 2 and thus
${\mathit{R}}(1)\geq 1$. However, ${\mathit{R}}(1)$ cannot be larger than one,
as otherwise we have two parts $V_{1}$ and $V_{2}$ in a graph $G$, where there
is exactly one vertex each in $V_{1}$ and $V_{2}$. So let
$V_{1}=\left\\{a_{1}\right\\}$ and $V_{2}=\left\\{a_{2}\right\\}$. By
condition 2 in Definition 2, we must have an edge from $a_{1}$ to $a_{2}$ and
an edge from $a_{2}$ to $a_{1}$. This gives a 2-cycle $a_{1}\rightarrow
a_{2}\rightarrow a_{1}$. However, this cycle contains exactly one vertex from
each $V_{1}$ and $V_{2}$, which contradicts condition 3 in Definition 2.

Similarly, using a more involved argument (appearing below) we can also
determine that $R(2)=2$. However, it is not at all clear what values $R(d)$
takes, or if it is finite for all integers $d$. A key technical result of this
paper is a polynomial (in $d$) upper-bound on ${\mathit{R}}(d)$.

######  Theorem 3.

For all $d\geq 1$, we have ${\mathit{R}}(d)\leq d^{4}+d$. Furthermore, let $G$
be a $k$-partite digraph with $k>d^{4}+d$ parts of cardinality at most $d$
each, such that for every vertex $v$ and any part $W$ not containing $v$,
there is an edge from $W$ to $v$. Then, there exists a cycle in $G$ visiting
each part at most once, and it can be found in time polynomial in $k$.

Observe that the definition of the rainbow cycle number
(${\mathit{R}}(\cdot)$) is independent of the agents, goods and valuation
functions. In the second key result of this paper, we establish a direct
relation between the rainbow cycle number and the existence of better EFX
relaxations: Finding a good upper bound on the rainbow cycle number can get us
weaker relaxations of EFX allocations (we can asymptotically improve the
number of unallocated goods). Formally,

######  Theorem 4.

Let $h(d)=d\cdot{\mathit{R}}(d)$ and $\varepsilon\in(0,1/2]$. Let
$h^{-1}(n/\varepsilon)$ be the smallest integer such that $h(d)\geq
n/\varepsilon$. Then, there is a $(1-\varepsilon)$-EFX allocation $X$ and a
set of unallocated goods $P$ such that $|P|\leq({4n}/{(\varepsilon\cdot
h^{-1}(2n/\varepsilon))}$.

Theorems 3 and 4 imply Theorem 1. We remark that, although we give a
polynomial upper bound on ${\mathit{R}}(d)$, we believe that there is further
room for improvement. As an illustration, we briefly show that
${\mathit{R}}(2)\leq 2$, which is significantly better than our upper-bound
for $d=2$ obtained from Theorem 4. We prove this by contradiction. Let us
assume otherwise and let $V_{1}$, $V_{2}$ and $V_{3}$ be any three parts of
$G$. We first look into the edges of the induced bipartite graph $G[V_{1}\cup
V_{2}]$. Without loss of generality, let us assume that vertex $b_{1}$ in
$V_{2}$ has an incoming edge from vertex $a_{1}$ in $V_{1}$. By condition 2 in
Definition 2, $a_{1}$ has an incoming edge from some vertex in $V_{2}$.
However, this vertex cannot be $b_{1}$ as this will violate condition 3 in
Definition 2. This implies that there must be another vertex in $V_{2}$, say
$b_{2}$ that has an edge to $a_{1}$. Again, by a similar argument, $b_{2}$
cannot have an incoming edge from $a_{1}$ and therefore has an incoming edge
from another vertex in $V_{1}$, say $a_{2}$ and $a_{2}$ has the incoming edge
from $b_{1}$ and not $b_{2}$ (since there can be no other vertices in
$V_{2}$). Thus, the induced bipartite graph $G[V_{1}\cup V_{2}]$ is a four-
cycle as shown below

$V_{1}$$V_{2}$$\scriptstyle{a_{1}}$$\scriptstyle{a_{2}}$$\scriptstyle{b_{1}}$$\scriptstyle{b_{2}}$

Note that the induced bipartite graph $G[V_{2}\cup V_{3}]$ will be isomorphic
to $G[V_{1}\cup V_{2}]$. Thus, so far we have the following edges in
$G[V_{1}\cup V_{2}\cup V_{3}]$,

$V_{1}$$V_{2}$$V_{3}$$\scriptstyle{a_{1}}$$\scriptstyle{a_{2}}$$\scriptstyle{b_{1}}$$\scriptstyle{b_{2}}$$\scriptstyle{c_{1}}$$\scriptstyle{c_{2}}$

We now look at the edges between the parts $V_{1}$ and $V_{3}$. Since
$G[V_{1}\cup V_{3}]$ is isomorphic to $G[V_{1}\cup V_{2}]$, it must also be a
four-cycle and hence in $G[V_{1}\cup V_{3}]$, there is either an edge from
$a_{1}$ to $c_{1}$ or from $c_{1}$ to $a_{1}$. If there is an edge from
$a_{1}$ to $c_{1}$, then we have a $3$-cycle $a_{1}\rightarrow
c_{1}\rightarrow b_{2}\rightarrow a_{1}$, which visits each part of $G$ at
most once and thus this is a contradiction. Similarly, if there is an edge
from $c_{1}$ to $a_{1}$, then also we have a $3$-cycle $a_{1}\rightarrow
b_{1}\rightarrow c_{1}\rightarrow a_{1}$, which visits each part of $G$ at
most once and thus this is also a contradiction.

We suspect that ${\mathit{R}}(d)\in\mathcal{O}(d)$. We believe that finding
better upper bounds on ${\mathit{R}}(d)$ is a natural combinatorial question
and better upper-bounds to ${\mathit{R}}(d)$ imply the existence of better
relaxations of EFX allocations. Therefore investigating better upper bounds on
the rainbow cycle number is of interest in its own right and we leave this as
an interesting open problem.

###  1.1 Finding $(1-\varepsilon)$-EFX allocations with high Nash welfare.

Let us recall that _efficiency_ is also an important and desirable property of
the allocations in Fair Division. The efficiency of an allocation is a measure
of the overall welfare the allocation achieves. This is important as an envy-
free allocation could be otherwise unsatisfactory: consider a simple instance
with two agents $1$ and $2$ and two goods $g_{1}$ and $g_{2}$. Let
$v_{1}(g_{1})=v_{2}(g_{2})=1$ and $v_{1}(g_{2})=v_{2}(g_{1})=0$. Note that
$X_{1}\leftarrow\\{g_{2}\\}$ and $X_{2}\leftarrow\\{g_{1}\\}$ is an EFX
allocation as each bundle is a singleton and following the removal of a single
good results in an empty bundle which is unenvied. However, there is clearly a
better EFX allocation, where the individual and the total welfare is better,
namely $X_{1}\leftarrow\\{g_{1}\\}$ and $X_{2}\leftarrow\\{g_{2}\\}$.

_Nash welfare_ of an allocation $X$, defined as the geometric mean of the
valuations of the agents,
$(\prod_{i\in[n]}v_{i}(X_{i}))^{\nicefrac{{1}}{{n}}}$ is a popular measure of
economic efficiency.333It implies other notions of efficiency like _Pareto-
optimality_. An allocation $X=\langle X_{1},\dots,X_{n}\rangle$ is Pareto-
optimal if there is no allocation $Y=\langle Y_{1},\dots,Y_{n}\rangle$ where
$v_{i}(Y_{i})\geq v_{i}(X_{i})$ for all $i\in[n]$ and
$v_{j}(Y_{j})>v_{j}(X_{j})$ for some $j$. In fact, when agents have additive
valuations, then the allocation with the highest Nash welfare is also EF1
(another popular fairness notion weaker than EFX). Unfortunately, maximizing
Nash welfare is APX-hard. However, there have been several approximation
algorithms [20, 7, 10] that give a constant factor approximation. The best
approximation ratio is $e^{1/e}\approx 1.445$, given by Barman et al. [10].

Similar to the algorithm in [19], we show that with minor modifications to our
main algorithm, we can determine an allocation that satisfies the conditions
in Theorem 1, and simultaneously achieves a $2e^{1/e}\approx 2.88$
approximation of the Nash welfare, i.e., in polynomial time we can find
efficient $(1-\varepsilon)$-EFX allocation with sublinear number of
unallocated goods.

######  Theorem 5.

For all $\varepsilon\in(0,1/2]$ we can determine a partial
$(1-\varepsilon)$-EFX allocation $X$ and a set of unallocated goods $P$ in
polynomial time such that $|P|\leq 64(n/\varepsilon)^{4/5}$ and
$\mathit{NW}(X)\geq(1/2.88)\cdot\mathit{NW}(X^{*})$, where $X^{*}$ is the
allocation with highest Nash welfare.

###  1.2 Further Related Work

Fair division has received significant attention since the seminal work of
Steinhaus [38] in the 1940s. Other than envy-freeness, another fundamental
fairness notion is that of _proportionality_. Recall that, in an envy-free
allocation, every agent values her own bundle at least as much as she values
the bundle of any other agent. However, in a proportional allocation, each
agent gets a bundle that is worth $1/n$ times her valuation on the entire set
of goods. Since envy-freeness and proportionality cannot always be guaranteed
while dividing indivisible goods, various relaxations of the same have been
studied. Alongside EFX, another popular relaxation of envy-freeness is _envy-
freeness up to one good (EF1)_ where no agent envies another agent following
the removal of _some_ good from the other agent’s bundle. While the existence
of EFX allocations is open, EF1 allocations are known to exist for any number
of agents, even when agents have weakly monotone valuation functions [31].
While EF1 and EFX are fairness notions that relax envy-freeness, the most
popular notion of fairness that relaxes proportionality for indivisible items
is _maximin share_ (MMS), which was introduced by Budish [15]. While MMS
allocations do not always exist [29], but there has been extensive work to
come up with approximate MMS allocations [15, 13, 5, 9, 29, 28, 26, 27]. Some
works assume ordinal ranking over the goods, as opposed to cardinal values,
e.g., [8, 14].

Alongside fairness, the efficiency of an allocation is also a desirable
property. Two common measures of efficiency is that of Pareto-optimality and
Nash welfare. Caragiannis et al. [17] showed that any allocation that has the
maximum Nash welfare is guaranteed to be Pareto-optimal (efficient) and EF1
(fair). Barman et al. [10] give a pseudopolynomial algorithm to find an
allocation that is both EF1 and Pareto-optimal. Other works explore
relaxations of EFX with high Nash welfare [16, 19].

The rest of the paper is organized as follows: In Section 2, we briefly
highlight our main techniques used to prove our main results (Theorem 1, 4 and
3). Then in Section 3, we outline the basic concepts, notations and techniques
from existing literature on EFX allocations that will be useful to prove our
main results. In Sections 4 and 5, we give the proofs of Theorem 4 and Theorem
3 respectively. In Section 6, we show how a minor modification of our main
algorithm helps us achieve our main result (Theorem 1) with high Nash welfare
(efficiency guarantees). Finally, in Section 7, we show why the technique from
[18] does not extend to a setting with four agents with additive valuations.

##  2 Our Techniques

In this section, we give a brief overview of our key ideas and techniques. We
first sketch the key idea that relates the number of unallocated goods to the
function the rainbow cycle number (Theorem 4) and then we briefly show that
${\mathit{R}}(d)$ is finite.

#### Relation between the number of unallocated goods to the rainbow cycle
number.

A very crucial concept that is often used while studying relaxations of envy-
freeness in discrete fair division is the _envy-graph of an allocation_. Given
an allocation $X=\langle X_{1},X_{2},\dots,X_{n}\rangle$, the envy-graph
$E_{X}$ has vertices corresponding to the agents and there is an edge from
agent $i$ to agent $j$ in $E_{X}$ if agent $i$ envies agent $j$
($v_{i}(X_{i})<v_{i}(X_{j})$). Without loss of generality, one assumes that
the envy-graph of an allocation is acyclic: If there is a cycle, then one can
shift the bundles along the cycle, thereby giving every agent in the cycle a
strictly better bundle and the other agents retain their previous bundle. Such
a procedure reduces the number of edges in the envy-graph, and one can
continue this until $E_{X}$ is cycle-free.

Most of the algorithms that have been used to prove the existence of
relaxations of EFX allocations [19, 18, 35] maintain a _relaxed EFX
allocation_ 444$(1-\varepsilon)$-EFX allocation in [19, 18] and $1/2$-EFX
allocation in [35]. $X$ on the set of allocated goods and as long as the envy-
graph $E_{X}$ and the set of unallocated goods satisfy some “properties”, they
determine another relaxed EFX allocation $X^{\prime}$, in which
$\phi(X^{\prime})\geq\phi(X)+\delta$ for some $\delta\geq 1$, where $\phi$ is
an integral upper-bounded function. In that case, we say that the relaxed EFX
allocation $X^{\prime}$ _dominates_ the relaxed EFX allocation $X$. Since
$\phi$ is integral and upper-bounded, such a procedure will finally converge
to a relaxed EFX allocation where the envy graph $E_{X}$ and the unallocated
goods will not satisfy the said properties and this will be the final
allocation of the algorithms.

We now highlight another crucial concept used in these algorithms. The envy-
graph $E_{X}$ does not provide any information on an agent’s valuations of the
bundles formed by adding unallocated goods to the current bundles of the
allocation. This information is crucial when we want to create another
dominating relaxed EFX allocation by allocating some of the unallocated goods
and unallocating some of the already allocated goods. The algorithms in [19,
18] make use of this information through other concepts. For instance [19, 18]
define _champions_ 555They are called “most envious agents” in [19] and
_champion graphs_. Given an allocation $X$ and an unallocated good $g$, we say
that an agent $i$ is a champion for agent $j$ w.r.t $g$ if there is a set
$S\subseteq X_{j}\cup\\{g\\}$ such that $v_{i}(X_{i})<(1-\varepsilon)\cdot
v_{i}(S)$ and no agent (including $i$ and $j$) envies $S$ up to a factor of
$(1-\varepsilon)$, following the removal of a single good, i.e, for all
$\ell\in[n]$, we have $(1-\varepsilon)\cdot v_{\ell}(S\setminus\\{h\\})\leq
v_{\ell}(X_{\ell})$ for all $h\in S$.666Since we are dealing with
$(1-\varepsilon)$-EFX allocations and not EFX allocations, we have changed the
definition of champions and champion graphs appropriately. [18, 19] also use
this definition in their algorithms as the polynomial time algorithms also
deal with $(1-\varepsilon)$-EFX allocations. A champion graph w.r.t an
unallocated good $g$ has vertices corresponding to the agents (similar to the
envy graph) and there is an edge from agent $i$ to agent $j$ if agent $i$
champions agent $j$ w.r.t. $g$. Depending on the configuration of the envy-
graph and the champion graphs (one for each unallocated good), the current
$(1-\varepsilon)$-EFX allocation $X$ is transformed into another
$(1-\varepsilon)$-EFX allocation $X^{\prime}$ such that $X^{\prime}$ dominates
$X$. However, when the number of agents are large, there are several different
possible configurations of the champion graphs and the envy-graph and it is
very hard and tedious to come up with better update rules. In this paper, we
introduce the notion of a _group champion graph_ which is significantly more
insightful and well structured than the champion graphs.

Given a $(1-\varepsilon)$-EFX allocation $X$ and a set of unallocated goods
$M^{\prime}$, we define the group champion graph. To this end, for each agent
$a\in[n]$, we assign a unique source $s(a)$ in $E_{X}$ such that $a$ is
reachable from $s(a)$ in $E_{X}$ (if there are multiple sources from which $a$
is reachable in $E_{X}$, then pick one source arbitrarily). The group champion
graph of $M^{\prime}$ is a $|M^{\prime}|$-partite graph $G=(\cup_{g\in
M^{\prime}}V_{g},E)$, in which each part $V_{g}$ contains a copy of the
assigned sources of all the agents that find $g$ “valuable”; an agent $a$
finds $g$ valuable if $v_{a}(\\{g\\})>\varepsilon\cdot v_{a}(X_{a})$. There is
an edge from vertex $s(a)$ in $V_{g}$ to $s(a^{\prime})$ in $V_{h}$ if and
only if $a$ champions $s(a^{\prime})$ w.r.t $g$ (see Figure 1 for an
illustration). At a high level, the group champion graph encodes the most
relevant information from all the champion graphs. We make this point more
explicit by briefly explaining how group champion graphs help us prove Theorem
4.

$V_{g_{a}}$$V_{g_{b}}$$\scriptstyle{a_{1}}$$\scriptstyle{a_{2}}$$\scriptstyle{a_{3}}$$\scriptstyle{a_{4}}$$\scriptstyle{b_{1}}$$\scriptstyle{b_{2}}$$\scriptstyle{a_{1}}$$\scriptstyle{a_{3}}$$\scriptstyle{b_{1}}$$a_{2}$
champions all agents w.r.t $g_{a}$.$b_{2}$ champions all agents w.r.t $g_{b}$.
Figure 1: Illustration of a group champion graph. We have an instance with six
agents $\cup_{i\in[4]}a_{i}$ and $\cup_{i\in[2]}b_{i}$ and two unallocated
goods, namely $g_{a}$ and $g_{b}$. The agents $\cup_{i\in[4]}a_{i}$ find
$g_{a}$ valuable and the agents $\cup_{i\in[2]}b_{i}$ find $g_{b}$ valuable.
The envy graph $E_{X}$ of the instance is shown on the left side. $E_{X}$
shows that $s(a_{2})=a_{1}$, $s(a_{4})=a_{3}$, and $s(b_{2})=b_{1}$. Also, we
have that agent $a_{2}$ champions all the agents w.r.t $g_{a}$ and $b_{2}$
champions all the agents w.r.t $g_{b}$. The group champion graph (right) has
two parts, $V_{g_{a}}$ corresponding to $g_{a}$ and $V_{g_{b}}$ corresponding
to $g_{b}$. $V_{g_{a}}$ contains the sources of all the agents that find
$g_{a}$ valuable, namely $a_{1}$ and $a_{3}$. Similarly, $V_{g_{b}}$ contains
$b_{1}$. There is an edge from $a_{1}$ to $b_{1}$ as $a_{2}$ (which is
reachable from $a_{1}$ in $E_{X}$) champions $b_{1}$ w.r.t to $g_{a}$.
Similarly, there is an edge from $b_{1}$ to $a_{3}$ as $b_{2}$ (which is
reachable from $b_{1}$ in $E_{X}$) champions $a_{3}$ w.r.t to $g_{b}$.

We first observe that if there is an unallocated good $g$ and an agent $i$
such that the other agents do not envy $(X_{i}\cup\\{g\\})\setminus
g^{\prime}$ up to a factor of $(1-\varepsilon)$ for all $g^{\prime}\in
X_{i}\cup\\{g\\}$, then we allocate $g$ to $i$. Thus, we assume that for each
unallocated good $g$ and each agent $i$, there is an agent $j$ that envies
$(X_{i}\cup\\{g\\})\setminus g^{\prime}$ up to a factor of $(1-\varepsilon)$
for some $g^{\prime}\in X_{i}\cup\\{g\\}$. In particular, this implies that
every unallocated good is valuable to some agent, because if there is a good
$g$ which is not valuable to any agent, i.e.,
$v_{i}(\\{g\\})\leq\varepsilon\cdot v_{i}(X_{i})$ for all $i\in[n]$, then we
can simply allocate $g$ to a source $s$ in $E_{X}$ as no agent will envy the
bundle $X_{s}\cup\\{g\\}$ up a factor of $(1-\varepsilon)$: for all $i\in[n]$,
we have that $v_{i}(X_{i})\geq v_{i}(X_{s})$ (as $s$ is unenvied) and
$\varepsilon\cdot v_{i}(X_{i})\geq v_{i}(\\{g\\})$, implying that
$(1+\varepsilon)v_{i}(X_{i})\geq v_{i}(X_{s}\cup\\{g\\})$, further implying
that $v_{i}(X_{i})\geq(1-\varepsilon)\cdot v_{i}(X_{s}\cup\\{g\\})$. Now we
classify the set of unallocated goods into two categories depending on how
many agents find them valuable: We fix an integer $d<n$ and define “high-
demand goods” and “low-demand goods”. A high-demand good is valuable to more
than $d$ agents and a low-demand good is valuable to at most $d$ agents. We
show in Section 4, that if the number of high-demand goods is more than
$2n/(\varepsilon\cdot d)$, then we can determine a dominating
$(1-\varepsilon)$-EFX allocation from the existing $(1-\varepsilon)$-EFX
allocation. Thus, we may assume that the number of high-demand goods is at
most $2n/(\varepsilon d)$. We now bound the number of low-demand goods. Let
$M^{\prime\prime}$ be the set of low-demand goods. We construct the group
champion graph $G=(\cup_{g\in M^{\prime\prime}}V_{g},E)$ of $M^{\prime\prime}$
in which part $V_{g}$ contains the assigned sources of the agents that find
$g$ valuable. Note that for all $g\in M^{\prime\prime}$, $g$ is not valuable
to more than $d$ agents. Thus $|V_{g}|\leq d$ for all $g\in M^{\prime\prime}$.
Now, consider any two parts $V_{g}$ and $V_{h}$ in $G$. By our assumption, for
all $a\in V_{h}$, there is an agent that envies $(X_{a}\cup\\{g\\})\setminus
g^{\prime}$ up to a factor of $(1-\varepsilon)$ for some good $g^{\prime}\in
X_{a}\cup\\{g\\}$, implying that for each $a$ in $V_{h}$, there are agents
that champion $a$ w.r.t $g$. Since $a$ is a source in $E_{X}$, it is intuitive
that the agents that champion $a$ w.r.t. $g$, must find $g$ valuable.
Therefore, for all $a\in V_{h}$, there is a source $s(a^{\prime})\in V_{g}$,
where $a^{\prime}$ champions $s(a)$ w.r.t $g$. Thus, every vertex in $V_{h}$
has an incoming edge from a vertex in $V_{g}$. _In Section 4, we show that
whenever $G$ has a cycle that visits each part at most once, then we can
determine a $(1-\varepsilon)$-EFX allocation that dominates $X$._ Therefore,
we can assume that $G$ has no cycle that visits each part at most once. Since
$G$ is a $|M^{\prime\prime}|$-partite graph that satisfies the conditions in
Definition 2, we have that the number of low-demand goods is
$|M^{\prime\prime}|\leq{\mathit{R}}(d)$. Therefore, the total number of
unallocated goods is $\mathcal{O}(\mathit{max}(2n/(\varepsilon\cdot
d),{\mathit{R}}(d)))$. By choosing the appropriate value for $d$, we arrive at
the statement of Theorem 4.

We now elaborate that ${\mathit{R}}(d)$ is indeed upper-bounded, which then
establishes the existence of $(1-\varepsilon)$-EFX allocations with sublinear
number of unallocated goods.

#### Upper bounds on the rainbow cycle number.

We briefly show that for any $d\in\mathbb{N}$, ${\mathit{R}}(d)$ is finite.
Consider a $k$-partite graph $G=(\cup_{i\in[k]}V_{i},E)$ in Definition 2. For
all $i\in[k]$, let $V_{i}=\\{(i,1),(i,2),\dots,(i,|V_{i}|)\\}$. For all $i<j$
and $i^{\prime}<j^{\prime}$, we say that the directed bipartite graphs
$G[V_{i}\cup V_{j}]$ and $G[V_{i^{\prime}}\cup V_{j^{\prime}}]$ have the same
configuration if and only if for each directed edge from vertex $(i,a)$ to
$(j,b)$ (and equivalently from $(j,b^{\prime})$ to $(i,a^{\prime})$) in
$G[V_{i}\cup V_{j}]$, there is an edge from $(i^{\prime},a)$ to
$(j^{\prime},b)$ (and equivalently from $(j^{\prime},b^{\prime})$ to
$(i^{\prime},a^{\prime})$) in $G[V_{i^{\prime}}\cup V_{j^{\prime}}]$ and vice-
versa. We first show that if there are $4d$ parts in $G$, say w.l.o.g.
$V_{1},V_{2},\dots,V_{4d}$, such that the induced directed bipartite graph
$G[V_{i}\cup V_{j}]$ has the same configuration for all $1\leq i<j\leq 4d$,
then there exists a cycle in $G$ that visits each part at most once.

Consider the parts $V_{1}$ and $V_{2}$, and the induced directed bipartite
graph $G[V_{1}\cup V_{2}]$. Since every vertex in one part has an incoming
edge from a vertex in the other part, $G[V_{1}\cup V_{2}]$ is cyclic. Let the
simple cycle be
$C=(1,i_{1})\rightarrow(2,i_{2})\rightarrow(1,i_{3})\rightarrow\dots\rightarrow(2,i_{2\beta})\rightarrow(1,i_{1})$
for some $\beta\leq d$. Since all the induced bipartite graphs $G[V_{i}\cup
V_{j}]$ have the same configuration for all $1\leq i<j\leq 4d$, we can claim
that for all $\ell\in[\beta]$, for each edge
$(1,i_{2\ell-1})\rightarrow(2,i_{2\ell})$ in $C$, there is an edge from
$(2\ell-1,i_{2\ell-1})$ to $(4d-\ell,i_{2\ell})$ in
$G[V_{2\ell-1},V_{4d-\ell}]$ (note that $2\ell-1<4d-\ell$ as
$\ell\leq\beta\leq d$). Similarly for all $\ell\in[\beta]$, for each edge
$(2,i_{2\ell})\rightarrow(1,i_{2\ell+1})$ in $C$ ($2\beta+1$ is to interpreted
as $1$), there is an edge from $(4d-\ell,i_{2\ell})$ to
$(2\ell+1,i_{2\ell+1})$ in $G[V_{2\ell+1},V_{4d-\ell}]$ (again, note that
$2\ell+1<4d-\ell$ as $\ell\leq\beta\leq d$). This implies that there is a
cycle
$C^{\prime}=(1,i_{1})\rightarrow(4d-1,i_{2})\rightarrow(3,i_{3})\rightarrow(4d-2,i_{4})\rightarrow\dots\rightarrow(4d-\beta,i_{2\beta})\rightarrow(1,i_{1})$
in $G$. Clearly, $C$ visits each part of $G$ at most once. Therefore, there
cannot be $4d$ parts in $G$ such that the induced directed bipartite graph
$G[V_{i}\cup V_{j}]$ has the same configuration for all $1\leq i<j\leq 4d$.

We now rephrase the question about an upper bound on ${\mathit{R}}(d)$. Let
$\mathcal{D}$ be the set of all configurations of a directed bipartite graph,
where the number of vertices in each part is at most $d$ and every vertex has
an incoming edge. We treat $\mathcal{D}$ as a set of _colors_ and note that
$|\mathcal{D}|\in 2^{\mathcal{O}(d^{2})}$. Now consider a complete graph
$K_{k}$ with vertex set $[k]$, where the vertex $\ell\in[k]$ corresponds to
part $V_{\ell}$ in $G$. For all $1\leq i<j\leq k$, we color/label the edge
$(i,j)$ in $K_{k}$ with a color from $\mathcal{D}$. The color on the edge
$(i,j)$ corresponds to the configuration of the directed bipartite graph
$G[V_{i}\cup V_{j}]$. Clearly, ${\mathit{R}}(d)$ must be strictly smaller than
the largest $k$ such that every coloring of the edges of $K_{k}$ with colors
from $\mathcal{D}$ contains a monochromatic clique of size $4d$. This value of
$k$ corresponds to the _(multicolor) Ramsey number_ [24]
$\mathcal{R}(n_{1},n_{2},\dots n_{|\mathcal{D}|})$ in which $n_{i}=4d$ for all
$i\in[|\mathcal{D}|]$. This number is finite and the current best known upper
bounds on it are exponential in $|\mathcal{D}|$ and $d$ [25, 30, 24, 21].
Therefore, ${\mathit{R}}(d)$ is also bounded. However, this upper-bound is
very large and only provides a weak version of Theorem 1. This necessitates
the study of finding “good” upper bounds on ${\mathit{R}}(d)$; in particular,
upper bounds that are polynomial in $d$. We address this in Section 5 by
showing that ${\mathit{R}}(d)\in\mathcal{O}(d^{4})$.

##  3 Preliminaries and Tools

A fair division instance is given by the three tuple
$\langle[n],M,\mathcal{V}\rangle$, where $[n]$ is the set of agents, $M$ is
the set of indivisible goods, and
$\mathcal{V}=\\{v_{1}(),v_{2}(),\dots,v_{n}()\\}$ where each $v_{i}\colon
2^{M}\rightarrow\mathbb{R}_{\geq 0}$ denotes the valuation function of agent
$i$. We assume that agents have _additive valuations_ , i.e, for all
$i\in[n]$, we have $v_{i}(S)=\sum_{g\in S}v_{i}(\\{g\\})$ for all $S\subseteq
M$. For the ease of notation, we write $v_{i}(g)$ instead of $v_{i}(\\{g\\})$
and similarly $v_{i}(S\cup g)$ for $v_{i}(S\cup\\{g\\})$. We assume that
$v_{i}(g)$ can be accessed in constant time for any $i$ and $g$. For a fixed
$0<\epsilon<1$, we say that an agent $i$

  * •

_envies_ a set $S$ of goods if $v_{i}(X_{i})<v_{i}(S)$,

  * •

_heavily envies_ a set $S$ of goods if $v_{i}(X_{i})<(1-\varepsilon)v_{i}(S)$,

  * •

_strongly envies_ a set $S$ of goods if it heavily envies a proper subset of
$S$, and

  * •

is a _most envious agent_ for a set $S$ of goods if there exists a subset
$Z\subseteq S$ such that $i$ heavily envies $Z$ and no agent strongly envies
$Z$. The pair $(t,Z)$ is called a _most-envious-agent-witness pair_ for $S$.

An agent envies (heavily envies, strongly envies) an agent $j$ if it has these
feelings for the set $X_{j}$. Clearly, strong envy implies heavy envy implies
envy. An allocation $X^{\prime}$ _strongly Pareto-dominates_ an allocation
$X$, or equivalently $X^{\prime}>_{\mathit{PD}}X$, if and only if
$v_{i}(X^{\prime}_{i})\geq v_{i}(X_{i})$ for all $i\in[n]$ and for some agent
$i^{\prime}\in[n]$ we have $(1-\varepsilon)\cdot
v_{i^{\prime}}(X^{\prime}_{i^{\prime}})\geq v_{i^{\prime}}(X_{i^{\prime}})$.

At a high level, our algorithm is similar to previous algorithms used to prove
the existence of relaxations of EFX allocations [19, 35, 18]. Our algorithm
always maintains a $(1-\varepsilon)$-EFX allocation on the set of allocated
goods and as long as the current allocation and the set of unallocated goods
$P$ satisfies “some properties”, it determines another $(1-\varepsilon)$-EFX
allocation that strongly Pareto-dominates the previous $(1-\varepsilon)$-EFX
allocation. Since the valuation of an agent for the entire good set is
bounded, this procedure will eventually converge to a $(1-\varepsilon)$-EFX
allocation, where the current allocation and the set of unallocated goods do
not satisfy these properties. The bulk of the effort goes into determining the
right properties under which one can come up with update rules that transform
one $(1-\varepsilon)$-EFX allocation into a “better” $(1-\varepsilon)$-EFX
allocation. We briefly recollect the update rules used in [31] and [19].

#### Envy cycle elimination [31].

The _envy-graph_ $E_{X}$ of an $(1-\varepsilon)$-EFX allocation $X$ has the
agents as its vertex set and there is an edge from vertex $i$ to vertex $j$ in
$E_{X}$ if agent $i$ envies agent $j$, i.e., $v_{i}(X_{i})<v_{i}(X_{j})$. The
paper [31] shows that whenever $E_{X}$ has a cycle, then one can determine
another $(1-\varepsilon)$-EFX allocation $X^{\prime}$ in which no agent has a
worse bundle and $E_{X^{\prime}}$ is acyclic. Formally,

######  Lemma 6 ([31]).

Consider a $(1-\varepsilon)$-EFX allocation $X$. If there is a cycle in
$E_{X}$, then in polynomial time, we can determine a $(1-\varepsilon)$-EFX
allocation $X^{\prime}$ such that $v_{i}(X^{\prime}_{i})\geq v_{i}(X_{i})$ for
all $i\in[n]$, and $E_{X^{\prime}}$ is acyclic.777Let $C$ be an envy cycle.
For each edge $(i,j)$ of the cycle one assigns in $X^{\prime}$ the bundle
$X_{j}$ to $i$. One continues in this way as long as there is a cycle in the
envy graph.

#### Update rules in [19].

These rules888We modify the update rules in [19] slightly, as we are dealing
with $(1-\varepsilon)$-EFX allocations and not EFX allocations are more
involved and make essential use of the concept of _a most envious agent_.

######  Observation 7.

Consider an allocation $X$ and a set $S\subseteq M$. If there is an agent that
heavily envies the bundle $S$, then we can determine a most-envious-agent-
witness pair $(t,Z)$ for $S$ in $\mathcal{O}(n\cdot|S|^{2})$ time. If there is
an agent that strongly envies $S$ then $t$ strongly envies $S$.

###### Proof.

Let $i$ be an agent that heavily envies $S$. We construct a sequence
$(t_{\ell},Z_{\ell})$ as follows: initially we set $t_{1}$ to $i$ and $Z_{1}$
to $S$. Assume that $(t_{\ell-1},Z_{\ell-1})$ is defined. If no agent
(including $t_{\ell-1}$) strongly envies $Z_{\ell-1}$, then we stop. Otherwise
let $i^{\prime}$ be an agent such that
$v_{i^{\prime}}(X_{i^{\prime}})<(1-\varepsilon)\cdot
v_{i^{\prime}}(Z_{\ell-1}\setminus\\{g\\})$ for some $g\in Z_{\ell-1}$. We set
$t_{\ell}$ to $i^{\prime}$ and $Z_{\ell}$ to $Z_{\ell-1}\setminus\\{g\\}$ and
continue. We will eventually stop, as with every next pair in the sequence,
the size of the set $Z_{\ell}$ decreases by one. Say we stop at $\ell^{*}$.
Then, we have an agent $t_{\ell^{*}}$ that heavily envies the subset
$Z_{\ell^{*}}$ of $S$. Moreover, no agent strongly envies $Z_{\ell^{*}}$. Thus
$(t_{\ell^{*}},Z_{\ell^{*}})$ is a most-envious-agent-witness pair.

If there is an agent that strongly envies $S$ then $\ell\geq 1$ and hence
$t_{\ell^{*}}$ heavily envies a proper subset of $S$. Thus $t_{\ell^{*}}$
strongly envies $S$.

It is clear that we can determine the pair in $\mathcal{O}(n\cdot|S|^{2})$
time: the maximum length of the sequence constructed is $|S|+1$ as the size of
the set $Z_{\ell}=|S|+1-\ell$. We need time $\mathcal{O}(n|S|)$ to determine
$v_{i}(S)$ for all $i$ and can update any such value in time $\mathcal{O}(1)$
after the removal of an element. For each value of $\ell$, it takes
$\mathcal{O}(n\cdot|Z_{\ell}|)=\mathcal{O}(n\cdot|S|)$ time to find
$(t_{\ell+1},Z_{\ell+1})$. Thus the total time needed is
$\mathcal{O}(n\cdot|S|^{2})$. ∎

For an allocation $X$ and set $S$ of goods that is heavily envied by some
agent, let $(t,Z)$ be the pair returned by the procedure in Observation 7. We
call $t$ _the champion_ of $S$ and $Z$ the corresponding witness.

We now state the update rules. The first rule is the simplest. It is
applicable whenever we can allocate an unallocated good to an unenvied agent
(a source in $E_{X}$), without creating any strong envy. In this case, we
simply allocate this good to the corresponding source. This creates another
$(1-\varepsilon)$-EFX allocation where no agent gets a worse bundle and the
number of unallocated goods decreases.

######  Lemma 8 ($U_{1}$ [19]).

Consider a $(1-\varepsilon)$-EFX allocation $X$. If there is a source $s$ in
$E_{X}$ and an unallocated good $g$ such that no agent strongly envies
$X_{s}\cup g$, then $X^{\prime}=\langle X_{1},X_{2},\dots,X_{s}\cup
g,\dots,X_{n}\rangle$ is a $(1-\varepsilon)$-EFX allocation and
$v_{i}(X^{\prime}_{i})\geq v_{i}(X_{i})$ for all $i\in[n]$.

Note that there can be at most $m$ consecutive applications of this rule as
the number of unallocated goods decreases by one every time we apply this
update rule. The remaining rules are applicable whenever, there are either
“valuable” goods unallocated or if “too many” goods are unallocated. We state
the second update rule, which is applicable if there is any agent that heavily
envies the set of unallocated goods. Formally,

######  Lemma 9 ($U_{2}$ [19]).

Consider a $(1-\varepsilon)$-EFX allocation $X$ and let $P$ be the set of
unallocated goods. If there is an agent $i\in[n]$ such that heavily envies
$P$, then in polynomial time, we can determine999Let $t$ be the champion of
$P$ and $Z$ be the corresponding witness. In $X^{\prime}$, one assigns $Z$ to
$t$ and changes the pool to $X_{t}\cup(P\setminus Z)$. a $(1-\varepsilon)$-EFX
allocation $X^{\prime}>_{\mathit{PD}}X$.

The third update rule is a refinement of envy-cycle elimination. In [19] it
was shown that it is applicable whenever the number of unallocated goods is at
least the number of agents.

######  Lemma 10 ($U_{3}$ [19]).

Consider a $(1-\varepsilon)$-EFX allocation $X$. If there exists a set of
sources $s_{1},s_{2},\dots s_{\ell}$ in $E_{X}$, a set of unallocated goods
$g_{1},g_{2},\dots,g_{\ell}$, and a set of agents
$t_{1},t_{2},\dots,t_{\ell}$, such that each $t_{i}$ is reachable from $s_{i}$
in $E_{X}$ and $t_{i}$ is the champion of $X_{s_{i+1}}\cup g_{i+1}$ (indices
are modulo $\ell$), then in polynomial time, we can determine101010Let
$Z_{i+1}\subseteq X_{s_{i+1}}\cup g_{i+1}$ be the witness corresponding to
$t_{i}$. One then essentially proceeds as in cycle elimination. For each $i$
one assigns $Z_{i+1}$ to $t_{i}$ and to each agent on the path from $s_{i}$ to
$t_{i}$ except for $t_{i}$ one assigns the bundle owned by the successor on
the path. a $(1-\varepsilon)$-EFX allocation $X^{\prime}>_{\mathit{PD}}X$.

##  4 Relating the Number of Unallocated Goods to the Rainbow Cycle Number

In this section, we give the proof of Theorem 4, i.e, we show how any upper
bound on ${\mathit{R}}(d)$ allows us to obtain a $(1-\varepsilon)$-EFX with
sublinear many goods unallocated. More precisely, we show that given a
$(1-\varepsilon)$-EFX allocation $X$, if $E_{X}$ is acyclic, and the update
rules $U_{1}$ and $U_{2}$ are not applicable, and the number of unallocated
goods is larger than $4n/(\varepsilon\cdot h^{-1}(2n/\varepsilon))$, then rule
$U_{3}$ is applicable. Therefore, for most of this section, we proceed under
the assumption

$E_{X}$ is acyclic and the update rules $U_{1}$(Lemma 8) and $U_{2}$ (Lemma 9)
are not applicable. (*)

We start with some definitions. Given a partial allocation $X$, we call an
unallocated good $g$ _valuable_ to an agent $i$ if $v_{i}(g)>\varepsilon\cdot
v_{i}(X_{i})$. We first make an observation about the agents that could
potentially strongly envy $X_{s}\cup g$, where $s$ is a source in $E_{X}$ and
$g$ is an unallocated good.

######  Observation 11.

Consider an unallocated good $g$ and any source $s$ in $E_{X}$. If agent $i$
heavily envies $X_{s}\cup g$, then $g$ is valuable to agent $i$.

###### Proof.

We have $v_{i}(X_{s})\leq v_{i}(X_{i})$ since $s$ is a source of $E_{X}$ and
$v_{i}(X_{i})<(1-\varepsilon)v_{i}(X_{s}\cup g)$ since $i$ heavily envies
$X_{s}\cup g$. Thus $v_{i}(X_{i})<(1-\varepsilon)(v_{i}(X_{i})+v_{i}(g))$ and
hence $(1-\varepsilon)v_{i}(g)>\varepsilon v_{i}(X_{i})$. ∎

Note that under assumption (*) for each unallocated good $g$, and each source
$s$ in the envy-graph, there is an agent that strongly envies $X_{s}\cup g$
(since the conditions of the update rule $U_{1}$ (Lemma 8) are not satisfied).
Thus, each unallocated good is valuable to some agent. Now, we make a
classification of the unallocated goods based on the number of agents that
find them valuable. To be precise, given an allocation $X$, we classify the
unallocated goods into two categories: _high-demand goods_ $H_{X}$ and _low-
demand goods_ $L_{X}$. A good $g$ belongs to $H_{X}$, if it is valuable to at
least $d+1$ agents and to $L_{X}$ if it is valuable to at most $d$ agents. We
will choose the exact value of $d$ later (right now, just think of it as any
integer less than $n$). Observe that the set of unallocated goods $P=H_{X}\cup
L_{X}$. To prove our claim, it suffices to show that when
$|H_{X}|+|L_{X}|>4n/(\varepsilon\cdot h^{-1}(2n/\varepsilon))$, the rule
$U_{3}$ is applicable. To this end, we first make a simple observation about
$|H_{X}|$.

######  Observation 12.

Under assumption (*), we have $|H_{X}|<2n/(\varepsilon\cdot d)$.

###### Proof.

For each good $g\in H_{X}$, let $\eta_{g}$ be the number of agents that find
$g$ valuable. By definition of $H_{X}$, we have that $\eta_{g}>d$ and hence
$\sum_{g}\eta_{g}>|H_{X}|d$. We next upper bound $\sum_{g}\eta_{g}$ by
$n\cdot(2/\varepsilon)$ by showing that at most $2/\varepsilon$ unallocated
goods are valuable to any agent.

Consider any agent $i$. By assumption (*) rule $U_{2}$ is not applicable and
hence the value of the unallocated goods to $i$ is at most
$1/(1-\varepsilon)v_{i}(X_{i})$. This is at most $2v_{i}(X_{i})$ since
$\varepsilon\leq 1/2$. Any valuable good has value at least $\varepsilon
v_{i}(X_{i})$ for $i$. Thus the number of unallocated goods valuable to $i$ is
at most $2/\varepsilon$. ∎

We next bound $|L_{X}|$. In particular, we show that
$|L_{X}|\leq{\mathit{R}}(d)$. To this end, we introduce the notion of _group
champion graph_ $G$.

#### Group champion graph.

To each agent $a$, we assign a source $s(a)$, such that $a$ is reachable from
$s(a)$ in the envy-graph $E_{X}$. Recall that we operating under assumption
(*) and hence $E_{X}$ is acyclic. If $a$ is reachable from multiple sources,
we pick $s(a)$ arbitrarily from these sources. Let $k:=|L_{X}|$. For each
$g\in L_{X}$, let $Q_{g}$ be the set of all agents that find $g$ valuable. By
definition of $L_{X}$, we have $|Q_{g}|\leq d$ for all $g\in L_{X}$. We now
define a $k$-partite graph $G=(\cup_{g\in L_{X}}V_{g},E)$, in which the part
$V_{g}$ corresponding to $g$ consists of copies of the sources assigned to the
agents in $Q_{g}$, formally, $V_{g}=\\{(g,s(a))\mid a\in Q_{g}\\}$. For any
goods $g$ and $h$ and agents $a\in Q_{g}$ and $b\in Q_{h}$, there is an edge
from $(g,s(a))$ in $V_{g}$ to $(h,s(b))$ in $V_{h}$ if and only if $a$ is the
champion of $X_{s(b)}\cup g$. We now make an observation about the set of
edges between $V_{g}$ and $V_{h}$ in $G$ for any $g,h\in L_{X}$.

######  Observation 13.

Under assumption (*): Consider any $g,h\in L_{X}$. Then each vertex in
$V_{h}$, has an incoming edge from a vertex in $V_{g}$.

###### Proof.

Consider any vertex $(h,s(b))\in V_{h}$. By assumption (*), there is an agent
that strongly envies the bundle $X_{s(b)}\cup g$. Otherwise, rule $U_{1}$
would be applicable. By Observation 11, all agents that strongly envy
$X_{s(b)}\cup g$, consider $g$ valuable and hence belong to $Q_{g}$. Let $a$
be the champion of $X_{s(b)}\cup g$. By Observation 7, $a$ strongly envies
$X_{s(b)}\cup g$ and hence belongs to $Q_{g}$. Thus there is an edge from
$(g,s(a))$ in $V_{g}$ to $(h,s(b))$ in $V_{h}$ (by the construction of $G$). ∎

Now we claim that the existence of a cycle that visits each part of $G$ at
most once, would imply the existence of a $(1-\varepsilon)$-EFX allocation
that Pareto-dominates the existing $(1-\varepsilon)$-EFX allocation.

######  Lemma 14.

Given a cycle $C$ in $G$ that contains at most one vertex from each $V_{g}$,
for all $g\in L_{X}$, we can determine a $(1-\varepsilon)$-EFX allocation
$X^{\prime}>_{\mathit{PD}}X$ in polynomial time.

###### Proof.

Let
$C=(g_{i+1},s_{i})\rightarrow(g_{i+2},s_{i+1})\rightarrow\dots\rightarrow(g_{j+1},s_{j})\rightarrow(g_{i+1},s_{i})$
be a cycle in $G$ that visits each part at most once. It will become clear
below, why we index the $g$’s starting at $i+1$. Consider the sequence
$s_{i},s_{i+1},\dots,s_{j}$. If all the sources in this sequence are not
distinct, there exists a contiguous subsequence
$s_{i^{\prime}},s_{i^{\prime}+1},\dots,s_{j^{\prime}}$ where all the sources
are distinct and $s_{j^{\prime}+1}=s_{i^{\prime}}$ with $i\leq
i^{\prime}<j^{\prime}\leq j$ (index $j+1$ is to be interpreted as $i$).

We now work with the sequence
$s_{i^{\prime}},s_{i^{\prime}+1},\dots,s_{j^{\prime}}$ where all the sources
are distinct and $s_{j^{\prime}+1}=s_{i^{\prime}}$. For all
$\ell\in[i^{\prime}+1,j^{\prime}+1]$, the existence of the edge
$(g_{\ell},s_{\ell-1})\rightarrow(g_{\ell+1},s_{\ell})$ implies the existence
of an agent $t_{\ell-1}$ such that $t_{\ell-1}$ is the champion of
$X_{s_{\ell}}\cup g_{\ell}$ and $s(t_{\ell-1})=s_{\ell-1}$, i.e., $t_{\ell-1}$
is reachable from $s_{\ell-1}$ in $E_{X}$. Since the sources
$s_{i^{\prime}},s_{i^{\prime}+1},\dots,s_{j^{\prime}}$ are distinct, the
agents $a_{i^{\prime}},a_{i^{\prime}+1},\dots,a_{j^{\prime}}$ are also
distinct (as each agent has a unique source assigned). Therefore, we have
distinct sources $s_{i^{\prime}},\dots,s_{j^{\prime}}$ in $E_{X}$, distinct
goods $g_{j^{\prime}+1},g_{i^{\prime}+1},\dots,g_{j^{\prime}}$ and distinct
agents $t_{i^{\prime}},\dots t_{j^{\prime}}$ that satisfy the conditions under
which the update rule $U_{3}$ (Lemma 10) is applicable. By applying $U_{3}$ we
can get a $(1-\varepsilon)$-EFX allocation $X^{\prime}>_{\mathit{PD}}X$. ∎

With Lemma 14, we are now ready to give an upper bound on $|L_{X}|$. Observe
that $|L_{X}|$ equals the number of parts in $G$. Now the question is how many
parts can $G$ have such that it does not admit a cycle that visits each part
at most once. This is where we upper bound $|L_{X}|$ with the rainbow cycle
number.

######  Lemma 15.

Consider a $(1-\varepsilon)$-EFX allocation $X$. If $|L_{X}|>{\mathit{R}}(d)$,
there is a $(1-\varepsilon)$-EFX allocation $X^{\prime}>_{\mathit{PD}}X$.

###### Proof.

Recall that $|L_{X}|=k$, where $k$ is the number of parts in $G$. Note that
each part of $G$ corresponds to the sources assigned to the agents that find a
particular good in $L_{X}$ valuable ($Q_{g}$ for some $g\in L_{X}$). By
definition of $L_{X}$, there are at most $d$ agents that find a good in
$L_{X}$ valuable. Thus each part has at most $d$ vertices. Again, by
Observation 13, between any two parts $V_{g}$ and $V_{h}$ of $G$, each vertex
in $V_{h}$ has an incoming edge from a vertex in $V_{g}$. Therefore, by
Definition 2, we have that if $k>{\mathit{R}}(d)$, then there exists a cycle
$C$ in $G$ that visits each part at most once. Once we have $C$, by Lemma 14,
we can determine a $(1-\varepsilon)$-EFX allocation
$X^{\prime}>_{\mathit{PD}}X$. ∎

Given a $(1-\varepsilon)$-EFX allocation $X$ such that
$|L_{X}|>{\mathit{R}}(d)$, Lemma 15 only gives the existence of a
$(1-\varepsilon)$-EFX allocation $X^{\prime}>_{\mathit{PD}}X$. However, to
determine $X^{\prime}$ in polynomial time, one needs to find a cycle $C$ in
$G$ which visits each part at most once when $|L_{X}|>{\mathit{R}}(d)$, in
polynomial time. Let us remark that this is a non-trivial problem in general,
reminiscent of the well-known $k$-Path and $k$-Cycle problems which are NP-
complete [22]. Here, the input is a (di)graph $G$ and an integer $k$, and the
objective is to determine of there is a path (cycle) on at least $k$-distinct
vertices of the graph. These problems can be solved in
$2^{\mathcal{O}(k)}\cdot{\sf\textup{poly}(n)}$ time using techniques based on
color-coding, hash-functions and splitters [22, 3, 34]. In particular, we can
reduce $k$-Path to the following problem in polynomial time: find a $k$-path
in a _colorful_ graph on $n$ vertices, whose vertices have been colored with
$\mathcal{O}({\sf\textup{poly}}(k)\cdot\log n)$ colors, such that every vertex
of the $k$-path has a distinct color. However, for our purposes the
construction of the cycle $C$ in $G$ is a part of the proof of Theorem 21
(described in Section 5: we show that in polynomial time, one can find a cycle
in a $(d^{4}+d)$-partite digraph, in which each part has at most $d$ vertices
and for any two parts $V$ and $V^{\prime}$ in the digraph, every vertex in
$V^{\prime}$ has an incoming edge from some vertex in $V$ and vice-versa. This
implies that if $|L_{X}|>d^{4}+d$, then in polynomial time, we can determine a
cycle $C$ in $G$ that visits each part at most once and then determine a
$(1-\varepsilon)$-EFX allocation $X^{\prime}>_{\mathit{PD}}X$ by applying
$U_{3}$. This also implies that ${\mathit{R}}(d)\leq d^{4}+d$. Therefore,

######  Lemma 16.

Consider a $(1-\varepsilon)$-EFX allocation $X$. If $|L_{X}|>d^{4}+d$, then in
polynomial time, we can determine a $(1-\varepsilon)$-EFX allocation
$X^{\prime}>_{\mathit{PD}}X$.

#### Putting it together.

We give the existence proof and indicate in brackets the changes required for
the polynomial time algorithm. We start with an empty allocation, which is
trivially a $(1-\varepsilon)$-EFX. Then, our algorithm iteratively maintains a
$(1-\varepsilon)$-EFX allocation $X$ and a pool of unallocated goods. In each
iteration, the algorithm first makes $E_{X}$ acyclic in polynomial time (Lemma
6). Thereafter, our algorithm checks whether any one of the update rules
$U_{1}$ and $U_{2}$ is applicable. If $U_{1}$ is applicable, then our
algorithm determines an allocation a $(1-\varepsilon)$-EFX allocation
$X^{\prime}$ where $v_{i}(X^{\prime}_{i})\geq v_{i}(X_{i})$ for all $i\in[n]$
and the number of unallocated goods reduces. If $U_{2}$ is applicable, then
our algorithm determines a $(1-\varepsilon)$-EFX allocation
$X^{\prime}>_{\mathit{PD}}X$. If neither $U_{1}$ nor $U_{2}$ is applicable,
then it determines the sets $H_{X}$ and $L_{X}$. By Lemma 12, we have
$|H_{X}|\leq 2n/(\varepsilon\cdot d)$. If $|L_{X}|\leq{\mathit{R}}(d)$
($|L_{X}|\leq d^{4}+d$), then it returns the allocation $X$. Otherwise it
determines a cycle that visits each part of $G$ at most once and then
determines $(1-\varepsilon)$-EFX allocation $X^{\prime}>_{\mathit{PD}}X$ by
applying update rule $U_{3}$ (by Lemma 15). If $|L_{X}|>d^{4}+d$, the cycle
can be determined in polynomial time. Therefore, when the algorithm
terminates, we have that $|H_{X}|\leq 2n/(\varepsilon\cdot d)$ and
$|L_{X}|\leq{\mathit{R}}(d)$, ($|L_{X}|\leq d^{4}+d$) implying that the total
number of unallocated goods is $|H_{X}|+|L_{X}|\leq
2\cdot\max(2n/(\varepsilon\cdot d),{\mathit{R}}(d))$
($2\cdot\max(2n/(\varepsilon\cdot d),2d^{4})$).

We now state the explicit value of $d$, first for the existence proof. We
choose $d$ as the smallest integer such that $2n/(\varepsilon
d)\leq{\mathit{R}}(d)$, i.e, $d=h^{-1}(2n/\varepsilon)$. 111111Recall that
$h(d)=d\cdot{\mathit{R}}(d)$ in Definition 2 and that $h^{-1}(2n/\varepsilon)$
is defined as the smallest integer such that $h(d)\geq 2n/\varepsilon$.
Therefore, the number of unallocated goods is at most $4n/(\varepsilon\cdot
h^{-1}(2n/\varepsilon))$.

For the algorithmic result, we choose $d$ as the smallest integer such that
$2n/(\varepsilon\cdot d)\leq 2d^{4}$. Then
$d=\lceil(n/\varepsilon)^{1/5}\rceil$ and the number of unallocated goods is
at most $4\lceil(n/\varepsilon)^{1/5}\rceil^{4}$. This is less than
$64(n/\varepsilon)^{4/5}$.

It only remains to show that the algorithm will terminate. We prove a
polynomial bound on the number of iterations. The bound applies to the
existence and the algorithmic version. To this end, note that in each
iteration, after removing cycles from $E_{X}$, our algorithm determines a new
$(1-\varepsilon)$-EFX allocation $X^{\prime}$ through one of the following
procedures:

  * •

applying $U_{1}$,

  * •

applying $U_{2}$,

  * •

determining a cycle $C$ that visits each part in $G$ at most once and then
applying $U_{3}$.

Note that the initial envy-cycle elimination and subsequent application of all
of the above procedures ensure that $v_{i}(X^{\prime}_{i})\geq v_{i}(X_{i})$
for all $i\in[n]$ (Lemmas 6, 8, 9, 10). Thus, throughout the algorithm the
valuation of an agent never decreases. Note that there cannot be more than $m$
_consecutive applications_ of $U_{1}$, as the number of unallocated goods
decreases with each application of $U_{1}$. Every time we apply $U_{2}$ or
$U_{3}$, we ensure that $X^{\prime}>_{\mathit{PD}}X$, implying that the
valuation of some agent improves by a factor of at least $(1+\varepsilon)$.
Since each agent’s valuation is bounded by $W=\mathit{max}_{i\in[n]}v_{i}(M)$,
and the valuation of an agent never decreases throughout the algorithm, we can
have at most $\textup{poly}(n,m,W,1/\varepsilon)$ many iterations that involve
applications of $U_{2}$ and $U_{3}$. Therefore, the total number of iterations
of our algorithm is $m\cdot(\text{iterations involving application of $U_{2}$
or $U_{3}$})$ which is also $\textup{poly}(n,m,\log W,1/\varepsilon)$. Notice
that in the algorithmic case, each of the iterations can also be implemented
in polynomial time: $U_{1}$ and $U_{2}$ can be implemented in polynomial time
(Lemmas 8 and 9). When $|L_{X}|\geq 2d^{4}\geq d^{4}+d$, then in polynomial
time we can determine the cycle $C$ and apply $U_{3}$ (Lemma 16). We can now
state the main result of this section.

######  Theorem 17.

Let $h(d)=d\cdot{\mathit{R}}(d)$. Then there is a $(1-\varepsilon)$-EFX
allocation $X$ and a set of unallocated goods $P$ such that
$|P|\leq({4n}/{(\varepsilon\cdot h^{-1}(n/(\varepsilon)))}$. In polynomial
time, one can find a $(1-\varepsilon)$-EFX allocation and a set $P$ of
unallocated goods such that $|P|\leq 64(n/\varepsilon)^{4/5}$.

Note that any upper bound on the rainbow cycle number will imply an upper
bound on the number of unallocated goods.

##  5 Bounds on the Rainbow Cycle Number

In this section, we give the proof of Theorem 3. We briefly recall the setup:
There is a $k$-partite digraph $G=(\cup_{i\in[k]}V_{i},E_{G})$ such that each
part has at most $d$ vertices. For every distinct parts $V_{i}$ and $V_{j}$,
every vertex in $V_{j}$ has an incoming edge from some vertex in $V_{i}$.
There is no cycle in $G$ that visits each part at most once. Our goal is to
establish an upper bound on $k$.

We now introduce some helpful notations and concepts. For each $i\in[k]$, we
represent the vertices in the part $V_{i}$ as $(i,\textup{vertex id})$, i.e,
$V_{i}=\\{(i,1),(i,2),\dots,(i,\lvert V_{i}\rvert)\\}$. For any positive
integer $d$ and $a,b\in[d]$, we use $\sigma_{d}(a,b)$ to denote $(a-1)\cdot
d+b$. Note that $1\leq\sigma_{d}(a,b)\leq d^{2}$. The $\sigma_{d}(a,b)$
captures the lexicographic ordering among the pairs
$\cup_{a\in[d]}\cup_{b\in[d]}(a,b)$. For any Boolean vector
$u\in\\{0,1\\}^{r}$, we use $u[k]$ to refer to the $k^{\mathit{th}}$
coordinate of the vector $u$. We introduce the simple yet crucial notion of
_representative set for a set of Boolean vectors_. Given a set $D$ of
$r$-dimensional Boolean vectors, the set $B\subseteq D$ is a _representative
set_ of $D$, if $\\{\ell\mid\text{$a[\ell]=1$ for some $a\in
D$}\\}=\\{\ell\mid\text{$b[\ell]=1$ for some $b\in B$}\\}$. We first make an
observation about the size of $B$.

######  Observation 18.

Given any set $D$ of $r$-dimensional Boolean vectors, there exists a
representative set $B\subseteq D$ of size at most $r$.

###### Proof.

For each coordinate $\ell\in[r]$ we do: if there is a vector $a\in D$ with
$a[\ell]=1$, we put one such vector into $B$. Clearly, $|B|\leq r$. ∎

We prove Theorem 3 by contradiction. To be precise, we show that if
$k>d^{4}+d$, then there exists a cycle in $G$ that visits every part at most
once. Moreover, this cycle can be found in time polynomial in $k$.

We construct the cycle in two steps. We first show the existence of a part
$V_{\tilde{\ell}}$ such that there is a directed cycle that visits only the
parts $V_{\tilde{\ell}}$, $V_{1}$, $V_{2}$, …, $V_{d}$ and moreover each of
the parts $V_{1}$, $V_{2}$, …, $V_{d}$ at most once. In the second step we
replace the vertices in $V_{\tilde{\ell}}$ in this cycle by vertices in
distinct parts.

For each ordered pair $(i,j)\in[d]\times[d]$, and $\ell\in[k]\setminus[d]$, we
define a $d^{2}$-dimensional vector $u_{i,j,\ell}$ as follows: for all
$x\in[d]$ and $y\in[d]$, we set $u_{i,j,\ell}[\sigma_{d}(x,y)]=1$ if and only
if there exists a path $(i,x)\rightarrow(\ell,z)\rightarrow(j,y)$ in $G$ for
some $(\ell,z)\in V_{\ell}$, i.e., if there exists a path from vertex $(i,x)$
in $V_{i}$ to vertex $(j,y)$ in $V_{j}$ through some vertex in $V_{\ell}$.
Otherwise, we set $u_{i,j,\ell}[\sigma_{d}(x,y)]=0$.

Let $\mathcal{L}=[k]\setminus[d]$. For each ordered pair
$(i,j)\in[d]\times[d]$, we construct the sets $B^{i,j}$ and
$\mathcal{L}^{i,j}$ as follows: For each $(i,j)$ taken in the increasing order
of $\sigma_{d}(i,j)$, define $\mathcal{L}^{i,j}=\mathcal{L}$ and $B^{i,j}$ as
a representative vector set of
$\\{u_{i,j,\ell}\mid\ell\in\mathcal{L}^{i,j}\\}$ of size at most $d^{2}$. A
set $B^{i,j}$ of this size exists because our vectors have dimension $d^{2}$.
Then we set $\mathcal{L}=\mathcal{L}\setminus\\{\ell\mid u_{i,j,\ell}\in
B^{i,j}\\}$. At most $d^{2}$ elements are removed from $\mathcal{L}$ in each
iteration.

For clarity, we write $\mathcal{L}^{f}$ to denote the set $\mathcal{L}$ at the
end of the construction. Observe that $|\mathcal{L}^{f}|\geq 1$. This holds
since we start with a set of size larger than $d^{4}$ and removed at most
$d^{2}$ elements in each of the $d^{2}$ iterations.

######  Observation 19.

Consider distinct ordered pairs $(i,j)\in[d]\times[d]$ and
$(i^{\prime},j^{\prime})\in[d]\times[d]$. The sets $\\{\ell\mid
u_{i,j,\ell}\in B^{i,j}\\}$ and $\\{\ell\mid u_{i^{\prime},j^{\prime},\ell}\in
B^{i^{\prime},j^{\prime}}\\}$ are disjoint.

###### Proof.

Let us assume without loss of generality that
$\sigma_{d}(i,j)<\sigma_{d}(i^{\prime},j^{\prime})$. Consider any $\ell$ such
that $u_{i,j,\ell}\in B^{i,j}$. Then $\ell$ is removed from $\mathcal{L}$ at
the end of the iteration for the pair $(i,j)$ and hence does not belong to
$\mathcal{L}$ at the beginning of the iteration for the pair
$(i^{\prime},j^{\prime})$. Consequently $u_{i^{\prime},j^{\prime},\ell}\notin
B^{i^{\prime},j^{\prime}}$ (by definition of $B^{i^{\prime},j^{\prime}}$, if
$u_{i^{\prime},j^{\prime},\ell}\in B^{i^{\prime},j^{\prime}}$, then
$\ell\in\mathcal{L}^{i^{\prime},j^{\prime}}$). ∎

At the end of the construction, we arbitrarily pick a
$\tilde{\ell}\in\mathcal{L}^{f}$ (this is possible as
$\mathcal{L}^{f}\neq\emptyset$). Now, we make a small observation about the
vector $u_{i,j,\tilde{\ell}}$ for all $i,j\in[d]$.

######  Observation 20.

For all $i,j\in[d]$, if $u_{i,j,\tilde{\ell}}[q]=1$ for some $q\in[d^{2}]$,
then there exists a vector $u_{i,j,{l^{\prime}}}\in B^{i,j}$ such that
$u_{i,j,{l^{\prime}}}[q]=1$.

###### Proof.

Observe that $\mathcal{L}^{f}\subseteq\mathcal{L}^{i,j}$. Therefore,
$\tilde{l}\in\mathcal{L}^{i,j}$. By definition, $B^{i,j}$ is a representative
vector set of $\\{u_{i,j,\ell}\mid\ell\in\mathcal{L}^{i,j}\\}$. Therefore, by
the definition of representative set, there exists a vector
$u_{i,j,{\ell^{\prime}}}\in B^{i,j}$ such that $u_{i,j,{\ell^{\prime}}}[q]=1$.
∎

We are now ready for the construction of a cycle that visits each part at most
once. We first show that there exists a cycle $C$ in $G$ that visits only the
parts $V_{\tilde{\ell}}$, $V_{1}$, …, $V_{d}$ and each of the parts $V_{1}$,
…$V_{d}$ at most once, i.e, the only part it may visit more than once is
$V_{\tilde{\ell}}$. See Figure 2 for an illustration.

$\scriptstyle{(1,v_{1})}$$\scriptstyle{(2,v_{2})}$$\scriptstyle{(3,v_{3})}$$\scriptstyle{(\tilde{\ell},w_{1})}$$\scriptstyle{(\tilde{\ell},w_{2})}$$\scriptstyle{(\tilde{\ell},w_{3})}$$V_{1}$$V_{2}$$V_{3}$$V_{\tilde{\ell}}$
Figure 2: Illustration of the first part of the construction. The cycle in the
figure visits the parts $V_{1}$, $V_{2}$ and $V_{3}$ exactly once and the part
$V_{\tilde{\ell}}$ three times. It is given by
$(\tilde{\ell},w_{3})\rightarrow(1,v_{1})\rightarrow(\tilde{\ell},w_{1})\rightarrow(2,v_{2})\rightarrow(\tilde{{\ell}},w_{2})\rightarrow(3,v_{3})\rightarrow(\tilde{\ell},w_{3})$.

Let $({\tilde{\ell}},w_{d})$ be an arbitrary vertex in $V_{\tilde{\ell}}$. We
construct a path

$(\tilde{\ell},w_{0})\rightarrow(1,v_{1})\rightarrow\ldots\rightarrow(i-1,v_{i-1})\rightarrow(\tilde{\ell},w_{i-1})\rightarrow(i,v_{i})\rightarrow(\tilde{\ell},w_{i})\rightarrow\ldots\rightarrow(d,v_{d})\rightarrow(\tilde{\ell},w_{d})$

by starting at $(\tilde{\ell},w_{d})$ and tracing backwards: We start in
$(\tilde{\ell},w_{d})$. Assume that we already traced back to
$(\tilde{\ell},w_{i})$ with $i=d$ initially. By the construction of $G$, there
must be an edge from some vertex $(i,v_{i})$ in $V_{i}$ to
$(\tilde{\ell},w_{i})$ in $V_{\tilde{\ell}}$, and there must be an edge from
some vertex $(\tilde{\ell},w_{i-1})$ in $V_{\tilde{\ell}}$ to $(i,v_{i})$ in
$V_{i}$. Thus there is the path
$(\tilde{\ell},w_{i-1})\rightarrow(i,v_{i})\rightarrow(\tilde{\ell},w_{i})$ in
$G$. We keep continuing this procedure until we reach $(\tilde{\ell},w_{0})$.

Since the part $V_{\tilde{\ell}}$ can have at most $d$ vertices, by the
pigeonhole principle, there must be $i$ and $j$ with $0\leq i<j\leq d$ such
that $w_{i}=w_{j}$. Let $C$ be the subpath from $(\tilde{\ell},w_{i})$ to
$(\tilde{\ell},w_{j})$, i.e.,

$C=(\tilde{\ell},w_{i})\rightarrow(i+1,v_{i+1})\rightarrow(\tilde{\ell},w_{i+1})\rightarrow\ldots\rightarrow(\tilde{\ell},w_{j-1})\rightarrow(j,v_{j})\rightarrow(\tilde{\ell},w_{j}).$

Observe that $C$ visits all the parts of $G$ except $V_{\tilde{\ell}}$ at most
once. We now show that by using “bypass” parts we can make the cycle simple.
For clarity, we rewrite $C$ as

$C=(i+1,v_{i+1})\rightarrow(\tilde{\ell},w_{i+1})\rightarrow\ldots\rightarrow(\tilde{\ell},w_{j-1})\rightarrow(j,v_{j})\rightarrow(\tilde{\ell},w_{j})\rightarrow(i+1,v_{i+1}).$

$\scriptstyle{(1,v_{1})}$$\scriptstyle{(2,v_{2})}$$\scriptstyle{(3,v_{3})}$$\scriptstyle{(\tilde{\ell},w_{1})}$$\scriptstyle{(\tilde{\ell},w_{2})}$$\scriptstyle{(\tilde{\ell},w_{3})}$$\scriptstyle{(\ell_{1},y_{1})}$$\scriptstyle{(\ell_{2},y_{2})}$$\scriptstyle{(\ell_{3},y_{3})}$$V_{1}$$V_{2}$$V_{3}$$V_{\tilde{\ell}}$$V_{\ell_{1}}$$V_{\ell_{2}}$$V_{\ell_{3}}$
Figure 3: Illustration of the existence of a cycle that visits every part at
most once. We take the instance in Figure 2, where there exists a cycle $C$
that visits every part other than $V_{\tilde{\ell}}$ at most once. The edges
of the cycle $C$ are light gray color in color. The figure shows how to obtain
a cycle $C^{\prime}$ that visits every part at most once from $C$. The edges
of $C^{\prime}$ are blue in color. For all $i\in[3]$, we replace the subpath
in $C$ of the form
$(i,v_{i})\rightarrow(\tilde{\ell},w_{i})\rightarrow(i+1,v_{i+1})$ ($3+1$ is
to be interpreted as $1$) by
$(i,v_{i})\rightarrow(\ell_{i},y_{i})\rightarrow(i+1,v_{i+1})$ to get
$C^{\prime}$.

#### Making the Cycle Simple.

For all $q\in[i+1,j]$ consider the subpath

$(q,v_{q})\rightarrow(\tilde{\ell},w_{q})\rightarrow(q+1,v_{q+1})$

of $C$ (index $j+1$ is to be interpreted as $i+1$). The existence of such a
subpath in $G$ implies that
$u_{q,q+1,\tilde{\ell}}[\sigma_{d}(v_{q},v_{q+1})]=1$. By Observation 20, we
know that there is a vector $u_{q,q+1,\ell_{q}}\in B^{q,q+1}$ such that
$u_{q,q+1,\ell_{q}}[\sigma_{d}(v_{q},v_{q+1})]=1$. This implies that there
exists a part $V_{\ell_{q}}$, and a vertex $(\ell_{q},y_{q})$ in part
$V_{\ell_{q}}$, such that there is a subpath

$(q,v_{q})\rightarrow({\ell_{q}},y_{q})\rightarrow(q+1,v_{q+1})\enspace.$

By Observation 19, we have that $\ell_{q}\neq\ell_{q^{\prime}}$ for all $q\neq
q^{\prime}$. Therefore we have a simple cycle $C^{\prime}$ in $G$ that visits
each part in $G$ at most once, namely,

$C^{\prime}=(i+1,v_{i+1})\rightarrow(\ell_{i+1},y_{i+1})\rightarrow\dots\rightarrow(\ell_{j-1},y_{j-1})\rightarrow(j,v_{j})\rightarrow(\ell_{j},y_{j})\rightarrow(i+1,v_{i+1}).$

See Figure 3 for an illustration of this entire procedure.

Therefore if $k>d^{4}+d$, then there exists a cycle in $G$ that visits each
part at most once. Moreover, this cycle can be found in time polynomial in
$k$. With this we arrive at the main result of this section.

######  Theorem 21.

For all $d\geq 1$, we have ${\mathit{R}}(d)\leq d^{4}+d$. Furthermore, Let $G$
be a $k$-partite digraph with $k>d^{4}+d$ parts of cardinality at most $d$
each, such that for every vertex $v$ and any part $W$ not containing $v$,
there is an edge from $W$ to $v$. Then, there exists a cycle in $G$ visiting
each part at most once, and it can be found in time polynomial in $k$.

An improved upper bound on ${\mathit{R}}(d)$ would imply a better bound on the
number of unallocated goods. However, we show that an exponential improvement
(e.g. ${\mathit{R}}(d)\in\textup{poly}(\log(d))$) is not possible by showing a
_linear_ lower bound, i.e., ${\mathit{R}}(d)\geq d$. However, this still
leaves room for polynomial improvement and we suspect that
${\mathit{R}}(d)\in\mathcal{O}(d)$. This would imply the existence of a
$(1-\varepsilon)$-EFX allocation with $\mathcal{O}(\sqrt{n/\varepsilon})$ many
goods unallocated. For a polynomial time algorithm, the construction of a
cycle as in Theorem 21 would have to be polynomial time. However, we remark
that this is an initiation study for determining $(1-\varepsilon)$-EFX
allocations with sublinear number of unallocated goods and we use concepts
like the _group champion graph_ that are natural extensions of the champion
graph. We believe that this still leaves room for developing more
sophisticated concepts and techniques that may reduce the number of
unallocated goods to $o(\sqrt{n/\varepsilon})$.

#### Lower bound on ${\mathit{R}}(d)$.

We show that ${\mathit{R}}(d)\geq d$. We construct a $d$-partite graph
$G=(\cup_{i\in[d]}V_{i},E)$ such that each part $V_{i}$ has $d$ vertices, for
all pairs of parts $V_{i}$ and $V_{j}$, every vertex in $V_{j}$ has an
incoming edge from a vertex in $V_{i}$ and vice-versa, and there exists no
cycle that visits each part at most once.

We now define the edges in $G$. Let $V_{i}=\\{(i,0),(i,1),\dots,(i,d-1)\\}$.
Consider any $i$ and $j$ such that $i<j$ . For each $0\leq\ell\leq d-1$, we
have an edge from $(i,\ell)$ in $V_{i}$ to $(j,\ell)$ in $V_{j}$ and there is
an edge from $(j,\ell)$ in $V_{j}$ to $(i,(\ell+1)\bmod d)$ in $V_{i}$ (see
Figure 4 for an illustration). One can easily verify that for all parts
$V_{i}$ and $V_{j}$, every vertex in part $V_{j}$ has an incoming edge from
part $V_{i}$ and vice-versa. It suffices to show that $G$ admits no cycle that
visits each part at most once.

$V_{1}$$V_{2}$$\scriptstyle{(1,0)}$$\scriptstyle{(1,1)}$$\scriptstyle{(2,0)}$$\scriptstyle{(2,1)}$$V_{1}$$V_{2}$$V_{3}$$\scriptstyle{(1,0)}$$\scriptstyle{(1,1)}$$\scriptstyle{(1,2)}$$\scriptstyle{(2,0)}$$\scriptstyle{(2,1)}$$\scriptstyle{(2,2)}$$\scriptstyle{(3,0)}$$\scriptstyle{(3,1)}$$\scriptstyle{(3,2)}$
Figure 4: Illustration of the construction of $d$-partite graph $G$ that
satisfies all the conditions in Definition 2, for $d=2$ (left) and $d=3$
(right).

######  Lemma 22.

There exists no cycle in $G$ that visits each part at most once.

###### Proof.

We prove by contradiction. Assume that there is a cycle
$C=(i_{1},\ell_{1})\rightarrow(i_{2},\ell_{2})\rightarrow\dots\rightarrow(i_{r},\ell_{r})\rightarrow(i_{1},\ell_{1})$
that visits each part at most once, i.e., $i_{1}\neq i_{2}\neq\dots\neq
i_{r}$. From here on, all the indices are modulo $r$. Note that by the
construction of the edges of $G$, for all $q\in[r]$, we have
$\ell_{q+1}=\ell_{q}$ if $i_{q}<i_{q+1}$ and $\ell_{q+1}=(\ell_{q}+1)\bmod d$
if $i_{q}>i_{q+1}$. Let $\\#_{1}=\\{q\in[r]\mid i_{q}>i_{q+1}\\}$ (recall that
$r+1$ is $1$). The existence of the cycle $C$ in $G$ implies that
$\ell_{1}=(\ell_{1}+\\#_{1})\bmod d$.

Since $i_{1}\neq i_{2}\neq\dots\neq i_{r}$ and there exists the cycle $C$ in
$G$, there are indices $q^{\prime}$ and $q^{\prime\prime}$ such that
$i_{q^{\prime}}>i_{q^{\prime}+1}$ and
$i_{q^{\prime\prime}}<i_{q^{\prime\prime}+1}$, further implying that
$1\leq\\#_{1}\leq r-1$. Since $G$ has $d$ parts, we have $r\leq d$, implying
that $1\leq\\#_{1}\leq d-1$. However this implies that $(\ell_{1}+\\#_{1})\mod
d\neq\ell_{1}$, which is a contradiction. ∎

##  6 Finding _Efficient_ $(1-\varepsilon)$-EFX Allocations with Sublinear
Number of Unallocated Goods

We note that like the algorithms in [19, 35], our algorithm is flexible with
the initialization, i.e., starting with any initial $(1-\varepsilon)$-EFX
allocation $X$, it can determine a final $(1-\varepsilon)$-EFX allocation $Y$
with at most $\mathcal{O}((n/\varepsilon)^{\tfrac{4}{5}})$ many goods
unallocated and $v_{i}(Y_{i})\geq v_{i}(X_{i})$ for all $i\in[n]$. This is
consequence of the fact that the valuation of an agent never decreases
throughout our algorithm. Therefore, our algorithm maintains the welfare of
the initial allocation. Thus, if we choose the initial $(1-\varepsilon)$-EFX
allocation carefully, we can also guarantee high Nash welfare for our final
$(1-\varepsilon)$-EFX allocation with sublinear many goods unallocated. To
this end, we use an important result from Caragiannis et al. [16] about
determining partial EFX allocations with high Nash welfare in polynomial time.

######  Theorem 23 ([16]).

In polynomial time, we can determine a partial EFX allocation $X$ such that
$\mathit{NW}(X)\geq 1/(2.88)\cdot\mathit{NW}(X^{*})$ where $X^{*}$ is the Nash
welfare maximizing allocation.121212In fact, the result in [16] show the
existence of partial EFX allocations that achieve a $1/2$ approximation of the
Nash welfare. However, in polynomial time, one can only find a partial EFX
allocation with a $1/2.88$ approximation of the Nash welfare.

Let $X$ be the partial EFX allocation that achieves a $2.88$ approximation of
the Nash welfare. We run our algorithm starting with $X$ as the initial
allocation. The final $(1-\varepsilon)$-EFX allocation with sublinear many
unallocated goods is also a $2.88$ approximation of the Nash welfare as the
valuations of the agents in the final allocation is at least their valuations
in $X$. Therefore, we have the following theorem,

######  Theorem 24.

In polynomial time, we can determine a $(1-\varepsilon)$-EFX allocation with
$\mathcal{O}((n/\varepsilon)^{\tfrac{4}{5}})$ goods unallocated. Furthermore,
$\mathit{NW}(X)\geq 1/(2.88)\cdot\mathit{NW}(X^{*})$.131313Note that using the
existence of partial EFX allocations with $1/2$ approximation to Nash welfare,
one can also claim the existence of a $(1-\varepsilon)$-EFX allocation $X$
with $\mathcal{O}((n/\varepsilon)^{\tfrac{4}{5}})$ goods unallocated such that
$\mathit{NW}(X)\geq 1/2\cdot\mathit{NW}(X^{*})$.

##  7 Limitations of the Approach in [18]

In [18], an algorithmic proof to the existence of EFX allocations is shown for
three agents with additive valuations. We briefly sketch the proof technique
in [18] and then highlight why it does not work for determining a
$(1-\varepsilon)$-EFX allocations with just four agents. Let the three agents
be $a$, $b$ and $c$ and for any allocation $X$, let $\phi(X)$ be the vector
$\langle v_{a}(X_{a}),v_{b}(X_{b}),v_{c}(X_{c})\rangle$. The algorithm starts
with an empty allocation which is trivially EFX and as long as there is an
unallocated good, the algorithm determines another EFX allocation $X^{\prime}$
such that $\phi(X^{\prime})$ is lexicographically larger than $\phi(X)$, i.e.,
either $v_{a}(X^{\prime}_{a})>v_{a}(X_{a})$ or
$v_{a}(X^{\prime}_{a})=v_{a}(X_{a})$ and $v_{b}(X^{\prime}_{b})>v_{b}(X_{b})$
or $v_{a}(X^{\prime}_{a})=v_{a}(X_{a})$, $v_{b}(X^{\prime}_{b})=v_{b}(X_{b})$
and $v_{c}(X^{\prime}_{c})>v_{c}(X_{c})$. Berger et al. [12] show that the
same potential (namely $\phi(\cdot)$) can be used to show the existence of EFX
allocations for four agents with at most one unallocated good. In this paper,
we show that such a technique cannot be used to show the existence of
$(1-\varepsilon)$-EFX allocations for four agents.

######  Theorem 25.

There exists an instance $I$ with four agents, $\\{a,b,c,d\\}$ with additive
valuations, nine goods $\\{g_{i}\mid i\in[9]\\}$ and a partial
$(1-\varepsilon)$-EFX allocation $X$ on the goods $\cup_{i\in[8]}g_{i}$, such
that in all complete $(1-\varepsilon)$-EFX allocation, the valuation of agent
$a$ will be strictly less than her valuation in $X$, i.e., for all complete
$(1-\varepsilon)$-EFX allocation $Y$, $\phi(Y)$ is lexicographically smaller
than $\phi(X)$.

We remark that our instance builds on the instance in [18], that is used to
show the existence of a partial EFX allocation which is not Pareto-dominated
by any complete EFX allocation. We now construct an instance $I$ with four
agents, say $\\{a,b,c,d\\}$ with additive valuations and nine goods
$\\{g_{i}\mid i\in[9]\\}$. Let $\phi(X)=\langle
v_{a}(X_{a}),v_{b}(X_{b}),v_{c}(X_{c}),v_{d}(X_{d})\rangle$. We show a
$(1-\varepsilon)$-EFX allocation $X$ of eight goods among four agents. Then we
show in any complete $(1-\varepsilon)$-EFX allocation, the valuation of agent
$a$ will be strictly less than (almost half of) her valuation in $X$. This
shows that for any complete $(1-\varepsilon)$-EFX allocation $Y$, we have
$\phi(X)$ is lexicographically larger than $\phi(Y)$.

| $g_{1}$ | $g_{2}$ | $g_{3}$ | $g_{4}$ | $g_{5}$ | $g_{6}$ | $g_{7}$ | $g_{8}$ | $g_{9}$
---|---|---|---|---|---|---|---|---|---
$\mathbf{a}$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $6$ | $4$ | $0$
$\mathbf{b}$ | $16$ | $4$ | $24$ | $4$ | $0$ | $34$ | $31$ | $0$ | $2$
$\mathbf{c}$ | $10$ | $0$ | $18$ | $8$ | $20$ | $0$ | $29$ | $0$ | $6$
$\mathbf{d}$ | $0$ | $0$ | $0$ | $0$ | $18$ | $20$ | $19$ | $0$ | $4$
Table 1: An instance where showing that the technique in [18] cannot be used
to determine $(1-\varepsilon)$-EFX allocations with four agents. In
particular, given a $(1-\varepsilon)$-EFX allocation $X$ and the unallocated
good $g_{9}$, there is no complete $(1-\varepsilon)$-EFX allocation where the
valuation of agent $a$ does not strictly decrease, i.e., in any complete
$(1-\varepsilon)$-EFX allocations $Y$, we have $v_{a}(Y_{a})<v_{a}(X_{a})$.

The full description of our instance is captured by Table 1. We choose our
$\varepsilon\ll 1$. The sub-instance defined by the agents $b$, $c$ and $d$,
and the goods $\cup_{i\in[6]}g_{i}\cup g_{9}$ is the instance in [18] used to
show the existence of a partial EFX allocation which is not Pareto-dominated
by any complete EFX allocation. We now specify the allocation $X$.

$\displaystyle X_{a}=\\{g_{7},g_{8}\\}$ $\displaystyle
X_{b}=\\{g_{2},g_{3},g_{4}\\}$ $\displaystyle X_{c}=\\{g_{1},g_{5}\\}$
$\displaystyle X_{d}=\\{g_{6}\\}$

The good $g_{9}$ is unallocated. We will show that in any complete
$(1-\varepsilon)$-EFX allocation, agent $a$ cannot have both $g_{7}$ and
$g_{8}$. This would imply that agent $a$’s valuation in any final
$(1-\varepsilon)$-EFX allocation is strictly less than her valuation in $X$
(as agent $a$’s valuation for all goods other than $g_{7}$ and $g_{8}$ is
zero). We prove this claim by contradiction. So assume that $Y$ is a complete
$(1-\varepsilon)$-EFX allocation and $\\{g_{7},g_{8}\\}\subseteq Y_{a}$. Note
that $v_{b}(g_{7})=31$, $v_{c}(g_{7})=29$, and $v_{d}(g_{7})=19$. Since
$Y_{a}$ contains at least one other good namely $g_{8}$, each of the agents
$b$, $c$ and $d$ need to be allocated bundles that they value at least $31$,
$29$ and $19$ respectively.

First, consider the case that ${g_{6}\in Y_{b}}$. Then we have
$v_{b}(Y_{b})\geq 34$. Now, to ensure $v_{d}(Y_{d})\geq 19$, we need to
allocate $g_{5}$ and $g_{9}$ to $d$, as $d$ values all the other goods zero.
We are left with goods $g_{1}$, $g_{2}$, $g_{3}$ and $g_{4}$. In order to
ensure $v_{c}(Y_{c})\geq 29$, we definitely need to allocate $g_{1}$, $g_{3}$
and $g_{4}$ to $c$. Now, even if we allocate the remaining good $g_{2}$ to
$b$, we have
$v_{b}(Y_{b})=v_{b}(\left\\{g_{2},g_{6}\right\\})=38<(1-\varepsilon)\cdot
40=(1-\varepsilon)\cdot
v_{b}(\left\\{g_{1},g_{3}\right\\})\leq(1-\varepsilon)\cdot{v_{b}}(Y_{c}\setminus
g_{4})$. Therefore, $b$ will strongly envy $c$. Thus $g_{6}\notin Y_{b}$.

If $g_{6}\notin Y_{b}$ and $v_{b}(Y_{b})\geq 31$, $Y_{b}$ must contain $g_{3}$
(the total valuation for $b$ of all the goods other than $g_{3}$, $g_{6}$,
$g_{7}$ and $g_{8}$ is less than $31$). Now we consider some more subcases.

Let us first assume that ${g_{1}\in Y_{b}}$. Since $Y_{b}$ already contains
$g_{1}$ and $g_{3}$, the goods that can be allocated to $c$ and $d$ are
$g_{2}$, $g_{4}$, $g_{5}$, $g_{6}$, and $g_{9}$. In order to ensure
$v_{c}(Y_{c})\geq 29$ we need to allocate $g_{4}$, $g_{5}$, and $g_{9}$ to
$c$. Now, even if we allocate all the remaining goods ($g_{2}$ and $g_{6}$) to
$d$, we have
$v_{d}(Y_{d})=v_{d}(\left\\{g_{3},g_{6}\right\\})=20<(1-\varepsilon)\cdot
22=(1-\varepsilon)\cdot
v_{d}(\left\\{g_{5},g_{7}\right\\})\leq(1-\varepsilon)\cdot
v_{d}(Y_{c}\setminus g_{4})$. Therefore, $d$ will strongly envy $c$.

Thus $g_{1}\notin Y_{b}$. Since neither $g_{1}$ nor $g_{6}$ belongs to
$Y_{b}$, the only way to ensure $v_{b}(Y_{b})\geq 31$ is to at least allocate
$g_{2}$, $g_{3}$, and $g_{4}$ to $b$ (we can allocate more). Similarly, given
that the goods not allocated yet are $g_{1}$, $g_{5}$, $g_{6}$, and $g_{9}$,
the only way to ensure $v_{c}(Y_{c})\geq 29$ is to allocate at least $g_{1}$
and $g_{5}$ to $c$. Similarly, the only way to ensure $v_{d}(Y_{d})\geq 19$
now is to allocate at least $g_{6}$ to $d$. Now we only have to allocate
$g_{9}$. We show that adding $g_{9}$ to any one of the existing bundles will
cause a violation of the $(1-\varepsilon)$-EFX property.

  * •

Adding $g_{9}$ to $Y_{a}$: $b$, $c$ and $d$ strongly envies $a$ as
$v_{b}(Y_{b})=32<(1-\varepsilon)\cdot 33=(1-\varepsilon)\cdot
v_{b}(\\{g_{7},g_{9}\\})\leq(1-\varepsilon)\cdot v_{b}(Y_{a}\setminus g_{8})$.
Similarly we have $v_{c}(Y_{c})=30<(1-\varepsilon)\cdot
35=(1-\varepsilon)\cdot v_{c}(\\{g_{7},g_{9}\\})\leq(1-\varepsilon)\cdot
v_{c}(Y_{a}\setminus g_{8})$ and $v_{d}(Y_{d})=20<(1-\varepsilon)\cdot
23=(1-\varepsilon)\cdot v_{d}(\\{g_{7},g_{9}\\})\leq(1-\varepsilon)\cdot
v_{d}(Y_{a}\setminus g_{8})$.

  * •

Adding $g_{9}$ to $Y_{b}$: $c$ strongly envies $b$ as
$v_{c}(Y_{c})=30<(1-\varepsilon)\cdot 32=(1-\varepsilon)\cdot
v_{c}(\left\\{g_{3},g_{4},g_{7}\right\\})=(1-\varepsilon)\cdot
v_{c}(Y_{b}\setminus g_{2})$.

  * •

Adding $g_{9}$ to $Y_{c}$: $d$ strongly envies $c$ as
$v_{d}(Y_{d})=20<(1-\varepsilon)\cdot 22=(1-\varepsilon)\cdot
v_{d}(\left\\{g_{5},g_{9}\right\\})=(1-\varepsilon)\cdot v_{d}(Y_{c}\setminus
g_{1})$.

  * •

Adding $g_{9}$ to $Y_{d}$: $b$ strongly envies $d$ as
$v_{b}(Y_{a})=32<(1-\varepsilon)\cdot 34=(1-\varepsilon)\cdot
v_{b}(g_{6})=(1-\varepsilon)\cdot v_{b}(Y_{d}\setminus g_{9})$.

This shows that $\\{g_{7},g_{8}\\}\not\subseteq Y_{a}$ for any complete
$(1-\varepsilon)$-EFX allocation $Y$. This implies that agent $a$’s valuation
in $Y$ is strictly less than her valuation in $X$, implying that $\phi(X)$ is
lexicographically larger than $\phi(Y)$. This shows that the approach from
[18] cannot be generalized to guarantee $(1-\varepsilon)$-EFX allocation when
there are four or more agents.

## References

  * [1] www.spliddit.org.
  * [2] www.fairoutcomes.com.
  * [3] N. Alon, R. Yuster, and U. Zwick.  Color-coding.  Journal of the ACM (JACM), 42(4):844–856, 1995.
  * [4] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris.  Maximum Nash welfare and other stories about EFX.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (IJCAI), pages 24–30, 2020.
  * [5] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi.  Approximation algorithms for computing maximim share allocations.  ACM Transactions on Algorithms, 13(4):52:1–52:28, 2017.
  * [6] G. Amanatidis, E. Markakis, and A. Ntokos.  Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.  Theor. Comput. Sci., 841:94–109, 2020.
  * [7] N. Anari, S. O. Gharan, A. Saberi, and M. Singh.  Nash Social Welfare, Matrix Permanent, and Stable Polynomials.  In 8th Innovations in Theoretical Computer Science Conference (ITCS), pages 1–12, 2017.
  * [8] H. Aziz, S. Gaspers, S. Mackenzie, and T. Walsh.  Fair assignment of indivisible objects under ordinal preferences.  Artif. Intell., 227:71–92, 2015.
  * [9] S. Barman and S. K. Krishnamurthy.  Approximation algorithms for maximin fair division.  In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 647–664, 2017.
  * [10] S. Barman, S. K. Krishnamurthy, and R. Vaish.  Finding fair and efficient allocations.  In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 557–574, 2018.
  * [11] S. Barman, S. K. Krishnamurthy, and R. Vaish.  Greedy algorithms for maximizing Nash social welfare.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 7–13, 2018.
  * [12] B. Berger, A. Cohen, M. Feldman, and A. Fiat.  (Almost full) EFX exists for four agents (and beyond).  CoRR, abs/2102.10654, 2021.
  * [13] S. Bouveret and M. Lemaître.  Characterizing conflicts in fair division of indivisible goods using a scale of criteria.  In Autonomous Agents and Multi-Agent Systems (AAMAS) 30, 2, pages 259–290, 2016.
  * [14] S. J. Brams, D. M. Kilgour, and C. Klamler.  Maximin envy-free division of indivisible items.  Group Decision and Negotiation, 26(1):115–131, 2017.
  * [15] E. Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [16] I. Caragiannis, N. Gravin, and X. Huang.  Envy-freeness up to any item with high Nash welfare: The virtue of donating items.  In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 527–545, 2019.
  * [17] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang.  The unreasonable fairness of maximum Nash welfare.  In Proceedings of the 17th ACM Conference on Economics and Computation (EC), pages 305–322, 2016.
  * [18] B. R. Chaudhury, J. Garg, and K. Mehlhorn.  EFX exists for three agents.  In EC, pages 1–19. ACM, 2020.
  * [19] B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa.  A little charity guarantees almost envy-freeness.  In Proceedings of the 31st Symposium on Discrete Algorithms (SODA), pages 2658–2672, 2020.
  * [20] R. Cole and V. Gkatzelis.  Approximating the Nash social welfare with indivisible items.  SIAM J. Comput., 47(3):1211–1236, 2018.
  * [21] D. Conlon and A. Ferber.  Lower bounds for multicolor ramsey numbers.  Advances in Mathematics, 378:107528, 2021.
  * [22] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [23] A. Darmann and J. Schauer.  Maximizing nash product social welfare in allocating indivisible goods.  SSRN Electronic Journal, 247, 2014.
  * [24] R. Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [25] P. Erdös and G. Szekeres.  A combinatorial problem in geometry.  Compositio mathematica, 2:463–470, 1935.
  * [26] J. Garg, P. McGlaughlin, and S. Taki.  Approximating maximin share allocations.  In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA), volume 69, pages 20:1–20:11, 2019.
  * [27] J. Garg and S. Taki.  An improved approximation algorithm for maximin shares.  CoRR, abs/1903.00029, 2019.
  * [28] M. Ghodsi, M. T. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami.  Fair allocation of indivisible goods: Improvements and generalizations.  In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 539–556, 2018.
  * [29] D. Kurokawa, A. D. Procaccia, and J. Wang.  Fair enough: Guaranteeing approximate maximin shares.  Journal of ACM, 65(2):8:1–27, 2018.
  * [30] H. Lefmann.  A note on ramsey numbers.  Studia Sci. Math. Hungar, 22(1-4):445–446, 1987.
  * [31] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi.  On approximately fair allocations of indivisible goods.  In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004.
  * [32] P. Manurangsi and W. Suksompong.  Closing gaps in asymptotic fair division.  CoRR, abs/2004.05563, 2020.
  * [33] H. Moulin.  Fair division in the internet age.  Annual Review of Economics, 11(1):407–441, 2019.
  * [34] M. Naor, L. J. Schulman, and A. Srinivasan.  Splitters and near-optimal derandomization.  In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 182–191. IEEE, 1995.
  * [35] B. Plaut and T. Roughgarden.  Almost envy-freeness with general valuations.  In Proceedings of the 29th Symposium on Discrete Algorithms (SODA), pages 2584–2603, 2018.
  * [36] A. D. Procaccia.  Technical perspective: An answer to fair division’s most enigmatic question.  Commun. ACM, 63(4):118, Mar. 2020.
  * [37] A. D. Procaccia.  Technical perspective: An answer to fair division’s most enigmatic question.  Commun. ACM, 63(4):118, Mar. 2020.
  * [38] H. Steinhaus.  The problem of fair division.  Econometrica, 16(1):101–104, 1948.