EFX Exists for Three Agents

Introduction

This relaxation was introduced by Budish [Bud11]. An allocation $X$ is said to be EF1 if no agent $i$ envies another agent $j$ after the removal of some item in $j$’s bundle, i.e., $v_{i}(X_{i})\geq v_{i}(X_{j}\setminus g)$ for some $g\in X_{j}$. So we allow $i$ to envy $j$, but the envy must disappear after the removal of some valuable item (according to agent $i$) from $j$’s bundle. Note that there is no actual removal: This is simply to assess how agent $i$ values his own bundle when compared to $j$’s bundle. It is well known that an EF1 allocation always exists, and it can be obtained in polynomial time using the famous envy-cycles procedure by Lipton et al. [LMMS04]. However, an EF1 allocation may be unsatisfactory: Intuitively, EF1 insists that envy disappears after the removal of the most valuable item according to the envying agent from the envied agent’s bundle—however, in many cases, the most valuable item might be the primary reason for very large envy to exist in the first place. Therefore, stronger notions of fairness are desirable in many circumstances.

Envy-freeness up to any item (EFX):

This relaxation was introduced by Caragiannis et al. [CKM+16]. An allocation $X$ is said to be EFX if no agent $i$ envies another agent $j$ after the removal of any item in $j$’s bundle, i.e., $v_{i}(X_{i})\geq v_{i}(X_{j}\setminus g)$ for all $g\in X_{j}$. Unlike EF1, in an EFX allocation, the envy between any pair of agents disappears after the removal of the least valuable item (according to agent $i$) from $j$’s bundle. Note that every EFX allocation is an EF1 allocation, but not vice-versa. Consider a simple example of two agents with additive valuations and three items $\{a,b,c\}$ from [CKMS20], where the agents valuation for individual items are as follows,

Observe that $g_{3}$ is twice as valuable than $g_{1}$ or $g_{2}$ for both agents. An allocation where one agent gets $\{g_{1}\}$ and the other gets $\{g_{2},g_{3}\}$ is EF1 but not EFX. The only possible EFX allocation is where one agent gets $\left\{g_{3}\right\}$ and the other gets $\left\{g_{1},g_{2}\right\}$, which is clearly fairer than the given EF1 allocation. This example also shows how EFX helps to rule out some unsatisfactory EF1 allocations. Caragiannis et al. [CGH19] remark that

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

While an EF1 allocation is always guaranteed to exist, very little is known about the existence of EFX allocations. Caragiannis et al. [CKM+16] state that

“Despite significant effort, we were not able to settle the question of whether an EFX allocation always exists (assuming all items must be allocated), and leave it as an enigmatic open question.”

Plaut and Roughgarden [PR18] show two scenarios for which EFX allocations are guaranteed to exist: $(i)$ All agents have identical valuations (i.e., $v_{1}=v_{2}=\dots=v_{n}$), and $(ii)$ Two agents (i.e., $n=2$). Unfortunately, starting from three agents, even for the well studied class of additive valuations, it is open whether EFX allocations exist. Plaut and Roughgarden [PR18] also remark that:

“The problem seems highly non-trivial even for three players with different additive valuations.”

Furthermore, it is also suspected in [PR18] that EFX allocations may not exist in general settings:

“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.”

EFX allocations always exist for three agents with additive valuations.

EFX with charity:

Quite recently there have been studies [CGH19, CKMS20] that consider relaxations of EFX, called “EFX with charity”. Here we look for partial EFX allocations, where not all items need to be allocated (some of them remain unallocated). There is a trivial such allocation where no item is allocated to any agent. Therefore, the goal is to determine allocations with some qualitative or quantitative bound on the set of unallocated items. For instance, Chaudhury et al. [CKMS20] show how to determine a partial EFX allocation $X$ and a pool of unallocated items $P$ such that no agent envies the pool (i.e. for any agent $i$, we have $v_{i}(X_{i})\geq v_{i}(P)$), and $P$ has less than $n$ items (i.e., $\lvert P\rvert<n$), even in the case of general valuations. In case of additive valuations, Caragiannis et al. [CGH19] show the existence of a partial EFX allocation $X=\langle X_{1},X_{2},\dots,X_{n}\rangle$, where every agent gets at least half the value of his bundle in the allocation that maximizes the Nash welfare i.e., the geometric mean of agents’ valuations. (suggesting that unallocated items are not too valuable).

The Nash welfare of a fair allocation is often considered as a measure of its efficiency [CGH19]: Intuitively, it captures how much average welfare the allocation achieves while still remaining fair. The result of Caragiannis et al. [CGH19] imply that there are efficient partial EFX allocations (partial EFX allocations with a 2-approximation of the maximum possible Nash welfare). Indeed, it is a natural question to ask whether there are complete EFX allocations (all items are allocated) with good efficiency. To this end, Caragiannis et al. [CGH19] conjecture:

“In particular, we suspect that adding an item to an allocation problem (that provably has an EFX allocation) yields another problem that also has an EFX allocation with at least as high Nash welfare as the initial one.’’ This was posed as a monotonicity conjecture in their presentation at EC’19.

