Fair and Efficient Allocation of Indivisible Chores with Surplus

1 Introduction

Fair division of a set of indivisible items among agents is a fundamental area with applications in various multi-agent settings. The items can be either goods (provides positive utility) or chores (provides negative utility). The case of goods has been vastly studied [Amanatidis et al., 2022]. On the other hand, the case of chores is relatively new. In both settings, given a set N = [n] of n agents and a set M = [m] of m items, the goal is to find an allocation X = ⟨X1, . . . ,Xn⟩ satisfying some fairness and efficiency criteria where agent i receives the bundle Xi for all i ∈ [n].

In this paper, we focus on fair division of chores when each agent i has a disutility function di : 2M → R≥0 which indicates how much agent i dislikes each subset S ⊆ M of the chores. We assume that each di is additive, i.e., di(S) = ∑j∈S di({j}).

Envy-freeness is one of the most accepted notions of fairness. In the chores setting, allocation X is envy-free if for every pair of agents i and j, di(Xi) ≤ di(Xj). However, envy-freeness is too strong to be satisfied. 1 Hence, to obtain positive results we need to relax the fairness notion. Therefore, we study envy-freeness up to one item (EF1), envyfreeness up to transferring any item (tEFX) and proportionality as our fairness criteria. For efficiency, we consider (fractional) Pareto optimality (fPO).

1.1 EF1 and fPOwith Surplus for nAgents

An allocation X = ⟨X1, . . . ,Xn⟩ is Pareto optimal (PO), if there exists no allocation Y = ⟨Y1, . . . , Yn⟩ such that di(Yi) ≤ di(Xi) for all agents i and for some agent j, dj(Yj) < dj(Xj). For Pareto optimality, we assume Y is an integral allocation. A stronger notion is fractional Pareto optimality (fPO) which allows Y to be a fractional allocation. In a fractional allocation y = ⟨y1, . . . , yn⟩, yi,c is the fraction of chore c ∈ [m] allocated to agent i with ∑i∈[n] yi,c = 1 and yi = (yi,1, . . . , yi,m) is i's bundle. Then di(yi) = ∑c∈[m] yi,c · di({c}) is the disutility of agent i in the fractional allocation.

Fractional Pareto optimality (fPO). Allocation x is fractionally Pareto optimal or fPO, if there exists no fractional allocation y such that di(yi) ≤ di(xi) for all i and for some agent j, dj(yj) < dj(xj).

Envy-freeness up to one chore (EF1). Allocation X = ⟨X1, . . . ,Xn⟩ is EF1 if for all i, j ∈ N, di(Xi) ≤ di(Xj) or there exists a chore c ∈ Xi such that di(Xi \ {c}) ≤ di(Xj).

EF1 is defined for the case of the goods accordingly, with the difference that the good should be removed from the bundle of the envied agent [Budish, 2011]. For both goods and chores settings, EF1 allocations are known to exist, and they can also be computed in polynomial-time [Lipton et al., 2004; Bhaskar et al., 2021]. However, the outputs of these algorithms are not guaranteed to be efficient. Satisfying EF1 and PO simultaneously turns out to be a challenging problem.

1 For example, consider division of one chore among two agents.

In the goods setting under additive valuations, Caragiannis et al. [2016] proved that any allocation with maximum Nash welfare is EF1 and PO. Later, Barman et al. [2018] gave a pseudopolynomial-time algorithm for computing an EF1 and PO allocation, which was recently improved to output an EF1 and fPO allocation [Garg and Murhekar, 2021]. In the case of chores on the other hand, the existence of EF1 and PO allocations is a big open problem. Similar results on chores are known for very limited settings of bivalued disutilities [Garg et al., 2022a; Ebadian et al., 2022], three agents [Garg et al., 2022b] and when chores are divided into two types [Aziz et al., 2022].

In this paper, we make progress in this line of work by proving that given additive disutilities, there exists an EF1 and fPO allocation with (n-1) surplus. The analouge of surplus in the goods setting is charity, which is a well-accepted concept, and it means that some goods might remain unallocated. Caragiannis et al. [2019] introduced the notion of EFX with charity. Many follow-up papers proved relaxations of envy-freeness with charity [Chaudhury et al., 2021b; Berger et al., 2022; Akrami et al., 2022b; Mahara, 2021; Berendsohn et al., 2022]. In the chores setting, by "k surplus", we mean that all the chores are allocated, and at most, k extra chores are allocated to the agents, and each of these chores is a copy of an original chore.

One motivation behind defining the concept of surplus for chores is the lack of progress on the original problem for over half a decade. It is likely that an allocation that is both EF1 and PO might not always exist, and in that case, the concept of surplus seems a good alternative. Moreover, duplicating chores makes sense for many applications. For instance, consider the task of distributing papers among reviewers. The goal is to have all papers reviewed and also be fair toward the reviewers. To this end, it does not harm if a few papers are reviewed more than needed. Another practical scenario is when the chores are going to be repeated. Consider the case where the same set of chores needs to be done every month. This can happen in households, corporations, etc. In this case, multiplying some chore c for k times means that we already decide which agents should do c in the following k months. Thus, when planning for the next k months, we can remove c from the set of chores that need to be assigned.

