On the Pursuit of EFX for Chores: Non-existence and Approximations

1 Introduction

Fair Division has been widely studied in the past decade, yielding a series of results for various fairness notions. One of the most popular notions is envy-freeness (EF), under which each agent (weakly) prefers her own bundle to any other agent's bundle. In the case of divisible items, an EF allocation is always guaranteed to exist, while for indivisible items this is not always the case; consider for instance a scenario where we have to allocate a single item among two agents. This fact has led to numerous relaxations of envy-freeness and approximations thereof.

One such notion is that of envy-freeness up to one item (EF1) [Budish, 2011]. In EF1 allocations, an agent i might envy agent j but the envy is eliminated after hypothetically removing some item; either a good from agent j's bundle or a chore from agent i's bundle. EF1 allocations are known to exist for both goods [Lipton et al., 2004] and chores [Bhaskar et al., 2021; Aziz et al., 2021].

A stronger variant is that of envy-freeness up to any item (EFX); an allocation is said to be EFX if envy vanishes after the removal of any item. The existence of EFX allocations remains a challenging open problem in the area and has been even deemed as "fair division's most enigmatic question" [Procaccia, 2020]. EFX is known to exist for special cases: two agents with general valuations [Plaut and Roughgarden, 2020], and three additive agents [Chaudhury et al., 2020] 1 . In contrast to the fruitful agenda on EFX for goods, the landscape of EFX allocations is less explored in the context of chores. For instance, even the existence for three additive agents as well as a constant factor approximation is elusive.

The problem of EFX allocations remains open, even for additive valuations, in the context of goods, "despite significant effort" [Caragiannis et al., 2019]. Moreover, it has been suggested by Plaut and Roughgarden that EFX allocations may fail to exist:

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.

We verify the aforementioned suspicion, answering the analogous question of whether an EFX allocation always exists for chores to the negative. No such counterexample was known even in the setting of general monotone valuations, either for the goods or the chores setting. In fact, the only known counterexamples for the non-existence of EFX allocations employ mixed manna, i.e., mixtures of goods and chores, therefore non-monotone valuations [B´erczi et al., 2020; Hosseini et al., 2023]. Apart from being the first counterexample for EFX over general monotone functions, our chore construction signifies the first separation from its goods-only counterpart.

1.1 Our Contributions

We study fair allocations in a setting where m indivisible chores need to be allocated to n agents in a fair manner. We focus on a well-studied notion of fairness, (approximate) envy-freeness up to any item.

1 More recently, the result was further extended to capture more general valuations via a simplified analysis [Berger et al., 2022; Akrami et al., 2023])

We consider the following as our main technical results:

• An EFX allocation for chores need not exist under general cost functions. We present a construction with three agents in which no bounded approximation exists (Theorem 1).
• Determining whether an instance with three agents and superadditive costs admits an EFX allocation is NPcomplete (Theorem 2).

We note that no such counterexample was previously known for any subset of general monotone valuations, either in the context of goods-only or chores-only. Notably, this is the first separation result between goods and chores regarding EFX, since EFX allocations are known to exist when the number of goods is at most n + 3 [Mahara, 2023b].

In light of these negative results, we focus on a setting with few items, namely m ≤ n + 2; we prove the existence of EFX allocations under general monotone cost functions (Theorem 3). Due to the aforementioned negative example, this is the largest constant c for which all instances with three agents and m ≤ n + c items admit an EFX allocation. This is the first nontrivial result for a small number of chores under general cost functions; similar results have been established for goods [Amanatidis et al., 2020; Mahara, 2023b], as well as for chores, albeit under additive utilities [Kobayashi et al., 2023].

Next, we focus on additive cost functions and adapt a general framework in order to obtain approximation guarantees for chores (Theorem 4), establishing a series of improved (conditional) approximation ratios under ordinal-based assumptions. We follow recent works due to [Bhaskar et al., 2021; Li et al., 2022] that employ a variant of the well-known Envy Cycle Elimination technique, namely Top Trading Envy Cycle Elimination, to obtain improved approximation guarantees. Finally, we switch to the special case of three agents equipped with additive valuations. We improve the approximation ratio from 2 + √6 to 2 (Theorem 5).

