# Epistemic EFX Allocations Exist for Monotone Valuations

Hannaneh Akrami
Max Planck Institute for Informatics
Graduiertenschule Informatik, Universität des Saarlandes
<EMAIL_ADDRESS>
Nidhi Rathi
Max Planck Institute for Informatics
<EMAIL_ADDRESS>
###### Abstract

We study the fundamental problem of _fairly_ dividing a set of indivisible
items among agents with (general) monotone valuations. The notion of _envy-
freeness up to any item_ ($\mathsf{EFX}$) is considered to be one of the most
fascinating fairness concepts in this line of work. Unfortunately, despite
significant efforts, existence of $\mathsf{EFX}$ allocations is a major open
problem in fair division, thereby making the study of approximations and
relaxations of $\mathsf{EFX}$ a natural line of research. Recently,
Caragiannis et al. (2023) introduced a promising relaxation of $\mathsf{EFX}$,
called _epistemic_ $\mathsf{EFX}$ ($\mathsf{EEFX}$). We say an allocation to
be $\mathsf{EEFX}$ if, for every agent, it is possible to shuffle the items in
the remaining bundles so that she becomes “$\mathsf{EFX}$-satisfied”.
Caragiannis et al. (2023) prove existence and polynomial-time computability of
$\mathsf{EEFX}$ allocations for additive valuations. A natural question asks
what happens when we consider valuations more general than additive?

We address this important open question and answer it affirmatively by
establishing the _existence_ of $\mathsf{EEFX}$ allocations for an arbitrary
number of agents with general _monotone_ valuations. To the best of our
knowledge, $\mathsf{EEFX}$ is the only known relaxation of $\mathsf{EFX}$ to
have such strong existential guarantees. Furthermore, we complement our
existential result by proving computational and information-theoretic lower
bounds. We prove that even for an arbitrary number of (more than one) agents
with identical submodular valuations, it is $\mathsf{PLS}$-hard to compute
$\mathsf{EEFX}$ allocations and it requires exponentially-many value queries
to do so.

##  1 Introduction

The theory of fair division addresses the fundamental problem dividing a set
of resources in a _fair_ manner among individuals (often called as agents)
with varied preferences. This problem arises naturally in many real-world
settings, such as division of inheritance, dissolution of business
partnerships, divorce settlements, assigning computational resources in a
cloud computing environment, course assignments, allocation of radio and
television spectrum, air traffic management, course assignments, to name a few
(Etkin et al., 2007; Moulin, 2004; Vossen, 2002; Budish and Cantillon, 2012;
Pratt and Zeckhauser, 1990). Although the roots of fair division can be found
in antiquity, for instance, in ancient Greek mythology and the Bible, its
first mathematical exposition dates back to the seminal work of Steinhaus,
Banach, and Knaster (Steinhaus, 1948). Since then, the theory of fair division
has received significant attention and a flourishing flow of research from
areas across economics, social science, mathematics, and computer science; see
Amanatidis et al. (2022); Brams and Taylor (1996); Brandt and Procaccia
(2016); Robertson and Webb (1998) for excellent expositions.

The development of fair division protocols plays a crucial role in ensuring
equitable outcomes in the design of many social institutions. With the advent
of internet, the necessity of having division rules that are both transparent
and agreeable or, in other words, _fair_ has become evident (Moulin, 2019).
There are many examples to see how the principles of fair division are being
applied in various technological platforms today (Adj, ; spl, ).

Table 1: The additive valuation functions of $3$ agents for $7$ goods. | $g_{1}$ | $g_{2}$ | $g_{3}$ | $g_{4}$ | $g_{5}$ | $g_{6}$ | $g_{7}$
---|---|---|---|---|---|---|---
$v_{1}$ | $100$ | $100$ | $100$ | $1$ | $1$ | $1$ | $1$
$v_{2}$ | $1$ | $1$ | $1$ | $100$ | $100$ | $100$ | $1$
$v_{3}$ | $1$ | $50$ | $50$ | $1$ | $1$ | $1$ | $55$

Some of the central solution concepts and axiomatic characterizations in the
fair-division literature stem from the cake-cutting context (Moulin, 2004)
where the resource to be divided is considered to be a (divisible) cake
$[0,1]$. The quintessential notion of fairness— _envy-freeness_ —was also
mathematically formalized in this setup (Foley, 1967; Varian, 1973). We say an
allocation is envy-free if every agent prefers their share in the division at
least as much as any other agent’s share. Strong existential guarantees of
envy-free cake division that also establishes a connection with topology
(Stromquist, 1980; Su, 1999), has undeniably made envy-freeness as the
representative notion of fairness in resource-allocation settings.
Unfortunately, an envy-free allocation is not guaranteed to exist when we need
to fairly divide a set of indivisible items: consider two agents and a single
item: only one agent can get the item, and the other player will be envious.
Furthermore, it is NP-hard to decide whether an envy-free allocation exists
e.g., see Bouveret and Lemaître (2016). Infeasibility along-with high
computational complexity of envy-free allocations has led to study of its
various relaxations for discrete setting.

In this paper, we consider the setting where the resource is a set of discrete
or indivisible items, each of which must be wholly allocated to a single
agent. A fair division instance consists of a set
$\mathcal{N}=\\{1,2\dots,n\\}$ of $n$ agents and a set $\mathcal{M}$ of items.
Every agent $i$ specifies her preferences via a valuation function
$v_{i}\colon 2^{\mathcal{M}}\to\mathbb{R}$. We study general _monotone
valuations_ that pertains adding a good to a bundle cannot make it worse. The
goal is to find a partition $X=(X_{1},\dots,X_{n})$ of the items where every
agent $i\in\mathcal{N}$ upon receiving bundle $X_{i}$ considers $X$ to be
fair.

Envy-freeness up to any item ($\mathsf{EFX}$): One of the most compelling
notions of fairness for discrete setting is _envy-freeness up to any item_
($\mathsf{EFX}$). This notion was introduced by Caragiannis et al. (2016). We
say an allocation is $\mathsf{EFX}$ if every agent prefers her own bundle to
the bundle of any other agent, after removing _any_ item from the latter.
$\mathsf{EFX}$ is considered to be the “closest analogue of envy-freeness” for
discrete setting (Caragiannis et al., 2019). Unfortunately, despite
significant efforts over the past few years, existence of $\mathsf{EFX}$
allocations remain as the biggest and the most challenging open problem in
fair division, even for instances with more than three agents with additive
valuations (Procaccia, 2020). .

Epistemic envy-freeness up to any item ($\mathsf{EEFX}$): A recent work of
Caragiannis et al. (2023) introduced a promising relaxation of $\mathsf{EFX}$,
called as _epistemic_ $\mathsf{EFX}$. We call an allocation $X$ as
$\mathsf{EEFX}$ if for every agent $i\in[n]$, there exists an allocation $Y$
such that $Y_{i}=X_{i}$ and for every bundle $Y_{j}\in Y$, we have
$v_{i}(X_{i})\geq v_{i}(Y_{j}\setminus g)$ for every $g\in Y_{j}$. That is, an
allocation is $\mathsf{EEFX}$ if, for every agent, it is possible to shuffle
the items in the remaining bundles so that she becomes
“$\mathsf{EFX}$-_satisfied_ ”. See Example 1.1 for a better intuition.

######  Example 1.1.

Consider a fair division instance consisting of $7$ items and $3$ agents with
additive valuations as described in Table 1. Now consider the allocation $X$
where $X_{1}=\\{g_{1},g_{2},g_{4}\\},X_{2}=\\{g_{3},g_{5},g_{6}\\},$ and
$X_{3}=\\{g_{7}\\}$. Note that $X$ is envy-free, and hence, $\mathsf{EFX}$ and
$\mathsf{EEFX}$. Now assume that agent $1$ and $2$ exchange the items $g_{3}$
and $g_{4}$. Formally, let
$Y=(\\{g_{1},g_{2},g_{3}\\},\\{g_{4},g_{5},g_{6}\\},\\{g_{7}\\})$. For
$i\in\\{1,2\\}$, have $v_{i}(Y_{i})=300>201=v_{i}(X_{i})$, and
$v_{3}(Y_{3})=v_{3}(X_{3})$. Therefore, intuitively it seems that $Y$ is a
better allocation compared to $X$ since agents $1$ and $2$ are strictly better
off and agent $3$ is as happy as before (i.e., $Y$ Pareto dominates $X$).
However, note that while allocation $Y$ is still $\mathsf{EEFX}$, it is not
$\mathsf{EFX}$. Namely, agent $3$ strongly envies agent $1$:
$v_{3}(Y_{1}\setminus\\{g_{1}\\})=100>55=v_{3}(Y_{3})$.

