On Lower Bounds for Maximin Share Guarantees

1 Introduction

We are interested in the problem of fairly dividing a set of resources or tasks to a set of agents-a problem that frequently arises in day-to-day life and has been extensively studied since the seminal work of Steinhaus [1948]. While the classical setting assumes that the resources are infinitely divisible, a variant of the problem in which a set of indivisible items are to be allocated has been studied extensively in the last couple of decades (see, e.g., Amanatidis et al. [2022] and Suksompong [2021] for recent, detailed overviews).

For indivisible items, classical fairness criteria, such as envy-freeness and proportionality, are no longer guaranteed. Instead, relaxed fairness criteria are considered, such as the maximin share (MMS) guarantee [Budish, 2011]. For the MMS guarantee, each agent should receive a set of items worth at least as much as she could guarantee herself if she were to partition the items into bundles and got to choose a bundle last. Surprisingly, it is not guaranteed that an allocation of this kind exists [Procaccia and Wang, 2014]. In fact, there exists problem instances for which at least one agent receives a bundle worth no more than 39/40 of her MMS [Feige et al., 2022]. However, good approximations exist and can be found efficiently. The best current approximation algorithm guarantees each agent at least 3/4 + 1/(12n) of her MMS, where n is the number of agents [Garg and Taki, 2021].

When valuations are additive, MMS allocations are guaranteed to exist in certain special cases, such as when there are at most n + 5 items [Feige et al., 2022] or the set of valuation functions is restricted in certain ways [Amanatidis et al., 2017; Heinen et al., 2018]. Our goal in this paper is to further improve these existence results for MMS allocationsshowing that the number of items an instance can have scales with the number of agents, beyond one item per agent.

We are interested in improving this lower bound for existence to further determine the usefulness of MMS as a fairness measure, especially in real-world scenarios. Usage of the online fair allocation tool Spliddit [Procaccia et al., 2023] suggests that many real-world instances have few agents and on average a few times as many items as agents [Caragiannis et al., 2019]. As the upper bound for existence is currently at around three times as many items as agents [Feige et al., 2022], reducing the gap between the two bounds betters our understanding of these real-world scenarios.

1.1 Contributions

In this work, we improve on the known bound for the number of goods, m, an instance with n agents can have and be guaranteed to have an MMS allocation. We find that there exists some function f(n) = ω(√lgn) such that an MMS allocation exists for all instances with m ≤ n + f(n) goods, improving on the result of m ≤ n + 5 [Feige et al., 2022]. 1 Specifically, for any integer c > 0 we prove the following bound for the required number of agents for guaranteed MMS existence in instances with m ≤ n + c goods.

Theorem 1. For any integer c > 0, there exists an nc ≤ ⌊0.6597c (c!)⌋ such that all instances with n ≥ nc agents and no more than n + c goods have an MMS allocation.

It has been shown by counterexample that c = 5 is the largest constant such that an MMS allocation always exists for all instances with any number n of agents and at most n + c goods [Feige et al., 2022]. We show that when n ̸= 3, an MMS allocation always exists when c = 6.

Theorem 2. For an instance with n ̸= 3 agents, an MMS allocation always exists if there are m ≤ n + 6 goods.

1 Expressing f(n) in terms of n is nontrivial, due to the factorial in Theorem 1.

Finally, we show that there exists a similar existence guarantee for chores as was shown for goods in Theorem 1.

Theorem 3. For any integer c > 0, there exists an nc ≤ ⌊0.7838c (c!)⌋ such that all instances with n ≥ nc agents and no more than n + c chores have an MMS allocation.

Our proofs of Theorems 1 and 3 build on two new structural properties of ordered instances. First and most importantly, we exploit a common structure in MMS partitions for ordered instances with m ≤ 2n. When an ordered instance has n agents and m = n + c items for some constant c ≥ 0, each agent has an MMS partition in which the n - c most valuable (least valuable for chores) items appear in bundles of size one. If c ≤ n, the remaining 2c items must be placed in the remaining c bundles. The number of ways 2c items can be partitioned into c bundles depends only on c. Thus, as n increases, more agents will have similar MMS partitions.

To analyse the number of agents required for there to be enough similarity for an MMS allocation to exist, we impose a partial ordering over the bundles, based on the concept of domination. Due to the common preference order in ordered instances, we can for some pairs of bundles B and B′ determine that B is better than B′ no matter the valuation function. In this case, we say that B dominates B′ . A trivial example is when B and B′ differ by only a single item. When a sufficient number of agents have bundles in their MMS partitions that form a chain in the domination based partial ordering, a reduction to a smaller instance can be found. By employing induction, we use an upper bound for the size of the maximum antichain to obtain the existence bounds.

1.2 RelatedWork

