Approximately EFX Allocations for Indivisible Chores

1 Introduction

Fairness is receiving increasing attention in a broad range of research fields, including but not limited to computer science, economics and mathematics. A fair allocation problem focuses on allocating a set M of m items to a group N of n agents, where different agents may have different valuation functions on the items. When the valuation functions give positive values, the items are considered as goods, e.g., resources; when the valuation functions give negative values, the items are considered as chores, e.g., tasks. In the latter case we refer to the valuation functions as cost functions. In this paper, we consider the functions are additive. Arguably, two of the most well-studied fairness notions are envy-freeness (EF) [Foley, 1967] and proportionality (PROP) [Steinhaus, 1948]. Proportionality means that each agent received at least her proportional share of all items. Envyfreeness is even stronger. Informally speaking, an allocation is EF if no agent wants to exchange her bundle of items with another agent in order to increase her utility. In contrast to the case of divisible items, where EF and PROP allocations always exist [Aziz and Mackenzie, 2016; Edward Su, 1999; Alon, 1987], when items are indivisible, they are not guaranteed to exist even for some simple cases. For example, consider allocating a single indivisible item to two agents. This example also defies approximations of EF and PROP allocation. Therefore, researchers have turned their attention to relaxations of these fairness notions. Envy-free up to one item (EF1) [Lipton et al., 2004] and envy-free up to any item (EFX) [Caragiannis et al., 2019] are two widely studied relaxations of EF. Informally speaking, an EF1 allocation requires that the envy between any two agents can be eliminated by removing some item; while an EFX allocation requires that the envy can be eliminated by removing any item.

It has been shown that EF1 allocations are guaranteed to exist and can be found in polynomial time for goods [Lipton et al., 2004], chores and even mixture of the two [Bhaskar et al., 2021]. However, EF1 could sometimes lead to extreme unfairness, even if a much fairer allocation exists. EFX, on the other hand, puts a much stronger constraint on the allocation and is arguably the most compelling fairness notion. There are fruitful results regarding the existence and computation of (approximations of) EFX allocations since the notion was first proposed by Caragiannis et al. [Caragiannis et al., 2019]. For the allocation of goods, it has been shown that EFX allocations exist for two agents with general valuations and any number of agents with identical ordering (IDO) valuations [Plaut and Roughgarden, 2020], and recently for three agents [Chaudhury et al., 2020a]. It remains a fascinating open problem whether EFX allocations always exist in general. For general number of agents with additive valuations, there are efficient algorithms for the computation of 0.5-approximate 1 EFX allocations [Plaut and Roughgarden, 2020; Chan et al., 2019] and 0.618-approximate EFX allocations [Amanatidis et al., 2020].

In contrast to the allocation of goods, very little regarding EFX allocations for chores is known to this day. It can be easily shown that the divide-and-choose algorithm computes an EFX allocation when there are two agents with general valuations. Very recently, it is shown that EFX allocations always exist for IDO instances [Li et al., 2022] and levelled preferences [Gafni et al., 2021]. However, even for three agents with general additive valuations, it is unknown whether constant approximations of EFX allocations exist, let alone the existence of EFX allocations.

1 Regarding approximations of EFX allocations, the approximate ratios are at most 1 for goods, and at least 1 for chores.

1.1 Main Results

In this paper, we propose polynomial-time algorithms for the computation of approximately EFX allocations for indivisible chores. For three agents, our algorithm achieves an approximation ratio of 5 while for n ≥ 4 agents the approximation ratio is 3n2 . Prior to our work, no non-trivial results regarding the approximation of EFX allocation for chores are known, except for some special cases [Li et al., 2022].

Result 1 (Theorem 3). There exists a polynomial time algorithm that computes a 5-approximate EFX allocation for three agents with additive cost functions.

Result 2 (Theorem 8). There exists a polynomial time algorithm that computes a 3n2 -approximate EFX allocation for n ≥ 4 agents with additive cost functions.

