Maximin-Aware Allocations of Indivisible Chores with Symmetric and Asymmetric Agents

1 Introduction

Fairness is an important issue in many multi-agent systems, where all participants should be treated equally [Steinhaus, 1949]. For example, network technology companies like Amazon, Google and Meta use schedulers in the cloud to allocate resources (e.g., servers, memory, etc.) or tasks (e.g., development, maintenance, etc.) among a number of selfinterested agents who want to maximize the utility of their own allocations. To ensure the sustainability of the Internet economy, the schedulers want the allocations to be fair [Moulin, 2003; Verma et al., 2015; Grandl et al., 2014]. [Steven J. Brams and Alan D. Taylor, 1996] presented the real-life applications of fair allocation problems, and a recent survey by [Amanatidis et al., 2022] reviewed the progress from the perspective of computer science and economics.

Two of the most well-established fairness criteria are envyfreeness (EF) [Varian, 1974] and proportionality (PROP) [Steinhaus, 1949]. EF is an envy-based notion where every agent compares her own bundle with every other agent's and wants to get the best bundle. PROP is a share-based notion where every agent wants to ensure that the value of her bundle is no worse than 1n fraction of her value for all the items where n is the number of agents. When the items are indivisible, EF and PROP are hard to satisfy, and many relaxations have been studied instead in the literature. Among these relaxations, the

"up to one" relaxation is one of the most popular ways, which requires the fairness notions to be satisfied after the removal of some item. The resulting notions are called EF or PROP up to one item, abbreviated as EF1 [Lipton et al., 2004] and PROP1 [Conitzer et al., 2017]. A stronger relaxation is "up to any" which strengthens the qualifier of the removed item to be arbitrary. Thus we get EF or PROP up to any item, abbreviated as EFX [Caragiannis et al., 2019] and PROPX [Moulin, 2019]. Besides these additive relaxations, maximin share fairness (MMS) [Budish, 2011] is another popular notion, which requires every agent's value to be no worse than her worst share in an optimal n-partition of all items. Formal definitions of these fairness notions are deferred to Section 2.

1.1 Epistemic Fair Allocation

Motivated by the real-world applications where the agents do not have complete knowledge of the allocation due to privacy concerns or a huge number of agents involved in the system, an emerging line of research in fair resource allocation studies the epistemic fairness leveraging the information the agents have [Chen and Shah, 2017; Aziz et al., 2018; Hosseini et al., 2020; Caragiannis et al., 2022]. For example, epistemic EF was introduced by [Aziz et al., 2018] for the setting when the agents are connected via a social network and only know the bundles allocated to their neighbors. Informally, an allocation is epistemic EF if there exists a distribution of the items allocated to her non-neighboring agents such that the allocation is EF to her. Similar ideas have been extended to EFX by [Caragiannis et al., 2022].

What all the aforementioned works have in common is that they consider the epistemic variants of envy-based fairness notions. This is partly due to the fact that most share-based notions themselves do not require the knowledge of the allocations to the other agents. In comparison, [Chan et al., 2019] proposed another epistemic fairness notion named maximinaware (MMA), which combines envy-based and share-based requirements. Informally, the intuition of MMA is to ensure every agent does not obtain the worst bundle without knowing how the items that are not allocated to her are allocated among the other agents. Since MMA is hard to satisfy, they also proposed the up to one and up to any relaxations.

So far, most of the epistemic study of fair resource allocation has focused on the case of goods, when the agents want to obtain items with high value. Following [Chan et al., 2019], we study MMA allocations and make the following extensions. While [Chan et al., 2019] only considered allocating goods among symmetric agents, we study the allocation of indivisible chores (i.e., agents want to obtain items with low value) and the general situation where the agents may have different weights. We summarize our problem and the results in the following section.

1.2 Our Problem andMain Contribution

We study the maximin-aware (MMA) allocation of indivisible chores among n agents whose cost functions are additive. We use weights to represent the asymmetry of agents in the system when the agents may have different obligations or responsibilities in a system. For example, a person in a leadership position is naturally expected to undertake higher collaboration responsibilities. Weighted fairness has been justified since the very early study of fair division in the context of cake cutting problem [Robertson and Webb, 1998]. In our problem, the agents know the number of agents, the weights of agents and the set of items. Meanwhile, they are only aware of their own bundles but do not know how the items that are not allocated to them are allocated among the other agents. An MMA allocation guarantees that for each agent, there must exist some other agent whose bundle is no better than hers. A bit more formally, an allocation is MMA if the cost of every agent's bundle is no greater than her n - 1 (weighted) maximin share of the items that are not allocated to her, where weighted maximin share is defined in [Aziz et al., 2019].