Our first main result is formally stated in Theorem 1.

Theorem 1. Given additive disutilites, there exists an allocation with at most (n - 1) surplus which is EF1 and fPO. Moreover, it can be computed in polynomial time.

Note that the allocation in Theorem 1 being fPO means that it fractionally Pareto dominates all the allocations with the same surplus. Our approach is based on rounding of competitive equilibrium with equal incomes (CEEI). Since there is no polynomial-time algorithm known for computing a CEEI, we round a (1-ϵ)-approximate-CEEI for ϵ = 1 5nm , which can be computed in polynomial-time [Chaudhury et al., 2022a]. By integrally assigning chores which are fractionally allocated in the (1-ϵ)-CEEI, we guarantee that the final allocation is fPO. However, the main challenge here is to achieve EF1 guarantee with at most n - 1 surplus, which requires careful rounding.

1.2 tEFX or Proportionality for 3 Agents

The discrepancy between known results for the goods and chores setting carries over even for instances with a small number of agents. In the goods setting, EFX allocations always exist for 3 agents with additive utilities [Chaudhury et al., 2020]. However, the analogous problem for chores is open. An allocation X = ⟨X1, . . . ,Xn⟩ is EFX if for all agents i and j and all chores c ∈ Xi, di(Xi \ {c}) ≤ di(Xj). The existence of EFX allocations for chores has been studied in the very limited settings of 3 agents with bivalued disutilites [Zhou and Wu, 2022] and also when agents have the same ordinal preferences on the chores [Li et al., 2022].

Let us briefly discuss the technique to obtain EFX for three agents for the goods setting and why it fails in the chores setting. In [Chaudhury et al., 2020], the high-level idea is to start with an empty allocation and at each step, allocate some unallocated goods to some agents, possibly take away some goods from them or move the bundles among the agents while guaranteeing that the partial allocation is EFX at the end of each step. Basically, the algorithm moves in the space of partial EFX allocations, improving a sophisticated potential function at each step and terminates when it reaches a complete allocation. This algorithm relies on involved concepts such as champion-graphs and half-bundles. In the goods setting, by allocating more goods, we make progress in the sense of improving agents' utilities. However, in the chores setting, by allocating more chores, we make the agents less happy. Therefore, it is not easy to adapt the algorithm and come up with a potential function which improves after more chores get allocated. In fact, the existence of allocations satisfying even weaker notions of fairness than EFX like tEFX is open for the chores setting even when n = 3. Yin and Mehta [2022] proved the existence of a tEFX allocation for three agents if two of them have additive disutility functions and the ratio of their highest to lowest cost is bounded by two.

Envy-freeness up to transferring any chore (tEFX). An allocation is tEFX if no agent i envies another agent j after transferring any chore from i's bundle to j's bundle. Formally, allocation X is tEFX if for all agents i and j and any chore c ∈ Xi, di(Xi \ {c}) ≤ di(Xj ∪ {c}). We note that given additive utility/disutility functions, tEFX is stronger than EF2X studied in [Akrami et al., 2022b]. EF2X guarantees that any envy is removed upon the removal any two items from the envied/envious bundle.

Recently, Akrami et al. [2022a] gave an alternative proof for the existence of EFX allocations for three agents in the goods setting which overcomes the mentioned barrier. We use similar techniques, and instead of moving in the space of partial fair allocations and terminating when reaching a complete allocation, we move in the space of complete allocations and stop when we reach a fair allocation. Our technique resembles the cut-and-choose protocol used for fairly allocating items among two agents. In cut and choose, whether the resource is divisible or indivisible, one agent divides it into two parts so that she finds both parts fair. Then the second agent chooses her favorite part and the remaining part goes to the first agent. A similar idea for the case of three agents would be to find a partition (X1, X2, X3) such that agent 1 finds X1

and X2 fair and agent 2 finds X2 and X3 fair. This way the third agent can choose her favorite bundle and the remaining bundles can be fairly allocated to the two remaining agents.

An allocation X is proportional if for every agent i, di(Xi) ≤ di(M)/n. Note that proportionality is too strong to be satisfied when chores are indivisible. 2 We show that given any instance comprising of three agents with additive disutilities, in polynomial time one can find an allocation that is either proportional or tEFX; the choice of alternative is made by the algorithm. Note that the EFX result for 3 agents in the goods setting is existential and although the approach is constructive, the algorithm is not polynomial. Our second main result is stated in Theorem 2.

Theorem 2. Given an instance comprising of three agents with additive disutilities, and a set of indivisible chores, there exists an allocation X, such that for all i ∈ [3]

• either di(Xi) ≤ 1/3 · di(M), or
• for all c ∈ Xi and j ∈ [3], we have di(Xi \ {c}) ≤ di(Xj ∪ {c}).