Caragiannis et al. (2023) establish existence and polynomial-time
computability of $\mathsf{EEFX}$ allocations for an arbitrary number of agents
with a restricted class of _additive_ valuations. Thus, the following question
naturally arises:

Do $\mathsf{EEFX}$ allocations exist for an arbitrary number of agents with
general monotone valuations?

###  1.1 Our Results

We answer the above question in the affirmative and establish computational
hardness and information-theoretic lower bounds for finding $\mathsf{EEFX}$
allocations:

  1. 1.

$\mathsf{EEFX}$ allocations are guaranteed to _exist_ for any fair division
instance with an arbitrary number of agents having general _monotone_
valuations; see Theorem 3.5.

  2. 2.

An exponential number of valuation queries is required by any deterministic
algorithm to compute an $\mathsf{EEFX}$ allocation for fair division instances
with an arbitrary number of agents with identical submodular valuations; see
Theorem 4.7.

  3. 3.

The problem of computing $\mathsf{EEFX}$ allocations for fair division
instances with an arbitrary number of agents having identical submodular
valuations is $\mathsf{PLS}$-hard; see Theorem 4.8.

It is relevant to note that, with the above results, the notion of
epsitemic-$\mathsf{EFX}$ becomes the _first_ known relaxation of
$\mathsf{EFX}$ (and hence envy-freeness) that admits such strong existential
guarantees. Along-with its hardness results, the notion of $\mathsf{EEFX}$ for
discrete settings seem to enjoy results of _similar_ flavor as that of envy-
freeness for cake division (Stromquist, 1980, 2008; Deng et al., 2012).

Similar computational hardness and information-theoretic lower bounds are
known for computing an $\mathsf{EFX}$ allocation between two agents with
identical submodular valuations; see Plaut and Roughgarden (2020) and Goldberg
et al. (2023). We reduce our problem of computing an $\mathsf{EEFX}$
allocation among an arbitrary number of agents with identical submodular
valuations to the above computational problem for $\mathsf{EFX}$. See Appendix
B for further discussion on the $\mathsf{PLS}$ class (Johnson et al., 1988).

Therefore, note that, similar computational hardness and information-theoretic
bounds hold true for finding $\mathsf{EFX}$ and $\mathsf{EEFX}$ allocations.
But, our work has proved a _stark contrast_ to $\mathsf{EFX}$ by establishing
guaranteed existence of $\mathsf{EEFX}$ allocations for an arbitrary number of
agents with monotone valuations, whereas existence of $\mathsf{EFX}$
allocations for more than three agents even with additive valuations remain a
major open problem.

###  1.2 Our Techniques

We develop a novel technique to prove existence of $\mathsf{EEFX}$ allocations
for monotone valuations. In this section, we describe our technique in
generality since which we believe it could be employed in other (fair
division) problems as well.

Consider a fair division instance111A fair division instance
$\mathcal{I}=(\mathcal{N},\mathcal{M},\mathcal{V})$ consists of a set
$\mathcal{N}$ of $n$ agents and a set $\mathcal{V}$ consisting of agent-
valuations over a set $\mathcal{M}$ of items.
$\mathcal{I}=(\mathcal{N},\mathcal{M},\mathcal{V})$ and a _desirable property_
$\mathcal{P}$ of a bundle $B\subseteq\mathcal{M}$ for an agent
$i\in\mathcal{N}$. For example, in this work, we consider the fairness
property of whether $B$ is $n$-_epistemic_ -$\mathsf{EFX}$ for an agent $i$
(see Definition 2.3). We say $B$ is _desirable_ to $i$ when $B$ satisfies the
property $\mathcal{P}$ for agent $i$. The goal is to find an allocation
$A=(A_{1},\ldots,A_{n})$ such that $A_{i}$ is desirable to each agent
$i\in\mathcal{N}$; we call such an allocation as desirable.

For any partitioning of the items into $n$ bundles $X_{1},X_{2},\ldots,X_{n}$,
let us consider a bipartite graph $G(X)$ with one side representing the $n$
agents and the other side representing the $n$ bundles. There exists an edge
$(i,j)$ between (the node corresponding to) agent $i$ and (the node
corresponding to) bundle $X_{j}$, if and only if, bundle $X_{j}$ is
_desirable_ to agent $i$. For any subset of the nodes $S\subseteq\mathcal{N}$,
let us write $N(S)$ to denote the set of all neighbours of $S$ in $G(X)$.

Note that, if $G(X)$ has a perfect matching, then this matching translates to
a _desirable_ allocation in $\mathcal{I}$. Therefore, let us assume that
$G(X)$ does not admit a perfect matching and hence admits a Hall’s violator
set. That is, there exists a subset of agents $\\{a_{1},\ldots,a_{t+1}\\}$ for
which $N(\\{a_{1},\ldots,a_{t+1}\\})\leq t$. But also, there exists a subset
of bundles $\\{X_{j_{1}},\ldots,X_{j_{k+1}}\\}$ for which
$N(\\{X_{j_{1}},\ldots,X_{j_{k+1}}\\})\leq k$. Let us assume that
$\\{X_{j_{1}},\ldots,X_{j_{k+1}}\\}$ is minimal. If $k\geq 1$, this means that
we can find a non-empty matching of
$((i_{1},X_{j_{1}}),\ldots,(i_{k},X_{j_{k}}))$ such that there exists no edge
between agent $i\in\mathcal{N}\setminus\\{i_{1},\ldots,i_{k}\\}$ and bundles
$X_{j_{1}},\ldots,X_{j_{k+1}}$. In other words, for all $\ell\in[k]$,
$X_{j_{\ell}}$ is desirable to $i_{\ell}$ and is not desirable to any
$i\notin\\{i_{1},\ldots,i_{k}\\}$.

After finding such a matching, it is intuitive to allocate $X_{j_{\ell}}$ to
$i_{\ell}$ for $\ell\in[k]$ and then recursively find a desired allocation of
the remaining goods to the remaining agents. In order to do so, we need to
ensure two important conditions.

  1. 1.

We can find a non-empty matching
$((i_{1},X_{j_{1}}),\ldots,(i_{k},X_{j_{k}}))$ in each step.

  2. 2.

After removing $\\{X_{j_{1}},\ldots,X_{j_{k}}\\}$ from $\mathcal{M}$, we can
still find desirable bundles (with respect to the original instance) for the
remaining agents.

Whether ensuring these conditions is possible or not, depends on the property
$P$. In this work, we prove this approach works when the property $P$ is
$n$-epistemic-$\mathsf{EFX}$, and thereby proving the existence of
$\mathsf{EEFX}$ allocations for monotone valuations.

Although these two conditions might seem inconsequential, we prove that a
stronger condition can simultaneously imply both of them. Namely, we only need
to prove that at each step with $n^{\prime}$ remaining agents, for any
remaining agent $i$, we can partition the remaining items into $n^{\prime}$
many bundles $X_{1},\ldots,X_{n^{\prime}}$ such that $X_{j}$ is desirable to
$i$ for all $j\in[n^{\prime}]$. This way, at each step, we can ask one of the
remaining agents to partition the remaining goods into $n^{\prime}$ many
desirable bundles with respect to her own valuation. Then, we either find a
perfect matching, or we find a non-empty matching and reduce the size of the
instance.

###  1.3 Further Related Work