Since MMA is hard to satisfy, we also consider its "up to one" and "up to any" relaxations, resulting in the notions of MMA1 and MMAX. The relationships between MMA1/MMAX and existing notions are shown in Figure 1. We can see that general EF related notions are stronger than MMA related ones, but PROP related notions and MMA related ones are not comparable. An exception is that MMS implies MMA1 when the agents have the same weight, but fails to ensure any approximation of MMA1 if the agents' weights are arbitrary. Another one is that a PROP allocation is also MMA; however, a PROP1 or PROPX allocation does not have any guaranteed approximation of MMA1 or MMAX.

The advantage of MMA1 is its guaranteed existence for agents with arbitrary weights. Regarding MMAX, we show its existence when the agents have the same weight. When the agents have different weights, MMAX allocations may not exist for two agents, implied by [Hajiaghayi et al., 2023].

Accordingly, we design a (1 + λ)-approximation algorithm, where λ = √5+1 2 if n = 2 and λ = 3-n+√n2+10n-7 4n-4 if n ≥ 3. We plot the approximation ratios in Figure 2. As we can see, since 1 n-1 < λ < 2 n-1 , the approximation ratio becomes close to 1 when n becomes large. Designing algorithms for envy-based notions (such as EFX) is arguably harder than that for share-based ones (such as PROPX) since it requires comparisons between every agent with every other agent. For example, a PROPX allocation always exists when the agents have arbitrary weights [Li et al., 2022]; however, the best known approximation of EFX is O(n2 ) for agents with the same weight [Zhou and Wu, 2022], and nothing is known when the agents have different weights.

1.3 Other RelatedWork

Fair allocation of indivisible items for the case of goods has been widely studied; see the survey of [Amanatidis et al., 2022] for an overview. There is also a recent line of work regarding the fair allocation of indivisible chores. [Aziz et al., 2017] initiated the fair allocation of chores with MMS notions and showed that there exists an instance where MMS allocations do not exist. But approximate MMS allocations can be computed efficiently [Aziz et al., 2017; Barman and Krishnamurthy, 2020; Huang and Lu, 2021; Huang and Segal-Halevi, 2023]. When the agents are asymmetric, [Aziz et al., 2019] and [Feige and Huang, 2022] explored the weighted MMS fairness and anyprice share (APS) fairness. [Aziz et al., 2020] proposed a polynomial-time algorithm to compute an allocation that satisfies Pareto optimality and PROP1 simultaneously for asymmetric agents when the set of items include goods and chores. [Sun et al., 2021] studied the connections among several fairness notions like EFX, MMS, etc. in allocating chores. [Li et al., 2022] and [Wu et al., 2023], respectively, showed that when agents are asymmetric, PROPX and EF1 allocations exist and can be computed in polynomial time. [Garg et al., 2022] presented a polynomial-time algorithm to compute an allocation that satisfies Pareto optimality and EF1 simultaneously when agents have at most two values for chores, and [Wu et al., 2023] extended this result to asymmetric agents. [Hajiaghayi et al., 2023] showed that EFX allocations do not always exist when there are two or three agents with different weights.

2 Preliminaries

We introduce our model and solution concepts in this section. Let N = {1, . . . , n} be a set of n agents, and M = {f1, . . . , fm} be a set of m indivisible chores. Each agent i ∈ N has a cost function ci : 2N → R≥0. The cost functions are assumed to be additive, i.e., for any S ⊆ M, ci(S) = ∑f∈S ci({f}). For simplicity, we use ci(f) instead of ci({f}) for f ∈ M. We study the weighted setting, where each agent has a weight wi > 0, and the weights add up to one, i.e., ∑i∈N wi = 1. Without loss of generality, we assume that ci(M) = 1 for all agents i ∈ N. A chores allocation instance is denoted as I = ⟨M,N, c,w⟩, where c = (c1, . . . , cn) and w = (w1, . . . ,wn). An allocation X = (X1, . . . ,Xn), where Xi is the bundle allocated to agent i, is an n-partition of M among n agents, i.e., ⋃i∈N Xi = M and Xi ∩ Xj = ∅ for any two agents i ̸= j. Let Πn(M) denote the set of all n-partitions of M. Particularly, we denote the set of items that are not allocated to agent i as X-i = ⋃j∈N\{i} Xj .

