# Weighted EF1 and PO Allocations with
Few Types of Agents or Chores††thanks: Work supported by NSF Grants
CCF-1942321 and CCF-2334461.

Jugal Garg111University of Illinois at Urbana-Champaign, USA
<EMAIL_ADDRESS>Aniket Murhekar222University of Illinois at Urbana-
Champaign, USA
<EMAIL_ADDRESS>John Qin333University of Illinois at Urbana-Champaign,
USA
<EMAIL_ADDRESS>
###### Abstract

We investigate the existence of fair and efficient allocations of indivisible
chores to asymmetric agents who have unequal entitlements or weights. We
consider the fairness notion of weighted envy-freeness up to one chore (wEF1)
and the efficiency notion of Pareto-optimality (PO). The existence of EF1 and
PO allocations of chores to symmetric agents is a major open problem in
discrete fair division, and positive results are known only for certain
structured instances. In this paper, we study this problem for a more general
setting of asymmetric agents and show that an allocation that is wEF1 and PO
exists and can be computed in polynomial time for instances with:

  * •

Three types of agents, where agents with the same type have identical
preferences but can have different weights.

  * •

Two types of chores, where the chores can be partitioned into two sets, each
containing copies of the same chore.

For symmetric agents, our results establish that EF1 and PO allocations exist
for three types of agents and also generalize known results for three agents
[14], two types of agents [14], and two types of chores [4]. Our algorithms
use a weighted picking sequence algorithm as a subroutine; we expect this idea
and our analysis to be of independent interest.

##  1 Introduction

Fair division is a ubiquitous problem in many disciplines, such as computer
science, economics, social choice, and multi-agent systems. While the formal
study began with the cake-cutting problem proposed by Steinhaus [17], which
concerned the fair division of a divisible good, the fair division of
indivisible items has received considerable attention in recent times (see
excellent surveys [3, 1]). Although fairness of an allocation is inherently
subjective, envy-freeness (EF) is a quintessential and well-established notion
of fairness [11]. Envy-freeness requires that every agent (weakly-)prefers the
items allocated to her to those allocated to others. Unfortunately, EF
allocations need not exist when items are indivisible, as can be seen from the
simple example of assigning one task to two agents. Hence, relaxations of EF
have been defined to qualify fairness in the discrete case, with envy-free up
one item (EF1) being one such popular relaxation. When agent preferences are
monotone, EF1 allocations always exist and can be computed in polynomial time
[15, 6].

Instance | EF1 + fPO | wEF1 + fPO
---|---|---
General Additive | ? | ?
Two agents | ✓[2] | ✓[18]
Three agents | ✓[14] | ✓Theorem 1
Two-agent-types | ✓[14] | ✓Theorem 1
Three-agent-types | ✓Theorem 1 | ✓Theorem 1
Two-chore-types | ✓[4] | ✓Theorem 2
Bivalued | ✓[13, 9] | ✓[18]
Table 1: State-of-the-art for EF1/wEF1+fPO allocation of indivisible chores. ✓
denotes existence/polynomial-time algorithm, ? denotes (non-)existence is
unknown. Colored cells highlight our results.

A fair allocation can be quite sub-optimal in terms of overall efficiency: a
set of tasks could be allocated so that every agent is assigned tasks they are
bad at; as a result, agents may not envy each other by much, but the
allocation is inefficient. It is, therefore, natural to seek allocations that
are both fair as well as efficient. The classic notion of economic efficiency
is Pareto-optimality (PO): an allocation is PO if there is no re-allocation
such that every agent weakly prefers the re-allocation while some agents
strictly prefer it. Allocations that are simultaneously EF1 and PO are thus
highly desirable, and many works have investigated the existence and fast
computation of such allocations in various settings, e.g., [7, 5, 12, 9, 13,
14, 2, 4]. A common assumption in these works, including ours, is that agent
preferences are additive, i.e., the value to an agent from a set of items is
the sum of the values of items in the set. Under additive preferences, merely
checking if an allocation is PO is a co-NP-hard problem. This adds to the
challenge of investigating the existence and computation of EF1 and PO
allocations.

Further, the difficulty of the problem is significantly influenced by the
nature of the items, as is the definition of EF1. When items are goods and
provide value to the agents receiving them, in an EF1 allocation, every agent
prefers her bundle to that of another after the removal of one good from the
other agent’s bundle. For goods, an EF1 and PO allocation is known to exist
and can be computed in pseudo-polynomial time. In a pivotal paper, [7] proved
that an allocation with the highest Nash welfare — product of the agents’
utilities — is both EF1 and PO. This approach does not lead to fast
computation since computing an allocation with maximum Nash welfare is APX-
hard. Remarkably, [5] designed a pseudo-polynomial time algorithm for this
problem using the idea of a competitive equilibrium. In this approach, agents
are endowed with a fictitious amount of money, the goods are assigned prices,
and each agent is allocated goods that give them ‘maximum value-for-money’.
The latter ensures that the allocation is fractionally PO (fPO), an efficiency
property stronger than PO. While the allocation is not EF1, they transfer
goods between agents to reduce envy and make appropriate price changes to
maintain PO. Using involved potential function arguments, they prove their
algorithm terminates with an EF1 and PO allocation. Later, [12] showed an EF1
and fPO allocation can be computed in pseudo-polynomial time and in polynomial
time when agents have a constant number of different values for the goods.
Despite these results, designing a polynomial time algorithm remains an open
problem.

On the other hand, when items are chores and impose a cost on agents receiving
them, in an EF1 allocation every agent prefers her bundle to that of another
after the removal of one chore from her bundle. For chores, even the existence
of an EF1 and PO allocation is unclear, let alone computation. At first sight,
it may seem that the case of goods and chores are similar, and techniques from
the goods setting should be directly adaptable to chores. However, this does
not seem to be the case. Firstly, a welfare function like Nash welfare
guaranteeing EF1 is not known for chores. Secondly, while the competitive
equilibrium approach is promising since it guarantees PO, showing that
algorithms using this approach terminate has proved to be challenging. As a
result, the existence and computation of an EF1 and PO allocation of chores
remains a challenging open problem in discrete fair division. To understand
the ‘source of hardness’ of this problem, a series of works have focused on
identifying structured instances where the problem becomes tractable, i.e.,
where EF1 and PO allocations exist. These classes include instances with (i)
identical agents (folklore), (ii) two agents [2], (iii) bivalued disutilities
[13, 9], (iv) three agents [14], (v) two types of agents [14], and (vi) two
types of chores [4]. While the computation of EF1 and PO allocations is fairly
straightforward for (i) and (ii) using ideas for goods, that for classes (iii)
- (vi) is non-trivial. These results follow from carefully designed
algorithms, all of which use the competitive equilibrium framework but require
involved potential function arguments to prove termination. Table 1 lists
these results.

All of the above works assume that agents have equal entitlements, capacities,
or stakes. This is a limiting assumption, as practical scenarios may involve
agents with different capacities for handling workload. For example, Alice, a
teaching faculty at a university, may agree to teach twice as many courses as
Bob, a research faculty. Thus, Alice will only envy Bob if she feels the
workload from the courses assigned to her is more than twice that of Bob.
Likewise, the dissolution of a partnership poses the problem of fairly
dividing liabilities; in this context, it is only natural that they be divided
according to the entitlements/shares of the partners. These scenarios motivate
the definition of weighted envy-freeness (wEF) and its relaxation weighted
envy-freeness up to one item (wEF1) in the discrete case. Naturally, like the
unweighted case, one seeks fair and efficient allocations, which leads us to
the existence and computation of a wEF1 and PO allocation of chores. This
question is interesting not only because it generalizes an important open
problem in discrete fair division but also because it naturally models
practical chore division scenarios.

For goods, [8] showed that a wEF1 (without PO) allocation can be computed via
a weighted picking sequence algorithm. This algorithm proceeds in $m$ rounds
until all $m$ goods are allocated. In each round, a particular agent is chosen
who picks her favorite good among the remaining goods. For chores, the
existence of wEF1 allocations was only recently shown [18] via a modification
of the weighted picking sequence algorithm, and develops a novel analysis
technique. [8] showed that wEF1 and PO allocation exists and can be computed
in pseudo-polynomial time for goods by adapting the algorithm of [5] to the
weighted case. For chores, [18] also showed that wEF1 and PO allocation can be
computed for two agents and for bivalued chores (classes (ii), (iii) above).
The existence of wEF1 and PO allocations for chores remained an open problem,
including for the subclasses (iv)-(vi).

###  1.1 Our Contributions

In this work, we study the existence and computation of wEF1 and PO
allocations of chores to agents with unequal entitlements. We prove that a
wEF1 and fPO allocation exists and can be computed in polynomial time for
instances with

  * •

Three types of agents (Theorem 1). In a three-agent-type instance, the
disutility function of an agent is one of three given functions.

  * •

Two types of chores (Theorem 2). In a two-chore-type instance, the chores can
be partitioned into two sets, each containing copies of the same chore.

#### Significance.

Theorem 1 establishes another class for which EF1 and PO allocations exist,
namely three-agent-type instances. Theorem 1 also subsumes previous works
showing the existence of EF1 and PO allocations for (i) two agents [2], (ii)
three agents [14], and (iii) two-agent-types [14]. We note that improving the
existence from three agents to three types of agents in the symmetric setting
is itself significant, e.g., for another popular fairness notion of _maximin
share (MMS)_ , MMS allocations exist for two agents but not for two types of
agents [10]. Theorem 2 subsumes previous work showing EF1 and PO allocations
exist for two-chore-type instances [4], and also provides an alternative
algorithm for the symmetric case. Moreover, our ideas can also be applied to
the goods setting to show that wEF1 and PO allocations can be computed in
polynomial time for these classes. We record our results in Table 1.

Our results can also be of practical significance in certain settings. For
instance, a cluster may have machines with three types of processing power,
e.g., CPUs, GPUs, and TPUs (three types of agents). Likewise, allocation
problems may involve jobs that are either heavy or light (two types of
chores).

#### Techniques.

We first remark that simply replacing an agent with as many copies of the
agent as their weight, computing an EF1 and PO allocation, and combining the
allocation of all the copies does not guarantee a wEF1 and PO allocation; see
Appendix A for an example. Our algorithms use the competitive equilibrium
framework to ensure fPO (hence PO). To obtain wEF1, chores are transferred
from one set of agents to another while performing appropriate changes to the
chore payments444Chores have attached payments while goods have prices. to
maintain a competitive allocation. However, these transfers and payment
changes are carefully and selectively performed so that we can guarantee the
termination of our algorithms.

We first design Algorithm 2 to compute a wEF1 and fPO allocation for three-
agent-type instances using a novel combination of weighted picking sequence
and competitive equilibrium framework. We group agents according to their type
and allocate chores to agents in a group using a ‘weighted picking sequence’
algorithm. We begin by allocating all chores to one group and transferring
chores away from this group while ensuring that agents in the other two groups
do not wEF1-envy each other. For fPO, we carefully maintain the allocation at
a competitive equilibrium throughout the algorithm.

We next design Algorithm 3 to compute a wEF1 and fPO allocation for two-chore-
type instances. We first observe that fPO allocations in two-chore-type
instances follow a certain ‘ordered’ structure [4]. Leveraging this idea, we
initially allocate all chores to one agent called the pivot and repeatedly
transfer a chore away from the pivot. These transfers respect the ordered
structure ensuring fPO and are performed until we eventually obtain a wEF1
allocation, or conclude that the initial choice of the pivot is incorrect. We
argue that there exists some choice of the pivot for which the algorithm
results in a wEF1 and fPO allocation.

The correctness and termination of our algorithms rely on several involved and
novel potential function arguments. In particular, both our results crucially
utilize properties of a weighted picking sequence algorithm for chores (stated
and proved in Lemmas 3, 4, 14). We believe this may be of independent
interest, and may find use in algorithm design for fair division to asymmetric
agents in the future.

##  2 Preliminaries

An instance $(N,W,M,D)$ of the fair division problem with chores consists of a
set $N=[n]$ of $n$ agents, a list $W=\\{w_{i}\\}_{i\in N}$ with $w_{i}>0$
denoting the weight of agent $i$, a set $M=[m]$ of $m$ indivisible chores, and
a list $D=\\{d_{i}\\}_{i\in N}$, where $d_{i}:2^{M}\rightarrow\mathbb{R}_{\geq
0}$ is agent $i$’s disutility function over the chores. We let $d_{i}(j)$
denote the disutility of chore $j$ for agent $i$. We assume disutility
functions are additive, so that for every $i\in N$ and $S\subseteq M$,
$d_{i}(S)=\sum_{j\in S}d_{i}(j)$. We consider the following structured
classes. An instance $(N,W,M,D)$ is said to be a:

  * •

$k$-agent-type instance if there are $k$ types of agents. That is, there is a
set $C=\\{c_{1},\dots,c_{k}\\}$ of $k\in\mathbb{N}$ disutility functions s.t.
for all $i\in N$, $d_{i}\in C$.

  * •

$k$-chore-type instance if there are $k$ types of chores. That is, the set of
chores can be partitioned as $M=\bigcup_{\ell\in[k]}M_{\ell}$, where each set
$M_{\ell}$ consists of copies of the same chore.

An integral allocation
$\mathbf{x}=(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n})$ is a
partition of the chores into $n$ bundles, where agent $i$ receives bundle
$\mathbf{x}_{i}\subseteq M$ and gets disutility $d_{i}(\mathbf{x}_{i})$. In a
fractional allocation $\mathbf{x}\in[0,1]^{n\times m}$, chores are divisible
and $x_{ij}\in[0,1]$ denotes the fraction of chore $j$ given to agent $i$.
Here $d_{i}(\mathbf{x}_{i})=\sum_{j\in M}d_{i}(j)\cdot x_{ij}$. We will assume
that allocations are integral unless explicitly stated otherwise.

#### Fairness and efficiency notions.

An allocation $\mathbf{x}$ satisfies:

  1. 1.

Envy-free up to one chore (EF1) for symmetric agents if for all $i,h\in N$,
$d_{i}(\mathbf{x}_{i}\setminus j)\leq d_{i}(\mathbf{x}_{h})$ for some
$j\in\mathbf{x}_{i}$.

  2. 2.

Weighted envy-free up to one chore (wEF1) if for all $i,h\in N$,
$\frac{d_{i}(\mathbf{x}_{i}\setminus
j)}{w_{i}}\leq\frac{d_{i}(\mathbf{x}_{h})}{w_{h}}$ for some
$j\in\mathbf{x}_{i}$.

  3. 3.

Pareto-optimal if there is no allocation $\mathbf{y}$ that dominates
$\mathbf{x}$. An allocation $\mathbf{y}$ dominates an allocation $\mathbf{x}$
if for all $i\in N$, $d_{i}(\mathbf{y}_{i})\leq d_{i}(\mathbf{x}_{i})$, and
there exists $h\in N$ such that $d_{h}(\mathbf{y}_{h})<d_{h}(\mathbf{x}_{h})$.

  4. 4.

Fractionally Pareto-optimal if there is no fractional allocation that
dominates $\mathbf{x}$. An fPO allocation is clearly PO, but not vice-versa.

