Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number

Introduction

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

Theorem 1. For all ε ∈ (0, 1=2], we can determine a partial allocation X and a set of unallocated goods P in polynomial time such that • X is (1 � ε)-EFX and • | P| ∈ O((n=ε) 4=5 ).

We remark that reducing the number of unallocated goods could be quite challenging. Indeed, a corollary on the bounded-charity result in Chaudhury et al. [20] already establishes that there exists a partial EFX allocation with at most two goods unallocated when there are three agents. However, removing the last two goods to obtain an EFX allocation for three agents turns out to be a highly nontrivial task, and the proof by Chaudhury et al. [19] requires careful and cumbersome case analysis. Furthermore, in the appendix, we show that the technique in Chaudhury et al. [19] does not extend to four agents with additive valuations for finding a (1 � ε)-EFX allocation.

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

Definition 1. For any positive integer d, the rainbow cycle number or R(d) is the largest k such that there exists a directed k-partite graph G � (∪ i∈ [k] V i , E) such that 1. |V i | ≤ d for all i ∈ [k]; 2. for any two distinct parts V i and V j in G, every vertex in V i has an incoming edge from a vertex in V j ; and 3. there exists no cycle in G that intersects each part at most once.

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

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

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

Observe that the definition of the rainbow cycle number (R(•)) is independent of the agents, goods, and valuation functions. In the second key result of this paper, we establish a direct relation between the rainbow cycle number and the existence of better EFX relaxations. Finding a good upper bound on the rainbow cycle number can get us weaker relaxations of EFX allocations (we can asymptotically improve the number of unallocated goods). Formally, we have Theorem 3. Theorem 3. Let ζ(n=ε) be the largest integer d such that d • R(d) ≤ n=ε for ε ∈ (0, 1=2]. Then, there is a (1 � ε)-EFX allocation X and a set of unallocated goods P such that |P| ≤ 4n=(ε • ζ(2n=ε)).

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

Note that the induced bipartite graph

. Thus, so far we have the following edges in 2).

We now look at the edges between the parts V 1 and

, it must also be a four cycle, and hence, in

there is an edge either from a 1 to c 1 or from c 1 to a 1 . If there is an edge from a 1 to c 1 , then we have a three-cycle a 1 → c 1 → b 2 → a 1 , which visits each part of G at most once, and thus, this is a contradiction. Similarly, if there is an edge from c 1 to a 1 , then also we have a three-cycle a 1 → b 1 → c 1 → a 1 , which visits each part of G at most once, and thus, this is also a contradiction.

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

Finding (12«)-EFX Allocations with High Nash Welfare

Let us recall that efficiency is also an important and desirable property of the allocations in fair division. The efficiency of an allocation is a measure of the overall welfare the allocation achieves. This is important as an envy-free allocation could be otherwise unsatisfactory; consider a simple instance with two agents 1 and 2 and two goods g 1 and g 2 . Let v 1 (g 1 ) � v 2 (g 2 ) � 1 and v 1 (g 2 ) � v 2 (g 1 ) � 0. Note that X 1 ← {g 2 } and X 2 ← {g 1 } are an EFX allocation as each bundle is a singleton, and following the removal of a single good results in an empty bundle, which is unenvied. However, there is clearly a better EFX allocation, where the individual and the total welfare are better, namely