Plaut and Roughgarden (2020) proved the existence of $\mathsf{EFX}$ for two
agents with monotone valuations. For three agents, a series of works proved
the existence of $\mathsf{EFX}$ allocations when agents have additive
valuations (Chaudhury et al., 2020), _nice-cancelable_ valuations (Berger et
al., 2022), and finally when two agents have monotone valuations and one has
an _$\mathsf{MMS}$ -feasible_ valuation (Akrami et al., 2023a). $\mathsf{EFX}$
allocations exist when agents have identical (Plaut and Roughgarden, 2020),
binary (Halpern et al., 2020), or bi-valued (Amanatidis et al., 2021)
valuations. Several approximations (Chaudhury et al., 2021; Amanatidis et al.,
2020; Chan et al., 2019; Farhadi et al., 2021) and relaxations (Amanatidis et
al., 2021; Caragiannis et al., 2019; Berger et al., 2022; Mahara, 2021; Jahan
et al., 2023; Berendsohn et al., 2022; Akrami et al., 2022) of $\mathsf{EFX}$
have become an important line of research in discrete fair division.

Another relaxation of envy-freeness proposed in discrete fair division
literature is that of envy-freeness up to some item ($\mathsf{EF}$1),
introduced by Budish (2011). It requires that each agent prefers her own
bundle to the bundle of any other agent, after removing some item from the
latter. $\mathsf{EF}$1 allocations always exist and can be computed
efficiently (Lipton et al., 2004).

_Proportionality_ (Dubins and Spanier, 1961; Steinhaus, 1948) is another well-
studied notion of fairness having its roots in cake division literature. We
say an allocation is proportional if each agent gets a bundle of items for
which her value exceeds her total value for all items divided by the number of
agents. It is easy to see that a proportional division cannot exist for the
setting of discrete items.

Among the relaxations of proportionality, the one that has received the lion’s
share of attention uses the so-called maximin fair share ($\mathsf{MMS}$),
i.e., the maximum value an agent can attain in any allocation where she is
assigned her least preferred bundle, as threshold. Surprisingly, Kurokawa et
al. (2016) proved that $\mathsf{MMS}$ allocations may not always exist. Since
then, research has focused on computing allocations that approximate
$\mathsf{MMS}$; e.g., see Amanatidis et al. (2017); Kurokawa et al. (2018);
Ghodsi et al. (2018); Barman and Krishnamurthy (2020); Garg and Taki (2020);
Feige et al. (2021); Akrami et al. (2023b); Akrami and Garg (2024) for
additive, Barman and Krishnamurthy (2020); Ghodsi et al. (2018); Uziahu and
Feige (2023) for submodular, Ghodsi et al. (2018); Seddighin and Seddighin
(2022); Akrami et al. (2023c) for XOS, and Ghodsi et al. (2018); Seddighin and
Seddighin (2022) for subadditive valuations.

Proportionality up to one good (PROP1) (Conitzer et al., 2017) is another
relaxation of proportionality which can be guaranteed together with Pareto
optimality (Barman and Krishnamurthy, 2019). Proportionality up to any good
(PROPX) on the other hand, is not a feasible notion in the goods setting (Aziz
et al., 2020).

An excellent recent survey by Amanatidis et al. (2022) discusses the above
fairness concepts and many more. Another aspect of discrete fair division
which has garnered an extensive research is when the items that needs to be
divided are _chores_. We refer the readers to the survey by Guo et al. (2023)
for a comprehensive discussion.

###  1.4 Organization:

We begin by discussing the preliminaries in Section 2. We prove our key result
of guaranteed existence of $\mathsf{EEFX}$ allocations for monotone valuations
in Section 3. We conclude by proving information/theoretic lower bounds for
computing an $\mathsf{EEFX}$ allocation in Section 4. Towards the end, we
discuss a list of many interesting open problems motivated by this work in
Section 5.

##  2 Definitions and Notation

For any positive integer $k$, we use $[k]$ to denote the set
$\\{1,2,\ldots,k\\}$. We denote a fair division instance by
$\mathcal{I}=(\mathcal{N},\mathcal{M},\mathcal{V})$, where $\mathcal{N}=[n]$
is a set of $n$ agents, $\mathcal{M}$ is a set of $m$ items and
$\mathcal{V}=(v_{1},v_{2},\ldots,v_{n})$ is a vector of valuation functions.
For any agent $i\in\mathcal{N}$, we write
$v_{i}:2^{\mathcal{M}}\rightarrow\mathbb{R}_{\geq 0}$ to denote her valuation
function over the set of items. For all $i\in\mathcal{N}$, we assume $v_{i}$
is normalized; i.e., $v_{i}(\emptyset)=0$, and _monotone_ ; i.e., for all
$i\in\mathcal{N}$, $g\in\mathcal{M}$ and $S\subset\mathcal{M}$,
$v_{i}(S\cup\\{g\\})\geq v_{i}(S)$. Moreover, we say a valuation function $v$
is submodular if for all subsets $S,T\subseteq\mathcal{M}$, we have $v(S\cap
T)+v(S\cup T)\leq v(S)+v(T)$ and we say $v$ is additive when $v(S)=\sum_{g\in
S}v(g)$ for all subsets $S\subseteq\mathcal{M}$. Note that, monotone
valuations are submodular and additive, making them the most general class of
valuations.

For simplicity, we sometimes use $g$ instead of $\\{g\\}$ to denote an item
$g\in\mathcal{M}$. We use “items” and “goods” interchangeably.

An allocation $X=(X_{1},X_{2},\ldots,X_{n})$ of the items among agents is a
partition of items into $n$ bundles such that bundle $X_{i}$ is allocated to
agent $i$. That is, we have $X_{i}\cap X_{j}=\emptyset$ for all
$i,j\in\mathcal{N}$ and $\cup_{i\in[n]}X_{i}=\mathcal{M}$.

Let us now define the concept of _strong envy_ that characterizes one of most
compelling notions of fairness in the literature - _envy-freeness up to any
item_ ($\mathsf{EFX}$).

######  Definition 2.1 (Strong Envy).

For a fair division instance, we say an agent $i$ upon receiving a bundle
$A\subseteq\mathcal{M}$ _strongly envies_ a bundle $B\in\mathcal{M}$, if there
exists an item $g\in B$ such that $v_{i}(A)<v_{i}(B\setminus g)$. Under an
allocation $X$, we say agent $i$ _strongly envies_ agent $j$, if upon
receiving $X_{i}$, agent $i$ strongly envies the bundle $X_{j}$.

######  Definition 2.2 ($\mathsf{EFX}$).

For a fair division instance, an allocation $X=(X_{1},X_{2},\ldots,X_{n})$ is
said to be “ _envy-free up to any item_ ” or “$\mathsf{EFX}$”, if no agent
strongly envies another agent. i.e., for all agents $i$ and $j$,
$v_{i}(X_{i})\geq v_{i}(X_{j}\setminus g)$ for all $g\in X_{j}$.

Recently, Caragiannis et al. (2023) introduced a promising new notion of
fairness — _epistemic $\mathsf{EFX}$_ – by relaxing $\mathsf{EFX}$, that we
define next. They proved _epistemic $\mathsf{EFX}$_ allocations among an
arbitrary number of agents with additive valuations can be computed in
polynomial time.

######  Definition 2.3.

For any integer $k$, agent $i\in[n]$ and subset of items
$S\subseteq\mathcal{M}$, we say that a bundle $A\in S$ is “$k$_-epistemic-
$\mathsf{EFX}$_” for $i$ with respect to $S$, if there exists a partitioning
of $S\setminus A$ into $k-1$ bundles $C_{1},C_{2},\ldots,C_{k-1}$, such that
for all $j\in[k-1]$, upon receiving $A$, $i$ would not strongly envy $C_{j}$.
We call $C=\\{C_{1},C_{2},\ldots,C_{k-1}\\}$ a “$k$_-certificate_ ” of $A$ for
$i$ under $S$. Also we define

$\displaystyle\mathsf{EEFX}^{k}_{i}(S)=\\{\text{$A\subseteq S\ |\ A$ is
``$k$-epistemic-$\mathsf{EFX}$'' for agent $i$ with respect to }S\\}.$

######  Definition 2.4 ($\mathsf{EEFX}$).

For a fair division instance, an allocation $X=(X_{1},X_{2},\ldots,X_{n})$ is
said to be _epistemic $\mathsf{EFX}$_ or _$\mathsf{EEFX}$_ if for all agents
$i$, $X_{i}\in\mathsf{EEFX}^{n}_{i}(\mathcal{M})$.

Note that the set of $\mathsf{EFX}$ and $\mathsf{EEFX}$ allocations coincide
for the case of two agents. Next, we define a notion of
$\mathsf{EEFX}$_-graph_ that plays a crucial role in proving the existence of
$\mathsf{EEFX}$ allocations.

