Weighted Maxmin Fair Share Allocation of Indivisible Chores

1 Introduction

We consider fair allocation of indivisible chores when agents have asymmetric shares. In contrast to the case of goods for which agents have positive value, chores are disliked by agents and they have negative values for them. The fairness concept we focus on is the maxmin share (MMS) fairness which was designed for allocation of indivisible items. MMS is based on the thought experiment that if the items are partitioned into bundles and an agent would always get the least preferred bundle of items, what is the best way she can partition the items. The value of such a bundle is the maxmin share of the agent. An allocation is deemed MMS fair if each agent gets her required share.

Maxmin share fairness was proposed by [Budish, 2011] as a fairness concept for allocation of indivisible items. It is a relaxation of proportionality fairness that requires each of the n agents should get a value that is at least 1/n of the total value she has for the set of all items. When items are divisible, maxmin share fairness coincides with proportionality. Maxmin share fairness is a weaker concept when items are indivisible. It was conjectured that a maxmin fair allocation always exists but [Procaccia and Wang, 2014] identified a counter-example. Since the work of [Procaccia and Wang, 2014], there are several papers on algorithms that find an approximate MMS allocation [Amanatidis et al., 2015;

Barman and Murthy, 2017; Ghodsi et al., 2018; Aziz et al., 2017]. All these works make a typical assumption that agents are symmetric and should be treated in a similar manner.

[Farhadi et al., 2017] were the first to consider MMS fairness for the case where indivisible goods are allocated and the agents are not symmetric because they may have different entitlement share of the goods. Ideally, an agent would expect to get a share of the total value that is proportional to her entitlement. However, when items are indivisible, MMS fairness needs to be suitably generalized to the cater for asymmetric entitlement shares. Farhadi et al. generalized MMS fairness to that of the more general MMS concept as weighted MMS (WMMS) that caters for entitlements. They devised a simple ordinal (that only used the qualitative ranking information of items) algorithm that ensures an n-approximation guarantee for WMMS where each agent's allocation is at least 1/n of her value in a WMMS allocation. Beyond the results for goods [Farhadi et al., 2017; Farhadi et al., 2019], not much is known about chore allocation when the agents are asymmetric despite the recent active research in fair allocation of goods and chores. Furthermore, it is not clear whether the results for goods from one setting could carry over the other [Aziz, 2016].

In this paper, we focus on the fair allocation of chores rather than goods for asymmetric agents. In the case of chores, agents do not have entitlements but relative shares. If an agent has a higher share, she is expected to take a higher load of the chores. Treating agents asymmetrically may be a requirement for several reasons. For example, countries with a larger population and CO2 emission may be liable to undertake more responsibility to clean up the environment. In this paper, the central research question we examine is the following one. When indivisible chores are to be allocated among agents with asymmetric shares, for what approximation factor do approximately WMMS fair allocations exist and how efficiently can they be computed?

Our contributions are as follows. We consider a model of allocation of chores in which agents have relative shares as compared to entitlements. Different to the case of symmetric agents, we first prove that even with only two agents, no algorithm can simultaneously guarantee each agent's value to be higher than 4 3 of her weighted maxmin share. Moreover, we show that many greedy algorithms widely used in the literature, including [Farhadi et al., 2017] and [Aziz et al., 2017], may have arbitrarily bad performance.

Then we design a polynomial-time algorithm which provides a 4-approximation to the minimal relaxation of WMMS value (OWMMS) under which a WMMS allocation exists. To present this algorithm, we first study a special case when all agents have an identical valuation. The algorithm combines (1) the use of a greedy algorithm for the case of identical valuations and (2) linear programming and rounding techniques.

Finally, we study two restricted cases: a two-agent setting and a binary valuation setting. For the two-agent case, we present a variant of divide-and-choose protocol which ensures each agent's value is at least 3 2 of her weighted maxmin share; For binary valuations, we show that a WMMS allocation exists and can be efficiently computed. For asymmetric agents and indivisible items, this is the first algorithmic result for binary valuations.

2 RelatedWork

The fair allocation problem has been extensively studied in the cake cutting literature [Dubins and Spanier, 1961; Stromquist, 1980; Alon, 1987; Brams and Taylor, 1995; Brams and Taylor, 1996; Robertson and Webb, 1998; Aziz andMackenzie, 2016]. In this line of work, researchers study how to fairly allocate a divisible item (e.g., cake) among a number of agents. Solution concepts such as envy-freeness and proportionality are prominent criteria for fairness. In the context of divisible goods, researchers have extended results for the case of equal entitlements to those of unequal entitlements (see e.g., [Cseh and Fleiner, 2018]).

