Improved MMS Approximations for Few Agent Types

1 Introduction

Fair division of resources is a fundamental problem in various multi-agent settings. In this work, we focus on the discrete setting, where a set of indivisible goods needs to be partitioned among agents with additive preferences. The maximin share (MMS) is a widely studied fairness notion in this context. An allocation is said to satisfy MMS fairness if every agent receives a bundle of goods that they value at least their MMS value. The MMS value for an agent represents the maximum value they can guaranteee for themselves by partitioning all goods into n bundles (one for each agent) and receiving the least-valued bundle, where n is the total number of agents. Agents with identical valuation functions are considered the same type.

While MMS allocations provide a strong fairness guarantee for all agents, they are not guaranteed to exist for all instances [Procaccia and Wang, 2014]. Notably, when all agents have identical valuation functions-i.e., they belong to a single type-an MMS allocation is trivially guaranteed.

However, in settings with three or more agents and just two distinct types, MMS allocations may not always exist [Feige et al., 2021].

These non-existence results have shifted the focus toward approximate MMS guarantees. In this framework, an allocation is called α-MMS if every agent receives a bundle they value at least α times their MMS value. Over the last decade, extensive research has established the existence of allocations with an approximation guarantee of 3 4 + 3 3836 -MMS; see, e.g., [Barman and Krishnamurthy, 2020; Ghodsi et al., 2018; Garg et al., 2019; Amanatidis et al., 2017a; Kurokawa et al., 2018; Garg and Taki, 2021; Akrami and Garg, 2024]. This remains the best-known guarantee, even in settings with agents grouped into two distinct types.

Improving MMS approximations has proven to be a significant challenge, with progress being relatively slow. It remains unclear how to substantially improve the approximation ratio beyond 34 for all instances. The existence of 34 -MMSwas first established in [Ghodsi et al., 2018], and despite extensive efforts by multiple researchers, the ratio has only been slightly improved over the past eight years. This naturally leads to the question: Can we achieve better approximation ratios for intermediate cases where the number of agent types lies between 1 and n?

In this paper, we address this question affirmatively by providing novel algorithms that achieve a 45 -MMS allocation for two agent types, and a 16 21 -MMS allocation for three agent types. Beyond their theoretical significance, these results hold practical importance, as many real-world resource allocation scenarios involve agents grouped into a few distinct categories based on shared preferences or needs. For example, co-working spaces may group users as freelancers, startups, or larger companies, while land allocation might involve agricultural, residential, or commercial priorities. These cases often involve just two or three types of agents, making it crucial to design allocation mechanisms that exploit this structure for better outcomes. These special cases have also been explored in several prior works, often motivated by additional intriguing applications; see, e.g., [Garg et al., 2023; Garg et al., 2024; Ghosal et al., 2025].

A key innovation in our work lies in leveraging the 1MMS partition for valuation function of the majority type, the type with the largest number of agents. We adapt this partition to achieve better approximations. This departs significantly from traditional methods that typically begin with variations of bag-filling algorithms. Similar to [Akrami and Garg, 2024], we aim to ensure that each allocated bag contains exactly one high-valued item, enabling tighter bounds for subsequent bag-filling steps. However, rather than constructing these bags from scratch, we modify the initial MMS partition of the majority type.

Specifically, if some bags contain multiple high-valued items while others have none, we swap items to ensure that every bag contains exactly one high-valued item. The details of this process are provided in Section 3. While this process may compromise the 1-MMS property for the majority type, we ensure that the value of each modified bag remains at least 4 5 times the MMS for the majority type. Therefore, any of these bags can be allocated to the agents from majority type, but the other types will determine which bags. Essentially, we prioritize assigning bags that are considered low-valued by the other types to the majority type, thereby maximizing the remaining value for the non-majority types.

When there are three types of agents, the allocation problem becomes more complicated, as the two non-majority types might disagree on which bags should be allocated to the majority type. In such cases, we categorize the bags into four classes based on their value to the non-majority types: valuable to both, valuable to one but not the other, valuable to neither. By comparing the number of bags in these categories with the number of agents in each type, we develop tailored solutions for all possible cases. The most challenging scenario arises when many bags are low-valued for both non-majority types, leaving them undesired by either. In such instances, we aggregate all items from these bags and employ a sophisticated bag-filling algorithm to ensure that all agents receive allocations that meet their MMS requirements. The algorithms that achieve improved approximation guarantees for scenarios with two or three agent types are detailed in Section 4.