######  Definition 2.5.

For a fair division instance, consider a partition of $\mathcal{M}$ into $n$
bundles $Y_{1},\ldots,Y_{n}$. We define the $\mathsf{EEFX}$_-graph_ as an
undirected bipartite graph $G=(V,E)$, where $V$ has one part consisting of $n$
nodes corresponding to the agents and another part with $n$ nodes
corresponding to the bundles $Y_{1},\ldots,Y_{n}$. There exists an edge
$(i,j)$ between (the node corresponding to) agent $i$ and (the node
corresponding to) bundle $Y_{j}$ if and only if
$Y_{j}\in\mathsf{EEFX}^{n}_{i}(\mathcal{M})$.

We abuse the notation and refer to the “nodes corresponding to agents” as
“agents” and also refer to the “nodes corresponding to bundles” as “bundles”.
For any subsets $V$ of nodes, $N(V)$ is the set of all neighbors of the nodes
in $V$. For a matching $M$, $V(M)$ is the set of vertices of $M$.

##  3 Existence of Epistemic EFX Allocations

In this section, we prove our main result that establishes existence of
$\mathsf{EEFX}$ allocations for any fair division instance with $n$ agents
having monotone valuations. We start by proving an important structural
property (in Lemma 3.1) that enables us to reduce an instance with lower
number of agents.

######  Lemma 3.1.

For any fair division instance, consider an agent $i\in\mathcal{N}$ and
$A\subseteq\mathcal{M}$ such that $A\notin\mathsf{EEFX}^{n}_{i}(\mathcal{M})$.
Then for all bundles $B\in\mathsf{EEFX}^{n-1}_{i}(\mathcal{M}\setminus A)$, we
must have $B\in\mathsf{EEFX}^{n}_{i}(\mathcal{M})$.

###### Proof.

For an agent $i\in\mathcal{N}$, let us assume that bundle
$A\subseteq\mathcal{M}$ is such that
$A\notin\mathsf{EEFX}^{n}_{i}(\mathcal{M})$. Now, consider any bundle
$B\in\mathsf{EEFX}^{n-1}_{i}(\mathcal{M}\setminus A)$, i.e., there exists an
$(n-1)$-certificate of $B$ for $i$ under $\mathcal{M}\setminus A$, we call it
$C=\\{C_{1},\ldots,C_{n-2}\\}$. By definition, we have that

$\displaystyle v_{i}(B)\geq v_{i}(C_{j}\setminus g)\ \text{for all}\
j\in[n-2]\ \text{and}\ g\in C_{j}$ (1)

If $v_{i}(A)\geq v_{i}(B)$, then combining it with equation (1), we obtain
$\\{B,C_{1},\ldots,C_{n-2}\\}$ is an $n$-certificate of $A$ for $i$ under
$\mathcal{M}$ and $A\in\mathsf{EEFX}^{n}_{i}(\mathcal{M})$, leading to a
contradiction. Hence, we must have

$\displaystyle v_{i}(B)\geq v_{i}(A)$ (2)

Finally, combining equations (1) and (2), we obtain
$\\{A,C_{1},\ldots,C_{n-2}\\}$ is an $n$-certificate of $B$ for $i$ under
$\mathcal{M}$ and $B\in\mathsf{EEFX}^{n}_{i}(\mathcal{M})$. This completes our
proof. ∎

Lemma 3.1 implies that if an agent $i$ finds a bundle $A$ to be
$n$-epistemic-$\mathsf{EFX}$ while no other agent finds $A$ to be
$n$-epistemic-$\mathsf{EFX}$, we can safely allocate $A$ to $i$, and remove
$i$ and $A$ from the instance and find an $\mathsf{EEFX}$ allocation of
$\mathcal{M}\setminus A$ to the remaining $n-1$ agents. Note that we can
repeat this process iteratively and remove $t\geq 1$ agents and $t$ bundles.
The formal description is given in Corollary 3.2.

######  Corollary 3.2 (of Lemma 3.1).

For a fair division instance, consider a partial allocation
$(X_{k+1},X_{k+2},\dots,X_{n})$ to agents in the set $[n]\setminus[k]$. Let us
assume that for all agents $i\in[n]\setminus[k]$ and all $j\in[k]$, we have
$X_{i}\in\mathsf{EEFX}^{n}_{i}$, $X_{i}\notin\mathsf{EEFX}^{n}_{j}$. If
$(X_{1},\ldots,X_{k})$ is an $\mathsf{EEFX}$ allocation of
$\mathcal{M}\setminus\bigcup_{\ell\in[k]}X_{\ell}$ for agents in $[k]$, then
$(X_{1},X_{2},\ldots,X_{n})$ is an $\mathsf{EEFX}$ allocation for agents in
$[n]$.

Algorithm 1 $\mathsf{ALG}=\mathsf{EEFX}(\mathcal{I})$

Input: A fair division instance
$\mathcal{I}=(\mathcal{N},\mathcal{M},\mathcal{V})$ where agent
$i\in\mathcal{N}=[n]$ has monotone valuation $v_{i}$ over the set of items
$\mathcal{M}$
Output: An allocation $X=(X_{1},X_{2},\ldots,X_{n})$

1:if $\mathcal{N}=\emptyset$ then

2: return $\emptyset$;

3:$n\leftarrow|\mathcal{N}|$

4:$(X_{1},\ldots,X_{n})\leftarrow$ an $\mathsf{EFX}$ allocation of
$\mathcal{M}$ among $n$ agents with valuation $v_{n}$;

5:$G\leftarrow$ $\mathsf{EEFX}$-graph of $\\{X_{1},\ldots,X_{n}\\}$;

6:Let $M=\\{(k+1,X_{k+1}),\ldots,(n,X_{n})\\}$ be a matching of size at least
$1$ such that $N(\\{X_{k+1},\ldots,X_{n}\\})=\\{k+1,\ldots,n\\}$;

7:$\mathcal{N}^{\prime}\leftarrow[k]$;

8:$\mathcal{M}^{\prime}\leftarrow\mathcal{M}\setminus\bigcup_{\ell\in[n]\setminus[k]}X_{\ell}$;

9:$\mathcal{V}^{\prime}\leftarrow(V_{1},\ldots,V_{k})$;

10:$(X_{1},\ldots,X_{k})\leftarrow\mathsf{EEFX}(\mathcal{N}^{\prime},\mathcal{M}^{\prime},\mathcal{V}^{\prime})$;

11:return $(X_{1},X_{2},\ldots,X_{n})$;

We will now give a high-level overview of our constructive proof for
establishing the existence of $\mathsf{EEFX}$ allocation among arbitrary
number of agents with monotone valuations using $\mathsf{ALG}$ (see Algorithm
1). For a fair division instance
$\mathcal{I}=(\mathcal{N},\mathcal{M},\mathcal{V})$, our algorithm
$\mathsf{ALG}$, starts by considering an $\mathsf{EFX}$ allocation
$(X_{1},\dots,X_{n})$ of $\mathcal{M}$ among $n$ agents with valuation
$v_{n}$. We know such an allocation exists by the work of Plaut and
Roughgarden (2020). Next, we construct the $\mathsf{EEFX}$-graph $G$ between
the bundles $X_{1},\dots,X_{n}$ and the agents. Lemma 3.3 proves that there
will always exist a non-trivial matching222Without loss of generality, we can
rename the bundles and agents in the matching $M$
$M=\\{(k+1,X_{k+1}),\ldots,(n,X_{n})\\}$ such that
$N(\\{X_{k+1},\ldots,X_{n}\\})=\\{k+1,\ldots,n\\}$. That is, for every
$j\in[n]\setminus[k]$, bundle $X_{j}\in\mathsf{EEFX}^{n}_{j}(\mathcal{M})$.

Next, $\mathsf{ALG}$ reduces the instance by removing the agents
$\\{k+1,k+2,\dots,n\\}$ from $\mathcal{N}$ with their bundles
$X_{k+1},X_{k+2},\dots,X_{n}$ safely. Note that, no agent $i\in[k]$ has any
edge in $G$ to any bundle $X_{j}$ for $j\in[n]\setminus[k]$. Finally, this
also implies that finding an $\mathsf{EEFX}$ allocation
$(X_{1},X_{2},\dots,X_{k})$ in the reduced instance and combining it with
$(X_{k+1},X_{k+2},\dots,X_{n})$ leads to an overall $\mathsf{EEFX}$ allocation
in the original instance. That is, our technique enables us to reduce our
instance, find an $\mathsf{EEFX}$ allocation in the reduced instance, and
combine it in such a way that we produce an $\mathsf{EEFX}$ allocation the the
original instance.