#### Competitive equilibrium of chores.

In the Fisher market model for chores, we associate payments
$\mathbf{p}=(p_{1},\ldots,p_{m})$ with the chores. Each agent $i$ aims to earn
a desired minimum payment of $e_{i}\geq 0$ by performing chores in exchange
for payment. In a (fractional) allocation $\mathbf{x}$ with payments
$\mathbf{p}$, the earning of agent $i$ is
$\mathbf{p}(\mathbf{x}_{i})=\sum_{j\in M}p_{j}\cdot x_{ij}$. For each agent
$i$, we define the pain-per-buck ratio $\alpha_{ij}$ of chore $j$ as
$\alpha_{ij}=d_{i}(j)/p_{j}$ and the minimum-pain-per-buck (MPB) ratio as
$\alpha_{i}=\min_{j\in M}\alpha_{ij}$. Further, we let
$\mathsf{MPB}_{i}=\\{j\in M\mid d_{i}(j)/p_{j}=\alpha_{i}\\}$ denote the set
of chores which are MPB for agent $i$ under payments $\mathbf{p}$.

We say that $(\mathbf{x},\mathbf{p})$ is a competitive equilibrium (CE) if (i)
for all $j\in M$, $\sum_{i\in N}x_{ij}=1$, i.e., all chores are completely
allocated, (ii) for all $i\in N$, $\mathbf{p}(\mathbf{x}_{i})=e_{i}$, i.e.,
each agent receives her minimum payment, and (iii) for all $i\in N$,
$\mathbf{x}_{i}\subseteq\mathsf{MPB}_{i}$, i.e., agents receive only chores
which are MPB for them. The First Welfare Theorem [16] shows that competitive
equilibria are efficient, i.e., for a CE $(\mathbf{x},\mathbf{p})$, the
allocation $\mathbf{x}$ is fPO.

For a CE $(\mathbf{x},\mathbf{p})$ where $\mathbf{x}$ is integral, we let
$\mathbf{p}_{-1}(\mathbf{x}_{i}):=\min_{j\in\mathbf{x}_{i}}\mathbf{p}(\mathbf{x}_{i}\setminus
j)$ denote the payment agent $i$ receives from $\mathbf{x}_{i}$ excluding her
highest paying chore.

######  Definition 1.

(Weighted payment EF1) An allocation $(\mathbf{x},\mathbf{p})$ is said to be
weighted payment envy-free up to one chore (wpEF1) if for all $i,h\in N$ we
have
$\frac{\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}\leq\frac{\mathbf{p}(\mathbf{x}_{h})}{w_{h}}$.
Agent $i$ wpEF1-envies $h$ if
$\frac{\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}>\frac{\mathbf{p}(\mathbf{x}_{h})}{w_{h}}$.

The following lemma shows a sufficient condition for computing a wEF1 and PO
allocation.

######  Lemma 1.

Let $(\mathbf{x},\mathbf{p})$ be a CE with $\mathbf{x}$ integral. If
$(\mathbf{x},\mathbf{p})$ is wpEF1, then $\mathbf{x}$ is wEF1 and fPO.

###### Proof.

Let $\alpha_{i}$ be the MPB ratio of agent $i$ in $(\mathbf{x},\mathbf{p})$.
Consider any pair of agents $i,h\in N$. We have:

$\min_{j\in\mathbf{x}_{i}}\frac{d_{i}(\mathbf{x}_{i}\setminus
j)}{w_{i}}=\frac{\alpha_{i}\cdot\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}\leq\frac{\alpha_{i}\cdot\mathbf{p}(\mathbf{x}_{h})}{w_{h}}\leq\frac{d_{i}(\mathbf{x}_{h})}{w_{h}},$

where the first and last transitions use that $(\mathbf{x},\mathbf{p})$ is on
MPB, and the middle inequality uses the Definition 1. This shows that
$\mathbf{x}$ is wEF1. Moreover, the First Welfare Theorem [16] implies that
the allocation $\mathbf{x}$ is fPO since $(\mathbf{x},\mathbf{p})$ is a CE. ∎

An agent $\ell$ is called a weighted least earner (wLE) among agent set $A$ if
$\ell\in\mathsf{argmin}_{i\in A}\frac{\mathbf{p}(\mathbf{x}_{i})}{w_{i}}$. An
agent $b$ is called a weighted big earner (wBE) among agent set $A$ if
$b\in\mathsf{argmax}_{i\in A}\frac{\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}$.
The next lemma shows the importance of the wBE and wLE agents.

######  Lemma 2.

An integral CE $(\mathbf{x},\mathbf{p})$ is wpEF1 if and only if a wBE $b$
does not wpEF1-envy a wLE $\ell$.

###### Proof.

$(\Rightarrow)$ If $(\mathbf{x},\mathbf{p})$ is wpEF1 then clearly $b$ does
not wpEF1-envy $\ell$.

$(\Leftarrow)$ Suppose $b$ does not wpEF1-envy $\ell$. Then the following
shows that no agent $i$ wpEF1-envies any agent $h$, implying that
$(\mathbf{x},\mathbf{p})$ must be wpEF1.

$\frac{\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}\leq\frac{\mathbf{p}_{-1}(\mathbf{x}_{b})}{w_{b}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}(\mathbf{x}_{h})}{w_{h}},$

where the first and last inequalities use the definitions of wBE and wLE, and
the middle inequality uses that $b$ does not wpEF1-envy $\ell$. ∎

##  3 wEF1 and fPO Allocations in Three-Agent-Types Instances

We now study the existence and computation of wEF1 and fPO allocations in
instance with three agent types. We devise a polynomial time algorithm,
Algorithm 2, and show that it computes a wEF1 and fPO allocation for such
instances. We therefore have the following theorem.

######  Theorem 1.

In any three-agent-types instance, a wEF1 and fPO allocation exists, and can
be computed in polynomial time.

We remark that our result generalizes the following previously known results
regarding the polynomial time computability of allocations that are: (i)
EF1+fPO for three unweighted agents [14], (ii) EF1+fPO for two types of
unweighted agents [14], (iii) wEF1+fPO for two agents [18].

Let $N=N_{1}\sqcup N_{2}\sqcup N_{3}$ be a partition of the set of agents into
three sets, called agent groups, each containing agents of the same type. Let
$d_{i}(\cdot)$ be the disutility function of agents in group $N_{i}$, for
$i\in\\{1,2,3\\}$. Note that agents in the same group can have different
entitlements.

Algorithm 1 Weighted Picking Sequence ($\mathsf{WPS}$) Algorithm

Input: Agents $N$ with identical disutility function $d(\cdot)$, set of chores
$M$ s.t. $d_{1}\geq\dots\geq d_{m}$
Output: An wEF1 allocation $\mathbf{x}$

1:For each $i\in N$, $\mathbf{x}_{i}\leftarrow\emptyset$, $s_{i}\leftarrow 0$

2:for $j=1$ to $m$ do

3: $i\leftarrow\arg\min_{k\in N}\frac{s_{k}}{w_{k}}$; ties broken in favour of
smaller index agent

4: $\mathbf{x}_{i}\leftarrow\mathbf{x}_{i}\cup\\{j\\}$, $s_{i}\leftarrow
s_{i}+1$

5:return $\mathbf{x}$

###  3.1 Algorithm Description

Through the execution of Algorithm 2 we let $M_{i}$ denote the set of chores
allocated to group $N_{i}$. Initially, all chores are allocated to a single
group, $N_{1}$, i.e., $M_{1}=M$, and $M_{2}=M_{3}=\emptyset$. At each point,
the set of chores $M_{i}$ is allocated to the group $N_{i}$ by using the
weighted picking sequence (WPS) procedure, Algorithm 1, described below.

#### Weighted Picking Sequence (WPS) Algorithm.

The WPS algorithm (Algorithm 1) takes as input a set of agents $N$ of the same
type, i.e., with identical disutility function $d(\cdot)$, and a set of chores
$M$. The algorithm first sorts and re-labels the $m$ chores in non-increasing
order of disutility, i.e., $d_{1}\geq d_{2}\geq\dots\geq d_{m}$. The algorithm
then performs $m$ iterations, allocating one chore in each iteration. In
iteration $j$, chore $j$ is allocated to an agent with the least value of
$\frac{s_{i}}{w_{i}}$, where $s_{i}$ denotes the number of chores allocated to
agent $i$ so far. It is known that the WPS procedure returns a wEF1 allocation
for identical agents [8, 18]. Recently, [18] showed that by allocating the
chores in reverse order with each agent picking their least disutility chore
in their turn results in a wEF1 allocation, even for non-identical agents.
Since our algorithm uses the WPS algorithm to assign chores to agents of the
same type, we do not require this generalization. Using the WPS algorithm to
allocate chores $M_{i}$ to group $N_{i}$ ensures that agents within a group do
not ever wEF1-envy each other, and any wEF1-envy is between agents belonging
to different groups. To reduce wEF1-envy across groups, we transfer chores
from one group to another. After each chore transfer the set of chores $M_{i}$
gets updated and is re-allocated to the group $N_{i}$ by using the WPS
algorithm. We denote by
$\mathsf{WPS}(N_{1},M_{1})\cup\mathsf{WPS}(N_{2},M_{2})\cup\mathsf{WPS}(N_{3},M_{3})$
the allocation resulting from allocating $M_{i}$ to $N_{i}$ using WPS for each
$i\in[3]$.

#### Chore transfers and Payment drops: High-level Ideas.

To ensure that the resulting allocation is fPO, we attach payments to the
chores and maintain that all allocations in the run of Algorithm 2 are on MPB,
i.e., are competitive. Algorithm 2 performs two kinds of steps: (i) chore
transfers and (ii) payment drops. Chore transfers involve the transfer of a
chore from one group to another, and payment drops involve decreasing the
payments of all chores belonging to one or two agent groups.

Initially we set the payment of chore $j$ as $p_{j}=d_{1}(j)$. At some point
in the algorithm let the weighted big earner group $N_{\beta}$ be the group
containing the weighted big earner (wBE) at the time. Likewise, let the
weighted least earner group $N_{\lambda}$ be the group containing the weighted
least earner (wLE) at the time. We will call the group $N_{\mu}$ which
contains neither as the weighted middle earner (wME) group. If $\beta=\lambda$
then the allocation must already be wpEF1 by Lemma 2. Initially
$N_{\beta}=N_{1}$. We maintain that for the majority of the algorithm
$N_{\beta}=N_{1}$, i.e., the wBE is in $N_{1}$, and transfer chores
unilaterally from $N_{1}$ to $N_{2}$ and $N_{3}$. We also aim to maintain that
agents in $N_{2}$ and $N_{3}$ do not wpEF1-envy each other, and perform chore
transfers between $N_{2}$ and $N_{3}$ to eliminate any arising wpEF1-envy.

Algorithm 2 wEF1+fPO for three-agent-types instances

Input: Three-agent-types instance $(N,W,M,D)$
Output: A wEF1 and fPO integral allocation $\mathbf{x}$

1:Let $N=N_{1}\sqcup N_{2}\sqcup N_{3}$ be the partition of the agents
according to their type

2:Let $d_{i}(\cdot)$ denote the disutility function of agents in group
$N_{i}$, for $i\in\\{1,2,3\\}$

3:$M_{1}\leftarrow M,M_{2}\leftarrow\emptyset,M_{3}\leftarrow\emptyset$

4:$\mathbf{x}\leftarrow\mathsf{WPS}(N_{1},M_{1})\cup\mathsf{WPS}(N_{2},M_{2})\cup\mathsf{WPS}(N_{3},M_{3})$

5:For each $j\in M$, set $p_{j}\leftarrow d_{1}(j)$

6:while $\mathbf{x}$ is not wpEF1 do

7: $b\leftarrow\mathsf{argmax}_{k\in N}\mathbf{p}_{-1}(\mathbf{x}_{k})/w_{k}$
$\triangleright$ Weighted big earner

8: $\ell\leftarrow\mathsf{argmin}_{k\in
N}\mathbf{p}(\mathbf{x}_{k})/w_{k}$$\triangleright$ Weighted least earner

9: $\beta\leftarrow i\in[3]$ s.t. $b\in N_{i}$, $\triangleright$ Index of wBE
group

10: $\lambda\leftarrow i\in[3]$ s.t. $\ell\in N_{i}$ $\triangleright$ Index of
wLE group

11: $\mu\leftarrow i\in[3]\setminus\\{\beta,\lambda\\}$ $\triangleright$ Index
of wME group

12: $\triangleright$ Check for $N_{\beta}$ to $N_{\lambda}$ chore transfer

13: if $\exists j\in M_{\beta}\cap\mathsf{MPB}_{\lambda}$ then

14: $M_{\beta}\leftarrow M_{\beta}\setminus j$, $M_{\lambda}\leftarrow
M_{\lambda}\cup j$

15: $\mathbf{x}\leftarrow\bigcup_{i\in[3]}\mathsf{WPS}(N_{i},M_{i})$

16: $\triangleright$ Check for potential $N_{\mu}$ to $N_{\lambda}$ chore
transfer

17: else if $|M_{\mu}\cap\mathsf{MPB}_{\lambda}|>0$ then

18: $\triangleright$ Check if $N_{\mu}$ to $N_{\lambda}$ chore transfer is
allowed

19: if $\exists j\in M_{\mu}\cap\mathsf{MPB}_{\lambda}$ s.t.
$\min\limits_{k\in
N_{\mu}}\frac{\mathbf{p}(\mathbf{y}_{k})}{w_{k}}>\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}$
for $\mathbf{y}=\mathsf{WPS}(N_{\mu},M_{\mu}\setminus j)$ then

20: $M_{\mu}\leftarrow M_{\mu}\setminus j$, $M_{\lambda}\leftarrow
M_{\lambda}\cup j$

21: $\mathbf{x}\leftarrow\bigcup_{i\in[3]}\mathsf{WPS}(N_{i},M_{i})$

22: $\triangleright$ $N_{\beta}$ to $N_{\mu}$ chore transfer

23: else if $\exists j^{\prime}\in M_{\beta}\cap\mathsf{MPB}_{\mu}$ then

24: $M_{\beta}\leftarrow M_{\beta}\setminus j^{\prime}$, $M_{\mu}\leftarrow
M_{\mu}\cup j^{\prime}$

25: $\mathbf{x}\leftarrow\bigcup_{i\in[3]}\mathsf{WPS}(N_{i},M_{i})$

26: else$\triangleright$ No chore can be transferred from $N_{\beta}$

27: $\triangleright$ Lower payments of chores in $M_{\mu}\cup M_{\lambda}$

28: $\gamma\leftarrow\max_{i\in\\{\lambda,\mu\\},j\in
M_{\beta}}\frac{\alpha_{i}}{d_{i}(j)/p_{j}}$; $\alpha_{i}$ is the MPB ratio of
an agent in group $N_{i}$

29: for $j\in M_{\mu}\cup M_{\lambda}$ do

30: $p_{j}\leftarrow\gamma\cdot p_{j}$

31: else$\triangleright$ No chore can be transferred from $N_{\beta}$ or
$N_{\mu}$

32: $\triangleright$ Lower payments of chores in $M_{\lambda}$