2.1 Fairness Concepts

We next introduce the most classic fairness notions, including envy-freeness, proportionality and their relaxations.

Definition 1 (EF). For any α ∈ [1, +∞), an allocation X = (X1, . . . ,Xn) is α-approximate envy-free (α-EF), if for any two agents i, j ∈ N, ci(Xi) wi ≤ α · ci(Xj) wj . The allocation is EF if α = 1.

Definition 2 (EF1 and EFX). For any α ∈ [1, +∞), an allocation X = (X1, . . . ,Xn) is α-approximate envy-free up to one item (α-EF1), if for any two agents i, j ∈ N with Xi ̸= ∅,

If the quantifier "some" in Inequality (1) is changed to "any", the allocation is α-approximate envy-free up to any item (α-EFX). The allocation is EF1 or EFX if α = 1.

Definition 3 (PROP). For any α ∈ [1,+∞), an allocation X = (X1, . . . ,Xn) is α-approximate proportional (αPROP), if for any agent i ∈ N, ci(Xi) ≤ α · wi · ci(M). The allocation is PROP if α = 1.

Definition 4 (PROP1 and PROPX). For any α ∈ [1, +∞), an allocation X = (X1, . . . ,Xn) is α-approximate proportional up to one item (α-PROP1), if for any agent i ∈ N with Xi ̸= ∅,

If the quantifier "some" in Inequality (2) is changed to "any", the allocation is α-approximate proportional up to any item (α-PROPX). The allocation is PROP1 or PROPX if α = 1.

Besides PROP1 and PROPX, maximin share fairness is another popular relaxation of proportionality.

Given an instance I = ⟨M,N, c,w⟩, the maximin share of agent i on M among n agents is defined as :

Different from the unweighted case, we can see that even if two agents have the same cost function, they may still have different MMS values.

Definition 5 (MMS). For any α ∈ [1,+∞), an allocation X = (X1, . . . ,Xn) is α-approximate maximin share fair (αMMS), if for any agent i ∈ N, ci(Xi) ≤ α · MMSi(M, n). The allocation is MMS if α = 1.

2.2 Maximin-Aware and Its Relaxations

Next, we introduce our main solution concept, maximinaware fairness, which is a hybrid notion of EF and MMS. Intuitively, a bundle Xi is maximin-aware (MMA) fair to an agent i ∈ N if no matter how the items not allocated to her are distributed among the other agents, there always exists one agent whose bundle is no better than hers. In other words, for an arbitrary (n - 1)-allocation (Yj)j̸=i of X-i, there exists j ∗ ∈ N \ {i} such that ci(Xi) wi ≤ ci(Yj∗) wj∗ . Equivalently, a bundle Xi is MMA fair to an agent i ∈ N if ci(Xi) ≤ MMSi(X-i, n - 1), where

Definition 6 (MMA). For any α ∈ [1,+∞), an allocation X = (X1, . . . ,Xn) is α-approximate maximin-aware fair (α-MMA), if for any agent i ∈ N, ci(Xi) ≤ α · MMSi(X-i, n - 1). The allocation is MMA if α = 1.

Similar to EF and MMS, MMA allocations may not exist. Suppose that there are two agents and one item with positive costs for both agents. In any allocation, there always exists one agent who cannot satisfy the condition of MMA. Thus, we consider the relaxations of MMA.

Definition 7 (MMA1 and MMAX). For any α ∈ [1,+∞), an allocation X = (X1, . . . , Xn) is α-approximate maximinaware up to one item (α-MMA1), if for any agent i ∈ N with Xi ̸= ∅, there exists one item f ∈ Xi such that

Similarly, the allocation is α-approximate maximin-aware up to any item (α-MMAX) if Inequality (3) holds for any item f ∈ Xi. The allocation is MMA1 or MMAX if α = 1.

By the definitions, it is straightforward that any α-MMA allocation is α-MMAX, and any α-MMAX allocation is αMMA1. Next, we illustrate these definitions via an example.

Example 1. Consider an instance with three agents and five items. Assume that their weights are w1 = 12 , w2 = 13 and w3 = 16 respectively. For simplicity, assume that they have the same cost function, as shown in Table 1.

Let us examine an allocation X = (X1,X2,X3) with X1 = {f3}, X2 = {f1, f2} and X3 = {f4, f5}. It is not hard to see that for agent 1, X1 is MMA to her since c(X1) = 29 < MMS1(X-1, 2) = max{( 17 72 + 11 72 + 18 ) × 32 , 19 72 × 3} = 19 24 ; for agent 2, X2 is MMA1 but not MMAX to her since c(X2 \ {f1}) = 17 72 < MMS2(X-2, 2) = max{( 29 + 11 72 ) × 23 , 18 × 2} = 14 and c(X2 \ {f2}) = 19 72 > MMS2(X-2, 2) = 14 ; for agent 3, X3 is MMAX to her since c(X3 \ {f5}) = 11 72 = MMS3(X-3, 2) = max{( 16 72 + 17 72 ) × 13 , 19 72 × 12 } = 11 72 and c(X3 \ {f5}) > c(X3 \ {f4}).

Ordered instance. An instance I = ⟨M,N, c,w⟩ is called ordered if all agents have the same ranking on all the items, i.e., for every agent i ∈ N,

Note that in an ordered instance, the agents can still have different cardinal values for the items. Intuitively, there are more conflicts among agents in an ordered instance than in a general one since agents desire the same item. In fact, [Bouveret and Lemaˆıtre, 2016] and [Barman and Krishnamurthy, 2020] formalized this intuition and showed that any algorithm that ensures α-MMS allocations for ordered instances can be converted to an algorithm for the general instances in polynomial time with the same guarantee. We show that the same result holds for MMA1 and MMAX allocations even when the agents have non-identical weights. For space limit, we omit the proof. Therefore, in the following sections, we only focus on ordered instances.

3 Connections betweenMMA and Other Fairness Notions

In this section, we introduce the connections between MMA related notions and the ones related to EF, PROP and MMS. Due to space limit, some proofs in this section are omitted.

3.1 EF1 and EFX

We start with EF related notions. By the definitions, it is not hard to verify that EF implies MMA, and the implication also holds for up to one/any relaxations.

Lemma 1. For any α ∈ [1,+∞), any α-EF1 allocation is also α-MMA1.

Proof. Let X = (X1, . . . ,Xn) be an α-EF1 allocation. By the definition of EF1 allocations, for any agent i ∈ N, we have wj · ci(Xi \ {f imax }) ≤ α · wi · ci(Xj), where f imax = argmaxf∈Xi ci(f), for any agent j ∈ N\{i}. Then, summing up respective inequalities for all j ∈ N \ {i}, we get

Suppose, for the contradiction, that X is not an α-MMA1 allocation, i.e., there exists some agent i ∈ N such that ci(Xi \ {f}) > α · MMSi(X-i, n - 1) holds for any item f ∈ Xi. Let Y = (Yj)j̸=i, where wi · maxj∈N\{i} ci(Yj ) wj = MMSi(X-i, n - 1), be an (n - 1)-allocation of X-i. So we have wj · ci(Xi \ {f imax }) > α · wi · ci(Yj) for any j ∈ N \ {i}. Similarly, summing up respective inequalities for all j ∈ N \ {i}, we have (1 -wi) · ci(Xi \ {f imax }) > α · wi · ci(X-i). which contradicts Inequality (4).

[Wu et al., 2023] showed that a (weighted) EF1 allocation can be computed in polynomial time, and thus by Lemma 1, we directly have the following corollary.

Corollary 1. MMA1 allocations exist and can be computed in polynomial time.

The proof of the following lemma is identical to that of Lemma 1. except that we use f imin to replace f imax where f imin = argminf∈Xi ci(f).

Lemma 2. For any α ∈ [1,+∞), any α-EFX allocation is also α-MMAX.

When agents have different weights, EFX allocations may not exist for two or three agents [Hajiaghayi et al., 2023]. Especially, when there are two agents, EFX is equivalent to MMAX. Thus, MMAX allocations may not exist for two agents. However, when the agents have the same weight, the Top-trading Envy Cycle Elimination algorithm [Li et al., 2022; Bhaskar et al., 2021] can find EFX allocations for ordered instances in polynomial time. By Lemma 2, we have the following corollary.

Corollary 2. When all agents have the same weight, MMAX allocations exist and can be computed in polynomial time.