Main Challenge. While being two seemingly similar problems, the EFX allocations of goods and chores admit distinct difficulties in approximability. For the allocation of goods, while computing an EFX allocation seems difficult, getting a constant approximation ratio turns out to be quite straightforward. Existing algorithms [Amanatidis et al., 2020; Plaut and Roughgarden, 2020] for the computation of approximately EFX allocation for goods follow the common framework of Sequential Picking equipped with the Envy-Cycle Elimination technique [Lipton et al., 2004; Bhaskar et al., 2021]. Roughly speaking, in these algorithms, in each round an "un-envied" agent will be chosen to pick her favourite unallocated item, where the envy-cycle elimination technique ensures that there will always be an un-envied agent in each round. The result of [Li et al., 2022] also follows this framework to compute an EFX allocation for chores on identical ordering instances. The key to the analysis is by showing that the value/cost of an agent increases by at most a small constant factor in each round. However, it seems quite challenging to extend this framework to handle general instances for the allocation of chores. For the allocation of goods, it can be shown that the utilities of agents are non-decreasing in each round: the picking operation and envy-cycle elimination do not decrease the value of any agent. In contrast, for the allocation of chores, when an agent picks an item, its cost increases; when an envy-cycle is eliminated, the cost of the involved agents decreases. This introduces a main difficulty in computing an (approximation of) EFX allocation for chores: if the cost of an agent is very small when it picks an item with large cost, the approximation ratio of EFX can be arbitrarily bad.

Our Techniques. To get around this difficulty, we adopt a completely different approach in dividing the items. Our first observation is that when all items have small costs to all agents, then there is likely to exist a partition that looks

"even" to all agents. To handle this case, we propose the Sequential Placement algorithm, which computes a partition of the items for a group of agents such that the ratios between the cost of any two bundles are bounded, under every agent's cost function. On the other hand, if there exists an item e that has large cost to an agent i, then by allocating the item to some other agent j, we can ensure that agent i does not seriously envy agent j, no matter what items agent i received eventually. Our algorithms rely on a careful combination of the above two observations. For three agents, we show that by classifying the agents into different types depending on the number of large items they have, we are able to get a 5approximate EFX allocation. To extend the ideas to general number of agents, we borrow some existing techniques for the computation of PROP1 allocation for goods [Lipton et al., 2004], and bound the approximation ratio by 3n2 .

We also show that our results can be improved for bivalued instances. An instance is called a bi-valued instance if there exists two values a, b ≥ 0 such that ci(e) ∈ {a, b} for every agent i ∈ N and item e ∈ M. In other words, each agent classifies the set of items into heavy items and light items, and items in the same category have the same cost to the agent. The bi-valued instances are commonly considered as one of most important special case of the fair allocation problem [Aziz and Brown, 2020; Akrami et al., 2021; Garg and Murhekar, 2021; Amanatidis et al., 2021; Garg et al., 2021; Ebadian et al., 2021]. For the case of bi-valued goods, polynomial time algorithms have been proposed for the computation of EFX allocations [Amanatidis et al., 2021] and EFX allocations that are also Pareto optimal (PO) [Garg and Murhekar, 2021]. Very recently, it has been shown that for bi-valued chores, EF1 allocations that are PO can be computed in polynomial time [Garg et al., 2021; Ebadian et al., 2021]. Unfortunately, no non-trivial results regarding the approximation of EFX allocations is known for bi-valued chores.

In this paper, we make progress towards answering this problem for bi-valued instances. For three agents, we propose a polynomial time algorithm that always computes an EFX allocation; for n ≥ 4 agents, we propose a polynomial time algorithm that always computes a (n - 1)-approximate EFX allocation.

Result 3 (Theorem 15). There exists a polynomial time algorithm that computes an EFX allocation for three agents with bi-valued cost functions.

Result 4 (Theorem 19). There exists a polynomial time algorithm that computes a (n - 1)-approximate EFX allocation for n ≥ 4 agents with bi-valued cost functions.

1.2 Other RelatedWorks