The existence of MMS has been the focus of a range of publications in recent years. Early experiments failed to yield problem instances for which no MMS allocation exists [Bouveret and Lemaˆıtre, 2016]. Procaccia and Wang [2014] later found a way to construct counterexamples for any number of agents n ≥ 3. 2 These counterexamples used a number of goods that was exponential in the number of agents. The number of goods needed for a counterexample was later reduced to 3n + 4 by Kurokawa et al. [2016] and recently to 3n + 3 by Feige et al. [2022]. 3 In the opposite direction, Bouveret and Lemaˆıtre [2016] showed that all instances with at most n + 3 goods have MMS allocations, later improved to n + 4 by Kurokawa et al. [2016] and n + 5 by Feige et al. [2022]. Feige et al. also found an instance with 3 agents and 9 goods for which no MMS allocation exists.

While MMS allocations do not always exist, it has been shown that they exist with high probability, under certain simple assumptions [Kurokawa et al., 2016; Suksompong, 2016; Amanatidis et al., 2017].

The existence of MMS allocations has also been explored in cases where valuation functions are restricted. Amanatidis et al. [2017] showed that when item values are restricted to the set {0, 1, 2}, an MMS allocation always exists. Later, Heinen et al. [2018] studied existence for Borda and lexicographical valuation functions.

2 For n < 3, MMS allocations always exist.

3 3n + 1 when n is even.