Figure 1: If $G(X)$ does not admit a perfect matching, then there exists a
minimal subset $S=\\{X_{j_{1}},\ldots,X_{j_{k+1}}\\}$ of bundles such that
$|N(S)|<k+1$. Then, for all agent $i\in N(S)$ and all $\ell\in[k+1]$, no edge
between $X_{\ell}$ and $i$ exists. In other words, no such red dashed edges
can exist.

We begin by proving Lemma 3.3.

######  Lemma 3.3.

For any fair division instance, consider an agent $i\in\mathcal{N}$, let
$(X_{1},\ldots,X_{n})$ be an $\mathsf{EFX}$ allocation for an instance
consisting of $n$ agents with identical valuations $v_{i}$. Let $G$ be the
$\mathsf{EEFX}$-graph with $n$ agents and $n$ bundles $X_{1},\ldots,X_{n}$.
Then there always exists a matching
$M=\\{(i_{1},X_{j_{1}}),\ldots,(i_{k},X_{j_{k}})\\}$ of size at least $1$,
such that $N(\\{X_{j_{1}},\ldots,X_{j_{k}}\\})=\\{i_{1},\ldots,i_{k}\\}$.

###### Proof.

To begin with, if $G$ has a perfect matching
$M=\\{(i_{1},X_{j_{1}}),\ldots,(i_{n},X_{j_{n}})\\}$, then the lemma trivially
holds true since $\mathcal{N}\setminus\\{i_{1},\ldots,i_{n}\\}=\emptyset$.

Therefore, let us assume that no perfect matching exists in $G$. This implies
that the Hall’s condition is not satisfied, i.e., there exists a subset
$S=\\{X_{j_{1}},\ldots,X_{j_{k+1}}\\}$ of bundles such that
$|N(\\{X_{j_{1}},\ldots,X_{j_{k+1}}\\})|<k+1$. See Figure 1 for a better
intuition. We assume that the subset $S=\\{X_{j_{1}},\ldots,X_{j_{k+1}}\\}$ is
minimal. That is, for all $S^{\prime}\subsetneq S$, we have
$N(S^{\prime})\geq|S^{\prime}|$. Now consider
$T=\\{X_{j_{1}},\ldots,X_{j_{k}}\\}\subsetneq S$. By minimality of $S$, we
know that Hall’s condition holds for $T$, i.e., there exists a perfect
matching, say $M=\\{(i_{1},X_{j_{1}}),\ldots,(i_{k},X_{j_{k}})\\}$ between the
nodes in $T$ and $N(T)$. Since $|N(S)|<k+1$ and
$\\{i_{1},\ldots,i_{k}\\}\subseteq N(T)\subseteq N(S)$, it follows that
$N(S)=N(T)=\\{i_{1},\ldots,i_{k}\\}$.

Note that since $(X_{1},\dots,X_{n})$ is an $\mathsf{EFX}$ allocation for an
instance with identical valuations $v_{i}$, we know that $i\in N(S)$, thus
$k\geq 1$. Hence, $M=\\{(i_{1},X_{j_{1}}),\ldots,(i_{k},X_{j_{k}})\\}$ is a
matching of size $k\geq 1$, such that
$N(\\{X_{j_{1}},\ldots,X_{j_{k}}\\})=\\{i_{1},\ldots,i_{k}\\}$. The stated
claim stands proven. ∎

######  Theorem 3.4 (Plaut and Roughgarden (2020)).

When agents have identical monotone valuations, there always exists an
$\mathsf{EFX}$ allocation.

We are now ready to discuss our main result that constructively establishes
the existence of $\mathsf{EEFX}$ allocation among arbitrary number of agents
with monotone valuations using $\mathsf{ALG}$.

######  Theorem 3.5.

$\mathsf{EEFX}$ allocations exist for any fair division instance with monotone
valuations. In particular, $\mathsf{ALG}$ returns an $\mathsf{EEFX}$
allocation.

###### Proof.

We begin by proving that Algorithm 1 terminates. By Lemma 3.3, a matching
$M=\\{(i_{1},X_{i_{1}}),\ldots,(i_{t},X_{i_{t}})\\}$ of size at least $1$
exists such that
$N(\\{X_{i_{1}},\ldots,X_{i_{t}}\\})=\\{i_{1},\ldots,i_{t}\\}$. Note that we
can rename the bundles and the agents and without loss of generality assume
that the considered matching is $M=\\{(k+1,X_{k+1}),\ldots,(n,X_{n})\\}$.
Therefore, after removing $\\{k+1,\ldots,n\\}$ from $\mathcal{N}$, the size of
$\mathcal{N}$ decreases. Hence, the depth of the recursion is bounded by $n$
(the initial number of agents).

We prove the correctness of $\mathsf{ALG}$ by using induction on the number of
the agents. If $\mathcal{N}=\emptyset$, then $\emptyset$ is an $\mathsf{EEFX}$
allocation. We assume that $\mathsf{ALG}$ returns an $\mathsf{EEFX}$
allocation for any fair division instance with $n^{\prime}<n$ agents with
monotone valuations. Consider the matching $M$ described in $\mathsf{ALG}$. We
will show the output allocation of $\mathsf{ALG}$ for $n$ agents is
$\mathsf{EEFX}$ as well. For any $i\in[n]\setminus[k]$ and any $j\in[k]$, the
matching $M$ ensures that we have $X_{i}\in\mathsf{EEFX}^{n}_{i}$, and
$X_{i}\notin\mathsf{EEFX}^{n}_{j}$ (see Figure 1). By induction hypothesis
$(X_{1},\ldots,X_{k})$ is an $\mathsf{EEFX}$ allocation of
$\mathcal{M}\setminus\bigcup_{\ell\in[k]}X_{\ell}$ for agents in $[k]$. Thus,
by Corollary 3.2, $(X_{1},X_{2},\ldots,X_{n})$ is an $\mathsf{EEFX}$
allocation for agents in $[n]$. ∎

######  Remark 3.6.

All proofs of this section that we have for the setting when items are goods
easily extend to the setting when these items are ‘ _chores_ ’. Formally, when
agent valuations are monotonically decreasing, then EEFX allocations are
guaranteed to exist for an arbitrary number of agents.

##  4 Hardness Results

In this section, we complement our existential result of $\mathsf{EEFX}$
allocations for monotone valuations by proving computational and information-
theoretic lower bounds for finding an $\mathsf{EEFX}$ allocation. When agents
have submodular valuation functions, the way to compute the value $v(S)$ for a
subset $S$ of the items is through making value queries. Plaut and Roughgarden
(2020) proved that exponentially many value queries are required to compute an
$\mathsf{EFX}$ allocation _even_ for two agents with identical submodular
valuations. Formally, they proved the following information-theoretic lower
bounds.

######  Theorem 4.1 (Plaut and Roughgarden (2020)).

The query complexity of finding an $\mathsf{EFX}$ allocation with
$|\mathcal{M}|=2k+1$ many items is $\Omega(\frac{1}{k}{2k+1\choose k})$, even
for two agents with identical submodular valuations.

Moreover, Goldberg et al. (2023) proved the following computational hardness
for $\mathsf{EFX}$ allocations.

######  Theorem 4.2 (Goldberg et al. (2023)).

The problem of computing an $\mathsf{EFX}$ allocation for two agents with
identical submodular valuations is $\mathsf{PLS}$-complete.

Let us now define the computational problems corresponding to finding
$\mathsf{EFX}$ and $\mathsf{EEFX}$ allocations.

######  Definition 4.3.

($\mathsf{ID\text{-}EFX}$) Given a fair division instance
$\mathcal{I}=([2],\mathcal{M},(v,v))$ with two agents having identical
submodular valuations $v$, find an $\mathsf{EFX}$ allocation.

######  Definition 4.4.

($\mathsf{ID\text{-}EEFX}$) Given a fair division instance
$\mathcal{I}=([n],\mathcal{M},(v,\dots,v))$ with $n$ agents having identical
submodular valuations $v$, find an $\mathsf{EEFX}$ allocation.

We reduce the problem of finding an $\mathsf{EFX}$ allocation for two agents
with identical submodular valuations ($\mathsf{ID\text{-}EFX}$) to finding an
$\mathsf{EEFX}$ allocation for an arbitrary number of agents with identical
submodular valuations ($\mathsf{ID\text{-}EEFX}$), thereby establishing
similar hardness results for the latter.

Our Reduction: Consider an arbitrary instance
$\mathcal{I}=([2],\mathcal{M},(v,v))$ of $\mathsf{ID\text{-}EFX}$ with two
agents having identical submodular valuations $v$. Let
$\mathcal{I}^{\prime}=([n],\mathcal{M}^{\prime},(v^{\prime},\ldots,v^{\prime})\\})$
be an instance of $\mathsf{ID\text{-}EEFX}$ with $n$ agents having identical
valuations $v^{\prime}$ over the set of items
$\mathcal{M}^{\prime}=\mathcal{M}\cup\\{h_{1},\ldots,h_{n-2}\\}$. We define
the valuation $v$ as follows.

  * •

For all $S\subseteq\mathcal{M}$, $v^{\prime}(S)=v(S)$.

  * •

For all $j\in[n-2]$, $v^{\prime}(h_{j})=2v(\mathcal{M})+1$.

  * •

For all $j\in[n-2]$ and $S\subseteq\mathcal{M}^{\prime}\setminus\\{h_{j}\\}$,
$v^{\prime}(S\cup\\{h_{j}\\})=v(S)+v(h_{j})$.

We call items $h_{1},\ldots,h_{n-2}$ heavy items. Note that we can compute
$\mathcal{I}^{\prime}$ from $\mathcal{I}$ in polynomial time.

######  Lemma 4.5.

If $v$ is a submodular function, then $v^{\prime}$ is a submodular function as
well.

The proof is deferred to Appendix A.

######  Lemma 4.6.

Given any $\mathsf{EEFX}$ allocation $A$ in $\mathcal{I}^{\prime}$, we can
create an $\mathsf{EFX}$ allocation in $\mathcal{I}$ in polynomial time, where
$\mathcal{I}$ and $\mathcal{I}^{\prime}$ are as defined above.

###### Proof.

Let us assume that $A=(A_{1},\dots,A_{n})$ is an $\mathsf{EEFX}$ allocation in
instance $\mathcal{I}^{\prime}$. To begin with, note that there are $n-2$
heavy items in $\mathcal{I}^{\prime}$, and hence, by pigeonhole principle,
there exists at least two agents, say $i,j\in\mathcal{N}^{\prime}$ such that
they receive no heavy item under $A$. Without loss of generality, let us
assume that $i=1$ and $j=2$, and hence we have
$A_{1},A_{2}\subseteq\mathcal{M}$. This implies that we have

$\displaystyle
v^{\prime}(A_{1})=v(A_{1}),v^{\prime}(A_{2})=v(A_{2}),\text{and}\
v(A_{1}),v(A_{2})<2v(\mathcal{M})+1$ (3)

Without loss of generality, let us assume $v(A_{2})\geq v(A_{1})$.

We will prove $(A_{1},\mathcal{M}\setminus A_{1})$ forms an $\mathsf{EFX}$
allocation in $\mathcal{I}$. Note that valuations $v$ and $v^{\prime}$
coincide for the bundles $A_{1}$ and $\mathcal{M}\setminus A_{1}$. Since $A$
is $\mathsf{EEFX}$ in $\mathcal{I}^{\prime}$, let us denote the
$n$-certificate for agent $1$ with respect to $A_{1}$ by
$C=(C_{2},C_{3},\ldots,C_{n})$. First, we prove that no bundle $C_{k}$ with a
heavy item can have any other item as well. Assume otherwise. Let
$\\{g,h_{j}\\}\subseteq C_{k}$ for some $k\in\\{2,\ldots,n\\}$ and some
$j\in[n-2]$ and $g\neq h_{j}$. Then, we have

$\displaystyle v^{\prime}(C_{k}\setminus\\{g\\})\geq
v^{\prime}(h_{j})=2v(M)+1>v^{\prime}(A_{1})$

where, the last inequality uses equation (3). This implies that agent $1$
strongly envies bundle $C_{k}$ which is a contradiction to our assumption that
$C$ forms an $n$-certificate for bundle $A_{1}$ in instance $I^{\prime}$.
Therefore, the $n-1$ bundles in the $n$-certificate must look like
$\\{C_{2},\ldots,C_{n}\\}=\\{\\{h_{1}\\},\ldots,\\{h_{n-2}\\},\mathcal{M}\setminus
A_{1}\\}$. First, note that, agent $1$ with bundle $A_{1}$ must not strongly
envy bundle $\mathcal{M}\setminus A_{1}$ since $C$ is an $n$-certificate. And
since, $\mathcal{M}\setminus A_{1}=A_{2}$, we already have $v(A_{2})\geq
v(A_{1})$. Therefore, the allocation $(A_{1},\mathcal{M}\setminus A_{1})$
forms an $\mathsf{EFX}$ allocation in $\mathcal{I}$. ∎

######  Theorem 4.7.

The query complexity of the $\mathsf{EEFX}$ allocation problem with
$|\mathcal{M}|=2k+n-1$ many items is $\Omega(\frac{1}{k}{2k+1\choose k})$, for
arbitrary number of agents $n$ with identical submodular valuations.

###### Proof.

Consider any arbitrary instance $\mathcal{I}=([2],\mathcal{M},(v,v))$ with two
agents having identical submodular valuations $v$ and $|\mathcal{M}|=2k+1$
items. Create the instance $\mathcal{I}^{\prime}$ as described above. Using
Lemma 4.5, $\mathcal{I}^{\prime}$ consists of $n$ agents with identical
submodular valuations. By Lemma 4.6, given any $\mathsf{EEFX}$ allocation $A$,
we can obtain an $\mathsf{EFX}$ allocation for $\mathcal{I}$ in polynomial
time. Finally, using Theorem 4.1, we know that the query complexity of finding
an $\mathsf{EFX}$ allocation in $\mathcal{I}$ is
$\Omega(\frac{1}{k}{2k+1\choose k})$. Hence, the query complexity of
$\mathsf{EEFX}$ for $n$ agents with identical submodular valuations admits the
same lower bound. This establishes the stated claim. ∎

Finally, our next result follows using Lemma 4.6 and Theorem 4.2.

######  Theorem 4.8.

The problem of computing an $\mathsf{EEFX}$ allocation for arbitrary number of
agents with identical submodular valuations is $\mathsf{PLS}$-hard.

Since our reduction work even for three agents, Theorems 4.7 and 4.8 hold true
for the problem of computing $\mathsf{EEFX}$ allocations even for three agents
with identical submodular valuations. Note that the set of $\mathsf{EFX}$ and
$\mathsf{EEFX}$ allocations coincide for the case of two agents and hence it
inherits the same computational hardness guarantees as that of $\mathsf{EFX}$
here.

##  5 Conclusion and Open Problems

In this work, we establish the existence of $\mathsf{EEFX}$ allocations for an
arbitrary number of agents with general monotone valuations. To the best of
our knowledge, this is the strongest existential guarantee known for any
relaxation of $\mathsf{EFX}$ in discrete fair division. Furthermore, we also
prove that the problem of computing an $\mathsf{EEFX}$ allocation for
instances with an arbitrary number of agents with submodular valuations is
$\mathsf{PLS}$-hard and requires an exponential number of valuations queries
as well. Our existential result of $\mathsf{EEFX}$ allocations for monotone
valuations has opened a variety of major problems in discrete fair division.
We list three of them here, that we believe should be explored first.

The first interesting question is, for submodular or monotone valuations,
explore the possibility of a PTAS for computing an $\mathsf{EEFX}$ allocation,
or otherwise prove its $\mathsf{APX}$-hardness. An equally exciting problem
would be to explore the compatibility of $\mathsf{EEFX}$ and $\mathsf{EF}$1
allocations. Even for instances with additive valuations, does there always
exist an allocation that is simultaneously both $\mathsf{EEFX}$ and
$\mathsf{EF}$1? If yes, can we compute it? What about similar compatibility
question of $\mathsf{EEFX}$ with _Nash social welfare_? We know that a
_maximum Nash welfare_ (MNW) allocation is both $\mathsf{EF}$1 and _Pareto-
optimal_. What kind of a relation exist between $\mathsf{EEFX}$ and MNW
allocations?

