Improved Approximation of Weighted MMS Fairness for Indivisible Chores

1 Introduction

The task in fair job scheduling is to allocate a set of jobs M = {o1, . . . , om} (called chores or items throughout this paper) to a set of agents N = {a1, . . . , an} in a fair manner, where every job has to be entirely allocated to exactly one agent. Each agent ai has a valuation function vi : 2M → R≥0 to evaluate the cost of completing the jobs allocated to her. In this paper, we focus on additive valuations. In the general situation, and most likely what happens in reality, the agents have possibly different obligations or responsibilities in completing these jobs. For example, a person in a leadership position is naturally expected to undertake higher responsibility than the others. To model this asymmetry of the agents, each agent ai is assumed to hold a share of 0 < wi < 1 over all jobs, where ∑ni=1 wi = 1, and wi's are called the agents' weights in the system. Among the various fairness notions, which will be briefly reviewed in Section 1.2, proportional fairness is a remarkable one, which requires the allocation to respects the agents' shares. Formally, an allocation (A1, . . . ,An) is proportional (PROP), if vi(Ai) ≤ wi · vi(M) for all agents ai [Steinhaus, 1948; Robertson and Webb, 1998].

PROP is ideal, but it is very hard to satisfy. For example, if M contains a single job and all agents have non-zero cost on it, no matter which agent receives it, the allocation is not fair to her. Accordingly, several ways of relaxing the requirements of PROP are proposed in the literature. For example, proportionality up to any item (PROPX) is studied in [Li et al., 2022], where an allocation is PROPX if for all agents ai, vi(Ai \ {e}) ≤ wi · vi(M) holds for any e ∈ Ai. The good news is that a PROPX allocation is always guaranteed to exist and can be found easily if the valuations are additive. Another popular relaxation of PROP is the maximin share (MMS) fairness, which was first proposed for allocating goods (where agents prefer to get more items) and symmetric agents, i.e., when w1 = · · · = wn = 1n , by [Budish, 2010]. The intuition of MMS fairness is to relax the weight 1n to a weaker share that is easy to satisfy. Let A be the set of all allocations, then the MMS of agent ai is

which is the minimum of the maximum cost for ai in any n-partition of the chores. Clearly, MMSi ≥ 1n and thus agent ai is satisfied if her cost is no greater than MMSi. Although there are still, but rare, instances for which the MMS value cannot be guaranteed for every agent [Aziz et al., 2017; Feige et al., 2021], there are constant approximations [Huang and Lu, 2021; Huang and Segal-Halevi, 2023]. To generalize this share-based notion to asymmetric agents (when the agents have non-identical weights), AnyPrice share (APS) fairness was proposed in [Babaioff et al., 2021]. The definition of APS is slightly more complicated; informally, APSi defines a share for every agent ai which is the maximum effort she needs to pay when her loan to the system equals her weight wi and she completes a least painful set of items to repay her loan when the jobs are adversarially priced with a total price of 1. Since APS is not easy to understand, a simple notion, chore share (CS), is introduced in [Huang and SegalHalevi, 2023], which provides a convenient replacement and a lower bound on the APS. For agent ai with weight wi,

where o1, ok, ok+1 are the items with the 1-st, k-th and (k + 1)-th highest values and k = ⌊ 1 wi ⌋. If m is not sufficiently large, vi({ok, ok+1}) can be dropped from the max operator.

Consider a simple instance of allocating two identical items to two agents with w1 = 1 - ϵ, w2 = ϵ, where ϵ > 0 is a sufficiently small number. The values are shown in Table 1. It can be verified that, APS2 = CS2 = 0.5, which means if we only allocate one item to agent a2 (and the other item to a1), a2 would accept this allocation since the item's value is also 0.5, i.e., the allocation is APS and CS fair. The allocation is also PROPX, since by removing the item from a2's allocation, her bundle is empty. However, when ϵ approaches 0, we may not regard this allocation as a fair one because agent a2 bears little responsibility. This drawback is commonly observed in all the aforementioned notions: if an agent receives a single item, they would consider the allocation fair, regardless of the item's value.