33: $\gamma\leftarrow\max_{j\in M_{\beta}\cup
M_{\mu}}\frac{\alpha_{\ell}}{d_{\ell}(j)/p_{j}}$

34: for $j\in M_{\lambda}$ do

35: $p_{j}\leftarrow\gamma\cdot p_{j}$

36:return $\mathbf{x}$

Since $N_{1}$ only loses chores, in at most $m$ chore transfers from $N_{1}$
it must be that either the allocation becomes wpEF1 (hence wEF1), or the wBE
ceases to be in $N_{1}$. In the latter case we show that in one additional
chore transfer step the allocation is wEF1. To ensure fPO and facilitate chore
transfers, we perform payment drops of chores when appropriate, and maintain
the MPB condition during chore transfers. That is, a chore $j$ is transferred
from group $N_{i}$ to $N_{h}$ only if $j$ belongs to the MPB set
$\mathsf{MPB}_{h}$ of agents in $N_{h}$, i.e., $j\in
M_{i}\cap\mathsf{MPB}_{h}$.

#### Chore transfers and Payment drops: Details.

We perform payment drops and chore transfers across groups in a careful and
specific manner, as described below.

  * (Lines 12-14) Since we desire a wpEF1 allocation if possible we first check if there exists a chore $j\in M_{\beta}\cap\mathsf{MPB}_{\lambda}$ which can be transferred directly from the wBE group to the wLE group. If so we make this transfer.

  * (Lines 15-18) If no chore can be transferred from $N_{\beta}$ to $N_{\lambda}$, we check if a chore in $M_{\mu}\cap\mathsf{MPB}_{\lambda}$ can be potentially transferred from $N_{\mu}$ to $N_{\lambda}$. If there is a chore $j\in M_{\mu}\cap\mathsf{MPB}_{\lambda}$ s.t. after losing $j$ the least weighted earning of an agent in $N_{\mu}$ is strictly larger than the weighted earning of the current wLE, then we transfer $j$ from $N_{\mu}$ to $N_{\lambda}$ (Line 17-18). Line 16 performs this check. If not, an $N_{\mu}$ to $N_{\lambda}$ transfer is not allowed.

  * (Lines 19-21) If an $N_{\mu}$ to $N_{\lambda}$ transfer is not allowed, we check if an $N_{\beta}$ to $N_{\mu}$ transfer is possible, i.e., there is a chore $j^{\prime}\in M_{\beta}\cap\mathsf{MPB}_{\mu}$. If so, we make such a transfer.

  * (Lines 22-25) Otherwise, no chore can be transferred from $N_{\beta}$ to either $N_{\mu}$ or $N_{\lambda}$. In this case we lower the payments of chores in $M_{\mu}$ and $M_{\lambda}$ until a chore in $M_{\beta}$ becomes MPB for agents in $N_{\mu}$ or $N_{\lambda}$.

  * (Lines 26-29) Finally if there is no chore that can be transferred from $N_{\beta}$ or $N_{\mu}$ to $N_{\lambda}$, we lower the payments of chores in $M_{\lambda}$ until a chore in $M_{\beta}$ or $M_{\mu}$ becomes MPB for agents in $N_{\lambda}$.

###  3.2 Analysis of Algorithm 2: Overview

We begin the analysis of Algorithm 2 by proving some important properties of
the WPS algorithm (Alg. 1). The following lemmas compare the disutilities of
agents before and after a chore transfer.

######  Lemma 3.

Let $N$ be a set of agents with the same disutility function
$\mathbf{p}(\cdot)$ and $M$ be a set of chores. Let
$\mathbf{x}=\mathsf{WPS}(N,M)$ be an allocation of $M$ to $N$ using the WPS
algorithm, and $\mathbf{y}=\mathsf{WPS}(N,M\setminus j)$, for a chore $j\in
M$. Then we have:

  1. (i)

For all $i\in N$, $\mathbf{p}(\mathbf{y}_{i})\leq\mathbf{p}(\mathbf{x}_{i})$.

  2. (ii)

For all $i\in N$,
$\mathbf{p}_{-1}(\mathbf{y}_{i})\leq\mathbf{p}_{-1}(\mathbf{x}_{i})$.

  3. (iii)

For all $i,h\in N$,
$\frac{\mathbf{p}(\mathbf{y}_{i})}{w_{i}}\geq\frac{\mathbf{p}_{-1}(\mathbf{x}_{h})}{w_{h}}$.
In particular,
$\frac{\mathbf{p}(\mathbf{y}_{\ell})}{w_{\ell}}\geq\frac{\mathbf{p}_{-1}(\mathbf{x}_{b})}{w_{b}}$,
where agent $\ell$ has the least weighted disutility in $\mathbf{y}$ and agent
$b$ has the biggest weighted disutility up to one chore in $\mathbf{x}$.

######  Lemma 4.

Let $N$ be a set of agents with the same disutility function
$\mathbf{p}(\cdot)$ and $M$ be a set of chores. Let
$\mathbf{x}=\mathsf{WPS}(N,M)$ be an allocation of $M$ to $N$ using the WPS
algorithm, and $\mathbf{y}=\mathsf{WPS}(N,M\cup j)$, for a chore $j\notin M$.
Then we have:

  1. (i)

For all $i\in N$, $\mathbf{p}(\mathbf{y}_{i})\geq\mathbf{p}(\mathbf{x}_{i})$.

  2. (ii)

For all $i\in N$,
$\mathbf{p}_{-1}(\mathbf{y}_{i})\geq\mathbf{p}_{-1}(\mathbf{x}_{i})$.

  3. (iii)

For all $i,h\in N$,
$\frac{\mathbf{p}_{-1}(\mathbf{y}_{h})}{w_{h}}\leq\frac{\mathbf{p}(\mathbf{x}_{i})}{w_{i}}$.
In particular,
$\frac{\mathbf{p}_{-1}(\mathbf{y}_{b})}{w_{b}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}$,
where agent $b$ has the biggest weighted disutility up to one chore in
$\mathbf{y}$ and agent $\ell$ has the least weighted disutility in
$\mathbf{x}$.

When a set of chores $M$ with associated payments $\mathbf{p}$ is on MPB for
an group $N$ containing agents of the same type, the disutility of a chore is
proportional to its payment. Therefore, the claims in the above lemmas are
also true when $\mathbf{p}$ represents the payment vector (which is
proportional to the disutility vector) and $\mathbf{p}(\mathbf{x}_{i})$
represents the earning of agent $i$ in $(\mathbf{x},\mathbf{p})$ (which is
proportional to the disutility of $i$ in $\mathbf{x}$). We next show:

######  Lemma 5.

Throughout the execution of Algorithm 2, no chore transfer decreases the
weighted earning of the weighted least earner.

The following two lemmas analyze steps of Algorithm 2 which cause a group
$N_{\lambda}$ to cease being the weighted least earner group.

######  Lemma 6.

If a step of Algorithm 2 results in the weighted least earner group becoming
the weighted big earner group, then the resulting allocation must be wpEF1.

######  Lemma 7.

If a step of Algorithm 2 results in the weighted least earner group
$N_{\lambda}$ becoming the weighted middle earning group, then agents in
$N_{\lambda}$ do not wpEF1-envy agents in the new weighted least earner group
in the resulting allocation.

To summarize, if a group $N_{\lambda}$ ceases to be the weighted least earner
group, then either resulting allocation is wpEF1 or $N_{\lambda}$ becomes the
weighted middle earning group and agents in $N_{\lambda}$ do not wpEF1-envy
agents in the new weighted least earner group. These observations are
important for proving the lemmas that follow.

We next consider steps of Algorithm 2 which cause a group $N_{\beta}$ cease
being the weighted big earner group. We first show that:

######  Lemma 8.

If a step of Algorithm 2 results in the weighted big earner group becoming the
weighted least earner group, then the resulting allocation must be wpEF1.

Recall that we initially assigned all the chores to group $N_{1}$. Hence
$N_{\beta}=N_{1}$ was the initial weighted big earner group. We prove that
this is the case almost throughout the execution of the algorithm. To this
end, we show that $N_{\beta}$ (i.e. $N_{1}$) loses a chore in every
$\mathsf{poly}(m)$-many steps.

######  Lemma 9.

While the weighted big earner belongs to the group $N_{\beta}$ and the
allocation is not wpEF1, $N_{\beta}$ must lose a chore in $\mathsf{poly}(m)$
steps.

Note that $N_{1}$ has $m$ chores to begin with (i.e. always $|M_{1}|\leq m$),
and Algorithm 2 never transfers a chore to $N_{1}$. Lemma 9 therefore implies
that in $\mathsf{poly}(m)$ steps either the allocation is wpEF1 or $N_{1}$
ceases to be the weighted big earner group. In the latter scenario, we show
that we arrive at a wEF1 allocation in at most one more chore transfer step.

######  Lemma 10.

After $N_{1}$ stops being the weighted big earner group for the last time,
Algorithm 2 terminates with a wEF1 and fPO allocation after performing at most
one subsequent chore transfer.

The above discussion leads us to conclude that Algorithm 2 computes a wEF1 and
fPO allocation in polynomial time for three-agent-types instances. This proves
Theorem 1.

###  3.3 Analysis of Algorithm 2: Proofs

This section proves the lemmas stated in the previous section.

See 3

###### Proof.

We use the function $\sigma:[m]\rightarrow[n]$ to represent the $m$-length
picking sequence used by the WPS algorithm on an instance $(N,M,\mathbf{p})$.
Thus if $\sigma(c)=i$ for a chore $c$ and agent $i$, then in iteration $c$ of
the WPS algorithm (Alg. 1) agent $i\in\arg\min_{k}s_{k}/w_{k}$ and agent $i$
is assigned chore $c$. We now consider the allocation $\mathbf{y}$ produced by
the WPS algorithm on the instance $M\setminus j$ for some chore $j\in[m]$. For
conceptual convenience, we also add a dummy item $(m+1)$ with $p_{m+1}=0$.
This ensures that for all $i$, $|\mathbf{x}_{i}|=|\mathbf{y}_{i}|$. The
addition of the dummy item has no effect on either the values of disutility or
the disutility minus the worst chore for any agent. Moreover the dummy item
will necessarily be the last item to be allocated in the picking sequence
$\sigma^{\prime}:[m+1]\setminus\\{j\\}\rightarrow[n]$ generating $\mathbf{y}$.
They key observation is that since the WPS algorithm only depends on the
number of items $s_{i}$ allocated to an agent $i$, the sequence
$\sigma^{\prime}$ is the same as $\sigma$ up to item $(j-1)$, after which it
is ‘left-shifted’. That is, for $j^{\prime}\in[m+1]\setminus\\{j\\}$, we have:

$\sigma^{\prime}(j^{\prime})=\begin{cases}\sigma(j^{\prime}),\text{ if
}j^{\prime}<j,\\\ \sigma(j^{\prime}-1),\text{ if }j^{\prime}>j.\end{cases}$
(1)

For an agent $i$, let $\mathbf{x}_{i}=\\{a_{1},\dots,a_{k}\\}$ be the items in
$M=[m]$ assigned to $i$ in $\mathbf{x}$ in the order in which they are picked
by $i$. Thus, $p_{a_{1}}\geq p_{a_{2}}\geq\dots\geq p_{a_{k}}$. Let
$\mathbf{y}_{i}=\\{b_{1},\dots,b_{k}\\}$ be the items assigned to $i$ in
$\mathbf{y}$ in the order in which they are picked by $i$. Eq. 1 implies that
for $t\in[k]$:

$b_{t}=\begin{cases}a_{t},\text{ if }a_{t}<j\\\ a_{t}+1,\text{ if }a_{t}\geq
j\end{cases}$ (2)

Since $p_{a_{t}}\geq p_{a_{t}+1}$, Eq. 2 immediately implies that
$p_{b_{t}}\leq p_{a_{t}}$ for all $t\in[k]$. Thus we have:

$\mathbf{p}(\mathbf{y}_{i})=\sum_{t=1}^{k}p_{b_{t}}\leq\sum_{t=1}^{k}p_{a_{t}}=\mathbf{p}(\mathbf{x}_{i}),\text{
and
}\mathbf{p}_{-1}(\mathbf{y}_{i})=\sum_{t=2}^{k}p_{b_{t}}\leq\sum_{t=2}^{k}p_{a_{t}}=\mathbf{p}_{-1}(\mathbf{x}_{i}),$

which proves parts (i) and (ii).

To prove (iii), we use the continuous interpretation of the WPS algorithm
[18]. We imagine $s_{i}:[0,m]\rightarrow[0,m]$ as a non-decreasing function
that grows uniformly at a rate of $1/w_{i}$ during time $(j-1,j]$ if $i$ was
chosen in iteration $j$, and is unchanged during other time intervals. Define
a function $\varphi:(0,k/w_{i}]\rightarrow\mathbb{R}^{+}$ such that
$\varphi(\alpha)$ is the disutility of the item being picked by agent $i$ when
$s_{i}(t)=\alpha$ in allocation $\mathbf{x}$. In other words, for $z\in[k]$
and $\alpha\in\big{(}\frac{z-1}{w_{i}},\frac{z}{w_{i}}\big{]}$, define
$\varphi(\alpha)=p_{a_{z}}$. Similarly define
$\varphi^{\prime}:(0,k/w_{i}]\rightarrow\mathbb{R}^{+}$ such that
$\varphi^{\prime}(\alpha)$ is the disutility of the item being picked by agent
$i$ when $s_{i}(t)=\alpha$ in allocation $\mathbf{y}$. In other words, for
$z\in[k]$ and $\alpha\in\big{(}\frac{z-1}{w_{i}},\frac{z}{w_{i}}\big{]}$,
define $\varphi^{\prime}(\alpha)=p_{b_{z}}$. These definitions imply that:

$\frac{\mathbf{p}(\mathbf{y}_{i})}{w_{i}}=\int_{0}^{\frac{k}{w_{i}}}\varphi^{\prime}(\alpha)\>d\alpha.$
(3)

Consider another agent $h$ and let
$\mathbf{x}_{h}=\\{e_{1},\dots,e_{\ell}\\}$. As before, define
$\phi:(0,\ell/w_{h}]\rightarrow\mathbb{R}^{+}$ such that $\phi(\alpha)$ is the
disutility of the item being picked by agent $h$ when $s_{h}(t)=\alpha$ in
allocation $\mathbf{x}$. In other words, for $z\in[\ell]$ and
$\alpha\in\big{(}\frac{z-1}{w_{h}},\frac{z}{w_{h}}\big{]}$, define
$\phi(\alpha)=p_{e_{z}}$. This implies:

$\frac{\mathbf{p}_{-1}(\mathbf{x}_{h})}{w_{h}}=\int_{\frac{1}{w_{h}}}^{\frac{\ell}{w_{h}}}\phi(\alpha)\>d\alpha.$
(4)

We now prove the following claims.

######  Claim 1.

$\frac{\ell-1}{w_{h}}\leq\frac{k}{w_{i}}$.

###### Proof.