3.2 PROP, PROP1 and PROPX

Next, we discuss the connections between MMA and PROP related notions. As we will see, in sharp contrast to EF, although PROP still implies MMA, PROP1 and PROPX do not guarantee any bounded approximation for MMA1 and MMAX.

Lemma 3. Any EF or PROP allocation is also MMA.

Proposition 1. A PROPX allocation is not necessarily αMMA1 or α-MMAX for any α ∈ [1,+∞), even when the agents have the same weight.

Proof. Consider an instance with two agents with the same weight and four items. We focus on agent 1, and the cost of each item, according to agent 1, is shown in Table 2.

Now consider an allocation X = (X1,X2) with X1 = {f1, f2} and X2 = {f3, f4} and assume that this allocation is PROPX to agent 2. 1 For agent 1, this is a PROPX allocation, andX1 is not better than ( 1 4ϵ - 12 )-MMA1 or ( 1 4ϵ - 12 )-MMAX to her since c1(X1\{f}) MMS1(X-1,1) = 12 -ϵ 2ϵ for any item f ∈ X1. For any given α ≥ 1, setting ϵ < 1 4α+2 , we have 1 4ϵ - 1 2 > α. Thus, this allocation is not α-MMA1 or α-MMAX.

1 For agent 2, it is easy to assign costs to the items to make allocation X be PROPX to her. Therefore, we do not specify the cost of each item from her perspective. The same applies to the subsequent examples.

The above result directly implies the following corollary.

Corollary 3. A PROP1 allocation is not necessarily αMMA1 or α-MMAX for any α ∈ [1, +∞).

Similarly, we have the following counterpart results.

Proposition 2. An MMAX allocation may not be PROP1 or PROPX, even when the agents have the same weight.

The above result directly implies the following corollary. Corollary 4. An MMA1 allocation may not be PROP1 or PROPX.

3.3 MMS

Finally, we discuss the relationship between MMS and MMA related notions.

Proposition 3. When the agents have arbitrary weights, an MMS allocation is not necessarily α-MMA1 or α-MMAX for any α ∈ [1, +∞).

Proposition 4. When the agents have the same weight,

1. any MMS allocation is also MMA1;
2. there exists α ∈ (1,+∞) such that an α-MMS allocation is not necessarily β-MMA1 for any β ∈ [1, +∞);
3. an MMS allocation is not necessarily α-MMAX for any α ∈ [1, +∞).

Proof. For the first statement, let X = (X1, . . . ,Xn) be an MMS allocation. Suppose, for the contradiction, that X is not an MMA1 allocation, i.e., there exists some agent i ∈ N such that ci(Xi \ {f}) > MMSi(X-i, n - 1) holds for any item f ∈ Xi. Let Y = (Yj)j̸=i, where maxj∈N\{i} ci(Yj) = MMSi(X-i, n - 1), be an (n - 1)-allocation of X-i. In allocation Y, we assume that bundle Yk satisfies ci(Yk) = MMSi(X-i, n - 1). Next, if we choose one item f imax from Xi, where f imax = argmaxf∈Xi ci(f), and put it in bundle Yk, we obtain a new n-partition of M, i.e., P new = {Xi \ {f imax }, Yk ∪{f imax }}∪{Yj}j̸=i,k. In P new , the cost of the bundle with the maximum cost is strictly less than ci(Xi), which contradicts the definition of MMSi(M, n).

Regarding the second statement, consider an instance with two agents with the same weight and three items. We focus on agent 1, and the cost of each item, according to agent 1, is shown in Table 3.

Note that MMS1 = 2 3+ϵ . Now consider an allocation X = (X1,X2) with X1 = {f1, f2} and X2 = {f3} and assume that this allocation is MMS to agent 2. It is easy to see that, for agent 1, this is a 32 -MMS allocation, and X1 is no better than 1ϵ -MMA1 to her since c1(X1\{f1}) MMS1(X-1,1) = 1ϵ . For any β ≥ 1, setting ϵ < 1β , we have 1ϵ > β. Thus, this allocation is not β-MMA1.

For the last statement, suppose that we have two agents with the same weight and three items. We focus on agent 1, and the cost of each item, according to agent 1, is shown in Table 4.