There is also a rich literature on finding approximate MMS allocations, either by providing each agent with a bundle worth at least a percentage of her MMS [Amanatidis et al., 2017; Garg et al., 2018; Gourv`es and Monnot, 2019; Garg and Taki, 2021; Ghodsi et al., 2021; Feige and Norkin, 2022] or providing a percentage of the agents with bundles worth at least MMS [Hosseini and Searns, 2021].

While the main focus of the literature has been on goods, some work has been done on MMS for chores, both on existence [Aziz et al., 2017; Feige et al., 2022] and approximation [Aziz et al., 2017; Barman and Krishnamurthy, 2020; Huang and Lu, 2021; Feige and Norkin, 2022].

2 Preliminaries

An instance I = ⟨N,M, V ⟩ of the fair allocation problem consists of a set N = {1, 2, . . . , n} of agents and a set M = {1, 2, . . . ,m} of items. Additionally, there is a collection V of n valuation functions, vi : 2M → R, one for each agent i ∈ N. To simplify notation, we let both vij and vi(j) denote vi({j}) for j ∈ M. We assume that the valuation functions are additive, i.e., vi(M) = ∑g∈M vi(g), with vi(∅) = 0. We deal, separately, with two types of items: goods, which have non-negative value, vi(j) ≥ 0, and chores, which have non-positive value, vi(j) ≤ 0. 4 Mixed instances, which consist of a mix of goods and chores, and perhaps have items that are goods for some agents and chores for others, will not be considered. Hence, the valuation functions are monotone, i.e., for S ⊆ T ⊆ M, vi(S) ≤ vi(T) for goods and vi(S) ≥ vi(T) for chores. For simplicity, we assume throughout the paper that all instances consist of goods, except in Section 5, which covers instances consisting of only chores.

For any instance I = ⟨N,M, V ⟩, we wish to partition the items in M into n bundles, one for each agent. An n-partition of M is called an allocation. We are interested in finding allocations that satisfy the fairness criteria known as the maximin share guarantee [Budish, 2011]. That is, we wish to find an allocation in which each agent gets a bundle valued at no less than what she would get if she were to partition the items into bundles and got to choose her own bundle last.

Definition 4. For an instance I = ⟨N,M, V ⟩, the maximin share (MMS) of an agent i ∈ N is given by

where ΠI is the set of all possible allocations in I. If obvious from context, the instance is omitted, and we write simply µi.

We say that an allocation A = ⟨A1,A2, . . . ,An⟩ satisfies the MMS guarantee or, simply, is an MMS allocation, if each agent i ∈ N receives a bundle valued at no less than her MMS, i.e., vi(Ai) ≥ µi. For a given agent i ∈ N we call any allocation A in which vi(Aj) ≥ µi for every bundle Aj ∈ A, an MMS partition of i for I. By definition, each agent has at least one MMS partition for any instance I, but can possibly have several.

4 By this definition, an item j with vij = 0 is both a good and a chore. However, as we do not consider mixed instances, the overlapping definitions do not matter.

Several useful properties of MMS have been discovered in previous work. Perhaps the most useful, is the concept of ordered instances, in which the agents have the same preference order over the items.

Definition 5. Instance I = ⟨N,M, V ⟩ is said to be ordered if vij ≥ vi(j+1) for all i ∈ N and 1 ≤ j < |M|. 5

Bouveret and Lemaˆıtre showed that both for existence and approximation results, it is sufficient to consider only ordered instances.

Lemma 6 (Bouveret and Lemaˆıtre, 2016). For any instance I = ⟨N,M, V ⟩, there exists an ordered instance I ′ , with µIi = µI ′ i for all i ∈ N, and for any allocation A′ for I ′ there exists an allocation A for I such that vi(Ai) ≥ v′i (A′i ) for all i ∈ N.

The instance I ′ is constructed by sorting the item valuations of each agent and reassigning them to the items in a predetermined order. The MMS of an agent does not change from I to I ′ , due to the inherent one-to-one map between items in I and I ′ . Allocation A can be constructed from A′ by going through the items in order from most to least valuable, letting the agent i that received item j in A′ select her most preferred remaining item in I. Since there are at least j items in I with an equivalent or greater value than j has in I ′ , at least one of these must remain when i selects an item for j and the selected item has at least as high value in I as j has in I ′ . Consequently, each agent's bundle in A is at least as valuable as in A′ .

Another useful form of instance simplification, that we will rely heavily on, is the concept of valid reductions. A valid reduction is, simply put, an allocation of a subset of the items to a subset of the agents, where each agent receives a satisfactory bundle, 6 while the MMS of the remaining agents is not smaller in the new, smaller instance.

Definition 7. Let I = ⟨N,M, V ⟩ be an instance. Removing a subset of items M ′ ⊆ M and a subset of agents N ′ ⊆ N is called a valid reduction if there exists a way to allocate the items inM ′ to the agents in N ′ such that each agent i′ ∈ N ′ receives a bundle Bi′ with vi′(Bi′) ≥ µIi′ and for i ∈ N \ {N ′ }, we have µI ′ i ≥ µIi , where I ′ = ⟨N \N ′ ,M \M ′ , V ′ ⟩.

Valid reductions are commonly used when finding approximate MMS allocations, where several simple reductions have been found [Kurokawa et al., 2016; Amanatidis et al., 2017; Ghodsi et al., 2018; Garg et al., 2018; Garg and Taki, 2021]. These reductions allocate a small number of goods to a single agent-providing a powerful tool when considering instances with only a few more goods than agents. Most of these reductions can also be used in the existence case and the ones relevant to us are given below. Proofs for their validity have been omitted due to space constraints, but can be found in the cited papers. These proofs often use αµi for some α < 1 instead of just µi, but trivially extend to any α ≤ 1. For completeness we prove these results in the extended version of this paper 7 , along with all other omitted proofs.

5 For simplicity, we assume vij ≤ vi(j+1) for chores.

6 A bundle B is satisfactory for an agent i if vi(B) ≥ µi, or in the case of approximation vi(B) ≥ αµi for some α > 0.

7 Available at https://arxiv.org/abs/2302.00264.

Lemma 8 (Bouveret and Lemaˆıtre, 2016). For an instance I = ⟨N,M, V ⟩ with an agent i ∈ N and good j ∈ M such that vij ≥ µi, allocating {j} to i is a valid reduction.

Lemma 9 (Ghodsi et al., 2018). Let I = ⟨N,M, V ⟩ be an instance with an agent i ∈ N and distinct goods j, j ′ ∈ M such that vi({j, j ′ }) ≥ µi and vi′({j, j ′ }) ≤ µi′ for all i′ ∈ (N \ {i}), then allocating {j, j ′ } to i is a valid reduction.

Lemma 10 (Garg et al., 2018). Let I = ⟨N,M, V ⟩ be an ordered instance. If there is an agent i ∈ N with vi({n, n+ 1}) ≥ µi, then allocating {n, n+1} to i is a valid reduction. Lemma 11 (Feige et al., 2022). Given an ordered instance I = ⟨N,M, V ⟩, agent i ∈ N and good j ∈ M with vi(j) ≥ µi and vi′(j) < µi′ for all i′ ∈ N \ {i}, allocating {j, j ′ } to i, where j ′ is the worst good in M \ {j}, is a valid reduction.

In addition to valid reductions, there are several cases in which an MMS allocation is known to exist. These cases will be used as base cases in our existence argument.

Lemma 12 (Bouveret and Lemaˆıtre, 2016). If in an instance I = ⟨N,M, V ⟩ there are at least n - 1 agents with the same MMS partition, then an MMS allocation exists.

Lemma 13 (Bouveret and Lemaˆıtre, 2016). An MMS allocation always exists for an instance I = ⟨N,M, V ⟩ if n ≤ 2.

Lemma 14 (Feige et al., 2022). An MMS allocation always exists for an instance I = ⟨N, M, V ⟩ if m ≤ n + 5.

3 Existence for Any Constant

Our first main result is that for any c > 0, there exists an nc > 0 such that all instances with n ≥ nc agents and n + c goods have MMS allocations. To show this, we exploit a structural similarity in MMS partitions when c < n. Specifically, if m < 2n, any MMS partition contains some bundles of cardinality zero or one. 8 For ordered instances of this kind (ordering can be assumed by Lemma 6), there is a set of at least n - c goods valued, individually, at MMS or higher by each agent, namely the set of the n - c most valuable goods:

Lemma 15. Let I = ⟨N,M, V ⟩ be an ordered instance with m = n + c for some c with n > c > 0. Then vij ≥ µi for all i ∈ N and j ∈ {1, 2, . . . , n - c}.

Proof. Agent i ∈ N either has µi = 0 or each bundle in any one of her MMS partitions contains at least one good. If µi = 0, then vij ≥ µi for all j ∈ M. Otherwise, at most c of the bundles in an MMS partition can contain more than one good. The worst good g contained in a bundle of cardinality one, is such that g ≥ n - c. Since µi ≤ vig by definition, µi ≤ vig ≤ vi(n - c) ≤ vi(n - c - 1) ≤ · · · ≤ vi(1).

The shared set of goods valued at MMS or higher guarantees that each agent has an MMS partition where these goods appear in bundles of cardinality one.

Lemma 16. Given an ordered instance I = ⟨N,M, V ⟩ and agent i ∈ N, let k denote the number of goods i value at µi or higher. Then i has an MMS partition in which each of the goods 1, 2, . . . ,min(n - 1, k) forms a bundle of cardinality one.

8 If there is a bundle of cardinality zero in an MMS partition of agent i, then µi = 0.

Proof. Let A be an arbitrary MMS partition of i, Bg ∈ A denote the bundle containing some g ∈ M and let GA = {g ∈ {1, 2, . . . ,min(n - 1, k)} : |Bg| > 1}. If GA = ∅, then all the goods 1, 2, . . . ,min(n - 1, k) appear in bundles of cardinality one. We wish to show that if GA ̸= ∅, then there exists an MMS partition A′ with |GA′ | < |GA|. Assume that GA ̸= ∅ and for some g ∈ GA, select Aj ∈ A such that {1, 2, . . . ,min(n - 1, k)} ∩ Aj = ∅. Then, the allocation A′ = ⟨A1, . . . , {g}, . . . , Aj ∪ (Bg \ {g}), . . . , An⟩ is an MMS partition of i, as vi(Aj ∪ (Ag \ {g})) ≥ vi(Aj) ≥ µi and vig ≥ µi. Further, as only the two bundles Bg and Aj have been modified, and Aj did not contain any good in {1, 2, . . . , min(n-1, k)}, we have |GA′ | = |GA|-1. Hence, i has an MMS partition A∗ with GA∗ = ∅.

Lemma 16 enforces a particularly useful restriction on the set of n-partitions of M when n > c. As a result of Lemma 15, Lemma 16 guarantees that each agent has at least one MMS partition in which the n - c most valuable goods appear in bundles of cardinality one. In this MMS partition, the remaining 2c goods are partitioned into c bundles. Ignoring the possibility of having empty bundles, the number of ways to partition these 2c goods into c bundles is {2c c }, where {2c c } is a Stirling number of the second kind. 9

The value of {2c c } does not depend on the value of n. Thus, as the number of agents increases, there must eventually be multiple agents with the same MMS partition. Specifically, when there are {2c c }(c - 2) + 1 agents, at least c - 1 of them share the same MMS partition of the type outlined in Lemma 16. Then an MMS allocation can be constructed by allocating the goods 1, 2, . . . , n - c to n - c of the other n-c+1 agents. The last of the n-c+1 agents receives her favorite remaining bundle in the shared MMS partition, and the last c-1 agents each receives an arbitrary remaining bundle in the shared MMS partition. This is an MMS allocation, as all but one agent receives a bundle from one of her MMS partitions, and the remaining agent i receives a bundle worth at least (vi(M) - vi({1, 2, . . . , n - c}))/c ≥ (cµi)/c = µi.

While the above argument is sufficient for showing existence for any c > 0, the lower bounds of Rennie and Dobson [1969] on Stirling numbers give nc = {2c c }(c - 2) + 1 > cc . Hence, while straightforward, the argument is not sufficient to prove the bound of Theorem 1, nc ≤ ⌊0.6597c · c!⌋. For that, we will use a more involved inductive argument.

Our inductive procedure builds on the observation that a full MMS allocation need not be found directly. Instead, it is sufficient to use valid reductions to obtain an instance with a smaller number c′ of additional goods. If this smaller instance has at least nc′ agents, an MMS allocation exists for the original instance. Here, the existence for n′ ≥ nc′ with m′ ≤ n′ + c′ is assumed proven, using Lemma 14 and Theorem 2 as base cases. To show the existence of valid reductions, we again exploit the structure of the MMS partitions guaranteed by Lemmas 15 and 16 in order to construct an upper bound on the number of agents required before enough agents have MMS partitions with additional shared structure.

9 If there is an empty bundle, then all n-partitions, including those without empty bundles, are MMS partitions of the agent.

To construct valid reductions, and as a definition of shared structure, we utilize a partial ordering of bundles. For ordered instances, it is often possible to say that some subset of goods B ⊆ M is at least as good as some other subset B′ ⊆ M, no matter the valuation function. Obviously, this holds when B′ ⊆ B, even for non-ordered instances. However, due to the common preference-order of the agents, it could be that B is better than B′ even when B′ ̸⊆ B. For example, when B = {3, 7, 8, 11, 14} and B′ = {6, 7, 11, 13}. As illustrated in Fig. 1, B is at least as valuable as B′ , since vi(3) ≥ vi(6), vi(8) ≥ vi(13), {7, 11} ⊂ B, and {7, 11} ⊂ B′ . We can formalize the partial ordering as follows.

Definition 17. For an ordered instance I = ⟨N,M, V ⟩, a subset of goods B ⊆ M dominates a subset of goods B′ ⊆ M if there is an injective function f : B′ → B such that f(j) ≤ j for all j ∈ B′ . If B dominates B′ , we denote this by B ⪰ B′ . We use B ≻ B′ for the case where B ̸= B′ .

The domination ordering provides a useful set of valid reductions. Whenever an agent i values a bundle B at MMS or higher, and every other agent in the instance has a bundle in her MMS partition that dominates B, then allocating B to i forms a valid reduction.

Lemma 18. Let I = ⟨N,M, V ⟩ be an ordered instance and B be a bundle with vi(B) ≥ µi for some i ∈ N. If each agent i′ ∈ N \ {i} has a bundle Bi′ in her MMS partition with Bi′ ⪰ B, then allocating B to i is a valid reduction.

Proof. For any agent i′ ∈ N \ {i}, we wish to show that her MMS is at least as high in the reduced instance as in the original instance. Since Bi′ ⪰ B, there exists an injective function fi′ : B →Bi′ with fi′(g) ≤ g for g ∈ B. We will show that an MMS partition of i′ can be turned into a n-partition containing B and n - 1 bundles valued at µi′ or higher. Then, in the reduced instance, the MMS of i′ cannot be less than the value of the least valuable bundle among these n-1 bundles, which has a value of at least µi′ . The conversion is done by performing the following steps on an MMS partition of i′ containing Bi′ .

1. Go through the goods g ∈ B from least to most valuable, exchanging the position of g and fi′ (g) in the partition.
2. Move all goods in Bi′ \ B to any other bundle in the partition.

Since fi′(g) ≤ g, after exchanging the position of g and fi′(g) in step 1, g will not move. Further, since fi′ is injective, fi′(g) will not be moved before it is exchanged with g. Thus, since fi′(g) ∈ Bi′ before the step, B ⊆ Bi′ after all the exchanges. Additionally, after step 1 the value of any other bundle in the partition cannot have decreased, as vi′ (g) ≤ vi′ (fi′ (g)). As adding an item to a bundle does not decrease the value of the bundle, step 2 does not decrease the value of other bundles than Bi′ . Thus, afterwards, Bi′ = B and the value of each other bundle remains at least µi′ .

In order to find valid reductions through the domination ordering, we will consider bundles that are of the same size k ≥ 2. 10 When two bundles of size k share a subset of k - 1

10 Bundles of size 1 immediately induce a valid reduction.

goods, we know that one dominates the other, as each bundle only contains one good in addition to the shared subset. 11 With multiple bundles of size k that all share the same subset of k - 1 goods, at least one of the bundles is dominated by all the other bundles. Thus, if for some (k - 1)-sized subset of goods S ⊂ M, each agent has a k-sized bundle containing S in one of her MMS partitions, then there exists a valid reduction that removes one agent and k goods.

Lemma 19. Let I = ⟨N,M, V ⟩ be an ordered instance, k > 0 an integer, and S ⊂ M a subset of k - 1 goods. For each agent i ∈ N, let Bi be a bundle in an MMS partition of i such that |Bi| = k and S ⊂ Bi. Then, there is an agent i′ ∈ N such that allocating Bi′ to i′ is a valid reduction.

Proof. Let g = max{g′ : i ∈ N, g′ ∈ (Bi \ S)}. Then, for any i ∈ N, Bi ⪰ (S ∪ {g}) and there is i′ ∈ N such that Bi′ = S ∪ {g}. By Lemma 18, giving Bi′ to i′ is a valid reduction.

Making use of Lemma 19 requires an instance where all agents share similar k-sized bundles in one of their MMS partitions-a property that usually does not hold for arbitrary instances. However, for any integer c > 0, Lemmas 15 and 16 guarantee that when n > c, all agents have MMS partitions in which any bundle of size greater than one is a subset of the 2c worst goods. Thus, as the number of agents increases, there will eventually be some k ≥ 2 for which some set S of k - 1 goods is shared between k-sized bundles in the MMS partitions of multiple agents. When there are at least c such agents, the combination of Lemmas 15 and 19 provides a way to create a valid reduction removing n′ ≤ n-c+1 agents and n′ +k-1 goods. Simply allocate one of 1, 2, . . . , n-c to each of the at most n - c agents without an MMS partition containing a k-sized bundle with subset S, and use the method of Lemma 19 to allocate a k-sized bundle to one of the remaining agents. This approach can be used in our inductive argument as long as n-n′ ≥ nc-k+1. In other words, there must be at least max(c, nc-k+1 + 1) agents with a k-sized bundle in one of their MMS partitions that has S as a subset.

To obtain the bound in Theorem 1, we will, instead of using max(c, nc-k+1 +1), show that if nc′ ≥ nc′-1 +1 for c′ > 6 and there are at least c agents with a k-sized bundle in their MMS partition, then we only need max(c-k+1, nc-k+1+1) agents with a k-sized bundle sharing the same (k - 1)-sized subset of goods. Our proof relies on a result of Aigner-Horev and Segal-Halevi [2022] on envy-free matchings. 12 In this setting, for a graph G and set X of vertices in G, NG(X) denotes the union of the open neighbourhood in G of each vertex in X.

11 The bundles may be equal. However, by definition they dominate each other when equal.

12 Their result has previously been used in MMS approximation.

Definition 20. A matching M in a bipartite graph G = (X ∪ Y,E) is envy-free with regards to X if no unmatched vertex in X is adjacent in G to a matched vertex in Y .

Theorem 21 (Aigner-Horev and Segal-Halevi, 2022). Given a bipartite graph G = (X ∪ Y, E), there exists a non-empty envy-free matching with regards to X if |NG(X)| ≥ |X| ≥ 1.

Using Theorem 21 and the assumptions described above, we show that an MMS allocation exists if an agent has an MMS partition with at most one bundle containing more than two goods.

Lemma 22. Let I = ⟨N,M, V ⟩ be an ordered instance, with m = n + c goods for some c > 0 and assume that for c > c′ > 5, there exists an integer nc′ > 0 such that all instances with n′ ≥ nc′ agents and m′ = n′ + c′ goods have MMS allocations and nc′ > nc′-1 for c′ > 6. Then, if n > nc-1 and an agent i ∈ N has an MMS partition A with at least n - 1 bundles of size less than three, an MMS allocation exists.

Proof sketch (full proof in extended version). If µi = 0, the result follows from Lemma 10. If µi > 0, each bundle in A, except at most one, has size one or two. We wish to show that unless there exists a perfect matching of agents to bundles in A they value at MMS or more, there instead exists a non-empty envy-free matching that only contains bundles of size one or two. Given such an envy-free matching, a valid reduction that removes x agents and 2x goods can be found by allocating all bundles of size two in the matching before applying Lemma 11 to each bundle of size one.

To find a non-empty envy-free matching, we exploit that Hall's marriage theorem allows us to create a subgraph with fewer agents than bundles, where an envy-free matching in the subgraph is envy-free in the original graph. Agent i will be present in the subgraph, as bundles are from i's MMS partition. Furthermore, there are fewer agents than bundles in the subgraph. Thus, we can additionally remove the bundle of size three or larger, unless already removed, while Theorem 21 still guarantees a non-empty envy-free matching.

Using Lemma 22 we can improve our lower bound on the number of goods valued at MMS or higher by an agent i based on the size of the bundles in their MMS partitions.

Lemma 23. Let I = ⟨N,M, V ⟩ be an ordered instance, with m = n + c goods for some c > 0 and assume that for any c′ > 5, there exists an integer nc′ > 0 such that all instances with n′ ≥ nc′ agents and m′ = n′ + c′ goods have MMS allocations and nc′ > nc′-1 for c′ > 6. If n > nc-1 and agent i ∈ N has an MMS partition A with a bundle of size k > 2, then either vi(n - c + k - 1) ≥ µi or an MMS allocation exists.

Proof. If µi = 0, then vi(n-c+k-1) ≥ µi. Now, assume that µi > 0, and as a result k ≤ c+1. If vi(n-c+k-1) < µi, then at most n - c + k - 2 bundles in A have size one and no bundle is empty. Of the remaining bundles, there is one of size k and the c-k+1 others contain at least two goods each. These bundles of size at least two, contain the remaining n+ c-(n-c+k-2)-k = 2(c-k+1) goods. Thus, each of these bundles contains exactly two goods, and A contains a single bundle of cardinality greater than 2. Consequently, an MMS allocation exists by Lemma 22.

Lemma 23 guarantees an MMS allocation unless vi(n-c+ k - 1) ≥ µi for any agent i with a k-sized bundle. Thus, if there are at least c agents with at k-sized bundle in their MMS partition, we can construct a valid reduction to an instance with any (c-k+1)-sized subset of these agents by allocating one of the goods 1, 2, . . . , n - c + k - 1 to each of the other agents. Hence, as long as there are c agents in the instance with a k-sized bundle in their MMS partition, only max(c - k+1, nc-k+1+1) of them need a shared (k-1)-sized subset.

Theorem 1. For any integer c > 0, there exists an nc ≤ ⌊0.6597c (c!)⌋ such that all instances with n ≥ nc agents and no more than n + c goods have an MMS allocation.

Proof. Lemma 14 guarantees that for any c ≤ 5, an MMS allocation always exists for any number of agents. Further, Theorem 2, which is proven without Theorem 1, guarantees that an MMS allocation always exists when c = 6 and n ≥ 4 < ⌊0.65976 · 6!⌋. Thus, the conditions of the theorem hold for all c < 7 and we only need to consider cases where c ≥ 7.

To show that the theorem holds for every integer c ≥ 7, we will use induction with c < 7 as base case. For a given c ≥ 7, we will assume that the theorem holds for all c′ < c and then show that any instance with at least ⌊0.6597c · c!⌋ agents and at most m = n + c goods has an MMS allocation. That is, we assume that for any integer c′ with 6 < c′ < c, an MMS allocation exists for all instances with at least nc′ = ⌊0.6597c′ · c′ !⌋ agents and at most n′ + c′ goods. Under this assumption we know that ⌊0.6597c′-1 (c′ -1)!⌋ < ⌊0.6597c′ · c′ !⌋ for all values of c′ . Hence, we are able to use Lemmas 22 and 23 and need only consider instances where m = n + c.

Let I = ⟨N,M, V ⟩ be an ordered instance of n agents and m = n + c goods, where n ≥ ⌊0.6597c (c!)⌋. Let AI(i) be an MMS partition of agent i ∈ N of the type described by Lemma 16, maximizing the number of bundles of cardinality one. To show that I has an MMS allocation, we will consider domination between particularly bad bundles in AI(i) of different agents. Since AI(i) contains n disjoint bundles, at most n-1 of these can contain goods in {1, 2, . . . , n-1}. Thus, there is a bundle in AI(i) in which the best good g is such that n ≤ g. Let BI(i) be such a bundle in AI(i). Observe that if |BI(i)| = k for some integer k, BI(i) is one of (c+1 k ) possible k-sized subsets of {n, n + 1, . . . , n + c}.

Before proceeding, we will deal with some special cases, to simplify and tighten the further analysis. If for any agent i ∈ N it holds that µi = 0 or |BI(i)| ≤ 2, then vi({n, n + 1}) ≥ µi and an MMS allocation exists by Lemma 10. If |BI (i)| > c-1, then an MMS allocation exists by Lemma 22. Furthermore, if µi > 0 and |BI(i)| = c - 1, then either an MMS allocation exists by Lemma 22 or AI (i) contains n - 2 bundles of size one and vi(n - 2) ≥ µi. If vi(n - 2) ≥ µi, there could exist a subset N ′ ⊂ N of n - 2 agents such that removing N ′ and {1, 2, . . . , n - 2} forms a valid reduction.

Otherwise, there is a non-empty subset N ′′ ⊂ N of agents and an equally-sized subset M ′′ ⊂ M of at most c goods such that no agent in N \ N ′′ values any good in M ′′ at MMS or higher and there exists a perfect matching between the agents in N ′′ and goods they value at MMS or higher in M ′′ . The method from Lemma 22 can be used to extend the perfect matching to a valid reduction with |N ′′ | agents and 2|N ′′ | goods. Thus, an MMS allocation exists if |BI (i)| = c - 1.

We can now assume that 2 < |BI (i)| < c - 1 and µi > 0 for all i ∈ N. We wish to determine the number of agents required such that for at least one k ∈ {3, 4, . . . , c-2}, there must be at least max(c - k + 1, nc-k+1 + 1) agents with |BI (i)| = k and where the bundles BI (i) share a (k-1)-sized subset of goods. If there are this many agents, Lemmas 19 and 23 guarantee a valid reduction to an instance in which an MMS allocation exists by our inductive hypothesis.

Since BI (i) ⊂ {n, n + 1, . . . , n + c}, there are ( c+1 k-1) possible subsets of size k-1. Since |BI(i)| = k, BI(i) contains k distinct subsets of size k - 1. Thus, if there are at least 1 + z( c+1 k-1)/k agents with |BI(i)| = k for some z ≥ 0, at least z + 1 of the agents have the same (k - 1)-sized subset in their BI(i). If we separately consider subsets contain good n, we get that if there for a k ∈ {3, 4, . . . , c - 2} is at least

agents for which |BI(i)| = k, then there are at least max(ck + 1, nc-k+1 + 1) bundles in the multiset {BI(i) : i ∈ N, |BI(i)| = k} that share the same (k - 1)-sized subset of goods. Combining Eq. (1) for all possible size of BI(i), we get that when there are

agents, there is some 3 ≤ k ≤ c - 2 for which there are at least max(c - k + 1, nc-k+1 + 1) agents with |BI (i)| = k, where the BI (i) share the same (k - 1)-sized subset.

We wish to show that Eq. (2) is bounded from above by ⌊0.6597c (c!)⌋. In order to prove the bound, we make the following observations. Since nc′ = ⌊0.6597c′ ·c′ !⌋ for c > c′ > 0, when k < c - 2 we have max(c - k, nc-k+1) = nc-k+1. Also, since c ≥ 7 we can use Lemma 14 to show that:

Additionally, for any k ∈ {3, 4, . . . , c - 2}, it holds that

Combining the observations with Eq. (2), we get that if there are at least

agents in I, an MMS allocation must exist, since there is some k ∈ {3, 4, . . . , c - 2} for which there are c or more agents with |BI(i)| = k and at least max(c - k + 1, nc-k+1 + 1) of them have the same (k - 1)-sized subset of BI(i). Thus, we must show that Eq. (3) is less than or equal to our bound ⌊0.6597c · c!⌋. We have that for α > 0:

Using the Maclaurin series ey = ∑∞j=0 yj /(j!), we get that

Equation (7) is equal to 1 if α = 0.65964118 . . . , and less than 1 if α is larger. 13 Thus, as a result of Eq. (4), we know from Eq. (3) that the number of required agents is less than or equal to -1 + 0.6597c · c! < ⌊0.6597c · c!⌋. Consequently, I has an MMS allocation by our inductive hypothesis.

4 Improved Bounds for Small Constants

In the previous section, we saw that for any integer constant c > 0, there exists a, rather large, number nc such that all instances with n ≥ nc agents and no more than n + c goods have MMS allocations. There exists some slack in the calculations of the limit, especially for smaller values of c. Moreover, while hard to make use of in the general case, there exist additional, unused properties and interactions between the MMS partitions of different agents. As a result, it is possible to, on a case-by-case basis, show better bounds for small constants by analyzing the possible structures of MMS partitions and their interactions for specific values of c. We state the two following results for c = 6 and c = 7. Both proofs rely on an exhaustive analysis of possible MMS partition structure combinations, and are given in the extended version.

Theorem 2. For an instance with n ̸= 3 agents, an MMS allocation always exists if there are m ≤ n + 6 goods.

Theorem 24. For an instance with m = n + 7 goods, an MMS allocation always exists if there are n ≥ 8 agents.

5 Fair Allocation of Chores

So far we have only considered instances in which the items are goods. In this section, we show that a similar result to the one for goods in Theorem 1 exists for chores. The resulting bounds for nc are somewhat worse for chores due to minor differences in the way that valid reductions can be constructed. The main difference is the lack of a result equivalent to Lemma 10. In practice, this means that while we for goods could ignore bundles of cardinality two in our dominationbased counting argument, we must include bundles of cardinality two for chores. Fortunately, it is possible to show that the bundles of cardinality two that are of interest to us are all the same bundle. Thus, the number of agents with a bundle of cardinality two required to find a reduction is relatively small.

13 The exact value α for which Eq. (7) is equal to 1 can be used in Theorem 1 instead of the rounded value 0.6597.

Lemma 25. Let I = ⟨N,M, V ⟩ be an ordered instance for chores, and i ∈ N an agent with an MMS partition A containing a bundle B with |B| = 2, B ∩ {1, 2, . . . , n - 1} = ∅. Then i has an MMS partition A′ such that (i) |Aj| = |A′j | for all j ∈ N, (ii) {n, n + 1} ∈ A′ , and (iii) the position of the chores 1, 2, . . . , n - 1 is the same in A and A′ .

Proof. Assume that B = {x, y}, where x < y. Let A′ be the allocation equivalent to A, except for that x and y have changed place with, respectively, n and n + 1. We wish to show that A′ is an MMS partition and satisfies (i), (ii) and (iii). In any MMS partition, there must be at least one bundle B′ with |B′ ∩{1, 2, . . . , n+1}| ≥ 2. Thus, vi({n, n+1}) ≥ vi(B′ ) ≥ µi. Since n ≤ x and n + 1 ≤ y, the bundles that contained n and n + 1 are no worse after the swap and A′ is an MMS partition of i.

Since the only difference between A and A′ is two swaps of chores, and {n, n + 1, x, y} ∩ {1, 2, . . . , n - 1} = ∅, both (i) and (iii) hold. Furthermore, after the swap B = {n, n+1} and B ∈ A′ , thus (ii) holds.

The method used to prove Theorem 3 is almost identical to the one used for Theorem 1. The domination property transfers to chores perfectly, except that a bundle that dominates another bundle is now worse (or equivalent to) the bundle it dominates. Consequently, we wish to find a bundle that dominates bundles of the other agents, rather than one that is dominated by bundles of the other agents. Furthermore, one can show that all agents have MMS partitions with a similar structure to the one given in Lemma 16. Due to the close similarity to the proof of Theorem 1 and space constraints, the proof of Theorem 3 is given in the extended version.

Theorem 3. For any integer c > 0, there exists an nc ≤ ⌊0.7838c (c!)⌋ such that all instances with n ≥ nc agents and no more than n + c chores have an MMS allocation.

6 Conclusion and FutureWork

Theorems 1 and 3 show that instances with n agents and n+c items will for any c > 0 have an MMS allocation if n is sufficiently large. The required value for n does, however, grow exponentially in c. As a consequence, the result is mostly of use for instances with few agents, such as the motivating realworld instances, where the value for c is comparably large.

It is probable that the bounds can be improved by an approach that builds upon our domination-based partial ordering. By better understanding how quickly large chains must appear in the ordering, one can potentially replace Eq. (1) or Eq. (2) by a smaller term and obtain a better bound. To this end, we can extend Lemma 16 so that there is no domination within the MMS partition, unless both bundles have size one.