For the allocation of goods, there are also works that study partial EFX allocations, i.e., EFX allocations with some of the items unallocated. To name a few, Chaudhury et al. [Chaudhury et al., 2020b] show that EFX allocations exist if we are allowed to leave at most n-1 items unallocated. The result has recently been improved to n - 2 items by Berger et al. [Berger et al., 2021]. They also show that an EFX allocation that leaves at most one item unallocated exists for four agents. Very recently, Chaudhury et al. [Chaudhury et al., 2021] show that a (1 - ϵ)-approximate EFX allocation with sublinear number of unallocated goods and high Nash welfare exists. It remains unknown whether similar results hold for the allocation of chores.

Besides EFX, there are other well-studied fairness notions, e.g., MMS [Budish, 2011] and PROPX [Moulin, 2019], for the allocation of chores. While it has been shown that MMS allocations are not guaranteed to exist for indivisible chores [Aziz et al., 2017], there are many works that study its approximations [Aziz et al., 2017; Aziz et al., 2020a; Aziz et al., 2019; Huang and Lu, 2021]. The state-of-theart approximation ratio for MMS allocation for indivisible chores is 11/9 by Huang and Lu [Huang and Lu, 2021]. Regarding PROPX allocations, in contrast to the allocation of goods, where PROPX allocation is not guaranteed to exist [Moulin, 2019; Aziz et al., 2020b], it is shown that PROPX allocation always exists and can be computed efficiently for chores [Li et al., 2022].

2 Preliminaries

We consider how to fairly allocate a set of m indivisible chores M to a group of n agents N. A bundle is a subset of items X ⊆ M. An allocation is represented by a n-partition X = (X1, · · · ,Xn) of the items, where Xi ∩Xj = ∅ for all i ̸= j and ∪i∈NXi = M. In the allocation X, agent i ∈ N received bundle Xi. Each agent i ∈ N has an additive cost function ci : 2M → R+ ∪ {0}. That is, for any i ∈ N and X ⊆ M, ci(X) = ∑e∈X ci({e}).

When there is no confusion, we use cie and ci(e) to denote ci({e}) for convenience. Further, given any set X ⊆ M and e ∈ M, we use X + e and X - e to denote X ∪ {e} and X \ {e}, respectively.

Definition 1 (α-EFX). For any α ≥ 1, an allocation X is α-approximate envy-free up to any item (α-EFX) if for any i, j ∈ N and any e ∈ Xi,ci(Xi - e) ≤ α · ci(Xj). When α = 1, the allocation X is EFX.

Without loss of generality, we assume that all cost functions are normalized. That is, for any i ∈ N, ci(M) = 1. Let σi(j) be the j-th most costly item under ci (with ties broken deterministically, e.g., by item ID). In other words, for every agent i ∈ N, we have ci(σi(1)) ≥ ci(σi(2)) ≥ · · · ≥ ci(σi(m)). For each agent i ∈ N, we define M - i = {σi(j) : j ≥ n} as the set of tail items. Observe that we have |M - i | = m-n+ 1 and ci(e) ≥ ci(e′ ) for all e /∈ M - i and e′ ∈ M - i . With this observation, we show that for every instance there exists a simple allocation that is (m-n)-EFX.

Lemma 2. There exists a (m-n)-EFX allocation for every instance with m items and n agents.

Proof. Fix an arbitrary agent, e.g., agent n, and define the allocation as follows. For all i < n, let Xi = {σn(i)}. Let Xn = M - n be the set containing the remaining items. Obviously, the resulting allocation is EFX for all agents i < n since |Xi| = 1. By the definition of M - n , for every e ∈ M - n , every i < n, we have

Consequently, the allocation is (m-n)-EFX.

Unfortunately the above approximation ratio is large, especially when m is large and n is small. In the following sections, we present algorithms that compute allocations with approximations of EFX that depend only on n. In particular, our algorithm computes a 5-EFX allocation when n = 3 and 3n2 -EFX allocation for n ≥ 4.

3 5-EFXAllocation for Three Agents

In this section we present the algorithm that computes a 5EFX allocation when n = 3. The ideas we use to compute the allocation in this part inspires our design of approximation algorithm for general n.