At the time $t$ when agent $h$ picks her last item $e_{\ell}$, it must be that
$s_{h}(t)\leq s_{i}(t)$, since $h$ was chosen at time $t$. The claim then
follows by noting $s_{h}(t)=(\ell-1)/w_{h}$, and $s_{i}(t)\leq
s_{i}(m)=k/w_{i}$ since $s_{i}$ is non-decreasing. ∎

######  Claim 2.

For all $\alpha\in\big{(}\frac{1}{w_{h}},\frac{\ell}{w_{h}}\big{]}$,
$\phi(\alpha)\leq\varphi^{\prime}(\alpha-\frac{1}{w_{h}})$.

###### Proof.

Let $z\in[\ell]$ be such that
$\alpha\in\big{(}\frac{z-1}{w_{h}},\frac{z}{w_{h}}\big{]}$. Then
$\phi(\alpha)=p_{e_{z}}$ by definition of $\phi$. Let $t_{2}$ be the time
instant s.t. $s_{h}(t_{2})=\alpha$ for the first time. Let $t^{*}$ be the
largest integer strictly smaller than $t_{2}$, i.e.,
$t_{2}\in(t^{*},t^{*}+1]$. In this interval $s_{h}(t)$ goes from
$\frac{z-1}{w_{h}}$ to $\frac{z}{w_{h}}$. Now let $t_{1}$ be the earliest time
when $s_{i}(t_{1})=\alpha-\frac{1}{w_{h}}$. Note that $t_{1}$ is well defined,
since $\alpha-\frac{1}{w_{h}}>0$, as
$\alpha\in(\frac{1}{w_{h}},\frac{\ell}{w_{h}}]$. Thus we have
$s_{i}(t_{1})=\alpha-\frac{1}{w_{h}}\leq\frac{z-1}{w_{h}}=s_{h}(t^{*})$. At
$t^{*}$, since agent $h$ is the agent chosen to pick an chore, hence it must
be that $s_{h}(t^{*})\leq s_{i}(t^{*})$. Therefore $s_{i}(t_{1})\leq
s_{i}(t^{*})$. Since $s_{i}(\cdot)$ is non-decreasing, we conclude $t_{1}\leq
t^{*}$. Since $t_{2}\in(t^{*},t^{*}+1]$, we have $t_{1}<t_{2}$.

At time $t_{1}$, let $a$ (resp. $b$ be the chore being consumed by agent $i$
in allocation $\mathbf{x}$ (resp. $\mathbf{y})$. From Eq. 2, we know that
either $b=a$ or $b=a+1$. Recall that $e_{z}$ is the chore being consumed by
agent $h$ at time $t_{2}$ in allocation $\mathbf{x}$. Since $t_{1}<t_{2}$, and
since chores are allocated in non-increasing order of disutility, it must be
that the disutility of $e_{z}$ does not exceed the disutility of chore
$(a+1)$, since $(a+1)$ is the chore with the highest disutility available
after chore $a$ gets consumed. Thus $p_{e_{z}}\leq p_{a+1}$ and hence
$p_{e_{z}}\leq p_{b}$. The claim then follows by noting that
$\phi(\alpha)=p_{e_{z}}$ and $p_{b}=\varphi^{\prime}(\alpha-\frac{1}{w_{h}})$.
The latter equality holds from the definition of $\varphi^{\prime}$, as $b$ is
the chore being consumed by $h$ at the time $t_{1}$ when
$s_{h}(t_{1})=\alpha-\frac{1}{w_{h}}$. ∎

Armed with Claims 1 and 2, we observe that:

$\displaystyle\frac{\mathbf{p}(\mathbf{y}_{i})}{w_{i}}$
$\displaystyle=\int_{0}^{\frac{k}{w_{i}}}\varphi^{\prime}(\alpha)\>d\alpha$
(Eq. 3)
$\displaystyle\geq\int_{0}^{\frac{\ell-1}{w_{h}}}\varphi^{\prime}(\alpha)\>d\alpha$
(1)
$\displaystyle=\int_{\frac{1}{w_{\ell}}}^{\frac{\ell}{w_{h}}}\varphi^{\prime}(\alpha+1/w_{h})\>d\alpha$
(change of variables)
$\displaystyle\geq\int_{\frac{1}{w_{\ell}}}^{\frac{\ell}{w_{h}}}\phi(\alpha)\>d\alpha$
(2) $\displaystyle=\frac{\mathbf{p}_{-1}(\mathbf{x}_{h})}{w_{h}},$ (Eq. 4)

thus proving part (iii) of the lemma. ∎

See 4

###### Proof.

Define $M^{\prime}=M\cup j$. Then $\mathbf{y}=\mathsf{WPS}(N,M^{\prime})$ and
$\mathbf{x}=\mathsf{WPS}(N,M^{\prime}\setminus j)$. Lemma 4 then directly
follows by invoking Lemma 3 on allocations $\mathbf{y}$ and $\mathbf{x}$ (with
labels $\mathbf{x}$ and $\mathbf{y}$ swapped). ∎

See 5

###### Proof.

Consider a transfer of a chore which strictly reduces the weighted earning of
the weighted least earner (wLE). Let $\mathbf{x}$ (resp. $\mathbf{y}$) be the
allocation before (resp. after) the transfer and $\mathbf{p}$ the payment
vector. Note that $(\mathbf{x},\mathbf{p})$ is not wpEF1, otherwise Algorithm
2 would have halted before the transfer.

######  Claim 3.

The new wLE in $(\mathbf{y},\mathbf{p})$ belongs to the group losing the
chore.

###### Proof.

By Lemma 3 (i), the new wLE cannot be in group receiving the chore. Moreover
the new wLE cannot be in the group which does not participate in the transfer,
since the earning of agents in that group is unchanged. Therefore the new wLE
must belong to the group losing the chore. ∎

Let $N_{\beta}$, $N_{\mu}$, and $N_{\lambda}$ be the wBE, wME, and wLE groups
in $(\mathbf{x},\mathbf{p})$. There are two possibilities:

  * •

Chore transfer from $N_{\beta}$ to $N_{\lambda}$ or $N_{\mu}$ . Let $\ell$ and
$b$ be the wLE and wBE in $(\mathbf{x},\mathbf{p})$ respectively, and
$\ell^{\prime}$ the new wLE in $(\mathbf{y},\mathbf{p})$. By definition we
have $\ell\in N_{\lambda}$, $b\in N_{\beta}$, and by 3, $\ell^{\prime}\in
N_{\beta}$. Observe that:

$\frac{\mathbf{p}(\mathbf{y}_{\ell^{\prime}})}{w_{\ell^{\prime}}}\geq\frac{\mathbf{p}_{-1}(\mathbf{x}_{b})}{w_{b}}>\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}},$

where the first inequality is due to Lemma 3 applied to $N_{\beta}$ and the
second inequality is because $(\mathbf{x},\mathbf{p})$ is not wpEF1.

  * •

Chore transfer from $N_{\mu}$ to $N_{\lambda}$. 3 implies the new wLE in the
allocation $(\mathbf{y},\mathbf{p})$ must be in $N_{\mu}$. By the design of
Algorithm 2 a chore transfer from $N_{\mu}$ to $N_{\lambda}$ is allowed only
if after the transfer the weighted earning of the wLE in $N_{\mu}$ is strictly
larger than the weighted earning of the current wLE (Line 16).

In either case the weighted earning of the wLE does not decrease due to the
chore transfer. ∎

See 6

###### Proof.

Clearly a payment drop step cannot cause the wLE group to change. Let us
therefore consider a chore transfer step which causes the wLE group
$N_{\lambda}$ in an allocation $(\mathbf{x},\mathbf{p})$ to become the wBE
group in the subsequent allocation $(\mathbf{y},\mathbf{p})$. If a chore is
not transferred to $N_{\lambda}$, the wLE in $(\mathbf{y},\mathbf{p})$ must
continue to lie in $N_{\lambda}$. Then $(\mathbf{y},\mathbf{p})$ must be wpEF1
since both the wBE and wLE lie in the same group in $(\mathbf{y},\mathbf{p})$.
Therefore suppose a chore is transferred to $N_{\lambda}$. Let $\ell$ be the
wLE in $(\mathbf{x},\mathbf{p})$. Let $\ell^{\prime}$ and $b^{\prime}$ be the
wLE and wBE in $(\mathbf{y},\mathbf{p})$ respectively. We know
$\ell,b^{\prime}\in N_{\lambda}$. Observe that:

$\frac{\mathbf{p}_{-1}(\mathbf{y}_{b^{\prime}})}{w_{b^{\prime}}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell^{\prime}})}{w_{\ell^{\prime}}},$

where the first inequality uses Lemma 4 applied to $N_{\lambda}$ and the
second inequality uses Lemma 5. The above equation implies that the wBE does
not wpEF1-envy the wLE in $(\mathbf{y},\mathbf{p})$, implying that
$(\mathbf{y},\mathbf{p})$ is wpEF1 by invoking Lemma 2. ∎

See 7

###### Proof.

Clearly a payment drop step cannot cause the wLE group to change. Let us
therefore consider a chore transfer step which causes the wLE group
$N_{\lambda}$ in an allocation $(\mathbf{x},\mathbf{p})$ to become the wME
group in the subsequent allocation $(\mathbf{y},\mathbf{p})$. If a chore is
not transferred to $N_{\lambda}$, the wLE in $(\mathbf{y},\mathbf{p})$ must
continue to lie in $N_{\lambda}$ and $N_{\lambda}$ cannot be the wME group in
$(\mathbf{y},\mathbf{p})$. Therefore suppose a chore is transferred to
$N_{\lambda}$. Let $\ell\in N_{\lambda}$ be the wLE in
$(\mathbf{x},\mathbf{p})$, $b^{\prime}$ be the wBE in $N_{\lambda}$ in
$(\mathbf{y},\mathbf{p})$, and $\ell^{\prime}$ the wLE in
$(\mathbf{y},\mathbf{p})$. Observe that:

$\frac{\mathbf{p}_{-1}(\mathbf{y}_{b^{\prime}})}{w_{b^{\prime}}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell^{\prime}})}{w_{\ell^{\prime}}},$

where the first inequality uses Lemma 4 applied to $N_{\lambda}$ and the
second inequality uses Lemma 5. The above equation implies that the wBE in
$N_{\lambda}$ does not wpEF1-envy the wLE in $(\mathbf{y},\mathbf{p})$,
implying that agents in $N_{\lambda}$ (the new wME group) do not wpEF1-envy
agents in the new wLE group. ∎

See 8

###### Proof.

Since $N_{1}$ does not participate in any payment drops, only a chore transfer
step can cause $N_{1}$ to stop being the wBE group. Let $j^{\prime}\in M_{1}$
be the chore transferred from $N_{1}$ in the allocation
$(\mathbf{x},\mathbf{p})$ which results in the allocation
$(\mathbf{x}^{\prime},\mathbf{p})$ in which $N_{1}$ is the wLE group. We show
$(\mathbf{x}^{\prime},\mathbf{p})$ is wpEF1. We have two possibilities for the
transfer of $j^{\prime}$.

#### Case 1.

Suppose $j^{\prime}$ is transferred from $N_{1}$ to $N_{\mu}$ in
$(\mathbf{x},\mathbf{p})$. We argue that $N_{1}$ cannot be the wLE group in
$(\mathbf{x}^{\prime},\mathbf{p})$. For sake of contradiction assume this is
the case. Let $\ell\in N_{\lambda}$ and $b\in N_{1}$ be the wLE and wBE in
$(\mathbf{x},\mathbf{p})$ respectively, and let $\ell^{\prime}\in N_{1}$ be
the wLE agent in group $N_{1}$ in $(\mathbf{x}^{\prime},\mathbf{p})$. Observe
that:

$\frac{\mathbf{p}(\mathbf{x}^{\prime}_{\ell^{\prime}})}{w_{\ell^{\prime}}}\geq\frac{\mathbf{p}_{-1}(\mathbf{x}_{b})}{w_{b}}>\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}=\frac{\mathbf{p}(\mathbf{x}^{\prime}_{\ell})}{w_{\ell}},$

where the first inequality uses Lemma 3 applied to group $N_{1}$, the second
inequality uses the fact that $(\mathbf{x},\mathbf{p})$ is not wpEF1, and the
equality holds because $\mathbf{x}_{\ell}=\mathbf{x}^{\prime}_{\ell}$. This
inequality implies that in $(\mathbf{x}^{\prime},\mathbf{p})$, the weighted
earning of the wLE agent $\ell^{\prime}$ in $N_{1}$ exceeds the weighted
earning of the wLE agent $\ell$ in $N_{\lambda}$, which contradicts the
assumption that $N_{1}$ is the wLE group in
$(\mathbf{x}^{\prime},\mathbf{p})$.

#### Case 2.

Suppose $j^{\prime}$ is transferred from $N_{1}$ to $N_{\lambda}$ in
$(\mathbf{x},\mathbf{p})$. If $N_{\lambda}$ is the wBE group in
$(\mathbf{x}^{\prime},\mathbf{p})$ then Lemma 6 implies
$(\mathbf{x}^{\prime},\mathbf{p})$ is wpEF1. Let us therefore assume
$N_{\lambda}$ is the wME group and $N_{\mu}$ is the wBE group in
$(\mathbf{x}^{\prime},\mathbf{p})$. Let $b\in N_{1}$ be the wBE agent in
$(\mathbf{x},\mathbf{p})$, and let $\ell^{\prime}\in N_{1}$ and $b^{\prime}\in
N_{\mu}$ be the wLE and wBE agents in $(\mathbf{x}^{\prime},\mathbf{p})$
respectively. Observe that:

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{b^{\prime}})}{w_{b^{\prime}}}=\frac{\mathbf{p}_{-1}(\mathbf{x}_{b^{\prime}})}{w_{b^{\prime}}}\leq\frac{\mathbf{p}_{-1}(\mathbf{x}_{b})}{w_{b}}\leq\frac{\mathbf{p}(\mathbf{x}^{\prime}_{\ell^{\prime}})}{w_{\ell^{\prime}}},$

where the equality uses $\mathbf{x}^{\prime}_{i}=\mathbf{x}_{i}$ for all $i\in
N_{\mu}$, the first inequality uses the fact that $b$ is the wBE agent in
$\mathbf{x}$, and the second inequality uses Lemma 3 applied to group $N_{1}$.
This shows that if $N_{1}$ is the wLE group in
$(\mathbf{x}^{\prime},\mathbf{p})$, then it is wpEF1. ∎

See 9

###### Proof.

We first note that there can be at most two payment drops (Lines 23-25 and
Lines 27-29) after which a chore transfer from the wBE group $N_{\beta}$ must
occur. We therefore only need to bound the number of chore transfers taking
place between the other two groups. Clearly there can only be $m$ chore
transfers from the wME group $N_{\mu}$ to the wLE group $N_{\lambda}$, after
which $N_{\lambda}$ stops being the wLE group. Consider the last transfer of a
chore $j\in M_{\mu}\cap\mathsf{MPB}_{\lambda}$ in an allocation
$(\mathbf{x},\mathbf{p})$ which results in an allocation $\mathbf{x}^{\prime}$
and causes $N_{\lambda}$ to stop being the wLE group. Using Lemmas 6 and 7, if
$(\mathbf{x}^{\prime},\mathbf{p})$ is not wpEF1 then in
$(\mathbf{x}^{\prime},\mathbf{p})$, $N_{\lambda}$ is the new wME group and
$N_{\mu}$ is the new wLE group and no agent in $N_{\lambda}$ wpEF1-envies an
agent in $N_{\mu}$.

