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 3 4 for all instances. The existence of 3 4 -MMS was 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 4 5 -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].

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.

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 143 to ensure their existence. A series of works has established 144 the current best approximation factor of 3 4 + 3 3836 for all in-145 stances [Akrami and Garg, 2024]. 146 Several works have examined special cases. For example, 147 when m ≤ n + 3, where m is the total number of goods, 148 an MMS allocation always exists [Amanatidis et al., 2017b]. 149 This bound was later improved to m ≤ n + 5 [Feige et al., 150 2021]. For n = 2, MMS allocations always exist [Bouveret 151 and Lemaître, 2016]. For n = 3, the MMS approxima-152 tion was improved from 3 4 [Procaccia and Wang, 2014] to 7 8 153 [Amanatidis et al., 2017b] to 8 9 [Gourvès and Monnot, 2019], 154 and then to 11 12 [Feige and Norkin, 2022a]. For n = 4, 4 5 -155 MMS allocations exist [Ghodsi et al., 2018]. For n ≥ 5, the 156 best known factor is the general 3 4 + 3 3836 bound [Akrami and 157 Garg, 2024]. For the special case of (non-personalized) bi-158 valued instances, MMS allocations are known to exist [Feige, 159 2022]. Finally, given only three agents, an 11 12 -MMS ex-160 ists [Feige and Norkin, 2022b], and given two agents, the 161 cut-and-choose protocol guarantees a 1-MMS allocation. 162 Chores The MMS notion can naturally be defined for the 163 fair division of chores, where items provide negative value. 164 As with goods, MMS allocations for chores do not always 165 exist [Aziz et al., 2017; Feige et al., 2021]. However, substan-166 tial research on approximate MMS allocations for chores has 167 yielded significant results. Notable works [Aziz et al., 2017; 168 Barman and Krishnamurthy, 2020; Huang and Lu, 2021; 169 Huang and Segal-Halevi, 2023] have led to the existence of 170 13 11 -MMS allocations. For three agents, 19 18 -MMS allocations 171 exist [Feige and Norkin, 2022a], and for factored instances, 172 MMS allocations are guaranteed [Garg et al., 2025]. Ad-173 ditionally, for the special case of personalized bivalued in-174 stances, 15 13 -MMS allocations exist [Garg et al., 2025]. 175 2 Preliminaries 176 In this paper, we primarily follow the notations used in previ-177 ous work [Akrami et al., 2023] to be consistent with the lit-178 erature. However, beginning with Definition 6, we introduce 179 new notations that are specific to our work. 180 For any positive integer n, let [n] = {1, 2, . . . , n}, and for 181 two positive integers i, j where

and 184 a vector of valuation functions V = (v 1 , v 2 , . . . , v n ). Each 185 valuation function v i : 2 M → R ≥0 represents agent i's pref-186 erence over subsets of goods. We assume additive valuations, 187 so for all S ⊆ M , v i (S) = g∈S v i ({g}). For ease of nota-188 tion, for all g ∈ M , we use v i (g) or v i,g instead of v i ({g}). 189 Likewise, throughout this paper, we use the notation v i (g, g ′ ) 190 as a shorthand for v i ({g, g ′ }). For agent i, an MMS partition P i = (P i 1 , P i 2 , . . . , P i n ) satis-

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

is ordered if there exists a permutation of the goods

For any fair division instance