Theorem 3. There exists an algorithm that computes a 5EFX allocation for three agents in O(mlogm) time.

Given an allocation X, we say that agent i envies agent j if ci(Xi) > ci(Xj); strongly-envies agent j if ∃e ∈ Xi such that ci(Xi - e) > 5 · ci(Xj). In other words, an allocation is 5-EFX if and only if no agent strongly-envies another agent. For three agents we have M - i = M \ {σi(1), σi(2)} for any i ∈ N. Observe that if there exists an agent i ∈ N with ci(M - i ) ≤ 5 · ci(σi(2)), then by allocating σi(1) and σi(2) to the other two agents and M - i to agent i, we end up having a 5-EFX allocation (following an analysis similar to the proof of Lemma 2). Hence it suffices to consider the case in which every agent i ∈ N has ci(M - i ) > 5 · ci(σi(2)). In other words, item σi(2) (and thus every item other than σi(1)) is "small" to agent i in the sense that it contributes at most a 1/6 fraction to the total cost of M - σi(1). Depending on whether σi(1) has large cost, we classify the agents into two types: large agent and small agent.

Definition 4 (Large/Small Agent). We call agent i ∈ N a large agent if ci(σi(1)) ≥ 1/8; small otherwise.

The main intuition behind the definition is as follows. Recall that we are aiming for a 5-EFX allocation. For a large agent i, if σi(1) ∈ Xj for some agent j ̸= i, then as long as ci(Xi) ≤ 5/8, agent i does not strongly-envy agent j, even if |Xj| = 1. On the other hand, for a small agent i, every item e ∈ M has cost ci(e) < 1/8. Thus we can partition the items into bundles of roughly the same cost, under ci, so that no matter which of these bundles agent i eventually receives, she will not strongly-envy any other agent.

Following the above intuitions, we proceed by considering how many small agents there are.

3.1 At Least Two Small Agents

W.l.o.g., suppose agent 1 and 2 are small. Agent 3 can be either small or large.

Lemma 5. We can compute in polynomial-time a 3-partition (S1, S2, S3) of M such that for both i ∈ {1, 2}, we have ci(Sj) ∈ [1/8, 5/8] for all j ∈ {1, 2, 3}.

Note that Lemma 5 immediately implies Theorem 3 when there are at least two small agents for the following reasons. Since the costs of the three bundles S1, S2 and S3 differ by a factor of at most 5, agent 1 and 2 will not strongly-envy any other agent as long as every agent gets exactly one bundle.

Algorithm 1: Sequential Placement

• 1 Initialize: Sj ← ∅ for all j ∈ {1, 2, 3}, P ←M and k ← 1 ;

2 while P ̸= ∅ do 3 let e∗ ← argmax{ck(e) : e ∈ P} and j ∗ ← argmin{ck(Sj) : j ∈ {1, 2, 3}}; 4 Sj ∗ ←Sj ∗ + e∗ , P ←P - e∗ ; 5 k ← (k mod 2) +1 ; Output: (S1, S2, S3)

Therefore, by letting agent 3 pick her favourite bundle, i.e., the one with minimum c3(Sj), and allocating the remaining two bundles to agents 1 and 2 arbitrarily, we end up with a 5EFX allocation: agent 3 does not envy agents 1 and 2; agents 1 and 2 do not strongly-envy any other agent.

Thus it remains to give the polynomial-time algorithm for the computation of (S1, S2, S3). The main idea behind the algorithm is quite simple: since agents 1 and 2 have small costs on every item, round-robin like algorithms should work in computing such a partition.

The Algorithm. We initialize Sj as an empty bundle for all j ∈ {1, 2, 3}. Then we let agents 1 and 2 take turns to put the unallocated item with maximum cost into the bundle with smallest cost, both under her own cost function, until all items are allocated (refer to Algorithm 1).