We claim that after the last transfer of the chore $j$ from $N_{\mu}$ to
$N_{\lambda}$, Algorithm 2 will not perform any chore transfer from
$N_{\lambda}$ to $N_{\mu}$ in $(\mathbf{x}^{\prime},\mathbf{p})$. Recall the
Algorithm 2 allows transfers from the wME group to the wLE group only under
certain conditions (Lines 16-18). We argue that these conditions are not met
at $(\mathbf{x}^{\prime},\mathbf{p})$ and hence a transfer from $N_{\lambda}$
to $N_{\mu}$ cannot take place. In $(\mathbf{x}^{\prime},\mathbf{p})$, we have
$j\in M_{\lambda}\cap\mathsf{MPB}_{\mu}$. Consider the allocation
$\mathbf{y}=\mathsf{WPS}(N_{\lambda},\big{(}\bigcup_{i\in
N_{\lambda}}\mathbf{x}^{\prime}_{i}\big{)}\setminus j)$ as computed in Line 16
when deciding whether or not to allow a transfer from $N_{\lambda}$ to
$N_{\mu}$ in $(\mathbf{x}^{\prime},\mathbf{p})$. In the allocation
$\mathbf{x}^{\prime}$, the group $N_{\lambda}$ is assigned all chores
allocated to $N_{\lambda}$ including the transferred chore $j$, i.e.,
$\big{(}\bigcup_{i\in N_{\lambda}}\mathbf{x}^{\prime}_{i}\big{)}\setminus
j)=\big{(}\bigcup_{i\in N_{\lambda}}\mathbf{x}_{i}\big{)})$. Thus the
allocation $\mathbf{y}$ is exactly the allocation $\mathbf{x}$ restricted to
the group $N_{\lambda}$, i.e., for all $i\in N_{\lambda}$,
$\mathbf{y}_{i}=\mathbf{x}_{i}$. We therefore have:

$\min_{i\in N_{\lambda}}\frac{\mathbf{p}(\mathbf{y}_{i})}{w_{i}}=\min_{i\in
N_{\lambda}}\frac{\mathbf{p}(\mathbf{x}_{i})}{w_{i}}\leq\min_{k\in
N_{\mu}}\frac{\mathbf{p}(\mathbf{x}^{\prime}_{k})}{w_{k}},$

where the second inequality is due to Lemma 5 as the wLE in
$(\mathbf{x}^{\prime},\mathbf{p})$ lies in $N_{\mu}$. Therefore, Algorithm 2
will not proceed with a transfer from the wME group $N_{\lambda}$ to the wLE
group $N_{\mu}$ in $(\mathbf{x}^{\prime},\mathbf{p})$.

The next step of the algorithm will thus either be a chore transfer from
$N_{\beta}$ or a payment drop of chores assigned to $N_{\lambda}\cup N_{\mu}$
immediately after which a chore is transferred from $N_{\beta}$. Therefore in
every $\mathsf{poly}(m)$ steps a chore is taken from $N_{\beta}$. ∎

See 10

###### Proof.

Since $N_{1}$ does not participate in any payment drops, only a chore transfer
step can cause $N_{1}$ to stop being the wBE group. Let
$(\mathbf{x},\mathbf{p})$ be the last allocation in the execution of Algorithm
2 in which $N_{1}$ is the wBE group. Let us suppose the transfer of a chore
$j^{\prime}\in M_{1}$ in $(\mathbf{x},\mathbf{p})$ results in the allocation
$\mathbf{x}^{\prime}$ where $N_{1}$ is no longer the wBE group. If $N_{1}$ is
the wLE group in $(\mathbf{x}^{\prime},\mathbf{p})$ then Lemma 8 shows that
$(\mathbf{x}^{\prime},\mathbf{p})$ is wpEF1. If $N_{\lambda}$ is the wBE group
in $(\mathbf{x},\mathbf{p})$ then Lemma 6 implies
$(\mathbf{x}^{\prime},\mathbf{p})$ is wpEF1. Therefore for the rest of the
proof, we assume that

> In $(\mathbf{x}^{\prime},\mathbf{p})$, $N_{\lambda}$ is the wLE group,
> $N_{1}$ is the wME group, and $N_{\mu}$ is the wBE group.

Let $\ell\in N_{\lambda}$ and $b\in N_{1}$ be the wLE and wBE agents in
$(\mathbf{x},\mathbf{p})$, and let $\ell^{\prime}\in N_{\lambda}$ and
$b^{\prime}\in N_{\mu}$ be the wLE and wBE agents in
$(\mathbf{x}^{\prime},\mathbf{p})$. We have two possibilities for the transfer
of $j^{\prime}$ in $(\mathbf{x},\mathbf{p})$.

#### Case 1.

Suppose $j^{\prime}$ is transferred from $N_{1}$ to $N_{\mu}$ in
$(\mathbf{x},\mathbf{p})$. Let $M_{\mu}$ and $M^{\prime}_{\mu}$ be the set of
chores allocated to agents in $N_{\mu}$ in allocations $\mathbf{x}$ and
$\mathbf{x}^{\prime}$ respectively. That is, $M_{\mu}=\bigcup_{i\in
N_{\mu}}\mathbf{x}_{i}$, and $M^{\prime}_{\mu}=\bigcup_{i\in
N_{\mu}}\mathbf{x}^{\prime}_{i}=M_{\mu}\cup j^{\prime}$. The fact that
Algorithm 2 performed the transfer of $j^{\prime}$ from $N_{1}$ to $N_{\mu}$
implies that $|M_{\mu}\cap\mathsf{MPB}_{\lambda}|\neq\emptyset$, and for all
$j\in M_{\mu}\cap\mathsf{MPB}_{\lambda}$ such that for
$\mathbf{y}=\mathsf{WPS}(N_{\mu},M_{\mu}\setminus j)$ as computed in Line 16,
we have:

$\min_{k\in
N_{\mu}}\frac{\mathbf{p}(\mathbf{y}_{k})}{w_{k}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}.$
(5)

Suppose $(\mathbf{x}^{\prime},\mathbf{p})$ is not wpEF1. Notice that in
$(\mathbf{x}^{\prime},\mathbf{p})$, there is a chore $j$ which belongs to the
wBE group $N_{\mu}$ and lies in the MPB set of the wLE group $N_{\lambda}$,
i.e., $j\in M^{\prime}_{\mu}\cap\mathsf{MPB}_{\lambda}$. This is because we
know there exists some chore $j\in M_{\mu}\cap\mathsf{MPB}_{\lambda}$ and
$M^{\prime}_{\mu}=M_{\mu}\cup j^{\prime}$. Thus as per Lines 12-14, Algorithm
2 will transfer chore $j$ from the wBE group $N_{\mu}$ to the wLE group
$N_{\lambda}$ of $(\mathbf{x}^{\prime},\mathbf{p})$, resulting in an
allocation $\mathbf{x}^{\prime\prime}$. We show that
$(\mathbf{x}^{\prime\prime},\mathbf{p})$ is wpEF1 by considering the identity
of the wBE group in $(\mathbf{x}^{\prime\prime},\mathbf{p})$ as follows.

  * (i)

In $(\mathbf{x}^{\prime\prime},\mathbf{p})$, $N_{\lambda}$ is the wBE group.
This means that a chore transfer step caused the wLE group $N_{\lambda}$ of
$(\mathbf{x}^{\prime},\mathbf{p})$ to become the wBE group in
$(\mathbf{x}^{\prime\prime},\mathbf{p})$. By Lemma 6 the allocation
$(\mathbf{x}^{\prime\prime},\mathbf{p})$ must be wpEF1.

  * (ii)

In $(\mathbf{x}^{\prime\prime},\mathbf{p})$, $N_{1}$ is the wBE group. This
contradicts the fact that $(\mathbf{x},\mathbf{p})$ was the last allocation in
which $N_{1}$ is the wBE group.

  * (iii)

In $(\mathbf{x}^{\prime\prime},\mathbf{p})$, $N_{\mu}$ is the wBE group. Let
$\ell^{\prime\prime}$ be the wLE agent and $b^{\prime\prime}\in N_{\mu}$ be
the wBE agent in $(\mathbf{x}^{\prime\prime},\mathbf{p})$.

Let $\hat{\mathbf{x}}^{\prime\prime}$ be the allocation
$\mathbf{x}^{\prime\prime}$ restricted to the agents in group $N_{\mu}$. Then
we have $M^{\prime\prime}_{\mu}:=\bigcup_{i\in
N_{\mu}}\hat{\mathbf{x}}^{\prime\prime}_{i}=M^{\prime}_{\mu}\setminus
j=(M_{\mu}\setminus j)\cup j^{\prime}$. Note that
$\hat{\mathbf{x}}^{\prime\prime}=\mathsf{WPS}(N_{\mu},M^{\prime\prime}_{\mu})=\mathsf{WPS}(N_{\mu},(M_{\mu}\setminus
j)\cup j^{\prime})$, and $\mathbf{y}=\mathsf{WPS}(N_{\mu},M_{\mu}\setminus
j)$. Hence we can apply Lemma 4 to the group $N_{\mu}$ and the allocations
$\hat{\mathbf{x}}^{\prime\prime}$ and $\mathbf{y}$ to obtain:

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime\prime}_{b^{\prime\prime}})}{w_{b^{\prime\prime}}}\leq\min_{k\in
N_{\mu}}\frac{\mathbf{p}(\mathbf{y}_{k})}{w_{k}}.$

Putting this together with Eq. 5, we get:

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime\prime}_{b^{\prime\prime}})}{w_{b^{\prime\prime}}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}(\mathbf{x}^{\prime\prime}_{\ell^{\prime\prime}})}{w_{\ell^{\prime\prime}}},$

where the first inequality uses Eq. 5 and the second inequality uses Lemma 5
which shows that the weighted earning of the wLE agent is non-decreasing. The
above inequality shows that the wBE does not wpEF1-envy the wLE in
$(\mathbf{x}^{\prime\prime},\mathbf{p})$, hence Lemma 2 implies that
$(\mathbf{x}^{\prime\prime},\mathbf{p})$ must be wpEF1.

Thus in this case, after the last allocation $(\mathbf{x},\mathbf{p})$ where
$N_{1}$ was the wBE group, Algorithm 2 halts in at most two subsequent chore
transfers, since either allocation $(\mathbf{x}^{\prime},\mathbf{p})$ or
$(\mathbf{x}^{\prime\prime},\mathbf{p})$ will be wpEF1.

#### Case 2.

Suppose $j^{\prime}$ is transferred from $N_{1}$ to $N_{\lambda}$ in
$(\mathbf{x},\mathbf{p})$. We show that $\mathbf{x}^{\prime}$ is wEF1. Recall
that agents belonging to the same group do not wpEF1-envy each other. We
analyze the other possibilities below.

  * (i)

No agent $i\in N_{\lambda}$ wpEF1-envies another agent $h\in N$ in
$(\mathbf{x}^{\prime},\mathbf{p})$. This is because:

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{i})}{w_{i}}\leq\frac{\mathbf{p}(\mathbf{x}^{\prime}_{\ell^{\prime}})}{w_{\ell^{\prime}}}\leq\frac{\mathbf{p}(\mathbf{x}^{\prime}_{h})}{w_{h}},$

where the first inequality uses that agents in $N_{\lambda}$ do not wpEF1-envy
each other, and the second inequality uses the fact that $\ell^{\prime}$ is a
wLE agent in $(\mathbf{x}^{\prime},\mathbf{p})$.

  * (ii)

No agent $i\in N_{\mu}$ wpEF1-envies an agent $h\in N_{1}$ in
$(\mathbf{x}^{\prime},\mathbf{p})$. This is because:

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{i})}{w_{i}}=\frac{\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}\leq\frac{\mathbf{p}_{-1}(\mathbf{x}_{b})}{w_{b}}\leq\frac{\mathbf{p}(\mathbf{x}^{\prime}_{h})}{w_{h}},$

where the equality uses $\mathbf{x}^{\prime}_{i}=\mathbf{x}_{i}$ for $i\in
N_{\mu}$, the first inequality uses that $b\in N_{1}$ is the wBE agent in
$(\mathbf{x},\mathbf{p})$, and the second inequality uses Lemma 3 applied to
group $N_{1}$.

  * (iii)

No agent $i\in N_{1}$ wpEF1-envies an agent $h\in N_{\mu}$ in
$(\mathbf{x}^{\prime},\mathbf{p})$. This is because:

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{i})}{w_{i}}\leq\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{b^{\prime}})}{w_{b^{\prime}}}\leq\frac{\mathbf{p}(\mathbf{x}^{\prime}_{h})}{w_{h}},$

where the first inequality uses that $b^{\prime}$ is the wBE agent in
$(\mathbf{x}^{\prime},\mathbf{p})$, and the second inequality uses that agents
in $N_{\mu}$ do not wpEF1-each other.

At this point, it only remains to be shown that agents in $N_{1}$ or $N_{\mu}$
do not wEF1-envy agents in $N_{\lambda}$.

  * (iv)

No agent $i\in N_{\mu}$ wEF1-envies an agent $\ell\in N_{\lambda}$. In the
following, we refer to the $t^{th}$ step of Algorithm 2 as time-step $t$. We
use the notation $(\mathbf{x}^{t},\mathbf{p}^{t})$ to denote the allocation
and payments just after the execution of the time-step $t$. Thus the initial
allocation is $(\mathbf{x}^{0},\mathbf{p}^{0})$. Let $t_{4}$ be the time-step
such that
$(\mathbf{x}^{t_{4}},\mathbf{p}^{t_{4}})=(\mathbf{x}^{\prime},\mathbf{p})$.

Let $t_{1}$ be the most recent time-step in the execution of Algorithm 2 after
which $N_{\lambda}$ becomes the wLE group. Formally, $t_{1}$ is the largest
time-step $t$ s.t. in $(\mathbf{x}^{t},\mathbf{p}^{t})$, $N_{\lambda}$ is the
wLE group but in $(\mathbf{x}^{(t-1)},\mathbf{p}^{(t-1)})$, $N_{\lambda}$ is
not the wLE group. In other words, $N_{\lambda}$ is the wLE group during the
time-interval $[t_{1},t_{4}]$. Just before time-step $t_{1}$, the group
$N_{\mu}$ was the wLE group and is the wME group at $t_{1}$. From Lemma 7, we
must have that an agent $i\in N_{\mu}$ (the former wLE group) cannot
wpEF1-envy any agent in $N_{\lambda}$ (the former wME group) at time $t_{1}$.
Thus:

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{t_{1}}_{i})}{w_{i}}\leq\frac{\mathbf{p}(\mathbf{x}^{t_{1}}_{\ell_{1}})}{w_{\ell_{1}}},$
(6)