As for MMS fairness, it is already known that even for additive valuations, there exists an instance such that no allocation can simultaneously guarantee each agent receives at least her MMS [Kurokawa et al., 2018]. But approximate MMS can be efficiently computed; see [Barman and Murthy, 2017; Ghodsi et al., 2018; Kurokawa et al., 2018]. Computing WMMS shares is an NP-hard problem for both goods and for chores even for the case of 2 agents and for equal shares. The statement can be derived via a reduction from the integer partition problem [Garey and Johnson, 1979].

Most of the work on fair allocation of items is for the case of goods although recently, fair allocation of chores [Aziz et al., 2017] or combinations of goods and chores [Aziz et al., 2018] has received attention as well. It is shown by [Aziz et al., 2017] that MMS allocations for chores do not always exist but can be 2-approximated by a simple round-robin algorithm. [Aziz et al., 2017] also presented a PTAS for relaxation of MMS called optimal MMS. [Barman and Murthy, 2017] presented an improved approximation algorithm for MMS allocation of chores. Fair allocation of indivisible goods and asymmetric agents has also been studied [Farhadi et al., 2017; Farhadi et al., 2019]. We take a similar approach and study the chore allocation problem when the agents are not symmetric. [Babaioff et al., 2017] considered the allocation of indivisible goods where agents have different entitlements. One of the concepts that they propose is called ℓ-out-of-d MMS that can also apply to agents having ordinal preferences over bundles of chores. However, the paper focusses on results for goods.

3 Preliminaries

We begin by presenting our setting formally and discussing fairness concepts as well as some basic notations in the paper.

3.1 Setting

Let N = {1, 2, · · · , n} be a set of n agents, and M = {1, 2, · · · ,m} be a set of m indivisible items. In this work, we always use i ∈ N and j ∈ M to indicate an agent and an item, separately. Each agent has a valuation function Vi : 2M → R. Denote by Vij = Vi({j}). We assume that items are chores to every agent, i.e., Vij ≤ 0 for all j ∈ M and the valuations are additive, i.e., for any S ⊆ M, Vi(S) = ∑j∈S Vij. Without loss of generality and just for ease of presentation, throughout this paper except Section 6.2, it is assumed that all of the valuations are normalized, i.e. Vi(∅) = 0 and Vi(M) = -1.

In this work, we consider the case when agents are asymmetric. Particularly, every agent has a share for the chores, namely si ∈ (0, 1]. The shares add up to 1, i.e., ∑i∈N si = 1. Letting V = (V1, · · · , Vn) and s = (s1, · · · , sn), we use I = (N,M, s, V ) to denote a chore allocation instance and I = (N,M, s, V ) when all agents have the identical valuation V . Note that when all agents have identical valuation V , V ({j}) is simplified as V j for any j ∈ M. Let Π(M) be the set of all n-partitions of the items. A generic allocation will be denoted by X = 〈X1, . . . , Xn〉 where Xi is the bundle of agent i.

3.2 WMMS Fairness

Before presenting the WMMS fairness concept that takes into account the shares of the agents, we first present the standard MMS fairness concept that assumes the shares of the agents are equal. For symmetric agents, the classical maxmin share (MMS) of an agent i with valuation Vi is defined as

Intuitively, when allocating items to n agents, each agent should get an allocation with a value that is 1/n of the total value they have for all the items. Since the items are not divisible, this proportionality requirement may be not achievable for the agents. In view of this, MMSi can be viewed as a relaxed lower bound on the value that agent i hopes for if she has the chance to partition the items into n bundles and every other agent adversarially chooses a bundle before i. Next, we generalize the classical MMS notion to the setting with asymmetric agents.

Definition 1 (WeightedMMS) Given any chore allocation instance I = (N,M, s, V ), for every agent i ∈ N, the weighted maxmin share (WMMS) value of i is defined as:

Any partition achieves WMMSi(I) is called a P-i partition.

When the instance I is clear from the context, we may use WMMSi for short. The definition above for WMMS fairness is exactly the same as that of WMMS as formalized by

[Farhadi et al., 2017] for the case of goods except that the entitlement ei of an agent i is replaced by her share si. As mentioned in the introduction, whereas a higher entitlement for goods is desirable for an agent, a higher share for chores is undesirable for the agent.