It remains to show that for both i ∈ {1, 2}, we have ci(Sj) ∈ [1/8, 5/8] for all j ∈ {1, 2, 3}. The complete analysis (and most of the lemmas to follow) can be found in the full version of the paper (see the supplementary material).

3.2 One Small Agent

Next we consider the case when there is exactly one small agent, say agent 3. Let e1 = σ1(1) and e2 = σ2(1) be the most costly item under c1 and c2, respectively. Since agents 1 and 2 are large, we have c1(e1) ≥ 1/8 and c2(e2) ≥ 1/8.

Lemma 6. When there is exactly one small agent, there exists a 4-EFX allocation and could be found in polynomial time.

Obviously there are two possibilities here, e1 = e2 and e1 ̸= e2 respectively. For the first case, we can use the fact that the large item for agent 1 and 2 is the same, and assign it to agent 3. Let X3 = {e1}, and we compute an EFX allocation (X1,X2) between agents 1 and 2 on itemsM-e1. In this allocation agent 3 obviously does not strongly-envy agents 1 and 2 because |X3| = 1, and agents 1 and 2 do not envy each other by more than one item. On the other hand, since (X1, X2) is an EFX allocation on items M-e1, by removing any item e from X1 (resp. X2), we have c1(X1 - e) ≤ 1/2 (resp. c2(X2 - e) ≤ 1/2). Since c1(X3) = c1(e1) ≥ 1/8 and c2(X3) = c2(e2) ≥ 1/8, the allocation is 4-EFX.

So it remains us to deal with the case that e1 ̸= e2. And we use the fact that agent 3 is a small agent to compute an allocation that is fair to all.

The Algorithm. If e1 ̸= e2, let M - = M - e1 - e2. We first compute an EFX allocation (S1, S2, S3) for three agents under cost function c3, on items M -. Assume w.l.o.g. that

Algorithm 2: Algorithm for 2 Large Agents

• 1 Initialize: Xj ← ∅ for all j ∈ {1, 2, 3}, P ←M - ; 2 Compute an EFX allocation (S1, S2, S3) on items P under cost function c3 ; 3 X1 ← S1 + e2, X2 ← argmin{c2(S2 + e1), c2(S3)} ; 4 X3 ←M -X1 -X2 ;

• Output: (X1,X2,X3)

Algorithm 3: Algorithm for 3 Large Agents

• 1 Initialize: Xj ← ∅ for all j ∈ {1, 2, 3}, P ←M - ;
• 2 let X3 ← {e1, e2} ;
• 3 Compute an EFX allocation (S1, S2) on items P under cost function c1 ;
• 4 let Si∗ ← argmin{c3(S1), c3(S2)} ;
• 5 X2 ← argmin{Si∗ + e3, P - Si∗} ;
• 6 X1 ←P + e3 -X2 ;

Output: (X1,X2,X3)

c1(S1) ≤ c1(S2) ≤ c1(S3), we decide the allocation X as follows. Let X1 = S1 +e2, let agent 2 pick a bundle between S2 + e1 and S3; then agent 3 gets the remaining bundle.

3.3 All Agents are Large

Finally, we consider the case when all agents are large. Let e1 = σ1(1), e2 = σ2(1) and e3 = σ3(1). By definition we have c1(e1) ≥ 1/8, c2(e2) ≥ 1/8 and c3(e3) ≥ 1/8.

Lemma 7. When all three agents are large, there exists a 4-EFX allocation and could be found in polynomial time.

As before, if there exist two of {e1, e2, e3} that are the same item, say e1 = e2, then we can easily compute an 4EFX allocation by assigning e1 to X3 and computing an EFX allocation between agent 1 and 2 on the remaining items. Hence we assume e1, e2 and e3 are three different items, and let M - = M \ {e1, e2, e3}.

TheAlgorithm. We initializeXj as an empty bundle for all j ∈ {1, 2, 3}. We first assign both e1 and e2 to agent 3, and agent 3 quit the allocation. Then we compute an EFX allocation (S1, S2) on items M - under cost function c1. Assume w.l.o.g. that c3(S1) ≤ c3(S2). We let agent 2 pick a bundle between S1 +e3 and S2, and assign the other bundle to agent 1 (refer to Algorithm 3).