While our approach is effective for instances with two and three types, it faces scalability challenges as the number of types increases. Specifically, the number of bag categories grows significantly, and the resulting case analysis becomes increasingly intricate. Therefore, this paper focuses exclusively on scenarios involving two or three agent types. Notably, barring the MMS value computation for each type through a PTAS [Woeginger, 1997], all our algorithms run in polynomial time in n and m.

In Section 2, we give formal definitions, notations, and preliminaries. Proofs for all claims, lemmas, propositions, and theorems marked with a † can be found in the supplementary material.

1.1 Additional RelatedWork

Given the intense study of the MMS fairness notion and its special cases and variants, we focus here on closely related work. Computing the MMS value of an agent is NPhard. However, a Polynomial Time Approximation Scheme (PTAS) exists for this computation [Woeginger, 1997]. As noted earlier, MMS allocations are not guaranteed to exist for more than two agents with two distinct types [Procaccia and Wang, 2014; Feige et al., 2021]. This non-existence has motivated the exploration of approximate MMS allocations to ensure their existence. A series of works has established the current best approximation factor of 34 + 3 3836 for all instances [Akrami and Garg, 2024].

Several works have examined special cases. For example, when m ≤ n + 3, where m is the total number of goods, an MMS allocation always exists [Amanatidis et al., 2017b]. This bound was later improved to m ≤ n + 5 [Feige et al., 2021]. For n = 2, MMS allocations always exist [Bouveret and Lemaˆıtre, 2016]. For n = 3, the MMS approximation was improved from 34 [Procaccia and Wang, 2014] to 78 [Amanatidis et al., 2017b] to 89 [Gourv`es andMonnot, 2019], and then to 11 12 [Feige and Norkin, 2022a]. For n = 4, 4 5 - MMS allocations exist [Ghodsi et al., 2018]. For n ≥ 5, the best known factor is the general 34 + 3 3836 bound [Akrami and Garg, 2024]. For the special case of (non-personalized) bivalued instances, MMS allocations are known to exist [Feige, 2022]. Finally, given only three agents, an 11 12 -MMS exists [Feige and Norkin, 2022b], and given two agents, the cut-and-choose protocol guarantees a 1-MMS allocation.

Chores The MMS notion can naturally be defined for the fair division of chores, where items provide negative value. As with goods, MMS allocations for chores do not always exist [Aziz et al., 2017; Feige et al., 2021]. However, substantial research on approximate MMS allocations for chores has yielded significant results. Notable works [Aziz et al., 2017; Barman and Krishnamurthy, 2020; Huang and Lu, 2021; Huang and Segal-Halevi, 2023] have led to the existence of 13 11 -MMS allocations. For three agents, 19 18 -MMS allocations exist [Feige and Norkin, 2022a], and for factored instances, MMS allocations are guaranteed [Garg et al., 2025]. Additionally, for the special case of personalized bivalued instances, 15 13 -MMS allocations exist [Garg et al., 2025].

2 Preliminaries

In this paper, we primarily follow the notations used in previous work [Akrami et al., 2023] to be consistent with the literature. However, beginning with Definition 6, we introduce new notations that are specific to our work.

For any positive integer n, let [n] = {1, 2, . . . , n}, and for two positive integers i, j where i < j, let [i, j] = {i, i + 1, · · · , j}. A fair division instance I = (N,M, V) consists of a set of agents N = [n], a set of goods M = [m], and a vector of valuation functions V = (v1, v2, . . . , vn). Each valuation function vi : 2M → R≥0 represents agent i's preference over subsets of goods. We assume additive valuations, so for all S ⊆ M, vi(S) = ∑g∈S vi({g}). For ease of notation, for all g ∈ M, we use vi(g) or vi,g instead of vi({g}). Likewise, throughout this paper, we use the notation vi(g, g′ ) as a shorthand for vi({g, g′ }).

For a set S of goods and a positive integer d, let Πd(S) be the set of all partitions of S into d bundles. The maximin share (MMS) value for a valuation v is defined as:

When the instance I = (N,M, V) is clear from the context, we use the notation MMSnvi (M) as MMSi(I) or MMSi.

For agent i, an MMS partition P i = (P i 1 , P i 2 , . . . , P in ) satisfies MMSi = minj∈[n] vi(P i j ). An allocation X is MMS if vi(Xi) ≥ MMSi for all i ∈ N. More generally, for 0 < α ≤ 1, an allocation X is α-MMS if vi(Xi) ≥ α·MMSi for all i ∈ N.

For a list of items H, let |H| denote the number of items in the list. Given positive integers i ∈ [|H|] and j ∈ [|H|] with i < j, let H[i : j] denote the subset of items in H from the i-th to the j-th position, inclusive. Also, let H[-1] represent the last item in the list.

Definition 1 (Ordered instance). An instance I = (N,M, V) is ordered if there exists a permutation of the goods (g1, g2, . . . , gm) such that for all agents i ∈ N, vi(g1) ≥ vi(g2) ≥ . . . ≥ vi(gm). For any fair division instance I = ([n], [m], V), the transformation order(I) produces an ordered instance I ′ = ([n], [m], V ′ ), where for each i ∈ [n] and j ∈ [m], v′i (j) is the jth largest value in the multiset {vi(g) | g ∈ [m]}.

Theorem 1 (Theorem 2 in [Barman and Krishnamurthy, 2020]). Given an instance I and an α-MMS allocation of order(I), one can compute an α-MMS allocation of I in polynomial time.

Theorem 1 implies the transformation order is α-MMSpreserving. For ordered instances I, we assume without loss of generality that vi(1) ≥ vi(2) ≥ . . . ≥ vi(m) for all i ∈ [n].

Definition 2 (Normalized instance). An instance I = (N,M, V) is normalized if for all agents i ∈ N and all bundles P i j in an MMS partition of i, vi(P i j ) = 1. For any fair division instance I, the transformation normalize(I) computes a normalized instance I ′ = (N,M, V ′ ) by determining the MMS partition P i for each agent i ∈ N and rescaling valuations: for all j ∈ [n] and g ∈ P i j , set v′i,g = vi,g/vi(P i j ).

Lemma 1 (Lemma 4 in [Akrami et al., 2023]). Let I ′ = ([n], [m], V ′ ) = normalize(I = ([n], [m], V)). Then for any allocation A, vi(Ai) ≥ v′i (Ai) · MMSnvi for all i ∈ N.

Note that in a normalized instance, the MMS value for every agent is 1. Consequently, Lemma 1 establishes that normalize is α-MMS-preserving. This means that if an allocation A is an α-MMS allocation for the normalized instance I ′ , then A is also an α-MMS allocation for the original instance I. Note that in a normalized instance, the total value of all items satisfies v′i ([m]) = ∑j∈[n] v′i (P i j ) = n for every agent i ∈ [n]. Also, for each agent i and for every MMS partition Q of agent i, we have v′i (Qj) = 1 ∀j ∈ [n].

Given an instance I, a reduction rule R(I) allocates a subset S ⊆ M of goods to an agent i and produces a new instance I ′ = (N \ {i},M \ S, V).

Definition 3 (Valid reductions). A reduction rule R is a valid α-reduction if, for R(I) = (N ′ , M ′ , V), where {i} = N \N ′ and S = M \ M ′ :

1. vi(S) ≥ α · MMS|N| vi (M), and
2. MMS|N|-1 vj (M ′ ) ≥ MMS|N| vj (M) for all j ∈ N ′ .

If R is a valid α-reduction and an α-MMS allocation A exists for R(I), then an α-MMS allocation for I can be constructed by allocating S to i and distributing the remaining goods as in A. We now describe three standard transformations, known as reduction rules, and demonstrate their validity.

Definition 4 (Reduction rules). Consider an ordered fair division instance (N,M, v), where M := {g1, . . . , g|M|} and vi,g1 ≥ . . . ≥ vi,g|M| for every agent i. Define

1. S1 := {g1}. 2. S2 := {g|N|, g|N|+1} if |M| ≥ |N| +1, else S2 := ∅. 3. S3 := {g2|N|-1, g2|N|, g2|N|+1} if |M| ≥ 2|N|+1, else S3 := ∅.

Reduction rule Rk(α): If vi(Sk) ≥ α · MMSi for some agent i, then give Sk to i. A fair division instance is called Rk(α)-irreducible if Rk(α) cannot be applied, i.e., vi(Sk) < α · MMSi for every agent i. An instance is called totally-αirreducible if it is Rk(α)-irreducible for all k ∈ [3].

Definition 5. The reduceα operation takes an ordered fair division instance as input and iteratively applies the reduction rules R1(α), R2(α), and R3(α) in any order until the instance becomes totally-α-irreducible.

Lemma 2 (Lemma 3.1 in [Garg and Taki, 2021]). For an ordered instance and for 0 ≤ α ≤ 1, R1(α), R2(α), and R3(α) are valid α-reductions.

Lemma 3 (Lemmas 2 and 3 in [Akrami et al., 2023]). Let I := ([n], [m], V) be an ordered instance where vi,1 ≥ . . . ≥ vi,m for each agent i. If I is totally-α-irreducable, then m≥ 2n, and for each agent i and every good j > (k - 1)n, we have vi,j < α · MMSi/k.

Lemma 4 (Lemma 6 in [Akrami et al., 2023]). Let ([n], [m], V) be an ordered and normalized fair division instance. For all k ∈ [n] and agent i ∈ [n], if vi(k) + vi(2n - k + 1) > 1, then vi(2n - k + 1) ≤ 1/3 and vi(k) > 2/3.

Definition 6. For a fair division instance I, define ̂ Iα := order(normalize(reduceα(order(I)))) as the ordered, normalized, totally-α-irreducible (ONIα) instance of I.

Lemma 5. † Let I be a fair division instance, and ̂ Iα be the ONIα instance of I. ̂ Iα is ordered, normalized, and totallyα-irreducible. Furthermore, the transformation of I to ̂ Iα is α-MMS-preserving, i.e., a α-MMS allocation of ̂ Iα can be used to obtain a α-MMS allocation of I.

Definition 7. Let ̂ Iα := ([n], [m], V) be an ONIα instance, where vi,1 ≥ vi,2 ≥ . . . ≥ vi,m for all i ∈ [n]. The items are categorized into high-valued, middle-valued, and low-valued items as follows:

1. High-valued (HV) items: HV = [n].
2. Middle-valued (MV) items: MV = [n + 1, 2n].
3. Low-valued (LV) items: If m = 2n1 , then LV = ∅; otherwise, LV = [2n + 1, m].

1 By Lemma 3, m ≥ 2n.

Corollary 1 (of Lemma 3). In anONIα instance ̂ Iα, for each agent i and every good j: if j ∈ HV , then vi(j) < α; if j ∈ MV , then vi(j) < α/2; and if j ∈ LV , then vi(j) < α/3.

Definition 8 (Single-High-Valued (SHV) Partition). Given an ONIα instance ̂ Iα := ([n], [m], V), a partition of [m], A = {A1,A2, . . . ,An} is a Single-High-Valued (SHV) partition if each bundle in A contains exactly one HV item.

Definition 9 (SHV α-MMS Partition). Given an ONIα instance ̂ Iα := ([n], [m], V), a partition of [m], A = {A1,A2, . . . ,An} is an SHV α-MMS partition if A is an SHV partition and satisfies vi(Ai) ≥ α for all i ∈ [n].

Definition 10. Agents are classified into types based on their valuation functions. All agents sharing the same valuation function v : 2m →R≥0 are of the same type.

Definition 11. A k-type instance I = ([n], [m], V) is a fair division instance involving k distinct agent types, characterized by the set of valuation functions V = {v1, v2, . . . , vk}. Each agent's valuation function belongs to this set, i.e., Vi ∈ V for all i ∈ [n]. For each j ∈ [k], type j agents are defined as those whose valuation function is vj .

Remark 1. A k-type instance can be fully described by I := ([n], [m], {T1, . . . , Tk}, {v1, . . . , vk}), where {v1, v2, . . . , vk} represents the set of valuation functions for the k types, and Tj denotes the number of type j agents for any j ∈ [k]. Since each agent belongs to exactly one of the k types, ∑j∈[k] Tj = n. We also assume that the type sizes are ordered as T1 ≥ T2 ≥ · · · ≥ Tk.

Claim 1. Let I be a k-type instance. The ONIα instance of I, ̂ Iα is a k′ -type instance where k′ ≤ k.

Proof. In the instance I, agents of the same type share the same valuation function. Consequently, they experience the same transformations under the operations order, normalize, and reduceα, and retain the same valuation function in ̂ Iα. However, agents from different types may converge to the same valuation function; for instance, if the valuations of some types are permutations of the same set of m numbers, they become identical after the order transformation. Consequently, the number of types can only decrease, and ̂ Iα becomes a k′ -type instance where k′ ≤ k.

Definition 12. In an α-MMS problem, given a k-type ONIα instance, a type i agent is said to claim a bundle of items B if vi(B) ≥ α. Furthermore, a type i is considered to claim a bundle if any type i agent claims the bundle.

In Sections 3 and 4.1, where we study the 45 -MMS problem, type i claims a bundle B if vi(B) ≥ 45 . In Section 4.2, as we consider the 16 21 -MMS problem, type i claims B if vi(B) ≥ 16 21 .

3 SHV 4 5 -MMS Partition of Same-type Agents

Given a 1-type ONIα instance, where v represents the common valuation function shared by all agents, the objective is to find an SHV 45 -MMS partition. Since all agents belong to the same type, the MMS value is identical for each agent, i.e., MMSi = MMSnv for all i ∈ [n]. Moreover, having identical valuations implies an MMS partition for any single agent serves as the MMS partition for the entire instance.

The PTAS described in [Woeginger, 1997] for computing the MMS partition of a single agent can be utilized to obtain a (1 - ϵ)-MMS partition in poly( 1ϵ ) time. By choosing ϵ = min(0.04, 1 5n ), we can compute a (1 - ϵ)-MMS partition in polynomial time. However, such a partition may include bags with multiple HV items, which violates the current problem's constraints. To address this, we design Algorithm 1 to modify the initial partition, ensuring an SHV 4 5 -MMS solution for same-type agents.

Main ideas of Algorithm 1: At a high level, A represents the set of flawed bags, while A′ consists of correct bags. A bag B is deemed correct if it contains exactly one HV item and v(B) ≥ 45 ; otherwise, it is considered flawed. As long as there exists at least one flawed bag, we iteratively select a subset of flawed bags and ensure that at least one of them is corrected in each iteration.

Algorithm 1 SHV 45 -MMS of same-type agents

• 1: Input: A1-typeONIα instance I = ([n], [m], {n}, {v}), α = 4 5 2: Output: SHV 45 -MMS. 3: ϵ ←min(0.04, 1 5n ). 4: A0 ← (1 - ϵ) - MMS partition of an agent. 5: A′ ← bags in A0 with one HV item. 6: A←A0 \ A′ . 7: while |A′ | < n do 8: Let a ∈ A be an arbitrary bag with k > 1 HV items 9: Let H = [h1, · · · , hk] be the list of HV items in a sorted in an ascending order of valuation. 10: Let B = {b1, · · · , bk-1} ⊂ A be k - 1 bags without any HV items. 11: A←A \ {a ∪B}. 12: Let G = {g1, · · · , gk-1} be k - 1 highest valued items in ∪b∈Bb. 13: Swap each HV item in H[1 : k - 1] with a unique item in G. 14: Denote updated bags as ¯a,¯b1, · · · ,¯bk-1. 15: if v(¯a) < 4 5 then 16: P ← items in ∪k-1 j=1 ¯bj excluding HV items H[1 : k - 1]. 17: Construct k - 1 new empty bags B′ = {b′1 , · · · , b′k-1 } 18: Put one HV item from H[1 : k - 1] in each bag of B′ . 19: FromP fill each bag in ¯a∪B′ until it is claimed. 20: Add ¯a and all bags of B′ to A′ . 21: else 22: Add ¯a and any bag in {¯b1, · · · , ¯bk-1} containing one HV to A′ , and the rest to A. return A′

Claim 2. † At any point in the algorithm, the following invariants hold:

1. The total number of bags satisfies |A| + |A′ | = n.

1. For any a ∈ A, a does not contain exactly one HV item and v(a) ≥ 1 - ϵ.
2. For any a ∈ A′ , a contains exactly one HV item and v(a) ≥ 4 5 .
3. If there exists a bag a ∈ A that contains k HV items, then there must be at least k - 1 bags in A that do not contain any HV items.

Lemma 6. † If in some iteration of the while loop, after the swapping step, v(¯a) < 45 , the algorithm never runs out of items while performing bag-filling in line 19.

Combining these results, we arrive at the following theorem.

Theorem 2. Given a 1-type ONIα instance, Algorithm 1 returns an SHV 4 5 -MMS partition.

4 ImprovedMMS Approximations

This section presents the main results, including Theorems 4 and 5. Together with Lemma 5 and Claim 1, these results lead to the following general theorem:

Theorem 3. For a k-type fair division instance I, the ONIα instance of I results in a k′ -type instance with k′ ≤ k, then:

• If k′ = 2, a 45 -MMS allocation exists.
• If k′ = 3, a 16 21 -MMS allocation exists.

Corollary 2. For any 2-type fair division instance, a 45 -MMS allocation exists.

Corollary 3. For any 3-type fair division instance, a 16 21 -MMS allocation exists.

4.1 45 -MMS for 2-type ONIα Instance

Given a 2-type ONIα instance, Algorithm 2 first constructs a 1-type ONIα instance ̂ I based on the valuation function of the majority type. It computes the SHV 45 -MMS partition of ̂ I and sorts the n bags in ascending order according to the minority type's valuation. The first T1 bags are assigned to type 1 agents. The remaining T2 bags are assigned to type 2 agents if all these bags are claimed by type 2 agents. If any bag is left unclaimed, the items from all T2 bags are pooled together. From this pool, each of the T2 HV items is placed into a new empty bag, and the bags are filled until each of them is claimed by type 2 agents. This process is called bagfilling.

Theorem 4. Given a 2-type ONIα instance, Algorithm 2 returns a 4 5 -MMS.

Proof. Note that α = 45 . In Algorithm 2, first we obtain A, an SHV 4 5 -MMS partition of ̂ I. Note that type 1 agents claim all bags in A. Then type 2 sorts all the n bags of A in an ascending order of valuation, therefore v2(Aj) ≤ v2(Aj+1) for j ∈ [n - 1]. Let F = {Aj}T1 j=1 be the collection of the first T1 bags. Each bag in F is assigned to a unique type 1 agent. If v2(AT+1) ≥ α, since bags are sorted in ascending order, v2(Aj) ≥ α for all j ∈ [T1 + 1, n]. Therefore, all the remained bags are claimed by type 2, and we'll assign them to the remained agents. In this case the assignment is

Algorithm 2 45 -MMS for 2 types

• 1: Input: 2-type ONIα instance I = ([n], [m], {T1, T2}, {v1, v2}), α = 45 .
• 2: Output: 45 -MMS.
• 3: Define a 1-type ONIα instance ̂ I = ([n], [m], {n}, {v1})
• 4: Let A be the SHV 4 5 -MMS partition after running Algorithm 1 on ̂ I.
• 5: Sort bags of A by type 2 in an ascending order of valuation.
• 6: Assign the first T1 bags to type 1 agents.
• 7: if type 2 agents claim all remaining bags then
• 8: Assign all the remained bags to type 2 agents.
• 9: else
• 10: P ← items from all remained bags.
• 11: Put each HV item of P in a new bag.
• 12: From the remaining items in P, fill each new bag until a type 2 agent claims it, then assign it to her.

a 45 -MMS as all the assigned bags are claimed by the corresponding agents.

On the other hand if v2(AT+1) < α, items in the remained bags are pooled in P , and since valuations are in an ascending order, v2(Aj) < α for all j ∈ [T1]. Therefore

Note that since each bag in A has exactly one HV item, we have exactly n - T1 HV items in P, and as T2 = n - T1, the number of remained HV items is exactly the same as the number of type 2 agents. We construct T2 new empty bags, and by putting each HV item in a separate bag, the remained pool of items will not have any HV item any more. By Corollary 1 the value of each remained item in the pool is at most α2 . When filling a bag until type 2 claims it, its value for type 2 cannot exceed 3α 2 for the following reason; before the last item was added, the bag's value was less than α, and the last item contributes at most α2 . Let Anew be the set of bags created during the bag filling phase. We have that

Set of bags assigned to all agents is {Aj}T1 j=1 ∪Anew. Putting Eq. (1) and Eq. (2) together we obtain

where we used α = 4 5 , T1 + T2 = n and T1 ≥ n2 since type 1 agents are the majority by assumption. The total value of the assigned bags is upper bounded by n, the total available value in a normalized instance. Therefore, we never run out of goods while bag filling or, equivalently, all type 2 agents receive a claimed bag. Therefore, this assignment is a 4 5 -MMS.

4.2 16 21 -MMS for 3-type ONIα Instance

Given a 3-type ONIα instance, Algorithm 3 first constructs a 1-type ONIα instance ̂ I based on the valuation function of the majority type, and computes the SHV 45 -MMS partition of ̂ I, A. For any choice of α, each bag in A is either liked by more than α by both types 2 and 3, or just one of them, or none. Based on the valuations of types 2 and 3, we partition the n bags in A into four classes C1,C2,C3 and C4 using Algorithm 4. By choosing α = 16 21 , type 2 agents claim all the bags in C2 and C4, type 3 agents claim all the bags in C3 and C4, and type 1 agents claim all the bags in A = ⋃4i=1 Ci.

Finally, by comparing the number of bags in these classes with the number of agents of each type, we identify four cases. The specific approach for handling each case to achieve a 16 21 -MMS is detailed in Algorithm 3. Notably, the last case addressed in this algorithm presents the greatest challenge and depends on executing Algorithm 5. We analyze each case of the algorithm separately and show that, in all four cases, Algorithm 3 guarantees a 16 21 -MMS allocation. Consequently, we derive the following theorem.

Theorem 5. Given a 3-type ONIα instance, Algorithm 3 returns a 16 21 -MMS.

After allocating T2 bags from C2 to all type 2 agents and T3 bags from C3 to all type 3 agents, the remaining bags are assigned to all type 1 agents. Since all bags in A are claimed by type 1 agents, all bags in C2 by type 2 agents, and all bags in C3 by type 3 agents, this allocation achieves a 16 21 -MMS guarantee.

Let A′ denote the set of Ti arbitrary bags allocated to type i agents fromCi. After this allocation, only two types of agents remain. Type 1 agents will receive T1 bags from A \ A′ . As each of the bags in A has a value of at least 45 for type 1 agents, all of them are claimed by these agents. Since all the bags in A′ are valued at less than α by type i′ agents, the loss incurred by type i′ is minimal. Essentially, this scenario is equivalent to considering type i′ agents forfeiting these bags to type 1 agents in a two type setting where the number of type 1 agents is T1 + Ti.

Lemma 7. † If ∃i, i′ ∈ {2, 3} s.t. i ̸= i′ , |Ci| > Ti and |Ci′ | ≤ Ti′ , Algorithm 3 returns a 16 21 -MMS.

After assigning all bags in C1, C2, C3 to some agents of types 1, 2, 3 respectively, we are remained with bags in C4 that are claimed by all types. Hence we can assign them to any remaining agents, and obtain a 16 21 -MMS assignment.

Definition 13. A type is considered saturated if every agent of that type has received a claimed bag in the assignment; otherwise, it is unsaturated.

Definition 14. A bag B is safe for type i agents if vi(B) ≤ 1.

Algorithm 3 16 21 -MMS for 3 types

• 1: Input: A 3-type ONIα instance I = ([n], [m], {T1, T2, T3}, {v1, v2, v3}), α = 16 21 . 2: Output: 16 21 -MMS. 3: Define a 1-type ONIα instance ̂ I = ([n], [m], {n}, {v1}) 4: Let A be the SHV 4 5 -MMS partition after running Algorithm 1 on ̂ I. 5: Using Algorithm 4, partition bags of A into C1, C2, C3, C4. 6: if |C2| > T2, |C3| > T3 then // Case 1 7: Assign T2 bags fromC2 to all type 2 agents. 8: Assign T3 bags fromC3 to all type 3 agents. 9: Assign the remained bags to all type 1 agents. 10: if ∃i, i′ ∈ {2, 3}s.t.i ̸= i′ , |Ci| > Ti, |Ci′ | ≤ Ti′ : then // Case 2 11: Assign Ti bags of Ci to all type i agents. 12: Type i′ sorts all remained bags in an ascending order of valuation. 13: Assign the first T1 bags to type 1 agents. 14: if all remained bags are claimed by type i′ then 15: Assign all the remained bags to type i′ agents. 16: else 17: P ← items from all remained bags. 18: Put each HV item of P in a new bag. 19: Fill each new bag with remaining items from P until a type i′ agent claims it, then assign it to her. 20: else 21: if |C1| ≤ T1 then // Case 3 22: Assign all bags in C1 to some type 1 agents. 23: Assign all bags in C2 to some type 2 agents. 24: Assign all bags in C3 to some type 3 agents. 25: Assign all remaining bags in C4 to any remaining agents. 26: if |C1| > T1 then // Case 4 27: Assign T1 bags in C1 to all agents of type 1. 28: P ← items from all remained bags. 29: Let H = HV ∩P , M = MV ∩P , L = LV ∩P . 30: Run Algorithm 5 with α = 16 21 .

After assigning T1 bags in C1 to all agents of type 1, type 1 is saturated. Let H, M, and L denote the lists of high-valued, middle-valued, and low-valued items, respectively, that remain in the remaining n - T1 bags. Each list is ordered in descending order of valuation. Since each assigned bag to type 1 had exactly one HV item, |H| = n - T1. On the other hand, since any number of middle-valued items might remain after the assignment of bags to the majority type, 0 ≤ |M| ≤ n. Finally, Algorithm 5 is invoked.

Main Ideas of Algorithm 5 The algorithm consists of two parts. Initially, both type 2 and type 3 are active and unsaturated. A type remains active until it meets one of the conditions specified in lines 13 or 16, or until it becomes saturated in the first part of the algorithm (by line 21). Once a type becomes inactive, it stays inactive; if none of these conditions are met, it may never become inactive.

Algorithm 4 Clustering bags of A

1: Input: A = {A1, · · · ,An}, α = 16 21 . 2: Output: A partition of bags in A into 4 classes C1, C2, C3, C4. 3: for i ∈ {1, 2, 3, 4} do Ci ← ∅ 4: for a ∈ A do 5: if v2(a) < α, v3(a) < α then C1 ← C1 ∪ {a}. 6: if v2(a) ≥ α, v3(a) < α then C2 ← C2 ∪ {a}. 7: if v2(a) < α, v3(a) ≥ α then C3 ← C3 ∪ {a} . 8: if v2(a) ≥ α, v3(a) ≥ α then C4 ← C4 ∪ {a} .

As the algorithm proceeds, items are grouped into bundles that are either immediately assigned to agents or saved for future assignment. In either case, the bundled items become unavailable and are removed fromH, M, and L, thereby reducing the number of available items. Consequently, at any given stage, H, M, and L represent the currently available high-valued, middle-valued, and low-valued items. The algorithm operates in two parts, as described below.

1. First Part: As long as there is an active type and remaining high-valued and middle-valued items, the algorithm constructs certain bundles that are safe for all active types. Each bundle contains one HV item and one MV item. The bags are either:
2. Assigned to an agent from an unsaturated type that claims the bag, or
3. Saved in F for the second part if no unsaturated type claims the bag.

This process continues until no high-valued or middlevalued items remain, or no active types remain. Given a set of available high-valued and middle-valued items H and M, where H ̸= ∅ and M ̸= ∅, type i becomes inactive (i.e., is no longer active) if it becomes saturated (by line 21), or if vi(M[1],H[-1]) > 1 and there exists no j such that α ≤ vi(M[j], H[-1]) ≤ 1, by lines 13 or 16. Recall that H[-1] is the least valued available HV item.

1. Second Part: When both types are inactive or either M = ∅ or H = ∅, the second part begins. The collection of bags F inherited from the first part consists of bags, each containing one HV and one MV item, with a total value of less than α for any unsaturated type. If H ̸= ∅, each remaining item in H is placed in a separate new bag and the bag is added to F .

The algorithm then picks an arbitrary bag from F and fills it with remaining items until an unsaturated type claims it. The bag is then assigned to an arbitrary agent belonging to an unsaturated type that claimed it. This bag-filling procedure repeats until all types are saturated.

Proposition 1. † Throughout the first part of the algorithm, as long as a type remains active, all saved and assigned bags are guaranteed to be safe for that type.

Lemma 8. In Algorithm 5, both types 2 and 3 get saturated.

Algorithm 5 Algorithm for Case 4

1: Let F ← ∅, active ← {2, 3}, unsaturated ← {2, 3}. // Part 1 begins 2: while H ̸= ∅ and M ̸= ∅ and active ̸= ∅ do 3: B ← {M[1],H[-1]}. 4: Let X = {i ∈ active | vi(B) > 1}. 5: if |X| = 0 then 6: if ∃j ∈ unsaturated, vj(B) ≥ α then 7: Assign B to a type j agent. 8: else, F ← F ∪ B. 9: if |X| = 1 then 10: Let i be the unique element of X. 11: if ∃j s.t. α ≤ vi(M[j], H[-1]) ≤ 1 then 12: Assign B′ = {M[j],H[-1]} to a type i agent. 13: else, active ← active \ {i}. 14: if |X| = 2 then 15: if ∃i ∈ X | ∄j : α ≤ vi(M[j],H[-1]) ≤ 1 then 16: active ← active \ {i}. 17: else 18: Let j be the largest index where for some i ∈ X, α ≤ vi(M[j], H[-1]) ≤ 1. 19: Assign B′ = {M[j],H[-1]} to type i.

• 20: If a bag is saved or assigned, remove its items from M and H.
• 21: If a type is saturated, remove it from active and unsaturated. // Part 2 begins
• 22: Place all the remaining items of H in a separate new bag and add the bag to F .
• 23: Let R = M ∪ L be the pool of remained items.
• 24: while unsaturated ̸= ∅ do
• 25: Choose a bag B from F, fill it with available items from R, and assign it to any agent of type in unsaturated upon claim.
• 26: Update F, R, and unsaturated.

By combining Lemma 8 with the fact that all bags assigned to type 1 agents have a value of at least 45 , it follows that Algorithm 3 obtains a 16 21 -MMS allocation in the fourth case.

5 Conclusion

In the fair division of indivisible goods, the maximin share is one of the most extensively studied fairness notions. Determining tight lower and upper bounds on the maximum α for which α-MMS allocations are guaranteed to exist remains a fundamental open problem. Since MMS allocations do not always exist even for instances with two agent types, our improved bounds represent a significant step forward in this area. To gain deeper insights into this problem, we focused on the special cases of two and three agent types. A compelling open question is whether uniform improvements can be achieved for any k < n types, with guarantees that decreases as k increases, surpassing the current best-known approximation of 3 4 + 3 3836 .

Acknowledgements

Parnian Shahkar was supported by NSF Grant CCF 2230414. Jugal Garg has been supported by NSF Grants CCF-1942321 and CCF-2334461.