hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS
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. Towards resolving this problem, many
impressive results show the existence of its relaxations, e.g., the existence
of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated
goods. The latter result was recently improved for three agents, in which the
two unallocated goods are allocated through an involved procedure. Reducing the
number of unallocated goods for 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 $R(\cdot)$. For all $d
\in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite
digraph $G =(\cup_{i \in [k]} V_i, E)$, in which
1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for
all $i \in [k]$,
2) 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
3) there exists no cycle in $G$ that contains at most one vertex from each
part.
We show that any upper bound on $R(d)$ directly translates to a sublinear
bound on the number of unallocated goods. We establish a polynomial upper bound
on $R(d)$, yielding our main result. Furthermore, our approach is constructive,
which also gives a polynomial-time algorithm for finding such an allocation.