Furthermore, such an allocation can be determined in polynomial time.

We remark that although our result does not fully settle the existence of tEFX allocations in the chores setting, the guarantees in Theorem 2 are indeed desirable, especially given that no relaxation of envy-freeness other than EF1, is currently known to exist in the chores setting. Proportionality is a very desirable property of an allocation and is often unattainable in the discrete setting. In fact, the discrete fair division protocol used in Spliddit 3 , prior to the Nash-welfare maximization algorithm in 2015 4 , first checks for a proportional allocation and only if proportional allocations are unattainable, it attempts at finding relaxations of envy-freeness. There is also research in discrete fair division that attempts to give as many agents their proportional share [Feige and Norkin, 2022], whilst satisfying certain relaxations of classical fairness notions.

1.3 Further RelatedWork

The notion of CEEI has a long history dating back to classical theories in microeconomics [Fisher, 1891]. When agents have linear utilities, CEEI with goods is known to be convex, and the equilibrium prices are unique [Eisenberg and Gale, 1959]. Such properties have facilitated the formulation of several polynomial time algorithms [Devanur et al., 2008; Orlin, 2010]. In contrast, CEEI with chores forms a non-convex disconnected set [Bogomolnaia et al., 2017], and admits several equilibrium prices. Branzei and Sandomirskiy [2019] give a polynomial-time algorithm when the number of agents or the number of goods is constant, which was later improved in [Garg and McGlaughlin, 2020; Garg et al., 2021] to the case of mixed manna containing both goods and chores. Later, Chaudhury et al. [2021a] gave a complementary pivot algorithm for finding a CEEI for the case of mixed manna. Recently, Boodaghians et al. [2022] and Chaudhury et al. [2022b] have given polynomial time algorithms for computing (1 - ε)-CEEI. However, the complexity of finding an exact CEEI in the chores setting is open. Moreover, Fisher markets that admit integral equilibria is studied in [Barman and Krishnamurthy, 2019].

2 Consider the counter-example of two agents and one chore.

3 spliddit.org

4 This is elaborated in Introduction of [Caragiannis et al., 2016].

2 Preliminaries

An instance of discrete fair division with chores is given by the tuple ⟨N,M,D⟩, where N = [n] is the set of n agents, M = [m] is the set of m indivisible chores and D = (d1(·), . . . , dn(·)), where each di : 2M → R≥0 is the disutility function of agent i. For all agents i, di is assumed to be normalized, i.e., di(∅) = 0 and monotone, i.e., di(S ∪ {c}) ≥ di(S) for all S ⊆ M and c /∈ S. A function f : 2M → R≥0 is said to be additive if f(S) = ∑s∈S f({s}) for all S ⊆ M. For ease of notation, we use c instead of {c}. For ⊕ ∈ {≤, ≥, <, >}, we use S ⊕i T for di(S) ⊕ di(T ).

Fisher market. In the Fisher market setting for chores in addition to a set N of agents, a set M of chores and a disutility profile D, each agent i has an initial liability ℓi > 0 which specifies how much money this agent should earn in the market. We denote the fisher market instance by F = ⟨N, M, D, L⟩ where L = (ℓ1, . . . , ℓn). Given the instance F , the market outcome is a pair of fractional allocation and payment vector ⟨x, p⟩. For all agents i and chores c, xi,c denotes what fraction of c is assigned to i and pc denotes the price of chore c. The income of agent i from market outcome ⟨x, p⟩ is p(xi) = ∑c∈M xi,cpc. We can also treat integral bundles as vectors with 0 and 1 entries. Given payment vector p, the pain per buck of agent i for chore c is di(c)/pc. We denote the minimum pain per buck of agent i at payment p by MPBi, i.e., MPBi = minc∈M di(c)/pc.

Definition 1. Given a Fisher market instance F, a market outcome ⟨x, p⟩ is a Fisher market equilibrium if

• the market clears, i.e., for all chores c ∈ M, ∑i∈[n] xi,c = 1, and
• for all agents i, ∑c∈M xi,c · pc = ℓi, and
• all agents only receive chores with minimum pain per buck, i.e., for all agents i and chores c, if xi,c > 0, then di(c)/pc = MPBi.

If for all agents i, ℓi = 1, then a Fisher equilibrium is called competitive equilibrium with equal incomes or CEEI. Bogomolnaia et al. [2017] proved that a CEEI always exists when agents have linear disutilities.

For goods, any Fisher equilibrium is fPO [Mas-Colell et al., 1995]. The same holds true for chores as essentially the same argument shows.

Proposition 1. Given additive disutilities, any Fisher equilibrium is fractionally Pareto Optimal.