If this conjecture is true, it implies the existence of an efficient complete EFX allocation. We show (in Section 5) that

To disprove the conjecture we exhibit an instance where there exists a partial EFX allocation with higher Nash welfare than the Nash welfare of any complete EFX allocation. This also highlights an inherent barrier in the current techniques to determining EFX allocations: Several of the existing algorithms for approximate EFX allocations ([PR18]) and EFX allocations with charity ([CKMS20]) start with a inefficient partial EFX allocation and make it more efficient iteratively by cleverly allocating some of the unallocated items and unallocating some of the allocated items. However, our instance in Section 5 shows that such approaches will not help if our goal is to determine a complete EFX allocation.

A large chunk of our work in this paper develops better tools to overcome this particular barrier, and we consider the tools introduced here as the most innovative technical contribution of our work. We also feel that these tools and the instance may help resolving the major open problem of the existence of EFX allocations for more than three agents and more general valuations (positively or negatively).

1 Our Contributions

Our major contribution in this paper is to prove that an EFX allocation always exists when there are three agents with additive valuations. The proof is algorithmic. To discuss our techniques, we first briefly highlight how we overcome two barriers in the current techniques.

We first sketch the simple algorithm of Plaut and Roughgarden [PR18] that determines an EFX allocation when all agents have the same valuation function, say $v$. Let us restrict our attention to the special case where there is no zero marginals, i.e., for any $S\subseteq M$ and $g\notin S$ we have $v(S\cup g)>v(S)$. Also, note that since agents have the same valuation function, if $v(X_{i})<v(X_{j}\setminus g)$ for two agents $i$ and $j$ for some $g\in X_{j}$ then we have $v(X_{i_{\mathit{min}}})<v(X_{j}\setminus g)$ where $i_{\mathit{min}}$ is the agent with the lowest valuation. The algorithm in [PR18] starts off with an arbitrary allocation (not necessarily EFX), and as long as there are agents $i$ and $j$ such that $v(X_{i})<v(X_{j}\setminus g)$ for some $g\in X_{j}$, the algorithm takes the item $g$ away from $j$ ($j$’s new bundle is $X_{j}\setminus g$) and adds it to $i_{\mathit{min}}$’s bundle ($i_{\mathit{min}}$’s new bundle is $X_{i_{\mathit{min}}}\cup g$). Also, note that after re-allocation the only changed bundles are that of $i_{\mathit{min}}$ and $j$, and both of them have valuations still higher than $i_{\mathit{min}}$’s initial valuation: $v(X_{i_{\mathit{min}}}\cup g)>v(X_{i_{\mathit{min}}})$ and $v(X_{j}\setminus g)>v(X_{i_{\mathit{min}}})$. Observe that such an operation increases the valuation of an agent with the lowest valuation. Thus, after finitely many applications of this re-allocation we must arrive at an EFX allocation. Note that this crucially uses the fact that the agents have identical valuations. In the general case, the valuation of agent $j$ may drop significantly after removing $g$ and $j$’s current valuation may be even less than $i_{\mathit{min}}$’s initial valuation. Therefore, it is important to understand how agents value item(s) that we move across the bundles. To this end, we carefully split every bundle into upper and lower half bundles (see (2) in Section 2). We systematically quantify the agent’s relative valuations agents have for these upper and lower half bundles, and in most cases, we are able to move these bundles from one agent to the other, improve the valuation of some of the agents, and while still guaranteeing EFX property. This idea is detailed in Sections 3 and 4.

A new potential function:

We need to show that there is progress after every swap of half bundles. The typical method here is to show improvement of the valuation vector on the Pareto front (see [CKMS20] and [PR18]). However, there are limitations to this approach: In particular, we show an instance and a partial EFX allocation such that the valuation vector of any complete EFX allocation does not Pareto dominate the valuation vector of the existing partial EFX allocation. To overcome this barrier, we first pick an arbitrary agent $a$ at the beginning and show that whenever we are unable to improve the valuation vector on the Pareto front, we can strictly increase $a$’s valuation. In other words, the valuation of a particular agent $a$ never decreases throughout re-allocations, and it improves after finitely many re-allocations, showing convergence. A more elaborate discussion on this technique is presented in Section 2.

2 Further Related Work

Fair division has received significant attention since the seminal work of Steinhaus [Ste48] in the 1940s, where he introduced the cake cutting problem among $n>2$ agents. Perhaps the two most crucial notions of fairness properties that can be guaranteed in case of divisible items are envy-freeness and proportionality. In a proportional allocation, each agent gets at least a $1/n$ share of all the items. In case of indivisible items, as mentioned earlier, none of these two notions can be guaranteed. 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 [Bud11]. While MMS allocations do not always exist [KPW18], but there has been extensive work to come up with approximate MMS allocations [Bud11, BL16, AMNS17, BK17, KPW18, GHS+18, GMT19, GT19].

