Ordinal Maximin Guarantees for Group Fair Division

1 Introduction

A fundamental problem in society is how to allocate scarce resources among interested parties. The burgeoning field of fair division studies how to perform the allocation fairly in scenarios ranging from dividing properties between families to distributing supplies among departments of a university or neighborhoods of a city [Brams and Taylor, 1996; Robertson and Webb, 1998; Moulin, 2019]. Often, the resources to be allocated are indivisible, meaning that each item is discrete and must be allocated as a whole to one of the parties.

To argue about fairness, one must specify what it means for an allocation to be "fair". A popular fairness notion when allocating indivisible items is maximin share fairness [Budish, 2011]. If the items are allocated among n agents, the maximin share (MMS) of an agent is defined as the largest value that the agent can guarantee for herself by dividing the items into n bundles and getting the worst bundle. While an allocation that gives every agent at least her maximin share always exists when n = 2, this is no longer the case if n ≥ 3 [Kurokawa et al., 2018]. A large stream of work has therefore focused on guaranteeing every agent a constant fraction of her maximin share, with the current best constant being marginally above 3/4 [Akrami and Garg, 2024].

The discussion in the preceding paragraph, like the majority of the fair division literature, assumes that each recipient of a bundle of items corresponds to a single agent. However, in many allocation scenarios, each interested party is in fact a group of agents. Even though the agents in each group share the same set of items, they do not necessarily share the same views on the items. Indeed, members of the same family, university department, or city neighborhood may have varying desires for different items based on their individual preferences and needs. As a consequence, several researchers have investigated fair division among groups of agents in the last few years [Manurangsi and Suksompong, 2017; Ghodsi et al., 2018; Segal-Halevi and Nitzan, 2019; SegalHalevi and Suksompong, 2019; Kyropoulou et al., 2020; Segal-Halevi and Suksompong, 2021; Manurangsi and Suksompong, 2022]. 1

The study of maximin share fairness for groups was initiated by Suksompong [2018], who showed, e.g., that for two groups with two agents each, it is possible to guarantee each agent 1/8 of her MMS. Unfortunately, Suksompong observed that if each group contains three agents, it may already be impossible to give all of them any positive fraction of their MMS. 2 In light of this, it may appear that maximin share fairness is not useful for group resource allocation unless the groups are extremely small. Nevertheless, while cardinal approximations of MMS have been intensively examined in the literature, another type of relaxation, which has also received increasing attention, is ordinal. This type of relaxation allows each agent to partition the items into k bundles for some parameter k > n-the corresponding notion is called 1-outof-k MMS. For individual fair division, Akrami et al. [2023] proved that ordinal MMS fairness can always be satisfied if we set k = ⌈4n/3⌉, improving upon prior results by AignerHorev and Segal-Halevi [2022] and Hosseini et al. [2022b]. Can ordinal approximations of MMS provide general fairness guarantees for groups as well?

1.1 Our Results

We consider a setting where n = n1 + · · · + ng agents are partitioned into g ≥ 2 groups of sizes n1, . . . , ng ≥ 1, respectively. Each agent has an additive and non-negative utility function over the set of items to be allocated. We denote by pMMS(n1, . . . , ng) the smallest integer p such that for g groups of sizes n1, . . . , ng, there always exists an allocation that gives every agent at least her 1-out-of-p MMS.

1 The line of work on consensus halving and consensus 1/kdivision problems (e.g., [Simmons and Su, 2003; Filos-Ratsikas and Goldberg, 2018; Goldberg et al., 2022; Filos-Ratsikas et al., 2023]) can also be viewed as fair division for groups.

2 Suppose there are three items and each agent has utility 1 for two of them and 0 for the remaining item, where the three agents in each group value distinct pairs of items. Then, each agent's MMS is 1, but every allocation leaves some agent with utility 0.