Given a market ⟨x, p⟩, the payment graph of x is a weighted bipartite (undirected) graph with one part consisting of nodes corresponding to the n agents and one part consisting of nodes corresponding to the m chores. We denote the payment graph of x by G⟨x,p⟩. There is an edge between agent i and chores c, if and only if xi,c > 0. For any edge {i, c} in G⟨x,p⟩, the weight of {i, c} is ei,c = xi,c · pc which is the earning of agent i from chore c in this market. For any graph G, we denote the set of edges of G by E(G).

There is no known polynomial time algorithm for computing a CEEI. However, Boodaghians et al. [2022] gave an exterior point algorithm to compute a (1-ϵ)-CEEI in polynomial time. The running time was improved by a combinatorial algorithm in [Chaudhury et al., 2022a]. Namely, a (1-ϵ)-CEEI can be computed in time polynomial in the size of the input and 1ϵ . In a (1-ϵ)-CEEI, the income of each agent is between 1 - ϵ and 1 + ϵ. We formally define (1 - ϵ)-CEEI below.

Definition 2. Given a Fisher market F, a market outcome ⟨x, p⟩ is a (1 - ϵ)-CEEI, for an ϵ ∈ [0, 1], if

• the market clears, i.e., for all chores c ∈ M, ∑i∈[n] xi,c = 1, and
• for all agents i, 1- ϵ ≤ ∑c∈M xi,c · pc ≤ 1+ ϵ, and
• all agents only receive chores with minimum pain per buck, i.e., for all agents i and chores c, if xi,c > 0, then di(c)/pc = MPBi.

Similar to envy-freeness and its relaxations, we can define payment envy-freeness and its relaxations. In particular, given a payment vector p = (p1, . . . , pm) for the chores, an integral allocation X is payment envy-free up to one chore or pEF1, if for all agents i and j, either Xi = ∅ or there exists a chore c ∈ Xi such that p(Xi \ c) ≤ p(Xj).

Proposition 2 (Lemma 3.5 in Ebadian et al., 2022). If an integral allocation X is pEF1 with respect to payment vector p and ⟨X, p⟩ is a Fisher equilibrium, then X is EF1.

3 EF1 + fPO + Surplus

In this section, we prove that after introducing at most n - 1 chores, an allocation exists which is EF1 and fPO at the same time. Each of these new chores is a copy of an existing chore. Moreover, we compute such an allocation in polynomial time. The high-level idea is to first consider a fractional allocation x which admits a (1 - ϵ)-CEEI for ϵ = 1 5nm . Then to each agent, we fully allocate some of the chores that are fractionally allocated to her in x. This way, each agent only receives her MPB chores and therefore the allocation is fPO. Furthermore, we guarantee that each agent earns at least 1-ϵ amount of money and there exists a chore that upon its removal, the earned money drops below 1-ϵ. This way, we can also guarantee EF1 property for the allocation. In order to achieve such an allocation, we allocate some chores to multiple agents and hence we need multiple copies of some of the chores. However, we prove that the number of required copies does not exceed n - 1. Basically, our algorithm introduces at most n-1 copies of the existing chores and finds an integral Fisher equilibrium where each agent earns 1 - ϵ amount of money up to one chore.

Lemma 1. Given any Fisher equilibrium ⟨x, p⟩ for a Fisher market F, there exists a polynomial time algorithm makeAcyclic(x, p) that computes allocation y such that ⟨y, p⟩ is a Fisher equilibrium for F and G⟨y,p⟩ is acyclic.

Now we explain Algorithm 1. Given instance I, let ϵ = 1 5nm and ⟨x, p⟩ = approxCEEI(I, ϵ) be the (1 - ϵ)-CEEI computed in polynomial time by [Chaudhury et al., 2022a]. First we run makeAcyclic(x, p) to make G⟨x,p⟩ acyclic. Then, we compute the integral allocation Y as follows. Our Algorithm consists of two phases. We start with G = G⟨x,p⟩ and during Phase 1, we alter G. At each point in time, let y be such that G is the payment graph of ⟨y, p⟩ (i.e. G = G⟨y,p⟩). Let Nv be the set of the neighbors of node v in G.

Phase 1. Start from an empty allocation Y and run phase 1 as long as there is an unallocated chore c∗ such that |Nc∗| = 1. Phase 1 of the algorithm consist of 2 steps. Basically, as long as there exists an unallocated chore c∗ with |Nc∗| = 1, run Step 1 and then Step 2.

Step 1. For all unallocated chores c with |Nc| = 1, let ic be the agent such that Nc = {ic}. Then add c to Yic .

Step 2. For all agents i and chores c such that {i, c} ∈ E(G), if for all chores c′ ∈ Yi ∪{c}, p((Yi ∪c) \ c′ ) > 1-ϵ, then distribute the earning of agent i from chore c equally among the other neighbors of c and remove the edge {i, c} from G. Recall that ej,c = xj,cpc is the earning agent j receives from chore c in the market outcome ⟨x, p⟩. Formally, for all j ∈ Nc \ {i}, we set