We call an allocation WMMS if the value of the allocation to each agent i is worth at least WMMSi to her. Similarly, an allocation is called α-WMMS, if the total value of items allocated to each agent i is at least αWMMSi for α ≥ 1.

Note that when all shares are equal, WMMS coincides with MMS fairness so it is a proper generalization of MMS. Secondly, we spell out an insight that also provides justification for the WMMS concept that was defined by [Farhadi et al., 2017]. We note that when the items are divisible, then WMMSi = siVi(M). Hence, for divisible chores, WMMS fairness also implies a natural generalization of proportionality that takes into account the shares of agents. We call the latter requirement as weighted proportionality.

In the following, we define some more notation that will be used in the paper. Given a chore allocation instance I = (N,M, s, V ), for any agent i and any partition X = 〈Xi〉i∈N, let WI i (X) = mink∈N Vi(Xk) sk . That is, WI i (X) is the unfairness degree of allocation X to i. Let Wi(I) = max〈X1,...,Xn〉∈Π(M) WI i (X). Thus Wi(I) is the smallest degree of unfairness and WMMSi(I) = siWi(I). Moreover, we have the following simple properties.

Lemma 1 Given any instance I = (N,M, s, V ), for any i ∈ N, Wi(I) ≤ -1, and WMMSi(I) ≤ -si.

Proof: Note that for any agent i and any allocation 〈Xi〉i∈N, ∑k∈N Vi(Xk) sk · sk = ∑k∈N Vi(Xk) = -1, which is the weighted arithmetic mean of the terms Vi(Xk) sk , with weights sk (whose sum is 1). As the mean equals -1, the smallest must be at most -1 and Wi(I) = mink∈N Vi(Xk) sk ≤ -1. □

Next we show a simple algorithm, Naive, which returns an n-WMMS allocation. Algorithm Naive produces an allocation that allocates all of the items to a single agent who has the highest share (ties are broken arbitrarily).

Lemma 2 Let I = (N,M, s, V ) be any chore allocation instance and 〈Xi〉i∈N be the output of Algorithm Naive. Then Vi(Xi) ≥ nWMMSi(I) for any i ∈ N.

Proof: Let i∗ be the agent who has the largest share, thus si∗ ≥ 1n . It is easy to see that for any agent i ̸= i∗ , Vi(Xi) = 0, which is trivially at least as large as nWMMSi(I). By Lemma 1, WMMSi∗(I) ≤ -si∗ ≤ - 1n . Accordingly, Vi∗ (M) ≥ nWMMSi∗ (I). □

4 Optimal WMMS Fairness

It is well known that for symmetric agents, no matter the items are goods or chores, an MMS allocation always exists for the 2-agent case. But for asymmetric agents, we note that an exact WMMS allocation may not exist even when there are only two agents. Indeed, by the following lemma, we see that the lower bound of the problem is at least 4 3 , which means that there is no allocation that can guarantee each agent's value to be greater than 43 WMMSi(I) for every i ∈ N.

Lemma 3 In the chore allocation problem, any algorithm has an approximation ratio of at least 4 3 for WMMS fairness.

Proof: In the following we construct an instance I = (N,M, s, V ) with N = {1, 2}, M = {1, 2} and the shares and valuations are shown in Table 1.

We first note that for agent 1, the unique P-1 partition is X = 〈X1,X2〉 with X1 = {1} and X2 = {2}, since W I 1 (X) = min { - 3 4 34 , - 14 14 } = -1, which is the largest among all possible allocations. Accordingly, WMMS1(I) = 34 × (-1) = - 3 4 . For agent 2, to maximize WI 2 , the only way is to set X′ = 〈X′1 ,X′2 〉 with X′1 = {1, 2} and X′2 = ∅, since WI 2 (X′ ) = min { -1 34 , 014 } = - 43 , which is the largest among all possible allocations. Accordingly, WMMS2(I) = 1 4 × (- 43 ) = - 13 .

However, X is bad to agent 2, since V2(X2) = - 12 < WMMS2(I) and X′ is bad to agent 1, since V1(X′1 ) = -1 < WMMS1(I). Therefore the best tradeoff to satisfy the two agents simultaneously would be allocation X′ , since V2(X2) = 3 2 WMMS2(I) and V1(X′1 ) = 4 3 WMMS1(I). Indeed, we need to take all possible allocations into consideration, but it is easy to see that all other allocations can only be worse.