We shall prove asymptotically tight bounds on pMMS. Perhaps surprisingly, we show that the answer differs between the "unbalanced" case where one group is much larger than all other groups and the "balanced" case where this condition does not hold. The first case may be applicable, for instance, when a city has a large central neighborhood in which the majority of its residents live. Formally, we establish the following theorems. Note that the constant 1000 is unimportant, as the two bounds in each theorem are of the same order when log(n1 + 1) = Θ(log[(n2 + 1) · · · (ng + 1)]).

Theorem 1.1 (Upper bounds). Let n1 ≥ · · · ≥ ng be any positive integers. If log(n1+1) log[(n2+1)···(ng+1)] ≤ 1000, then

On the other hand, if log(n1+1) log[(n2+1)···(ng+1)] > 1000, then

Theorem 1.2 (Lower bounds). Let n1 ≥ · · · ≥ ng be any positive integers and n = n1 + · · · + ng. If log(n1+1) log[(n2+1)···(ng+1)] ≤ 1000, then

On the other hand, if log(n1+1) log[(n2+1)···(ng+1)] > 1000, suppose further that g ≤ (logn)1-δ for some constant δ ∈ (0, 1). Then, for any sufficiently large n (depending on δ), we have

Observe that our upper and lower bounds match in the balanced case, regardless of the relationship between the number of groups and the number of agents-for example, this is true even when n1, . . . , ng ∈ Θ(1). While our bounds also coincide in the unbalanced case, the corresponding lower bound relies on the condition that g ∈ (log n)1-Ω(1) . We remark that this is a relatively mild condition, as unbalancedness already implies that g ∈ O(logn1) ≤ O(logn). Moreover, our upper bounds come with efficient randomized algorithms. To gain more intuition on our bounds, notice that if n1 = n2 = · · · = ng = n/g, then pMMS(n1, . . . , ng) = Θ(g log(n/g)), whereas if n2 + · · · + ng ∈ Θ(1), then pMMS(n1, . . . , ng) = Θ(log n/ log log n).

In addition to these asymptotic bounds, we also derive concrete non-asymptotic results on pMMS for the case of two groups. When both groups are of the same size, our upper and lower bounds differ by only a factor of 2. Furthermore, our bounds are exactly tight for certain group sizes-for instance, we show that pMMS(2, 1) = pMMS(2, 2) = pMMS(3, 1) = pMMS(4, 1) = 3 and pMMS(4, 4) = pMMS(5, 5) = 4.

1.2 Additional RelatedWork

Although fair division has been studied extensively for several decades, the group aspect was only considered quite recently. Manurangsi and Suksompong [2017] assumed that agents' utilities are drawn from probability distributions and showed that an allocation satisfying another important fairness notion, envy-freeness, is likely to exist when there are sufficiently many items. Kyropoulou et al. [2020] and Manurangsi and Suksompong [2022] presented worst-case guarantees with respect to relaxations of envy-freeness. In particular, the latter authors showed that when the number of groups is constant, the smallest k such that an "envy-free up to k items" allocation always exists is k = Θ(√n); unlike for MMS as in our work, for envy-freeness the bound is the same no matter how the n agents are distributed into groups. Segal-Halevi and Suksompong [2019] investigated democratic fairness, where the objective is to provide fairness guarantees to a fraction of the agents in each group; they also considered ordinal MMS, but the corresponding results are mainly restricted to binary utilities. Segal-Halevi and Nitzan [2019] and Segal-Halevi and Suksompong [2021; 2023] examined group fairness for divisible resources, while Ghodsi et al. [2018] analyzed it in rent division.

Besides the model that we consider, group fairness has also been studied in individual fair division [Berliant et al., 1992; Todo et al., 2011; Aleksandrov and Walsh, 2018; Benabbou et al., 2019; Conitzer et al., 2019; Aziz and Rey, 2020]. In this setting, each agent receives a bundle of items and there is no sharing; however, fairness is desired not only for individual agents, but also for groups. Some of these authors assumed that the groups are fixed in advance (e.g., ethnic, gender, or socioeconomic groups), whereas others required fairness to hold across all groups that could possibly be formed. Scarlett et al. [2023] explored the interplay between individual and group fairness in this model.

As we mentioned earlier, although the majority of work on MMS concerns cardinal approximations, ordinal relaxations have also attracted growing interest among researchers. For individual fair division, Aigner-Horev and Segal-Halevi [2022] established the existence of a 1-out-of-k MMS allocation for k = 2n - 2. This was later improved to k = ⌊3n/2⌋ [Hosseini et al., 2022b], and subsequently to k = ⌈4n/3⌉ [Akrami et al., 2023]. Furthermore, ordinal MMS has been investigated in the context of indivisible chore allocation [Hosseini et al., 2022a], cake cutting [Elkind et al., 2021; Elkind et al., 2022], and land division [Elkind et al., 2023].

2 Preliminaries

We use log to denote the logarithm with base 2 and ln to denote the natural logarithm. For any positive integer z, let [z] := {1, . . . , z}.

Let g ≥ 2 and n1, . . . , ng be positive integers. Let N be a set of n = n1 + · · · + ng agents partitioned into g groups, where for each i ∈ [g], the i-th group is denoted by Ni and contains ni agents. Let M = [m] be the set of items to be allocated. A bundle refers to any (possibly empty) subset of M. Each agent a ∈ N has an additive utility function ua : 2M →R≥0 over the items inM; for a single item ℓ, we sometimes write ua(ℓ) instead of ua({ℓ}). For i ∈ [g] and j ∈ [ni], we refer to the j-th agent in Ni as agent (i, j), and use ui,j to denote the agent's utility function. An allocation A = (A1, . . . ,Ag) is an ordered partition of the items in M such that for each i ∈ [g], bundle Ai is assigned to group Ni. For i ∈ [g], we let

2.1 Ordinal MMS

Let p be a positive integer, and denote by Πp(M) the set of all (unordered) partitions of M into p parts. We now introduce our fairness notion of interest in this paper.

Definition 2.1. The 1-out-of-p maximin share of an agent a ∈ N, denoted by MMS1-out-of-p a , is defined as

An allocation (A1, . . . , Ag) is said to be an MMS1-out-of-p allocation if every agent's utility for her group's bundle is at least her 1-out-of-p maximin share. For an agent a ∈ N and a set of items S ⊆ M, we write MMS1-out-of-p a (S) to denote agent a's 1-out-of-p maximin share when restricted to S.

For any g ≥ 2 and positive integers n1, . . . , ng, we denote by pMMS(n1, . . . , ng) the smallest integer p such that for any g groups containing n1, . . . , ng agents respectively, there exists an MMS1-out-of-p allocation. We make some observations about pMMS. First, observe that if we add extra agents to existing groups, the problem can only become more difficult, as we still need to satisfy the original agents.

Observation 2.2. For any positive integers n1, . . . , ng and n′1 , . . . , n′g such that ni ≥ n′i for each i ∈ [g], we have pMMS(n1, . . . , ng) ≥ pMMS(n′1 , . . . , n′g ).

Similarly, if we remove a group, the problem can only become easier, as the items originally assigned to that group can be allocated arbitrarily among the remaining groups.

Observation 2.3. For any positive integers n1, . . . , ng and i ∈ [g], we have pMMS(n1, . . . , ng) ≥ pMMS(n1, . . . , ni).

By considering g - 1 identical items, we also have that p needs to be at least the number of groups.

Observation 2.4. For any positive integers n1, . . . , ng, we have pMMS(n1, . . . , ng) ≥ g.

2.2 Covering Designs

When deriving lower bounds, we will make use of covering designs, which are extensively studied in combinatorics.

Definition 2.5 (e.g., [Gordon et al., 1996]). For positive integers m, s, t, an (m, s, t)-covering design is a collection {S1, . . . , Sr} of subsets of [m], each of size s, with the property that for any subset T ⊆ [m] of size at most t, there exists i ∈ [r] such that T ⊆ Si.

Denote by C(m, s, t) the size of the smallest (m, s, t)- covering design. The following two upper bounds are known in the literature.