We argue that above three algorithms run in O(mlogm) time because under a fix cost function, computing an EFX allocation can be done by sorting items and allocating items sequentially to form a partition. Given this partition the final allocation can be determined in O(1) time. In summary, in all cases we can compute a 5-EFX allocation for three agents in polynomial-time, which proves Theorem 3. From the above analysis we observe that it is crucial to distinguish whether an item e is large to an agent i: if it is, then by allocating the item to another agent j who values it small, we can eliminate the strong envyness from i to j; if it is not, then putting item e in Xi does not hurt the approximation ratio too much. In the following section, we show how these ideas can be extended to the general case when n ≥ 4.

4 General Number of Agents

In this section, we give an algorithm that computes a 3n2 - EFX allocation for any given instance with n ≥ 4 agents.

Theorem 8. There exists an algorithm that computes a 3n2 -EFX allocation for any instance with n agents in O(nmlogm) time.

For each agent i ∈ N, we define M - i = {σi(j) : j ≥ n}. As before (refer to Lemma 2 for a formal analysis), if there exists an agent i with ci(M - i ) ≤ 3n2 · ci(σi(n - 1)), then we can easily compute a 3n2 -EFX allocation by allocating exactly one item in M \ M - i to each agent in N - i, and assigning the remaining items M - i to agent i. Since each agent other than i receives only one item, and agent i receives a set of items with total cost at most 3n2 times the cost of any other agent, the allocation is 3n2 -EFX.

In the following we say that agent i strongly-envies agent j if for some e ∈ Xi it holds ci(Xi - e) > 3n2 · ci(Xj). We define bi = 1 3n2-n+2 · ci(M - i ), and let Li = {e ∈ M : ci(e) ≥ bi} be the set of large items of agent i. Note that by the above discussion we have |Li| ≤ n - 2 for all i ∈ N. The main intuition behind the definition of large items is as follows. Our algorithm will compute an allocation X = (X1, . . . , Xn) ensuring that for each agent i ∈ N, either Xi ∩ Li = ∅, i.e., no large item in Li is assigned to agent i; or |Xi| = 1. We show that as long as no large item is assigned to agent i, i does not strongly-envy any other agent that receives at least one item in Li.

Lemma 9. For any agent i ∈ N, if Xi ∩ Li = ∅ and Li ∩ Xj ̸= ∅, then i does not strongly-envy agent j.

Remark. A few difficulties arise when we try to extend the ideas we develop for three agents to general number of agents. First, for a large number of agents, it is no longer feasible to classify agents depending on how many large items they have because there are too many cases. Instead, our new algorithm removes the large items of each agent, and treats all agents as "small agents". Second, even if all agents have no large items, i.e., Li = ∅ for all i ∈ N, it is not clear how to extend the Round Robin Placement algorithm (Lemma 5) to compute O(n) subsets with upper and lower bounded costs for general number of agents. To get around this, we borrow existing results for the PROP1 allocation of goods, and show that when items are small to the agents, we can partition the items into O(n) bundles such that the ratio between the costs of any two bundles is bounded by 3n2 .

Let L = ∪i∈NLi be the set of items that are large to at least one agent. Let K = ∩i∈NLi. Note that each item e ∈ K is large to all agents. Let M - = M \ L be the set of items that are small to all agents.

Claim 4.1. For each i ∈ N and e ∈ M -, we have ci(e) ≤ 1 2n2+2n · ci(M -).

Recall that now we have three sets of items K, M - and L \ K, each of which will be handled as follows.

