--- title: "Maximin-Aware Allocations of Indivisible Chores with Symmetric and Asymmetric Agents" authors: - "Tianze Wei" - "Bo Li" - "Minming Li" doi: "10.24963/ijcai.2023/323" url: "https://ijcai.org/proceedings/2023/323" pdf: "https://ijcai.org/proceedings/2023/0323.pdf" venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence" year: 2023 pages: "2897-2905" track: "Main Track" keywords: - "Game Theory and Economic Paradigms: GTEP: Computational social choice" - "Game Theory and Economic Paradigms: GTEP: Fair division" --- # Maximin-Aware Allocations of Indivisible Chores with Symmetric and Asymmetric Agents Tianze Wei, Bo Li, Minming Li *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 2897-2905. DOI: [10.24963/ijcai.2023/323](https://doi.org/10.24963/ijcai.2023/323) ## Abstract The real-world deployment of fair allocation algorithms usually involves a heterogeneous population of users, which makes it challenging for the users to get complete knowledge of the allocation except for their own bundles. Recently, a new fairness notion, maximin-awareness (MMA) was proposed and it guarantees that every agent is not the worst-off one, no matter how the items that are not allocated to this agent are distributed. We adapt and generalize this notion to the case of indivisible chores and when the agents may have arbitrary weights. Due to the inherent difficulty of MMA, we also consider its up to one and up to any relaxations. A string of results on the existence and computation of MMA related fair allocations, and their connections to existing fairness concepts is given. ## Full text ## 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. Figure 1: Relationship between MMA and other notions. The dotted arrow means the implication holds when the weights are the same. ![Image](https://ijcai.org/proceedings/2023/fulltext/323/image_000000_af1b470be6523890cb63d39461cd67697379f44ea9a408456a600ae1771c0a13.png) ## 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]. Figure 2: The illustration of the approximation ratios for MMAX when agents have arbitrary weights. ![Image](https://ijcai.org/proceedings/2023/fulltext/323/image_000001_619145d509ce932cb286af642eb442202aa428d0a174f684863da0f96e5d4343.png) 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}). Table 1: An example of MMA related notions. | fj | f1 | f2 | f3 | f4 | f5 | |-------|-------|-------|------|-------|------| | c(fj) | 19 72 | 17 72 | 29 | 11 72 | 18 | 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). Table 2: An example that a PROPX allocation with symmetric agents fails to provide a bounded approximation ratio of MMA1 or MMAX, where ϵ > 0 is arbitrarily small. | fj | f1 | f2 | f3 | f4 | |--------|--------|--------|------|------| | c1(fj) | 12 - ϵ | 12 - ϵ | ϵ | ϵ | [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. Table 3: An example that an approximate MMS allocation with symmetric agents fails to provide a bounded approximation ratio of MMA1, where ϵ > 0 is arbitrarily small. | fj | f1 | f2 | f3 | |---------|-------|-------|-------| | c1(fj ) | 2 3+ϵ | 1 3+ϵ | ϵ 3+ϵ | 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. Table 4: An example that an MMS allocation with symmetric agents fails to provide a bounded approximation ratio of MMAX, where ϵ > 0 is arbitrarily small. | fj | f1 | f2 | f3 | |---------|-------|-------|------| | c1(fj ) | 1 1+ϵ | ϵ 1+ϵ | 0 | Table 5: An example that an approximate MMAX allocation is preferred, where ϵ > 0 is arbitrarily small. | fj | f1 | f2 | f3 | f4 | f5 | |--------|------|------|------|------|------| | c(fj ) | 3 | 1 | 3ϵ | 3ϵ | 3ϵ | | c(fj ) | 4+9ϵ | 4+9ϵ | 4+9ϵ | 4+9ϵ | 4+9ϵ | 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 ![Image](https://ijcai.org/proceedings/2023/fulltext/323/image_000002_f86ffc2548cd00911687e6ba68a357fe4144ec127745f196085629abcc5ee649.png) 𝑋𝑋𝑗𝑗 𝑋𝑋𝑖𝑖 𝑋𝑋𝑘𝑘 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 Lemma 4. Given any PROPX allocation X = (X1, . . . , Xn), the following inequality holds for every agent i ∈ N, ![Image](https://ijcai.org/proceedings/2023/fulltext/323/image_000003_5e7c57c9f145f5d09b61332773953ef6fde14e753d724d597e498e41787501b5.png) 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. ## References 1. [Amanatidis et al., 2022] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: A survey. CoRR, abs/2208.08782, 2022. 2. [Aziz et al., 2017] Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. Algorithms for max-min share fair allocation of indivisible chores. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 335- 341, 2017. 3. [Aziz et al., 2018] Haris Aziz, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and Jérôme Lang. Knowl- edge, fairness, and social constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4638- 4645, 2018. 4. [Aziz et al., 2019] Haris Aziz, Hau Chan, and Bo Li. Weighted maxmin fair share allocation of indivisible chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 46-52, 2019. 5. [Aziz et al., 2020] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. A polynomial-time algorithm for comput- ing a pareto optimal and almost proportional allocation. Operations Research Letters, 48(5):573-578, 2020. 6. [Barman and Krishnamurthy, 2020] Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation algorithms for maximin fair division. ACM Transactions on Eco- nomics and Computation, 8(1):1-28, 2020. 7. [Bhaskar et al., 2021] Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivisible chores and mixed resources. In Approximation, Random- ization, and Combinatorial Optimization. Algorithms and Techniques, pages 1-23, 2021. 8. [Bouveret and Lemaître, 2016] Sylvain Bouveret and Michel Lemaître. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2):259-290, 2016. 9. [Budish, 2011] Eric Budish. The combinatorial assign- ment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. 10. [Caragiannis et al., 2019] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):1-32, 2019. 11. [Caragiannis et al., 2022] Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio. Existence and computation of epistemic EFX. CoRR, abs/2206.01710, 2022. 12. [Chan et al., 2019] Hau Chan, Jing Chen, Bo Li, and Xi- aowei Wu. Maximin-aware allocations of indivisible goods. In Proceedings of the 28th International Joint Con- ference on Artificial Intelligence, pages 137-143, 2019. 13. [Chen and Shah, 2017] Yiling Chen and Nisarg Shah. Ig- norance is often bliss: Envy with incomplete informa- tion. Technical report, Working paper, Harvard University, 2017. 14. [Conitzer et al., 2017] Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair public decision making. In Pro- ceedings of the 18th ACM Conference on Economics and Computation, pages 629-646, 2017. 15. [Feige and Huang, 2022] Uriel Feige and Xin Huang. On picking sequences for chores. CoRR, abs/2211.13951, 2022. 16. [Garg et al., 2022] Jugal Garg, Aniket Murhekar, and John Qin. Fair and efficient allocations of chores under bivalued preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5043-5050, 2022. 17. [Grandl et al., 2014] Robert Grandl, Ganesh Anantha- narayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. Multi-resource packing for cluster schedulers. ACM SIGCOMM Computer Communication Review, 44(4):455-466, 2014. 18. [Hajiaghayi et al., 2023] MohammadTaghi Hajiaghayi, Max Springer, and Hadi Yami. Almost envy-free allocations of indivisible goods or chores with entitlements. CoRR, abs/2305.16081, 2023. 19. [Hosseini et al., 2020] Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, Hejun Wang, and Lirong Xia. Fair division through information withholding. In Proceedings of the AAAI Con- ference on Artificial Intelligence, pages 2014-2021, 2020. 20. [Huang and Lu, 2021] Xin Huang and Pinyan Lu. An algo- rithmic framework for approximating maximin share allo- cation of chores. In Proceedings of the 22nd ACM Con- ference on Economics and Computation, pages 630-631, 2021. 21. [Huang and Segal-Halevi, 2023] Xin Huang and Erel Segal- Halevi. A reduction from chores allocation to job schedul- ing. CoRR, abs/2302.04581, 2023. 22. [Li et al., 2022] Bo Li, Yingkai Li, and Xiaowei Wu. Almost (weighted) proportional allocations for indivisible chores. In Proceedings of the ACM Web Conference 2022, pages 122-131, 2022. 23. [Lipton et al., 2004] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125- 131, 2004. 24. [Moulin, 2003] Hervé Moulin. Fair division and collective welfare. MIT Press, 2003. 25. [Moulin, 2019] Hervé Moulin. Fair division in the internet age. Annual Review of Economics, 11:407-441, 2019. 26. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can. CRC Press, 1998. 27. [Steinhaus, 1949] Hugo Steinhaus. Sur la division pragma- tique. Econometrica: Journal of the Econometric Society, 17:315-319, 1949. 28. [Steven J. Brams and Alan D. Taylor, 1996] Steven J. Brams and Alan D. Taylor. Fair division: from cake-cutting to dispute resolution. Cambridge University Press, 1996. 29. [Sun et al., 2021] Ankang Sun, Bo Chen, and Xuan Vinh Doan. Connections between fairness criteria and effi- ciency for allocating indivisible chores. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 1281-1289, 2021. 30. [Varian, 1974] Hal Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63-91, 1974. 31. [Verma et al., 2015] Abhishek Verma, Luis Pedrosa, Mad- hukar Korupolu, David Oppenheimer, Eric Tune, and John Wilkes. Large-scale cluster management at google with borg. In Proceedings of 10th European Conference on Computer Systems, pages 1-17, 2015. 32. [Wu et al., 2023] Xiaowei Wu, Cong Zhang, and Shengwei Zhou. Weighted EF1 allocations for indivisible chores. CoRR, abs/2301.08090, 2023. 33. [Zhou and Wu, 2022] Shengwei Zhou and Xiaowei Wu. Ap- proximately EFX allocations for indivisible chores. In Proceedings of the 31th International Joint Conference on Artificial Intelligence, pages 783-789, 2022.