Lemma 2.6 ([Rees et al., 1999, Thm. 5]). For any positive integers m, k, s, t such that m ≥ k + st, it holds that C(m, m - k, t) ≤ (t+⌈k/s⌉ t ).

Lemma 2.7 ([Erd˝os and Spencer, 1974] 3 ). For any positive integers m ≥ s ≥ t, we have C(m, s, t) ≤ (mt ) (st) · (1+ ln (st)).

2.3 Concentration Bounds

We will also use the following concentration inequalities often referred to as multiplicative Chernoff bounds.

Lemma 2.8. Let X1, . . . ,Xk be independent random variables taking values in [0, 1], and let Z := X1 + · · · + Xk. Then, for every δ ≥ 0, we have

and

3 Upper Bounds

In this section, we derive upper bounds on pMMS by proving Theorem 1.1. We will use the following algorithm for approximating the MMS1-out-of-p value.

Lemma 3.1 ([Deuermeyer et al., 1982]). For any agent a ∈ N and any positive integer p, there is a polynomial-time algorithm that computes a value ta such that MMS1-out-of-p a ≥ ta ≥ 34 · MMS1-out-of-p a .

We will also use the following results by Aigner-Horev and Segal-Halevi [2022]. 4

Lemma 3.2 ([Aigner-Horev and Segal-Halevi, 2022]). Suppose that an agent a has utility at most 1 for each item, and ua(M) ≥ 2p for some positive integer p. Then, MMS1-out-of-p a ≥ 1.

Lemma 3.3 ([Aigner-Horev and Segal-Halevi, 2022]). If n1 = · · · = ng = 1, there is a polynomial-time algorithm that, given values (ta)a∈N such that ta ≤ MMS1-out-of-(2n-2) a for all a ∈ N, outputs an allocation that gives each agent a ∈ N utility at least ta.

We start by proving a general upper bound of O(log[(n1 + 1) · · · (ng + 1)]), which already implies the first part of Theorem 1.1. The high-level idea is to allocate (roughly) half of the items randomly. We can show that this partial allocation already satisfies the desired MMS guarantee for most of the agents. For the remaining agents, we use the algorithm from Lemma 3.3 to individually assign to them the remaining (roughly half) of the items.

Theorem 3.4. For any group sizes n1, . . . , ng, let

3 See, e.g., [Gordon et al., 1995, p. 270].

4 The first result is stated as Lemma 5.1 in their paper, and the second follows from the same proof as their Theorem 1.4.

Then, an MMS1-out-of-p allocation always exists. Furthermore, there is a randomized polynomial-time algorithm that finds such an allocation with probability at least 2/3.

Proof. First, we run the algorithm from Lemma 3.1 to find a value ta for each a ∈ N such that 3 4 · MMS1-out-of-p a (M) ≤ ta ≤ MMS1-out-of-p a (M). By scaling all utilities of a by a factor of 3/(4ta), we may assume henceforth that 34 ≤ MMS1-out-of-p a (M) ≤ 1. Furthermore, we can assume that each agent's utility for each item is at most 1. Indeed, otherwise we may decrease it to 1, which does not change the MMS1-out-of-p value nor whether a bundle satisfies MMS1-out-of-p for the agent. Our algorithm for finding the desired allocation (A1, . . . , Ag) works as follows.

• Let q1 = 40⌈log(n1+1)⌉ p , . . . , qg = 40⌈log(ng+1)⌉ p , and q = 1 - q1 - · · · - qg = 12 .
• Construct ˜ A1, . . . , ˜ Ag, ˜ A by assigning each item from M to one of these sets independently with probabilities q1, . . . , qg, q, respectively.
• Let N ′ = ⋃j∈[g] {a ∈ Nj | ua( ˜ Aj ) < 1}.
• Check whether the following two conditions hold:

and

If at least one condition does not hold, the algorithm terminates with failure.

• Run the algorithm from Lemma 3.3 on the agents N ′ (with ta = 1 for all a ∈ N ′ ) and items ˜ A. Let the output be ( ˜ Aa )a∈N ′ .
• Finally, output (A1, . . . ,Ag) defined by