where $\ell_{1}\in N_{\lambda}$ is the wLE agent in
$(\mathbf{x}^{t_{1}},\mathbf{p}^{t_{1}})$. Thus at time $t_{1}$, no agent
$i\in N_{\mu}$ wpEF1-envies any agent in $N_{\lambda}$. From time-step $t_{1}$
onwards, $N_{\lambda}$ does not lose any chores as it is the wLE group. Hence
it is possible for the agent $i\in N_{\mu}$ to start wEF1-envying an agent in
$N_{\lambda}$ only if $i$ gains a chore. Let $t_{2}\in[t_{1},t_{4}]$ be the
last time-step during which a chore $j_{1}$ is transferred from $N_{1}$ to
$N_{\mu}$. Let $t_{2}^{-}:=t_{2}-1$ be the previous time-step. Let
$M_{\mu}=\bigcup_{i\in N_{\mu}}\mathbf{x}_{i}^{t_{2}^{-}}$, and
$\mathsf{MPB}_{\lambda}$ denote the MPB set of $N_{\lambda}$ at
$(\mathbf{x}^{t_{2}^{-}},\mathbf{p}^{t_{2}^{-}})$. Because Algorithm 2
performed the transfer of $j_{1}$ from $N_{1}$ to $N_{\mu}$, it must be that
$|M_{\mu}\cap\mathsf{MPB}_{\lambda}|\neq\emptyset$ and for every $j_{2}\in
M_{\mu}\cap\mathsf{MPB}_{\lambda}$, we have for allocation
$\mathbf{y}=\mathsf{WPS}(N_{\mu},M_{\mu}\setminus j_{2})$ as computed in Line
16, we have:

$\min_{k\in
N_{\mu}}\frac{\mathbf{p}^{t_{2}^{-}}(\mathbf{y}_{k})}{w_{k}}\leq\frac{\mathbf{p}^{t_{2}^{-}}(\mathbf{x}^{t_{2}^{-}}_{\ell})}{w_{\ell}},\text{for
all $\ell\in N_{\lambda}$}.$ (7)

We now argue that if agent $i\in N_{\mu}$ wpEF1-envies an agent in
$N_{\lambda}$ in the allocation $(\mathbf{x}^{t_{2}},\mathbf{p}^{t_{2}})$,
then Algorithm 2 will perform a chore transfer from $N_{\mu}$ to $N_{\lambda}$
at some later time-step $t_{3}\in[t_{2},t_{4}]$ such that in
$(\mathbf{x}^{t_{3}},\mathbf{p}^{t_{3}})$ no agent in $N_{\mu}$ wpEF1-envies
any agent in $N_{\lambda}$.

To see why, let us examine the chore transfers occuring in $[t_{2},t_{4}]$. By
definition of $t_{2}$, there are no $N_{1}$ to $N_{\mu}$ chore transfers in
this interval. If there are also no $N_{\mu}$ to $N_{\lambda}$ chore transfers
in this interval, then at time-step $t_{4}$, group $N_{1}$ ceases to be the
wBE group due to a chore transfer from $N_{1}$ to $N_{\lambda}$. Hence by the
analysis in Case (1), we have that $(\mathbf{x}^{t_{4}},\mathbf{p}^{t_{4}})$
is wpEF1.

Let us therefore consider the earliest time-step $t_{3}\in[t_{2},t_{4})$ when
a $N_{\mu}$ to $N_{\lambda}$ transfer takes place. With $t_{3}^{-}:=t_{3}-1$
and the definitions of $t_{2}$ and $t_{3}$, one notes that
$\mathbf{x}^{t_{3}^{-}}_{i}=\mathbf{x}^{t_{2}}_{i}$ for every $i\in N_{\mu}$.
By defining $\hat{\mathbf{x}}^{t_{3}}$ as the allocation $\mathbf{x}^{t_{3}}$
restricted to agents in $N_{\mu}$, we observe:

$\displaystyle\hat{\mathbf{x}}^{t_{3}}$
$\displaystyle=\mathsf{WPS}(N_{\mu},\bigcup_{i\in
N_{\mu}}\mathbf{x}_{i}^{t_{3}^{-}}\setminus j_{2})$
$\displaystyle=\mathsf{WPS}(N_{\mu},\bigcup_{i\in
N_{\mu}}\mathbf{x}_{i}^{t_{2}}\setminus j_{2})$
$\displaystyle=\mathsf{WPS}(N_{\mu},(M_{\mu}\setminus j_{2})\cup j_{1}).$

Comparing this with $\mathbf{y}=\mathsf{WPS}(N_{\mu},M_{\mu}\setminus j_{2})$,
we can apply Lemma 3 to the group $N_{\mu}$ to conclude for any $i\in
N_{\mu}$:

$\frac{\mathbf{p}_{-1}^{t_{2}^{-}}(\mathbf{x}^{t_{3}}_{i})}{w_{i}}\leq\min_{k\in
N_{\mu}}\frac{\mathbf{p}^{t_{2}^{-}}(\mathbf{y}_{k})}{w_{k}}.$

Using this with Eq. 7 we get that:

$\frac{\mathbf{p}_{-1}^{t_{2}^{-}}(\mathbf{x}^{t_{3}}_{i})}{w_{i}}\leq\min_{\ell\in
N_{\lambda}}\frac{\mathbf{p}^{t_{2}^{-}}(\mathbf{x}^{t_{2}^{-}}_{\ell})}{w_{\ell}}.$

Now notice that in the period $[t_{2},t_{3}]$, the groups $N_{\lambda}$ and
$N_{\mu}$ undergo payment drops together. Together with the fact that
$\mathbf{x}^{t_{2}^{-}}_{\ell}\subseteq\mathbf{x}^{t_{3}}_{\ell}$ for all
$\ell\in N_{\lambda}$, we also have:

$\frac{\mathbf{p}_{-1}^{t_{3}}(\mathbf{x}^{t_{3}}_{i})}{w_{i}}\leq\min_{\ell\in
N_{\lambda}}\frac{\mathbf{p}^{t_{3}}(\mathbf{x}^{t_{3}}_{\ell})}{w_{\ell}},$

showing that no agent $i\in N_{\mu}$ wpEF1-envies any agent in $N_{\lambda}$
at $(\mathbf{x}^{t_{3}},\mathbf{p}^{t_{3}})$. Subsequent to $t_{3}$, the group
$N_{\mu}$ does not gain any new chores and the group $N_{\lambda}$ will not
lose any chores. Hence no agent in $N_{\mu}$ wEF1-envies any agent in
$N_{\lambda}$ at $(\mathbf{x}^{t_{4}},\mathbf{p}^{t_{4}})$ as well.

  * (v)

We now argue that no agent $i\in N_{1}$ wEF1-envies an agent $\ell\in
N_{\lambda}$ at
$(\mathbf{x}^{\prime},\mathbf{p})=(\mathbf{x}^{t_{4}},\mathbf{p}^{t_{4}})$.
Observe that:

$\displaystyle\frac{\mathbf{p}_{-1}^{t_{4}}(\mathbf{x}^{t_{4}}_{i})}{w_{i}}$
$\displaystyle\leq\frac{\mathbf{p}_{-1}^{t_{4}}(\mathbf{x}^{t_{4}}_{b})}{w_{b}}$
(8) $\displaystyle\leq\max_{h\in
N_{\mu}}\frac{\mathbf{p}_{-1}^{t_{3}}(\mathbf{x}^{t_{3}}_{h})}{w_{h}}$
$\displaystyle\leq\min_{\ell\in
N_{\lambda}}\frac{\mathbf{p}^{t_{3}}(\mathbf{x}^{t_{3}}_{\ell})}{w_{\ell}},$

where the first inequality uses that $b\in N_{\mu}$ is the wBE agent at
$(\mathbf{x}^{t_{4}},\mathbf{p}^{t_{4}})$, the second inequality uses the fact
that in the interval $[t_{3},t_{4}]$, the group $N_{\mu}$ either undergoes
payment drops or loses chores, but does not gain any chores, and the third
inequality uses the fact from part (iv) that no agent $h\in N_{\mu}$
wpEF1-envies any agent $\ell\in N_{\lambda}$ at
$(\mathbf{x}^{t_{3}},\mathbf{p}^{t_{3}})$.

Now observe that no agent in $N_{1}$ ever undergoes a payment drop, hence the
MPB ratio of all agents in $N_{1}$ is one. Eq. 8 therefore implies:

$\displaystyle\min_{j\in\mathbf{x}^{t_{4}}_{i}}\frac{d_{i}(\mathbf{x}^{t_{4}}_{i}\setminus
j)}{w_{i}}$
$\displaystyle=\frac{\mathbf{p}_{-1}^{t_{4}}(\mathbf{x}^{t_{4}}_{i})}{w_{i}}$
(9) $\displaystyle\leq\min_{\ell\in
N_{\lambda}}\frac{\mathbf{p}^{t_{3}}(\mathbf{x}^{t_{3}}_{\ell})}{w_{\ell}}$
$\displaystyle\leq\min_{\ell\in
N_{\lambda}}\frac{d_{i}(\mathbf{x}^{t_{3}}_{\ell})}{w_{\ell}}.$

Moreover since an agent $N_{\lambda}$ can only gain a chore in the interval
$[t_{3},t_{4}]$, we have
$\mathbf{x}^{t_{3}}_{\ell}\subseteq\mathbf{x}^{t_{4}}_{\ell}$ for all $\ell\in
N_{\lambda}$. Together with Eq. 9 this implies that:

$\min_{j\in\mathbf{x}^{t_{4}}_{i}}\frac{d_{i}(\mathbf{x}^{t_{4}}_{i}\setminus
j)}{w_{i}}\leq\min_{\ell\in
N_{\lambda}}\frac{d_{i}(\mathbf{x}^{t_{3}}_{\ell})}{w_{\ell}}\leq\min_{\ell\in
N_{\lambda}}\frac{d_{i}(\mathbf{x}^{t_{4}}_{\ell})}{w_{\ell}},$ (10)

showing that in the allocation $\mathbf{x}^{t_{4}}$, no agent $i\in N_{1}$
wEF1-envies any agent $\ell\in N_{\lambda}$.

Since these cases are exhaustive, we conclude that the allocation
$\mathbf{x}^{\prime}$ is wEF1. ∎

##  4 wEF1+fPO for Two-Chore-Types Instances

We now turn to the problem of existence and computation of a wEF1+fPO
allocation for instances with two types of chores. We answer this question
positively in this section. Thus, our result generalizes that of [4], who
showed that EF1+fPO allocations can be computed in polynomial time for two-
chore-types instances with unweighted agents.

######  Theorem 2.

In any two chore type instance, a wEF1 and fPO allocation exists, and can be
computed in polynomial time.

To prove Theorem 2, we present a polynomial time algorithm, Algorithm 3, that
computes a wEF1 and fPO allocation for a given two-chore-types instance. We
note that Algorithm 3 is also an alternative algorithm to that of [4] for
computing an EF1+PO allocation.

Algorithm 3 wEF1+fPO for two-chore-types instances

Input: Two-chore-types instance $(N,W,M,D)$
Output: An integral wEF1 and fPO allocation $\mathbf{x}$

1:Let $M=A\sqcup B$ be a partition of chores according to type

2:for $i=1$ to $n$ do

3: $\mathbf{x}_{i}\leftarrow M$, $\mathbf{x}_{h}\leftarrow\emptyset$ for
$h\neq i$

4: Set payments as $p_{A}=d_{iA}$ and $p_{B}=d_{iB}$

5: while $(\mathbf{x},\mathbf{p})$ is not wpEF1 do

6:
$L\leftarrow\\{k:k\in\arg\min_{h\in[n]}\frac{\mathbf{p}(\mathbf{x}_{h})}{w_{h}}\\}$
$\triangleright$ $L$ is the set of global wLE agents

7: $\ell_{A}\leftarrow\max(L\cap[i-1])$ $\triangleright$ Set $\ell_{A}$ as the
maximum index wLE in $[i-1]$; $\max\emptyset=\infty$

8: $\ell_{B}\leftarrow\min(L\cap[n]\setminus[i])$ $\triangleright$ Set
$\ell_{B}$ as the minimum index wLE in $[n]\setminus[i]$; $\min\emptyset=0$

9: if $\ell_{A}<i$ and $\mathbf{x}_{i}\cap A\neq\emptyset$ then
$\triangleright$ Transfer $A$-chore from $i$ to $\ell_{A}$

10: Let $a\in\mathbf{x}_{i}\cap A$ be an $A$-chore in $\mathbf{x}_{i}$

11: $\mathbf{x}_{i}\leftarrow\mathbf{x}_{i}\setminus a$,
$\mathbf{x}_{\ell_{A}}\leftarrow\mathbf{x}_{\ell_{A}}\cup a$

12: else if $\ell_{B}>i$ and $\mathbf{x}_{i}\cap B\neq\emptyset$ then
$\triangleright$ Transfer $B$-chore from $i$ to $\ell_{B}$

13: Let $b\in\mathbf{x}_{i}\cap B$ be a $B$-chore in $\mathbf{x}_{i}$

14: $\mathbf{x}_{i}\leftarrow\mathbf{x}_{i}\setminus b$,
$\mathbf{x}_{\ell_{B}}\leftarrow\mathbf{x}_{\ell_{B}}\cup b$

15: else: Break $\triangleright$ Failure in Phase $i$

16: if $(\mathbf{x},\mathbf{p})$ is wpEF1 then

17: return $\mathbf{x}$

Let $M=A\sqcup B$ be a partition of the chores into two sets, each containing
chores of the same type. For $X\in\\{A,B\\}$, we refer to a chore in set $X$
as an $X$-chore, and denote by $d_{iX}$ the disutility an agent $i$ has for
any chore in set $X$.

###  4.1 Algorithm Description

We first sort and re-label the agents in non-decreasing order of
$d_{iA}/d_{iB}$, i.e., for $i<j$,
$\frac{d_{iA}}{d_{iB}}\leq\frac{d_{jA}}{d_{jB}}$. Roughly speaking, agents
with a smaller index prefer to do $A$-chores over $B$-chores, and vice-versa.