While much research effort goes into finding fair allocations, there has also been a lot of interest in guaranteeing efficient fair allocations. A standard notion of efficiency is 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$.. Caragiannis et al. [CKM+16] showed that any allocation that has the maximum Nash welfare is guaranteed to be Pareto-optimal (efficient) and EF1 (fair). Therefore, the Nash welfare of an allocation is also considered as a measure of efficiency and fairness of an allocation. However, finding an allocation with the maximum Nash welfare is APX-hard [Lee17], and its approximation has received a lot of attention recently, e.g., [CG18, CDG+17, AGSS17, GHM18, AMGV18, BKV18, CCG+18, GKK20]. Barman et al. [BKV18] give a pseudopolynomial algorithm to find an allocation that is both EF1 and Pareto-optimal. Other works try to approximate MMS with Pareto-optimality [GM19] or explore relaxations of EFX with high Nash welfare [CGH19].

There are several real-world scenarios where resources need to be divided fairly and efficiently, e.g., splitting rent among tenants, dividing inheritance property in a family, splitting taxi fares among riders, and many more. One examples of fair division techniques used in practice is Spliddit (http://www.spliddit.org). Since its launch in 2014, Spliddit has had several thousands of users [CKM+16]. For more details on Spliddit, we refer the reader to [GP14, PR18]. Another example is Course Allocate, which is used by the Wharton School at the University of Pennsylvania to fairly allocate 350 courses to 1700 MBA students [PR18, BCKO17]. Kurokawa et al. [KPS18] used leximin fairness to allocate unused classrooms in public schools to charter schools in California. The best part of the allocations determined in all these applications is that they yield results that not only seem fair on most instances, but also come with mathematical guarantees.

Preliminaries and Technical Overview

We call an instance $I=\langle,M,\mathcal{V}\rangle$ non-degenerate if and only if no agent values two different sets equally, i.e., $\forall i\in$ we have $v_{i}(S)\neq v_{i}(T)$ for all $S\neq T$. We first show that it suffices to deal with non-degenerate instances. Let $M=\left\{g_{1},g_{2},\dots,g_{m}\right\}$. We perturb any instance $I$ to $I(\varepsilon)=\langle,M,\mathcal{V}(\varepsilon)\rangle$, where for every $v_{i}\in\mathcal{V}$ we define $v^{\prime}_{i}\in\mathcal{V}(\varepsilon)$, as

Let $\delta=\min_{i\in}\min_{S,T\colon v_{i}(S)\neq v_{i}(T)}|v_{i}(S)-v_{i}(T)|$ and let $\varepsilon>0$ be such that $\varepsilon\cdot 2^{m+1}<\delta$. Then

For any agent $i$ and $S,T\subseteq M$ such that $v_{i}(S)>v_{i}(T)$, we have $v^{\prime}_{i}(S)>v^{\prime}_{i}(T)$.

$I(\varepsilon)$ is a non-degenerate instance. Furthermore, if $X=\langle X_{1},X_{2},X_{3}\rangle$ is an EFX allocation for $I(\varepsilon)$ then $X$ is also an EFX allocation for $I$.

For the first statement of the lemma, observe that

For the second statement of the lemma, consider any two sets $S,T\subseteq M$ such that $S\neq T$. Now, for any $i\in$, if $v_{i}(S)\neq v_{i}(T)$, we have $v^{\prime}_{i}(S)\neq v^{\prime}_{i}(T)$ by the first statement of the lemma. If $v_{i}(S)=v_{i}(T)$, we have $v^{\prime}_{i}(S)-v^{\prime}_{i}(T)=\varepsilon(\sum_{g_{j}\in S\setminus T}2^{j}-\sum_{g_{j}\in T\setminus S}2^{j})\neq 0$ (as $S\neq T$). Therefore, $I(\varepsilon)$ is non-degenerate.

For the final claim, let us assume that $X$ is an EFX allocation in $I(\varepsilon)$ and not an EFX allocation in $I$. Then there exist $i,j$, and $g\in X_{j}$ such that $v_{i}(X_{j}\setminus g)>v_{i}(X_{i})$. In that case, we have $v^{\prime}_{i}(X_{j}\setminus g)>v^{\prime}_{i}(X_{i})$ by the first statement of the lemma, implying that $X$ is not an EFX allocation in $I(\varepsilon)$ as well, which is a contradiction. ∎

From now on we only deal with non-degenerate instances. In non-degenerate instances, all goods have positive value for all agents.

Overall approach:

An allocation $X^{\prime}$ Pareto dominates an allocation $X$ if $v_{i}(X_{i})\leq v_{i}(X_{i}^{\prime})$ for all $i$ with strict inequality for at least one $i$. The existing algorithms for “EFX with charity” [CKMS20] or “approximate EFX allocations” [PR18] construct a sequence of EFX allocations in which each allocation Pareto dominates its predecessor. However we exhibit in Section 5 a partial EFX allocation that is not Pareto dominated by any complete EFX allocation. Thus we need a more flexible approach in the search for a complete EFX allocation.

We name the agents $a$, $b$, and $c$ arbitrarily and consider the lexicographic ordering of the triples

i.e., $\phi(X)\prec_{\mathit{lex}}\phi(X^{\prime})$ ($X^{\prime}$ dominates $X$) if (i) $v_{a}(X_{a})<v_{a}(X^{\prime}_{a})$ or (ii) $v_{a}(X_{a})=v_{a}(X^{\prime}_{a})$ and $v_{b}(X_{b})<v_{b}(X^{\prime}_{b})$ or (iii) $v_{a}(X_{a})=v_{a}(X^{\prime}_{a})$ and $v_{b}(X_{b})=v_{b}(X^{\prime}_{b})$ and $v_{c}(X_{c})<v_{c}(X^{\prime}_{c})$. We construct a sequence of allocations in which each allocation dominates its predecessor. Of course, if $X^{\prime}$ Pareto dominates $X$, then it also dominates $X$, so we can use all the update rules in [CKMS20].

Our goal then is to iteratively construct a sequence of EFX allocations such that each EFX allocation dominates its predecessor.

Most envious agent:

We use the notion of a most envious agent, introduced in [CKMS20]. Consider an allocation $X$, and a set $S\subseteq M$ that is envied by at least one agent. For an agent $i$ such that $S>_{i}X_{i}$, we “measure the envy” that agent $i$ has for $S$ by $\kappa_{X}(i,S)$, where $\kappa_{X}(i,S)$ is the size of a smallest subset of $S$ that $i$ still envies, i.e., $\kappa_{X}(i,S)$ is the smallest cardinality of a subset $S^{\prime}$ of $S$ such that $S^{\prime}>_{i}X_{i}$. Thus, the smaller the value of $\kappa_{X}(i,S)$, the greater the envy of agent $i$ for the set $S$. So let $\kappa_{X}(S)=\mathit{min}_{i\in}\kappa_{X}(i,S)$. Naturally, we define the set of the most envious agents $A_{X}(S)$ for a set $S$ as the set of agents with smallest values of $\kappa_{X}(i,S)$, i.e.,

The following simple observation about the most envious agents of specific kinds of bundles will be useful.

Given any allocation $X$, and an unallocated good $g$, for any $i\in$, $A_{X}(X_{i}\cup g)\neq\emptyset$.

It suffices to prove that there exists at least one agent who strictly prefers $X_{i}\cup g$ over his own bundle in allocation $X$. This is guaranteed since we are dealing with non-degenerate instances, in which $X_{i}\cup g>_{i}X_{i}$. ∎

Champions and Champion Graph MXM_{X}:

Let $X$ be the partial EFX allocation at any stage in our algorithm, and let $g$ be an unallocated good. We say that $i$ champions $j$ (w.r.t $g$) if $i$ is a most envious agent for $X_{j}\cup g$, i.e., $i\in A_{X}(X_{j}\cup g)$. We define the champion graph $M_{X}$, where each vertex corresponds to an agent and there is a directed edge $(i,j)\in M_{X}$ if and only if $i$ champions $j$.

By Observation 2, we have that the set of champions of any agent is never empty. Therefore, every vertex in $M_{X}$ has at least one incoming edge. Thus $M_{X}$ is cyclic. ∎

If $i$ champions $j$, we define $G_{ij}$ as a largest cardinality subset of $X_{j}\cup g$ such that $(X_{j}\cup g)\setminus G_{ij}>_{i}X_{i}$. Since the valuations are additive, note that such a subset can be identified efficiently as the set $K$ of the $k$ least valuable goods for $i$ in $X_{j}\cup g$ such that $(X_{j}\cup g)\setminus K>_{i}X_{i}$ and $k$ is maximum. Now we make some small observations.

We have $((X_{j}\cup g)\setminus G_{ij})\setminus h\leq_{k}X_{k}$ for all $h\in(X_{j}\cup g)\setminus G_{ij}$ and all agents $k$ including $i$.

If agent $k$ does not champion $j$, we have $(X_{j}\cup g)\setminus G_{ij}\leq_{k}X_{k}$.

Note that by definition, $G_{ij}$ is a largest cardinality subset of $X_{j}\cup g$ such that $i$ values $(X_{j}\cup g)\setminus G_{ij}$ more than $X_{i}$. This implies that $(X_{j}\cup g)\setminus G_{ij}$ is a smallest cardinality subset of $X_{j}\cup g$ that $i$ values more than $X_{i}$. Thus $\lvert(X_{j}\cup g)\setminus G_{ij}\rvert=\kappa_{X}(i,X_{j}\cup g)$. Since $i$ champions $j$, we have that $i\in A_{X}(X_{j}\cup g)$ and thus $\kappa_{X}(i,X_{j}\cup g)=\kappa_{X}(X_{j}\cup g)$. Now, no agent $k$ values a subset of $X_{j}\cup g$ of size less than $\kappa_{X}(k,X_{j}\cup g)$ more than $X_{k}$. Note that $((X_{j}\cup g)\setminus G_{ij})\setminus h$ has size $\kappa_{X}(X_{j}\cup g)-1<\kappa_{X}(k,X_{j}\cup g)$ and ,thus, $((X_{j}\cup g)\setminus G_{ij})\setminus h\leq_{k}X_{k}$.

Now if $k$ did not champion $j$ then $\kappa_{X}(k,X_{j}\cup g)<\kappa_{X}(X_{j}\cup g)$. Thus, $\lvert(X_{j}\cup g)\setminus G_{ij}\rvert=\kappa_{X}(X_{j}\cup g)<\kappa_{X}(k,X_{j}\cup g)$. Since $k$ values any subset of $X_{j}\cup g$ of size less than $\kappa_{X}(k,X_{j}\cup g)$ at most $X_{k}$, we have $(X_{j}\cup g)\setminus G_{ij}\leq_{k}X_{k}$. ∎

We next mention two cases where it is known how to obtain a Pareto dominating EFX allocation from an existing EFX allocation. For an allocation $X$, we define the envy graph $E_{X}$, whose vertices represent agents, and in which there is a directed edge from $i$ to $j$ if $i$ envies $j$, i.e., $X_{j}>_{i}X_{i}$. We can assume without loss of generality (w.l.o.g.) that $E_{X}$ is acyclic.

Let $X=\langle X_{1},X_{2},X_{3}\rangle$ be an EFX allocation. Then there exists another EFX allocation $Y=\langle Y_{1},Y_{2},Y_{3}\rangle$, where for all $i\in$, $Y_{i}=X_{j}$ for some $j\in$, such that $E_{Y}$ is acyclic and $\phi(Y)\succeq_{\mathit{lex}}\phi(X)$ (because $Y$ Pareto dominates $X$).

Consider an EFX allocation $X$. Let $s$ be any agent and let $g$ be an unallocated good. If $i$ champions $s$ and $i$ is reachable from $s$ in $E_{X}$, then there is an EFX allocation $Y$ Pareto dominating $X$. Additionally, agent $s$ is strictly better off in $Y$, i.e., $Y_{s}>_{s}X_{s}$.

We have that $i$ is reachable from $s$ in $E_{X}$. Let $t_{1}\rightarrow t_{2}\rightarrow\dots\rightarrow t_{k}$ be the path from $t_{1}=s$ to $t_{k}=i$ in $E_{X}$. We determine a new allocation $Y$ as follows:

Note that every agent along the path has strictly improved his valuation: Agents $t_{1}$ to $t_{k-1}$ got bundles they envied in $E_{X}$ and agent $i$ championed $s$ and got $(X_{s}\setminus G_{is}\cup g)$, which is more valuable to $i$ than $X_{i}$ (by definition of $G_{is}$). Also, every other agent retained their previous bundles and thus their valuations are not lower than before. Thus $\phi(Y)\succ_{\mathit{lex}}\phi(X)$ and also $Y_{s}>_{s}X_{s}$ ($s$ was an agent along the path). It only remains to argue that $Y$ is EFX. To this end, consider any two agents $j$ and $j^{\prime}$. We wish to show that $j$ does not strongly envy $j^{\prime}$ in $Y$.

We have $Y_{j^{\prime}}=(X_{s}\setminus G_{is})\cup g$. Since $i$ championed $s$, by Observation 4 (part 1) we have that $((X_{s}\setminus G_{is})\cup g)\setminus h\leq_{j}X_{j}$. Like earlier, $Y_{j}\geq_{j}X_{j}$ (no agent is worse off in $Y$). Thus $j$ does not strongly envy $i$. ∎

Observation 6 implies that if there is some unallocated good and (i) if the envy graph $E_{X}$ has a single source A source is a vertex in $E_{X}$ with in-degree zero. or (ii) any agent champions himself then there is a strictly Pareto dominating EFX allocation.

Let $X$ be an EFX allocation, and $g$ be an unallocated good. If $E_{X}$ has a single source $s$, or $M_{X}$ has a $1$-cycle involving agent $s$, then there is an EFX allocation $Y$ that Pareto dominates $X$ in which $Y_{s}>_{s}X_{s}$.

If $E_{X}$ has a single source $s$, the champion of $s$ (which always exist, by Observation 2) is reachable from $s$. If $M_{X}$ has a $1$-cycle involving agent $s$ then again the champion of $s$ (which is $s$ itself) is reachable from $s$. In both cases, since the champion of $s$ is reachable from $s$ in the envy graph $E_{X}$, there is a Pareto dominating allocation $Y$ such that $Y_{s}>_{s}X_{s}$ by Observation 6. ∎

Hence, starting from Section 3, we only discuss the cases where the envy-graph has more than one source and there are no self-champions.

We start with some simple yet crucial observations.

If $i$ champions $j$ and $X_{i}\geq_{i}X_{j}$, then $g\notin G_{ij}$, $G_{ij}\subseteq X_{j}$, and $G_{ij}<_{i}g$.

We have $i\in A_{X}(X_{j}\cup g)$. Since $g\notin X_{j}$, $G_{ij}\subseteq X_{j}\cup g$, and valuations are additive and we have that $v_{i}((X_{j}\cup g)\setminus G_{ij})=v_{i}(X_{j})+v_{i}(g)-v_{i}(G_{ij})$. Again since $i\in A_{X}(X_{j}\cup g)$, by the definition of $G_{ij}$, $(X_{j}\cup g)\setminus G_{ij}>_{i}X_{i}$, and hence, $v_{i}(X_{i})<v_{i}(X_{j})+v_{i}(g)-v_{i}(G_{ij})$. Now we have $X_{i}\geq_{i}X_{j}$, implying that $G_{ij}<_{i}g$, and therefore, $g\not\in G_{ij}$. ∎

Observation 8 tells us that if $i$ champions $j$, and $i$ does not envy $j$, then $G_{ij}\subseteq X_{j}$. Therefore, we can split the bundle of agent $j$ into two parts $G_{ij}$ and $X_{j}\setminus G_{ij}$. We refer to $G_{ij}$ as the lower-half bundle of $j$, and to $X_{j}\setminus G_{ij}$ as the upper-half bundle of $j$, and visualize the bundle of agent $j$ as

We collect some more facts about the values of lower and upper half bundles.

If $i$ champions $j$ and $j$ does not champion himself (self-champion), then we have $G_{ij}\not=\emptyset$ and $G_{ij}\geq_{j}g$.

Since $j$ does not self-champion, by Observation 4 (part 2), we have that $(X_{j}\cup g)\setminus G_{ij}\leq_{j}X_{j}$. Since $g\notin X_{j}$ and $G_{ij}\subseteq X_{j}\cup g$ we have $v_{j}((X_{j}\cup g)\setminus G_{ij})=v_{j}(X_{j})+v_{j}(g)-v_{j}(G_{ij})\leq v_{j}(X_{j})$, implying that $G_{ij}\geq_{j}g$. Since the value of $g$ for $j$ is non-zero, $G_{ij}$ is non-empty. ∎

Let $i$ champion $j$, and $X_{i}\geq_{i}X_{j}$. Let $i^{\prime}$ champion $k$ and $X_{i^{\prime}}\geq_{i^{\prime}}X_{k}$. If $i$ does not champion $k$, then $X_{j}\setminus G_{ij}>_{i}X_{k}\setminus G_{i^{\prime}k}$.

Since $i\in A_{X}(X_{j}\cup g)$ and $X_{i}\geq_{i}X_{j}$, by Observation 8, we have $g\notin G_{ij}$. Thus, $G_{ij}\subseteq X_{j}$. By the same reasoning, $g\notin G_{i^{\prime}k}$ and $G_{i^{\prime}k}\subseteq X_{k}$. Therefore, $(X_{j}\cup g)\setminus G_{ij}=(X_{j}\setminus G_{ij})\cup g$, and $(X_{k}\cup g)\setminus G_{i^{\prime}k}=(X_{k}\setminus G_{i^{\prime}k})\cup g$. By the definition of $G_{ij}$, we have $(X_{j}\setminus G_{ij})\cup g>_{i}X_{i}$. Since $i\notin A_{X}(X_{k}\cup g)$, we have $X_{i}\geq_{i}(X_{k}\setminus G_{i^{\prime}k})\cup g$ by Observation 4 (part 2). Combining the two inequalities, we have $(X_{j}\setminus G_{ij})\cup g>_{i}(X_{k}\setminus G_{i^{\prime}k})\cup g$, which implies $X_{j}\setminus G_{ij}>_{i}X_{k}\setminus G_{i^{\prime}k}$. ∎

In the upcoming sections, we show how to derive a dominating EFX allocation from an existing EFX allocation. Corollary 7 already deals with the cases that $E_{X}$ has a single source or $M_{X}$ has a 1-cycle. We proceed under the following general assumptions: $E_{X}$ is cycle-free and has at least two sources and there is no 1-cycle in $M_{X}$. We distinguish the remaining cases by the number of sources in $E_{X}$.

Existence of EFX: Three sources in EXE_{X}

If $E_{X}$ has three sources, the allocation $X$ is envy-free, i.e., $X_{i}\geq_{i}X_{j}$ for all $i$ and $j$. We make a case distinction by whether or not $M_{X}$ contains a $2$-cycle.

Assume without loss of generality that agent 2 champions agent 1 and agent 1 champions agent 2. Since $X_{1}\geq_{1}X_{2}$ and $X_{2}\geq_{2}X_{1}$, the bundles $X_{1}$ and $X_{2}$ decompose according to (2). Since neither 1 nor 2 self-champion (as $M_{X}$ has no $1$-cycle), by Observation 10, we have $X_{2}\setminus G_{12}>_{1}X_{1}\setminus G_{21}$ and $X_{1}\setminus G_{21}>_{2}X_{1}\setminus G_{12}$. We swap the upper-halves of $X_{1}$ and $X_{2}$ to obtain

Note that agent 3 has the same valuation as before, while 1 and 2 are strictly better off. If $X^{\prime}$ is EFX we are done. So assume otherwise. We first determine the potential strong envy edges.

From 1: We replaced the more valuable (according to 1) $X_{2}\setminus G_{12}$ in $X_{2}$ with the less valuable $X_{1}\setminus G_{21}$ and left $X_{3}$ unchanged. Thus 1 is strictly better off and according to him, the valuations of the bundles of 2 and 3 in $X^{\prime}$ is at most the valuation of their bundles in $X$. As 1 did not envy 2 and 3 before in $X$, 1 does not envy 2 and 3 in $X^{\prime}$.

From 2: A symmetrical argument shows that 2 does not envy 1 and 3.

From 3: For agent 3, the sum of the valuations of agents 1 and 2 has not changed by the swap and 3 envied neither 1 nor 2 before the swap. Thus 3 envies at most one of the agents 1 and 2 after the swap. Assume without loss of generality that he envies agent 2. We then replace the lower-half bundle of agent 2 ($G_{12}$) with $g$ to obtain

In $X^{\prime\prime}$, agent 2 is still strictly better off than in $X$ since by the definition of $G_{21}$, we have $(X_{1}\setminus G_{21})\cup g>_{2}X_{2}$. Thus, $X^{\prime\prime}$ Pareto dominates $X$. We still need to show that $X^{\prime\prime}$ is EFX. To this end, observe that as we have not changed the bundles of agents 1 and 3, there is no strong envy between them. So we only need to exclude strong envy edges to and from agent 2.

Nobody strongly envies agent 2: Note that 2 championed 1. Thus, $((X_{1}\setminus G_{21})\cup g)\setminus h\leq_{1}X_{1}$ and $((X_{1}\setminus G_{21})\cup g)\setminus h\leq_{3}X_{3}$ for all $h\in(X_{1}\setminus G_{21})\cup g$ by Observation 4 (part 1). Since both 1 and 3 are not worse off than before, they do not strongly envy 2.

Agent 2 does not envy anyone: We have that $(X_{1}\setminus G_{21})\cup g>_{2}X_{2}$. Also according to 2, the valuation of the current bundles of 1 and 3 is at most their previous one, and 2 did not envy them before (when he had $X_{2}$). Hence, 2 does not envy 1 and 3.

We have thus shown that $X^{\prime\prime}$ is EFX and Pareto dominates $X$. Actually, the strategy described above handles a more general situation. It yields a Pareto dominating EFX allocation as long as 3 envies neither 1 nor 2 initially, even if 1 and 2 envied (not strongly envied) 3 initially:

Let $X$ be an EFX allocation, and let $g$ be an unallocated good. If $M_{X}$ has a $2$-cycle, say involving agents 1 and 2, and agent 3 envies neither 1 nor 2, then there exists an EFX allocation $Y$ Pareto dominating $X$.

Remark 11 will be helpful when we deal with certain instances where $E_{X}$ has two sources later in Section 4.

2 No 22-cycle in MXM_{X}

We now consider the case when $M_{X}$ has no two cycle. Since $M_{X}$ is cyclic and we neither have a $1$-cycle nor a $2$-cycle, we must have a $3$-cycle. Let us assume w.l.o.g. that agent $i+1$ is the unique champion of agent $i$ (indices are modulo 3, so $i+1$ corresponds to $(i\bmod 3)+1$). Since, in addition, $i+1$ does not envy $i$, all three bundles decompose according to (2) and the current allocation can be written as

Let us collect what we know for agent 1’s valuation of the upper-half bundles: 1 uniquely champions 3, while 2 and 3 uniquely champion 1 and 2, respectively. Also, the current allocation is envy-free. Thus $X_{i}\geq X_{j}$ for all $i,j\in$. By Observation 10, we know that $X_{3}\setminus G_{13}>_{1}\max_{1}(X_{1}\setminus G_{21},X_{2}\setminus G_{32})$ $\max_{1}(X_{1}\setminus G_{21},X_{2}\setminus G_{32})$ is 1’s favorite bundle out of $X_{1}\setminus G_{21}$ and $X_{2}\setminus G_{32}$ ($X_{3}\setminus G_{13}$ is 1’s favorite upper-half bundle).

Now, let us collect what we know for agent 1’s valuation of the lower-half bundles: 1 champions 3 and does not envy 3’s bundle. Thus, by Observation 8, $G_{13}<_{1}g$ and $g\not\in G_{13}$. Also, 1 does not champion himself, and 3 champions 1. Thus, by Observation 9, $g\leq_{1}G_{21}$. We can make similar statements about agents 2 and 3. Since $g\not\in G_{21}$, and our instance is assumed to be non-degenerate, we even have $g<_{1}G_{21}$. Tables 1 and 2 summarize this information.

We first move to an allocation where everyone gets their favorite upper-half bundle (we achieve this by performing a cyclic shift of the upper-half bundles). Thus, the new allocation is:

Clearly, every agent is strictly better off, and thus, $X^{\prime}$ Pareto dominates $X$. If $X^{\prime}$ is EFX, we are done. So we assume otherwise. What envy edges could exist? We first observe that no agent will envy the agent from whom it took its upper-half during the cyclic shift.

In $X^{\prime}$, agent $i+1$ does not envy agent $i$ for all $i\in$ (indices are modulo 3).

We just show the proof for $i=1$, and the other cases follow symmetrically. Note that 2 values its current upper-half more than 1’s upper-half (it has its favorite upper-half): $X_{1}\setminus G_{21}>_{2}X_{3}\setminus G_{13}$. Similarly 2’s also values its lower-half more than 1’s lower-half: $G_{32}\geq_{2}g>_{2}G_{21}$. Therefore, 2 values his entire bundle more than 1’s bundle, and hence does not envy 1. ∎

Therefore, the only envy edges (and hence strong envy edges) can be from agent $i$ to agent $i+1$ as shown in the following figure. In the figures that follow, we use red edges to indicate strong envy, and blue edges to indicate weak envy.

$\scriptstyle{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mn>2</mn></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4511em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mtight">2</span></span></span></span></span></span>\scriptstyle{3}$ We now distinguish two cases depending on the number of such strong envy edges.

In this case, the envy-graph is a 3-cycle. We perform a cyclic shift of the bundles and obtain an EFX allocation Pareto dominating the initial allocation $X$.

At most two strong envy edges:

Note that in this case, there is a strong envy edge from at least one agent $i\in$ to $i+1$ and there is no strong envy edge from at least one agent $j\in$ to $j+1$. Let us assume without loss of generality that there is a strong envy edge from 1 to 2 , there may or may not be a strong envy edge from 2 to 3, and there is no strong envy edge from 3 to 1.

$\scriptstyle{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mn>2</mn></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4511em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mtight">2</span></span></span></span></span></span>\scriptstyle{3}$ Note that 1 is strictly better off in $X^{\prime}$ than in $X$. The existence of envy from 1 and 2, despite this improvement, allows us to say more about the preference ordering of the upper-half and the lower-half bundles.

If 1 envies 2 in $X^{\prime}$, $X_{1}\setminus G_{21}>_{1}X_{2}\setminus G_{32}$, and $G_{32}>_{1}G_{21}$.

We argue by contradiction. Therefore, assume that i.e. $X_{1}\setminus G_{21}\leq_{1}X_{2}\setminus G_{32}$ or $G_{32}\leq_{1}G_{21}$. If $X_{1}\setminus G_{21}\leq_{1}X_{2}\setminus G_{32}$, then

implying that 1 does not envy 2, a contradiction. If $G_{32}\leq_{1}G_{21}$, then

again implying that 1 does not envy 2, a contradiction. ∎

We replace the lower-half bundle of 2 ($G_{32}$) by $g$ to obtain

Note that agents 1 and 3 are still strictly better off (as we have not changed their bundles after the cyclic shift of the upper-half bundles) than in $X$. Agent 2 championed 1, thus, $X_{1}\setminus G_{21}\cup g>_{2}X_{2}$, and agent 2 is also strictly better off. Hence, $X^{\prime\prime}$ Pareto dominates $X$. If there are no strong envy edges, we are done. So assume otherwise. We first note that the only possible strong envy edge is from 2 to 3:

Agent 1 does not envy anyone: 1 did not envy 3 in $X^{\prime}$ and the bundles of 1 and 3 are the same in $X^{\prime}$ and $X^{\prime\prime}$. 1 does not envy 2 anymore as he prefers his own upper-half bundle and lower-half bundle to 2’s upper-half bundle and lower-half bundle respectively, i.e., $X_{3}\setminus G_{13}>_{1}X_{1}\setminus G_{21}$ (from Table 1) and $G_{21}\geq_{1}g$ (from Table 2).

Agent 3 does not envy anyone: We use a similar argument. 3 did not envy 1 in $X^{\prime}$ and the bundles of 1 and 3 are the same in $X^{\prime}$ and $X^{\prime\prime}$. 3 does not envy 2 as well as he prefers his own upper-half bundle and lower-half bundle to 2’s upper-half bundle and lower-half bundle respectively, namely $X_{2}\setminus G_{32}>_{3}X_{1}\setminus G_{21}$ (from Table 1) and $G_{13}\geq_{3}g$ (from Table 2).

Agent 2 does not envy 1: Note that agent 2 has his favorite upper-half bundle and values it more than 1’s upper-half bundle: $X_{1}\setminus G_{21}>_{2}X_{3}\setminus G_{13}$ (from Table 1) and 2 also values his lower-half bundle more than 1’s lower-half bundle: $g>_{2}G_{21}$ (from Table 2).

Therefore, the only possible strong envy edge is from 2 to 3 as shown below.

$\scriptstyle{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mn>2</mn></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4511em;"></span><span class="mord mtight sizing reset-size6 size3"><span class="mord mtight">2</span></span></span></span></span></span>\scriptstyle{3}$ Similar to Observation 13, we can now infer more about 2’s preference ordering for the bundles:

If 2 strongly envies 3 in $X^{\prime\prime}$, we have $X_{2}\setminus G_{32}>_{2}X_{3}\setminus G_{13}$ and $G_{13}>_{2}G_{32}$.