Nash welfare of an allocation X defined as the geometric mean of the valuations of the agents, (

, is a popular measure of economic efficiency. 1 In fact, when agents have additive valuations, then the allocation with the highest Nash welfare is also EF1 (another popular fairness notion weaker than EFX). Unfortunately, maximizing Nash welfare is Approximable hard. However, there have been several approximation algorithms (Anari et al.

[7], Barman et al. [10], Cole and Gkatzelis [22]) that give a constant factor approximation. The best approximation ratio is e 1=e ≈ 1:445, given by Barman et al. [10].

Similar to the algorithm in Chaudhury et al. [20], we show that with minor modifications to our main algorithm, we can determine an allocation that satisfies the conditions in Theorem 1 and simultaneously achieves a 2e 1=e ≈ 2:88 approximation of the Nash welfare (i.e., in polynomial time, we can find efficient (1 � ε)-EFX allocation with a sublinear number of unallocated goods).

Theorem 4. For all ε ∈ (0, 1=2], we can determine a partial (1 � ε)-EFX allocation X and a set of unallocated goods P in polynomial time such that |P | ∈ O((n=ε) 4=5 ) and NW(X) ≥ (1=2:88) • NW(X * ), where X * is the allocation with the highest Nash welfare.

Further Related Work

Because the fair division literature is too vast, we restrict here to previous work that appears most relevant and refer the reader to recent surveys (Amanatidis et al. [6], Walsh [42]).

Fair division has received significant attention since the seminal work of Steinhaus [41] in the 1940s. Other than envy freeness, another fundamental fairness notion is that of proportionality. Recall that, in an envy-free allocation,

every agent values her own bundle at least as much as she values the bundle of any other agent. However, in a proportional allocation, each agent gets a bundle that is worth 1=n times her valuation on the entire set of goods. Because envy freeness and proportionality cannot always be guaranteed while dividing indivisible goods, various relaxations of the same have been studied. Alongside EFX, another popular relaxation of envy freeness is envy freeness up to one good (EF1), where no agent envies another agent following the removal of some good from the other agent's bundle. Although the existence of an EFX allocation is open, EF1 allocations are known to exist for any number of agents, even when agents have weakly monotone valuation functions (Lipton et al. [34]). Although 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 [16]. Although MMS allocations do not always exist (Kurokawa et al. [32]), there has been extensive work to come up with approximate MMS allocations (Amanatidis et al. [4], Barman and Krishnamurthy [9], Bouveret and Lemaître [14], Budish [16], Garg and Taki [29], Garg et al. [30], Ghodsi et al. [31], Kurokawa et al. [32]). Some works assume ordinal ranking over the goods as opposed to cardinal values (e.g., Aziz et al. [8], Brams et al. [15]).

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

A one-page abstract of our work appeared in Chaudhury et al. [21].

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

Our Techniques

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

Relation Between the Number of Unallocated Goods and the Rainbow Cycle Number

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

Most of the algorithms that have been used to prove the existence of relaxations of EFX allocations (Chaudhury et al. [19], Chaudhury et al. [20], Plaut and Roughgarden [39]) maintain a relaxed EFX allocation 2 X on the set of allocated goods, and as long as the envy graph E X and the set of unallocated goods satisfy some "properties," they determine another relaxed EFX allocation X ′ , in which φ(X ′ ) ≥ φ(X) + δ for some δ ≥ 1, where φ is an integral upper-bounded function. In that case, we say that the relaxed EFX allocation X ′ dominates the relaxed EFX allocation X. Because φ is integral and upper bounded, such a procedure will finally converge to a relaxed EFX allocation where the envy graph E X and the unallocated goods will not satisfy the said properties, and this will be the final allocation of the algorithms.

We now highlight another crucial concept used in these algorithms. The envy graph E X does not provide any information on an agent's valuations of the bundles formed by adding unallocated goods to the current bundles of the allocation. This information is crucial when we want to create another dominating relaxed EFX allocation by allocating some of the unallocated goods and unallocating some of the already allocated goods. The algorithms in Chaudhury et al. [19] and Chaudhury et al. [20] make use of this information through other concepts. For instance, Chaudhury et al. [19] and Chaudhury et al. [20] define champions 3 and champion graphs. Given an allocation

X and an unallocated good g, we say that an agent i is a champion for agent j w.r.t. g if there is a set S ⊆ X j ∪ {g} such that v i (X i ) < (1 � ε) • v i (S) and no agent (including i and j) envies S up to a factor of (1 � ε), following the removal of a single good (i.e., for all ℓ ∈ [n], we have 4 A champion graph w.r.t. an unallocated good g has vertices corresponding to the agents (similar to the envy graph), and there is an edge from agent i to agent j if agent i champions agent j w.r.t. g. Depending on the configuration of the envy graph and the champion graphs (one for each unallocated good), the current

However, when the number of agents is large, there are several different possible configurations of the champion graphs and the envy graph, and it is very hard and tedious to come up with better update rules. In this paper, we introduce the notion of a group champion graph, which is significantly more insightful and well structured than the champion graphs.

Given a (1 � ε)-EFX allocation X and a set of unallocated goods M ′ , we define the group champion graph. To this end, for each agent a ∈ [n], we assign a unique source s(a) in E X such that a is reachable from s(a) in E X (if there are multiple sources from which a is reachable in E X , then pick one source arbitrarily). The group champion graph of M ′ is a |M ′ | -partite graph G � (∪ g∈M ′ V g , E), in which each part V g contains a copy of the assigned sources of all the agents who find g "valuable." An agent a finds g valuable if v a ({g}) > ε • v a (X a ). There is an edge from vertex s(a) in V g to s(a ′ ) in V h if and only if a champions s(a ′ ) w.r.t. g (see Figure 3 for an illustration). At a high level, the group champion graph encodes the most relevant information from all the champion graphs. We make this point more explicit by briefly explaining how group champion graphs help us prove Theorem 3.

We first observe that if there is an unallocated good g and an agent i such that the other agents do not envy (X i ∪ {g}) \ g ′ up to a factor of (1 � ε) for all g ′ ∈ X i ∪ {g}, then we allocate g to i. Thus, we assume that for each unallocated good g and each agent i, there is an agent j that envies (X i ∪ {g}) \ g ′ up to a factor of (1 � ε) for some g ′ ∈ X i ∪ {g}. In particular, this implies that every unallocated good is valuable to some agent because if there is a good g that is not valuable to any agent (i.e., v i ({g}

), then we can simply allocate g to a source s in E X as no agent will envy the bundle X s ∪ {g} up to a factor of (1 � ε);

. Now, we classify the set of unallocated goods into two categories depending on how many agents find them valuable. We fix an integer d < n and define "high-demand goods" and "low-demand goods." A high-demand good is valuable to more than d agents, and a low-demand good is valuable to at most d agents. We show in Section 4 that if the number of high-demand goods is more than 2n=(ε • d), then we can determine a dominating (1 � ε)-EFX allocation from the existing (1 � ε)-EFX allocation. Thus, we may assume that the number of high-demand goods is at most 2n=(εd). We now bound the number of low-demand goods. Let M ′′ be the set of low-demand goods. We construct the group champion graph G � (∪ g∈M ′′ V g , E) of M ′′ , in which part V g contains the assigned sources of the agents who find g valuable. Note that for all g ∈ M ′′ , g is not valuable to more than d agents. Thus, |V g | ≤ d for all g ∈ M ′′ . Now, consider any two parts V g and V h in G. By our assumption, for all a ∈ V h , there is an agent who envies (X a ∪ {g}) \ g ′ up to a factor of (1 � ε) for some good g ′ ∈ X a ∪ {g}, implying that for each a in V h , there are agents who champion a w.r.t. g. We prove in Section 4 that because a is a source in E X , the agents who champion a w.r.t. g must find g valuable. Therefore, for all a ∈ V h , there is a source s(a ′ ) ∈ V g , Notes. We have an instance with six agents ∪ i∈[4] a i and ∪ i∈[2] b i and two unallocated goods, namely g a and g b . The agents ∪ i∈[4] a i find g a valuable, and the agents ∪ i∈[2] b i find g b valuable. The envy graph E X of the instance is shown in the left panel. E X shows that s(a 2 ) � a 1 , s(a 4 ) � a 3 , and s(b 2 ) � b 1 . Also, we have that agent a 2 champions all the agents with respect to (w.r.t.) g a and that b 2 champions all the agents w.r.t. g b . The group champion graph (right panel) has two parts: V ga corresponding to g a and V g b corresponding to g b . V ga contains the sources of all the agents who find g a valuable, namely a 1 and a 3 . Similarly, V g b contains b 1 . There is an edge from a 1 to b 1 as a 2 (which is reachable from a 1 in E X ) champions b 1 w.r.t. g a . Similarly, there is an edge from b 1 to a 1 and

where a ′ champions a w.r.t. g. Thus, every vertex in V h has an incoming edge from a vertex in V g . In Section 4, we further show that whenever G has a cycle that visits each part at most once, then we can determine a (1 � ε)-EFX allocation that dominates X. Therefore, we can assume that G has no cycle that visits each part at most once. Because G is an |M ′′ | -partite graph that satisfies the conditions in Definition 1, we have that the number of low-demand goods is

. By choosing the appropriate value for d, we arrive at the statement of Theorem 3.

We now elaborate that R(d) is indeed upper bounded, which then establishes the existence of (1 � ε)-EFX allocations with a sublinear number of unallocated goods.

Upper Bounds on the Rainbow Cycle Number

We briefly show that for any

have the same configuration if and only if for each directed edge from vertex (i, a) to (j, b) (and equivalently, from

there is an edge from (i ′ , a) to (j ′ , b) (and equivalently, from

and vice versa. We first show that if there are 4d parts in G, say without loss of generality (w.l.o.g.) V 1 , V 2 , : : : , V 4d , such that the induced directed bipartite graph G[V i ∪ V j ] has the same configuration for all 1 ≤ i < j ≤ 4d, then there exists a cycle in G that visits each part at most once.

Consider the parts V 1 and V 2 and the induced directed bipartite graph

Because every vertex in one part has an incoming edge from a vertex in the other part,

Clearly, C visits each part of G at most once. Therefore, there cannot be 4d parts in G such that the induced directed bipartite graph G[V i ∪ V j ] has the same configuration for all 1 ≤ i < j ≤ 4d.

We now rephrase the question about an upper bound on R(d). Let D be the set of all configurations of a directed bipartite graph, where the number of vertices in each part is at most d and every vertex has an incoming edge. We treat D as a set of colors and note that |D | ∈ 2 O(d 2 ) . Now, consider a complete graph K n with vertex set [n], where the vertex ℓ ∈ [n] corresponds to part V n in G. For all 1 ≤ i < j ≤ n, we color/label the edge (i, j) in K n with a color from D. The color on the edge (i, j) corresponds to the configuration of the directed bipartite graph

Clearly, R(d) must be strictly smaller than the largest n such that every coloring of the edges of K n with colors from D contains a monochromatic clique of size 4d. This value of n corresponds to the (multicolor) Ramsey number (Diestel [26]) R(n 1 , n 2 , : : :

This number is finite, and the current best-known upper bounds on it are exponential in |D | and d (Conlon and Ferber [23], Diestel [26], Erdős and Szekeres [27], Lefmann [33]). Therefore, R(d) is also bounded. However, this upper bound is very large and only provides a weak version of Theorem 1. This necessitates the study of finding "good" upper bounds on R(d): in particular, upper bounds that are polynomial in d. We address this in Section 5 by showing that R(d) ∈ O(d 4 ).

Preliminaries and Tools

A fair division instance is given by the three tuple 〈[n], M, V〉, where [n] is the set of agents, M is the set of indivisible goods, and V � {v 1 (), v 2 (), : : : , v n ()}, where each v i : 2 M → R ≥0 denotes the valuation function of agent i. We assume that agents have additive valuations (i.e., for all i ∈ [n], we have v i (S) � P g∈S v i ({g}) for all S ⊆ M). For the ease of notation, we write v i (g) instead of v i ({g}) and similarly, v i (S ∪ g) for v i (S ∪ {g}). We assume that v i (g) can be accessed in constant time for any i and g. For a fixed 0 < ɛ < 1 and an allocation X � (X 1 , : : : , X n ), we say that an agent i

• strongly envies a set S of goods if it heavily envies a proper subset of S; and

• is a most envious agent for a set S of goods if there exists a subset Z ⊆ S such that i heavily envies Z and no agent strongly envies Z. The pair (i, Z) is called a most-envious-agent-witness pair for S. We emphasize that the most envious agent of the set S is not necessarily the agent with the highest envy for S, but it is the agent who envies a subset of S that no other agent strongly envies.

An agent envies (heavily envies, strongly envies) an agent j if it has these feelings for the set X j . Clearly, strong envy implies heavy envy implies envy. An allocation X ′ ε-strongly Pareto dominates an allocation X or equivalently,

and for some agent j ∈ [n], we have

. At a high level, our algorithm is similar to previous algorithms used to prove the existence of relaxations of EFX allocations (Chaudhury et al. [19], Chaudhury et al. [20], Plaut and Roughgarden [39]). Our algorithm always maintains a (1 � ε)-EFX allocation on the set of allocated goods, and as long as the current allocation and the set of unallocated goods P satisfy "some properties," it determines another (1 � ε)-EFX allocation that ε-strongly Pareto dominates the previous (1 � ε)-EFX allocation. Because the valuation of an agent for the entire good set is bounded, this procedure will eventually converge to a (1 � ε)-EFX allocation, where the current allocation and the set of unallocated goods do not satisfy these properties. The bulk of the effort goes into determining the right properties under which one can come up with update rules that transform one (1 � ε)-EFX allocation into a "better" (1 � ε)-EFX allocation. We briefly recollect the update rules used in Chaudhury et al. [20] and Lipton et al. [34].

Envy Cycle Elimination (Lipton et al. [34])

The envy graph E X of a (1 � ε)-EFX allocation X has the agents as its vertex set, and there is an edge from vertex i to vertex j in E X if agent i envies agent j (i.e., v i (X i ) < v i (X j )). The paper by Lipton et al. [34] shows that whenever E X has a cycle, then one can determine another (1 � ε)-EFX allocation X ′ in which no agent has a worse bundle and E X ′ is acyclic. Formally, we have Lemma 1.

Lemma 1 (Lipton et al. [34]). Consider a (1 � ε)-EFX allocation X. If there is a cycle in E X , then in polynomial time, we can determine a

, and E X ′ is acyclic. 5

Update Rules in Chaudhury et al. [20]

We modify the update rules in Chaudhury et al. [20] slightly, as we are dealing with (1 � ε)-EFX allocations and not EFX allocations. These rules are more involved and make essential use of the concept of a most envious agent.

Lemma 2. Consider an allocation X and a set S ⊆ M. If there is an agent who heavily envies the bundle S, then we can determine a most-envious-agent-witness pair (t, Z) for S in O(n • | S| 2 ) time. If there is an agent who strongly envies S, then t strongly envies S.

Proof. Let i be an agent who heavily envies S. We construct a sequence (t ℓ , Z ℓ ) as follows; initially, we set t 1 to i and Z 1 to S. Assume that (t ℓ�1 , Z ℓ�1 ) is defined. If no agent (including t ℓ�1 ) strongly envies Z ℓ�1 , then we stop. Otherwise, let i ′ be an agent such that

. We set t ℓ to i ′ and Z ℓ to Z ℓ�1 \ {g} and continue. We will eventually stop as with every next pair in the sequence, the size of the set Z ℓ decreases by one. Say we stop at ℓ * . Then, we have an agent t ℓ * that heavily envies the subset Z ℓ * of S. Moreover, no agent strongly envies Z ℓ * . Thus, (t ℓ * , Z ℓ * ) is a most-envious-agent-witness pair.

If there is an agent who strongly envies S, then ℓ ≥ 1, and hence, t ℓ * heavily envies a proper subset of S. Thus, t ℓ * strongly envies S.

It is clear that we can determine the pair in O(n • |S| 2 ) time; the maximum length of the sequence constructed is | S| + 1 as the size of the set Z ℓ � | S| + 1 � ℓ. We need time O(n |S|) to determine v i (S) for all i and can update any such value in time O(1) after the removal of an element. For each value of ℓ, it takes O(n

For an allocation X and a set S of goods that is heavily envied by some agent, let (t, Z) be the pair returned by the procedure in Lemma 2. Now, for notational convenience only, we introduce a slightly different definition of champions. We call t the champion of S and Z the corresponding witness. We now state the update rules.

Update Rule U 1 (Chaudhury et al. [20])

The first rule is the simplest. It is applicable whenever we can allocate an unallocated good to an unenvied agent (a source in E X ) without creating any strong envy. In this case, we simply allocate this good to the corresponding source. This creates another (1 � ε)-EFX allocation where no agent gets a worse bundle and the number of unallocated goods decreases.

Lemma 3 (U 1 (Chaudhury et al. [20])). Consider a (1 � ε)-EFX allocation X. If there is a source s in E X and an unallocated good g such that no agent strongly envies X s ∪ g, then X ′ � 〈X 1 , X 2 , : : : , X s ∪ g, : : :

Note that there can be at most m consecutive applications of this rule as the number of unallocated goods decreases by one every time we apply this update rule. The remaining rules are applicable whenever there are either "valuable" goods unallocated or if "too many" goods are unallocated. We state the second update rule.

Update Rule U 2 (Chaudhury et al. [20])

This update rule is applicable if there is an agent i ∈ [n] who heavily envies the set of unallocated goods P. In this case, let t be the champion of P and Z be the corresponding witness. In X ′ , one assigns Z to t and changes the pool to X t ∪ (P \ Z). The resulting allocation X ′ is EFX and ε-strongly Pareto dominates X. Lemma 4. (U 2 (Chaudhury et al. [20])). Consider a (1 � ε)-EFX allocation X, and let P be the set of unallocated goods. If there is an agent i ∈ [n] that heavily envies P, then in polynomial time, we can determine a (1 � ε)-EFX allocation X ′ > PD(ε) X.

The third update rule is a refinement of envy-cycle elimination.

Update Rule U 3 (Chaudhury et al. [20])

This rule is applicable whenever the number of unallocated goods is at least the number of agents. Chaudhury et al. [20]) shows that when the number of unallocated goods is larger than the number of agents and when rule U 1 is no longer applicable, then in polynomial time, we can find a set of sources s 1 , s 2 , : : : , s ℓ in E X ; a set of unallocated goods g 1 , g 2 , : : : , g ℓ ; and a set of agents t 1 , t 2 , : : : , t ℓ such that each t i is reachable from s i in E X , the paths from s i to t i for all i ∈ [ℓ] are disjoint, and t i is the champion of X s i+1 ∪ g i+1 (indices are modulo ℓ). Then, one essentially proceeds as in cycle elimination. Let Z i+1 ⊆ X s i+1 ∪ g i+1 be the witness corresponding to t i . For each I, one assigns Z i+1 to t i , and to each agent on the path from s i to t i except for t i , one assigns the bundle owned by the successor on the path. The resulting allocation X ′ is EFX and ε-strongly Pareto dominates X.

Lemma 5 (U 3 (Chaudhury et al. [20])). Consider a (1 � ε)-EFX allocation X. If there exists a set of sources s 1 , s 2 , : : : s ℓ in E X ; a set of unallocated goods g 1 , g 2 , : : : , g ℓ ; and a set of agents t 1 , t 2 , : : : , t ℓ such that each t i is reachable from s i in E X , the paths from s i to t i for all i ∈ [ℓ] are disjoint, and t i is the champion of X s i+1 ∪ g i+1 (indices are modulo ℓ), then in polynomial time, we can determine a (1 � ε)-EFX allocation X ′ > PD(ε) X.

Relating the Number of Unallocated Goods to the Rainbow Cycle Number

In this section, we give the proof of Theorem 3 (i.e., we show how any upper bound on R(d) allows us to obtain a (1 � ε)-EFX with sublinear many goods unallocated). More precisely, we show that given a (1 � ε)-EFX allocation X, if E X is acyclic, the update rules U 1 and U 2 are not applicable, and the number of unallocated goods is larger than 4n=(ε • ζ(2n=ε)), then rule U 3 is applicable. Therefore, for most of this section, we proceed under the assumption that (*) E X is acyclic and the update rules U 1 (Lemma 3) and U 2 (Lemma 4) are not applicable:

We start with some definitions. We first make an observation about the agents who could potentially strongly envy X s ∪ g, where s is a source in E X and g is an unallocated good.

Observation 1. Consider an unallocated good g and any source s in E X . If agent i heavily envies X s ∪ g, then g is valuable to agent i.

Note that under assumption (*) for each unallocated good g and each source s in the envy graph, there is an agent who strongly envies X s ∪ g (because the conditions of the update rule U 1 in Lemma 3 are not satisfied). Thus, each unallocated good is valuable to some agent. Now, we make a classification of the unallocated goods based on the number of agents who find them valuable. To be precise, given an allocation X, we classify the unallocated goods into two categories: high-demand goods H X and low-demand goods L X . A good g belongs to H X if it is valuable to at least d + 1 agents and to L X if it is valuable to at most d agents. We will choose the exact value of d later (right now, just think of it as any integer less than n). Observe that the set of unallocated goods P � H X ∪ L X . To prove our claim, it suffices to show that when |H

the rule U 3 is applicable. To this end, we first make a simple observation about | H X |. Observation 2. Under assumption (*), we have | H X | < 2n=(ε • d). Proof. For each good g ∈ H X , let η g be the number of agents who find g valuable. By definition of H X , we have that η g > d, and hence, P g η g > |H X |d. We next upper bound P g η g by n • (2=ε) by showing that at most 2=ε unallocated goods are valuable to any agent. Chaudhury et al.: Improving EFX Guarantees Through Rainbow Cycle Number Mathematics of Operations Research, 2024, vol. 49, no. 4, pp. 2323-2340, © 2023 INFORMS

Consider any agent i. By assumption (*) rule, U 2 is not applicable, and hence, the value of the unallocated goods to i is at most 1=(1 � ε)v i (X i ). This is at most 2v i (X i ) because ε ≤ 1=2. Any valuable good has a value at least εv i (X i ) for i. Thus, the number of unallocated goods valuable to i is at most 2=ε. w

We next bound |L X |. In particular, we show that |L X | ≤ R(d). To this end, we introduce the notion of group champion graph G.

Group Champion Graph

Recall that we are operating under assumption (*), and hence, E X is acyclic. Given E X and the sources in E X , we fix an arbitrary total order ⋏ among the sources. To each agent a, we assign a source s(a) such that a is reachable from s(a) in the envy graph E X (note that a can coincide with s(a)). If a is reachable from multiple sources, we pick s(a) to be the source with the highest rank in the order ⋏ . However, once picked, s(a) is fixed and remains unique throughout our algorithm and its analysis. Let k :� |L X | . For each g ∈ L X , let Q g be the set of all agents who find g valuable. By definition of L X , we have |Q g | ≤ d for all g ∈ L X . We now define a k-partite graph G � (∪ g∈L X V g , E), in which the part V g corresponding to g consists of copies of the sources assigned to the agents in Q g : formally, V g � {(g, s(a)) | a ∈ Q g }. For any goods g and h and agents a ∈ Q g and b ∈ Q h , there is an edge from (g, s(a)) in V g to (h, s(b)) in V h if and only if a is the champion of X s(b) ∪ g. We now make a claim about the set of edges between V g and V h in G for any g, h ∈ L X . Lemma 6. Under assumption (*), consider any g, h ∈ L X . Then, each vertex in V h has an incoming edge from a vertex in V g .

Proof. Consider any vertex (h, s(b))

∈ V h . By assumption (*), there is an agent who strongly envies the bundle X s(b) ∪ g. Otherwise, rule U 1 would be applicable. By Observation 1, all agents who strongly envy X s(b) ∪ g consider g valuable and hence, belong to Q g . Let a be the champion of X s(b) ∪ g. By Lemma 2, a strongly envies X s(b) ∪ g and hence, belongs to Q g . Thus, there is an edge from (g, s(a)) in V g to (h, s(b)) in V h (by the construction of G). w Now, we claim that the existence of a cycle that visits each part of G at most once would imply the existence of a (1 � ε)-EFX allocation that ε-strongly Pareto dominates the existing (1 � ε)-EFX allocation.

Lemma 7. Given a cycle C in G that contains at most one vertex from each V g , for all g ∈ L X , we can determine a (1 � ε)-EFX allocation X ′ > PD(ε) X in polynomial time.

Proof. Let C � (g i+1 , s i ) → (g i+2 , s i+1 ) → ⋯ → (g j+1 , s j ) → (g i+1 , s i ) be a cycle in G that visits each part at most once. It will become clear why we index the g's starting at i + 1. Consider the sequence s i , s i+1 , : : : , s j . If all the sources in this sequence are not distinct, there exists a contiguous subsequence s i ′ , s i ′ +1 , : : : , s j ′ where all the sources are distinct and s j ′ +1 � s i ′ with i ≤ i ′ < j ′ ≤ j (index j + 1 is to be interpreted as i).

We now work with the sequence s i ′ , s i ′ +1 , : : : , s j ′ where all the sources are distinct and s j ′ +1 � s i ′ . For all ℓ ∈ [i ′ + 1, j ′ + 1], the existence of the edge (g ℓ , s ℓ�1 ) → (g ℓ+1 , s ℓ ) implies the existence of an agent t ℓ�1 such that t ℓ�1 is the champion of X s ℓ ∪ g ℓ and s(t ℓ�1 ) � s ℓ�1 (i.e., t ℓ�1 is reachable from s ℓ�1 in E X ). Furthermore, note that the paths from s ℓ�1 to t ℓ�1 for all ℓ ∈ [i ′ + 1, j ′ + 1] are disjoint. Assume otherwise, and let there be an intersection between paths from s a to t a and from s b to t b and w.l.o.g. s a ⋏ s b . Note that because the paths intersect, both t a and t b are reachable from s b , and s a ⋏ s b , we have s(t a ) ≠ s a , which is a contradiction. Because the sources s i ′ , s i ′ +1 , : : : , s j ′ are distinct, the agents a i ′ , a i ′ +1 , : : : , a j ′ are also distinct (as each agent has a unique source assigned). Therefore, we have distinct sources s i ′ , : : : , s j ′ in E X ; distinct goods g j ′ +1 , g i ′ +1 , : : : , g j ′ ; and distinct agents t i ′ , : : : t j ′ that satisfy the conditions under which the update rule U 3 (Lemma 5) is applicable. By applying U 3 , we can get a

We clarify a boundary case of this analysis. Note that in principle, the length of the contiguous subsequence could be also one (i.e., i ′ � j ′ ). In this case, it means that there is an agent t i ′ , reachable from s i ′ in E X , who is the champion of X s i ′ ∪ g i ′ +1 (i.e., the most envious agent of X s i ′ ∪ g i ′ +1 is reachable from s i , and thus, we apply rule U 3 and get a (1 � ε)-EFX allocation X ′ > PD(ε) X). w With Lemma 7, we are now ready to give an upper bound on | L X |. Observe that |L X | equals the number of parts in G. Now, the question is how many parts can G have such that it does not admit a cycle that visits each part at most once. This is where we upper bound |L X | with the rainbow cycle number.

where k is the number of parts in G. Note that each part of G corresponds to the sources assigned to the agents who find a particular good in L X valuable (Q g for some g ∈ L X ). By definition of L X , there are at most d agents who find a good in L X valuable. Thus, each part has at most d vertices. Again, by Lemma 6, between any two parts V g and V h of G, each vertex in V h has an incoming edge from a vertex in V g . Therefore, by Definition 1, we have that if k > R(d), then there exists a cycle C in G that visits each part at most once. Once we have C, by Lemma 7, we can determine a

, Lemma 8 only gives the existence of a (1 � ε)-EFX allocation X ′ > PD(ε) X. However, to determine X ′ in polynomial time, one needs to find a cycle C in G that visits each part at most once when |L X | > R(d) in polynomial time. Let us remark that this is a nontrivial problem in general, reminiscent of the well-known K-PATH and K-CYCLE problems, which are nondeterministic polynomial-time complete (Cygan et al. [24]). Here, the input is a (di-)graph G and an integer k, and the objective is to determine if there is a path (cycle) on at least k-distinct vertices of the graph. These problems can be solved in 2 O(k) • poly(n) time using techniques based on color coding, hash functions, and splitters (Alon et al. [2], Cygan et al. [24], Naor et al. [38]). In particular, we can reduce K-PATH to the following problem in polynomial time. Find a k-path in a colorful graph on n vertices, whose vertices have been colored with O(poly(k) • log n) colors, such that every vertex of the k-path has a distinct color. However, for our purposes, the construction of the cycle C in G is a part of the proof of Theorem 6 (described in Section 5); we show that in polynomial time, one can find a cycle in a (d 4 + d)-partite digraph, in which each part has at most d vertices and for any two parts V and V ′ in the digraph, every vertex in V ′ has an incoming edge from some vertex in V and vice versa. This implies that if |L X | > d 4 + d, then in polynomial time, we can determine a cycle C in G that visits each part at most once and then determine a (1 � ε)-EFX allocation X ′ > PD(ε) X by applying U 3 . This also implies that R(d) ≤ d 4 + d. Therefore, we have Lemma 9.

Putting it Together

We give the existence proof and indicate the appropriate changes required for the polynomial-time algorithm. We start with an empty allocation, which is trivially a (1 � ε)-EFX. Then, the algorithm iteratively maintains a (1 � ε)-EFX allocation X and a pool of unallocated goods. In each iteration, the algorithm first makes E X acyclic in polynomial time by Lemma 1. Thereafter, the algorithm checks whether any one of the update rules U 1 and U 2 is applicable. If U 1 is applicable, then it determines a (1 � ε)-EFX allocation X ′ , where v i (X ′ i ) ≥ v i (X i ) for all i ∈ [n] and the number of unallocated goods reduces. If U 2 is applicable, then it determines a (1 � ε)-EFX allocation X ′ > PD(ε) X. If neither U 1 nor U 2 is applicable, then it determines the sets H X and L X . By Lemma 2, we have

then it returns the allocation X. Otherwise, it determines a cycle that visits each part of G at most once and then determines (1 � ε)-EFX allocation X ′ > PD(ε) X by applying update rule U 3 , as in Lemma 8. If |L X | > d 4 + d, the cycle can be determined in polynomial time. Therefore, when the algorithm terminates, we have that

We now state the explicit value of d first for the existence proof. We choose d as the largest integer such that

Therefore, the number of unallocated goods is at most 4n=(ε

For the algorithmic result, we choose d as the smallest integer such that 2n=(ε • d) ≤ 2d 4 . Then, d � ⌈(n=ε) 1=5 ⌉, and the number of unallocated goods is at most 4⌈(n=ε

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

• applying U 1 ,

• applying U 2 , or • determining a cycle C that visits each part in G at most once and then applying U 3 . Note that the initial envy-cycle elimination and subsequent application of all of the procedures ensure that v i (X ′ i ) ≥ v i (X i ) for all i ∈ [n] (Lemmas 1 and 3-5). Thus, throughout the algorithm, the valuation of an agent never decreases. Note that there cannot be more than m consecutive applications of U 1 , as the number of unallocated goods decreases with each application of U 1 . Every time we apply U 2 or U 3 , we ensure that X ′ > PD(ε) X, implying that the valuation of some agent improves by a factor of at least (1 + ε). Because each agent's valuation is bounded by W � max i∈ [n] v i (M) and the valuation of an agent never decreases throughout the algorithm, we can have at most poly(n, m, log W, 1=ε) many iterations that involve applications of U 2 and U 3 . Therefore, the total number of iterations of our algorithm is m • (iterations involving application of U 2 or U 3 ), which is also poly(n, m, log W, 1=ε).

Notice that in the algorithmic case, each of the iterations can also be implemented in polynomial time; U 1 and U 2 can be implemented in polynomial time (Lemmas 3 and 4). When |L X | ≥ 2d 4 ≥ d 4 + d, then in polynomial time, we can determine the cycle C and apply U 3 (Lemma 9). We can now state the main result of this section.

Theorem 5. There exists a (1 � ε)-EFX allocation X and a set of unallocated goods P such that | P| ≤ 4n=(ε • ζ(2n=ε)). In polynomial time, we can find a (1 � ε)-EFX allocation and a set P of unallocated goods such that |P | ∈ O((n=ε) 4=5 ).

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

Bounds on the Rainbow Cycle Number

In this section, we give the proof of Theorem 2. We briefly recall the setup. There is a k-partite digraph G � (∪ i∈[k] V i , E G ) such that each part has at most d vertices. For every pair of distinct parts V i and V j , every vertex in V j has an incoming edge from some vertex in V i . There is no cycle in G that visits each part at most once. Our goal is to establish an upper bound on k.

We now introduce some helpful notations and concepts. For each i ∈ [k], we represent the vertices in the part V i as (i, vertex id) (i.e., V i � {(i, 1), (i, 2), : : : We prove Theorem 2 by contradiction. To be precise, we show that if k > d 4 + d, then there exists a cycle in G that visits every part at most once. Moreover, this cycle can be found in time polynomial in k.

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

For each ordered pair (i, j)

we define a d 2 -dimensional vector u i, j, ℓ as follows; for all x ∈ [d] and y ∈ [d], we set u i, j, ℓ [σ d (x, y)] � 1 if and only if there exists a path (i, x) → (ℓ, z) → (j, y) in G for some (ℓ, z) ∈ V ℓ (i.e., if there exists a path from vertex (i, x) in V i to vertex (j, y) in V j through some vertex in V ℓ ). Otherwise, we set

we construct the sets B i, j and L i, j as follows. For each (i, j) taken in the increasing order of σ d (i, j), define L i, j � L and B i, j as a representative vector set of {u i, j, ℓ |ℓ ∈ L i, j } of size at most d 2 . A set B i, j of this size exists because our vectors have dimension d 2 . Then, we set L � L \ {ℓ |u i, j, ℓ ∈ B i, j }. At most, d 2 elements are removed from L in each iteration.

For clarity, we write L f to denote the set L at the end of the construction. Observe that |L f | ≥ 1. This holds because we start with a set of size larger than d 4 and remove at most d 2 elements in each of the d 2 iterations.

Proof. Let us assume without loss of generality that σ d (i, j) < σ d (i ′ , j ′ ). Consider any ℓ such that u i, j, ℓ ∈ B i, j . Then, ℓ is removed from L at the end of the iteration for the pair (i, j) and hence, does not belong to L at the beginning of the iteration for the pair (i ′ , j ′ ). Consequently,

At the end of the construction, we arbitrarily pick a l ∈ L f (this is possible as L f ≠ ∅). Now, we make a small observation about the vector u i, j, l for all i, j ∈ [d].

Observation 5. For all i, j ∈ [d], if u i, j, l [q] � 1 for some q ∈ [d 2 ], then there exists a vector u i, j, l ′ ∈ B i, j such that u i, j, l ′ [q] � 1.

Proof. Observe that L f ⊆ L i, j . Therefore, l ∈ L i, j . By definition, B i, j is a representative vector set of {u i, j, ℓ | ℓ ∈ L i, j }. Therefore, by the definition of representative set, there exists a vector u i, j, ℓ ′ ∈ B i, j such that u i, j, ℓ ′ [q] � 1. w

We are now ready for the construction of a cycle that visits each part at most once. We first show that there exists a cycle C in G that visits only the parts V l , V 1 , … , V d and each of the parts V 1 , … , V d at most once (i.e., the only part it may visit more than once is V l ). See Figure 4 for an illustration.

Let ( l, w d ) be an arbitrary vertex in V l . We construct a path

by starting at ( l, w d ) and tracing backward. We start in ( l, w d ). Assume that we already traced back to ( l, w i ) with i � d initially. By the construction of G, there must be an edge from some vertex (i, v i ) in V i to ( l, w i ) in V l , and there must be an edge from some vertex ( l, w i�1 ) in V l to (i, v i ) in V i . Thus, there is the path ( l, w i�1 ) → (i, v i ) → ( l, w i ) in G. We keep continuing this procedure until we reach ( l, w 0 ).

Because the part V l can have at most d vertices, by the pigeonhole principle, there must be i and j with 0 ≤ i < j ≤ d such that w i � w j . Let C be the subpath from ( l, w i ) to ( l, w j ): that is,

Observe that C visits all the parts of G except V l at most once. We now show that by using "bypass" parts, we can make the cycle simple. For clarity, we rewrite C as

Making the Cycle Simple

For all q ∈ [i + 1, j], consider the subpath (q, v q ) → ( l, w q ) → (q + 1, v q+1 ) of C (index j + 1 is to be interpreted as i + 1). The existence of such a subpath in G implies that u q, q+1, l [σ d (v q , v q+1 )] � 1. By Observation 5, we know that there is a vector u q, q+1, ℓ q ∈ B q, q+1 such that u q, q+1, ℓ q [σ d (v q , v q+1 )] � 1. This Notes. The cycle in the figure visits the parts V 1 , V 2 , and V 3 exactly once and the part Vl three times. It is given by ( l, w

implies that there exists a part V ℓ q and a vertex (ℓ , y q ) in part V ℓ q such that there is a subpath (q, v q ) → (ℓ q , y q ) → (q + 1, v q+1 ):

By Observation 4, we have that ℓ q ≠ ℓ q ′ for all q ≠ q ′ . Therefore, we have a simple cycle C ′ in G that visits each part in G at most once; namely,

See Figure 5 for an illustration of this entire procedure.

Therefore, if k > d 4 + d, then there exists a cycle in G that visits each part at most once. Moreover, this cycle can be found in time polynomial in k. With this, we arrive at the main result of this section. Notes. We take the instance in Figure 4, where there exists a cycle C that visits every part other than Vl at most once. The edges of the cycle C are light in color. The figure shows how to obtain a cycle C ′ that visits every part at most once from C. The edges of C ′ are dark in color. For all i ∈ [3], we replace the subpath in C of the form An improved upper bound on R(d) would imply a better bound on the number of unallocated goods. However, we show that an exponential improvement (e.g., R(d) ∈ poly(log(d))) is not possible by showing a linear lower bound (i.e., R(d) ≥ d)). However, this still leaves room for polynomial improvement, and we suspect that R(d) ∈ O(d). This would imply the existence of a (1 � ε)-EFX allocation with O( ffi ffi ffi ffi ffi ffi ffi ffi n=ε p ) many goods unallocated. For a polynomial-time algorithm, the construction of a cycle as in Theorem 6 would have to be polynomial time. However, we remark that this is an initiation study for determining (1 � ε)-EFX allocations with a sublinear number of unallocated goods, and we use concepts like the group champion graph that are natural extensions of the champion graph. We believe that this still leaves room for developing more sophisticated concepts and techniques that may reduce the number of unallocated goods to o( ffi ffi ffi ffi ffi ffi ffi ffi n=ε p ).

Lower Bound on R(d)

We show that R(d) ≥ d. We construct a d-partite graph G � (∪ i∈[d] V i , E) such that each part V i has d vertices; for all pairs of parts V i and V j , every vertex in V j has an incoming edge from a vertex in V i and vice versa; and there exists no cycle that visits each part at most once. We now define the edges in G. Let V i � {(i, 0), (i, 1), : : : , (i, d � 1)}. Consider any i and j such that i < j. For each 0 ≤ ℓ ≤ d � 1, we have an edge from (i, ℓ) in V i to (j, ℓ) in V j , and there is an edge from (j, ℓ) in V j to (i, (ℓ + 1) mod d) in V i (see Figure 6 for an illustration). One can easily verify that for all parts V i and V j , every vertex in part V j has an incoming edge from part V i and vice versa. It suffices to show that G admits no cycle that visits each part at most once. Lemma 10. There exists no cycle in G that visits each part at most once.

Proof. We prove by contradiction. Assume that there is a cycle C � (i 1 , ℓ 1 ) → (i 2 , ℓ 2 ) → ⋯ → (i r , ℓ r ) → (i 1 , ℓ 1 ) that visits each part at most once (i.e., i x ≠ i y for all x, y ∈ [r]). From here on, all the indices are modulo r. Note that by the construction of the edges of G, for all q ∈ [r], we have ℓ q+1 � ℓ q if i q < i q+1 and ℓ q+1 � (ℓ q + 1) mod d if i q > i q+1 . Let # 1 � |{q ∈ [r] |i q > i q+1 } | (recall that r + 1 is one). The existence of the cycle C in G implies that ℓ 1 � (ℓ 1 + # 1 ) mod d.

Because i x ≠ i y for all x, y ∈ [r] and there exists the cycle C in G, there are indices q ′ and q ′′ such that i q ′ > i q ′ +1 and i q ′′ < i q ′′ +1 , further implying that 1 ≤ # 1 ≤ r � 1. Because G has d parts, we have r ≤ d, implying that 1 ≤ # 1 ≤ d � 1. However, this implies that (ℓ 1 + # 1 ) mod d ≠ ℓ 1 , which is a contradiction. w

Finding Efficient (12«)-EFX Allocations with a Sublinear Number of Unallocated Goods

We note that like the algorithms in Chaudhury et al. [20] and Plaut and Roughgarden [39], our algorithm is flexible with the initialization (i.e., starting with any initial (1 � ε)-EFX allocation X, it can determine a final (1 � ε)-EFX allocation Y with at most O((n=ε) 4=5 ) many goods unallocated and v i (Y i ) ≥ v i (X i ) for all i ∈ [n]). This is a consequence of the fact that the valuation of an agent never decreases throughout our algorithm. Therefore, our algorithm maintains the welfare of the initial allocation. Thus, if we choose the initial (1 � ε)-EFX allocation carefully, we can also guarantee high Nash welfare for our final (1 � ε)-EFX allocation with sublinear many goods unallocated. To this end, we use an important result from Caragiannis et al. [17] about determining partial EFX allocations with high Nash welfare in polynomial time.

Theorem 7 (Caragiannis et al. [17]). In polynomial time, we can determine a partial EFX allocation X such that NW(X) ≥ 1=(2:88) • NW(X * ), where X * is the Nash welfare-maximizing allocation. In fact, the result in Caragiannis et al. [17] shows the existence of partial EFX allocations that achieve a 1/2 approximation of the Nash welfare. However, in polynomial time, one can only find a partial EFX allocation with a 1=2:88 approximation of the Nash welfare.

Let X be the partial EFX allocation that achieves a 2.88 approximation of the Nash welfare. We run our algorithm starting with X as the initial allocation. The final (1 � ε)-EFX allocation with sublinear many unallocated goods is also a 2.88 approximation of the Nash welfare as the valuations of the agents in the final allocation are at least their valuations in X. Therefore, we have the following theorem. Theorem 8. In polynomial time, we can determine a (1 � ε)-EFX allocation X with O((n=ε) 4=5 ) goods unallocated such that NW(X) ≥ 1=(2:88) • NW(X * ), where X * is the Nash welfare-maximizing allocation. Furthermore, using the existence of partial EFX allocations with 1/2 approximation to Nash welfare (Caragiannis et al. [17]), there exists a (1 � ε)-EFX allocation X with O((n=ε) 4=5 ) goods unallocated such that NW(X) ≥ 1=2 • NW(X * ).

Table A.1. An instance where showing that the technique in Chaudhury et al. [19] cannot be used to determine (1 � ε)-EFX allocations with four agents. g 1 g 2 g 3 g 4 g 5 g 6 g 7 g 8 g 9 a 0 0 0 0 0 0 6 4 0 b 16 4 24 4 0 34 31 0 2 c 10 0 18 8 20 0 29 0 6 d 0 0 0 0 18 20 19 0 4

Notes. In particular, given a (1 � ε)-EFX allocation X and the unallocated good g 9 , there is no complete (1 � ε)-EFX allocation where the valuation of agent a does not strictly decrease (i.e., in any complete (1 � ε)-EFX allocations Y, we have v a (Y a ) < v a (X a )).

Chaudhury et al.: Improving EFX Guarantees Through Rainbow Cycle Number

Mathematics of Operations Research, 2024, vol. 49, no. 4, pp. 2323-2340, © 2023 INFORMS Downloaded from informs.org by [2620:0:e00:4037::12f] on 18 February 2025, at 20:18 . For personal use only, all rights reserved.