Let us first argue that if the algorithm does not fail, then the output A = (A1, . . . , Ag) indeed satisfies MMS1-out-of-p . By definition of N ′ and our assumption that MMS1-out-of-p a (M) ≤ 1 for all agents a ∈ N, this is already satisfied for all agents in N \ N ′ . For the agents in N ′ , note that (3) implies that 2|N ′ | ≤ 4g. Furthermore, Lemma 3.2 together with (4) implies that MMS1-out-of-4g a ( ˜ A) ≥ 1 for all a ∈ N ′ . Thus, the guarantee of Lemma 3.3 ensures that these agents also receive a bundle with utility at least 1 in A. It follows that A satisfies MMS1-out-of-p .

Next, we show that the algorithm fails with probability at most 1/3. To this end, we first bound the probability that (3) fails. Consider any agent a ∈ Nj for some j ∈ [g]. For ℓ ∈ M, let Xℓ denote the random variable 1[ℓ ∈ ˜ Aj ] · ua(ℓ). Note that X := ∑ℓ∈M Xℓ is exactly equal to ua( ˜ Aj). Furthermore, we have E[X] = qj · ua(M) ≥ qj · p · MMS1-out-of-p a (M) ≥ qj · p · 34 = 30⌈log(nj + 1)⌉. Thus, applying Lemma 2.8 (specifically, (1)), we get

The above inequality is equivalent to

As a result, we have

Using Markov's inequality, we get

Next, we bound the probability that (4) fails. Consider any agent a ∈ Nj for some j ∈ [g]. For ℓ ∈M, let ˜Xℓ denote the random variable 1[ℓ ∈ ˜ A] · ua(ℓ). Note that ˜X := ∑ℓ∈M ˜Xℓ is exactly equal to ua( ˜ A). Furthermore, we have E[ ˜X] = q · ua(M) ≥ q · p · MMS1-out-of-p a (M) ≥ q · p · 34 = 38 p ≥ 30g. Thus, applying Lemma 2.8 (specifically, (1)), we get

The above inequality is equivalent to

Using the union bound over all agents, we get

Finally, by combining (5) and (6) via the union bound, we conclude that (3) and (4) hold simultaneously with probability at least 1-1/20-1/10 > 2/3. In other words, the algorithm succeeds with probability at least 2/3, as desired.

To prove the second part of Theorem 1.1, we again use random assignment in the first stage; however, this time we assign almost all of the items to the first group. We then use the algorithm from Theorem 3.4 to assign the leftover items to the remaining groups. By appealing to the stronger concentration for the upper tail bound when the required value is much larger than its expectation (i.e., (2) in Lemma 2.8), we arrive at the improved bound stated in the following theorem. Note that this bound implies the desired bound in Theorem 1.1 due to the assumption that β1 > 1000. (Recall the definition of β1 from Section 2.)

Theorem 3.5. Let n1, . . . , ng be group sizes such that β1 > 1000, and let

Then, an MMS1-out-of-p allocation always exists. Furthermore, there is a randomized polynomial-time algorithm that finds such an allocation with probability at least 2/3.

The proof of Theorem 3.5, along with all other omitted proofs, can be found in the full version of our paper [Manurangsi and Suksompong, 2024].

4 Lower Bounds

In this section, we turn our attention to lower bounds and prove Theorem 1.2. We first present a generic construction based on covering designs, and later apply this construction with more specific parameters to derive our theorem.

Lemma 4.1. Let m, p, t1, . . . , tg, n1, . . . , ng be positive integers such that

1. For each i ∈ [g], at least one of the following holds:
2. ti ≤ ⌊m/p⌋ - 1;
3. m-(p-1) > ti and C(m,m-(p-1), ti) ≤ ni.

Then, pMMS(n1, . . . , ng) > p.

Proof. For each i ∈ [g], we define the utilities of the agents in the i-th group Ni for the m items as follows.

