Weighted EF1 and PO Allocations with Few Types of Agents or Chores

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 [Steinhaus, 1949], 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 [Aziz et al., 2022; Amanatidis et al., 2023]). Although fairness of an allocation is inherently subjective, envy-freeness (EF) is a quintessential and well-established notion of fairness [Foley, 1967]. 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 [Lipton et al., 2004; Bhaskar et al., 2021].

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., [Caragiannis et al., 2016; Barman et al., 2018; Garg and Murhekar, 2021; Ebadian et al., 2022; Garg et al., 2022; Garg et al., 2023; Aziz et al., 2019; Aziz et al., 2023]. 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, [Caragiannis et al., 2016] 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, [Barman et al., 2018] 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-formoney'. 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, [Garg and Murhekar, 2021] 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 [Aziz et al., 2019], (iii) bivalued disutilities [Garg et al., 2022; Ebadian et al., 2022], (iv) three agents [Garg et al., 2023], (v) two types of agents [Garg et al., 2023], and (vi) two types of chores [Aziz et al., 2023]. 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, [Chakraborty et al., 2020] 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 [Wu et al., 2023] via a modification of the weighted picking sequence algorithm, and develops a novel analysis technique. [Chakraborty et al., 2020] showed that wEF1 and PO allocation exists and can be computed in pseudo-polynomial time for goods by adapting the algorithm of [Barman et al., 2018] to the weighted case. For chores, [Wu et al., 2023] 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 [Aziz et al., 2019], (ii) three agents [Garg et al., 2023], and (iii) two-agent-types [Garg et al., 2023]. 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 [Feige et al., 2021]. Theorem 2 subsumes previous work showing EF1 and PO allocations exist for two-choretype instances [Aziz et al., 2023], 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 our full paper [Garg et al., 2024] 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 payments 1 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 1 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 [Aziz et al., 2023]. 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 novel properties of a weighted picking sequence algorithm for chores (e.g. Lemmas 3 and 4). We believe this may be of independent interest, and may find use in algorithm design for fair division to asymmetric agents in the future.

1 Chores have attached payments while goods have prices.

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 = {wi}i∈N with wi > 0 denoting the weight of agent i, a set M = [m] of m indivisible chores, and a list D = {di}i∈N, where di : 2M →R≥0 is agent i's disutility function over the chores. We let di(j) denote the disutility of chore j for agent i. We assume disutility functions are additive, so that for every i ∈ N and S ⊆ M, di(S) = ∑j∈S di(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 = {c1, . . . , ck} of k ∈ N disutility functions s.t. for all i ∈ N, di ∈ C.
• k-chore-type instance if there are k types of chores. That is, the set of chores can be partitioned as M = ⋃ℓ∈[k] Mℓ, where each set Mℓ consists of copies of the same chore.

An integral allocation x = (x1, x2, . . . , xn) is a partition of the chores into n bundles, where agent i receives bundle xi ⊆ M and gets disutility di(xi). In a fractional allocation x ∈ [0, 1]n×m, chores are divisible and xij ∈ [0, 1] denotes the fraction of chore j given to agent i. Here di(xi) = ∑j∈M di(j)·xij . We will assume that allocations are integral unless explicitly stated otherwise.

Fairness and efficiency notions. An allocation x satisfies:

1. Envy-free up to one chore (EF1) for symmetric agents if for all i, h ∈ N, di(xi \ j) ≤ di(xh) for some j ∈ xi.
2. Weighted envy-free up to one chore (wEF1) if for all i, h ∈ N, di(xi\j) wi ≤ di(xh) wh for some j ∈ xi.
3. Pareto-optimal if there is no allocation y that dominates x. An allocation y dominates an allocation x if for all i ∈ N, di(yi) ≤ di(xi), and there exists h ∈ N such that dh(yh) < dh(xh).
4. Fractionally Pareto-optimal if there is no fractional allocation that dominates 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 p = (p1, . . . , pm) with the chores. Each agent i aims to earn a desired minimum payment of ei ≥ 0 by performing chores in exchange for payment. In a (fractional) allocation x with payments p, the earning of agent i is p(xi) = ∑j∈M pj · xij. For each agent i, we define the pain-per-buck ratio αij of chore j as αij = di(j)/pj and the minimum-pain-per-buck (MPB) ratio as αi = minj∈M αij. Further, we let MPBi = {j ∈ M | di(j)/pj = αi} denote the set of chores which are MPB for agent i under payments p.

