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
Instance EF1 + fPO wEF1 + fPO General Additive ? ? Two agents ✓[Aziz et al., 2019] ✓[Wu et al., 2023] Three agents ✓[Garg et al., 2023] ✓Theorem 1 Two-agent-types ✓[Garg et al., 2023] ✓Theorem 1 Three-agent-types ✓Theorem 1 ✓Theorem 1 Two-chore-types ✓[Aziz et al., 2023] ✓Theorem 2 Bivalued ✓[Garg et al., 2022; Ebadian et al., 2022] ✓[Wu et al., 2023]
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.
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 teach-ing 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).
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 1 Chores have attached payments while goods have prices.
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.
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∈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∈N , where d i : 2 M → R ≥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 ∈ N and S ⊆ M , d i (S) = j∈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
• k-chore-type instance if there are k types of chores. That is, the set of chores can be partitioned as
where each set M ℓ consists of copies of the same chore.
An integral allocation x = (x 1 , x 2 , . . . , x n ) is a partition of the chores into n bundles, where agent i receives bundle x i ⊆ M and gets disutility d i (x i ). In a fractional allocation x ∈ [0, 1] n×m , chores are divisible and x ij ∈ [0, 1] denotes the fraction of chore j given to agent i. Here d i (x i ) = j∈M d i (j)•x ij . 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 , d i (x i \ j) ≤ d i (x h ) for some j ∈ x i .
2. Weighted envy-free up to one chore (wEF1) if for all i, h ∈ N , di(xi\j) wi ≤ di(x h ) w h for some j ∈ x i . 3. Pareto-optimal if there is no allocation y that dominates
x. An allocation y dominates an allocation x if for all i ∈ N , d i (y i ) ≤ d i (x i ), and there exists h ∈ N such that
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 = (p 1 , . . . , p m ) with the chores. Each agent i aims to earn a desired minimum payment of e i ≥ 0 by performing chores in exchange for payment. In a (fractional) allocation x with payments p, the earning of agent i is p(x i ) = j∈M p j • x ij . For each agent i, we define the pain-per-buck ratio α ij of chore j as α ij = d i (j)/p j and the minimum-pain-per-buck (MPB) ratio as α i = min j∈M α ij . Further, we let MPB i = {j ∈ M | d i (j)/p j = α 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 x ij = 1, i.e., all chores are completely allocated, (ii) for all i ∈ N , p(x i ) = e i , i.e., each agent receives her minimum payment, and (iii) for all i ∈ N , x i ⊆ MPB i , 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 (x i ) := min j∈xi p(x i \ j) denote the payment agent i receives from x i 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
w h . 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 ℓ ∈ argmin i∈A p(xi) wi . An agent b is called a weighted big earner (wBE) among agent set A if b ∈ argmax i∈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 ℓ.
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. d 1 ≥ • • • ≥ d m Output: An wEF1 allocation x 1: For each i ∈ N , x i ← ∅, s i ← 0 2: for j = 1 to m do 3: i ← arg min k∈N s k w k ; ties broken in favour of smaller index agent 4:
x i ← x i ∪ {j}, s i ← s i + 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 = N 1 ⊔ N 2 ⊔ 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 (•) be the disutility function of agents in group N i , for i ∈ {1, 2, 3}. Note that agents in the same group can have different entitlements.
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 = ∅. 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(•), and a set of chores M . The algorithm first sorts and relabels the m chores in non-increasing order of disutility, i.e.,
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 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 [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 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
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 β 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 β = N 1 . We maintain that for the majority of the algorithm N β = 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.
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 MPB h of agents in N h , i.e., j ∈ M i ∩ 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 ∈ 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 = N 1 ⊔ N 2 ⊔ N 3 be the partition of the agents according to their type 2: Let d i (•) denote the disutility function of agents in group
For each j ∈ M , set p j ← d 1 (j) 6: while x is not wpEF1 do
▷ Index of wBE group 10: (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 λ .
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 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: Let M = A⊔B be a partition of chores according to type 2: for i = 1 to n do 3:
x
Set payments as p A = d iA and p B = d iB 5:
while (x, p) is not wpEF1 do ▷ L is the set of global wLE agents 6:
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 x i ∩ 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 x i ∩ 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.
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 a B-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].
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.
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence