Maximin Share Guarantees for Few Agents with Subadditive Valuations

1 Introduction

Fair allocation of indivisible goods is a fundamental problem at the intersection of economics and computer science. The goal is to allocate a set of m goods among a set of n agents with heterogeneous preferences. In contrast to the case of divisible goods (known as cake-cutting) fundamental concepts of fairness-such as envy-freeness and proportionality- do not carry over when pivoting from the continuous to the discrete domain.

In this work, we investigate (approximate) Maximin Share fairness (MMS), a well-studied concept introduced by [Budish, 2011]. This notion can be seen as the discrete analogue of proportionality in the context of indivisible goods. The objective is to allocate a bundle to each agent, ensuring that her value is at least her maximin share (or a significant fraction of it). Intuitively, an agent's maximin share is the maximum value she could guarantee by proposing a partition of the items into n parts and then receiving the least desirable bundle from that division.

Although for two agents with additive valuations, MMS allocations always exist, [Kurokawa et al., 2018] showed that this is not always the case for three or more agents. Studying approximate MMS fairness has led to a surge of research in the past decade, for additive (e.g., [Amanatidis et al., 2017; Ghodsi et al., 2021; Garg and Taki, 2021; Akrami and Garg, 2024]) but also for more general valuation classes (e.g., [Barman and Krishnamurthy, 2020; Ghodsi et al., 2022; Akrami et al., 2023b; Seddighin and Seddighin, 2024]). The case of subadditive valuations, is wide-open with a logarithmic gap between the best known upper and lower bounds. Closing this gap is considered a major open problem in this area.

1.1 Our contribution

We study the existence of approximate MMS allocations, a predominant notion of fairness in settings with indivisible goods, under submodular and subadditive valuations. We focus on settings with few agents. We are able to show the following results (we refer the reader to a full version of the paper [Christodoulou et al., 2025]):

• In our main technical result (Theorem 1), we show the existence of 1/2-MMS allocations for at most four agents with subadditive valuations. We note that this result improves the best known bounds for many other valuation classes, including OXS, Gross Substitutes, submodular and XOS. We emphasize that the guarantee of our theorem matches the best known impossibility result due to [Ghodsi et al., 2022], thus settling the case of four agents for both subbaditive and XOS valuations (see also Table 1).
• We show the existence of 1/2-MMS allocations for multiple agents when they have one of two admissible valuation functions (Theorem 2).
• On the way to prove Theorem 1 we develop a new model that is useful for inductive arguments. This model incorporates nicely previously studied MMS variants, and we believe that it is of independent interest. In Section 4, we provide a complete characterization of 1/2-MMS(d), i.e., the allocations that guarantee 1/2 approximation to each agent with respect to their minimum guarantee when they partition the items into d = (d1, d2, d3) parts, respectively (Theorem 3), and a complete characterization of (1, 1/2, 1/2)-MMS(d), where one of the agents gets an 1 approximation (Theorem 4).
• We show an improved impossibility result for three agents with submodular valuation functions: we present

an instance in which an α-MMS allocation does not exist for α > 2/3 (Theorem 5). This improves the previous best known result of 3/4 due to [Ghodsi et al., 2022].

α-MMS(d). In order to show Theorem 1, we find it useful to study a notion that we call α-MMS(d), where α = (α1, . . . , αn) is a vector of threshold values ai ∈ [0, 1], and d = (d1, . . . , dn) is a vector of positive integers. Roughly an allocation is α-MMS(d) if it guarantees to each agent i an αi approximation of the minimum value she could guarantee if she could partition all the items in di parts (see Definition 1 for a formal definition). This notion is very useful for showing approximate MMS guarantees using inductive arguments, as we demonstrate in the technical part. It effectively captures several previous studied notions, and we believe it is of independent interest. For example, 1-MMS(d) corresponds to ordinal approximations of the maximin share, i.e. the maximum value an agent i can guarantee if she partitions the set of items into d bundles [Budish, 2011]. Another example is the notion of (α, β)-MMS introduced by [Hosseini and Searns, 2021], which guarantees to an α fraction of the agents a β approximation of their MMS. This can be captured by our notation α′ -MMS(d) where α′ = (β, . . . , β, 0, . . . , 0) is a vector where αn of its elements are equal to β and the rest are equal to 0, and for d = (n, . . . , n). They further showed that the existence of (α, 1)-MMS implies the existence of 1-out-of-kMMS for k ≥ ⌈ nα ⌉. Perhaps more closely related to our work, is the model of [Akrami et al., 2024] for approximate MMS guarantees with agent priorities, which captures both ordinal and multiplicative approximations as special cases, i.e. the concept of α-MMS(d), (for d = (n, . . . , n)).