It is not hard to see that MMS1 = 1 1+ϵ . Next, consider an allocation Y = (Y1, Y2) with Y1 = {f1, f3} and Y2 = {f2} and assume that this allocation is MMS to agent 2. For agent 1, this is an MMS allocation, and Y1 is no better than 1ϵ -MMAX to her since c1(X1\{f3}) MMS1(X-1,1) = 1ϵ . Similarly, for any α ≥ 1, setting ϵ < 1α , we have 1ϵ > α. Thus, this allocation is not α-MMAX.

Proposition 5. An MMA allocation may not be MMS, even when the agents have the same weight.

The above result directly implies the following corollary.

Corollary 5. An MMA1 or MMAX allocation may not be MMS.

Before the end of this section, we use the following example to illustrate that there are some scenarios where finding approximate MMAX allocations is preferred over finding approximate MMS allocations. Consider an instance with three agents whose weights are w1 = 12 and w2 = w3 = 1 4 , respectively, and five items. Assume that they have the same cost function shown in Table 5.

It can be verified that MMS1 = 3 4+9ϵ and MMS2 = MMS3 = 3 8+18ϵ . Allocating X1 = {f1, f2} to agent 1 is 43 -MMS to her, which is not too bad regarding MMS fairness but is severely unfair since almost all cost is on agent 1. Fortunately, any (bounded-approximate) MMAX allocation ensures that one agent can only get one of the items f1 and f2, since we have

and similarly for i = 2, 3,

4 Computing Approximate MMAX Allocations

As we have shown, an MMA1 allocation can be computed in polynomial time, while an MMAX allocation may not exist

𝑋𝑋𝑗𝑗

𝑋𝑋𝑖𝑖

𝑋𝑋𝑘𝑘

Figure 3: The illustration of swap when n ≥ 3 and Xi satisfies the condition in Step 10 of Algorithm 1.

when the agents have different weights. In this section, we design efficient algorithms to compute approximate MMAX allocations.

Computing MMAX allocations, which is a hybrid notion that combines envy-based and share-based comparisons, is arguably harder than that for PROPX allocations. By the definition of MMAX, each agent i will compare ci(Xi \ {f}) for an item f ∈ Xi and MMSi(X-i, n - 1), where MMSi(X-i, n - 1) depends on the allocation X instead of a prefixed share. That is, an MMAX allocation, on the one hand, requires that every agent has a low cost on her bundle excluding any item (similar to PROPX), and on the other hand, requires the existence of some agent whose bundle is worse off than hers (similar to EFX) no matter how the items that are not allocated to her are distributed. Proposition 1 shows that a PROPX allocation does not provide any guarantee for MMAX. However, we show that we can turn an arbitrary PROPX allocation into an approximate MMAX allocation with some modifications.

Consider the following instance, where we have three agents such that w1 = 12 and w2 = w3 = 14 , and four items. We focus on agent 1, and the cost of each item, according to agent 1, is shown in Table 2. Consider a PROPX allocation X = (X1,X2,X3) with X1 = {f1, f2}, X2 = {f3} and X3 = {f4}. It is clear that X2 and X3 are PROPX to agents 2 and 3, and X1 = {f1, f2} is PROPX to agent 1. However, X1 is far from being MMAX to agent 1 since f3 and f4 have infinitesimally small costs compared to the weights of the other two agents.

In this example, the PROPX allocation fails to provide a good approximation of MMAX to an agent because the items allocated to an agent are all very heavy compared to those allocated to the other agents. Then our algorithm starts with an arbitrary PROPX allocation, and if an agent only obtains a single item, her bundle is trivially MMAX to her. The bad situation is when an agent i gets at least two items where each item has a cost larger than a fraction (a parameter determined by n) of that of the items allocated to the other agents. Next we exchange two arbitrary items in Xi with the two smallest bundles among the other agents in agent i's perspective. Note that if n = 2, we can only exchange one item with one bundle. We check if the bad situation happens for the agents one by one and return the final allocation. The formal description of the algorithm is shown in Algorithm 1.

Before showing the performance of the algorithm, we first prove the following property for PROPX allocations.

Algorithm 1: Swap algorithm

where f imin = argminf∈Xi ci(f).

Proof. By the definition of PROPX allocations, for any agent i ∈ N, we haveci(Xi \ {f imin }) ≤ wi · ci(M). (5)

Next, we expand ci(M), i.e., ci(M) = ci(Xi \ {f imin }) + ci(X-i) + ci(f imin ), and then Inequality (5) can be changed into the desired form