• If ti ≤ ⌊m/p⌋ - 1, let each item have utility 1 for every agent in Ni.
• If m- (p - 1) > ti and C(m,m- (p - 1), ti) ≤ ni, then let {Si,1, . . . , Si,ni } be any (m,m - (p - 1), ti)- covering design. For each j ∈ [ni], we define the utility function of agent (i, j) by

If both conditions are met, we pick one arbitrarily.

Suppose for contradiction that an MMS1-out-of-p allocation exists. We claim that each group Ni must receive at least ti + 1 items. In the first case, group i must receive at least ⌊m/p⌋ ≥ ti + 1 items. Consider the second case. Each agent (i, j)'s MMS1-out-of-p is 1, by putting all items from Si,j in one bundle and each remaining item in its own bundle. Now, for any set T of at most ti items, there exists j such that T ⊆ Si,j, and so ui,j(T) ≤ ti m-(p-1) < 1. Hence, group i must again receive at least ti +1 items in this case. The total number of items that need to be allocated is therefore at least ∑i∈[g] (ti + 1) = t1 + · · · + tg + g > m, a contradiction. It follows that no MMS1-out-of-p allocation exists in this instance, and so pMMS(n1, . . . , ng) > p.

We now apply Lemma 4.1 using various parameter settings, starting with the balanced case.

Theorem 4.2. Let n1 ≥ · · · ≥ ng ≥ 63 be positive integers such that ⌊ 1 6 log(n1 + 1)⌋ ≤ ∑gi=2 ⌊ 1 6 log(ni +1)⌋. Then, for

we have pMMS(n1, . . . , ng) > p.

Proof. Let ti = 2 ⌊ 16 log(ni +1)⌋ ≥ 2 for all i ∈ [g]. Note that p = 12 (t1 + · · · + tg), and let m = 2p. We verify the two conditions in Lemma 4.1. For the first condition, we have t1 + · · · + tg + g = m + g > m.

It remains to check the second condition for each i ∈ [g]. To do so, first note that

where the second inequality follows from our assumption in the theorem. Let si = ⌊ p+1 ti ⌋ ≥ 1. We have si ≥ p+1 2ti and m = (p-1)+(p+1) ≥ (p-1)+siti. Applying Lemma 2.6, we get

where the last inequality is due to the definition of ti. As a result, Lemma 4.1 implies that pMMS(n1, . . . , ng) > p.

For the unbalanced case, it will be more convenient to have two separate constructions. First, we consider the case where the smaller groups N2, . . . ,Ng are "not too small". In this case, we can still use a covering design (from Lemma 2.7) for these groups.

Theorem 4.3. Let n1 ≥ n2 ≥ · · · ≥ ng be positive integers such that β1 ≥ 1000 and, for each i ∈ [g], it holds that ni ≥ 4(log(n1 + 1))4 . Then, for

we have pMMS(n1, . . . , ng) > p.

In the next construction, we do not make any assumption on N2, . . . ,Ng (i.e., they could all be of size 1), and simply use the "identical utilities" construction.

Theorem 4.4. Let n1 be a positive integer such that log(n1+ 1) ≥ 1000(g - 1). Then, for

we have pMMS(n1, 1, . . . , 1) > p.

By appropriately combining the previous three theorems for different regimes of parameters, we arrive at Theorem 1.2.

Proof of Theorem 1.2. We consider the two cases separately. Case 1: β1 ≤ 1000. If log[(n1 +1) · · · (ng +1)] ≤ 9000g, then Observation 2.4 immediately implies the desired bound. Assume therefore that log[(n1 + 1) · · · (ng + 1)] > 9000g. Suppose for contradiction that n2 < 63. Then n2, . . . , ng < 63 and log(n1 + 1) > 9000g - 6g > 8000g. On the other hand, β1 ≤ 1000 implies that log(n1 + 1) ≤ 1000 · (6g) = 6000g, a contradiction. Hence, n2 ≥ 63.