Our algorithm proceeds in at most $n$ phases. Starting from $i=1$, in Phase
$i$ we select agent $i$ as the pivot agent. The pivot agent $i$ is initially
assigned all the chores (making $i$ the only agent with wpEF1-envy and the
unique wBE), and the payments of the chores are set according to the
disutilities of the pivot. In other words, we set the payment of a chore in
set $X$ as $p_{X}=d_{iX}$ for $X\in\\{A,B\\}$. While the allocation is not
wpEF1, we attempt to reduce the wpEF1-envy of $i$ by transferring a chore from
$i$ to a wLE agent (this maintains the property that while the allocation is
not wpEF1, $i$ is the only agent with wpEF1-envy and is the unique wBE). Let
$\ell_{A}$ be the index of a wLE agent among agents $1$ through $(i-1)$ if
such an agent exists (otherwise let $\ell_{A}=\infty$), with ties broken in
favour of larger index (Line 7). Similarly, let $\ell_{B}$ be the index of a
wLE agent among agents $(i+1)$ through $n$ if such an agent exists (otherwise
let $\ell_{B}=0$), with ties broken in favour of smaller index (Line 8). We
attempt to make a chore transfer as follows:

  * (Lines 9-11) If $\ell_{A}<i$ and $\mathbf{x}_{i}\cap A\neq\emptyset$, then there is a wLE agent to the left of the pivot agent $i$ and $i$ has an $A$-chore which is on MPB for $\ell_{A}$. Thus, we transfer this $A$-chore from $i$ to $\ell_{A}$.

  * (Lines 12-14) If $\ell_{B}>i$ and $\mathbf{x}_{i}\cap B\neq\emptyset$, then there is a wLE agent to the right of pivot agent $i$ and $i$ has a $B$-chore which is on MPB for $\ell_{B}$. Thus, we transfer this $B$-chore from $i$ to $\ell_{B}$.

  * (Line 15) If neither of the above cases are met, then we have encountered a failure in Phase $i$. It cannot be that a wLE exists on both sides of $i$, as then $i$ must have been able to transfer some chore to a wLE agent (since we maintain that $i$ is the wBE her bundle must be non-empty). This implies that either (i) a wLE agent exists only on the left side of $i$ but $i$ has no $A$-chores to transfer, or (ii) a wLE agent exists only on the right side of $i$ but $i$ has no $B$-chores to transfer. In the case of (i), we say that agent $i$ faces an $A$-fail in Phase $i$, and in the case of (ii) we say that agent $i$ faces a $B$-fail in Phase $i$. After facing a failure, no more transfers are performed in Phase $i$.

Algorithm 3 terminates either when a wpEF1 allocation is found, or when all
phases are completed.

###  4.2 Analysis of Algorithm 3

We now prove Theorem 2 by arguing that Algorithm 3 finds a wpEF1 and fPO
allocation. We first show:

######  Lemma 11.

Throughout the run of Algorithm 3, every allocation is fPO.

###### Proof.

Consider Phase $i$. Recall that the payment of a chore $j\in X$ is
$p_{X}=d_{iX}$, for $X\in\\{A,B\\}$. Consider an allocation $\mathbf{x}$
during Phase $i$. By the nature of transfers performed by Algorithm 3, we have
$\mathbf{x}_{h}\subseteq A$ for all $h<i$, and $\mathbf{x}_{h}\subseteq B$ for
all $h>i$. We show $(\mathbf{x},\mathbf{p})$ is on MPB. This is clear for
agent $i$. For an agent $h<i$, the ordering of the agents implies that
$\frac{d_{hA}}{d_{hB}}\leq\frac{d_{iA}}{d_{iB}}$. Thus,
$\frac{d_{hA}}{p_{A}}\leq\frac{d_{hB}}{p_{B}}$, showing that $\mathbf{x}_{h}$
is on MPB for agent $h$. Likewise for an agent $h>i$, the ordering of the
agents implies that $\frac{d_{iA}}{d_{iB}}\leq\frac{d_{hA}}{d_{hB}}$. Thus,
$\frac{d_{hB}}{p_{B}}\leq\frac{d_{hA}}{p_{A}}$, once again showing that
$\mathbf{x}_{h}$ is on MPB for agent $h$. By the Second Welfare Theorem we can
conclude that $\mathbf{x}$ is fPO since $(\mathbf{x},\mathbf{p})$ is on MPB. ∎

To show that Algorithm 3 eventually finds a wpEF1 allocation, we first show:

######  Lemma 12.

Throughout the execution of Phase $i$, if the allocation is not wpEF1 then
agent $i$ is the only weighted big earner.

###### Proof.

We prove this inductively. In the initial allocation where all chores are
assigned to $i$, it is clear that $i$ is the only agent with wpEF1-envy and is
the wBE. Suppose it is true that in an allocation $\mathbf{x}$ during the
execution of Phase $i$, agent $i$ is the only agent with wpEF1-envy. Let
$\mathbf{x}^{\prime}$ be the allocation obtained by transferring one chore $j$
from $i$ to a wLE $\ell$. Thus
$\mathbf{x}^{\prime}_{i}=\mathbf{x}_{i}\setminus j$,
$\mathbf{x}^{\prime}_{\ell}=\mathbf{x}_{\ell}\cup j$, and for
$h\notin\\{i,\ell\\}$, we have $\mathbf{x}^{\prime}_{h}=\mathbf{x}_{h}$. We
show that no agent $h\neq i$ has wpEF1-envy towards any other agent. We have
the following four cases to consider:

  * •

Agents $h\notin\\{i,\ell\\}$ does not wpEF1-envy $k\neq i$. Note that
$\mathbf{x}^{\prime}_{h}=\mathbf{x}_{h}$ and
$\mathbf{x}_{k}\subseteq\mathbf{x}^{\prime}_{k}$. Since $h$ did not wpEF1-envy
$k$ in $(\mathbf{x},\mathbf{p})$, $h$ will not wpEF1-envy agent $k$ in
$(\mathbf{x}^{\prime},\mathbf{p})$ as well.

  * •

Agent $h\notin\\{i,\ell\\}$ does not wpEF1-envy $i$ in $\mathbf{x}^{\prime}$.
Observe the following.

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{h})}{w_{h}}=\frac{\mathbf{p}_{-1}(\mathbf{x}_{h})}{w_{h}}\leq\frac{\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}\leq\frac{\mathbf{p}(\mathbf{x}_{i}\setminus
j)}{w_{i}}=\frac{\mathbf{p}(\mathbf{x}^{\prime}_{i})}{w_{i}}.$

Here: (i) the first equality holds because
$\mathbf{x}^{\prime}_{h}=\mathbf{x}_{h}$, (ii) the first inequality holds
because $i$ is a wBE in $(\mathbf{x},\mathbf{p})$, (iii) the second inequality
is due to the definition of $\mathbf{p}_{-1}(\cdot)$, and (iv) the last
equality is because $\mathbf{x}^{\prime}_{i}=\mathbf{x}_{i}\setminus j$.

  * •

Agent $\ell$ does not wpEF1-envy any agent $h\notin\\{i,\ell\\}$. Observe the
following.

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}(\mathbf{x}_{h})}{w_{h}}=\frac{\mathbf{p}(\mathbf{x}^{\prime}_{h})}{w_{h}}.$

Here: (i) the first inequality uses
$\mathbf{x}^{\prime}_{\ell}=\mathbf{x}_{\ell}\cup j$ and the definition of
$\mathbf{p}_{-1}(\cdot)$, (ii) the second inequality holds because $\ell$ is a
wLE in $(\mathbf{x},\mathbf{p})$, and (iii) the last equality uses
$\mathbf{x}^{\prime}_{h}=\mathbf{x}_{h}$.

  * •

Agent $\ell$ does not wpEF1-envy agent $i$. Observe the following.

$\frac{\mathbf{p}_{-1}(\mathbf{x}^{\prime}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}}<\frac{\mathbf{p}_{-1}(\mathbf{x}_{i})}{w_{i}}\leq\frac{\mathbf{p}(\mathbf{x}^{\prime}_{i})}{w_{i}}.$

Here: (i) the first inequality uses
$\mathbf{x}^{\prime}_{\ell}=\mathbf{x}_{\ell}\cup j$ and the definition of
$\mathbf{p}_{-1}(\cdot)$, (ii) the second inequality uses the fact that
$(\mathbf{x},\mathbf{p})$ was not wpEF1, and (iii) the last equality uses
$\mathbf{x}^{\prime}_{i}=\mathbf{x}_{i}\setminus j$.

Thus, only agent $i$ can wpEF1-envy another agent in
$(\mathbf{x}^{\prime},\mathbf{p})$. Consequently, $i$ is the only wBE. ∎

The above lemma shows that if we did not find a wpEF1 allocation in Phase $i$,
it must be because the only wBE $i$ could not transfer a chore to a wLE agent.
That is, Phase $i$ was terminated due to $i$ facing either an $A$-fail or a
$B$-fail. We next prove that:

######  Lemma 13.

If agent $i$ faces a $B$-fail, then agent $(i+1)$ cannot face an $A$-fail.

Before proving Lemma 13, we note that we can now prove Theorem 2. By
definition of a failure, agent $1$ cannot face an $A$-fail. Thus if agent $1$
faces a failure, it must be due to a $B$-fail. By Lemma 13, we know that agent
$2$ cannot face an $A$-fail. Proceeding inductively, we conclude for each
$i\in[n]$ that either agent $i$ faces a $B$-fail or does not face a failure at
all. However, agent $n$ cannot face a $B$-fail by definition of failure. Thus
it must be that there is some pivot agent $i^{*}\in[n]$ who did not face a
failure.

Therefore, by invoking Lemma 12 we conclude that in Phase $i^{*}$, it was
always possible to transfer chores from the only wBE agent $i^{*}$ to a wLE
agent, until the allocation became wpEF1. Lemma 11 shows that all allocations
encountered in Algorithm 3 are fPO. Thus, a wEF1 and fPO allocation will be
found in Phase $i^{*}$. Since there are at most $n$ phases and there are at
most $m$ chore transfers in each phase, Algorithm 3 terminates in polynomial
time. This proves Theorem 2.

It only remains to prove the crucial Lemma 13. To do this, we relate the
allocation returned by Algorithm 3 in Phase $i$ with the allocation returned
by running the weighted picking sequence algorithm for assigning $A$-chores to
$[i]$ and $B$-chores to $[n]\setminus[i]$. Let $\mathcal{A}$ be the algorithm
given by Algorithm 4, which allocates identical chores to agents by initially
assigning all chores to agent 1 and then transferring chores one by one to the
smallest index wLE agent until the allocation is wpEF1. Thus $\mathcal{A}$
mimics the execution of Phase $i$ of Algorithm 2 for assigning $B$-chores, as
well as $A$ chores but in reverse order. Our next lemma proves that the
executions of $\mathcal{A}$ and $\mathsf{WPS}$ return the same allocation for
identical chores.

Algorithm 4 Algorithm $\mathcal{A}$

Input: Agents $N$, set of identical chores $M$
Output: A wEF1 allocation $\mathbf{x}$

1:$\mathbf{x}_{1}\leftarrow M$; $\mathbf{x}_{i}\leftarrow\emptyset$ for $i\neq
1$

2:Set payments as $p_{j}=1$ for all $j\in M$

3:while $(\mathbf{x},\mathbf{p})$ is not wpEF1 do

4: $i\leftarrow\arg\min_{k\geq 2}\frac{\mathbf{p}(\mathbf{x}_{k})}{w_{k}}$;
ties broken in favour of smaller index

5: Transfer a single chore from $\mathbf{x}_{1}$ to $\mathbf{x}_{i}$

6:return $\mathbf{x}$

######  Lemma 14.

Consider a set $N$ of agents and a set $M$ of identical chores. Then the
allocations returned by Algorithm 4 and $\mathsf{WPS}$ are the same. That is,
$\mathcal{A}(N,M)=\mathsf{WPS}(N,M)$.

###### Proof.

Let $\mathbf{x}(t)$ (resp. $\mathbf{y}(t)$) denote the allocation after $t$
iterations of $\mathcal{A}(N,M)$ (resp. $\mathsf{WPS}(N,M)$). Since the chores
are identical, an allocation is characterized simply by the number of chores
assigned to each agent. Let $x_{i}(t)$ (resp. $y_{i}(t)$) denote the number of
chores assigned to agent $i$ in $\mathbf{x}(t)$ (resp. $\mathbf{y}(t)$). Note
that $\mathsf{WPS}(N,M)$ runs for $m$ iterations. We claim that:

> For all $0\leq t\leq m$ and $2\leq i\leq n$, $y_{i}(t)=x_{i}(t-y_{1}(t))$.

We prove this claim by induction on $t$. For $t=0$ the claim holds since
$y_{i}(0)=x_{i}(0)=0$ for all $i\neq 1$. Suppose the claim is true for some
$0\leq t\leq m-1$. Consider iteration $(t+1)$ of $\mathsf{WPS}(N,M)$. We have
two cases.

  * •

$\mathsf{WPS}(N,M)$ assigns a chore to agent $1$ in iteration $(t+1)$. Then
$y_{1}(t+1)=y_{1}(t)+1$ and $y_{i}(t+1)=y_{i}(t)$ for $i\neq 1$ . We then have
for $i\neq 1$:

$x_{i}(t+1-y_{1}(t+1))=x_{i}(t-y_{1}(t))=y_{i}(t)=y_{i}(t+1),$

where we used the induction hypothesis in the second equality.

  * •

$\mathsf{WPS}(N,M)$ assigns a chore to agent $k\neq 1$ in iteration $(t+1)$.
We argue that $k$ is a minimum-index wLE in
$(\mathbf{x}(t-y_{1}(t)),\mathbf{p})$; recall that $\mathcal{A}$ sets all
payments equal to $1$. Since $\mathsf{WPS}$ chose agent $k$ to be assigned a
chore in iteration $(t+1)$, agent $k$ must be a minimum-index agent satisfying
$\frac{y_{k}(t)}{w_{k}}\leq\frac{y_{h}(t)}{w_{h}}$, for all $h\in N$. Then by
the induction hypothesis we have
$\frac{x_{k}(t-y_{1}(t))}{w_{k}}\leq\frac{x_{h}(t-y_{1}(t))}{w_{h}}$, for all
$h\in N$, implying $k$ is the minimum-index wLE in
$(\mathbf{x}(t-y_{1}(t)),\mathbf{p})$.

We show that agent $1$ wpEF1-envies agent $k$ in
$(\mathbf{x}(t-y_{1}(t)),\mathbf{p})$ as follows:

$\displaystyle\frac{x_{k}(t-y_{1}(t))}{w_{k}}=\frac{y_{k}(t)}{w_{k}}\qquad\qquad\qquad\qquad\quad\;\;{\text{
(using IH)}}$
$\displaystyle<\frac{y_{1}(t)}{w_{1}}\qquad\qquad\qquad\quad{\text{ (since $k$
is the min-index wLE)}}$ $\displaystyle=\frac{t-\sum_{i\geq
2}y_{i}(t)}{w_{1}}\qquad\qquad\qquad\quad\quad\text{ ($\mathbf{y}(t)$ has $t$
chores)}$ $\displaystyle\leq\frac{t-\sum_{i\geq
2}x_{i}(t-y_{1}(t))}{w_{1}}\qquad\qquad\qquad\quad\quad\text{ (using IH)}$
$\displaystyle=\frac{m-1-\sum_{i\geq
2}x_{i}(t-y_{1}(t))}{w_{1}}\qquad\;\;\text{ (since $t\leq m-1$)}$
$\displaystyle=\frac{x_{1}(t-y_{1}(t))}{w_{1}}.\;\;\text{(since
$\mathbf{x}(t-y_{1}(t))$ has $m$ total chores)}$

Thus $\mathcal{A}$ will perform a transfer of a chore from agent $1$ to agent
$k$ in $(\mathbf{x}(t-y_{1}(t)),\mathbf{p})$. This results in the allocation
$\mathbf{x}(t+1-y_{1}(t))$, which equals $\mathbf{x}(t+1-y_{1}(t+1))$ since
$y_{1}(t+1)=y_{1}(t)$. Using the induction hypothesis, the claim then follows
by noting that for agent $i\in[n]\setminus\\{1,k\\}$:

$\displaystyle x_{i}(t+1-y_{1}(t+1))$ $\displaystyle=x_{i}(t+1-y_{1}(t))$
$\displaystyle=x_{i}(t-y_{1}(t)$ $\displaystyle=y_{i}(t)=y_{i}(t+1).$

and for agent $k$:

$\displaystyle x_{k}(t+1-y_{1}(t+1))$ $\displaystyle=x_{k}(t+1-y_{1}(t))$
$\displaystyle=x_{k}(t-y_{1}(t))+1$ $\displaystyle=y_{k}(t)+1=y_{k}(t+1).$

Thus by induction the claim holds. Plugging $t=m$ we obtain
$x_{i}(m-y_{1}(m))=y_{i}(m)$ for all $i\neq 1$. Then we have
$x_{1}(m-y_{1}(m))=m-\sum_{i\geq 2}x_{i}(m-y_{1}(m))=m-\sum_{i\geq
2}y_{i}(m)=y_{1}(m)$. This shows that $\mathbf{x}(m-y_{1}(m))=\mathbf{y}$.
Since $\mathbf{y}=\mathsf{WPS}(N,M)$ is wEF1, so is the allocation
$\mathbf{x}(m-y_{1}(m))$, and $\mathcal{A}(N,M)$ halts and returns with
$\mathbf{x}(m-y_{1}(m))$. This proves that
$\mathcal{A}(N,M)=\mathsf{WPS}(N,M)$. ∎

We now prove Lemma 13. See 13

###### Proof.

For the sake of contradiction, assume agent $i$ faces a $B$-fail and agent
$(i+1)$ faces an $A$-fail. Let $(\mathbf{x},\mathbf{p})$ be the allocation
when Phase $i$ was terminated and let $\ell>i$ be the minimum-index wLE.
Moreover, all chores in $A$ are allocated to agents $1$ to $i$ while chores in
$B$ are allocated to agents $(i+1)$ to $n$. Next, let
$(\mathbf{x}^{\prime},\mathbf{p}^{\prime})$ be the allocation when Phase
$(i+1)$ was terminated and let $k<i+1$ be the maximum index wLE. As in
$\mathbf{x}$, in $\mathbf{x}^{\prime}$ all chores in $A$ are allocated to
agents $1$ to $i$ while chores in $B$ are allocated to agents $(i+1)$ to $n$.

Let us first examine the allocation of $B$ to agents $(i+1)$ to $n$. Let
$\hat{\mathbf{x}}$ (resp. $\hat{\mathbf{x}}^{\prime}$) be the allocation
$\mathbf{x}$ (resp. $\mathbf{x}^{\prime}$) when restricted to agents $(i+1)$
to $n$. Observe that $\hat{\mathbf{x}}$ is obtained by iteratively allocating
a $B$-chore to the wLE in $[n]\setminus[i]$. Since the payment of each
$B$-chore is the same, the wLE is the agent with the least ratio
$t_{\ell}/w_{\ell}$, where $t_{\ell}$ is the number of $B$-chores allocated to
agent $\ell$. Moreover since transfers are made to minimum-index wLE agents,
the allocation $\hat{\mathbf{x}}$ is the same as
$\mathsf{WPS}([n]\setminus[i],B)$, the allocation obtained by using the
weighted picking sequence algorithm applied to agents $(i+1)$ to $n$ with ties
broken in favour of smaller index agents. Thus,
$\hat{\mathbf{x}}=\mathsf{WPS}([n]\setminus[i],B)$. On the other hand,
$\hat{\mathbf{x}}^{\prime}$ is obtained by initially allocating all chores in
$B$ to agent $(i+1)$ and then iteratively transferring a chore to the minimum-
index wLE. Thus, $\hat{\mathbf{x}}^{\prime}$ is an allocation encountered in
the run of algorithm $\mathcal{A}$ (Alg. 4) applied to agents $(i+1)$ to $n$,
with all chores initially assigned to $(i+1)$. Thus we have for all
$h\in(i+1,n]$, $\hat{\mathbf{x}}^{\prime}_{h}\subseteq\mathbf{y}_{h}$, where
$\mathbf{y}=\mathcal{A}([n]\setminus[i],B)$. In Lemma 14 we show that
$\mathsf{WPS}([n]\setminus[i],B)=\mathcal{A}([n]\setminus[i],B)$. Thus we have
for $h\in(i+1,n]$,
$\hat{\mathbf{x}}^{\prime}_{h}\subseteq\hat{\mathbf{x}}_{h}$. In particular,
this implies $\mathbf{x}^{\prime}_{\ell}\subseteq\mathbf{x}_{\ell}$.

Let us next examine the allocation of $A$ to agents $1$ to $i$. Let
$\tilde{\mathbf{x}}$ (resp. $\tilde{\mathbf{x}}^{\prime}$) be the allocation
$\mathbf{x}$ (resp. $\mathbf{x}^{\prime}$) when restricted to agents $1$ to
$i$. Note that in $\mathbf{x}$, chores are transferred from $i$ to the maximum
index wLE. Hence, by reversing the labels of agents in $[i]$ and using similar
arguments, we have that $\tilde{\mathbf{x}}^{\prime}$ is the same as
$\mathsf{WPS}([i],A)$, and $\tilde{\mathbf{x}}$ is an allocation encountered
in the run of $\mathcal{A}$ applied to agents $1$ to $i$. Thus we have for all
$h\in[1,i)$, $\tilde{\mathbf{x}}_{h}\subseteq\mathbf{z}_{h}$, where
$\mathbf{z}=\mathcal{A}([i],A)$. Lemma 14 shows
$\mathsf{WPS}([i],A)=\mathcal{A}([i],A)$, hence
$\tilde{\mathbf{x}}_{h}\subseteq\tilde{\mathbf{x}}^{\prime}_{h}$ for
$h\in[1,i)$. In particular, this implies
$\mathbf{x}_{k}\subseteq\mathbf{x}^{\prime}_{k}$.

We can now complete the proof of the lemma. Observe the following:

$\frac{\mathbf{p}^{\prime}(\mathbf{x}_{k})}{w_{k}}\leq\frac{\mathbf{p}^{\prime}(\mathbf{x}^{\prime}_{k})}{w_{k}}\leq\frac{\mathbf{p}^{\prime}(\mathbf{x}^{\prime}_{\ell})}{w_{\ell}}\leq\frac{\mathbf{p}^{\prime}(\mathbf{x}_{\ell})}{w_{\ell}},$
(11)

where the first inequality uses
$\mathbf{x}_{k}\subseteq\mathbf{x}^{\prime}_{k}$, the second uses that $k$ is
a wLE in $(\mathbf{x}^{\prime},\mathbf{p}^{\prime})$, and the third uses
$\mathbf{x}^{\prime}_{\ell}\subseteq\mathbf{x}_{\ell}$. Next, we note that
since $\ell$ is the wLE in $(\mathbf{x},\mathbf{p})$ and $k$ is not, we have:

$\frac{\mathbf{p}(\mathbf{x}_{k})}{w_{k}}>\frac{\mathbf{p}(\mathbf{x}_{\ell})}{w_{\ell}},$
(12)

Using the above two inequalities (12) and (11), we get
$\frac{\mathbf{p}(\mathbf{x}_{\ell})}{\mathbf{p}(\mathbf{x}_{k})}<\frac{w_{\ell}}{w_{k}}\leq\frac{\mathbf{p}^{\prime}(\mathbf{x}_{\ell})}{\mathbf{p}^{\prime}(\mathbf{x}_{k})}$.
Note that $\mathbf{p}(\mathbf{x}_{\ell})=|\mathbf{x}_{\ell}|\cdot
p_{B}=|\mathbf{x}_{\ell}|\cdot d_{iB}$ and
$\mathbf{p}(\mathbf{x}_{k})=|\mathbf{x}_{k}|\cdot
p_{A}=|\mathbf{x}_{\ell}|\cdot d_{iA}$. Similarly,
$\mathbf{p}^{\prime}(\mathbf{x}_{\ell})=|\mathbf{x}_{\ell}|\cdot
p^{\prime}_{B}=|\mathbf{x}_{\ell}|\cdot d_{(i+1)B}$ and
$\mathbf{p}^{\prime}(\mathbf{x}_{k})=|\mathbf{x}_{k}|\cdot
p^{\prime}_{A}=|\mathbf{x}_{k}|\cdot d_{(i+1)A}$. Putting these together, we
obtain $\frac{d_{iB}}{d_{iA}}<\frac{d_{(i+1)B}}{d_{(i+1)A}}$, which is a
contradiction, since we sorted agents in non-decreasing order of
$d_{iA}/d_{iB}$. ∎

##  5 Discussion

In this work we studied the problem of computing a wEF1 and fPO allocation of
chores for agents with unequal weights or entitlements. We showed positive
algorithmic results for this problem for instances with three types of agents,
or two types of chores. The existence of EF1 and fPO allocations of chores in
the symmetric case remains a hard open problem. Our results further our
understanding of this problem by contributing to the body of positive non-
trivial results. Together with the result of [18] concerning bivalued chores,
our paper shows that wEF1 and fPO allocations exists for every structured
instance known so far that admits an EF1 and fPO allocation. Our idea of
combining the competitive equilibrium framework with envy-resolving algorithms
like the weighted picking sequence algorithms could be an important tool in
settling the problem in its full generality.

##  Appendix A Examples

######  Example 3.

An unweighted EF1+PO allocation in an instance with copies of agents does not
give a weighted wEF1+PO allocation.

Consider an instance with two agents $a$ and $b$ and three chores, with
$w_{a}=1$ and $w_{b}=2$, and disutilities given by:

| $j_{1}$ | $j_{2}$ | $j_{3}$
---|---|---|---
$a$ | 1 | 10 | 10
$b$ | 2 | 10 | 10

Suppose we create two copies of agent $b$: agents $b_{1}$ and $b_{2}$, and
construct an EF1+PO allocation in the resulting unweighted instance with three
agents $a,b_{1}$ and $b_{2}$. Observe that the following allocation
$\mathbf{x}$ is EF1+PO:

  * •

$\mathbf{x}_{a}=\\{j_{1}\\}$,

  * •

$\mathbf{x}_{b_{1}}=\\{j_{2}\\}$,

  * •

$\mathbf{x}_{b_{2}}=\\{j_{3}\\}$.

Now consider the allocation $\mathbf{y}$ where agents $b_{1}$ and $b_{2}$ are
combined to give $\mathbf{y}_{b}=\mathbf{y}_{b_{1}}\cup\mathbf{y}_{b_{2}}$,
and $\mathbf{y}_{a}=\mathbf{x}_{a}$. However $\mathbf{y}$ is not wEF1 since
$b$ wEF1 envies $a$ as $d_{b}(\mathbf{y}_{b}\setminus
j)/w_{b}=10/2>2=d_{b}(\mathbf{y}_{a})/w_{a}$ for $j\in\\{j_{2},j_{3}\\}$.

######  Example 4.

A weighted wEF1+PO allocation does not give an unweighted EF1+PO allocation
with copies of agents.

We observe the following weighted instance with two agents $a$ and $b$ and
seven chores, where $w_{a}=1$ and $w_{b}=3$.

| $j_{1}$ | $j_{2}$ | $j_{3}$ | $j_{4}$ | $j_{5}$ | $j_{6}$ | $j_{7}$
---|---|---|---|---|---|---|---
$a$ | 2 | 2 | 2 | 3 | 3 | 3 | 3
$b$ | 100 | 100 | 100 | 99 | 99 | 99 | 99

Then, the following allocation $\mathbf{x}$ is wEF1+PO:

  * •

$\mathbf{x}_{a}=\\{j_{1},j_{2},j_{3}\\}$,

  * •

$\mathbf{x}_{b}=\\{j_{4},j_{5},j_{6},j_{7}\\}$.

However, this allocation does not give an unweighted EF1+PO allocation where
agent $b$ is split into three copies $b_{1}$, $b_{2}$, and $b_{3}$, and
$\mathbf{x}_{b_{1}}\cup\mathbf{x}_{b_{2}}\cup\mathbf{x}_{b_{3}}=\mathbf{x}_{b}$.
Indeed, some copy of $b$ must receive at most one chore, so this agent will be
EF1-envied by $a$.

## References

  * [1] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu.  Fair division of indivisible goods: Recent progress and open questions.  Artificial Intelligence, 322:103965, 2023.  URL: https://www.sciencedirect.com/science/article/pii/S000437022300111X, doi:10.1016/j.artint.2023.103965.
  * [2] Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh.  Fair allocation of indivisible goods and chores.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), page 53–59, 2019.
  * [3] Haris Aziz, Bo Li, Hervé Moulin, and Xiaowei Wu.  Algorithmic fair allocation of indivisible items: a survey and new questions.  SIGecom Exch., 20(1):24–40, nov 2022.  doi:10.1145/3572885.3572887.
  * [4] Haris Aziz, Jeremy Lindsay, Angus Ritossa, and Mashbat Suzuki.  Fair allocation of two types of chores.  In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’23, page 143–151, Richland, SC, 2023. International Foundation for Autonomous Agents and Multiagent Systems.
  * [5] 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.
  * [6] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish.  On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources.  In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:23, 2021.
  * [7] 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), page 305–322, 2016.
  * [8] Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick.  Weighted envy-freeness in indivisible item allocation.  In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), page 231–239, 2020.
  * [9] Soroush Ebadian, Dominik Peters, and Nisarg Shah.  How to fairly allocate easy and difficult chores.  In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2022.
  * [10] Uriel Feige, Ariel Sapir, and Laliv Tauber.  A tight negative example for MMS fair allocations.  In Web and Internet Economics - 17th International Conference, WINE, volume 13112, pages 355–372, 2021.
  * [11] D.K. Foley.  Resource allocation and the public sector.  Yale Economic Essays, 7(1):45–98, 1967.
  * [12] Jugal Garg and Aniket Murhekar.  On fair and efficient allocations of indivisible goods.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
  * [13] Jugal Garg, Aniket Murhekar, and John Qin.  Fair and efficient allocations of chores under bivalued preferences.  Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 5043–5050, 2022.
  * [14] Jugal Garg, Aniket Murhekar, and John Qin.  New algorithms for the fair and efficient allocation of indivisible chores.  In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages 2710–2718. International Joint Conferences on Artificial Intelligence Organization, 8 2023.  Main Track.  URL: https://doi.org/10.24963/ijcai.2023/302.
  * [15] Richard Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi.  On approximately fair allocations of indivisible goods.  In In ACM Conference on Electronic Commerce (EC, pages 125–131, 2004.
  * [16] A. Mas-Colell, M.D. Whinston, and J.R. Green.  Microeconomic Theory.  Oxford University Press, 1995.
  * [17] H. Steinhaus.  Sur la division pragmatique.  Econometrica, 17(1):315–319, 1949.
  * [18] Xiaowei Wu, Cong Zhang, and Shengwei Zhou.  Weighted EF1 allocations for indivisible chores.  In Proceedings of the 24th ACM Conference on Economics and Computation, EC ’23, page 1155, New York, NY, USA, 2023. Association for Computing Machinery.  doi:10.1145/3580507.3597763.