## References

  * [1] Adjusted winner.  http://www.nyu.edu/projects/adjustedwinner/.  Accessed: 2019-07-07.
  * [2] www.spliddit.org.
  * Akrami and Garg [2024] Hannaneh Akrami and Jugal Garg.  Breaking the 3/4 barrier for approximate maximin share.  In _Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 74–91. SIAM, 2024.
  * Akrami et al. [2022] Hannaneh Akrami, Rojin Rezvan, and Masoud Seddighin.  An EF2X allocation protocol for restricted additive valuations.  In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI_ , pages 17–23, 2022.
  * Akrami et al. [2023a] Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta.  Efx: A simpler approach and an (almost) optimal guarantee via rainbow cycle number.  In _Proceedings of the 24th ACM Conference on Economics and Computation_ , EC ’23, page 61, New York, NY, USA, 2023a. Association for Computing Machinery.
  * Akrami et al. [2023b] Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki.  Simplification and improvement of MMS approximation.  In _32nd_ , 2023b.
  * Akrami et al. [2023c] Hannaneh Akrami, Masoud Seddighin, Kurt Mehlhorn, and Golnoosh Shahkarami.  Randomized and deterministic maximin-share approximations for fractionally subadditive valuations.  _CoRR_ , abs/2308.14545, 2023c.
  * Amanatidis et al. [2017] Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi.  Approximation algorithms for computing maximin share allocations.  _ACM Transactions on Algorithms_ , 13(4):1–28, 2017.
  * Amanatidis et al. [2020] Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos.  Multiple birds with one stone: Beating 1/2 for efx and gmms via envy cycle elimination.  _Theoretical Computer Science_ , 841:94–109, 2020.
  * Amanatidis et al. [2021] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris.  Maximum Nash welfare and other stories about EFX.  _Journal of Theoretical Computer Science_ , 863:69–85, 2021.
  * Amanatidis et al. [2022] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu.  Fair division of indivisible goods: A survey.  _arXiv preprint arXiv:2208.08782_ , 2022.
  * Arunachaleswaran et al. [2022] Eshwar Ram Arunachaleswaran, Siddharth Barman, and Nidhi Rathi.  Fully polynomial-time approximation schemes for fair rent division.  _Mathematics of Operations Research_ , 47(3):1970–1998, 2022.
  * Aziz et al. [2020] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy.  A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation.  _Operations Research Letters_ , 48(5):573–578, 2020.  doi: 10.1016/j.orl.2020.07.005.
  * Barman and Krishnamurthy [2019] Siddharth Barman and Sanath Kumar Krishnamurthy.  On the proximity of markets with integral equilibria.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1748–1755, 2019.
  * Barman and Krishnamurthy [2020] Siddharth Barman and Sanath Kumar Krishnamurthy.  Approximation algorithms for maximin fair division.  _ACM Transactions on Economics and Computation_ , 8(1):1–28, 2020.
  * Berendsohn et al. [2022] Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma.  Fixed-point cycles and approximate EFX allocations.  In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, _47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria_ , volume 241 of _LIPIcs_ , pages 17:1–17:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * Berger et al. [2022] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat.  Almost full EFX exists for four agents.  In _Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI)_ , volume 36(5), pages 4826–4833, 2022.
  * Bouveret and Lemaître [2016] Sylvain Bouveret and Michel Lemaître.  Characterizing conflicts in fair division of indivisible goods using a scale of criteria.  In _Proceedings of the 15th Autonomous Agents and Multi-Agent Systems (AAMAS)_ , pages 259–290. Springer, 2016.
  * Brams and Taylor [1996] Steven J Brams and Alan D Taylor.  _Fair Division: From cake-cutting to dispute resolution_.  Cambridge University Press, 1996.
  * Brandt and Procaccia [2016] Felix Brandt and Ariel D Procaccia.  _Handbook of computational social choice_.  Cambridge University Press, 2016.
  * Budish [2011] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  _Journal of Political Economy_ , 119(6):1061–1103, 2011.
  * Budish and Cantillon [2012] Eric Budish and Estelle Cantillon.  The multi-unit assignment problem: Theory and evidence from course allocation at harvard.  _American Economic Review_ , 102(5):2237–2271, 2012.
  * Caragiannis et al. [2016] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum nash welfare.  In _Proceedings of the 2016 ACM Conference on Economics and Computation_ , pages 305–322. ACM, 2016.
  * Caragiannis et al. [2019] Ioannis Caragiannis, Nick Gravin, and Xin 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.
  * Caragiannis et al. [2023] Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio.  New fairness concepts for allocating indivisible items.  In Edith Elkind, editor, _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23_ , pages 2554–2562. International Joint Conferences on Artificial Intelligence Organization, 2023.
  * Chan et al. [2019] Hau Chan, Jing Chen, Bo Li, and Xiaowei Wu.  Maximin-aware allocations of indivisible goods.  In _Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 137–143, 2019.
  * Chaudhury et al. [2020] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn.  EFX exists for three agents.  In _Proceedings of the 21st ACM Conference on Economics and Computation (EC)_ , pages 1–19, 2020.
  * Chaudhury et al. [2021] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa.  A little charity guarantees almost envy-freeness.  _SIAM Journal on Computing_ , 50(4):1336–1358, 2021.
  * Conitzer et al. [2017] Vincent Conitzer, Rupert Freeman, and Nisarg Shah.  Fair public decision making.  In _Proceedings of the 2017 ACM Conference on Economics and Computation_ , pages 629–646, 2017.
  * Deng et al. [2012] Xiaotie Deng, Qi Qi, and Amin Saberi.  Algorithmic solutions for envy-free cake cutting.  _Operations Research_ , 60(6):1461–1476, 2012.
  * Dubins and Spanier [1961] Lester E Dubins and Edwin H Spanier.  How to cut a cake fairly.  _The American Mathematical Monthly_ , 68(1P1):1–17, 1961.
  * Etkin et al. [2007] Raul Etkin, Abhay Parekh, and David Tse.  Spectrum sharing for unlicensed bands.  _IEEE Journal on Selected Areas in Communications_ , 25(3):517–528, 2007.
  * Farhadi et al. [2021] Alireza Farhadi, MohammadTaghi Hajiaghayi, Mohamad Latifian, Masoud Seddighin, and Hadi Yami.  Almost envy-freeness, envy-rank, and nash social welfare matchings.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 5355–5362, 2021.
  * Feige et al. [2021] Uriel Feige, Ariel Sapir, and Laliv Tauber.  A tight negative example for MMS fair allocations.  In _Proceedings of the 17th International Conference on Web and Internet Economics (WINE)_ , pages 355–372. Springer, 2021.
  * Foley [1967] Duncan K Foley.  Resource allocation and the public sector.  1967\.
  * Garg and Taki [2020] Jugal Garg and Setareh Taki.  An improved approximation algorithm for maximin shares.  In _Proceedings of the 21st ACM Conference on Economics and Computation (EC)_ , pages 379–380, 2020.
  * Ghodsi et al. [2018] Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi 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.
  * Goldberg et al. [2023] Paul W. Goldberg, Kasper Høgh, and Alexandros Hollender.  The frontier of intractability for efx with two agents.  In _Algorithmic Game Theory: 16th International Symposium, SAGT 2023, Egham, UK, September 4–7, 2023, Proceedings_ , page 290–307. Springer-Verlag, 2023.
  * Guo et al. [2023] Hao Guo, Weidong Li, and Bin Deng.  A survey on fair allocation of chores.  _Mathematics_ , 11(16):3616, 2023.
  * Halpern et al. [2020] Daniel Halpern, Ariel D Procaccia, Alexandros Psomas, and Nisarg Shah.  Fair division with binary valuations: One rule to rule them all.  In _Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7–11, 2020, Proceedings 16_ , pages 370–383. Springer, 2020.
  * Jahan et al. [2023] Shayan Chashm Jahan, Masoud Seddighin, Seyed Mohammad Seyed Javadi, and Mohammad Sharifi.  Rainbow cycle number and EFX allocations: (almost) closing the gap.  In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China_ , pages 2572–2580. ijcai.org, 2023.
  * Johnson et al. [1988] David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis.  How easy is local search?  _Journal of computer and system sciences_ , 37(1):79–100, 1988.
  * Kurokawa et al. [2016] David Kurokawa, Ariel D. Procaccia, and Junxing Wang.  When can the maximin share guarantee be guaranteed?  In _Proceedings of the 13th AAAI Conference on Artificial Intelligence (AAAI)_ , 2016.
  * Kurokawa et al. [2018] David Kurokawa, Ariel D. Procaccia, and Junxing Wang.  Fair enough: Guaranteeing approximate maximin shares.  _Journal of the ACM_ , 65(2):1–27, 2018.
  * Lipton et al. [2004] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In _Proceedings of the 5th ACM conference on Electronic commerce_ , pages 125–131. ACM, 2004.
  * Mahara [2021] Ryoga Mahara.  Extension of additive valuations to general valuations on the existence of EFX.  In _Proceedings of 29th Annual European Symposium on Algorithms (ESA)_ , page 66:1–66:15, 2021.  doi: 10.4230/LIPIcs.ESA.2021.66.
  * Moulin [2004] Hervé Moulin.  _Fair division and collective welfare_.  MIT press, 2004.
  * Moulin [2019] Hervé Moulin.  Fair division in the internet age.  _Annual Review of Economics_ , 11:407–441, 2019.
  * Plaut and Roughgarden [2020] Benjamin Plaut and Tim Roughgarden.  Almost envy-freeness with general valuations.  _SIAM Journal on Discrete Mathematics_ , 34(2):1039–1068, 2020.
  * Pratt and Zeckhauser [1990] John Winsor Pratt and Richard Jay Zeckhauser.  The fair and efficient division of the winsor family silver.  _Management Science_ , 36(11):1293–1301, 1990.
  * Procaccia [2020] Ariel D Procaccia.  Technical perspective: An answer to fair division’s most enigmatic question.  _Communications of the ACM_ , 63(4):118–118, 2020.
  * Robertson and Webb [1998] Jack Robertson and William Webb.  _Cake-cutting algorithms: Be fair if you can_.  AK Peters/CRC Press, 1998.
  * Seddighin and Seddighin [2022] Masoud Seddighin and Saeed Seddighin.  Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem.  In _AAAI 2022, IAAI 2022, EAAI 2022 Virtual Event, February 22 - March 1, 2022_. AAAI Press, 2022.
  * Steinhaus [1948] Hugo Steinhaus.  The problem of fair division.  _Econometrica_ , 16:101–104, 1948.
  * Stromquist [1980] Walter Stromquist.  How to cut a cake fairly.  _The American Mathematical Monthly_ , 87(8):640–644, 1980.
  * Stromquist [2008] Walter Stromquist.  Envy-free cake divisions cannot be found by finite protocols.  _the electronic journal of combinatorics_ , 15(1):11, 2008.
  * Su [1999] Francis Edward Su.  Rental harmony: Sperner’s lemma in fair division.  _The American mathematical monthly_ , 106(10):930–942, 1999.
  * Uziahu and Feige [2023] Gilad Ben Uziahu and Uriel Feige.  On fair allocation of indivisible goods to submodular agents, 2023.
  * Varian [1973] Hal R Varian.  Equity, envy, and efficiency.  1973\.
  * Vossen [2002] Thomas Vossen.  _Fair allocation concepts in air traffic management_.  PhD thesis, PhD thesis, University of Maryland, College Park, 2002.