Thus, no algorithm could provide an allocation with each agent i's value being strictly larger than 43 WMMSi(I), which finishes the proof of Lemma 3. □

Accordingly, it is natural to consider a relaxed version of WMMS, optimal WMMS (OWMMS) fairness, which is similar to the one introduced in [Aziz et al., 2017].

Definition 2 (Optimal WMMS) Let I = (N,M, s, V ) be a chore allocation instance. The optimal WMMS (OWMMS) ratio α∗ is defined as the minimal α ∈ [1,∞) for which an α-WMMS allocation always exists. Let OWMMSi(I) = α∗WMMSi for any i ∈ N. A partition X = 〈X1, . . . ,Xn〉 is called an OWMMS allocation, if Vi(Xi) ≥ OWMMSi(I) for all i ∈ N.

It is easy to see that WMMSi(I) ≥ OWMMSi(I) for any instance I and any agent i. For any partition X = 〈X1, . . . ,Xn〉, if Vi(Xi) ≥ c · OWMMSi(I) for all i ∈ N, then X is called c-approximation to the OWMMS allocation.

5 Approximation Algorithms

For the case of goods allocation, the greedy round robin algorithm considered by [Farhadi et al., 2017] gives the best guarantee (of n-approximation for goods). Interestingly, the same algorithm was proved to provide a 2-approximation for MMS allocation of chores when agents are symmetric [Aziz et al., 2017]. However, when agents have different shares, such an algorithm can be arbitrarily poor. Due to space limit, we provide the bad example in the full version, where we also show that natural attempts to 'fix' the bad performance of the greedy algorithm do not help.

In the following, we give our polynomial-time (4 + ϵ)- approximation algorithm. That is, for any ϵ > 0, it returns an allocation 〈Xi〉i∈N such that for any agent i, Vi(Xi) ≥ (4+ϵ)OWMMSi. In order to present the main algorithm, we first present a polynomial-time algorithm which guarantees each agent i's value to be at least 2WMMSi, when all of the agents have an identical valuation.

5.1 Identical Valuation

When all agents have an identical valuation, we show the algorithm, EgalGreedy defined in Algorithm 1, is a 2approximation to an exact WMMS allocation.

Algorithm 1 EgalGreedy - An Algorithm for Identical Valuations

Require: Chore allocation instance (N,M, s, V ) Ensure: Allocation X = 〈X1, . . . ,Xn〉.

• 1: Initially, Xi = ∅ for all i ∈ N.
• 2: Order all chores from the lowest value to the highest value such that V 1 ≤ V 2 ≤ · · · ≤ V m.
• 3: for j = 1 to mdo
• 4: i∗ ∈ argmax i∈N V (Xi ∪ {j}) si ;
• 5: Xi∗ =Xi∗ ∪ {j}.
• 6: return Allocation X.

The next lemma relies on a connection to the parallel processors scheduling problem. In this problem, there is a set of jobs and a set of processors. Each job has to be processed exactly once on exactly one processor. Processors may have different speeds [Gonzalez et al., 1977; Friesen, 1987]. The problem specifies the time required to process a given job on a given machine. Typically, the goal of scheduling problems is to find an assignment of the jobs such that the longest finishing time (i.e., makespan) is minimized. A detailed survey of this line of work can be found in [Pinedo, 2016]. Due to space limit, we prove Lemma 4 in the full version.

Lemma 4 For any chore allocation instance I = (N,M, s, V ), where all agents have the identical valuation V , let 〈Xi〉i∈N be the allocation outputted by EgalGreedy. We have V (Xi) ≥ 2WMMSi(I) for any i ∈ N.

One may suspect that a natural generalization of EgalGreedy to the case that agents have different valuations may work well. Unfortunately, in the full version, we provide an example that such an algorithm cannot have any constant approximation ratio.

5.2 General Valuations

Now we are ready to study the general case when agents may have different valuations. For any chore allocation instance I = (N,M, s, V ), let variable α represent the WMMS ratio, and variable xij ∈ {0, 1} represent whether agent i gets item j. Let x = (xij)i∈N,j∈M. Then the problem of computing its OWMMS ratio and an OWMMS allocation can be formalized as the following integer program.

To solve IP, in what follows, we first prove a key technical lemma by using the rounding technique introduced by [Lenstra et al., 1990], which gives us the tool to round a fractional assignment to an integer assignment.