V), the transformation order(I) produces an

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

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, v i (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

Lemma 1 (Lemma 4 in [Akrami et al., 2023]).

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

. Also, for each agent i and for every MMS

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

If R is a valid α-reduction and an α-MMS allocation A 250 exists for R(I), then an α-MMS allocation for I can be con-251 structed by allocating S to i and distributing the remaining 252 goods as in A. We now describe three standard transforma-253 tions, known as reduction rules, and demonstrate their valid-254 ity.

Definition 5. The reduce α operation takes an ordered fair 268 division instance as input and iteratively applies the reduc-269 tion rules R 1 (α), R 2 (α), and R 3 (α) in any order until the 270 instance becomes totally-α-irreducible.

Lemma 2 (Lemma 3.1 in [Garg and Taki, 2021]). For an 272 ordered instance and for

and 273 R 3 (α) are valid α-reductions. 274 Lemma 3 (Lemmas 2 and 3 in [Akrami et al., 2023]). Let 275 I := ([n], [m], V) be an ordered instance where v i,1 ≥ . . . ≥ 276 v i,m for each agent i. If I is totally-α-irreducable, then m ≥ 277 2n, and for each agent i and every good j > (k -1)n, we 278 have v i,j < α • MMS i /k. 279 Lemma 4 (Lemma 6 in [Akrami et al., 2023]). Let 280 ([n], [m], V) be an ordered and normalized fair division in-281 stance. For all k ∈ [n] and agent i ∈ [n], if v i (k) + v i (2n -282 k + 1) > 1, then v i (2n -k + 1) ≤ 1/3 and v i (k) > 2/3. 283 Definition 6. For a fair division instance I, define I α := 284 order(normalize(reduce α (order(I)))) as the ordered, 285 normalized, totally-α-irreducible (ONI α ) instance of I. 286 Lemma 5. † Let I be a fair division instance, and I α be the 287 ONI α instance of I. I α is ordered, normalized, and totally-288 α-irreducible. Furthermore, the transformation of I to I α is 289 α-MMS-preserving, i.e., a α-MMS allocation of I α can be 290 used to obtain a α-MMS allocation of I. 291 Definition 7. Let I α := ([n], [m], V) be an ONI α instance, 292 where v i,1 ≥ v i,2 ≥ . . . ≥ v i,m for all i ∈ [n]. The items are 293 categorized into high-valued, middle-valued, and low-valued 294 items as follows: Corollary 1 (of Lemma 3). In an ONI α instance I α , for each agent i and every good j: if j ∈ HV , then v i (j) < α; if j ∈ M V , then v i (j) < α/2; and if j ∈ LV , then v i (j) < α/3. 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 v i (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 4 5 -MMS problem, type i claims a bundle B if v i (B) ≥ 4 5 . In Section 4.2, as we consider the 16 21 -MMS problem, type i claims B if v i (B) ≥ 16 21 .

Given a 1-type ONI α instance, where v represents the common valuation function shared by all agents, the objective is to find an SHV 4 5 -MMS partition. Since all agents belong to the same type, the MMS value is identical for each agent, i.e.,

. Moreover, having identi-352 cal valuations implies an MMS partition for any single agent 353 serves as the MMS partition for the entire instance.

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

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

Algorithm 1 SHV 4 5 -MMS of same-type agents 1:

Let a ∈ A be an arbitrary bag with k > 1 HV items 9:

be the list of HV items in a sorted in an ascending order of valuation. A ← A \ {a ∪ B}.

12:

Swap each HV item in H[1 : k -1] with a unique item in G. if v(ā) < 4 5 then 16:

Put one HV item from H[1 : k -1] in each bag of B ′ .

From P fill each bag in ā ∪ B ′ until it is claimed. 2. For any a ∈ A, a does not contain exactly one HV item and v(a) ≥ 1 -ϵ.

3. For any a ∈ A ′ , a contains exactly one HV item and v(a) ≥ 4 5 .

4. 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(ā) < 4 5 , 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.

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: all the remained bags are claimed by type 2, and we'll assign them to the remained agents. In this case the assignment is

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 T 1 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.

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 4 5 -MMS as all the assigned bags are claimed by the corre-424 sponding agents.

On the other hand if v 2 (A T +1 ) < α, items in the remained 426 bags are pooled in P , and since valuations are in an ascending 427 order, v 2 (A j ) < α for all j ∈ [T 1 ]. Therefore

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

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

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

Let A ′ denote the set of T i arbitrary bags allocated to type i agents from C i . After this allocation, only two types of agents remain. Type 1 agents will receive T 1 bags from A \ A ′ . As each of the bags in A has a value of at least 4 5 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

Algorithm 3 returns a 16 21 -MMS. Case 3: If |C 2 | ≤ T 2 , and |C 3 | ≤ T 3 , |C 1 | ≤ T 1 After assigning all bags in C 1 , C 2 , C 3 to some agents of types 1, 2, 3 respectively, we are remained with bags in C 4 that are claimed by all types. Hence we can assign them to any remaining agents, and obtain a 16 21 -MMS assignment. Case 4: If |C 2 | ≤ T 2 , and |C 3 | ≤ T 3 , |C 1 | > T 1 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 v i (B) ≤ 1. Algorithm 3 16 21 -MMS for 3 types 1: Input: A 3-type ONI α instance I = ([n], [m], {T 1 , T 2 , T 3 }, {v 1 , v 2 , v 3 }), α = 16 21 . 2: Output: 16 21 -MMS. 3: Define a 1-type ONI α instance I = ([n], [m], {n}, {v 1 }) 4: Let A be the SHV 4 5 -MMS partition after running Algorithm 1 on I. 5: Using Algorithm 4, partition bags of

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 from H, 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. if ∃j ∈ unsaturated, v j (B) ≥ α then 7:

Assign B to a type j agent.

else, F ← F ∪ B.

if |X| = 1 then 10:

Let i be the unique element of X. 17: else 18:

Let j be the largest index where for some i ∈ X, α ≤ v i (M [j], H[-1]) ≤ 1. 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.

Update F , R, and unsaturated.

By combining Lemma 8 with the fact that all bags assigned 562 to type 1 agents have a value of at least

4 5 , it follows that 563 Algorithm 3 obtains a 16 21 -MMS allocation in the fourth case. 564 5 Conclusion 565 In the fair division of indivisible goods, the maximin share 566 is one of the most extensively studied fairness notions. De-567 termining tight lower and upper bounds on the maximum 568 α for which α-MMS allocations are guaranteed to exist re-569 mains a fundamental open problem. Since MMS allocations 570 do not always exist even for instances with two agent types, 571 our improved bounds represent a significant step forward in 572 this area. To gain deeper insights into this problem, we fo-573 cused on the special cases of two and three agent types. A 574 compelling open question is whether uniform improvements 575 can be achieved for any k < n types, with guarantees that 576 decreases as k increases, surpassing the current best-known 577 approximation of 3 4 + 3 3836 . 578