In fact, in the above instance, there is an allocation that is fairer when ϵ is small - allocating both items to agent a1. Agent a1 understands that she is expected to take 1 - ϵ fraction of all the items, and allocating both items to her is not too far away from a PROP one; however, if one of the items is given to a2, agent a2's value is 0.5 ≫ ϵ (even so in a1's perspective), which is far from a fair allocation. This intuition has been formalized as weighted maximin share fairness (WMMS) defined in [Aziz et al., 2019]. Given an allocation (A1, . . . , An), we define the unfairness ratio of agent ai as

and then the "fairest" allocation is to minimize the unfairness ratio. Thus, the weighted MMS of ai is her weight times the smallest unfairness ratio, i.e.,

It is easy to see that when all agents have the same weight, WMMSi is exactly MMSi. An allocation is WMMS fair if all agents' values are no greater than their WMMS.

Recall the example in Table 1,

and

By the definition of WMMSi, we need to enumerate all possible allocations to find the smallest unfairness ratio. But in the example, it is clear that this ratio appears between allocating both items to agent a1 and allocating one of the items, say o1, to agent a2. When ϵ → 0, we can see that WMMSi is closer to the proportionality wi, and the only WMMS fair allocation is to allocated both items to agent a1. Moreover, in this case, any finite approximation of WMMS would allocate both items to agent a1.

Then our question is if we can guarantee (approximate) WMMS fairness for all instances. A trivial solution is to allocate all items to the agent with the largest weight, which achieves n-approximate WMMS, but beyond that nothing is known. In this paper, we show how to improve the approximation ratio via simple sequential algorithms, and also investigate the inherit difficulties of approximating WMMS.

1.1 Our Contribution

Our main results can be summarized as follows.

It is proved in [Aziz et al., 2019] that allocating all items to the agent with the highest weight achieves n-approximation of WMMS, but no non-trivial approximation ratio beyond n has been proved thus far. Our first contribution is a simple sequential picking algorithm that improves the approximation ratio to O(logn), where the algorithm only accesses each agent's ordinal ranking of the items. Informally, the algorithm uses the weights of the agents to divide the run of the algorithm in rounds. The agents with higher weights will join the algorithm in earlier rounds and thus receive more items. Within each round, we fractionally allocate the items to the agents proportional to their weights, and show that such a fractional allocation can be converted to an integral one without loss of much approximation ratio, using a rounding technique in [Feige and Huang, 2023]. By carefully choosing all parameters, we show that no agent obtains cost higher than O(logn) times of her WMMS. Although the analysis of our algorithm is not trivial, given these parameters, the implementation of the algorithm is straightforward.

Main Result 1. There exists an O(logn)-approximate WMMS allocation for all instances with additive valuations.

We next focus on a typical case of two agents. Intuitively, if the two agents possess similar weights, the divide-and-choose algorithm should yield favorable results. Conversely, if one agent has a significantly larger weight than the other, allocating all items to that agent should also produce a satisfactory allocation. However, the challenge lies in the situations that fall between these two extremes. Through a more intricate analysis and by carefully distinguishing these three cases, we show that we can achieve √3+1 2 ≈ 1.366 approximation. Further, we prove that this is the optimal approximation ratio an algorithm can reach, surpassing the previously proven inapproximability of 4 3 ≈ 1.33 in [Aziz et al., 2019].

Main Result 2. For the case of two agents, the optimal approximation ratio of WMMS fairness is √3+1 2 .

This result also shows the distinction between weighted and unweighted cases, where 1.182-MMS allocation exists [Huang and Segal-Halevi, 2023] when the agents have identical weights for arbitrary number of agents and an MMS allocation exists when there are two agents.