Lemma 5 Let (N,M, s, V ) be any chore allocation instance, w = (w1,w2, · · · ,wn) ∈ (R-)N , and t = (t1, t2, · · · , tn) ∈ (R-)N . Denote by Mi = {j ∈ M|Vij ≥ ti} and Nj = {i ∈ N|j ∈ Mi}. If the following linear program

has a feasible solution, then any extreme point ˜x of this polytope (defining the solution space) can be rounded to a feasible solution ¯x of the integer program

Proof: Let ˜x be an extreme point of the polytope defined by P. Then ˜x contains at most m + n nonzero variables due to the number of constraints in P. We construct a bipartite graph via ˜x, G = (N,M,E), where N is the set of agents, M is the set of chores and E = {(i, j)|˜xij > 0, i ∈ N, j ∈ M}. Using the same argument with the proof of Theorem 1 in [Lenstra et al., 1990], we know that G is a pseudoforest, i.e., each connected component of G is a tree or a tree plus one additional edge.

Next, we round ˜x to ¯x. In any connected component C of G, whenever there is a chore j whose degree is 1, then it must be that for some i, ˜xij = 1. Then set ¯xij = 1 and delete this chore from C. Denote by C ′ the remained graph. Note that in C ′ , any remaining chore has a degree at least 2. Therefore C ′ must contain a matching which covers all chores, due to the fact that C ′ is a tree or a tree plus one additional edge. According to this matching, if (i, j) is matched, set ¯xij = 1; otherwise, set ¯xij to be 0.

Next, it suffices to verify that ¯x is a feasible solution of P ′ . For each chore j, ¯x assigns it to exactly one agent. Thus, ∑i∈Nj ¯xij = 1 for any j ∈ M. For each agent i ∈ N, there is at most 1 chore j such that ˜xij is increased to 1. Since 0 ≥ Vij ≥ ti,

which completes the proof of Lemma 5.

□

Note that, solving the optimal α for integer program IP is equivalent to finding the minimum value of α such that IP has a feasible integer solution x. However, P is not the relaxation of IP since in P, there is not a variable xij for which Vij < ti. Equivalently, we can add these variables to P and set them to zero. In the following, we discuss the relationship between the solutions of IP, P and P ′ .

Recall that α∗ is the OWMMS ratio, which is also the optimal value of IP. Let

Note that c∗ always exists as c = n is always feasible by Algorithm Naive. Moreover, although P is not the relaxation of IP, c∗ is still a lower bound of α∗ .

Lemma 6 α∗ ≥ c∗ .

Lemma 6 shows that to approximate α∗ , it suffices to find a feasible solution of IP whose value is a good approximation to c∗ . Next, we show that a feasible solution of P ′ is naturally a feasible solution of IP.

Lemma 7 Let c ∈ R+0 . If x is a feasible solution of P ′ with ti = wi = cWMMSi(I) for all i ∈ N, then (x, 2c) is a feasible solution of IP.

Both Lemmas 6 and 7 are proved in the full version. Before we show our main algorithm, let us discuss the following intuitive procedure. First, compute c∗ and its corresponding fractional allocation ˜x. Then use Lemma 5 to round ˜x to an integer solution ¯x. By Lemma 7, ¯x is also a feasible solution of IP. Let X = 〈Xi〉i∈N be the final allocation, where Xi = {j ∈ M|¯xij = 1} for every i ∈ N. Thus,

where the first inequality is by Lemma 5 and the second inequality is by Lemma 6. That is, X is a 2-approximation to the optimal WMMS allocation.

However, there are two computational issues with respect to the procedure above: (1) The computation of WMMSi(I) may need exponential time 1 ; (2) Even if we know all the WMMSi(I)'s, there is a problem of computing c∗ .

To resolve (1), we use Algorithm EgalGreedy to compute an approximate value WMMS′i for each WMMSi(I), where WMMS′i ≥ 2WMMSi(I). Then we replace all WMMSi(I) byWMMS′i in above procedure.

To resolve (2), we use binary search to find a near optimal value of c∗ . Initially, we first use Algorithm Naive to get an upper bound n of α and 1 is a trivial lower bound. Let δ > 0 be the desired precision. Denote by u and l the current upper and lower bounds, respectively. Set c = u+l 2 and wi = ti = cWMMS′i , and check if P has a feasible solution. If P has a feasible solution, reset u to be u+l 2 ; Otherwise reset l = u+l 2 . Repeat this process until u - l ≤ δ.