1.2 RelatedWork

In this section we discuss prior works regarding EFX for goods and chores. We focus on the latter case. The growing literature on fair division is too extensive to cover here, and thus, we point the interested reader to the survey of Amanatidis et al. for an extensive discussion on recent developments, along with further notable fairness notions and open problems.

The seminal work of [Caragiannis et al., 2019] showed that maximizing the Nash social welfare produces EF1 and Pareto optimal allocations for goods. The existence of EF1 and PO allocations remains a major open problem for chores, beyond a couple of restricted settings [Garg et al., 2022; Ebadian et al., 2022; Barman et al., 2023].

Envy-freeness up to any item (EFX) for goods. Perhaps the most compelling relaxation of envy-freeness is EFX [Gourv`es et al., 2014; Caragiannis et al., 2019]. In sharp contrast to EF1 that enjoys strong existential and algorithmic properties, EFX remains a challenging open problem. In the past years, numerous works have studied approximate versions while also establishing the existence of the notion in restricted settings. [Plaut and Roughgarden, 2020] considered approximate EFX showing that 1/2-EFX allocations always exist; [Chan et al., 2019] subsequently showed that such allocations can be computed in polynomial time while Amanatidis et al. improved the approximation ratio to ϕ - 1 for additive valuations, which is the best currently known factor [Amanatidis et al., 2020]. Chaudhury et al. showed in a breakthrough result that exact EFX allocations always exist for three agents with additive valuation functions [Chaudhury et al., 2020]. Regarding restricted settings, positive results are known for a small number of items, lexicographic preferences, two types of goods, two valuation types, and EFX in graphs. [Mahara, 2023b; Hosseini et al., 2021; Mahara, 2023a; Gorantla et al., 2023; Christodoulou et al., 2023]. Lastly, a major line of work has focused on binary valuations and generalizations thereof, including bi-valued instances and dichotomous valuations [Halpern et al., 2020; Amanatidis et al., 2021; Babaioff et al., 2021; Benabbou et al., 2021].

Envy-freeness up to any item (EFX) for chores. In contrast to the case of goods, the existence of EFX allocations even for three agents with additive valuations remains an open problem. Zhou and Wu obtained a 5-approximation (later improved to 2 + √6 in the journal version) while also showing that an O(n2 )-EFX allocation always exists under additive cost functions for any number of agents [Zhou and Wu, 2024]. Li et al. showed the existence of EFX allocations when agents exhibit identical orderings over the set of items (commonly referred to as IDO instances) [Li et al., 2022], while Gafni et al. showed the existence of EFX allocations under additive leveled valuations [Gafni et al., 2023]. Similarly to the case of goods, several works have shown positive results for dichotomous valuations [Zhou and Wu, 2024; Kobayashi et al., 2023; Barman et al., 2023; Tao et al., 2023]. EFX allocations always exist under additive cost functions when m ≤ 2n [Kobayashi et al., 2023] or when there are only two types of chores [Aziz et al., 2023].

Lastly, we note that we heavily rely on an important subclass of valuations, namely superadditive cost functions; such functions capture complementarities among items and have received significant attention in the microeconomics and game theory literature [Nisan et al., 2007; Hassidim et al., 2011]. Prior work has also examined fair allocations in the presence of complements, both in the goods and the bads setting [Caragiannis et al., 2019; Barman et al., 2023].

Paper Outline. The remaining sections of the paper are outlined below. Section 2 includes the formal model and relevant definitions. In Section 3 we derive our main technical results regarding existence, approximation, and hardness of EFX allocations. Section 4 deals with the few items setting, while in Section 5 we show improved approximations under additive cost functions. Finally, we conclude and propose two major open questions.

2 Preliminaries

The problem of discrete fair division with chores is described by the tuple ⟨N,M,C⟩ where N = {1, . . . , n} is the set of n agents, M is the set of m indivisible chores and C = (c1(·), . . . , cn(·)) is the agents' cost functions. For each agent i, ci : 2M → R≥0 is normalized, i.e. ci(∅) = 0, and monotone, ci(S ∪ {e}) ≥ ci(S) for all S ⊆ M and e ∈ M. A subset of chores X ⊆ M is called a bundle and an allocation X = (X1, . . . ,Xn) is an n-partition of M where agent i receives the bundle Xi. A cost function c is superadditive if for any S, T ⊆ M : c(S ∪ T) ≥ c(S) + c(T) and additive if the previous relation holds always with equality. For ease of notation, we sometimes use e instead of {e}. We use the terms valuations and cost functions for chores (or bads) interchangeably.

Definition 1 (α-EFX). An allocation X is α-approximate envy free up to any chore (α-EFX) if for any pair of agents i, j and any e ∈ Xi : ci(Xi \ e) ≤ α · ci(Xj).

We say that an agent i strongly envies when Definition 1 is violated, i.e., ci(Xi \ e) > α · ci(Xj) for some e ∈ Xj. By setting α = 1 we retrieve the definition of an exact EFX allocation 2 .

We denote by σi(j, S) the j-th most costly chore in S under ci, with ties broken arbitrarily. For instance, we can write ci(σi(1),M) ≥ ci(σi(2),M) ≥ · · · ≥ ci(σi(m),M) to describe agent i's preference over all chores in M. When it is clear from context we will drop the set parameter for brevity.

Definition 2 (Maximin share). An allocation X is said to be maximin share fair (MMS) if

2.1 Top Trading Envy Cycle Elimination

In Section 5, en route to obtaining better approximation guarantees we will make use of the Top Trading Envy Cycle Elimination algorithm (TTECE, Algorithm 1). In contrast to the goods-only setting where the utilities of the agents are nondecreasing while performing envy-cycle eliminations, their cost increases when picking an item while decreases for the agents involved in a cycle elimination. The main insight of the algorithm is that an agent that does not envy any other agent in some allocation X, meaning that Xi is her top bundle, can receive an additional chore without violating the EF1 property. If such an agent always exists, then we can proceed in an incremental fashion, allocating one item at a time. Assuming that no such agent exists we can create the envy digraph of the allocation GX as follows: each node represents an agent and an edge from node i to node j represents that agent j owns i's top bundle. Since every node has an outgoing edge the graph contains a cycle C. Reallocating the bundles along that cycle, i.e. each agent receives the bundle she envies, creates a new allocation XC that maintains the EF1 property and creates unenvied agents (sinks).

2 We note that there exists an alternative definition in the literature, in which α · ci(Xi \ e) ≤ ci(Xj) for any pair of agents i, j and any e ∈ Xi. In this case, α lies within the same range as in the context of EFX approximations for goods, i.e., 0 < α ≤ 1.

Algorithm 1 Top trading envy cycle elimination algorithm

• Input: N, M, C Output: An allocation X 1: X = {∅, . . . , ∅}. 2: while ∃ some unallocated chore e do 3: if there is no sink in GX then 4: Find a cycle C in GX 5: X =XC 6: end if 7: Choose a sink agent s and let Xs =Xs ∪ e 8: end while 9: return X

3 Non-Existence, Hardness, and Inapproximability of EFX

In this section we present our main technical results; namely, we describe our explicit construction and proceed with showing that no finite EFX approximation is possible. Then, we show that deciding whether an EFX allocations always exists is NP-complete.

3.1 Non-existence and Inapproximability

Our negative example relies on a simple superadditive structure with three "special" chores, which are common for all agents. We use repeatedly the fact that an agent i valuing the bundle of another agent j at zero, i.e. ci(Xj) = 0, can afford to take at most one item or a bundle of zero value, i.e. ci(Xi) = 0; this follows from the definition of EFX in the context of chores.

Theorem 1. An EFX allocation need not exist for three agents with superadditive cost functions. Moreover, no approximate solution exists, for any approximation factor.

To describe the cost function for bundles with multiple items we set A = {ˆa, a1, a2}, B = {b1, b2, b3} and B-i = B \ bi. Now the cost function for agent i is given by the following formula:

In words, agent 1 has a cost of k2 for the bundle {b2, b3}, its supersets, and any bundle that contains b1 paired with some chore fromA. Otherwise, her cost function is effectively additive. We are now ready to prove our main theorem.

Let X be an allocation and consider an agent i, say agent 1 without loss of generality, that receives some item(s) fromB.

3 We will at times abuse notation, using a as the name of a1 and a2 at once for ease of exposition.

• Agent 1 receives 3 items fromB Then we have that {b2, b3} ⊆ X1 \ b1 =⇒ c1(X1 \ e) = k2 while min(c1(X2), c1(X3)) ≤ 2 yielding a k2 /2 approximation ratio.
• Agent 1 receives 2 items fromB
• Agent 1 receives {b2, b3}

If she receives some extra item then again we have that B-1 ⊆ X1 \ e and min(c1(X2), c1(X3)) ≤ k giving a ratio of k. Thus, she should receive exactly B-1. But then c2(X1) = c3(X1) = 0 while at least one of them received multiple items, hence the EFX property is violated and the ratio is unbounded.

• Agent 1 receives {b1, b3} (symmetrically for B-3) Again if she receives some extra item then c1(X1 \ b3) = k2 while min(c1(X2), c1(X3)) ≤ k. Thus, she should receive exactly B-2; but then, c3(X1) = 0. Therefore agent 3 should receive at most one item; in case this item is b2, then agent 2 will receive all the non zero items while the other bundles have zero cost leading to unbounded ratio. But if agent 3 does not receive b2, then X2 = {b2, a, ˆa} (where here, a denotes either a1 or a2) or {b2, a1, a2} meaning that c2(X2 \ a) = k2 while c2(X3) ≤ k. Once again the EFX property is violated and the ratio is k.
• Agent 1 receives 1 item fromB
• Agent 1 receives b1 If she receives two more items from A her cost is k2 even after removing one item while min(c1(X2), c1(X3)) ≤ k, while if she receives only b1 then c2(X1) = c3(X1) = 0 leading to a scenario analogous to when agent 1 receives B-1. It remains to check what happens when agent 1 receives exactly one item from A.
• Agent 1 receives {b1, ˆa} Now c1(X1 \ e) = k and we are left with a1, a2 and b2, b3. No matter how we partition the remaining items among the rest of the agents, min(c1(X2), c1(X3)) ≤ 2 giving us a k/2 approximation ratio.
• Agent 1 receives {b1, a}, i.e. b1 and one of a1 and a2

Now it is the other way around: c2(X1) = c3(X1) = 1 thus whoever gets ˆa shall not receive more items; in any other case she would have been strongly envious, leading to a k approximation ratio. Assume wlog that agent 2 gets ˆa. Then agent 3 gets b2, b3, a1 (or similarly, b2, b3, a2) thus after removing b2, her cost remains k2 , resulting in a k2 ratio.

• Agent 1 does not receive b1 Assume wlog that no agent received her matching item and again due to symmetry assume that 1 ← b2, 2 ← b3, 3 ← b1. Furthermore, assume that 1 also gets ˆa. Then c1(X1 \ e) = c1(ˆa) = k ≥ k2 · c1(X2) completing the proof.

We conclude that the instance admits no EFX allocation and the approximation ratio is k/2 that grows unbounded as k → ∞.

We conclude the section with an immediate corollary of Theorem 1.

Corollary 1 (Maximin share guarantee implications). The existence of a maximin share (MMS) fair allocation does not imply the existence of an α-EFX allocation for any α ≥ 1.

Proof. Notice that the MMS value for agent i is µni (M) = k, since proposing the allocation X′ = ({k}, {a1, a2, bl}, {bi, bj}) guarantees her MMS. Finally, the allocation A = ({k}, {a1, a2, b1}, {b2, b3}) achieves the maximin share for each agent. However, the approximation ratio for EFX is unbounded, due to the fact that c2(A2 \ e) ≥ 1, ∀e ∈ A2 while c2(A3) = 0. In fact, this implies something even stronger: the existence of a maximin share (MMS) fair allocation does not imply the existence of an α-EF1 allocation for any α ≥ 1.

3.2 NP-Completeness

In the sequel, we complement our negative results by studying the computational complexity of EFX allocations with indivisible chores under general monotone cost functions. We show that the problem is NP-complete. In fact, the crux of the non-existence argument lies in the inherent structure of the partition problem, which is well-known to be NP-complete. Some of the cases follow the analysis presented in Theorem 1; we defer the full proof to the full version.

Theorem 2. Deciding whether an EFX allocation exists given a chores-only instance is NP-complete.

Proof. We will prove the statement by reducing from (a variant of) the partition problem, in which we are given a set {ai}ni=1 of n positive integers summing to 3S with ai < S and the question is whether a partition of A into three sets of equal sum exists. Given an instance I of Partition, we construct an instance I ′ of our problem that has 3 agents and n+3 items M = {a1, . . . , an, b1, b2, b3}. We call B = {b1, b2, b3} and A = M \ B. The costs of individual chores are uniform for any agent i ∈ {1, 2, 3}: ci(aj) = aj for j ∈ [n], and ci(bj) = 0 for j ∈ {1, 2, 3}. For a bundle Xi assigned to agent i where |Xi| > 1, the agent's valuation is determined as follows:

For the forward direction, suppose that I is a YES-instance of Partition. Then, there exists a partition of {ai}ni=1 into 3 sets, say A1,A2,A3 such that ∑x∈A1 x = ∑x∈A2 x = ∑x∈A3 x. We construct the following chore allocation for I ′ and we will prove that it is EFX: for i ∈ 1, 2, 3, agent i is assigned the items from A whose corresponding integers belong to Ai, along with an item bj where j ̸= i. Then, for any two agents i, j it holds that ci(Xi) = ∑x∈Ai x = ∑x∈Aj x = ci(Aj ) ≤ ci(Xj ), and the EFX property follows.

We now move to the reverse direction and we suppose that I ′ is a YES-instance of our problem. Then there exists an EFX allocation, and we will demonstrate that I is a YESinstance of 3-partition by initially establishing the following claim:

Claim 1. The only plausible EFX allocations for I ′ involve assigning to each agent i exactly one item from B which should be an item bj where j ̸= i.

Proof. To prove the claim we will eliminate every other feasible allocation by showing that it is not EFX. Note that for each agent, at most two bundles can have an infinite cost, implying that if there exists an agent i with ci(Xi \ e) = ∞, she will always be envious of another agent. Therefore, no agent might receive all items from B (e.g. agent 1 would have had an infinite cost after removing b1) or two items from B and some item(s) from A (e.g. agent 1 would have had an infinite cost even after removing bj from b1, bj , a or a from b2, b3, a). So we have two cases based on how many items from B an agent can receive. We consider the following cases:

• Suppose that the EFX allocation involves an agent i such that |Xi ∩B| = 2 and Xi ∩A = ∅. Again, there are two subcases to consider based on whether i receives bi or not.
• In the first case, apart from bi, agent i also receives a chore bj, for some j ̸= i. Then, for agent j it holds that cj(Xi) = 0, since Xi contains bj and no items from A. If agent j receives at least two items, they will envy agent i after the removal of one of them. Otherwise, agent j receives at most one item and the third agent, called agent k, either receives bk and at least two items fromA, or agent j receives only bk. In the first case say that a ∈ Xk which results in ck(Xk \ a) = ∞ > ∑x∈Xj x = ck(Xj) and consequently in envy towards agent j. In the second case, ck(Xj) = 0 and, since once again agent k receives at least two items from A, it holds that ck(Xj \ a) > ck(Xj), demonstrating envy from agent k to agent j.
• For the second case where agent i receives B-i and no items from A, it holds that cj(Xi) = 0 for any agent j other than i. Each of these agents will envy agent i unless they receive at most one item, but taking into account that the total number of items that should be fully allocated among these agents is n+1, the considered allocation does not satisfy the EFX property.

Therefore, the EFX allocation should allocate exactly one item from B to every agent. Now, suppose that there exists an agent i who has been allocated bi. First, consider the case where |Xi ∩ A| > 1 and say that a ∈ Xi ∩ A. Then ci(Xi \ a) = ∞ and ci(Xj) = ∑x∈Xj x < ∞, since bi /∈ Xj, leading to an envy from agent i to agent j. On the other hand, we focus on the case where agent i has received at most 1 item from A. Say that agent j ̸= i has received a bundle Xj and that cj(Xi) = a, where a is the valuation that agents have towards the item from A in Xi

(perhaps 0, if Xi ∩ A = ∅). Since a < S = ∑i∈[n] ai 3 , there should be an agent, say agent j, such that a < ∑x∈Xj x. Agent j has also received an item from B, say b. Thus, cj(Xj \ b) = ∑x∈Xj\b x = ∑x∈Xj x > a = cj(Xi), leading to an envy from agent j to agent i.

Say that the given EFX allocation assigns a bundle Xi to agent i such that Xi = bj ∪ Ai, for some j ̸= i and some set Ai ⊆ A. Obviously it should hold that ∪i∈{1,2,3}Ai = A and that Ai ∩ Aj = ∅, for any i, j ∈ {1, 2, 3}. By the EFX property, it should hold that ci(Xi \ e) ≤ ci(Xj), for any e ∈ Xi and any pair of agents i, j. Therefore it should hold that ci(Ai) ≤ ci(Xj) = ci(Aj), for any pair of agents i, j, which leads to ∑x∈A1 x = ∑x∈A2 x = ∑x∈A3 x and, consequently to the fact that I is also a YES-instance of the partition problem.

It follows directly from our proof that the non-existence construction can be extended to an arbitrarily large number of items.

4 EFXwith a FewChores

Following the negative result of the previous section (three agents, six chores) it is natural to ask whether an EFX allocation always exists with less items. We answer this question affirmatively for the case of m ≤ n+2 chores and any number of agents. We note that this is the best achievable guarantee for the special case of three agents. The ideas to be presented revolve around the following simple fact.

Observation 1. An agent who receives her two smallest chores does not strongly envy any nonempty bundle.

Proof. Recall that σi(j) denotes the j-th larger chore according to agent i. Now, for any k < m - 1 we have ci(Xi \ e) ≤ ci(σ1(m - 1)) ≤ ci(σ1(k)) ≤ ci(Xj )

We are now ready to state the following theorem.

Theorem3. There exists an EFX allocation whenm≤ n+2 for any number of agents with general monotone valuations.

Proof. If m ≤ n then we have an EFX allocation by allocating at most one chore to each agent. If m = n + 1 then let Zi be the two smallest chores of agent i. Allocating Z1 to agent 1 and one chore to each of the remaining agents arbitrarily is EFX due to Observation 1. We focus on m = n + 2. At a high level, the idea is the following: if there is a pair of agents i, j ∈ N such that Zi ∩ Zj = ∅, we allocate Zi to i,Zj to j and again one chore to the other agents arbitrarily. Asking for a pair of disjoint Z's is strict and can be relaxed. For instance, if we allocate Z1 to agent 1 and the two smallest chores chores from M \ Z1 to agent 2, then agent 2 is EFX towards agents 3 to n due to Observation 1. Therefore, strong envy might only arise from agent 2 to agent 1. In order to avoid this scenario, it suffices that Z1 contains one large chore for agent 2. Concretely, we have the following two cases:

• For some agent j : σj(k) ∈ Zi for some k ≤ n - 1. We construct an EFX allocation as follows: agent i gets Zi, agent j gets her two smallest chores from M \ Zi and each remaining agent gets exactly one chore arbitrarily. It suffices to check that j does not strongly envy i. Indeed, there are three chores with index larger than k, i.e. smaller than σj(k), and agent i received at most one of them. Thus, both chores of j are smaller than σj(k) ∈ Xi = Zi and the case is completed.
• No such agent exists. Then Zi contains two out of the three smallest chores for any other agent. Consider the set M \ Zi.
• There exists an agent j such that σi(n,M \ Zi) ̸= σj(n,M \ Zi). In other words agents i and j disagree on the smallest chore in M \ Zi. Then we allocate σi(n,M \ Zi) to i and σj(n,M \ Zi) to j, one item from Zi to each one and a single item to the other agents arbitrarily. Note that both agents i and j have received two out of their three smallest chores while the rest of the agents have received a strictly larger one. Finally, agent i does not stongly envy j because σj(n,M \ Zi) has a smaller index than n for agent i and vice versa.
• No such agent exists. That means that all agents agree on the least costly chore in M \ Zi. Since Zi contains two out of the three smallest chores for all agents, we conclude that all agents agree upon the set of the three smallest chores, namely M -. If agent 1 can receive M - without breaking the EFX property the case is completed. Assuming the contrary, we have that there exists a subset Y ⊂ M - with |Y | = 2, such that c1(Y ) > c1(σ1(n - 1)). Therefore the allocation in which agent 1 gets σ1(n - 1) and M - \ Y , some agent gets Y , and all other agents get one item arbitrarily is EFX.

5 Approximations for Additive Cost Functions

We now switch to the case of additive cost functions, aiming to obtain better approximation guarantees. To that end, we revisit the Envy Cycle Elimination algorithm. So far, this procedure is less explored in the chore setting due to its lack of monotonicity. We try to bypass this obstacle via a general approximation framework due to [Farhadi et al., 2021; Markakis and Santorinaios, 2023].

5.1 Approximation Framework

Theorem 4. The allocation produced by Algorithm 2 is max (α, β + 1)-EFX.

We introduce some more notation and make the following observation before proceeding with the proof.

Observation 2. Consider a partial allocation Y and define the ratio matrix R = {rij} as follows

Algorithm 2 Chore approximation framework

Input: N, M, C

Output: An allocation X

• 1: For α, β > 0, compute a partial α-EFX allocation Y = (Y1, . . . , Yn), with the property that ci(e) ≤ β · ci(Yj) for all i, j ̸= i ∈ N and all e ∈ M \ Y
• 2: Run Algorithm 1 until there are no unallocated items

In the case of goods one produces approximations by considering only the diagonal of the matrix R while for chores we need to consider anything but the diagonal.

In the sequel, we refer to the property in line 1 of Algorithm 2 as the "ratio property" and stick with the rij notation.

Proof of Theorem 4. Fix some agent i. Initially, i.e. in Y , any envy from agent i is at most α-EFX. When a chore is not allocated to agent i, we get r′ij ≥ rij since the nominator increases or the denominator decreases or there are no changes. Thus r′ij ≥ β is maintained. Moreover, agent i is indifferent to cycle eliminations she does not participate in; such procedures simply permute the line Ri without affecting rii. Therefore, it remains to check what happens when she does participate in a cycle elimination or when she gets some item e. Let Z be the allocation in the first scenario and Zj the bundle she is about to receive. Then we have that ci(Zi) ≥ ci(Zj) =⇒ rii ≥ rij ≥ β. Therefore, line Ri is element-wise greater than β and thus, no bundle reallocations can disrupt her ratio property. Finally, when e gets allocated to i we have:

The first inequality holds since i is now a sink in the envy graph, while the second follows from the ratio property, as described above. Adding the inequalities yields the β + 1 term claimed, completing the proof.

5.2 Conditional Approximations

Similarly to the goods-only setting, one can obtain guarantees by examining only the few most important chores. Here, the most important ones are those with high costs for some agents.

Definition 3. Let Lki = {σi(1), . . . , σi(k)} denote the set of the k most burdensome chores for agent i.

In accordance with the goods setting, we refer to chores in Li as "top".

Lemma 1 (Top n agreement). If Lni = Lnj , i.e. all agents agree in the set of the top n chores, there exists a 2-EFX allocation. Moreover, it can be computed in polynomial time.

Proof. Note that allocating one chore from the set to each agent arbitrarily, produces an EFX allocation that satisfies Theorem 4 with α = 1 and β = 1, thus yielding a 2-EFX complete allocation. Moreover, since the partial allocation can be constructed in linear time the whole procedure is efficient.

Lemma 2 (Top n - 1 agreement). If Ln-1 i = Ln-1 j , i.e. all agents agree in the set of the top n - 1 chores, there exists a max(2, n-2)-EFX allocation. Moreover, it can be computed in polynomial time.

Proof. Let Ln-1 = {li}1≤i≤n-1 be the top set and construct the allocation X as follows:

Agents 1 to n - 1 are EFX towards the rest since they have a single item. If agent n also has a single item, we have α = 1, β = 1 thus a 2-EFX allocation. Assuming that agent n has multiple items we have

where the first inequality is due to the fact that n got at most n-1 items. Thus α = n-2. As for the ratio property, for all agents but n, rij ≥ 1 since every bundle contains one chore fromLni and for agent n : rij̸=i ≥ 1 since every other bundle contains one chore from Ln-1 n . Again β = 1 and the proof is complete.

Interestingly, the same approximation ratio can be obtained when the agents exhibit diametrically opposed preferences, i.e. disagree on all top n- 1 chores. Note, however, that this implies that there exist at least n(n-1) items.

Algorithm 3 Top n - 1 disagreement

1: for each agent i do 2: for each agent j ̸= i do 3: e∗ = arg maxe∈M ci(e) 4: Xj =Xj ∪ e∗ 5: M =M \ e∗ 6: end for 7: end for

Lemma 3. If Ln-1 i ∩ Ln-1 j = ∅, i.e. all the agents disagree in the set of the top n-1 chores, there exists a max(2, n-2)- EFX allocation. Moreover, it can be computed in polynomial time.

Proof. We will show that the partial allocation produced by Algorithm 3 satisfies the conditions of Theorem 4 with α = n - 2 and β = 1. We have that

since agent i cannot receive any item from Ln-1 i while every other agent receives exactly one item from it. The latter fact also implies that rij ≥ 1.

Lemma 4. Even if the agents agree upon the ranking of a large set S of top chores and an exact EFX allocation of S is given, we cannot obtain better guarantees via Algorithm 2.

Proof. Consider the instance with k common top chores, with 2n < k < m, as shown below:

5.3 Approximation for Three Agents

Next, we treat the case of three agents with additive disutilities. We show how to apply the techniques developed in the previous section to obtain unconditional results for the case of three agents, improving the approximation factor from 2+√6 to 2.

Theorem 5. A 2-EFX allocation for three agents exists and can be computed in polynomial time.

Proof. Due to Lemma 3 there exists a pair of agents that agree upon at least one top-2 item; otherwise the theorem follows immediately. Without loss of generality assume that agents 1 and 2 agree. If they agree only on the second chore, i.e. σ1(2) = σ2(2) we allocate it to agent 3 and agents 1 and 2 receive each other's top chore. Otherwise, agent 1's top chore lies in agent 2's top-2 set (or vice versa). We allocate it to agent 3. Then we allocate σ2(1,M \ X3) to agent 1 and σ1(1,M \ (X2 ∪X3)) to agent 2. Now, the allocation is trivially EFX since any agent has exactly one item. Crucially, due to the allocating order, agents 1 and 2 do not envy agent 3. As for the ratio matrix we have:

All that is left is to ensure that r31 and r32 can be made larger than 1. To that end, note that running TTECE using agent 3's cost function and picking the sinks lexicographically will allocate to agent 3 only after allocating one more item to the other agents, therefore at that point r3i ≥ 1, fulfilling the requirements of Theorem 4. In case that does not happen, the resulted allocation is complete; agent 3 has a single chore, thus she cannot strongly envy, while agents 1 and 2 satisfy the requirements of Theorem 4 with a = 1 and b = 1.

6 Conclusion and FutureWork

We explore EFX allocations in the context of bads. We demonstrate a series of strong negative results regarding the case of three superadditive agents. Moreover, we show that EFX always exists under a setting with a small number of items, and provide a separation result with the goods-only setting. Lastly, we show improved approximation ratios for a number of cases. Our work leaves two main open questions. First, determining whether similar constructions can be found for the case of goods. Second, whether an exact EFX allocation always exists for three agents with additive disutilities.

Acknowledgements

We would like to thank Georgios Amanatidis, George Christodoulou, Evangelos Markakis, and Alkmini Sgouritsa

• for helpful discussions and their constructive comments on a preprint of this work. We are also grateful to Georgios Papasotiropoulos and Nicos Protopapas for their assistance and their insightful feedback.

This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.