Let g′ ∈ {2, . . . , g} be the largest index such that ng′ ≥ 63. Since β1 ≤ 1000 and log[(n1 +1) · · · (ng +1)] > 9000g, we have log[(n2 + 1) · · · (ng + 1)] > 8g. It follows that

Applying Theorem 4.2, we get

Finally, combining this with Observations 2.2 and 2.3 yields the desired bound.

Case 2: β1 > 1000. This means that n1 + 1 > 21000 (n2 + 1) · · · (ng + 1), which implies that n1 > n2 + · · · + ng and therefore n1 > n/2. Let δ ∈ (0, 1) be the constant in the theorem statement, i.e., g ≤ (log n)1-δ .

Case 2.1: log[(n2+1) · · · (ng +1)] ≤ (log(n1+1))1-δ/2 . Since β1 > 1000, we have log(n1 + 1) > 1000(g - 1). Applying Theorem 4.4 and Observation 2.2, we get

where the last relation holds by the assumption of Case 2.1 and since δ is constant.

Case 2.2: log[(n2+1) · · · (ng +1)] > (log(n1+1))1-δ/2 . Let τ = (log(n1+1))1-δ/2 2g , and let g′ ∈ {2, . . . , g} be the largest index such that log(ng′ + 1) ≥ τ; note that g is welldefined due to the assumption of Case 2.2. We have

Recall that n1 ≥ n/2. Hence, for any sufficiently large n, we have

where for the second relation we use the assumption g ≤ (log n)1-δ . We can thus apply Theorem 4.3 to conclude that

Applying Observation 2.3 then yields the desired bound.

5 Non-Asymptotic Results

While our bounds on pMMS are already asymptotically tight, in this section, we additionally present some concrete nonasymptotic bounds. Our focus will be on the fundamental case of two groups. We begin with the upper bound.

Theorem 5.1. Let n1, n2, p be positive integers such that

Then, we have pMMS(n1, n2) ≤ p.

Before we prove Theorem 5.1, we note that the theorem, together with Bernoulli's inequality, immediately implies the following more explicit bound.

Corollary 5.2. For any positive integers n1, n2, it holds that pMMS(n1, n2) ≤ 1 + ⌈log(n1 + n2)⌉.

For the proof of Theorem 5.1, we need some additional notation.

• For an agent a ∈ N, we write S p a to denote the collection of all subsets S ⊆ M such that ua(S) ≥ MMS1-out-of-p a (M).
• We write P(S) to denote the power set of S, and T ∼ P(S) to denote a (uniformly) random subset of S.
• We write X(S) to denote the set of all allocations of the items in S to two groups, and write (T1, T2) ∼ X(S) to denote a (uniformly) random allocation of S.

We start by establishing the following key lemma, which gives a lower bound on the probability that a random subset of items provides MMS1-out-of-p to an agent.

Lemma 5.3. For any agent a ∈ N, we have

Proof. Fix any a ∈ N. By definition of MMS1-out-of-p , there exists a partition {B1, . . . ,Bp} of M such that ua(Bi) ≥ MMS1-out-of-p a (M) for all i ∈ [p]. Observe that T ∼ P(M) can be equivalently generated as follows:

• Independently sample (B1 i ,B2 i ) ∼ X(Bi) for all i ∈ [p];
• Independently sample j1, . . . , jp ∼ {1, 2};
• Let T = ⋃i∈[p] Bji i .

In other words, we have

where in the second expression, the probability is taken over {(B1 i ,B2 i ) ∼ X(Bi), ji ∼ {1, 2}}i∈[p], and in the third expression, the expectation is taken over {(B1 i ,B2 i ) ∼ X(Bi)}i∈[p] and the probability over {ji ∼ {1, 2}}i∈[p].

Consider a fixed collection of (B1 1 , B2 1 ), . . . , (B1 p , B2 p ). We shall lower bound the inner probability above. To this end, first note that the probability does not change when we swap B1 i and B2 i for some i ∈ [p], or when we swap (B1 i ,B2 i ) and (B1 i′ , B2 i′ ) for some i, i′ ∈ [p]. Thus, we may assume without loss of generality that the following holds:

• ua(B1 i ) ≥ ua(B2 i ) for all i ∈ [p];
• ua(B2 1 ) ≤ · · · ≤ ua(B2 p ).

We claim that for all collections of j1, . . . , jp ∈ {1, 2} such that (j1, . . . , jp-1) ̸= (2, . . . , 2), it must hold that ua (⋃i∈[p] Bji i ) ≥ MMS1-out-of-p a (M). To see this, let ℓ ∈ [p - 1] be an index such that jℓ = 1. We have

proving the claim. From this claim, it follows that

Plugging this back into (7), we get

Finally, to see that the above inequality cannot be an equality, consider the case where B2 1 = · · · = B2 p = ∅. In this case, which occurs with positive probability, it holds that Prj1,...,jp∼{1,2} [ua (⋃i∈[p] Bji i ) ≥ MMS1-out-of-p a (M)] ≥ 1 - 1/2p > 1 - 1/2p-1 . This completes the proof.

Lemma 5.3 together with the union bound already implies Corollary 5.2. To obtain the stronger Theorem 5.1, we use a combinatorial lemma by Kleitman [1966] before applying the union bound; the details can be found in the full version of our paper [Manurangsi and Suksompong, 2024].

Next, we turn to lower bounds. For two groups of equal size, we establish the following bound, which is already within a factor of 2 of the upper bound from Corollary 5.2.

Theorem 5.4. For any positive integer n′ , it holds that pMMS(n′ , n′ ) ≥ 2 + ⌊(log n′ )/2⌋.

We summarize the upper and lower bounds for n1, n2 ≤ 5 in Table 1. The bound for n1 = n2 = 1 follows from the well-known result in the individual setting (e.g., [Kurokawa et al., 2018]). The remaining upper bounds are direct consequences of Theorem 5.1. As for the lower bounds, by Observation 2.2, it suffices to show that pMMS(2, 1) ≥ 3 and pMMS(4, 4) ≥ 4. The former follows from Theorem 1 of Suksompong [2018]. For the latter, observe that C(5, 3, 2) ≤ 4 due to the (5, 3, 2)-covering design {{1, 2, 3}, {3, 4, 5}, {2, 4, 5}, {1, 4, 5}}, and apply Lemma 4.1 with (m, p, g, t1, t2, n1, n2) = (5, 3, 2, 2, 2, 4, 4).

6 Conclusion

In this paper, we have explored group fairness in indivisible item allocation using the popular notion of maximin share (MMS). We showed that ordinal relaxations of MMS, unlike their cardinal counterparts, are useful for providing fairness in this setting. In particular, we derived asymptotically tight bounds on the ordinal MMS approximations that can be guaranteed-interestingly, these bounds differ depending on whether there is a group whose size is substantially larger than the sizes of all the remaining groups.

Besides obtaining tighter non-asymptotic bounds, an interesting direction is to establish strong guarantees with respect to both MMS and envy-freeness. In individual fair division, there always exists an allocation that is envy-free up to one item (EF1), and such an allocation inherently satisfies 1out-of-(2n-1) MMS [Segal-Halevi and Suksompong, 2019, Sec. 2]. In group fair division, however, Manurangsi and Suksompong [2022] showed that for constant g, the least k such that the existence of an EFk allocation can be ensured is k = Θ(√n); this cannot imply 1-out-of-ℓ MMS for any ℓ = o(√n), 5 so the implied MMS guarantee is significantly weaker than our logarithmic guarantees. An intriguing question is therefore whether optimal EF and MMS guarantees can be made together, or whether trade-offs are inevitable.

5 Indeed, for a given agent, the Θ(√n) items that need to be removed from the remaining groups in order to attain envy-freeness could be highly valuable to the agent.

Acknowledgments

This work was partially supported by the Singapore Ministry of Education under grant number MOE-T2EP202210001 and by an NUS Start-up Grant. We thank the anonymous reviewers for their valuable feedback.