We say that (x, p) is a competitive equilibrium (CE) if (i) for all j ∈ M, ∑i∈N xij = 1, i.e., all chores are completely allocated, (ii) for all i ∈ N, p(xi) = ei, i.e., each agent receives her minimum payment, and (iii) for all i ∈ N, xi ⊆ MPBi, i.e., agents receive only chores which are MPB for them. The First Welfare Theorem [Mas-Colell et al., 1995] shows that competitive equilibria are efficient, i.e., for a CE (x, p), the allocation x is fPO.

For a CE (x, p) where x is integral, we let p-1(xi) := minj∈xi p(xi \ j) denote the payment agent i receives from xi excluding her highest paying chore.

Definition 1. (Weighted payment EF1) An allocation (x, p) is said to be weighted payment envy-free up to one chore (wpEF1) if for all i, h ∈ N we have p-1(xi) wi ≤ p(xh) wh . Agent i wpEF1-envies h if p-1(xi) wi > p(xh) wh .

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

Lemma 1. Let (x, p) be a CE with x integral. If (x, p) is wpEF1, then x is wEF1 and fPO.

Proof. Let αi be the MPB ratio of agent i in (x, p). Consider any pair of agents i, h ∈ N. We have:

where the first and last transitions use that (x, p) is on MPB, and the middle inequality uses Definition 1. This shows that x is wEF1. Moreover, the First Welfare Theorem [Mas-Colell et al., 1995] implies that the allocation x is fPO since (x, p) is a CE.

An agent ℓ is called a weighted least earner (wLE) among agent set A if ℓ ∈ argmini∈A p(xi) wi . An agent b is called a weighted big earner (wBE) among agent set A if b ∈ argmaxi∈A p-1(xi) wi . The next lemma shows the importance of the wBE and wLE agents.

Lemma 2. An integral CE (x, p) is wpEF1 if and only if a wBE b does not wpEF1-envy a wLE ℓ.

Proof. (⇒) If (x, p) is wpEF1 then clearly b does not wpEF1-envy ℓ.

(⇐) Suppose b does not wpEF1-envy ℓ. Then the following shows that no agent i wpEF1-envies any agent h, implying that (x, p) must be wpEF1.

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

3 wEF1 and fPOAllocations 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.

Algorithm 1 Weighted Picking Sequence (WPS) Algorithm

Input: Agents N with identical disutility function d(·), set of

chores M s.t. d1 ≥ · · · ≥ dm

Output: An wEF1 allocation x

• 1: For each i ∈ N, xi ← ∅, si ← 0
• 2: for j = 1 to mdo
• 3: i ← argmink∈N sk wk ; ties broken in favour of smaller index agent
• 4: xi ←xi ∪ {j}, si ← si +1
• 5: return x

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 [Garg et al., 2023], (ii) EF1+fPO for two types of unweighted agents [Garg et al., 2023], (iii) wEF1+fPO for two agents [Wu et al., 2023].

Let N = N1 ⊔ N2 ⊔ N3 be a partition of the set of agents into three sets, called agent groups, each containing agents of the same type. Let di(·) be the disutility function of agents in group Ni, for i ∈ {1, 2, 3}. Note that agents in the same group can have different entitlements.

3.1 AlgorithmDescription