1 The computation of WMMSi is NP-hard, even when n = 2 and s1 = s2 = 1 2 , via a reduction from the Integer Partition Problem.

We formally describe the algorithm described above as Algorithm 2, denoted by LinPro.

Algorithm 2 LinPro - An Algorithm for General Valuations

Require: Chore allocation instance I = (N,M, s, V ) and ϵ > 0. Ensure: Allocation X = 〈X1, . . . ,Xn〉

• 1: Initially, Xi = ∅ for all i ∈ N.
• 2: For each i ∈ N, run Algorithm EgalGreedy on instance I and obtain allocation Xi = 〈Xi1,Xi2, . . . ,Xin〉.
• 3: Set WMMS′i = Vi(Xi i ) for all i ∈ N.
• 4: Let u = n and l = 1. % n is the upper bound by Naive.
• 5: while u- l > ϵ4 do
• 6: Set c = u+l 2 .
• 7: Check if P has a feasible solution by setting wi = ti = cWMMS′i for all i ∈ N.
• 8: if P has a feasible solution then
• 9: Reset u = c.
• 10: else
• 11: Reset l = c.
• 12: Set wi = ti = uWMMS′i for all i ∈ N and compute an extreme point ˜x of P.
• 13: Use Lemma 5 to round ˜x to ¯x.
• 14: Set Xi = {j ∈ M|¯xij = 1} for all i ∈ N.
• 15: return Allocation X.

Theorem 1 Given any chore allocation instance I = (N,M, s, V ) with α∗ being its OWMMS ratio. For any ϵ > 0, Algorithm LinPro runs in polynomial time (for any number of agents) and returns an allocation 〈Xi〉i∈N such that for any agent i, Vi(Xi) ≥ (4 + ϵ)OWMMSi(I).

Proof: By Lemma 7, X is a feasible solution of IP. At Step 12, as l ≤ c∗ ≤ u and u - l ≤ ϵ4 , we have u ≤ c∗ + ϵ4 . Thus,

where the first inequality is by Lemma 5, the second inequality is by Lemma 4, and the last inequality is by Lemma 6.

As LinPro requires us to run EgalGreedy and solve at most O(log( nϵ )) numbers of (polynomial-sized) linear program, LinPro runs in polynomial time. □

Note that the role of EgalGreedy in LinPro can be replaced by other (polynomial-time) approximation algorithms (such the PTAS in [Hochbaum and Shmoys, 1988]) and the approximation ratio (Lemma 4) is improved accordingly.

6 Restricted Cases

In this section, we consider two important restricted cases: (1) two agents and (2) all agents have binary valuations (in which case agents have value 0 or -1 for each item).

6.1 WMMS for Two Agents

Given any instance I = (N,M, s, V ) with N = {1, 2}, we prove that it is always possible to guarantee each agent i's value to be at least 32 WMMSi(I). Thus, by Lemma 3, the OWMMS ratio α∗ for the 2-agent case is within [ 43 , 32 ].

Divide-and-choose algorithms are widely studied in the literature, especially for the case of two agents. Roughly speaking, the algorithm starts by letting one of the agents divide the whole items (either goods or chores) into two bundles, and the other agent chooses one from the two bundles. Such an algorithm gives an exact MMS allocation for symmetric agents and a 2-WMMS allocation for asymmetric agents (the agent with smaller entitlement divides and the other agent chooses) when the items are goods. However, it is not hard to see that generic divide-and-choose algorithms could be arbitrarily bad when the items are chores.

In the following, we show that with some modification, a divide-and-choose style algorithm, DivCho (defined in Algorithm 3), works well and guarantees each agent i's value to be at least 32 WMMSi. Without loss of generality, assume s1 ≤ s2.

Algorithm 3 DivCho -An Algorithm for the 2-Agent Case

Require: Chore allocation instance I = (N,M, s, V ) with N = {1, 2}.

Ensure: Allocation X = 〈X1,X2〉.

• 1: Initially, set Xi = ∅ for both i ∈ N.
• 2: If s1 ≤ 1 3 and s2 ≥ 23 , set X1 = ∅ and X2 = M. Go to Step 5.
• 3: Let agent 2 partition M into A1 and A2 according to a P-2 partition with respect to WMMS2(I).
• 4: Let agent 1 select his favorite bundle fromA1 and A2. Denote by X1 the one chosen by agent 1 and by X2 the one left for Agent 2.
• 5: X = 〈X1,X2〉.
• 6: return Allocation X.