1.2 Further RelatedWork

We refer the reader to the recent survey of [Amanatidis et al., 2023] covering a wide variety of discrete fair division settings along with the main fairness notions and their properties. We focus on the concept of maximin share (MMS).

Maximin share and α-MMS. MMS has seen significant progress during the past years. Nevertheless, the case beyond additive utilities remains underexplored; we summarize the state-of-the-art bounds in Table 1 for the most well-known superclasses of additive valuations. Additionally, 1/2-MMS allocations are known to exist for SPLC valuations [Chekuri et al., 2024]. [Hummel, 2024] proved the same guarantee for the case of hereditary set systems [Hummel, 2024], improving upon the 11/30 guarantee of [Li and Vetta, 2021]. In sharp contrast, a surge of works has led to strong approximations for additive valuations [Kurokawa et al., 2018; Amanatidis et al., 2017; Ghodsi et al., 2021; Garg and Taki, 2021; Akrami et al., 2023a]. Notably, [Akrami and Garg, 2024] recently showed an approximation factor of 3/4 + 3/3836.

1-out-of-d-MMS. [Budish, 2011] introduced the notion and showed the existence of 1-out-of-(n + 1)-MMS, albeit with excess goods. [Aigner-Horev and Segal-Halevi, 2022] obtained a bound of d = 2n - 2 on the existence of 1out-of-d allocations under additive valuations, which was subsequently improved to 1-out-of-⌈3n/2⌉ by [Hosseini and Searns, 2021], 1-out-of-⌊3n/2⌋ by [Hosseini et al., 2022], and recently to 1-out-of-4⌈n/3⌉ by [Akrami et al., 2024].

[Babaioff et al., 2021] introduced the ℓ-out-of-d maximin share, which corresponds to the maximum value an agent can guarantee to herself if she partitions the items into d bundles and then being allocated the worst ℓ of them.