Through the execution of Algorithm 2 we let Mi denote the set of chores allocated to group Ni. Initially, all chores are allocated to a single group, N1, i.e., M1 = M, and M2 = M3 = ∅. At each point, the set of chores Mi is allocated to the group Ni by using the weighted picking sequence (WPS) procedure, Algorithm 1, described below.

WeightedPicking Sequence (WPS) Algorithm. TheWPS algorithm (Algorithm 1) takes as input a set of agents N of the same type, i.e., with identical disutility function d(·), and a set of chores M. The algorithm first sorts and relabels the m chores in non-increasing order of disutility, i.e., d1 ≥ d2 ≥ · · · ≥ dm. 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 si wi , where si 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 [Chakraborty et al., 2020; Wu et al., 2023]. Recently, [Wu et al., 2023] 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 Mi to group Ni 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 Mi gets updated and is re-allocated to the group Ni by using the WPS algorithm. We denote by WPS(N1,M1)∪WPS(N2,M2)∪WPS(N3,M3) the allocation resulting from allocating Mi to Ni using WPS for each i ∈ [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 pj = d1(j). At some point in the algorithm let the weighted big earner group Nβ be the group containing the weighted big earner (wBE) at the time. Likewise, let the weighted least earner group Nλ be the group containing the weighted least earner (wLE) at the time. We will call the group Nµ which contains neither as the weighted middle earner (wME) group. If β = λ then the allocation must already be wpEF1 by Lemma 2. Initially Nβ = N1. We maintain that for the majority of the algorithm Nβ = N1, i.e., the wBE is in N1, and transfer chores unilaterally from N1 to N2 and N3. We also aim to maintain that agents in N2 and N3 do not wpEF1-envy each other, and perform chore transfers between N2 and N3 to eliminate any arising wpEF1-envy.

Since N1 only loses chores, in at most m chore transfers fromN1 it must be that either the allocation becomes wpEF1 (hence wEF1), or the wBE ceases to be in N1. 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 Ni to Nh only if j belongs to the MPB set MPBh of agents in Nh, i.e., j ∈ Mi ∩MPBh.

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 ∈ Mβ ∩MPBλ 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β to Nλ, we check if a chore in Mµ ∩ MPBλ can be potentially transferred from Nµ to Nλ. If there is a chore j ∈ Mµ ∩ MPBλ s.t. after losing j the least weighted earning of an agent in Nµ is strictly larger than the weighted earning of the current wLE, then we transfer j from Nµ to Nλ (Line 17-18). Line 16 performs this check. If not, an Nµ to Nλ transfer is not allowed.

(Lines 19-21) If an Nµ to Nλ transfer is not allowed, we check if an Nβ to Nµ transfer is possible, i.e., there is a chore j ′ ∈ Mβ ∩MPBµ. If so, we make such a transfer.

(Lines 22-25) Otherwise, no chore can be transferred from Nβ to either Nµ or Nλ. In this case we lower the payments 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 x 1: Let N = N1 ⊔ N2 ⊔ N3 be the partition of the agents according to their type 2: Let di(·) denote the disutility function of agents in group Ni, for i ∈ {1, 2, 3} 3: M1 ←M,M2 ← ∅,M3 ← ∅ 4: x←WPS(N1,M1) ∪WPS(N2,M2) ∪WPS(N3,M3) 5: For each j ∈M, set pj ← d1(j) 6: while x is not wpEF1 do 7: b ← argmaxk∈Np-1(xk)/wk ▷ Weighted big earner 8: ℓ ← argmink∈Np(xk)/wk ▷Weighted least earner 9: β ← i ∈ [3] s.t. b ∈ Ni, ▷ Index of wBE group 10: λ ← i ∈ [3] s.t. ℓ ∈ Ni ▷ Index of wLE group 11: µ← i ∈ [3] \ {β, λ} ▷ Index of wME group ▷ Check for Nβ to Nλ chore transfer 12: if ∃j ∈ Mβ ∩MPBλ then 13: Mβ ←Mβ \ j, Mλ ←Mλ ∪ j 14: x ← ⋃i∈[3] WPS(Ni, Mi) ▷ Check for potential Nµ to Nλ chore transfer 15: else if |Mµ ∩MPBλ| > 0 then ▷ Check if Nµ to Nλ chore transfer is allowed 16: if ∃j ∈Mµ ∩MPBλ s.t. min k∈Nµ p(yk) wk > p(xℓ) wℓ for y = WPS(Nµ,Mµ \ j) then 17: Mµ ← Mµ \ j, Mλ ← Mλ ∪ j 18: x ← ⋃i∈[3] WPS(Ni, Mi) ▷ Nβ to Nµ chore transfer 19: else if ∃j ′ ∈Mβ ∩MPBµ then 20: Mβ ←Mβ \ j ′ , Mµ ←Mµ ∪ j ′ 21: x ← ⋃i∈[3] WPS(Ni, Mi) 22: else ▷ No chore can be transferred from Nβ ▷ Lower payments of chores in Mµ ∪Mλ 23: γ ← maxi∈{λ,µ},j∈Mβ αi di(j)/pj ; αi is the MPB ratio of an agent in group Ni 24: for j ∈ Mµ ∪Mλ do 25: pj ← γ · pj 26: else ▷ No chore can be transferred fromNβ or Nµ ▷ Lower payments of chores in Mλ 27: γ ← maxj∈Mβ∪Mµ αℓ dℓ(j)/pj 28: for j ∈ Mλ do 29: pj ← γ · pj 30: return x

of chores in Mµ and Mλ until a chore in Mβ becomes MPB for agents in Nµ or Nλ.

(Lines 26-29) Finally if there is no chore that can be transferred from Nβ or Nµ to Nλ, we lower the payments of chores in Mλ until a chore in Mβ or Mµ becomes MPB for agents in Nλ.

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 p(·) and M be a set of chores. Let x = WPS(N, M) be an allocation of M to N using the WPS algorithm, and y = WPS(N,M \ j), for a chore j ∈ M. Then we have:

• (i) For all i ∈ N, p(yi) ≤ p(xi).
• (ii) For all i ∈ N, p-1(yi) ≤ p-1(xi).
• (iii) For all i, h ∈ N, p(yi) wi ≥ p-1(xh) wh . In particular, p(yℓ) wℓ ≥ p-1(xb) wb , where agent ℓ has the least weighted disutility in y and agent b has the biggest weighted disutility up to one chore in x.

Lemma 4. Let N be a set of agents with the same disutility function p(·) and M be a set of chores. Let x = WPS(N, M) be an allocation of M to N using the WPS algorithm, and y = WPS(N,M ∪ j), for a chore j /∈ M. Then we have:

• (i) For all i ∈ N, p(yi) ≥ p(xi).
• (ii) For all i ∈ N, p-1(yi) ≥ p-1(xi).
• (iii) For all i, h ∈ N, p-1(yh) wh ≤ p(xi) wi . In particular, p-1(yb) wb ≤ p(xℓ) wℓ , where agent b has the biggest weighted disutility up to one chore in y and agent ℓ has the least weighted disutility in x.

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

Lemma 5. Throughout the execution of Algorithm 2, no chore transfer decreases the weighted earning of the wLE.

The following two lemmas analyze steps of Algorithm 2 which cause a group Nλ to cease being the wLE 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λ becoming the weighted middle earning group, then agents in Nλ do not wpEF1-envy agents in the new weighted least earner group in the resulting allocation.

To summarize, if a group Nλ ceases to be the wLE group, then either resulting allocation is wpEF1 or Nλ becomes the wME group and agents in Nλ do not wpEF1-envy agents in the new wLE group. These observations are important for proving the lemmas that follow.

We next consider steps of Algorithm 2 which cause a group Nβ to cease being the wBE group. We first show:

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 N1. Hence Nβ = N1 was the initial wBE group. We prove that this is the case almost throughout the execution of the algorithm. To this end, we show that Nβ (i.e. N1) loses a chore in every poly(m)-many steps.

Lemma 9. While the weighted big earner belongs to the group Nβ and the allocation is not wpEF1, Nβ must lose a chore in poly(m) steps.

Note that N1 has m chores to begin with (i.e. always |M1| ≤ m), and Algorithm 2 never transfers a chore to N1. Lemma 9 therefore implies that in poly(m) steps either the allocation is wpEF1 or N1 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 N1 stops being the wBE 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. Due to space constraints, we defer missing proofs to the full version of our paper [Garg et al., 2024].

4 wEF1+fPO for Two-Chore-Type 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 [Aziz et al., 2023], who showed that EF1+fPO allocations can be computed in polynomial time for two chore type instances with unweighted agents.

Theorem2. 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 type instance. We note that Algorithm 3 is also an alternative algorithm to that of [Aziz et al., 2023] for computing an EF1+PO allocation.

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

4.1 AlgorithmDescription

We first sort and re-label the agents in non-decreasing order of diA/diB, i.e., for i < j, diA diB ≤ djA djB . Roughly speaking, agents with a smaller index prefer to do A-chores over Bchores, 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 pX = diX for X ∈ {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 ℓA be Algorithm 3 wEF1+fPO for two chore types instances

Input: Two chore type instance (N,W,M,D) Output: An integral wEF1 and fPO allocation x 1: LetM = A⊔B be a partition of chores according to type 2: for i = 1 to n do 3: xi ←M, xh ← ∅ for h ̸= i 4: Set payments as pA = diA and pB = diB 5: while (x, p) is not wpEF1 do ▷ L is the set of global wLE agents 6: L ← {k : k ∈ argminh∈[n] p(xh) wh } ▷ Set ℓA asmax. indexwLE in [i-1], max∅ =∞ 7: ℓA ← max(L ∩ [i - 1]) ▷ Set ℓB as min. index wLE in [n] \ [i], min ∅ = 0 8: ℓB ← min(L ∩ [n] \ [i]) 9: if ℓA < i and xi ∩ A ̸= ∅ then ▷ Transfer A-chore from i to ℓA 10: Let a ∈ xi ∩ A be an A-chore in xi 11: xi ← xi \ a, xℓA ← xℓA ∪ a 12: else if ℓB > i and xi ∩ B ̸= ∅ then ▷ Transfer B-chore from i to ℓB 13: Let b ∈ xi ∩ B be a B-chore in xi 14: xi ← xi \ b, xℓB ← xℓB ∪ b 15: else: Break ▷ Failure in Phase i 16: if (x, p) is wpEF1 then 17: return x

the index of a wLE agent among agents 1 through (i - 1) if such an agent exists (otherwise let ℓA = ∞), with ties broken in favour of larger index (Line 7). Similarly, let ℓB be the index of a wLE agent among agents (i + 1) through n if such an agent exists (otherwise let ℓ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 ℓA < i and xi ∩A ̸= ∅, 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 ℓA. Thus, we transfer this A-chore from i to ℓA.

(Lines 12-14) If ℓB > i and xi ∩ B ̸= ∅, then there is a wLE agent to the right of pivot agent i and i has a B-chore which is on MPB for ℓB. Thus, we transfer this B-chore from i to ℓ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 done 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: Overview

We now provide an overview of the proof of 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.

We then argue that Algorithm 3 eventually finds a wpEF1 allocation. To this end, 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.

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 aB-fail, then agent (i+1) cannot face an A-fail.

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 ∈ [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∗ ∈ [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. 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.

To prove the crucial Lemma 13, 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] \ [i]. Due to space constraints, we defer missing proofs to the full version of our paper [Garg et al., 2024].

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 [Wu et al., 2023] 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.