Guaranteeing Maximin Shares: Some Agents Left Behind

1 Introduction

Fair division deals with the allocation of a set of resources to a set of agents in a fair manner [Brams and Taylor, 1996; Foley, 1967; Hosseini et al., 2020]. One of its most notable application domains deals with the allocation of indivisible (and non-shareable) goods. These applications arise, for example, in dividing inheritance and dispute resolution [Brams and Taylor, 1996], task assignment or course allocation [Budish, 2011], and have been popularized in recent years due to publicly accessible platforms such as Spliddit.

The most desirable fairness notion, envy-freeness, requires that each agent weakly prefers his own allocation to that of all other agents. A weaker notion, called proportionality, requires that each agent receives 1n of her valuation of all goods, where n is the total number of agents. Unfortunately, in the indivisible domain neither of these notions are guaranteed to exist: consider a single good and two interested agents. Neither envy-freeness nor proportionality can be satisfied as one agent is destined to remain empty handed.

A third fairness notion, proposed by Budish [2011], is the maximin share (MMS) guarantee, which can be seen as a generalization of the cut-and-choose protocol [Brams and Taylor, 1996]. In a nutshell, the maximin share is the value that an agent can guarantee by dividing the goods into n bundles, assuming that all other agents choose a bundle before she does. There is no reason to believe that such a bound can always be satisfied for all agents. It turns out that an MMS allocation does not always exist [Kurokawa et al., 2018], and even when it exists, computing an MMS partition is intractable [Bouveret and Lemaˆıtre, 2016]. Thus, several approximation techniques were developed to guarantee that each agent receives a fraction of her MMS. While these techniques are compelling, they may leave a large fraction of agents without their MMS guarantee.

We propose to circumvent this obstacle by taking an orthogonal direction based on the degree of fairness in the society of agents. Our goal is to find allocations that give a large fraction of agents their maximin share guarantee, possibly leaving a small fraction of agents behind (since MMS allocations do not always exist). This approach is related to ordinal approximations of MMS and is of interest in several application domains: resources in a hospital must be distributed among tasks/procedures in a manner that a subset of critical tasks can be fully accomplished; senior college students (as a fraction of all students) must be guaranteed seats in courses to avoid graduation delays.

Unfortunately, envy-freeness and proportionality cannot be approximated in this dimension. For instance, one may be interested in minimizing the fraction of envious agents. Envyfreeness (similarly proportionality) may leave almost all but one agent unsatisfied: consider n goods and n agents with identical valuations, having 1 - (n - 1)ϵ value for one good and ϵ for the rest. Any distribution of goods will leave n - 1 agents envious. Therefore, focusing on the maximin share guarantee we ask the following questions:

What fraction of agents can be guaranteed their MMS value? And can we compute allocations that guarantee MMS for the majority of the agents?

1.1 Our Contributions

We propose a novel fairness framework, called (α, β)-MMS, wherein α fraction of agents receive β approximations of their MMS value and investigate the interplay between the two approximation parameters. We establish the connection between (α, β)-MMS and ordinal approximations of MMS (Proposition 1), and investigate the computational boundaries of α and β as follows:

• Optimal MMS: We prove the existence of a family of instances where almost all agents do not receive their MMS by any optimal-MMS allocation that aims to maximize β for all agents. Our counterexample uses a quadratic number of goods, where n - 3 agents (n - 4 if n is odd) do not receive their MMS in any optimal-MMS allocation (Theorem 1).
• Computing ( n-1 n , β)-MMS: We devise a polynomial-time algorithm achieving (α, β)-MMS when α = n-1 n (Theorem 2). A consequence of this result is a tight approximation for n ≤ 4 that immediately implies an algorithm for computing MMSn+1 for n < 4 (Corollary 1).
• Existence of ( 2 3 , 1)-MMS: We prove the existence of ( 23 , 1)-MMS (Theorem 3), and provide an algorithm that achieves this bound in polynomial time for n < 9 (Theorem 4). A key implication of our result is the existence of allocations that guarantee MMS⌈3n/2⌉ , i.e., the value an agent receives by partitioning the goods into ⌈ 32 n⌉ bundles (Corollary 2). Our result significantly improves the best known guarantee of MMS2n-2 [Aigner-Horev and Segal-Halevi, 2019].