FewAgents. Settings with few agents have been previously studied in the fair division literature, particularly for MMS approximations involving three or four agents with additive valuations. The algorithm of [Kurokawa et al., 2018] provides a 3/4-MMS guarantee for three or four agents. [Amanatidis et al., 2017] subsequently established a bound of α ≥ 7/8 for the case of three agents, which was later improved to 8/9 by [Gourv`es and Monnot, 2019] and finally to 11/12 by [Feige and Norkin, 2022]. [Ghodsi et al., 2021] improved upon the previously known factor by showing a 4/5 lower bound for four agents.

2 Model

We consider a setting of allocating a set M = {1, . . . ,m} of indivisible items among a set N = {1, . . . , n} of agents. Each agent i ∈ N is equipped with a valuation function vi : 2M → R≥0, and we denote by v = (v1, . . . , vn) the valuation profile of all agents. We consider valuations that are monotone (i.e. v(S) ≤ v(T), for all S ⊆ T) and normalized (v(∅) = 0). For brevity, we sometimes use vi(g) instead of vi({g}). In this work, we consider valuation classes that belong to the complement-free hierarchy, such as additive, submodular, XOS, and subadditive valuation functions which we define below.

Additive valuations. A valuation function v is additive if v(S) = ∑g∈S v(g) for any S ⊆ M.

Submodular valuations. A valuation function v is submodular if v(S)+v(T) ≥ v(S∪T)+v(S∩T) for any S, T ⊆ M. Fractionally subadditive (XOS) valuations. A valuation function v is XOS if there exists a set of additive functions a1, . . . , ak such that v(S) = maxl∈[k] al(S).

Subadditive valuations. A valuation function v is subadditive if v(S) + v(T ) ≥ v(S ∪ T ) for any S, T ⊆ M.

It is well-known that Additive ⊊ Submodular ⊊ XOS ⊊ Subadditive.

We are interested in allocating M into n mutually disjoint sets A1, . . . ,An, where Ai is the bundle of items assigned to agent i. We denote the respective allocation by A = (A1, . . . , An).

Minimum values: We often present to an agent a partition P = (S1, . . . , Sd) of M into d parts and we ask them how they value each part. We denote by Πd(M) the set of all possible such partitions. We define the minimum value of agent i with respect to some fixed partition P as

We denote by µdi (M) the maximum minimum guarantee (MMS(d)) that agent i can achieve by the best partition with d parts; i.e.,

We refer to the d bundles S1, . . . , Sd that comprise the best partition P, as the MMS(d) bundles of agent i or just the MMS bundles of i when d is clear from the context. For d = n, µni (M) is the MMS value of agent i, and we drop the superscript and simply denote it by µi(M). Also, when M and d are clear from the context, we use the simpler notation µdi or µi. For simplicity we assume (by scaling) that all valuations are normalized such that µdi = 1.

Given a vector of n positive integers d = (d1, . . . , dn) we define a vector of partitions P := P(d) = (P1, . . . , Pn) with respect to d, where the partition Pi ∈ Πdi (M) corresponds to the partition of agent i into di parts. We are interested in providing approximation guarantees αi for the minimum value µPi i (M) of each agent i with respect to P. This is summarised in the following definition.

Definition 1 (α-MMS(P), α-MMS(d)). Fix α = (α1, . . . , αn) with αi ∈ [0, 1], and d = (d1, . . . , dn) with di ∈ N+ for all i ∈ N. Fix also P = (P1, . . . , Pn), a fixed vector of partitions with Pi ∈ Πdi (M) for each i. An allocation A is α-MMS(P) if vi(Ai) ≥ αi · µPi i (M) for all i ∈ N. An allocation A is α-MMS(d) if it is α-MMS(P(d)) for all partition vectors P(d) w.r.t to d. 1

Note that for α = (α, . . . , α) and d = (n, . . . , n), the definition of α-MMS(d) coincides with the standard definition of α-MMS and we drop the dependency on d. Additionally, for simplicity when α is uniform, i.e., αi = α for each agent i, we write α-MMS(d) instead of α-MMS(d). We use the notation d-i and α-i to refer to those vectors where their i-th element is omitted.

Our allocation protocols proceed by repeatedly asking agents to evaluate various subsets of items using specific types of valuation queries. In the most common type of query, which we call a cut, we present a subset C ⊆ M to an agent S, ask her how she values the intersection of C with each of her MMS bundles Sj. Due to subadditivity, at least one of Sj∩C or Sj\C will provide her with satisfactory value, that is higher than vS(Sj)/2. We call the side (intersection or complement) that has the highest number of satisfactory values a Maximum Desired Half (see definition below and Figure 1 for an illustration).

1 Equivalently, an allocation A is α-MMS(d) if vi(Ai) ≥ αi · µdi i (M) for all i ∈ N.

Definition 2 (Maximum Desired Half). Let C ⊆ M and P = (S1, . . . , Sr) ∈ Πr(M) be a partition into r bundles for an agent S. The set XS(C, P) collects intersections of C with each Si that have sufficiently high value (greater or equal to 1/2) i.e.,

We define the Maximum Desired Half of agent S over the set C w.r.t partition P as follows

We refer to the set C as a cut C. When the partition P is clear from the context (e.g., when the partition is the MMS bundles of S) we will drop the dependency on P .

Intuitively, every bundle in the Maximum Desired Half of agent S guarantees at least half the value of the minimum bundle in P for agent S and moreover it is disjoint with either the cut C or with its complement w.r.t to each bundle Sj. The key property of the Maximum Desired Half set is that it contains at least half of the bundles.

Proof. Due to subadditivity, for each Si it holds that vS(Si ∩ C) + vS(Si \ C) ≥ vS(Si), and therefore at least one of the two terms on the left hand side is at least vS(Si)/2, which in turns means that either Si ∩ C ∈ XS(C, P), or Si \ C ∈ XS(M \ C, P) (or both). So, |XS(C, P)| + |XS(M \ C, P)| ≥ r and hence, |X ∗ S (C, P)| ≥ r/2 ≥ ⌈r/2⌉.

3 Subadditive Valuations

In this section we present our main technical result which establishes the existence of 1/2-MMS allocation for the case of at most four agents (Theorem 1). In Sections 3.1- 3.3 we establish the existence of 1/2-MMS approximate allocations for two, three and four subadditive agents (Corollaries 1, 3 and 4), respectively, that follow as simple corollaries from more restricted settings (Lemmas 1, 2, and 3, respectively). We note that all these results improve the state-ofthe-art for MMS guarantees for a wide set of valuation classes that lie below subadditive in the complement-free hierarchy. Subsequently, in Section 3.4 we show how our proof techniques can be extended to obtain positive results for settings with many agents, when the agents have one of two types of admissible valuation functions. We emphasize that all the results presented herein are tight for subadditive valuations, i.e., there exist constructions where not all agents can receive more than 1/2 of their MMS values [Ghodsi et al., 2022]. In the proofs which follow we use "symmetric" cuts, i.e. no matter if X ∗ i (C) = Xi(C) or X ∗ i (C) = Xi(M \ C) for the maximum desired half of agent i over cut C, the proof will continue the same way.

Theorem 1. An 1/2-MMS allocation exists for at most four agents with subadditive valuations.

Before proceeding with the proofs for few agents, we give the following general observation that illustrates the implications of our results.

Observation 2. Given some fair division instance, an allocation that is α-MMS(d) is also α′ -MMS(d′ ), where α is pointwise larger or equal to α′ , and d is pointwise smaller or equal to d′ .

Proof. Let A = (A1, . . . ,An) be a α-MMS(d) allocation. By definition it holds that for each agent i, vi(Ai) ≥ αiµdi i .

We first show that A is also a α-MMS(d′ ) allocation. Note that if for some agent i there exists a partition of M into d′i bundles that she values each by at least µd′i i , then there exists a partition into di ≤ d′i bundles that she values by at least the same amount, by merging bundles of the first partition, due to monotonicity of the valuation functions. This in turns implies that µdi i ≥ µd′i i . Therefore, vi(Ai) ≥ αiµd′i i , for all i, which implies that A is a α-MMS(d′ ) allocation.

To complete the proof, it simply holds that vi(Ai) ≥ αiµd′i i ≥ α′iµd′i i , for all i, which means that A is also a α′ - MMS(d′ ) allocation.

3.1 Two Agents

In this section we show that there always exists a 1/2-MMS allocation for the case of two agents. We first show a stronger statement (Lemma 1) and obtain the main result as a corollary (Corollary 1). We further provide a useful restatement (Corollary 2) of Lemma 1 to be extensively used in the proofs for three and four agents.

Lemma 1 (Two agents). A (1/2, 1)-MMS(1, 2) allocation exists for two agents with subadditive valuation functions.

Proof. We denote by S and T the two agents and by Sj, Tj their j-th MMS bundle respectively, i.e., S1 for the first agent and T1, T2 for the second agent. We proceed in a cut-andchoose fashion; we partition the set of items into two disjoint bundles T1, T2 which both are worth at least 1 for T. Agent S picks her favorite bundle which (due to subadditivity) is guaranteed to have at least 1/2 value since vS(T1)+vS(T2) ≥ vS(T1 ∪ T2) = vS(S1) = 1, and T receives the remaining bundle. Hence a (1/2, 1)-MMS(1, 2) allocation exists (see Figure 2 for an illustration).

In the following corollary we state that Lemma 1 suggests that a 1/2-MMS approximation is attainable for two agents (by Observation 2); this bound is tight for two agents [Ghodsi et al., 2022].

Corollary 1. A 1/2-MMS allocation exists for two agents with subadditive valuation functions.

We also provide a useful restatement of Lemma 1 to be used as a reduction tool in the proofs with more agents.

Corollary 2. Consider a fair division instance of two agents with subadditive valuations and a set of M items, where one agent values M with at least 1, and there exists a partition into two bundles where the other agent values each by at least 1/2. Then, there exists an allocation that guarantees at least 1/2 value to each agent.

3.2 Three Agents

In this section we show that there exists a 1/2-MMS allocation for the case of three agents. Again, we first show a stronger statement (Lemma 2) and obtain the main result as a corollary (Corollary 3).

Lemma 2 (Three agents). An 1/2-MMS(3, 2, 2) allocation exists for three agents with subadditive valuation functions.

Proof. We denote by S, T,Q the three agents and by Sj, Tj,Qj their j-th MMS bundle, respectively.

The proof relies on the existence of (1/2, 1)-MMS(1, 2) in the instance with two agents; we show that we can identify a valuable subset AT (with value at least 1/2) to allocate to agent T, such that we can extend the allocation applying Corollary 2 for agents S and Q and for the remaining items M \ AT . In particular, agent Q will have value at least 1 for M \ AT , while agent S will be able to partition it into two bundles with value at least 1/2 each. To achieve this we will use two cuts sequentially, first to agent S and then (based on the response of S) to agent T (we refer the reader to Figure 3 (a) for an illustration of the proof).

First cut. Consider the cut C = T2 that we offer to S and let S∗ 1 , S∗ 2 ∈ X ∗ S (C) be two bundles in the maximum desired half (by Observation 1 there exist at least two such bundles). The cut is "symmetric" for T in a sense that both C = T2 and M \ C = T1 contain the same number of T's MMS bundles; so it is without loss of generality to assume that X ∗ S (C) = XS(C) (in Figure 3 (a) S∗ 1 ⊆ S1, S∗ 2 ⊆ S2 are represented with blue color).

Second cut. We next offer C = Q1 to T and let T ∗ 1 ∈ X ∗ T (C) be the bundle in the maximum desired half. The cut is "symmetric" for Q, so again without loss of generality assume that X ∗ T (C) = XT (C) (in Figure 3 (b) T ∗ 1 ⊆ T1 is represented with red color).

Apply Corollary 2. Overall, vT (T ∗ 1 ) ≥ 1/2 and T ∗ 1 will be allocated to T. Then, for M ′ = M \ T ∗ 1 , it holds that vQ(M ′ ) ≥ vQ(Q2) ≥ 1, and S∗ 1 , S∗ 2 ⊆ M ′ , for both of which S has value at least 1/2. So the lemma follows by using Corollary 2 on M ′ for agents Q and S. (in Figure 3 (c) S∗ 1 ⊆ S1, S∗ 1 ⊆ S2 are represented with blue color and Q2 with green).

As a corollary of Lemma 2, a 1/2-MMS allocation always exists for three agents (by Observation 2); this bound is also tight [Ghodsi et al., 2022].

Corollary 3. A 1/2-MMS allocation exists for three agents with subadditive valuation functions.

3.3 Four Agents

In this section we show the existence of 1/2-MMS allocation for the case of four agents, our main technical result. We are also able to show a stronger statement (Lemma 3) and obtain the main result as a corollary (Corollary 4).

Lemma 3 (Four agents). A 1/2-MMS(3, 3, 4, 4) allocation exists for four agents with subadditive valuation functions.

Proof. We denote by S, T,Q,R the four agents and by Sj, Tj,Qj,Rj their j-th MMS bundle, respectively.

We progressively identify four candidate allocations in total, and we show that one of those should be a 1/2MMS(3, 3, 4, 4) allocation.

In a nutshell, the protocol works as follows. By offering carefully chosen cuts to agents S, T,Q we are able to find partial allocations for two of those agents (in the first round these are S and T), that have high enough value (higher than 1/2), in a way that always preserves one MMS bundle of agent R intact, let it be R4. If the third agent (this is Q in the first round) values higher than 1/2 two of her bundles (on the remaining items) then we can apply Corollary 2 on Q and R and for the remaining items, and we can claim a 1/2-MMS(3, 3, 4, 4) allocation. If this is not the case, then the third agent must value at least two of the intersections of her bundles with the partial allocation of the other two agents with value higher than 1/2. In the next round we will tentatively allocate to the third agent one of these sets. We will also keep one of the other two agents and offer her a subset of high value from a different bundle (the notion of maximum desired half is useful to achieve this last property). We proceed in a similar manner by querying the remaining agent investigating again whether Corollary 2 can be employed). The key is that in every round that the third agent does not satisfy the conditions of Corollary 2 we are able to build a more structured partial allocation, which in the final step provides an allocation of M\R4 to agents S, T and Q, that they value by at least 1/2. Then R4 can be allocated to agent R and the allocation is 1/2-MMS(3, 3, 4, 4).

Building the first candidate allocation. We first consider agent S (an agent with 3 MMS bundles) and cut her MMS bundles by offering the cut C = R1 ∪ R2. By Observation 1 there are at least two bundles in the set X ∗ S (C); let those be S∗ 1 , S∗ 2 ∈ X ∗ S (C). We note that S∗ 1 , S∗ 2 intersect with exactly two MMS bundles of R, so w.l.o.g. assume that those are R1,R2, i.e., assume that X ∗ S (C) = XS(C). Therefore

Next, we offer a cut to agent T in a way that a) ensures that a whole MMS bundle of agent R remains intact and b) one of S∗ 1 , S∗ 2 does not intersect with the Maximum Desired Half of T. A cut that serves this purpose is C = S∗ 2 ∪ R4. Now each of the sets C and M \ C intersects with exactly one of S∗ 1 , S∗ 2 and with exactly one of R3,R4 which are the remaining whole bundles of R. W.l.o.g. assume that X ∗ T (C) = XT (M \ C). 2 By Observation 1 there are at least two bundles in the set X ∗ T (C), let those be T ∗ 1 , T ∗ 2 ∈ X ∗ T (C). Then, it holds that

First candidate allocation. Consider the following partial allocation for S and T: A = (S∗ 2 , T ∗ 1 ) (see Figure 4 for an illustration). By construction, both S and T value their allocated bundles by at least 1/2. If there exist at least two MMS bundles of Q that she values with at least 1/2 after the removal of S∗ 2 ∪ T ∗ 1 , then the conditions of Corollary 2 are satisfied for Q and R for the remaining items (recall that R values the remaining items by at least 1 since they contain R4). Hence by employing Corollary 2 we can find an allocation of M \ (S∗ 2 ∪T ∗ 1 ) to Q and R where they both value their bundles with at least 1/2, and we are done.

So, suppose that this is not the case. Then there must be at least three MMS bundles of Q, let them be Q1,Q2,Q3, such that vQ(Qj ∩ (S∗ 2 ∪ T ∗ 1 )) ≥ 1/2 for j ∈ {1, 2, 3}. In other words, if we consider the cut C = S∗ 2 ∪ T ∗ 1 for agent Q, then it is guaranteed that Q∗1 ,Q∗2 ,Q∗3 ∈ XQ(C). Since Q∗j ⊆ S∗ 2 ∪ T ∗ 1 , for all j ∈ {1, 2, 3} and also by (1) and (2) we conclude that

Second candidate allocation. Next, we consider the partial allocation A′ = (T ∗ 2 ,Q∗1 ) for agents T and Q which by (3) is valid and both vT (T ∗ 2 ), vQ(Q∗1 ) are higher than 1/2 (see Figure 5 for an illustration). If there exist at least two MMS bundles of S, that she values with at least 1/2 after the removal of T ∗ 2 ∪ Q∗1 , then by employing Corollary 2 we can find an allocation of M \ (T ∗ 2 ∪ Q∗1 ) to S and R where they both value their bundles with at least 1/2, and we are done.

Otherwise, it should be that for the cut C = T ∗ 2 ∪Q∗1 there are two sets 3 S′1 , S′2 ∈ XS(C). Since for any j ∈ {1, 2}, S′j ⊆ T ∗ 2 ∪Q∗1 , by (2) and (3) we conclude

Third candidate allocation. Consider the partial allocation A′′ = (S′1 ,Q∗2 ) for S and Q, which is valid (due to (4)) and both agents value their allocated bundles by at least 1/2. Again, if there exist at least two MMS bundles of T, that

she values with at least 1/2 after the removal of S′1 ∪Q∗2 , by using Corollary 2 on T and R, we are done (similarly as in the previous cases).

2 Even if it is w.l.o.g., we consider X ∗ T (C) = XT (M \ C) that includes S3 to avoid any confusion of the steps needed, since the case of X ∗ T (C) = XT (C) is simpler and can be handled similarly.

3 It is not necessarily the case that S′1 ⊆ S1 or S′2 ⊆ S2 although this is how it is depicted in the figures for the sake of exposition.

Otherwise, it should be that for the cut C = S′1 ∪Q∗2 there exist two sets T ′1 , T ′2 ∈ XT (C). Since for any j ∈ {1, 2}, T ′ j ⊆ S′1 ∪Q∗2 , by (3) and (4) it holds that

Final allocation. Finally, we offer the allocation A∗ = (S′2 , T ′1 ,Q∗3 ,R4) which is valid and each agent has value at least 1/2 for their allocated bundle. Hence, the lemma follows.

As a corollary of Lemma 3, a 1/2-MMS allocation always exists for four agents (by Observation 1); this bound is also tight [Ghodsi et al., 2022].

Corollary 4. A 1/2-MMS allocation exists for four agents with subadditive valuation functions.

3.4 Many agents

In this section, we demonstrate how our arguments developed in the previous sections can be useful towards proving positive results for the case of multiple agents. Indeed, we show the existence of 1/2-MMS allocations for multiple agents, when they have one of two admissible valuation functions.

Theorem 2. For every instance of n agents, where each agent i has a valuation function vi ∈ {vS, vT }, for any subadditive valuation functions vS, vT , there exists a 1/2-MMS allocation.

Proof. The proof is by induction on the number of agents. At the induction step we guarantee that µi for each remaining agent i does not decrease, so at the end they will receive at least 1/2 of their original µi value. For n = 2 the theorem follows by Corollary 1. Let's assume that the statement holds for less than n, we will show that it also works for n agents. Let nS and nT be the number of agents with valuation function vS (agents of type S), and vT (agents of type T). Note that nS + nT = n. W. l. o. g. assume that nS ≥ nT and hence nS ≥ ⌈ n2 ⌉ and nT ≤ ⌊ n2 ⌋. Let also Sj and Tj be the j-th MMS bundle of an agent of type S and T , respectively.

We consider the cut C = ⋃⌊n/2⌋ j=1 Tj, i.e., the union of the first ⌊n/2⌋ MMS bundles of the agents of type T; note that both C and M \ C contain at least ⌊n/2⌋ such MMS bundles. Then, we consider the maximum desired half, X ∗ S (C), of agents of type S over C. Let n′ = min{|X ∗ S (C)|, nS}, and by Observation 1, n′ ≥ ⌈ n2 ⌉. This implies that there exist n′ mutually disjoint bundles, each of which has value at least 1/2 for the agents of type S. Suppose that we assign those bundles to n′ ≤ nS agents of type S.

Let M ′ be the union of those bundles, then it holds that M ′ is disjoint with either C or M \ C, therefore M ′ is disjoint with at least ⌊n/2⌋ ≥ n-n′ MMS bundles of agents of type T . Moreover M ′ is a subset of n′ MMS bundles of agents of type S, therefore M ′ is disjoint with n - n′ MMS bundles of agents of type S. Altogether, we are left with a reduced instance with n - n′ agents, where each remaining agent i can partition the remaining items M \M ′ into at least n-n′ bundles of value at least µni (M), since µn-n′ i (M \ M ′ ) ≥ µni (M). By the induction hypothesis there exists a 1/2-MMS allocation for the reduced instance, and by combining it with the allocation of M ′ to the n′ agents the proof follows.

4 α-MMS(d) for Subadditive Valuations

In this section, we present a thorough study of conditions of existence (and non-existence) of α-MMS(d) allocations for various combinations of α and d. We provide two characterization results in Theorems 3 and 4. Due to space limitations, we refer the reader to the full version [Christodoulou et al., 2025] for the complete proofs.

4.1 Three Agents

In this section we consider three agents with subadditive valuations, and we fully characterize the conditions of existence of 1/2-MMS(d) (Theorem 3) and of (1, 1/2, 1/2)-MMS(d) allocations (Theorem 4), with respect to any vector d. We prove those results via a series of Lemmas and Corollaries.

Our proofs are based on the following property: if there exist two allocations that "satisfy" all but one agent, and those allocations are disjoint in one MMS bundle of the last agent, then one of the two allocations will leave items that the last agent values by at least 1/2. Hence, that allocation can be extended to include the last agent that is guaranteed to receive a bundle that he values by at least 1/2.

Characterizations of 1/2-MMS(d) guarantees

In this section we provide a complete characterization of results regarding 1/2-MMS(d) for three agents with subadditive valuations, for any vector d = (d1, d2, d3). We summarize the results in the following theorem; note that we use the value ∑3i=1 di to distinguish among different d, however, we do not claim that there is any strong correlation.

Theorem 3. A 1/2-MMS(d) allocation exists for three agents with subadditive valuation functions, when (i) d = (3, 2, 2) or (ii) ∑3i=1 (di) ≥ 8 and di = 1 for at most one agent i. In any other case, there exists an instance with no 1/2-MMS(d) allocation.

Proof. The positive results are derived by using Observation 2 and showing that there is always a 1/2-MMS(3, 2, 2) allocation (Lemma 2), and a (1, 1/2, 1/2)-MMS(d) allocation, for d = (5, 2, 1), d = (4, 3, 1), and d = (4, 2, 2). The impossibility results are derived by using Observation 2 and showing that for any of the following d, there exists an instance that no 1/2-MMS(d) allocation exists. This is shown for d = (k, 1, 1), for any k ≥ 1, d = (4, 2, 1), d = (3, 3, 1), and d = (2, 2, 2).

Characterizations of (1, 1/2, 1/2)-MMS(d) guarantees In this section we provide a complete characterization of results regarding (1, 1/2, 1/2)-MMS(d) for three agents with subadditive valuations.

Theorem 4. A (1, 1/2, 1/2)-MMS(d) allocation exists for three agents with subadditive valuation functions, when ∑3i=1 (di) ≥ 8, when di = 1 for at most one agent i, and maxi di ≥ 4. In any other case, there exists an instance with no 1/2-MMS(d) allocation.

Proof. The positive results are derived by using Observation 2 and showing that there is always a (1, 1/2, 1/2)- MMS(d) allocation, for d = (5, 2, 1), d = (4, 3, 1) and d = (4, 2, 2). The impossibility results are derived by using Observation 2 and showing that for any of the following d, there exists an instance that no 1/2-MMS(d) allocation exists. This is shown for d = (k, 1, 1), for any k ≥ 1, d = (4, 2, 1), and d = (3, 3, 3).

5 Impossibility for Submodular Valuations

In this section, we give an improved impossibility result for three agents with submodular valuations.

Theorem 5. There exists an instance of 3 agents with submodular valuations and 6 items for which there is no (2/3 + ϵ)-MMS allocation, for any ϵ > 0.

6 Conclusion

We study the existence of approximate MMS allocations in the case of subadditive valuations and few agents. We showed the existence of 1/2-MMS allocations for at most four agents with subadditive valuations, as well as for multiple agents when they have one of two types of valuations. The most challenging question of whether a constant-factor MMS approximations always exist for n > 4 agents, remains open. One hopes that our insights and technical lemmas might help pave the way for more general positive results. The study of α-MMS(d) and α-MMS(P) was proved useful for providing approximate MMS guarantees, but we believe they are of independent interest and deserve further investigation.

Acknowledgements

This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.