which completes the proof of the lemma.

Theorem 1. Algorithm 1 computes a (1 + λ)-MMAX allocation, where when n = 2, λ = √5+1 2 and when n ≥ 3, λ = 3-n+√n2+10n-7 4n-4 ( 1 n-1 < λ < 2 n-1 ).

Proof. PROPX allocations exist and can be computed by the Bid and Take algorithm [Li et al., 2022]. Therefore, the input allocation of Algorithm 1 can be guaranteed.

Let X = (X1, . . . ,Xn) be a PROPX allocation. Fix one agent i ∈ N. If |Xi| = 1, Xi is triviallyMMAX to agent i. If |Xi| ≥ 2 and ci(f imin ) ≤ λ · ci(X-i), by Lemma 4, we have

Therefore, Xi is (1 + λ)-MMAX to agent i.

If |Xi| ≥ 2 and ci(f imin ) > λ · ci(X-i), consider the following two cases:

Case 1: n = 2. We pick f imin from Xi, and swap it with X-i. Let Xnew i and Xnew j denote the new bundles of agent i and the other agent j ∈ N \ {i}, respectively, after the swap. For these two new bundles, we have Xnew i =M \ {f imin } = Xi ∪ X-i \ {f imin } and Xnew j = {f imin }. For agent j, it is trivial that Xnew j is MMAX to her.

For agent i, we have

where the inequality follows from ci(Xi \ {f imin }) ≥ ci(f imin ) > λ · ci(X-i).

In addition to that, we have

where ci(Xnew -i ) = ci(f imin ).

Note that λ = √5+1 2 , which is the root to the quadratic equation λ2 -λ-1 = 0. Combining Inequalities (6) and (7), and by Lemma 4, we get

Case 2: n ≥ 3. We pick f imin and f imax from Xi, choose two bundles Xj and Xk (j ̸= k), where these two bundles have the two smallest costs fromX-i in agent i's perspective, and then swap them. Let Xnew i , Xnew j and Xnew k denote the new bundles of agents i, j and k, respectively, after the swap. For these three new bundles, we have Xnew i = Xi ∪ Xj ∪ Xk \ {f imin , f imax }, Xnew j = {f imin } and Xnew k = {f imax }. It is easy to see that Xnew j and Xnew k are MMAX to agents j and k, respectively.

For agent i, we have

where the first inequality follows from ci(Xj ∪Xk) ≤ 2 n-1 · ci(X-i) and ci(f imax ) ≥ ci(f imin ) > λ · ci(X-i), and the second from 2 n-1 > λ, which is explained at the end of the proof, and ci(Xi \ {f imin }) ≥ ci(f imin ) > λ · ci(X-i).

Besides that, we have

where the first inequality follows from ci(Xj ∪Xk) ≤ 2 n-1 · ci(X-i) and ci(f imax ) ≥ ci(f imin ).

Note that λ = 3-n+√n2+10n-7 4n-4 , which is a root to the quadratic equation (2n - 2)λ2 + (n - 3)λ - 2 = 0. Putting Inequalities (8) and (9) together, and by Lemma 4, we have

Therefore, in the above two cases, Xnew i is (1+λ)-MMAX to agent i.

Regarding the range of λ, we have

Overall, the allocation X ∗ returned by Algorithm 1 is (1+ λ)-MMAX.

By [Hajiaghayi et al., 2023], the lower bound of EFX allocations for two agents with different weights is 1.272. The lower bounds for the case when n ≥ 3 is unknown.

5 Conclusion

We study the MMA allocation of indivisible chores, when the agents can be asymmetric. In general, MMA related notions (including MMA1 and MMAX) are weaker than the counterpart notions of EF but not comparable with those of PROP. The positive message from this work includes the following. MMA1 allocations always exist for agents with arbitrary weights. MMAX allocations exist when the agents have the same weight, and admit good approximation when the weights are arbitrary, where the approximation ratio gets close to 1 when the number of agents is large. An interesting future direction is to improve the upper and lower bounds for the approximation ratio of MMAX allocations.

Acknowledgments

Bo Li is supported by NSFC under Grant No. 62102333, HKSAR RGC under Grant No. PolyU 25211321, and CCFHuawei Populus Grove Fund. Minming Li is supported by the Fundamental Research Funds for the Central Universities.