Finally, we consider the online setting when the items arrive one after another and the algorithm does not know the information on the future events. The problem has been studied in [Zhou et al., 2023] when the agents are symmetric. It is shown that when the valuations are normalized, constant competitive ratios can be achieved. It is also known that if the valuations are not normalized, no online algorithm can be better than Ω(n)-competitive. We follow this trend and consider the general weighted case, and prove that we can achieve a competitive ratio of O(√n) via a simple greedy algorithm. Although we do not view this as a main result of the paper, it may show some insights in further improving the approximation ration in the offline setting. As mentioned in Main Result 1, the algorithm there only relies on the agents' weights and their ordinal valuations. We suspect that using the cardinal values (more information than an ordering) can give a better approximation ratio. The algorithm here shows one possible way to utilize the values.

1.2 RelatedWorks

Fair division is a multidisciplinary field that intersects computer science, economics, and mathematics. It remains a subject of ongoing debate regarding its fundamental concepts. Among the various fairness notions, two extensively studied and widely accepted ones are proportionality (PROP) [Steinhaus, 1948] and envy-freeness (EF) [Foley, 1967; Varian, 1973]. However, when it is not possible to divide the items, satisfying PROP and EF is not always feasible. Consequently, relaxations of these notions have been proposed, including MMS [Budish, 2010], PROP1 [Conitzer et al., 2017], PROPX [Aziz et al., 2020], EF1 [Budish, 2010; Lipton et al., 2004], and EFX [Gourv`es et al., 2014; Caragiannis et al., 2019]. MMS fairness was first introduced in [Budish, 2010] for goods and later [Kurokawa et al., 2018] proved that MMS may not exist in some instances but a 2/3-approximation always exists. The approximation ratio is later improved or extended to more general valuations in a series of works, e.g., [Ghodsi et al., 2018; Barman and Krishnamurthy, 2020; Garg and Taki, 2020], and the best-known approximation is (3/4 + 3/3836) so far, given in [Akrami and Garg, 2024].

[Aziz et al., 2017] extended the MMS fairness to chores, and proved that it may not be satisfiable for all additive valuations but a 2-approximate MMS allocation can be easily found. Later the approximation ratio is improved in [Barman and Krishnamurthy, 2020; Huang and Lu, 2021; Huang and Segal-Halevi, 2023] and generalized to more general valuations in [Li et al., 2023]. The best-known approximation for additive valuations is 13/11 [Huang and SegalHalevi, 2023]. For a more comprehensive introduction to these concepts, interested readers can refer to a recent survey [Amanatidis et al., 2023].

In recent years, most of the concepts mentioned earlier have been extended to the weighted versions that accommodate asymmetric agents. For goods, while a weighted PROP1 (PROP after removing some item) allocation exists but a weighted PROPX (PROP after removing any item) allocation may not exist [Aziz et al., 2020]. In contrast, for chores, a weighted PROPX (implying weighted PROP1) allocation exists and can be found easily [Li et al., 2022]. For both goods and chores, a weighted EF1 allocation can be computed in polynomial time [Wu et al., 2023], but the existence of weighted EFX allocations is not guaranteed [Hajiaghayi et al., 2023]. Regarding weighted MMS, Farhadi et al. [Farhadi et al., 2019] proved that the best possible approximation ratio is 1n for goods, and Aziz [Aziz et al., 2019] investigated the problem for chores but the best possible approximation ratio is still unknown. Apart from the aforementioned fairness criteria, there are additional notions, such as AnyPrice share (APS) [Babaioff et al., 2021; Feige and Huang, 2023] and maximin aware (MMA) up to one or any [Wei et al., 2023] for which constant approximations are allowed for chores.

2 Preliminaries

2.1 Model

We first formally introduce our problem. For any integer k ≥ 1, let [k] = {1, . . . , k}. For any set S and e ∈ S, let S-e = S\{e}. In a fair allocation instance, there are n agents and m indivisible chores (called items for convenience), denoted by N = {a1, . . . , an} andM= {o1, . . . , om}, respectively. The agents have asymmetric shares for completing the items, and let wi > 0 represent agent ai's share (also called weight). Without loss of generality, the weights are normalized, i.e., ∑ai∈N wi = 1, and assume w1 ≥ · · · ≥ wn. Denote w = (w1, . . . ,wn). Each agent ai has a valuation function vi : 2M → R≥0, where vi(S) represents her cost on completing the items in S. For simplicity, when a bundle contains a single item o, denote vi(o) = vi({o}). In this paper, we only consider additive valuation functions, i.e., vi(S) = ∑oj∈S vi(oj) for every S ⊆ M. Let v = (v1, . . . , vn). We sometimes assume, without loss of generality, that the valuations are normalized, i.e., vi(M) = 1 for all agents ai. In summary, a chore allocation instance is represented by I = (N , M, w, v).

An allocation, denoted by A = (A1, . . . ,An), is an ordered n-partition ofMwhere Ai is the set of items allocated to agent ai such that ⋃ai∈N Ai = M and Ai ∩Aj = ∅ for all i ̸= j. Denote by A the set of all allocations. An allocation is called partial if ⋃ai∈N Ai ⊊ M. Next, we introduce the solution concepts.

Definition 1 (WMMS). Given any chore allocation instance I = (N,M,w, v), for agent ai ∈ N, its weighted maximin share (WMMS), denoted by WMMSi(I), is defined as

When the instance is clear from the context, WMMSi(I) is also written as WMMSi for simplicity.

An partition A1, . . . , An of M is called a WMMS-defining partition for agent ai, if

A simple observation from the definition of WMMS is that

WMMSi ≥ wi · vi(M), for all j = 1, . . . , n. (1) This is because that for any partition B1, . . . , Bn ofM, there must be some j such that vi(Bj) ≥ wj · vi(M) since the weights of the agents are normalized.

Definition 2 (α-WMMS). Given α ≥ 1, an allocation A = (A1, . . . , An) is called α-approximate WMMS fair (αWMMS), if vi(Ai) ≤ α · WMMSi for all agents ai ∈ N.

2.2 Proportional and Ordered Instances

We next introduce some properties of the fair allocation instances, which will be used to simplify our analysis.

We start with additional definitions. A fair allocation instance I = (N,M, w, v) is called ordered if all agents have the same ranking over the items, i.e., vi(o1) ≥ vi(o2) ≥ · · · ≥ vi(om) for all ai ∈ N. It is widely known that the hardest case to approximate WMMS fairness is the ordered instances. The following lemma has been proved, for example, in [Barman and Krishnamurthy, 2020; Huang and Lu, 2021; Li et al., 2022].

Lemma 1. For any α ≥ 1, if there is an algorithmΨ1 that returns an α-WMMS allocation for all ordered instances, then there is another algorithm Ψ2 that ensures an α-WMMS allocation for all instances.

It deserves to note that in Lemma 1, if Ψ1 is a polynomialtime algorithm, then Ψ2 also runs in polynomial time.

Next, given any normalized instance, a valuation function vi is called proportional if WMMSi = wi, i.e., Mcan be partitioned into n bundles A1, . . . ,An such that vi(Aj) = wj for j = 1, . . . , n. The instance is called proportional if WMMSi = wi for all ai ∈ N. We prove that, similar as Lemma 1, to approximate WMMS fairness, it suffices to focus on the proportional instances.

Lemma 2. For any α ≥ 1, if there is an algorithmΨ1 that returns an α-WMMS allocation for all proportional instances, then there is another algorithm Ψ2 that ensures an α-WMMS allocation for all instances.

Proof. Given the algorithm Ψ1, we design the algorithm Ψ2 as follows. For any normalized instance I = (N,M,w, v), Ψ2 first constructs a proportional instance I ′ = (N,M′ ,w, v′ ). For each agent ai, let Ai1 , . . . ,Ain be an arbitrary WMMS-defining partition of her and construct n extra items, denoted byMi = {oi1 , . . . , oin }, such that for j = 1, . . . , n,

Since Ai1 , . . . ,Ain is a WMMS-defining partition, we have vi(Aij ) wj ≤ WMMSi(I) wi and thus v′i (oij ) ≥ 0. Let v′ l (oij ) = 0 for all l ̸= i. Let M′ =M∪M1 ∪ · · · ∪Mn and v′i (o) = vi(o) for all o ∈ M and ai ∈ N . Accordingly, we have

and thus

That is Ai1 ∪{oi1 }, . . . , Ain ∪{oin }, plusM-i being arbitrarily distributed among these n bundles, is a WMMS-defining partition of v′i with items M′ and WMMSi(I ′ ) = WMMSi(I). We remark that we do not normalize the valuations of I ′ to make the connection between I and I ′ evident.

Suppose A = (A1, . . . , An) is an α-WMMS allocation of instance I ′ returned by algorithm Ψ1. For i = 1, . . . , n, let Bi = Ai ∩M and we have

Thus B = (B1, . . . ,Bn) is an α-WMMS allocation of I, which completes the construction of Ψ2.

Remark The construction of instance I ′ in the proof of Lemma 2 does not run in polynomial time, which means Ψ2 may not be a polynomial-time algorithm even if Ψ1 is. By incorporating the rounding method used in [Aziz et al., 2019], our algorithm can be transformed to run in polynomial time, albeit with a constant factor loss in the approximation ratio.

For any instance, we first reduce it to a proportional instance, then reduce it to an ordered one, which is still proportional. Due to Lemmas 1 and 2, in the remaining of this paper, without loss of generality, it suffices to restrict our attention on the ordered and proportional instances.

Finally, we present the following technical lemma, which will be used to design our algorithms. It is easy to see that since agent a1 has the largest weight and the instance is proportional and ordered, we must have v1(o1) ≤ w1; otherwise, WMMS1 > w1 no matter which bundle contains o1 in a1's WMMS-defining partition. In general, we have the following property for all agents ai and i ≥ 2.

Lemma 3. For any proportional and ordered instance, given any agent ai with i ≥ 2, if ∑l∈[i-1] ⌊ wl wi ⌋ < m,

Proof. Given any WMMS-defining partition B1, . . . , Bn for agent ai, Bl cannot contain any item whose value is greater than wi for any l ≥ i since the instance is proportional. Moreover, as vi(Bl) = wl for all l < i, Bl contains at most ⌊ wl wi ⌋ items whose value is greater than wi. Thus in total the number of such large items is at most ∑l∈[i-1] ⌊ wl wi ⌋. Noting that the instance is ordered, we have the lemma.

3 The Main Algorithm

In this section, we prove our main result, where an O(log n)- WMMS allocation can be found in polynomial time.

3.1 Fractional Allocations

Before designing our main algorithm, we first introduce a technical lemma which can further simplify the description of the algorithm. An allocation is fractional if some items are divided and allocated among agents. Formally, denote by 0 ≤ xij ≤ 1 the fraction of item oj that is allocated to agent ai, and let xi = (xi1, . . . , xim). Denote by x = (x1, . . . , xn) a fractional allocation where it is required that ∑ai∈N xij = 1 for all oj ∈ M. The following lemma, proved in [Feige and Huang, 2023], shows that we can convert a fractional allocation to an integral one without sacrificing much on the approximation ratio of WMMS, if (1) the fractional allocation is a good approximation of WMMS and (2) the value

Algorithm 1 fractional allocation → integral allocation

Input: A fractional allocation x = (x1, . . . , xn) for ordered instance I = (M, N , w, v).

Output: An integral allocation A = (A1, . . . , An).

• 1: Initialize that Ai = ∅ for ai ∈ N.
• 2: for j = 1 to mdo
• 3: Choose one agent ai for whom |Ai| < ∑jk=1 xik.
• 4: Ai ←Ai ∪ {oj}.
• 5: end for
• 6: return A= (A1, . . . ,An).

of the largest item each agent positively receives is not much larger than her WMMS. We include the proof of Lemma 4 for completeness.

Lemma 4. [Feige and Huang, 2023] Given any ordered instance I = (M,N,w, v) and a fractional allocation x, where for every agent ai ∈ N, vi(xi) ≤ α · WMMSi and vi(oj) ≤ β · WMMSi for all oj ∈ M such that xij > 0, Algorithm 1 returns an integral (α + β)-WMMS allocation.

Proof. First, observe that Algorithm 1 is well-defined, i.e., for each iteration j = 1, . . . ,m, there exists at least one agent ai such that |Ai| < ∑jk=1 xij. This can be seen by induction. Suppose Algorithm 1 successfully reaches the j-th iteration, and thus exactly j - 1 items have been allocated. Let (Aj1 , . . . ,Ajn ) be the current partial allocation. Since x is a complete allocation, we have

and thus |Ai| < ∑jk=1 xik for at least one agent ai.

Next we bound the value of vi(Ai) for an arbitrary agent ai. If xij = 0 for all item oj ∈M, then ai cannot be selected in Step 3 for any iteration j. Thus Ai = ∅ and vi(Aj) = 0, which means the lemma holds trivially. Otherwise, let fi be the first item for which xifi > 0, then vi(o) ≤ vi(ofi ) for any o ∈ Ai. Suppose Ai = {oj1 , oj2 , . . . , ojp }. Then j1 ≥ fi and vi(oj1 ) ≤ vi(ofi ). Moreover, for any l ≥ 2, ojl can be added to Ai only when ∑k≤jl xik > l - 1 and ojl has smallest value among all the items before ojl . Accordingly vi(Ai \ {oj1 }) ≤ vi(xi) and thus

which completes the proof of the lemma.

3.2 The Algorithm

The goal of our algorithm is to find a fractional allocation x, where for any agent ai ∈ N, vi(xi) ≤ logn · WMMSi and vi(oj) ≤WMMSi for all oj such that xij > 0. By Lemma 4, x can be easily converted into an integral allocation A that is (logn+ 1)-WMMS. Recall that it suffices for us to focus on proportional and ordered instances. Given any such instance I = (N,M,w, v) with w1 ≥ · · · ≥ wn, we categorize the items by n + 1 disjoint groups G = {G0, G1, . . . , Gn}:

Note that Gl may be empty for l ≥ 1 if there are not enough items inM. Our algorithm ensures that the items in each Gi, 1 ≤ i ≤ n, are only allocated to agents in {a1, . . . , ai}, and thus by Lemma 3, the value of each single item allocated to an agent is no greater than her weight. In the following, we show how to ensure everyone's value for her assigned items to be no greater than log n times her weight.

The algorithm is described in Algorithm 2. The key idea is to allocate the items in each group Gi to agents {a1, . . . , ai} proportionally to their weights. Given any N,M,w, the fractional allocation (x1, . . . , xn) is fixed no matter what the valuation profile v is. To bound the approximation ratio of the algorithm, we next show that, agent a1, who has the largest weight, is the worst-off one in the algorithm, and her worstcase valuation is when it aligns the weights of the agents, i.e., v1j = wj for 1 ≤ j ≤ n and v1j = 0 for j > n. Formally, let v′1 be the worst-case valuation, i.e., the proportional valuation vi that maximizes the value of v1(x1) w1 .

Lemma 5. Given any N,M,w, for any agent ai ∈ N and any proportional valuation vi,

Proof. To prove the first inequality, it suffices to consider i ≥ 2. Let x′1 be the projected allocation of xi on groups Gi, . . . ,Gn, i.e., x′1j = 0 for all oj ∈ G1 ∪ · · · ∪ Gi-1 and x′1j = x1j otherwise. Then

where the equality is because the items in Gi, . . . ,Gn are proportionally allocated among the agents according to their

Algorithm 2 The main algorithm

Input: A proportional and ordered instance I = (M, N , w, v).

Output: A fractional allocation x = (x1, . . . , xn).

• 1: for l = 1 to n do
• 2: for i = 1 to l do
• 3: For each oj ∈ Gl, set xij = wi ∑k∈[l] wk .
• 4: end for
• 5: end for
• 6: return x = (x1, . . . , xn).

weights. Since v′1 maximizes the value of v1(x1) w1 ,

To prove the second inequality, it suffices to show v′1 (x1) = ∑mj=1 xij · v′1 (oj) ≤ ∑nj=1 x1j · wj. Recall that v′1 (·) is proportional, i.e., WMMS1 = w1 or equivalently the items can be partitioned into n bundles whose values are exactly w1, . . . , wn. Then we must have that for any 1 ≤ j ≤ n,

This is because, otherwise, to ensure proportionality, any WMMS-defining partition would assign at least one item in {o1, . . . , oj} (whose value is greater than wj) to a bundle with value in wj+1, . . . , wn, which also contradicts v1(·) being proportional. Note that by the design of the algorithm, x11 ≥ x12 ≥ · · · ≥ x1m, and thus we have

for all j < n and

for all j ≤ n. Therefore, summing up Inequality 3 for j = 1, . . . , n - 1 and Inequality 4 for j = n, we have

By the linearity and normalization of the valuation function, assigning positive value to items in {on+1, . . . , om} can only make the total cost to be smaller. Thus

which completes the proof of the lemma.

It remains to bound the value of ∑nj=1 x1j ·wj w1 , which gives the approximatio ratio.

Lemma 6. For any instance I = (N,M,w, v), we have

Proof. For each j = 1, . . . , n, let Gij be the group that contains oj; recall the definition of Gi in Equation 2. If j ≤ ij,

and thus,

Actually, j cannot be strictly smaller than ij by the definition of Gi's, but it does not affect the analysis.

If j > ij , by the definition of Gij , we have

and equivalently, j · wj ≤ ∑k∈[ij] wk. Therefore,

Combining both cases and summing up for all j,

which completes the proof.

Combining the above lemmas, we have the theorem, whose proof is omitted.

Theorem 1. For any fair allocation instance, there is an O(log n)-approximate WMMS allocation.

Finally, we note that our analysis is tight even when m = n, all agents have the same weight, and all the items are identical to the agents. This is because the fractional allocation returned by Algorithm 2 allocates 1i fraction of item oi to agent a1 for each i = 1, . . . , n, and then Algorithm 1 realizes an integral allocation where a1 gets log n complete items. However, any WMMS allocation allocates only one item to a1.

4 Tight Bound for 2 Agents

In this section, we restrict our focus on the case of two agents and prove the following result.

Theorem 2. When n = 2, the optimal approximation ratio of WMMS is √3+1 2 ≈ 1.366.

We prove Theorem 2 through Lemmas 7 and 8 in the subsequent two subsections.

4.1 Lower Bound

Lemma 7. When n = 2, no algorithm can be better than √3+1 2 -WMMS.

Proof. We construct the following instance with two agents a1 and a2 and three items o1, o2, o3. For agent a1, w1 = √3 - 1,v1,1 = √3 - 1, v1,2 = 2 - √3, v1,3 = 0. For agent a2, w2 = 2-√3, v2,1 = √3-1 2 , v2,2 = √3-1 2 , v2,3 = 2-√3. Obviously, WMMS1 = √3 - 1 and WMMS2 = 2 - √3.

If agent a2 get item o1 or o2, the approximation ratio is at least √3+1 2 . While if agent a2 doesn't get item o1 and o2, it means agent a1 get item o1 and o2, the approximation ratio is also at least √3+1 2 . So the lower bound is √3+1 2 .

4.2 Upper Bound

Lemma 8. When n = 2, a √3+1 2 -WMMS allocation exists.

Proof. Suppose the agents are N = {a1, a2}, and without loss of generality, assume agent a1 has a larger weight of w1, and thus 1 2 ≤ w1 ≤ 1. We determine different allocation schemes based on the value of w1:

1. When w1 ≥ √3-1, we allocate all the items M to a1, which ensures an approximation ratio of 1 w1 ≤ √3+1 2 .
2. When 12 ≤ w1 ≤ 35 , we ask agent a1 to partition all items M into two parts, S1 and S2, with the goal of ensuring that the values of the two parts are as equal as possible based on her own valuation. If one of the two parts has a value greater than WMMS1 for agent a1, agent a1 should divide the items in M into the WMMS-defining partitions instead of S1 and S2. Therefore, both parts S1 and S2 induce a WMMS approximation ratio of at most 1 for agent a1. Next, we turn to agent a2, and ask her to choose the part with the smaller value between S1 and S2 based on her own valuation, i.e., the part with a value less than or equal to 12 . The approximation ratio of the chosen bundle for agent a2 is less than or equal to 0.5 w2 ≤ 54 < √3+1 2 . Agent a1 takes the remaining part, resulting an approximation ratio less than or equal to 1. Thus it suffices to
3. set A2 = arg minS∈{S1,S2} v2(S), A1 = M \ A2.
4. When 35 < α < √3 - 1, we find agent a2's WMMS partition B1 and B2. Afterwards, we let agent a1 partition all items in B1 into two parts with values as equal as possible, denoted as B1,1 and B1,2, based on her own valuation. Since B1 ⊆ M, according to the discussion in the previous paragraph, the values of B1,1 and B1,2 are not greater than WMMS1 for agent a1. Then, agent a2 selects the part with smaller value according to her own valuation between B1,1 and B1,2, assuming it is B1,1. Therefore,

Now we have that for agent a2, the WMMS approximation ratios for B1,1 and B2 are both less than √3+1 2 . As for which one is chosen for agent a2 in the end, it is determined by agent a1. Agent a1 selects the larger one between B1,1 and B2 based on her own valuation and we give this bundle to a2, such that A2 = argmaxS∈{B1,1,B2} v1(S). Agent a1 keeps the remaining items inMas her allocation, i.e A1 =M\A2. Let v1(B1,2) = β. Then we have

Algorithm 3 The online greedy algorithm

Input: Online instance I = (M,N,w, v). Output: An allocation A = (A1, . . . , An).

• 1: Initialize that Ai = ∅ for ai ∈ N.
• 2: Find the set of valid agents

• 3: for each arrived item o ∈Mdo
• 4: ai ← argminaj∈N ′ vj(o).
• 5: Ai ←Ai ∪ {o}.
• 6: if vi(Ai) > α · wi and |N ′ | ̸= 1 then
• 7: N ′ ←N ′ \ {ai}.
• 8: end if
• 9: end for
• 10: return A= (A1, . . . ,An).

Given that β ≤ WMMS1 and WMMS1 ≥ w1 ≥ 35 , we have the approximation ratio

Combining the above three cases, we always have a √3+1 2 - WMMS allocation for any instance with two agents.

5 The Online Algorithm

In this section, we consider the online version of the problem, and design a simple O(√n)-competitive algorithm. Similar as [Zhou et al., 2023], we also assume the valuations are normalized, and w1 ≥ · · · ≥ wn. Our algorithm relies on the idea that we first find some agents whose weights are relatively larger than the others, and then only allocate the items to these them. Fix α = √n+1, and let N ′ = {a1, . . . , ak} be the set of agents whose weights are no less than wi ≥ 1α · w1. We call the agents in N ′ valid. Note that N ′ is not empty as agent a1 always belongs to N ′ . Our algorithm runs as follows. For each arrived item, we allocate it to one valid agent in N ′ who has the smallest value, and when an agent's value becomes larger than α times of her weight, we remove this agent from N ′ . We can prove that our algorithm can allocate all items, and the formal description is in Algorithm 3. Due to space limit, we omit the proof of Theorem 3.

Theorem 3. Algorithm 3 returns an O(√n)-WMMS allocation in polynomial time.

6 Conclusion

In this paper, we study the weighted maximin share fair allocation of indivisible chores when the agents have different weights on completing them. We improve the previously best known results for both upper and lower bounds. The direct open and intriguing problem is to design the tight approximation algorithm for arbitrary number of agents. Our O(log n)- approximation algorithm does not fully utilize the agents' cardinal valuations, and we suspect a more involved design could further improve the approximation ratio.

Acknowledgements

This work is funded by Hong Kong RGC General Research Fund (No. PolyU 15224823) and Guangdong Basic and Applied Basic Research Foundation (No. 2023A1515010592).