Phase 2. The second phase starts when for all unallocated chores c, |Nc| ̸= 1. In Lemma 2 we prove the case |Nc| = 0 is not possible and therefore for all remaining chores c, |Nc| > 1. Each of the connected components of G is a tree. For each of the trees T do the following. Take an arbitrary agent i0 in T and consider T rooted at i0. For agent i0, as long as p(Yi0 ) < 1-ϵ, keep adding chores from Ni \Yi0 to Yi0 . Then iterate on the agents in T in a breadth-first order and for each agent i do the following. Let ci be the chore corresponding to the parent of agent i in T. If ci is not allocated yet, add it to Yi, i.e., Yi ← Yi ∪ {ci}. Then, keep adding the chores in Ni \ (Yi ∪ {ci}) to Yi until p(Yi) ≥ 1 - ϵ or until we run out of chores. Note that all chores in Ni \ (Yi ∪ {ci}) correspond to children nodes of agent i in T. If at the end of this process p(Yi) < 1 - ϵ, add a copy of ci to Yi.

Algorithm 1 shows the pseudocode of our algorithm. In the rest of this section we prove that the final allocation Y is pEF1 and fPO with at most (n - 1) surplus.

Observation 1. For all agents i, p(yi) ≥ 1 - ϵ at any time during Phase 1.

Proof. The proof is by induction. In the beginning of the algorithm, y = x and thus the claim holds. Now fix an agent i and let y be the allocation such that G = G⟨y,p⟩ before deleting an edge e and y∗ be the allocation such that G\{e} = G⟨y∗ ,p⟩. Assuming p(yi) ≥ 1-ϵ, we prove p(y∗ i ) ≥ 1-ϵ. If e is not incident to i, then p(y∗ i ) ≥ p(yi) and thus the claim holds. If e is incident to i, then p((Yi ∪c) \ c′ ) > 1-ϵ for all c′ ∈ Yi∪{c}. Therefore, p(Yi) = p((Yi∪c)\c) > 1-ϵ. Note that all chores in Yi are incident to i in G⟨y∗ ,p⟩. Therefore, p(y∗ i ) ≥ p(Yi) > 1 - ϵ.

Input: Instance I. Output: Allocation Y . 1: ϵ ← 1 5nm 2: ⟨x, p⟩ ←makeAcyclic(approxCEEI(I, ϵ)) 3: G←payment graph of ⟨x, p⟩ 4: // Phase 1: 5: while ∃ an uncallocated chore c∗ : |Nc∗| = 1 do 6: // Step 1: 7: for i ∈ [n] do 8: Yi ← {c ∈ M|yi,c = 1} 9: // Step 2: 10: for {i, c} ∈ E(G) do 11: if ∀c′ ∈ Yi ∪ {c}: p((Yi ∪ c) \ c′ ) > 1 - ϵ then 12: for j ∈ Nc do 13: ej,c ← ej,c + yi,c·pc |Nc|-1 14: G ← G \ {{i, c}} 15: // Phase 2: 16: for all connected components T of G do 17: // Let T be rooted at i0 18: for all agents i in T in BFS-order do 19: if i ̸= i0 then 20: ci ← parent chore of i in T 21: if ci is not allocated then 22: Yi ← Yi ∪ {ci} 23: for c ∈ Ni \ (Yi ∪ {ci}) do 24: if p(Yi) < 1 - ϵ then 25: Yi ← Yi ∪ {c} 26: if p(Yi) < 1 - ϵ then 27: Yi ← Yi ∪ {ci} 28: return Y

Observation 2. For all agents i, p(yi) ≤ 1 + (2n - 1)ϵ at any time during Phase 1.

Proof. In the beginning of the algorithm, since y = x, we have ∑i∈N p(yi) ≤ (1 + ϵ)n. Allocation y changes during Phase 1 when an edge is deleted in Step 2. Upon the deletion of edge {i, c}, yi,c · pc is distributed among the neighbors of c (in case any such neighbors exist). Therefore, the value of ∑i∈N p(yi) cannot increase during Phase 1. Thus, for all agents i at any point during Phase 1 we have

Therefore, p(yi) ≤ 1 + (2n - 1)ϵ.

Lemma 2. Before the execution of Phase 2, for all unallocated chores c, Nc ̸= ∅.

Observation 3. All the chores in M are allocated in Y .

Proof. By Lemma 2, in the beginning of Phase 2 no unallocated chore is isolated in G. In Phase 2, all the chores that are the parent of some agent in T get allocated. Moreover, the leaf chores in T got allocated in Phase 1. Hence, all the chores are allocated in Y .

Observation 4. The number of copied chores in Y is at most n - 1.

Proof. In Phase 1, no chore is allocatedmore than once. Consider the step in which we allocate chores to agent i when iterating on T in breadth-first order. Note that except ci, all the chores that we allocate to i are her children nodes. Since we run BFS on T, these children chores had not been assigned to any other agent before. Therefore, for each non-root agent, we might need to copy one chore and namely her parent node. Thus, the number of copied chores is at most n - 1.