On the experimental front, we show that a simplified, polynomial-time variant of our algorithm satisfies a large fraction of agents on the most 'difficult' instances and this fraction grows as the ratio of goods to agents increases.

1.2 RelatedWork

On a high level, our approach is related to notions defined to measure the degree of fairness in a society of agents whether it pertains to minimizing the maximum or sum of envy [Chevaleyre et al., 2007; Chen and Shah, 2018; Nguyen and Rothe, 2014], minimizing envy ratio [Lipton et al., 2004], balancing the amount of envy experienced in a society, or promoting fairness through equitable allocations where agents receive the same level of utility [Schneckenburger et al., 2017; Freeman et al., 2019]. Another closely related line of work suggests the notion of counting instances of envious pairs-among several other plausible measuresas opposed to measuring the intensity of envy [Feldman and Kirman, 1974].

On a technical level, the non-existence of MMS allocations [Procaccia and Wang, 2014] and its intractability [Bouveret and Lemaˆıtre, 2016; Woeginger, 1997] has given rise to a number of approximation techniques. These algorithms guarantee that each agent receives an approximation of their maximin share. Recently, Nguyen et al. [2017] gave a Polynomial Time Approximation Scheme (PTAS) for a notion defined as optimal-MMS, that is, the largest value, β, for which each agent i receives the value of βMMSi. Since the number of possible partitions is finite, an optimal-MMS allocation always exists, and it is an MMS allocation if β ≥ 1. The current best results guarantee β ≥ 2/3 [Kurokawa et al., 2018; Garg et al., 2018] and β ≥ 3/4 [Garg and Taki, 2020; Ghodsi et al., 2018] in general, and β ≥ 7/8 [Amanatidis et al., 2017] and β ≥ 8/9 [Gourv`es and Monnot, 2019] in the case of three agents.

2 Preliminaries

Let N = {1, . . . , n} be a set of agents and M denote a set of m indivisible goods, where m > n. We denote the value of agent i ∈ N for good g ∈ M by vi(g) ≥ 0. We assume that the valuation functions are additive; that is, for each subset G ⊆ M, vi(G) = ∑g∈G vi(g). An instance of the problem is I = 〈N,M, V 〉 where V is the valuation profile of agents. An allocation A = (A1, . . . , An) is an n-partition of M that allocates the bundle of goods in Ai to each agent i ∈ N.

Definition 1 (Envy-freeness). An allocation A is envy-free (EF) if for every pair of agents i, j ∈ N, vi(Ai) ≥ vi(Aj). An allocation A is envy-free up to one good (EF1) if for every pair of agents i, j ∈ N such that Aj ̸= ∅, there exists some good g ∈ Aj such that vi(Ai) ≥ vi(Aj \ {g}). An allocation A is envy-free up to any good (EFX) if for every pair i, j ∈ N such that Aj ̸= ∅, for any good ∀g ∈ Aj, vi(Ai) ≥ vi(Aj \ {g}). These definitions are due to Foley [1967], Budish [2011], and Caragiannis et al. [2016] respectively.

Definition 2 (Maximin Share Guarantee). Let Πk(M) denote the set of k-partitions of M. The k-maximin share guarantee of agent i ∈ N on Πk(M) is

where [k] = {1, . . . , k}. Intuitively, this is the minimum value that can be guaranteed if agent i partitions the goods into k bundles and chooses the least valued bundle.

An allocation A = (A1, . . . ,Ak) ∈ Πk(M) is an MMSk allocation if and only if ∀i ∈ N, vi(Ai) ≥ MMSki . Note that MMSni (M) ≤ vi(M) n since proportionality implies MMS. When it is clear from the context, we write MMSi instead of MMSni (M) and simply refer to it as agent i's MMS value.

Definition 3 (Optimal-MMS). While an MMS allocation does not always exist, an optimal relaxation of MMS guarantees that agents receive a fraction of their MMS value [Nguyen et al., 2017]. Given an instance I = 〈N,M, V 〉, the optimal-MMS value is defined by

By definition, an allocation that gives each agent a λ∗ (I) fraction of its MMSni (M) value is guaranteed to exist.

Ordered instance. An instance is ordered when all agents agree on the linear ordering of the goods, irrespective of their valuations. Formally, I is an ordered instance if there exists an ordering of goods, (g1, g2, . . . , gm) such that for all agents i ∈ N we have vi(g1) ≥ vi(g2) ≥ . . . ≥ vi(gm). Bouveret and Lemaˆıtre [2016] showed that ordered instances are the 'hardest' for achieving MMS. In fact, these instances are the only known structures for which MMS does not exist [Kurokawa et al., 2018]. The next lemma states that given an unordered instance, it is always possible to generate a corresponding ordered instance in polynomial time. Furthermore, if the ordered instance admits an MMS allocation, the original instance also admits an MMS allocation which can be computed in polynomial-time.

Lemma 1 ([Barman and Krishna Murthy, 2017]). Let I ′ = 〈N, M, V ′ 〉 be an ordered instance constructed from the original instance I = 〈N,M, V 〉. Given allocation A′ on I ′ , a corresponding allocation A on I can be computed in polynomial time such that for all i ∈ N, vi(Ai) ≥ v′i (A′i ).

Scale invariance. The scale invariance property of MMS states that if an agent's valuations are scaled by a factor, then its MMS value scales by the same factor.

Lemma 2 ([Ghodsi et al., 2018]). Let I = 〈N,M, V 〉 be an instance and c > 0 be a real scalar. Let I ′ = 〈N,M, V ′ 〉 be constructed so that v′i (g) = cvi(g) for all g ∈ M. Then MMS′ k i (M) = cMMSki (M).

Thus, an instance I = 〈N,M, V 〉 and a real value k can be scaled to form a new instance I ′ = 〈N,M, V ′ 〉, such that for each agent i ∈ N, v′i (g) = k vi(M) vi(g), and v′i (M) = k.

Valid reduction. We call the act of removing a set Ai ⊆M of goods and an agent i a valid reduction if the following two conditions hold: i) vi(Ai) ≥ MMSni (M) and ii) ∀j ∈ N \ {i}, MMSn-1 j (M \ Ai) ≥MMSnj (M).

Lemma 3 ([Garg et al., 2018]). Given an ordered instance I = 〈N,M, V 〉 with |N| = n such that MMSni ≤ 1, if vi({gn, gn+1}) ≥ 1, then removing Ai = {gn, gn+1} and agent i forms a valid reduction. Similarly, the removal of {g1} and agent i forms a valid reduction if vi({g1}) ≥ 1.

Normalized instance. An instance is normalized if all of the following properties hold: i) the instance is ordered, ii) it is scaled so that vi(M) = n, and iii) it is reduced so that vi(g1) < 1 and vi({gn, gn+1}) < 1. By combining Lemma 1, 2, and 3, we may assume that instances are normalized. We prove this claim in Lemma 4.

3 ApproximatingMaximin Share

We introduce a fairness concept that allows for interpolation between two dimensions in approximating MMS pertaining to the fraction of agents α that receive a β approximation of their maximin share.

Definition 4 ((α, β)-MMS). An allocation A guarantees (α, β)-MMS if α ∈ (0, 1] fraction of agents receive at least their β ∈ (0, 1] approximation of their MMSni . Formally, given an instance I = 〈N,M, V 〉, an allocation A guarantees (α, β)-MMS if there exists a subset N ′ ⊆ N with |N ′ | ≥ ⌊α|N|⌋ such that for all i ∈ N ′ , vi(Ai) ≥ βMMSni . We say that (α, β)-MMS exists if for any instance I = 〈N,M, V 〉, for every subset N ′ ⊆ N of agents such that |N ′ | = ⌊α|N|⌋, there exists an allocation A such that for all i ∈ N ′ , vi(Ai) ≥ βMMSni .

Previous MMS approximation results can be seen in this context as efforts to tighten the approximation bound for all agents (α = 1). Notably, greedy algorithms exist to compute (1, 2 3 )-MMS [Barman and Krishna Murthy, 2017; Garg et al., 2018] and (1, 3 4 )-MMS [Ghodsi et al., 2018] allocations.

Remark 1. It is crucial to highlight two key distinctions: First, in contrast to previous works [Ortega, 2018; Nyman et al., 2020], the definition of (α, β)-MMS existence does not only hold for a fixed subset of agents. Rather, it is a stronger concept that holds for every subset of ⌊αn⌋ agents. Second, (α, β)-MMS enables a social planner to pre-select the N ′ ⊂ N of ⌊αn⌋ agents-independent of their preferencesaccording to some priority ordering over the agents or by selecting the agents uniformly at random. For instance, a higher priority may be given to senior college students; a practice that is already common in most course allocation procedures.

3.1 (α, 1)-MMS Implies MMSk for k ≥ ⌈ nα ⌉

Budish [2011] showed that approximating the competitive equilibrium from equal incomes (A-CEEI) guarantees MMSn+1 (M), i.e. adding a dummy agent and asking all agents to partition the goods into n + 1 bundles. However, this result does not imply the existence of MMSn+1 in allocating indivisible goods because allocations achieved by ACEEI may have excess supply or excess demands. This approach can result in infeasible allocations in fair division settings that do not allow the addition of excess goods. Therefore, the existence of MMSk for n+1 ≤ k ≤ 2n-2 remains an open problem. In Proposition 1 we show the relation between MMSk with (α, β)-MMS.

Proposition 1. The existence of (α, 1)-MMS implies the existence of MMSk for k ≥ ⌈ nα ⌉.

Proof. Suppose that (α, 1)-MMS exists. Given an instance I = 〈N,M, V 〉 with n agents, we construct an instance I ′ from I by adding ⌈ nα ⌉ - n dummy agents. Therefore, |N ′ | = ⌈ nα ⌉. Since (α, 1)-MMS exists, for every subset N ′′ ⊆ N ′ of size ⌊α|N ′ |⌋, there exists an allocation which satisfies (α, 1)-MMS on that set of agents. Thus, we may choose the ⌊α|N ′ |⌋ agents to contain exactly the well-defined original set of agents in N, that is, N ′′ := N. Hence, each agent i ∈ N receives at least vi(Ai) ≥ MMS|N ′ | , which implies MMS⌈ nα ⌉ for agents in N.

3.2 Failure of Optimal MMS Algorithms

There are two primary motivations behind the approximation parameter α (the fraction of agents). First, Proposition 1 states that fixing β = 1 immediately implies an ordinal approximation of MMS by partitioning goods into k > n bundles. Second, our next theorem shows that maximizing the value of β for all agents may result in only a small fraction of agents (α) receiving their MMS value. Theorem 1 shows that there exists a family of instances where any optimal-MMS allocation only gives a small constant number of agents their MMS value. Thus, an optimal-MMS algorithm (e.g. [Nguyen et al., 2017]) will result in an (α, λ∗ )-MMS allocation such that α goes to zero as the number of agents, n, increases.

Theorem 1. For every n ≥ 4, there exists an instance with O(n2 ) goods where every optimal-MMS allocation guarantees at most 3 (4 if n is odd) agents their MMS value.

The proof is inspired by constructions proposed by Kurokawa et al. [2016; 2018], but it includes a few intricate modifications by separating agents into ⌈ n2 ⌉ groups and setting up valuations such that only one group can receive its MMS value. The details and the necessary proofs are provided in the full version [Hosseini and Searns, 2021].

Theorem 1 illustrates that if the goal is to reach an optimalMMS threshold, the fraction of agents, α, who receive their MMS guarantee, β = 1, goes to zero as the number of agents increases. Thus, we ask for what values of α, (α, 1)-MMS is guaranteed to exist?

4 Computing (α, β)-MMS for n- 1 Agents

4.1 A ( 2 3 , 1)-MMS Algorithm for Three Agents

It is worth noting that although MMS always exists for n = 2 and can be achieved through the cut-and-choose protocol [Bouveret and Lemaˆıtre, 2016], computing such an allocation remains hard [Amanatidis et al., 2017]. Nonetheless, for two agents an allocation that guarantees MMS3 to each agent can be computed in polynomial time through an EF1 allocation [Aigner-Horev and Segal-Halevi, 2019]. We use this result to obtain the following result.

Proposition 2. For three agents, ( 2 3 , 1)-MMS always exists and can be computed in polynomial time.

Proof. By the definition of (α, β)-MMS, we can select any arbitrary subset of agents N ′ ⊂ N such that |N ′ | = 2. Then, run an EF1 algorithm on N ′ , which outputs an allocation A. Both agents in N ′ are guaranteed to receive their MMS3 , i.e., for each i ∈ N ′ we have vi(Ai) ≥ MMS3i , implying that 2 3 of agents receive their MMS. By the construction proposed by Kurokawa et al. [2018], an MMS allocation does not always exist for three agents; thus, ( 23 , 1)-MMS is a tight bound.

4.2 AGeneral Algorithm for n ≥ 4

To extend the analysis of approximate MMS for n-1 agents, we first provide an important lemma that enables us to focus on normalized instances in the remainder of this paper. This lemma states that we can employ valid reductions repeatedly (see Section 2) for computing (α, β)-MMS allocations.

Lemma 4. Given an instance I = 〈N,M, V 〉, we can compute a normalized instance I ′ = 〈N ′ ,M ′ , V ′ 〉 in polynomial time such that any (α, β)-MMS allocation on I ′ implies (α, β)-MMS on I.

We now focus attention on designing a polynomial-time algorithm that guarantees β MMS for n-1 agents. The algorithm relies on removing an arbitrary agent and computing an EFX allocation for the remaining n - 1 agents. By Lemma 1 an ordered instance can be generated (and easily converted back) from an unordered instance. A simple variant to the envy-graph algorithm satisfies EFX on ordered instances [Barman and Krishna Murthy, 2017]. We show that applying this procedure to normalized (and thus ordered) instances satisfies ( n-1 n , 12 ( n+2 n-1 ))-MMS. Since β depends on n, we cannot trivially extend this result to any (not normalized) instances. Nonetheless, we prove that together with Lemma 4 and Lemma 1 we can compute ( n-1 n , 12 ( n+2 n-1 ))-MMS for any instance in polynomial-time. The full proof of the theorem, along with necessary discussions, can be found in the full version of the paper [Hosseini and Searns, 2021].

Theorem 2. Given any instance of n agents, ( n-1 n , 12 ( n+2 n-1 ))-MMS can be computed in polynomial time.

By Proposition 1, we can add a dummy agent when n = 3 and select the original set of agents to obtain the following.

Corollary 1. For n = 3 agents, computing an allocation satisfying MMS4i , ∀i ∈ N can be done in polynomial time. 1

Remark 2. Theorem 2 immediately illustrates an intriguing interpolation between the approximation ratios of α and β: for n < 7, a better approximation of MMS values (β) can be achieved in polynomial time by sacrificing only one agent. Recall that the best approximation algorithms to date guarantee only (1, 34 )-MMS [Ghodsi et al., 2018] for general additive valuations. Table 1 shows the interpolation between α and β for n = 4 to n = 7.

5 The Existence of ( 23 , 1)-MMS Allocations

Theorem 2 optimizes the fraction of agents, α, and provides an efficient approach in achieving approximate MMS for n-1 agents. Another plausible, and often practical, approach aims at maximizing the fraction of agents α who receive their MMS guarantee (β = 1).

It turns out that simple modifications to existing approximation algorithms can guarantee ( 12 , 1)-MMS allocations. A key question is whether we can improve this bound for α beyond 12 and show the existence of such allocations. In what follows, we show that ( 23 , 1)-MMS exists and discuss an algorithm achieving this bound in polynomial-time when n < 9.

Our existence proof of ( 2 3 , 1)-MMS relies on combining techniques of bag-filling, strong normalization, and a variant of the lone divider procedure. Before discussing our main result, we briefly describe these techniques.

Bag-filling. Given a normalized instance, a good is highvalue for agent i if vi(g) ≥ 12 ; otherwise it is low-value. The bag-filling algorithm is a greedy approach for forming bundles in a normalized instance. An agent initializes a bag with a high-value good, and then adds low-value goods until the bag is worth at least 1. She then picks another high-value good and repeats this process. 2 For each bag, the total value never exceeds 1 + 12 = 32 since the last added good is low-value.

Remark 3. Bag-filling alone cannot guarantee ( 23 , 1)-MMS as it may 'run out' of low-value goods before filling ⌊ 2n 3 ⌋

1 Independently, Aigner-Horev and Segal-Halevi [2019] utilized envy-free matchings to compute MMSn+1 for 3 agents.

2 Similar approaches have been used by Garg et al. [2018]; Garg and Taki [2020]; Ghodsi et al. [2018] to compute (1, 23 )-MMS and (1, 34 )-MMS allocations. In their algorithms, the bag is filled until any agent values it at least 1.

bundles if the remaining value consists entirely of high-value goods. Consider n = 9 agents with identical valuations as follows: 5 goods of value 0.99, 5 goods of value 0.01, 1 good of value 0.95, 1 good of value 0.05, 3 goods of value 0.55, and 3 goods of value 0.45. Here, MMSni = 1 for all agents. The high-value goods are valued more than 0.5. During bagfilling, there will be three bundles of {0.99, 0.45}, one bundle of {0.99, 0.05}, and one bundle of {0.99, 0.01}. Since only 5 bundles were filled and ⌊ 2n 3 ⌋ = 6, we need to fill one more bundle. Adding all remaining low-value goods to the next high-value good 0.95 yields a total value 0.99. The remaining value is tied up with the high-value goods (0.55).

Strong Normalization. We say an instance is strongly normalized if it is ordered, vi(M) = n, and MMSni = 1. Observe that the definition of strong normalization implies that each bundle of an MMS partition is valued exactly 1. Furthermore, this implies that vi(g1) ≤ 1 and that vi(gn+1) ≤ 12 .

Lemma 5. For any additive instance I = 〈N,M, V 〉, there exists another strongly normalized instance I ′ = 〈N,M, V ′ 〉 such that I ′ is ordered and for all i ∈ N, MMSni = 1 and vi(M) = n. Furthermore, an (α, β)-MMS allocation on I ′ is also an (α, β)-MMS allocation on I.

Lemma 5 shows that any instance I can be modified via a non-polynomial-time transformation into a new instance I ′ that is strongly normalized such that an (α, β)-MMS allocation on I ′ implies an (α, β)-MMS allocation on I. Hence, we can focus only on strongly normalized instances.

Algorithm description. At its core, our algorithm implements the lone divider procedure for indivisible goods on n′ = ⌊ 2n 3 ⌋ of the agents. The lone divider procedure is an extension of the proportional cake-cutting algorithm [Robertson and Webb, 1998] that leverages non-empty envy-free matchings in a bipartite graph. It proceeds as follows: given n′ agents in N ′ , first, an arbitrary agent divides the goods into n′ acceptable bundles (A1, . . . ,An′). Second, we construct a bipartite graph between agents in N ′ and the bundles (A1, . . . , An′ ) wherein each edge connects an agent i ∈ N ′ to a bundle Ak such that vi(Ak) ≥ 1. Notice that the divider will be adjacent to all bundles. Next, we compute a non-empty envy-free matching, where no unmatched agent is adjacent to a bundle that was assigned to some other agent. A non-empty envy-free matching always exists if |N(N ′ )| ≥ |N ′ |, where N(N ′ ) denotes the set of bundles adjacent to N ′ [AignerHorev and Segal-Halevi, 2019]. All matched agents receive their bundles and leave. After the removal of matched agents and goods, we repeat the same procedure over the remaining goods and agents until there are no remaining agents. 3

The primary challenge in proving ( 2 3 , 1)-MMS existence lies in showing that in each iteration, given n′ remaining agents, the divider agent can form n′ bundles valued at least 1. We show that under the strong normalization assumption, the divider is always able to form n′ bundles either by pairing high-value goods or through restricted bag-filling.

Theorem 3. A ( 2 3 , 1)-MMS allocation is guaranteed to exist for any subset of ⌊ 2n 3 ⌋ agents.

Our proof relies on two technical cases based on the number of high-value goods (h). If h ≤ ⌊ 2n 3 ⌋, there are not many high-value goods, and thus, the simple bag-filling guarantees our desired result. The most challenging cases arise when h > ⌊ 2n 3 ⌋, that is, when there are too many high-value goods. Let s = h - ⌊ 2n 3 ⌋ be the number of excess high-value goods as shown in Figure 1. Here, we show that the divider agent is able to form the necessary bundles (i.e. the number of remaining agents) by adopting the following strategies: if n′ ≤ s, we can simply pair the remaining high-value goods since there are at least 2n′ high-value goods available, which implies n′ bundles are valued more than 1. On the other hand, if n′ > s, we are able to form s bundles by pairing the remaining highvalue goods. This means that we still need an additional n′ -s bundles. The key to handling this step relies on the restricted bag-filling procedure with exactly one high-value good per bundle but we restrict which low-value goods are used to fill bundles. In restricted bag-filling, we only use the low-value goods from bundles of the divider's MMSn partition whose high-value goods are no longer available (since those goods have been allocated in some previous round or assigned during pairing), as highlighted in Figure 1 by teal boxes.

The main reason behind this restriction is to ensure that not too much value is 'wasted' during bag-filling (as discussed in Remark 3). The restricted bag-filling relies on the strong normalization assumption - this way we can guarantee that the low-value goods used in restricted bag-filling have sufficient value when bundled with at most one high-value good.

3 See [Hosseini and Searns, 2021] for the technical details.

Our proof follows by showing that if n′ ≥ 2s, it is possible to form n′ - s bundles through restricted bag-filling. Otherwise if n′ < 2s, using restricted bag-filling we can form s bundles. In this case, we still need to form an additional n′ - 2s bundles, which is possible through simple bag filling by targeting for each bundle to have at most 32 value.

Remark 4. The strong normalization assumption in the proof of Theorem 3 requires modifying the values of some goods depending on an MMS partition for agent i. Furthermore, the restricted bag-filling phase of Theorem 3 selects available low-value goods from specific bundles of an MMS partition for agent i. Because of these dependencies on finding MMS partitions, Theorem 3 does not imply a polynomial time algorithm for ( 23 , 1)-MMS.

We show that by relaxing the strong normalization assumption to the weaker normalization of Lemma 4, we can devise a polynomial time algorithm for ( 23 , 1)-MMS when n < 9. Essentially, this algorithm is a simplified variant of our previous procedure that only includes simple bag-filling and pairing to form the required bundles in the lone divider procedure. Intuitively, since the total value of low-value goods is guaranteed to be at least 1 - vi(g1), at least one bundle can be allocated during bag-filling. When n < 9, adding the pairing phase forms ⌊ n2 ⌋ + 1 > ⌊ 2n 3 ⌋ bundles.

Theorem 4. For n < 9, ( 23 , 1)-MMS can be computed in polynomial time.

Theorem 4 only guarantees a ( 23 , 1)-MMS allocation when n < 9. We show by construction that this is tight (see [Hosseini and Searns, 2021] for details). We construct a family of instances with n ≥ 9 in which a small error in computing the MMS bound causes bag-filling to stop before ⌊ 2n 3 ⌋ bundles have been allocated. The challenge presented here is not unique to our algorithm. Any algorithm that satisfies ( 23 , 1)-MMS must be able to detect that MMSni < 1 for all agents. However, this task is intractable even when agents have identical valuations [Bouveret and Lemaˆıtre, 2016].

Combining this construction with Theorem 4 implies that no smaller counter-example exists. We note that despite this bound, the algorithm is still practical as there is no bound on the number of goods. For example, more than 99% of instances in the Spliddit dataset deal with less than 9 agents.

The analysis in Theorem 3 and Theorem 4 are indifferent to the set of agents N ′ . Consequently, we may select any subset of ⌊ 2n 3 ⌋ agents to be given their full MMS. An immediate consequence of this result, together with Proposition 1, is that there always exists an allocation of goods such that each agent receives at least the value of MMS⌈ 3n 2 ⌉ . Moreover, this allocation can be computed in polynomial time when ⌈ 3n 2 ⌉ < 9.

Corollary 2. An allocation satisfying MMS⌈ 3n 2 ⌉ always exists. Moreover, such allocations can be computed in polynomial time when n < 6.

6 Empirical Evaluations

The polynomial algorithm of Theorem 4 guarantees ( 23 , 1)-MMS only for n < 9. We evaluate a variant of this algorithm that does not rely on the strong normalization assumption (details relegated to the full version). It is similar to the algorithm of Theorem 4 until either no more bundles can be allocated during the lone divider procedure or all ⌊ 2n 3 ⌋ agents that were initially selected have received a bundle valued at least 1. In the latter case, any remaining goods are distributed among the unselected n - ⌊ 2n 3 ⌋ agents using bagfilling with priority given to agents who accept the smallest bundles. Notice that this algorithm does not guarantee that all initially selected agents receive their MMS.

We focus on ordered instances-as the most difficult instances in achieving MMS [Bouveret and Lemaˆıtre, 2016]- and generate 1,000 instances for each combination of n and m. Instances are sampled uniformly at random, ordered, and scaled such that vi(M) = n for all agents i ∈ N. Figure 2 illustrates the fraction of agents who receive their MMS for n = 3 to 50 agents and m = 3 to 200 goods. In almost all instances, the algorithm goes beyond the 23 bound: on average across all instances, more than 90% of agents receive their MMS. Moreover, the fraction of agents receiving their MMS improves as either n or m increases. We also observe linear bands where a lower fraction of agents are satisfied due to the ratio of goods to agents. In addition, when m < 2n a large fraction of the agents receive their MMS and are removed during the reduction phase of normalization.

7 Discussion

Theorem 3 proves the existence of ( 23 , 1)-MMS for any n, which implies the existence of MMS⌈ 3n 2 ⌉ . Therefore, improving the bound on (α, 1)-MMS for α > 2 3 and closing the gap between MMS⌈ 3n 2 ⌉ and MMSn+1 is an intriguing future direction. Theorem 4 provides a tractable approach for computing ( 23 , 1)-MMS for n < 9. Yet, computing such allocations for any n, if possible, will require further techniques to circumvent computing exact MMS bounds. Another interesting avenue for future research is exploring PTAS algorithms that guarantee optimal-MMS [Heinen et al., 2018] for a fraction of agents to achieve (α, 1)-MMS for α ∈ [ 23 , n-1 n ].

Acknowledgements

HH acknowledges the support from NSF grant #1850076. We are grateful to Erel Segal-Halevi for his valuable input that improved the proof of Theorem 3.