• Since each item in K is large to all agents, we assign each of them to a unique agent chosen arbitrarily. Let N ∗ be these agents, and N - = N \ N ∗ . Note that |N ∗ | = |K|. Our algorithm will not assign any further
• items to agents in N ∗ . Obviously these agents do not envy any other agents by more than one item. Moreover, if we can ensure that in the final allocation Xi ∩ Li = ∅ for all i ∈ N -, then no agent strongly-envies any agent in N ∗ , by Lemma 9.
• By Claim 4.1, for all agent i, all items inM - have small cost compared to ci(M -). We show in Lemma 10 that we can partition the items in M - into |N -| bundles evenly under every cost function of agents, and assign them to the agents in N -. The key to the computation of the partition is to ensure that each bundle has a considerably large cost to every agent in N -.
• It remains to assign items in L\K. Recall that these are items that are large to some agent but not to all agents. Our algorithm assigns each e ∈ L \ K to an arbitrary agent i for which e /∈ Li.

Lemma 10. Given a set of items M - and a group of agents N - such that for all i ∈ N - and e ∈ M -,ci(e) ≤ 1 2n2+2n · ci(M -), there exists a partition (S1, S2, . . . , S|N -|) of M - such that for all i, j ∈ N -, ci(Sj) ≥ 1 2n2+2n · ci(M -).

We show that no agent strongly-envies another agent. From the previous analysis, we know that agents in N ∗ do not envy any other agent by more than one item, and agents in N - do not strongly-envy agents in N ∗ . It remains to show that agents in N - do not strongly-envy each other. Recall that each agent i ∈ N - receives a bundle Si (see Lemma 10), and possibly some other items from L \ K that are small to agent i. By Lemma 10, for every j ∈ N - we have ci(Xj) ≥ 1 2n2+2n · ci(M -). Next we give an upper bound on ci(Xi). Recall that for any i ∈ N we have |Li| ≤ n - 2, and there are (n - 1) agents except i itself. Hence there are at most (n-1) · (n-2) items in L\K that are small to agent i, and

Combining the upper bound on ci(Xi) and lower bound on ci(Xj), we have ci(Xi) ≤ 3n2 · ci(Xj) for any i, j ∈ N -. Hence agents in N - do not strongly-envy each other.

We finally argue that our algorithm for computing 3n2 - EFX allocations for n ≥ 4 agents takes O(nmlogm) time. The main complexity comes from the division of items into three sets K, M - and L \ K, which takes O(nm log m) time as each Li can be computed in O(mlogm) time. Given the three sets, it can be verified that allocating items in K, M - and L \ K takes O(nm) time.

5 Bi-valued Instances

In this section, we consider the fair allocation problem with agents having bi-valued cost functions. That is, for any i ∈ N and e ∈ M, there exist constants a, b ≥ 0, ci(e) ∈ {a, b}. Equivalently, for any a ̸= b, we can scale the cost function so that ci(e) ∈ {ϵ, 1} where ϵ ∈ [0, 1). Note that when ϵ = 0, the instance is a binary instance. We call the allocation X a partial allocation if ∪i∈NXi ⊊ M. In the following, we present an algorithm that computes an EFX allocation when n = 3 and an algorithm that computes a (n - 1)-EFX allocation when n ≥ 4. We first give some definitions.

Definition 11 (Consistent Items). We call item e ∈ M a consistently large item if for all i ∈ N, ci(e) = 1; a consistently small item if for all i ∈ N, ci(e) = ϵ. All other items are called inconsistent items.

Definition 12 (Large/small Items). We call item e ∈ M large to agent i if ci(e) = 1; small to i if ci(e) = ϵ. Let M - i = {e ∈ M : ci(e) = ϵ} be the items that are small to agent i. If an item is large (resp. small) to agent i, but is small (resp. large) to all other agents, we say that it is large (resp. small) only to agent i.

The algorithm we use to compute an EFX allocation for three agents is based on the round-robin algorithm. The algorithm takes as input a set of items and an ordering of the agents {σ1, σ2, . . . , σn} = N, and lets the agents pick their favourite item one-by-one, following the order σ, until all items are allocated. We call the output allocation X a roundrobin allocation. Note that when M ′ ̸= M, the allocation is partial. We index the rounds by 1, 2, · · · ,m. Note that in each round, exactly one item is assigned. For every agent i, we denote that the last round she received an item by ri.