Proof. Fix an agent i. Since ⟨x, p⟩ is a (1-ϵ)-CEEI, p(xi) ≥ 1-ϵ. Note that if at some iteration of Step 2, an adjacent edge of i is deleted, then p(Yi) ≥ 1 - ϵ. Now assume no adjacent edge of i is deleted. Let Xi = {c ∈ M|xi,c > 0}. We have p(Xi) ≥ p(xi) ≥ 1 - ϵ. Note that all the chores in Xi which are not added to Yi in phase 1 are either children of i in T or her parent node. In either of the cases, as long as p(Yi) < 1 - ϵ, we add these chores to Yi. If we stop before adding the whole chores in Xi to Yi, it means that the condition p(Yi) ≥ 1 - ϵ is satisfied. Otherwise we have Yi = Xi and thus, p(Yi) ≥ 1 - ϵ.

Observation 6. For all agents i, there exists a chore c ∈ Yi such that p(Yi \ c) < 1 - ϵ.

Proof. Consider Y in the end of Phase 1. By Observation 2, p(Yi) ≤ p(yi) ≤ 1 + (2n - 1)ϵ. Let c be the chore with maximum pc in Yi. We have

Therefore, there exists a chores c ∈ Yi, such that p(Yi \ c) ≤ 1 - ϵ before the execution of Phase 2. Also, there exists a chore c ∈ Yi ∪ {ci} such that p((Yi ∪ {ci}) \ c) < 1 - ϵ. Otherwise, the edge (i, ci) would be deleted before Phase 2. So if in Phase 2 no chore is added to Yi or only ci is added to Yi, the claim holds. Otherwise, let c be the last chore added to Yi. Since we stop adding chores to Yi the moment p(Yi) > 1 - ϵ, p(Yi \ c) ≤ 1 - ϵ.

Now we are ready to prove Theorem 1.

Theorem 1. Given additive disutilites, there exists an allocation with at most (n - 1) surplus which is EF1 and fPO. Moreover, it can be computed in polynomial time.

Proof. Let Y be the output of Algorithm 1. Let M ′ be the set of copied chores that are allocated in Y in addition to the chores in M. First we prove that ⟨Y, p⟩ is a Fisher equilibrium for the market given by ⟨N,M∪M ′ , D, (p(Y1), . . . , p(Yn))⟩.

By Observation 3, the market clears. Since ⟨x, p⟩ is a CEEI for ⟨N,M,D⟩, for each agent i, all the chores in Xi = {c ∈ M|xi,c > 0} are MPB chores. Since Yi ⊆ Xi, all the chores in Yi are also MPB chores. In the end, it is clear that each agent i earns p(Yi). So all the conditions of a Fisher equilibrium hold for ⟨Y, p⟩. Now we prove each of the properties for Y separately.

EF1. By Observations 5 and 6, Y is pEF1. Since ⟨Y, p⟩ is a Fisher equilibrium, by Proposition 2, Y is EF1.

fPO. By Proposition 1, every Fisher equilibrium is fPO.

(n-1) surplus By Observation 3, all the chores in M are allocated and by Observation 4, the size of the surplus is at most n - 1.

Now we prove Algorithm 1 terminates in polynomial time. The subroutines makeAcyclic runs in poly(n,m) and approxCEEI(x, ϵ) runs in poly(n,m) for ϵ = 1 5nm . Step 1 can be executed at most m times since in each iteration of Step 1 a chore gets allocated. Step 2 can be executed at most m + n - 1 times since in each iteration of Step 2 an edge gets deleted. Phase 2 is a BFS subroutine which terminates in poly(n,m). Therefore, the total running time of Algorithm 1 is polynomial with respect to n and m.

Remark. The bound n-1 on the size of the surplus is tight for Algorithm 1. Consider the instance with n agents and one chore c with disutility 1 for all the agents. Then any ϵ-CEEI (for ϵ = 1 5n ) allocates some fraction of c to all of the agents and Algorithm 1 copies c for n - 1 times and allocates one copy to each agent.

4 Fairness Among Three Agents

Given an allocation X = ⟨X1,X2, . . . ,Xn⟩, we say that an agent i strongly envies an agent j if and only if Xi \c >i Xj ∪ c, for some c ∈ Xi. Thus, an allocation is a tEFX allocation if there is no strong envy between any pair of agents. We now introduce certain concepts that will be useful in this section.

Definition 3 (tEFX feasibility). Given a partition X = (X1,X2, . . . ,Xn) of M, a bundle Xk is tEFX-feasible to agent i if and only if for all chores c ∈ Xk and all j ∈ [n],

Therefore an allocation X = ⟨X1, X2, . . . , Xn⟩ is tEFX if and only if for each agent i, Xi is tEFX-feasible.

Note that when agents have additive disutility functions, Xk is tEFX-feasible for agent i if and only if for all j ∈ [n], Xk \ c∗ ≤i Xj ∪ c∗ for c∗ = argminc∈Xk di(c).

