# Fair and Efficient Allocation of Indivisible Chores with Surplus

Hannaneh Akrami  Max Planck Institute for Informatics, Germany
Graduiertenschule Informatik, Universität des Saarlandes, Germany  Bhaskar Ray
Chaudhury Bhaskar Ray Chaudhury was partially supported by NSF Grants
CCF-1942321 and CCF-1750436. University of Illinois at Urbana-Champaign, USA
Jugal Garg Jugal Garg was supported by NSF Grant CCF-1942321. University of
Illinois at Urbana-Champaign, USA  Kurt Mehlhorn  Max Planck Institute for
Informatics, Germany  Ruta Mehta Ruta Mehta was supported by NSF Grant
CCF-1750436. University of Illinois at Urbana-Champaign, USA

###### Abstract

We study fair division of indivisible chores among $n$ agents with additive
disutility functions. Two well-studied fairness notions for indivisible items
are envy-freeness up to one/any item (EF1/EFX) and the standard notion of
economic efficiency is Pareto optimality (PO). There is a noticeable gap
between the results known for both EF1 and EFX in the goods and chores
settings. The case of chores turns out to be much more challenging. We reduce
this gap by providing slightly relaxed versions of the known results on goods
for the chores setting. Interestingly, our algorithms run in polynomial time,
unlike their analogous versions in the goods setting.

We introduce the concept of $k$ surplus which means that up to $k$ more chores
are allocated to the agents and each of them is a copy of an original chore.
We present a polynomial-time algorithm which gives EF1 and PO allocations with
$(n-1)$ surplus.

We relax the notion of EFX slightly and define tEFX which requires that the
envy from agent $i$ to agent $j$ is removed upon the transfer of any chore
from the $i$’s bundle to $j$’s bundle. We give a polynomial-time algorithm
that in the chores case for $3$ agents returns an allocation which is either
proportional or tEFX. Note that proportionality is a very strong criterion in
the case of indivisible items, and hence both notions we guarantee are
desirable.

##  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 [3]. 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=\langle
X_{1},\ldots,X_{n}\rangle$ satisfying some fairness and efficiency criteria
where agent $i$ receives the bundle $X_{i}$ for all $i\in[n]$.