Lemma 13. For a given round-robin allocation, for any two agents i ̸= j such that ri < rj, agent i does not envy agent j, and agent j is EF1 towards agent i.

Lemma 14. Given the round-robin allocation on items M ′ and agents i and j with ri < rj, if there exists e ∈ M \M ′ such that ci(e) = ϵ and cj(e) = 1, then in the allocation (. . . ,Xi + e, . . . ,Xj, . . .), agent i is EFX towards agent j and agent j does not envy agent i.

Theorem 15. There exists an algorithm that computes an EFX allocation for three agents with bi-valued cost functions in O(mlogm) time.

Given an allocation X, we say that agent i strongly-envies agent j if there exists e ∈ Xi such that ci(Xi - e) > ci(Xj). We first note that computing an EFX allocation is easy for some special cases. For instance, if there exist two agents sharing the same cost function, e.g., c1 = c2, we can compute an EFX allocation by partitioning the items into an EFX allocation under the cost function of agent 1, then let agent 3 pick her favourite bundle. Clearly, agent 3 would not envy the other two agents. In addition, since agents 1 and 2 share the same cost function, no matter which bundle they receive, they will not strongly-envy the other agents. Hence in the following we assume that all agents have different cost functions.

Overview. The main idea of our algorithm is to make use of Lemma 13 and 14 to construct an EFX allocation. In particular, given a round-robin allocation X, we would like to assign some unallocated items to improve the fairness guarantee to EFX. Note that for every agent i, every item can be categorised into one of the following four types: consistently large, consistently small, large only to agent i, small only to agent i. For example, suppose every agent i has an item ei that is small only to agent i. Then by computing a roundrobin allocation on items M ′ = M \ {e1, e2, e3} and allocating each ei to agent i, the resulting allocation is EFX, by Lemma 14. When this does not hold, our algorithm carefully examines the number of items of each type in the viewpoint of each agent, and proceeds differently.

Lemma 16. If there exists an item small only to some agent, then an EFX allocation can be computed in polynomial time.

By Lemma 16, it remains to consider that case when every inconsistent item is large only to some agent i. In other words, suppose Li is the set of items that are large only to agent i, then (L1,L2,L3) is a partition of the inconsistent items into three sets. We finish the proof of Theorem 15 by the following two lemmas.

Lemma 17. If there exists |Li| ≥ 2, then an EFX allocation can be computed in polynomial time.

Lemma 18. If |Li| ≤ 1 for all i ∈ N, then an EFX allocation can be computed in polynomial time.

Finally, we consider instances with n ≥ 4 agents and prove the following, whose proof can be found in the full version.

Theorem 19. There exists an algorithm that computes a (n - 1)-EFX allocation for n ≥ 4 agents with bi-valued cost functions in O(nm) time.

6 Conclusion and FutureWork

In this paper we propose algorithms that always compute a 5EFX allocation for three agents and 3n2 -EFX allocation for n ≥ 4 agents. These are the first approximation ratios of EFX that are independent of m for the allocation of indivisible chores. Furthermore, we show that the approximation could be improved for bi-valued instances. We propose algorithms that always compute an EFX allocation for three agents with bi-valued cost functions and (n - 1)-EFX allocation for n ≥ 4 agents. There are many open problems regarding the computation of approximately EFX allocation for chores. For example, it would be interesting to investigate whether constant approximations of EFX allocation exist for general number of agents, and whether EFX allocations exist for three agents or any number of agents with bi-valued cost functions. Observe that to ensure (approximation of) EFX for an agent i, we often need to focus on increasing the costs of other agents, instead of minimizing the cost of i, which can possibly lead to inefficiency in the final allocation. It is thus interesting to study the existence of allocations for chores that are fair, e.g., approximation of EFX, MMS or PROPX, and efficient, e.g., Pareto optimal.

Acknowledgments

Xiaowei Wu is funded by FDCT (File no. 0143/2020/A3, SKL-IOTSC-2021-2023), the SRG of University of Macau (File no. SRG2020-00020-IOTSC) and GDST (2020B1212030003).