##  Appendix A Missing Proofs

See 4.5

###### Proof.

We need to prove that for all $S,T\subseteq\mathcal{M}$,
$v^{\prime}(S)+v^{\prime}(T)\geq v^{\prime}(S\cup T)+v^{\prime}(S\cap T)$. Let
$H_{S}$ and $H_{T}$ be the set of all heavy items in $S$ and $T$ respectively.
We have

$\displaystyle v^{\prime}(S)+v^{\prime}(T)$
$\displaystyle=v^{\prime}(S\setminus
H_{S})+v^{\prime}(H_{S})+v^{\prime}(T\setminus H_{T})+v^{\prime}(H_{T})$
$\displaystyle=\left(v(S\setminus H_{S})+v(T\setminus
H_{T})\right)+v^{\prime}(H_{S})+v^{\prime}(H_{T}))$ $\displaystyle\geq
v((S\setminus H_{S})\cup(T\setminus H_{T}))+v((S\setminus
H_{S})\cap(T\setminus H_{T}))+v^{\prime}(H_{S})+v^{\prime}(H_{T})$
(submodolarity of $v$) $\displaystyle=v^{\prime}((S\cup T)\setminus(H_{S}\cup
H_{T}))+v^{\prime}((S\cap T)\setminus(H_{S}\cap
H_{T}))+v^{\prime}(H_{S})+v^{\prime}(H_{T})$ $\displaystyle=v^{\prime}((S\cup
T)\setminus(H_{S}\cup H_{T}))+v^{\prime}((S\cap T)\setminus(H_{S}\cap H_{T}))$
$\displaystyle{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}=}+v^{\prime}(H_{S}\cup
H_{T})+v^{\prime}(H_{S}\cap H_{T})$ (additivity of $v^{\prime}$ on heavy
items) $\displaystyle=v^{\prime}(S\cup T)+v^{\prime}(S\cap T).$

∎

##  Appendix B Polynomial Local Search ($\mathsf{PLS}$)

The following is taken from Section 7.2 in Arunachaleswaran et al. [2022].

The class $\mathsf{PLS}$ (Polynomial Local Search) was defined by Johnson et
al. [1988] to capture the complexity of finding local optima of optimization
problems. Here, a generic instance $\mathcal{I}$ of an optimization problem
has a corresponding finite set of solutions $S(\mathcal{I})$ and a potential
$c(s)$ associated with each solution $s\in S(\mathcal{I})$. The objective is
to find a solution that maximizes (or minimizes) this potential. In the local
search version of the problem, each solution $s\in S(\mathcal{I})$
additionally has a well-defined neighborhood $N(s)\in 2^{S(\mathcal{I})}$ and
the objective is to find a local optimum, i.e., a solution $s\in
S(\mathcal{I})$ such that no solution in its neighborhood $N(s)$ has a higher
potential.

######  Definition B.1 ($\mathsf{PLS}$).

Consider an optimization problem $\mathcal{X}$, and for all input instances
$\mathcal{I}$ of $\mathcal{X}$ let $S(\mathcal{I})$ denote the finite set of
feasible solutions for this instance, $N(s)$ be the neighborhood of a solution
$s\in S(\mathcal{I})$, and $c(s)$ be the potential of solution $s$. The
desired output is a local optimum with respect to the potential function.

Specifically, $\mathcal{X}$ is a polynomial local search problem (i.e.,
$\mathcal{X}\in\mathsf{PLS}$) if all solutions are bounded in the size of the
input $\mathcal{I}$ and there exists polynomial-time algorithms
$\mathcal{A}_{1}$, $\mathcal{A}_{2}$, and $\mathcal{A}_{3}$ such that:

  1. 1.

$\mathcal{A}_{1}$ tests whether the input $\mathcal{I}$ is a legitimate
instance of $\mathcal{X}$ and if yes, outputs a solution
$s_{\text{initial}}\in S(\mathcal{I})$.

  2. 2.

$\mathcal{A}_{2}$ takes as input instance $\mathcal{I}$ and candidate solution
$s$, tests if $s\in S(\mathcal{I})$ and if yes, computes $c(s)$.

  3. 3.

$\mathcal{A}_{3}$ takes as input instance $\mathcal{I}$ and candidate solution
$s$, tests if $s$ is a local optimum and if not, outputs $s^{\prime}\in N(s)$
such that $c(s^{\prime})>c(s)$ (the inequality is reversed for the
minimization version).

Each $\mathsf{PLS}$ problem comes with an associated local search algorithm
that is implicitly described by the three algorithms mentioned above. The
first algorithm is used to find an initial solution to the problem and the
third algorithm is iteratively used to find a potential-improving neighbor
until a local optimum is reached.