In this paper, we focus on fair division of chores when each agent $i$ has a
disutility function $d_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ which
indicates how much agent $i$ dislikes each subset $S\subseteq M$ of the
chores. We assume that each $d_{i}$ is additive, i.e., $d_{i}(S)=\sum_{j\in
S}d_{i}(\\{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$,
$d_{i}(X_{i})\leq d_{i}(X_{j})$. However, envy-freeness is too strong to be
satisfied.111For example, consider division of one chore among two agents.
Hence, to obtain positive results we need to relax the fairness notion.
Therefore, we study envy-freeness up to one item (EF1), envy-freeness up to
transferring any item (tEFX) and proportionality as our fairness criteria. For
efficiency, we consider (fractional) Pareto optimality (fPO).

###  1.1 EF1 and fPO with Surplus for $n$ Agents

An allocation $X=\langle X_{1},\ldots,X_{n}\rangle$ is Pareto optimal (PO), if
there exists no allocation $Y=\langle Y_{1},\ldots,Y_{n}\rangle$ such that
$d_{i}(Y_{i})\leq d_{i}(X_{i})$ for all agents $i$ and for some agent $j$,
$d_{j}(Y_{j})<d_{j}(X_{j})$. 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=\langle y_{1},\ldots,y_{n}\rangle$, $y_{i,c}$ is the fraction of chore
$c\in[m]$ allocated to agent $i$ with $\sum_{i\in[n]}y_{i,c}=1$ and
$y_{i}=(y_{i,1},\ldots,y_{i,m})$ is $i$’s bundle. Then
$d_{i}(y_{i})=\sum_{c\in[m]}y_{i,c}\cdot d_{i}(\\{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 $d_{i}(y_{i})\leq d_{i}(x_{i})$ for all
$i$ and for some agent $j$, $d_{j}(y_{j})<d_{j}(x_{j})$.

#### Envy-freeness up to one chore (EF1).

Allocation $X=\langle X_{1},\ldots,X_{n}\rangle$ is EF1 if for all $i,j\in N$,
$d_{i}(X_{i})\leq d_{i}(X_{j})$ or there exists a chore $c\in X_{i}$ such that
$d_{i}(X_{i}\setminus\\{c\\})\leq d_{i}(X_{j})$.

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 [13]. For both
goods and chores settings, EF1 allocations are known to exist, and they can
also be computed in polynomial-time [32, 9]. However, the outputs of these
algorithms are not guaranteed to be efficient. Satisfying EF1 and PO
simultaneously turns out to be a challenging problem.

In the goods setting under additive valuations, Caragiannis et al. [15] proved
that any allocation with maximum Nash welfare is EF1 and PO. Later, Barman et
al. [6] gave a pseudopolynomial-time algorithm for computing an EF1 and PO
allocation, which was recently improved to output an EF1 and fPO allocation
[28]. 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 [29, 22], three agents [30] and
when chores are divided into two types [4].

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. [14] introduced the notion of EFX with charity. Many
follow-up papers proved relaxations of envy-freeness with charity [20, 8, 2,
33, 7]. 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-\epsilon)$-approximate-CEEI for $\epsilon=\frac{1}{5nm}$, which can be
computed in polynomial-time [17]. By integrally assigning chores which are
fractionally allocated in the $(1-\epsilon)$-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 [19].
However, the analogous problem for chores is open. An allocation $X=\langle
X_{1},\ldots,X_{n}\rangle$ is EFX if for all agents $i$ and $j$ and all chores
$c\in X_{i}$, $d_{i}(X_{i}\setminus\\{c\\})\leq d_{i}(X_{j})$. The existence
of EFX allocations for chores has been studied in the very limited settings of
$3$ agents with bivalued disutilites [37] and also when agents have the same
ordinal preferences on the chores [31].

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 [19], 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 [36] 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\in X_{i}$,
$d_{i}(X_{i}\setminus\\{c\\})\leq d_{i}(X_{j}\cup\\{c\\})$. We note that given
additive utility/disutility functions, tEFX is stronger than EF2X studied in
[2]. EF2X guarantees that any envy is removed upon the removal any two items
from the envied/envious bundle.

Recently, Akrami et al. [1] 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 $(X_{1},X_{2},X_{3})$ such
that agent $1$ finds $X_{1}$ and $X_{2}$ fair and agent $2$ finds $X_{2}$ and
$X_{3}$ 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$, $d_{i}(X_{i})\leq
d_{i}(M)/n$. Note that proportionality is too strong to be satisfied when
chores are indivisible.222Again consider the counter example of two agents and
one chore. 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\in[3]$

  * •

either $d_{i}(X_{i})\leq 1/3\cdot d_{i}(M)$, or

  * •

for all $c\in X_{i}$ and $j\in[3]$, we have $d_{i}(X_{i}\setminus\\{c\\})\leq
d_{i}(X_{j}\cup\\{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
Spliddit333spliddit.org, prior to the Nash-welfare maximization algorithm in
2015444This is elaborated in Introduction of [15]., 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 [24], whilst satisfying certain relaxations of classical fairness
notions.

###  1.3 Further Related Work

The notion of CEEI has a long history dating back to classical theories in
microeconomics [25]. When agents have linear utilities, CEEI with goods is
known to be convex, and the equilibrium prices are unique [23]. Such
properties have facilitated the formulation of several polynomial time
algorithms [21, 35]. In contrast, CEEI with chores forms a non-convex
disconnected set [10] and admits several equilibrium prices. Branzei and
Sandomirskiy [12] give a polynomial-time algorithm when the number of agents
or the number of goods is constant, which was later improved in [27, 26] to
the case of mixed manna containing both goods and chores. Later, Chaudhury et
al. [16] gave a complementary pivot algorithm for finding a CEEI for the case
of mixed manna, which runs fast in practice and is provably polynomial-time
when the number of agents or the number of items (goods and chores) is
constant. Recently, Boodaghians et al. [11] and Chaudhury et al. [18] have
given polynomial time algorithms for computing $(1-\varepsilon)$-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
[5].

##  2 Preliminaries

An instance of discrete fair division with chores is given by the tuple
$\langle N,M,\mathcal{D}\rangle$, where $N=[n]$ is the set of $n$ agents,
$M=[m]$ is the set of $m$ indivisible chores and
$\mathcal{D}=(d_{1}(\cdot),\dots,d_{n}(\cdot))$, where each
$d_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ is the disutility function of
agent $i$. For all agents $i$, $d_{i}$ is assumed to be _normalized_ , i.e.,
$d_{i}(\emptyset)=0$ and _monotone_ , i.e., $d_{i}(S\cup\\{c\\})\geq d_{i}(S)$
for all $S\subseteq M$ and $c\notin S$. A function
$f:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ is said to be _additive_ if
$f(S)=\sum_{s\in S}f(\\{s\\})$ for all $S\subseteq M$. For ease of notation,
we use $c$ instead of $\\{c\\}$. For
$\oplus\in\left\\{\leq,\geq,<,>\right\\}$, we use $S\oplus_{i}T$ for
$d_{i}(S)\oplus d_{i}(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 $\mathcal{D}$, each agent $i$ has
an initial liability $\ell_{i}>0$ which specifies how much money this agent
should earn in the market. We denote the fisher market instance by $F=\langle
N,M,\mathcal{D},\mathcal{L}\rangle$ where
$\mathcal{L}=(\ell_{1},\ldots,\ell_{n})$. Given the instance $F$, the market
outcome is a pair of fractional allocation and payment vector $\langle
x,p\rangle$. For all agents $i$ and chores $c$, $x_{i,c}$ denotes what
fraction of $c$ is assigned to $i$ and $p_{c}$ denotes the price of chore $c$.
The income of agent $i$ from market outcome $\langle x,p\rangle$ is
$p(x_{i})=\sum_{c\in M}x_{i,c}p_{c}$. 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 $d_{i}(c)/p_{c}$. We denote the minimum pain per
buck of agent $i$ at payment $p$ by $\text{MPB}_{i}$, i.e.,
$\text{MPB}_{i}=\min_{c\in M}d_{i}(c)/p_{c}$.

######  Definition 1.

Given a Fisher market instance $F$, a market outcome $\langle x,p\rangle$ is a
Fisher market equilibrium if

  * •

the market clears, i.e., for all chores $c\in M$, $\sum_{i\in[n]}x_{i,c}=1$,
and

  * •

for all agents $i$, $\sum_{c\in M}x_{i,c}\cdot p_{c}=\ell_{i}$, and

  * •

all agents only receive chores with minimum pain per buck, i.e., for all
agents $i$ and chores $c$, if $x_{i,c}>0$, then
$d_{i}(c)/p_{c}=\text{MPB}_{i}$.

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

For goods, any Fisher equilibrium is fPO [34]. The same holds true for chores
as essentially the same argument shows.

######  Proposition 1.

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

###### Proof.

Let $\langle x,p\rangle$ be a Fisher equilibrium and let $y$ be any other
allocation. Then

$\displaystyle\sum_{i\in[n]}\frac{d_{i}(x_{i})}{\text{MPB}_{i}}$
$\displaystyle=\sum_{i\in[n]}\sum_{c\in M}x_{i,c}p_{c}$
$\displaystyle=\sum_{c\in M}p_{c}$ $\displaystyle=\sum_{i\in[n]}\sum_{c\in
M}y_{i,c}p_{c}$ $\displaystyle\leq\sum_{i\in[n]}\sum_{c\in
M}\frac{y_{i,c}d_{i}(c)}{\text{MPB}_{i}}$
$\displaystyle=\sum_{i\in[n]}\frac{d_{i}(y_{i})}{\text{MPB}_{i}}.$

Hence, it cannot be the case that $d_{i}(y_{i})\leq d_{i}(x_{i})$ for all
$i\in[n]$ with one strict inequality. ∎

Given a market $\langle x,p\rangle$, 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_{\langle x,p\rangle}$. There
is an edge between agent $i$ and chores $c$, if and only if $x_{i,c}>0$. For
any edge $\\{i,c\\}$ in $G_{\langle x,p\rangle}$, the weight of $\\{i,c\\}$ is
$e_{i,c}=x_{i,c}\cdot p_{c}$ 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. [11] gave an exterior point algorithm to compute a
$(1-\epsilon)$-CEEI in polynomial time. The running time was improved by a
combinatorial algorithm in [17]. Namely, a $(1-\epsilon)$-CEEI can be computed
in time polynomial in the size of the input and $\frac{1}{\epsilon}$. In a
$(1-\epsilon)$-CEEI, the income of each agent is between $1-\epsilon$ and
$1+\epsilon$. We formally define $(1-\epsilon)$-CEEI below.

######  Definition 2.

Given a Fisher market $F$, a market outcome $\langle x,p\rangle$ is a
$(1-\epsilon)$-CEEI, for an $\epsilon\in[0,1]$, if

  * •

the market clears, i.e., for all chores $c\in M$, $\sum_{i\in[n]}x_{i,c}=1$,
and

  * •

for all agents $i$, $1-\epsilon\leq\sum_{c\in M}x_{i,c}\cdot p_{c}\leq
1+\epsilon$, and

  * •

all agents only receive chores with minimum pain per buck, i.e., for all
agents $i$ and chores $c$, if $x_{i,c}>0$, then
$d_{i}(c)/p_{c}=\text{MPB}_{i}$.

Similar to envy-freeness and its relaxations, we can define payment envy-
freeness and its relaxations. In particular, given a payment vector
$p=(p_{1},\ldots,p_{m})$ 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 $X_{i}=\emptyset$ or there exists a chore $c\in X_{i}$ such that
$p(X_{i}\setminus c)\leq p(X_{j})$.

######  Proposition 2 (Lemma 3.5 in Ebadian _et al._ , 2022).

If an integral allocation $X$ is pEF1 with respect to payment vector $p$ and
$\langle X,p\rangle$ is a Fisher equilibrium, then $X$ is EF1.

###### Proof.

Consider any two agents $i,j$ such that $X_{i}\neq\emptyset$. Let $c\in X_{i}$
be such that $p(X_{i}\setminus c)\leq p(X_{j})$. We have

$\displaystyle X_{i}\setminus c$ $\displaystyle=_{i}\text{MPB}_{i}\cdot
p(X_{i}\setminus c)$ ($\langle X,p\rangle$ is a Fisher equilibrium)
$\displaystyle\leq\text{MPB}_{i}\cdot p(X_{j})$ ($X$ is pEF1)
$\displaystyle=\text{MPB}_{i}\cdot\sum_{c\in X_{j}}\frac{p(c)}{d_{i}(c)}\cdot
d_{i}(c)$ $\displaystyle\leq_{i}X_{j}.$ ($\text{MPB}_{i}=\mathit{min}_{c\in
M}d_{i}(c)/p(c)$)

∎

##  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-\epsilon)$-CEEI for
$\epsilon=\frac{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-\epsilon$ amount of money and
there exists a chore that upon its removal, the earned money drops below
$1-\epsilon$. 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-\epsilon$ amount of
money up to one chore.

######  Lemma 1.

Given any Fisher equilibrium $\langle x,p\rangle$ for a Fisher market $F$,
there exists a polynomial time algorithm $\mathtt{makeAcyclic}(x,p)$ that
computes allocation $y$ such that $\langle y,p\rangle$ is a Fisher equilibrium
for $F$ and $G_{\langle y,p\rangle}$ is acyclic.

###### Proof.

We define $\mathtt{makeAcyclic}(x,p)$ as following. If $G_{\langle
x,p\rangle}$ is acyclic then return $\langle x,p\rangle$. Otherwise, as long
as $G_{\langle x,p\rangle}$ has a cycle do the following. Let
$C=(a_{1},c_{1}\ldots a_{t},c_{t},a_{1})$ be a cycle in $G_{\langle
x,p\rangle}$ where $a_{i}$ corresponds to the agent nodes and $c_{i}$ to the
chore nodes. Let us denote the earning of agent $i$ from chore $c$ in
allocation $x$ as $e^{x}_{i,c}=x_{i,c}\cdot p_{c}$. Without loss of
generality, assume $e^{x}_{a_{1},c_{1}}$ is minimum among all $e^{x}_{i,j}$
where $(i,j)$ is an edge in $C$. Now consider the allocation $y$ where for all
$i\in[t]$ $e^{y}_{a_{i},c_{i}}=e^{x}_{a_{i},c_{i}}-e$,
$e^{y}_{a_{i},c_{i-1}}=e^{x}_{a_{i},c_{i-1}}+e$. For all other pairs of
$(i,j)$, $e^{y}_{i,j}=e^{x}_{i,j}$. In the end of each iteration of detecting
a cycle and computing $y$, set $x\leftarrow y$.

First we prove $\mathtt{makeAcyclic}(x,p)$ terminates in polynomial time. Let
$x$ be the allocation in the beginning of each iteration of detecting a cycle
and $y$ be the allocation in the end of the iteration. Note that $E(G_{\langle
y,p\rangle})\subsetneq E(G_{\langle x,p\rangle})$ since the edge
$(a_{1},c_{1})$ exists in $G_{\langle x,p\rangle}$ but not in $G_{\langle
y,p\rangle}$. Since at each step the number of edges decreases and each step
terminates in polynomial time, the procedure terminates in polynomial time and
in the end $G_{\langle y,p\rangle}$ is acyclic.

Now we prove the final $\langle y,p\rangle$ is a Fisher equilibrium by
induction. Note that in the beginning $\langle x,p\rangle$ is a Fisher
equilibrium. Now assuming $\langle x,p\rangle$ is a Fisher equilibrium in the
beginning of an iteration of removing an edge, we prove in the end of that
iteration $\langle y,p\rangle$ is a Fisher equilibrium too. Note that for each
chore $c$, $\sum_{i\in[n]}e^{y}_{i,c}=e^{x}_{i,c}=p_{c}$. Thus, all chores are
fully allocated in $y$. Also, for each agents $i$, $\sum_{c\in
M}e^{y}_{i,c}=\sum_{c\in M}e^{x}_{i,c}=\ell_{i}$. Moreover, for all agents $i$
and chore $c$, if $y_{i,c}>0$, then $x_{i,c}>0$. Therefore, in $y$ like in $x$
agents only receive chores with MPB. This means that $\langle y,p\rangle$ is
also a Fisher equilibrium. ∎

Now we explain Algorithm 1. Given instance $\mathcal{I}$, let
$\epsilon=\frac{1}{5nm}$ and $\langle
x,p\rangle=\mathtt{approxCEEI}(\mathcal{I},\epsilon)$ be the
$(1-\epsilon)$-CEEI computed in polynomial time by [17]. First we run
$\mathtt{makeAcyclic}(x,p)$ to make $G_{\langle x,p\rangle}$ acyclic. Then, we
compute the integral allocation $Y$ as follows. Our Algorithm consists of two
phases. We start with $G=G_{\langle x,p\rangle}$ and during Phase $1$, we
alter $G$. At each point in time, let $y$ be such that $G$ is the payment
graph of $\langle y,p\rangle$ (i.e. $G=G_{\langle y,p\rangle}$). Let $N_{v}$
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 $|N_{c^{*}}|=1$. Phase $1$ of the
algorithm consist of $2$ steps. Basically, as long as there exists an
unallocated chore $c^{*}$ with $|N_{c^{*}}|=1$, run Step $1$ and then Step
$2$.

#### Step 1.

For all unallocated chores $c$ with $|N_{c}|=1$, let $i_{c}$ be the agent such
that $N_{c}=\\{i_{c}\\}$. Then add $c$ to $Y_{i_{c}}$.

#### Step 2.

For all agents $i$ and chores $c$ such that $\\{i,c\\}\in E(G)$, if for all
chores $c^{\prime}\in Y_{i}\cup\\{c\\}$, $p((Y_{i}\cup c)\setminus
c^{\prime})>1-\epsilon$, 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 $e_{j,c}=x_{j,c}p_{c}$ is the earning agent $j$ receives
from chore $c$ in the market outcome $\langle x,p\rangle$. Formally, for all
$j\in N_{c}\setminus\\{i\\}$, we set

$e_{j,c}\leftarrow e_{j,c}+\frac{y_{i,c}\cdot p_{c}}{|N_{c}|-1}.$

#### Phase 2.

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

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.

Algorithm 1 $\mathtt{fairAndEfficient}(\mathcal{I})$
Input: Instance $\mathcal{I}$.
Output: Allocation $Y$.

1:$\epsilon\leftarrow\frac{1}{5nm}$

2:$\langle x,p\rangle\leftarrow$
$\mathtt{makeAcyclic}(\mathtt{approxCEEI}(\mathcal{I},\epsilon))$

3:$G\leftarrow$ payment graph of $\langle x,p\rangle$

4:// Phase 1:

5:while $\exists$ an uncallocated chore $c^{*}$: $|N_{c^{*}}|=1$ do

6: // Step 1:

7: for $i\in[n]$ do

8: $Y_{i}\leftarrow\\{c\in M|y_{i,c}=1\\}$

9: // Step 2:

10: for $\\{i,c\\}\in E(G)$ do

11: if $\forall c^{\prime}\in Y_{i}\cup\\{c\\}$: $p((Y_{i}\cup c)\setminus
c^{\prime})>1-\epsilon$ then

12: for $j\in N_{c}$ do

13: $e_{j,c}\leftarrow e_{j,c}+\frac{y_{i,c}\cdot p_{c}}{|N_{c}|-1}$

14: $G\leftarrow G\setminus\\{\\{i,c\\}\\}$

15:// Phase 2:

16:for all connected components $T$ of $G$ do

17: // Let $T$ be rooted at $i_{0}$

18: for all agents $i$ in $T$ in BFS-order do

19: if $i\neq i_{0}$ then

20: $c_{i}\leftarrow$ parent chore of $i$ in $T$

21: if $c_{i}$ is not allocated then

22: $Y_{i}\leftarrow Y_{i}\cup\\{c_{i}\\}$

23: for $c\in N_{i}\setminus(Y_{i}\cup\\{c_{i}\\})$ do

24: if $p(Y_{i})<1-\epsilon$ then

25: $Y_{i}\leftarrow Y_{i}\cup\\{c\\}$

26: if $p(Y_{i})<1-\epsilon$ then

27: $Y_{i}\leftarrow Y_{i}\cup\\{c_{i}\\}$

28:return $Y$

######  Observation 1.

For all agents $i$, $p(y_{i})\geq 1-\epsilon$ 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_{\langle y,p\rangle}$ before deleting an edge $e$ and $y^{*}$ be the
allocation such that $G\setminus\\{e\\}=G_{\langle y^{*},p\rangle}$. Assuming
$p(y_{i})\geq 1-\epsilon$, we prove $p(y^{*}_{i})\geq 1-\epsilon$. If $e$ is
not incident to $i$, then $p(y^{*}_{i})\geq p(y_{i})$ and thus the claim
holds. If $e$ is incident to $i$, then $p((Y_{i}\cup c)\setminus
c^{\prime})>1-\epsilon$ for all $c^{\prime}\in Y_{i}\cup\\{c\\}$. Therefore,
$p(Y_{i})=p((Y_{i}\cup c)\setminus c)>1-\epsilon$. Note that all chores in
$Y_{i}$ are incident to $i$ in $G_{\langle y^{*},p\rangle}$. Therefore,
$p(y^{*}_{i})\geq p(Y_{i})>1-\epsilon$. ∎

######  Observation 2.

For all agents $i$, $p(y_{i})\leq 1+(2n-1)\epsilon$ at any time during Phase
$1$.

###### Proof.

In the beginning of the algorithm, since $y=x$, we have $\sum_{i\in
N}p(y_{i})\leq(1+\epsilon)n$. Allocation $y$ changes during Phase $1$ when an
edge is deleted in Step $2$. Upon the deletion of edge $\\{i,c\\}$,
$y_{i,c}\cdot p_{c}$ is distributed among the neighbors of $c$ (in case any
such neighbors exist). Therefore, the value of $\sum_{i\in N}p(y_{i})$ cannot
increase during Phase $1$. Thus, for all agents $i$ at any point during Phase
$1$ we have

$\displaystyle(1+\epsilon)n$ $\displaystyle\geq\sum_{j\in
N}p(x_{j})\geq\sum_{j\in N}p(y_{j})$
$\displaystyle\geq(1-\epsilon)(n-1)+p(y_{i}).$ (by Observation 1)

Therefore, $p(y_{i})\leq 1+(2n-1)\epsilon$. ∎

######  Lemma 2.

Before the execution of Phase $2$, for all unallocated chores $c$,
$N_{c}\neq\emptyset$.

###### Proof.

Towards a contradiction, assume at some point during Phase $1$, $\\{i,c\\}$ is
the only edge incident to $c$ and it gets deleted. Let $y$ be such that
$G=G_{\langle y,p\rangle}$ just before deleting $\\{i,c\\}$. Note that during
Phase $1$, as long as a chore has an incident edge, it remains fully
allocated. Therefore, $y_{i,c}=1$ since $i$ is the only neighbor of $c$. Also,
$p(Y_{i})>1-\epsilon$ (otherwise $\\{i,c\\}$ would not be deleted). We have

$\displaystyle 1+(2n-1)\epsilon$ $\displaystyle\geq p(y_{i})$ (by Observation
2) $\displaystyle\geq p(Y_{i})+y_{i,c}\cdot p_{c}$
$\displaystyle\geq(1-\epsilon)+p_{c}.$ (by Observation 1)

Thus, $p_{c}\leq 2n\epsilon$. Together with Observation 2 we get

$\displaystyle p(Y_{i}\cup c)\leq 1+(2n-1)\epsilon+2n\epsilon<1+4n\epsilon.$
(1)

Let $c^{*}$ be a chore with maximum $p_{c^{*}}$ in $Y_{i}\cup\\{c\\}$. By
Pigeonhole principle, $p_{c^{*}}\geq\frac{p(Y_{i}\cup
c)}{|Y_{i}\cup\\{c\\}|}\geq\frac{p(Y_{i}\cup c)}{m}$. Thus

$\displaystyle p((Y_{i}\cup c)\setminus c^{*})$
$\displaystyle\leq\frac{m-1}{m}\cdot p(Y_{i}\cup c)$
$\displaystyle<\frac{m-1}{m}\cdot(1+4n\epsilon)$ (by Inequality (1))
$\displaystyle\leq 1-\epsilon,$ (since $\epsilon=\frac{1}{5nm}$)

which is a contradiction with the edge $\\{i,c\\}$ getting deleted. Therefore,
for all chores $c$ at least one incident edge of $c$ remains until the end of
Phase $1$. ∎

######  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 allocated more than once. Consider the step in which
we allocate chores to agent $i$ when iterating on $T$ in breadth-first order.
Note that except $c_{i}$, 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$. ∎

######  Observation 5.

For all agents $i$, $p(Y_{i})\geq 1-\epsilon$.

###### Proof.

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

######  Observation 6.

For all agents $i$, there exists a chore $c\in Y_{i}$ such that
$p(Y_{i}\setminus c)<1-\epsilon$.

###### Proof.

Consider $Y$ in the end of Phase $1$. By Observation 2, $p(Y_{i})\leq
p(y_{i})\leq 1+(2n-1)\epsilon$. Let $c$ be the chore with maximum $p_{c}$ in
$Y_{i}$. We have

$\displaystyle p(Y_{i}\setminus c)$ $\displaystyle\leq\frac{m-1}{m}\cdot
p(Y_{i})$ ($p_{c}\geq p(Y_{i})/m$ by Pigeonhole principle)
$\displaystyle\leq\frac{m-1}{m}\cdot(1+(2n-1)\epsilon)$ (by Observation 2)
$\displaystyle\leq 1-\epsilon.$ (since $\epsilon=\frac{1}{5nm}$)

Therefore, there exists a chores $c\in Y_{i}$, such that $p(Y_{i}\setminus
c)\leq 1-\epsilon$ before the execution of Phase $2$. Also, there exists a
chore $c\in Y_{i}\cup\\{c_{i}\\}$ such that $p((Y_{i}\cup\\{c_{i}\\})\setminus
c)<1-\epsilon$. Otherwise, the edge $(i,c_{i})$ would be deleted before Phase
$2$. So if in Phase $2$ no chore is added to $Y_{i}$ or only $c_{i}$ is added
to $Y_{i}$, the claim holds. Otherwise, let $c$ be the last chore added to
$Y_{i}$. Since we stop adding chores to $Y_{i}$ the moment
$p(Y_{i})>1-\epsilon$, $p(Y_{i}\setminus c)\leq 1-\epsilon$. ∎

Now we are ready to prove Theorem 1. See 1

###### Proof.

Let $Y$ be the output of Algorithm 1. Let $M^{\prime}$ be the set of copied
chores that are allocated in $Y$ in addition to the chores in $M$. First we
prove that $\langle Y,p\rangle$ is a Fisher equilibrium for the market given
by $\langle N,M\cup M^{\prime},\mathcal{D},(p(Y_{1}),\ldots,p(Y_{n}))\rangle$.
By Observation 3, the market clears. Since $\langle x,p\rangle$ is a CEEI for
$\langle N,M,\mathcal{D}\rangle$, for each agent $i$, all the chores in
$X_{i}=\\{c\in M|x_{i,c}>0\\}$ are MPB chores. Since $Y_{i}\subseteq X_{i}$,
all the chores in $Y_{i}$ are also MPB chores. In the end, it is clear that
each agent $i$ earns $p(Y_{i})$. So all the conditions of a Fisher equilibrium
hold for $\langle Y,p\rangle$. Now we prove each of the properties for $Y$
separately.

#### EF1.

By Observations 5 and 6, $Y$ is pEF1. Since $\langle Y,p\rangle$ is a Fisher
equilibrium, by Proposition 2, $Y$ is EF1.

#### fPO.

By Proposition 1, every Fisher equilibrium is fPO.

####  $\mathbf{(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
$\mathtt{makeAcyclic}$ runs in poly$(n,m)$ and
$\mathtt{approxCEEI}(x,\epsilon)$ runs in poly$(n,m)$ for
$\epsilon=\frac{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 $\epsilon$-CEEI (for $\epsilon=\frac{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=\langle X_{1},X_{2},\dots,X_{n}\rangle$, we say that an
agent $i$ _strongly envies_ an agent $j$ if and only if $X_{i}\setminus
c>_{i}X_{j}\cup c$, for some $c\in X_{i}$. 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=(X_{1},X_{2},\dots,X_{n})$ of $M$, a bundle $X_{k}$ is
tEFX-feasible to agent $i$ if and only if for all chores $c\in X_{k}$ and all
$j\in[n]$,

$X_{k}\setminus c\leq_{i}X_{j}\cup c.$

Therefore an allocation $X=\langle X_{1},X_{2},\dots,X_{n}\rangle$ is tEFX if
and only if for each agent $i$, $X_{i}$ is tEFX-feasible.

Note that when agents have additive disutility functions, $X_{k}$ is tEFX-
feasible for agent $i$ if and only if for all $j\in[n]$, $X_{k}\setminus
c^{*}\leq_{i}X_{j}\cup c^{*}$ for $c^{*}=\text{argmin}_{c\in X_{k}}d_{i}(c)$.

EFX-feasibility is defined in the same way. Formally, given a partition
$X=(X_{1},X_{2},\dots,X_{n})$ of $M$, a bundle $X_{k}$ is EFX-feasible to
agent $i$ if and only if for all chores $c\in X_{k}$ and all $j\in[n]$,
$X_{k}\setminus c\leq_{i}X_{j}.$

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. [19] showed that to prove the
existence of EFX allocations in the goods setting, when agents have additive
valuations, it suffices to show the existence of EFX allocations for all non-
degenerate instances. We adapt their approach and in Appendix A we 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 $d_{1}$. During the algorithm we
maintain a partition $(X_{1},X_{2},X_{3})$ of the chores such that all the
following invariants hold.

######  Invariant 1.

$X_{1}$ and $X_{2}$ are tEFX-feasible for agent $1$.

######  Invariant 2.

For all $i\in[2]$ and $c\in X_{i}$, $X_{i}\setminus c\leq_{1}X_{3}$.

######  Invariant 3.

$X_{3}$ is tEFX-feasible for agent $3$.

We use the potential function $\Phi(X)=|X_{1}|+|X_{2}|$. Each iteration of our
algorithm updates the 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$.

Algorithm 2 EFX-Identical

1:Input : Instance $\mathcal{I}=([n],M,d)$

2:Output: allocation $X$

3:$X\leftarrow\langle\emptyset,\emptyset,\ldots,\emptyset\rangle$

4:Let $d(c_{1})\geq d(c_{2})\geq\ldots\geq d(c_{m})$

5:for $i\leftarrow 1\text{ to }m$ do

6: Let $j=\textit{argmin}_{\ell\in[n]}d(X_{\ell})$

7: $X_{j}\leftarrow X_{j}\cup\\{c_{i}\\}$

8:Return $X$

Li et al. [31] proved when agents have identical ordering on the chores, an
EFX allocation can be computed in polynomial time. For completeness, we prove
Lemma 3.

######  Lemma 3.

When all agents have additive disutility function $d$, Algorithm 2 returns an
EFX allocation in time $\mathcal{O}(m\log m)$.

###### Proof.

The proof is by induction on the number of allocated chores. In the beginning,
the empty allocation is EFX. Now assume the allocation is EFX right before
allocating chore $c_{i}$ to agent $j$. It suffices to prove that agent $j$
does not strongly envy any other agent. For all chores $c\in
X_{j}\cup\\{c_{i}\\}$ and all agents $j^{\prime}\neq j$ we have

$\displaystyle d(X_{j}\cup\\{c_{i}\\}\setminus\\{c\\})$
$\displaystyle=d(X_{j})+d(c_{i})-d(c)$ (additivity of $d$) $\displaystyle\leq
d(X_{j})$ ($d(c_{i})\leq d(c)$) $\displaystyle\leq d(X_{j^{\prime}}).$
($j=\textit{argmin}_{\ell\in[n]}d(X_{\ell})$)

Sorting the chores according to their disutility takes $\mathcal{O}(m\log m)$
time. We keep the pairs $(d(X_{i}),X_{i})$ in a priority queue which takes
$\mathcal{O}(n\log n)$. Then each round of allocating a chore requires a
delete-min action ($\mathcal{O}(1)$) and an insert ($\mathcal{O}(\log n)$).
Hence, Algorithm 2 terminates in time $\mathcal{O}(m\log m+n\log n+m\log
n)=\mathcal{O}(m\log m)$. ∎

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

Now we assume that $X_{3}$ is the only tEFX-feasible bundle for agent $3$. Let
$c_{1}=\textit{argmin}_{c\in X_{1}}d_{3}(c)$. Then the algorithm moves $c_{1}$
from $X_{1}$ to $X_{3}$. Let $X^{\prime}_{1}=X_{1}\setminus c_{1}$,
$X^{\prime}_{2}=X_{2}$ and $X^{\prime}_{3}=X_{3}\cup c_{1}$. The next step of
the algorithm depends on whether $X^{\prime}_{2}$ is tEFX-feasible for agent
$1$ or not. In Lemma 4 we show that if $X^{\prime}_{2}$ is tEFX-feasible for
agent $1$ then $X^{\prime}$ satisfies all the invariants.

######  Observation 7.

Let $c_{1}=\textit{argmin}_{c\in X_{1}}d_{3}(c)$. If $X_{3}$ is the only tEFX-
feasible bundle for agent $3$ and $X_{1}\leq_{3}X_{2}$, then $X_{1}\setminus
c_{1}>_{3}X_{3}\cup c_{1}$.

###### Proof.

Assume otherwise. For all $c\in X_{1}$ we have

$\displaystyle X_{1}\setminus c$ $\displaystyle\leq_{3}X_{1}\setminus c_{1}$
($c_{1}\leq_{3}c$ and additivity of $d_{3}$) $\displaystyle\leq_{3}X_{3}\cup
c_{1}$ $\displaystyle\leq_{3}X_{3}\cup c.$ ($c_{1}\leq_{3}c$ and additivity of
$d_{3}$)

Since $X_{1}\leq_{3}X_{2}$, $X_{1}$ is tEFX-feasible for agent $3$ which is a
contradiction. ∎

######  Lemma 4.

If $X^{\prime}_{2}$ is tEFX-feasible for agent $1$, then Invariants 1, 2 and 3
hold.

###### Proof.

For all $c\in X^{\prime}_{1}$ and $i\in\\{2,3\\}$ we have

$\displaystyle X^{\prime}_{1}\setminus c$ $\displaystyle\leq_{1}X_{1}\setminus
c$ ($X^{\prime}_{1}\subset X_{1}$) $\displaystyle\leq_{1}X_{i}\cup c$ ($X_{1}$
is tEFX-feasible for agent $1$) $\displaystyle\leq_{1}X^{\prime}_{i}\cup c.$
($X_{i}\subseteq X^{\prime}_{i}$)

Therefore, Invariant 1 holds. Also, for all $i\in[2]$ and $c\in
X^{\prime}_{i}$

$\displaystyle X^{\prime}_{i}\setminus c$ $\displaystyle\leq_{1}X_{i}\setminus
c$ ($X^{\prime}_{i}\subseteq X_{i}$) $\displaystyle\leq_{1}X_{3}$ (Invariant 2
holds for $X$) $\displaystyle\leq_{1}X^{\prime}_{3}.$ ($X_{3}\subset
X^{\prime}_{3}$)

Thus, Invariant 2 holds. By Observation 7, we have
$X^{\prime}_{1}>_{3}X^{\prime}_{3}$. Also,
$X^{\prime}_{2}=_{3}X_{2}\geq_{3}X_{1}\geq_{3}X^{\prime}_{1}$. Hence,
$X^{\prime}_{3}$ is the favorite bundle of agent $3$ and is tEFX-feasible for
her. Therefore, Invariant 3 holds as well. ∎

After moving $c_{1}$, we have
$\Phi(X^{\prime})=|X^{\prime}_{1}|+|X^{\prime}_{2}|=|X_{1}|-1+|X_{2}|<\Phi(X)$.
Thus, if $X^{\prime}_{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^{\prime}_{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^{\prime}_{2}$ to $X^{\prime}_{1}$ in non-decreasing order of
$d_{1}(\cdot)$. Formally, let
$X^{\prime}_{2}=\\{c^{\prime}_{1},c^{\prime}_{2},\ldots,c^{\prime}_{k}\\}$ and
$c^{\prime}_{1}\leq_{1}c^{\prime}_{2}\leq_{1}\ldots\leq_{1}c^{\prime}_{k}$.
Then $Y_{1}=X^{\prime}_{1}\cup\\{c^{\prime}_{1},\ldots,c^{\prime}_{\ell}\\}$
and
$Y_{2}=X^{\prime}_{2}\setminus\\{c^{\prime}_{1},\ldots,c^{\prime}_{\ell}\\}$
such that $Y_{1}<_{1}Y_{2}$ and $Y_{1}\cup
c^{\prime}_{\ell+1}\geq_{1}Y_{2}\setminus c^{\prime}_{\ell+1}$. Note that
$\ell\geq 1$. Let $Y_{3}=X^{\prime}_{3}$.

######  Lemma 5.

Invariants 1 and 2 hold for $Y$.

###### Proof.

We have

$\displaystyle Y_{1}$ $\displaystyle<_{1}Y_{2}\leq_{1}X^{\prime}_{2}\setminus
c^{\prime}_{1}$ ($Y_{2}\subseteq X^{\prime}_{2}\setminus c^{\prime}_{1}$)
$\displaystyle\leq_{1}X^{\prime}_{3}$ (Invariant 2 holds for $X^{\prime}$ by
Lemma 4) $\displaystyle=_{1}Y_{3}$ . ($Y_{3}=X^{\prime}_{3}$)

Therefore, Invariant 2 holds. We also know that for all $c^{\prime}\in Y_{2}$,
$c^{\prime}\geq_{1}c_{\ell+1}$. Hence, for all $c^{\prime}\in Y_{2}$,

$\displaystyle Y_{1}\cup c^{\prime}\geq_{1}Y_{1}\cup
c^{\prime}_{\ell+1}\geq_{1}Y_{2}\setminus
c^{\prime}_{\ell+1}\geq_{1}Y_{2}\setminus c^{\prime}.$

Since $Y_{1}<_{1}Y_{2}$, Invariant 1 holds too. ∎

Now if $Y_{3}$ is tEFX-feasible for agent $3$, then all the invariants hold
and
$\Phi(Y)=|Y_{1}|+|Y_{2}|=|X^{\prime}_{1}|+|X^{\prime}_{2}|=|X_{1}|+|X_{2}|-1<\Phi(X)$.
In Section 4.1, we prove that if $Y_{3}$ is not tEFX-feasible for agent $3$,
we can obtain a proportional allocation.

###  4.1 Proportional Allocation When $Y_{3}$ Is Not tEFX-feasible for Agent
$3$

In the following observations, we prove that $Y_{1}$ and $Y_{2}$ are
proportional for agent $1$, and $Y_{2}$ and $Y_{3}$ 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.

$d_{3}(Y_{3})<d_{3}(M)/3$.

###### Proof.

We have

$\displaystyle X^{\prime}_{2}=_{3}X_{2}$ $\displaystyle\geq_{3}X_{1}$
($X^{\prime}_{2}=X_{2}$) $\displaystyle\geq_{3}X^{\prime}_{1}$
($X^{\prime}_{1}=X_{1}\setminus c_{1}$) $\displaystyle>_{3}X^{\prime}_{3}$
(Observation 7) $\displaystyle=_{3}Y_{3}.$ ($Y_{3}=X^{\prime}_{3}$)

Hence, $d_{3}(X^{\prime}_{3})<d_{3}(X^{\prime}_{1})$ and
$d_{3}(X^{\prime}_{3})<d_{3}(X^{\prime}_{2})$. By additivity of
$d_{3}(\cdot)$, we get that $d_{3}(X^{\prime}_{3})<d_{3}(M)/3$. ∎

######  Observation 9.

If $Y_{3}$ is not tEFX-feasible for agent $3$, then $d_{3}(Y_{2})<d_{3}(M)/3$.

###### Proof.

We have

$\displaystyle Y_{1}$ $\displaystyle\geq_{3}X^{\prime}_{1}$
($X^{\prime}_{1}\subset Y_{1}$) $\displaystyle>_{3}X^{\prime}_{3}$
(Observation 7) $\displaystyle=_{3}Y_{3}.$ ($Y_{3}=X^{\prime}_{3}$)

Since $Y_{3}$ is not tEFX-feasible for agent $3$, it cannot be her favorite
bundle. Since $d_{3}(Y_{1})>d_{3}(Y_{3})$, we have
$d_{3}(Y_{2})<d_{3}(Y_{3})$. By Observation 8, $d_{3}(Y_{3})<d_{3}(M)/3$.
Hence, $d_{3}(Y_{2})<d_{3}(M)/3$. ∎

Finally, in Observation 10, we prove that $d_{1}(Y_{1})\leq d_{1}(M)/3$ and
$d_{1}(Y_{2})\leq d_{1}(M)/3$.

######  Observation 10.

$d_{1}(Y_{1})\leq d_{1}(M)/3$ and $d_{1}(Y_{2})\leq d_{1}(M)/3$.

###### Proof.

Consider the allocation $\langle X_{1}\cup c^{\prime}_{1},X_{2}\setminus
c^{\prime}_{1},X_{3}\rangle$. Note that since Invariants 1 and 2 hold for $X$,
we have $d_{1}(X_{2}\setminus c^{\prime}_{1})\leq d_{1}(X_{1}\cup
c^{\prime}_{1})$ and $d_{1}(X_{2}\setminus c^{\prime}_{1})\leq d_{1}(X_{3})$.
By additivity of $d_{1}$, we have $d_{1}(X_{2}\setminus c^{\prime}_{1})\leq
d_{1}(M)/3$. Now it suffices to prove that $d_{1}(Y_{1})\leq
d_{1}(X_{2}\setminus c^{\prime}_{1})$ and $d_{1}(Y_{2})\leq
d_{1}(X_{2}\setminus c^{\prime}_{1})$. Note that $d_{1}(Y_{1})<d_{1}(Y_{2})$
and $Y_{2}\subseteq X_{2}\setminus c^{\prime}_{1}$. Therefore, we have
$d_{1}(Y_{1})<d_{1}(Y_{2})\leq d_{1}(X_{2}\setminus c^{\prime}_{1})$. ∎

At this stage of the algorithm, by Observation 10 we have that
$d_{1}(Y_{1})\leq d_{1}(M)/3$ and $d_{1}(Y_{2})\leq d_{1}(M)/3$. Also by
Observations 8 and 9, we have $d_{3}(Y_{3})<d_{3}(M)/3$ and
$d_{3}(Y_{2})<d_{3}(M)/3$. Now we let agent $2$ pick her favorite bundle. Let
it be $Y_{i}$. Clearly, $d_{2}(Y_{i})\leq d_{2}(M)/3$. As already argued
before, no matter which bundle agent $2$ chooses, we can allocate one of
$Y_{1}$ or $Y_{2}$ to agent $1$ and one of $Y_{2}$ or $Y_{3}$ 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.

## References

  * [1] Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta.  EFX allocations: Simplifications and improvements.  CoRR, abs/2205.07638, 2022.
  * [2] Hannaneh Akrami, Rojin Rezvan, and Masoud Seddighin.  An EF2X allocation protocol for restricted additive valuations.  In Luc De Raedt, editor, Proc. 31st Intl. Joint Conf. Artif. Intell. (IJCAI), pages 17–23, 2022.
  * [3] Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris.  Fair division of indivisible goods: A survey.  In Proc. 31st Intl. Joint Conf. Artif. Intell. (IJCAI), pages 5385–5393, 2022.
  * [4] Haris Aziz, Jeremy Lindsay, Angus Ritossa, and Mashbat Suzuki.  Fair allocation of two types of chores.  CoRR, abs/2211.00879, 2022.
  * [5] Siddharth Barman and Sanath Kumar Krishnamurthy.  On the proximity of markets with integral equilibria.  In Proc. 33th Conf. Artif. Intell. (AAAI), pages 1748–1755, 2019.
  * [6] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 557–574, 2018.
  * [7] Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma.  Fixed-point cycles and approximate EFX allocations.  In Proc. 47th Symp. Math. Foundations of Computer Science (MFCS), volume 241, pages 17:1–17:13, 2022.
  * [8] Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat.  Almost full EFX exists for four agents.  In Proc. 36th Conf. Artif. Intell. (AAAI), 2022.
  * [9] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish.  On approximate envy-freeness for indivisible chores and mixed resources.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 207, pages 1:1–1:23, 2021\.
  * [10] Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaia.  Competitive division of a mixed manna.  Econometrica, 85(6):1847–1871, 2017.
  * [11] Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta.  Polynomial time algorithms to find an approximate competitive equilibrium for chores.  In Proc. 33rd Symp. Discrete Algorithms (SODA), pages 2285–2302, 2022.
  * [12] Simina Brânzei and Fedor Sandomirskiy.  Algorithms for competitive division of chores.  CoRR, abs/1907.01766, 2019.
  * [13] Eric Budish.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  Journal of Political Economy, 119(6):1061–1103, 2011.
  * [14] Ioannis Caragiannis, Nick Gravin, and Xin Huang.  Envy-freeness up to any item with high Nash welfare: The virtue of donating items.  In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 527–545, 2019.
  * [15] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum Nash welfare.  In Proceedings of the 17th ACM Conference on Economics and Computation (EC), pages 305–322, 2016.
  * [16] Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta.  Competitive allocation of a mixed manna.  In Proc. 32nd Symp. Discrete Algorithms (SODA), pages 1405–1424, 2021.
  * [17] Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta.  Competitive equilibrium with chores: Combinatorial algorithm and hardness.  In Proc. 23rd Conf. Economics and Computation (EC), pages 1106–1107. ACM, 2022.
  * [18] Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta.  On the existence of competitive equilibrium with chores.  In Proc. 13th Symp. Innovations in Theoret. Computer Science (ITCS), volume 215, pages 41:1–41:13, 2022.
  * [19] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn.  EFX exists for three agents.  In Proc. 21st Conf. Economics and Computation (EC), pages 1–19. ACM, 2020.
  * [20] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa.  A little charity guarantees almost envy-freeness.  SIAM J. Comput., 50(4):1336–1358, 2021.
  * [21] Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay V. Vazirani.  Market equilibrium via a primal–dual algorithm for a convex program.  J. ACM, 55(5), 2008.
  * [22] Soroush Ebadian, Dominik Peters, and Nisarg Shah.  How to fairly allocate easy and difficult chores.  In Proc. 21st Conf. Auton. Agents and Multi-Agent Systems (AAMAS), pages 372–380, 2022.
  * [23] Edmund Eisenberg and David Gale.  Consensus of subjective probabilities: The Pari-Mutuel method.  Ann. Math. Stat., 30(1):165–168, 1959.
  * [24] Uriel Feige and Alexey Norkin.  Improved maximin fair allocation of indivisible items to three agents.  CoRR, abs/2205.05363, 2022.
  * [25] Irving Fisher.  Mathematical Investigations in the Theory of Value and Prices.  PhD thesis, Yale University, 1891.
  * [26] Jugal Garg, Martin Hoefer, Peter McGlaughlin, and Marco Schmalhofer.  When dividing mixed manna is easier than dividing goods: Competitive equilibria with a constant number of chores.  In Proc. 14th Symp. Algorithmic Game Theory (SAGT), pages 329–344, 2021.
  * [27] Jugal Garg and Peter McGlaughlin.  Computing competitive equilibria with mixed manna.  In Proc. 19th Conf. Auton. Agents and Multi-Agent Systems (AAMAS), pages 420–428, 2020.
  * [28] Jugal Garg and Aniket Murhekar.  On fair and efficient allocations of indivisible goods.  In Proc. 35th Conf. Artif. Intell. (AAAI), 2021.
  * [29] Jugal Garg, Aniket Murhekar, and John Qin.  Fair and efficient allocations of chores under bivalued preferences.  In Proc. 36th Conf. Artif. Intell. (AAAI), 2022.
  * [30] Jugal Garg, Aniket Murhekar, and John Qin.  Improving fairness and efficiency guarantees for allocating indivisible chores.  CoRR, abs/2212.02440, 2022.
  * [31] Bo Li, Yingkai Li, and Xiaowei Wu.  Almost (weighted) proportional allocations for indivisible chores.  In Proceedings of the ACM Web Conference, page 122–131, 2022.
  * [32] Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In Proc. 5th Conf. Economics and Computation (EC), pages 125–131, 2004.
  * [33] Ryoga Mahara.  Extension of additive valuations to general valuations on the existence of EFX.  In Proc. 29th European Symp. Algorithms (ESA), pages 66:1–66:15, 2021.
  * [34] Andreu Mas-Colell, Michael Whinston, and Jerry Green.  Microeconomic Theory.  Oxford University Press, 1995.
  * [35] James Orlin.  Improved algorithms for computing Fisher’s market clearing prices.  In Proc. 42nd Symp. Theory of Computing (STOC), pages 291–300, 2010.
  * [36] Lang Yin and Ruta Mehta.  On the envy-free allocation of chores.  CoRR, abs/2211.15836, 2022.
  * [37] Shengwei Zhou and Xiaowei Wu.  Approximately EFX allocations for indivisible chores.  In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 783–789. ijcai.org, 2022.

##  Appendix A Non-Degenerate Instances

We call an instance $I=\langle[n],M,\mathcal{D}\rangle$ non-degenerate if and
only if no agent dislikes two different sets equally, i.e., $\forall i\in[n]$
we have $S\neq_{i}T$ for all $S\neq T$. We adapt the technique in [19] and
show that it suffices to deal with non-degenerate instances when there are $n$
agents with additive disutilities, i.e., if there exists a tEFX allocation in
all non-degenerate instances, then there exists a tEFX allocation in all
instances.

Let $M=\left\\{c_{1},c_{2},\dots,c_{m}\right\\}$. We perturb any instance
$\mathcal{I}=\langle[n],M,\mathcal{D}\rangle$ to
$\mathcal{I}(\epsilon)=\langle[n],M,\mathcal{D}(\epsilon)\rangle$, where for
every $d_{i}\in\mathcal{D}$ we define
$d^{\prime}_{i}\in\mathcal{D}(\epsilon)$, as

$d^{\prime}_{i}(c)=d_{i}(c_{j})+\epsilon\cdot 2^{j}\quad\quad\forall
S\subseteq M$

######  Lemma 6.

Let

$\delta=\min_{i\in[n]}\min_{S,T\colon d_{i}(S)\neq
d_{i}(T)}|d_{i}(S)-d_{i}(T)|$

and let $\epsilon>0$ be such that $\epsilon\cdot 2^{m+1}<\delta$. Then

  1. 1.

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

  2. 2.

$\mathcal{I}(\epsilon)$ is a non-degenerate instance. Furthermore, if
$X=\langle X_{1},\ldots,X_{n}\rangle$ is a tEFX allocation for
$\mathcal{I}(\epsilon)$ then $X$ is also a tEFX allocation for $\mathcal{I}$.

###### Proof.

For the first statement of the lemma, observe that

$\displaystyle d^{\prime}_{i}(S)-d^{\prime}_{i}(T)$
$\displaystyle=d_{i}(S)-d_{i}(T)+\epsilon(\sum_{c_{j}\in S\setminus
T}2^{j}-\sum_{c_{j}\in T\setminus S}2^{j})$
$\displaystyle\geq\delta-\epsilon\sum_{c_{j}\in T\setminus S}2^{j}$
$\displaystyle\geq\delta-\epsilon\cdot(2^{m+1}-1)$ $\displaystyle>0\enspace.$

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

For the final claim, let us assume that $X$ is a tEFX allocation in
$\mathcal{I}(\epsilon)$ and not a tEFX allocation in $\mathcal{I}$. Then there
exist $i,j$, and $c\in X_{i}$ such that $d_{i}(X_{i}\setminus
c)>d_{i}(X_{j}\cup c)$. In that case, we have $d^{\prime}_{i}(X_{i}\setminus
c)>d^{\prime}_{i}(X_{j}\cup c)$ by the first statement of the lemma, implying
that $X$ is not a tEFX allocation in $\mathcal{I}(\epsilon)$ either, which is
a contradiction. ∎