Theorem 2 Let I = (N,M, s, V ) with N = {1, 2}, and X = 〈X1,X2〉 be the output of Algorithm DivCho on I. Then, for any agent i ∈ N, Vi(Xi) ≥ 3 2 WMMSi(I) ≥ 3 2 OWMMSi(I).

Proof: If s1 ≤ 1 3 and s2 ≥ 23 , Algorithm DivCho allocates all chores to agent 2. Thus V1(X1) = 0 and V2(X2) = -1, where agent 1 is trivially satisfied as V1(X1) ≥ 3 2 WMMS1(I). By Lemma 1, we have WMMS2(I) ≤ -s2 ≤ - 2 3 . Accordingly, V2(X2) ≥ 32 WMMS2(I).

As we assume that s2 ≥ s1, our last case is to consider 12 ≤ s2 ≤ 23 . By the definition of WMMS2(I) = s2 ·min{ V2(A1) s1 , V2(A2) s2 }, V2(A1) ≥ V2(A2) ≥WMMS2(I). As a result, no matter which allocation agent 2 eventually receives after the divide-and-choose procedure, the value of the allocation will always be at least as much as WMMS2. For agent 1, since V (X1) + V (X2) = -1 by assumption and he selects his favorite allocation X1, V1(X1) ≥ - 12 . By Lemma 1 and the fact that s1 > 13 , WMMS1(I) < - 13 . Therefore, V1(X1) > 32 WMMS1(I). □

6.2 Binary Valuations

In this section, we study the case with any number of agents, but every agent's valuation is binary: Vij ∈ {0,-1} for all i ∈ N and j ∈ M. Note that, throughout this section, we do not impose normalization for ease of exposition. As will be clear later, for this case, we show that it is always possible to guarantee each agent i's value to be at least WMMSi, i.e., the optimal WMMS ratio for binary valuation case is exactly 1.

We first prove the following lemma.

Lemma 8 Let I = (N,M, s, V ) be a chore allocation instance where all agents have an identical valuation V . If V is uniform, (i.e. V (S) = -|S| for any S ⊆ M), an exact WMMS allocation can be computed in polynomial time.

Proof: It suffices to show if V is uniform, Algorithm EgalGreedy returns an exact WMMS allocation. Suppose X = 〈Xi〉i∈N is the output of EgalGreedy with respect to V . Recall W(X) = mink∈N V (Xk) sk = mink∈N -|Xk | sk . Let S = {k ∈ N| -|Xk| sk = W(X)} be the set of indices where the minimum is obtained. In the following we show W = W(X). Note that S ̸= ∅. If X is not an optimal partition, then there is a partition X∗ such that W(X∗ ) > W(X).

Thus, every k ∈ S, Xk has to contain a smaller number of chores compared with X∗ k . Accordingly, for some t ∈ N\S, Xt has to contain more chores than X∗ t , i.e., V (X∗ t ) ≤ -|Xt| - 1. If -|Xt|-1 st ≤ W(X), W(X∗ ) cannot be larger than W(X). Thus, -|Xt|-1 st > W(X). But this is a contradiction with the fact that EgalGreedy always allocates greedily, (i.e., Step 4 of EgalGreedy), since the last chore cannot be allocated to Xk for k ∈ S instead of Xt. That is W = W(X).

Therefore, V (Xi) si ≥ W(X) = W and V (Xi) ≥ siW = WMMSi for any i ∈ N, which competes the proof. □

Thus, by allocating all chores for which some agent has zero value to one such agent, we are left with only the chores for which all agents have value -1. As the modified instance if uniform, by Lemma 8, we have the following theorem.

Theorem 3 For any binary valuation case, a WMMS allocation exists and can be found efficiently.

7 Conclusions

We initiated the study on chore allocation with asymmetric agents. We show that many widely studied greedy algorithms in the literature performs badly and even for the 2-agent case an exact WMMS allocation may not exist. We then presented a constant approximation polynomial time algorithm for OWMMS allocations, and several algorithmic results for the case of identical utilities, binary utilities, and for 2 agents. Finding a stronger lower bound for WMMS allocations for any number of agents remains an open problem.

Acknowledgements

This work is partially supported by NSF CAREER Award No. 1553385. Haris Aziz is supported by a Scientia Fellowship.