EFX-feasibility is defined in the same way. Formally, given a partition X = (X1,X2, . . . ,Xn) of M, a bundle Xk is EFX-feasible to agent i if and only if for all chores c ∈ Xk and all j ∈ [n], Xk \ c ≤i Xj .

Restriction to non-degenerate instances is no loss of generality and simplifies arguments about linear programs. The same is true for allocation of goods and chores. Here, it means that no two distinct bundles of chores are valued the same by any agent. Chaudhury et al. [2020] showed that to prove the existence of EFX allocations in the goods setting, when agents have additive valuations, it suffices to show the

Algorithm 2 EFX-Identical

• 1: Input : Instance I = ([n],M, d)
• 2: Output: allocation X
• 3: X ← ⟨∅, ∅, . . . , ∅⟩
• 4: Let d(c1) ≥ d(c2) ≥ . . . ≥ d(cm)
• 5: for i ← 1 to mdo
• 6: Let j = argminℓ∈[n]d(Xℓ)
• 7: Xj ←Xj ∪ {ci}
• 8: Return X

existence of EFX allocations for all non-degenerate instances. We adapt their approach and show that the same claim holds, even when agents have additive disutilities and the notion of fairness is tEFX. Henceforth, in the rest of this section we assume that the given instance is non-degenerate, implying that every agent has positive disutility for every chore.

In this section we prove Theorem 2. We start with an allocation which is EFX assuming all agents' disutility functions are d1. During the algorithm we maintain a partition (X1,X2,X3) of the chores such that all the following invariants hold.

Invariant 1. X1 and X2 are tEFX-feasible for agent 1.

Invariant 2. For all i ∈ [2] and c ∈ Xi, Xi \ c ≤1 X3.

Invariant 3. X3 is tEFX-feasible for agent 3.

We use the potential function Φ(X) = |X1| + |X2|. Each iteration of the algorithm updates allocation such that the new allocation is proportional or tEFX or satisfies all the invariants and has a smaller potential value. Since the value of the potential is at most m, the number of iterations is at most m.

Li et al. [2022] proved when agents have identical ordering on the chores, an EFX allocation can be computed in polynomial time. Lemma 3 follows from their result.

Lemma 3. When all agents have additive disutility function d, Algorithm 2 returns an EFX allocation in time O(m log m).

In the beginning, we run Algorithm 2 with d = d1 to obtain allocation X. Note that all X1, X2 and X3 are EFXfeasible for agent 1. Without loss of generality, assume X3 ≤3 X1 ≤3 X2, i.e., d3(X3) ≤ d3(X1) ≤ d3(X2). Then, since all bundles are EFX-feasible for agent 1, Invariants 1 and 2 hold and since X3 is the favorite bundle of agent 3, Invariant 3 holds too. If X1 or X2 is tEFX-feasible for agent 3, we can allocate a tEFX-feasible bundle to each of the agents. Without loss of generality assume X2 is also tEFX-feasible for agent 3. Then we let agent 2 pick her favorite bundle. If she picks X2, we assign X1 to agent 1 and X3 to agent 3. If agent 2 picks X1, then we assign X2 to agent 1 and X3 to agent 3. The case that agent 2 picks X3 is symmetric.

Now we assume that X3 is the only tEFX-feasible bundle for agent 3. Let c1 = argminc∈X1 d3(c). Then the algorithm moves c1 from X1 to X3. Let X′1 = X1 \ c1, X′2 = X2 and X′3 = X3 ∪ c1. The next step of the algorithm depends on whether X′2 is tEFX-feasible for agent 1 or not. In Lemma 4 we show that if X′2 is tEFX-feasible for agent 1 then X′ satisfies all the invariants.

Observation 7. Let c1 = argminc∈X1 d3(c). If X3 is the only tEFX-feasible bundle for agent 3 and X1 ≤3 X2, then X1 \ c1 >3 X3 ∪ c1.

Proof. Assume otherwise. For all c ∈ X1 we have

Since X1 ≤3 X2, X1 is tEFX-feasible for agent 3 which is a contradiction.

Lemma 4. If X′2 is tEFX-feasible for agent 1, then Invariants 1, 2 and 3 hold.

Proof. For all c ∈ X′1 and i ∈ {2, 3} we have

Therefore, Invariant 1 holds. Also, for all i ∈ [2] and c ∈ X′ i

Thus, Invariant 2 holds. By Observation 7, we have X′1 >3 X′3 . Also, X′2 =3 X2 ≥3 X1 ≥3 X′1 . Hence, X′3 is the favorite bundle of agent 3 and is tEFX-feasible for her. Therefore, Invariant 3 holds as well.

After moving c1, we have Φ(X′ ) = |X′1 | + |X′2 | = |X1| - 1 + |X2| < Φ(X). Thus, if X′2 is tEFX-feasible for agent 1, by Lemma 4 all the invariants hold and also the potential function decreases.

Now we assume that X′2 is not tEFX-feasible for agent 1. As long as the second bundle is not tEFX-feasible for agent 1, keep moving chores from X′2 to X′1 in non-decreasing order of d1(·). Formally, let X′2 = {c′1 , c′2 , . . . , c′k } and c′1 ≤1 c′2 ≤1 . . . ≤1 c′k . Then Y1 = X′1 ∪ {c′1 , . . . , c′ℓ } and Y2 = X′2 \{c′1 , . . . , c′ℓ } such that Y1 <1 Y2 and Y1 ∪c′ℓ+1 ≥1 Y2 \ c′ℓ+1 . Note that ℓ ≥ 1. Let Y3 = X′3 .

Lemma 5. Invariants 1 and 2 hold for Y .

Proof. We have

Therefore, Invariant 2 holds. We also know that for all c′ ∈ Y2, c′ ≥1 cℓ+1. Hence, for all c′ ∈ Y2,

Since Y1 <1 Y2, Invariant 1 holds too.

Now if Y3 is tEFX-feasible for agent 3, then all the invariants hold and Φ(Y ) = |Y1| + |Y2| = |X′1 | + |X′2 | = |X1| + |X2| - 1 < Φ(X). In Section 4.1, we prove that if Y3 is not tEFX-feasible for agent 3, we can obtain a proportional allocation.

4.1 Proportional AllocationWhen Y3 Is Not tEFX-feasible for Agent 3

In the following observations, we prove that Y1 and Y2 are proportional for agent 1, and Y2 and Y3 are proportional for agent 3. Then without any further modification of the bundles, we allocate these bundles to the agents such that the final allocation is proportional.

Observation 8. d3(Y3) < d3(M)/3.

Proof. Since X′2 = X2 and X′1 = X1 \ c1, we have X′2 =3 X2 ≥3 X1 ≥3 X′1 . Also, by Observation 7, X′1 >3 X′3 . Therefore, X′2 >3 X′3 =3 Y3. Hence, d3(X′3 ) < d3(X′1 ) and d3(X′3 ) < d3(X′2 ). By additivity of d3(·), we get that d3(X′3 ) < d3(M)/3.

Observation 9. If Y3 is not tEFX-feasible for agent 3, then d3(Y2) < d3(M)/3.

Proof. By Observation 7, X′1 >3 X′3 =3 Y3. Since X′1 ⊂ Y1, we have Y1 ≥3 X′1 >3 Y3. Since Y3 is not tEFXfeasible for agent 3, it cannot be her favorite bundle. Since d3(Y1) > d3(Y3), we have d3(Y2) < d3(Y3). By Observation 8, d3(Y3) < d3(M)/3. Hence, d3(Y2) < d3(M)/3.

Finally, in Observation 10, we prove that d1(Y1) ≤ d1(M)/3 and d1(Y2) ≤ d1(M)/3.

Proof. Consider the allocation ⟨X1 ∪ c′1 ,X2 \ c′1 ,X3⟩. Note that since Invariants 1 and 2 hold for X, we have d1(X2 \ c′1 ) ≤ d1(X1 ∪ c′1 ) and d1(X2 \ c′1 ) ≤ d1(X3). By additivity of d1, we have d1(X2 \ c′1 ) ≤ d1(M)/3. Now it suffices to prove that d1(Y1) ≤ d1(X2 \ c′1 ) and d1(Y2) ≤ d1(X2 \ c′1 ). Note that d1(Y1) < d1(Y2) and Y2 ⊆ X2 \ c′1 . Therefore, we have d1(Y1) < d1(Y2) ≤ d1(X2 \ c′1 ).

At this stage of the algorithm, by Observation 10 we have that d1(Y1) ≤ d1(M)/3 and d1(Y2) ≤ d1(M)/3. Also by Observations 8 and 9, we have d3(Y3) < d3(M)/3 and d3(Y2) < d3(M)/3. Now we let agent 2 pick her favorite bundle. Let it be Yi. Clearly, d2(Yi) ≤ d2(M)/3. As already argued before, no matter which bundle agent 2 chooses, we can allocate one of Y1 or Y2 to agent 1 and one of Y2 or Y3 to agent 3. Therefore, we obtain a proportional allocation.

5 Conclusion

We have introduced a concept of k surplus and showed the existence of an allocation that is both EF1 and fPO with at most n - 1 surplus in the case of indivisible chores. Furthermore, such an allocation can be computed in polynomial time. A natural open question is whether there exists an allocation that is both EF1 and fPO with < n - 1 surplus.

Our second result shows the existence of allocation of indivisible chores among 3 agents that is either tEFXor proportional. Since proportionality is a very strong guarantee, which is not possible to satisfy for every instance, this result is the first non-trivial result for a slight relaxation of EFX for 3 agents. A natural open question is whether EFX allocations exist for 3 agents.

Acknowledgements

Jugal Garg was supported by NSF Grant CCF-1942321. Ruta Mehta was supported by NSF Grant CCF-1750436.