Fair division is the study of how to distribute a set of items among a set of agents in a fair manner. Achieving fairness is particularly challenging when items are indivisible. Computational and conceptual challenges have motivated researchers and practitioners to develop a variety of fairness concepts that are applicable to a large number of allocation problems. 1 One of the most common fairness concepts, proposed by Budish (2011), is Maximin Share (MMS), that aims to give each agent a bundle that is valued at a certain threshold. The MMS threshold, also known as 1-out-of-d MMS, generalizes the guarantee of the cut-and-choose protocol. It is the value that an agent can secure by partitioning the items into d bundles, assuming it will receive the least preferred bundle. The MMS value depends on the number of partitions, d. When all items are goods (i.e., have non-negative values), the 1-out-of-d MMS threshold is (weakly) monotonically decreasing as the number of partitions (d) increases.
When allocating goods among n agents, a natural desirable threshold is satisfying 1out-of-n MMS for all agents. Unfortunately, while this value can be guaranteed for n = 2 agents through the cut-and-choose protocol, a 1-out-of-n MMS allocation of goods may not exist in general for n ≥ 3 (Procaccia & Wang, 2014;Kurokawa, Procaccia, & Wang, 2018). These negative results have given rise to multiplicative approximations, wherein each agent is guaranteed at least a constant fraction of its 1-out-of-n MMS. While there have been many attempts in developing algorithms that improve the bound to close to 1, the best currently known fraction is 3 4 + 1 12n (Garg & Taki, 2020). Despite numerous studies devoted to their existence and computation, there is a conceptual and practical problem with the multiplicative approximations of MMS: they are very sensitive to agents' precise cardinal valuations. To illustrate, suppose n = 3 and there are four goods g 1 , g 2 , g 3 , g 4 that Alice values at 30, 39, 40, 41 respectively. Her 1-out-of-3 MMS is 40, and thus a 3 4 fraction guarantee can be satisfied by giving her the bundle {g 1 } or a bundle with a higher value. But if her valuation of good g 3 changes slightly to 40 + ε (for any ε > 0), then 3 4 of her 1-out-of-3 MMS is larger than 30, the bundle {g 1 } is no longer acceptable for her. Thus, the acceptability of a bundle (in this example {g 1 }) might be affected by an arbitrarily small perturbation in the value of an irrelevant good (i.e. g 3 ).
In the microeconomics literature, it is common to measure agents' preferences as ordinal rankings of the bundles; even when utility functions are used, it is understood that they only represent rankings. From this viewpoint, the set of acceptable bundles should only depend on the ranking of the bundles, and should not be affected by changes in valuations that-similar to the ε change in the value of g 3 -do not affect this ranking. According to this principle, Budish (2011) suggested the 1-out-of-(n + 1) MMS as a relaxation of the 1-out-of-n MMS. In the above example, 1-out-of-4 MMS fairness can be satisfied by giving Alice {g 1 } or a better bundle; small inaccuracies or noise in the valuations do not change the set of acceptable bundles. Hence, this notion provides a more robust approach in evaluating fairness of allocations.
To date, it is not known if 1-out-of-(n + 1) MMS allocations are guaranteed to exist. We aim to find allocations of goods that guarantee 1-out-of-d MMS for some integer d > n. A 1-out-of-d MMS allocation guarantees to each agent a bundle that is at least as good as the worst bundle in the best d-partition.
The aforementioned guarantee can be naturally generalized to -out-of-d MMS (Babaioff, Nisan, & Talgam-Cohen, 2021), that guarantees to each agent the value obtained by partitioning the goods into d bundles and selecting the least-valuable ones. Therefore, we further investigate the -out-of-d MMS generalization that allows us to improve the fairness thresholds. The notion of -out-of-d MMS fairness is robust in the sense that, a fair allocation remains fair even when each agent's utility function goes through an arbitrary monotonically-increasing transformation. Given these notions, we ask the following questions:
In the allocation of indivisible goods, (a) For what combinations of integers and d, can -out-of-d MMS allocations be guaranteed? and (b) For what integers and d can -out-of-d MMS allocations be computed in polynomial time?
We investigate the existence and computation of ordinal MMS approximations and make several contributions.
In Section 4, we prove the existence of -out-of-d MMS allocation of goods when d ≥ ( + 1 2 )n (Theorem 1). In particular, 1-out-of-3n/2 MMS, 2-out-of-5n/2 MMS, 3-out-of-7n/2 MMS, and so on, are all guaranteed to exist. This finding generalizes the previously known existence result of 1-out-of-3n/2 MMS (Hosseini & Searns, 2021).
The proof uses an algorithm which, given lower bounds on the -out-of-d MMS values of the agents, returns an -out-of-d MMS allocation. The algorithm runs in polynomial time given the agents' lower bounds. However, computing the exact -out-of-d MMS values is NP-hard. In the following sections we propose two solutions to this issue.
In Section 5, we present polynomial-time algorithms that find an -out-of-(d + o(n)) MMS-fair allocation, where d = ( + 1 2 )n. Specifically, for = 1, we present a polynomialtime algorithm for finding a 1-out-of-3n/2 MMS allocation (Theorem 2); this matches the existence result for 1-out-of-3n/2 MMS up to an additive gap of at most 1. For > 1, we present a different polynomial-time algorithm for finding a 1-out-of-( + 1
2 )n + O(nfoot_0/3 ) MMS allocation (Theorem 3).
In Appendix A, we conduct simulations with valuations generated randomly from various distributions. For several values of , we compute a lower bound on the -out-of-( + 1 2 )n MMS guarantee using a simple greedy algorithm. We compare this lower bound to an upper bound on the ( 3 4 + 1 12n )-fraction MMS guarantee, which is currently the best known worst-case multiplicative MMS approximation. 2 We find that, for any ≥ 2, when the number of goods is at least ≈ 20n, the lower bound on the ordinal approximation is better than the upper bound on the multiplicative approximation. This implies that, in practice, the algorithm of Section 4 can be used with these lower bounds to attain an allocation in which each agent receives a value that is significantly better than the theoretical guarantees.
At first glance, it would seem that the techniques used to attain 2/3 approximation of MMS should also work for achieving 1-out-of-3n/2 MMS allocations, since both guarantees approximate the same value, namely, the 2 3 approximation of the "proportional share" ( 1 n of the total value of all goods). In Appendix B we present an example showing that this is not the case, and thus, achieving ordinal MMS approximations requires new techniques. In this section, we briefly describe the techniques that we utilize to achieve ordinal approximations of MMS.
Lone Divider. To achieve the existence result for any ≥ 1, we use a variant of the Lone Divider algorithm, which was first presented by Kuhn (1967) for finding a proportional allocation of a divisible good (also known as a "cake"). Recently, it was shown that the same algorithm can be used for allocating indivisible goods too. When applied directly, the Lone Divider algorithm finds only an -out-of-(( +1)n-2) MMS allocation (Aigner-Horev & Segal-Halevi, 2022), which for small is substantially worse than our target approximation of -out-of-( + 1 2 )n . We overcome this difficulty by adding constraints on the ways in which the 'lone divider' is allowed to partition the goods, as well as arguing on which goods are selected to be included in each partition (see Section 4).
Bin Covering. To develop a polynomial-time algorithm when = 1, we extend an algorithm of Csirik, Frenk, Labbè, and Zhang (1999) for the bin covering problem-a dual of the more famous bin packing problem (Johnson, 1973). In this problem, the goal is to fill as many bins as possible with items of given sizes, where the total size in each bin must be above a given threshold. This problem is NP-hard, but Csirik et al. (1999) presents a polynomial-time 2/3 approximation. This algorithm cannot be immediately applied to the fair division problem since the valuations of goods are subjective, meaning that agents may have different valuations of each good. We adapt this technique to handle subjective valuations.
The idea of using the highest utility an agent could obtain if all other agents had the same preferences as a benchmark for fairness, originated in the economics literature (Moulin, 1990(Moulin, , 1992)). It was put to practice in the context of course allocation by Budish (2011), where he introduced the ordinal approximation to MMS, and showed a mechanism that guarantees 1-out-of-(n + 1) MMS to all agents by adding a small number of excess goods. In the more standard fair division setting, in which adding goods is impossible, the first non-trivial ordinal approximation was 1-out-of-(2n-2) MMS (Aigner-Horev & Segal-Halevi, 2022). Hosseini and Searns (2021) studied the connection between guaranteeing 1-out-of-n MMS for 2/3 of the agents and the ordinal approximations for all agents. The implication of their results is the existence of 1-out-of-3n/2 MMS allocations and a polynomial-time algorithm for n < 6. Whether or not 1-out-of-(n + 1) MMS can be guaranteed without adding excess goods remains an open problem to date.
The generalization of the maximin share to arbitrary ≥ 1 was first introduced by Babaioff, Nisan, and Talgam-Cohen (2019), Babaioff et al. (2021), and further studied by Segal-Halevi (2020). They presented this generalization as a natural fairness criterion for agents with different entitlements. The implication relations between -out-of-d MMSfairness guarantees for different values of and d were characterized by Segal-Halevi (2019). Recently, the maximin share and its ordinal approximations have also been applied to some variants of the cake-cutting problem (Elkind, Segal-Halevi, & Suksompong, 2021c, 2021b, 2021a;Bogomolnaia & Moulin, 2022).
The multiplicative approximation to MMS originated in the computer science literature (Procaccia & Wang, 2014). The non-existence of MMS allocations (Kurokawa et al., 2018) and its intractability (Bouveret & Lemaître, 2016;Woeginger, 1997) have given rise to a number of approximation techniques.
These algorithms guarantee that each agent receives an approximation of their maximin share threshold. The currently known algorithms guarantee β ≥ 2/3 (Kurokawa et al., 2018;Amanatidis, Markakis, Nikzad, & Saberi, 2017;Garg, McGlaughlin, & Taki, 2018) and β ≥ 3/4 (Ghodsi, HajiAghayi, Seddighin, Seddighin, & Yami, 2018;Garg & Taki, 2020) in general, and β ≥ 7/8 (Amanatidis et al., 2017) as well as β ≥ 8/9 (Gourvès & Monnot, 2019) when there are only three agents. There are also MMS approximation algorithms for settings with constraints, such as when the goods are allocated on a cycle and each agent must get a connected bundle (Truszczynski & Lonc, 2020). McGlaughlin and Garg (2020) showed an algorithm for approximating the maximum Nash welfare (the product of agents' utilities), which also attains a fraction 1/(2n) of the MMS.
Recently, Nguyen, Nguyen, and Rothe (2017) gave a Polynomial Time Approximation Scheme (PTAS) for a notion defined as optimal-MMS, that is, the largest value, β, for which each agent receives at least a fraction β of its MMS. Since the number of possible partitions is finite, an optimal-MMS allocation always exists, and it is an MMS allocation if β ≥ 1. However, an optimal-MMS allocation may provide an arbitrarily bad ordinal MMS guarantee. Searns and Hosseini (2020), Hosseini and Searns (2021) show that for every n, there is an instance with n agents in which under any optimal-MMS allocation only a constant number of agents (≤ 4) receive their MMS value.
An advantage of the ordinal MMS approximation is that it depends only on the ranking over the bundles. Other fair allocation algorithms with this robustness property are the Decreasing Demands algorithm of Herreiner and Puppe (2002), the Envy Graph algorithm of Lipton, Markakis, Mossel, and Saberi (2004), and the UnderCut algorithm of Brams, Kilgour, and Klamler (2012). Amanatidis, Birmpas, and Markakis (2016), Halpern and Shah (2021) study an even stronger robustness notion, where the agents report only a ranking over the goods. Their results imply that, in this setting, the highest attainable multiplicative approximation of MMS is Θ(1/ log n).
Menon and Larson (2020) define a fair allocation algorithm as stable if it gives an agent the same value even if the agent slightly changes his cardinal valuations of goods, as long as the ordinal ranking of goods remains the same. They show that most existing algorithms are not stable, and present an approximately-stable algorithm for the case of two agents.
Finally, robustness has been studied also in the context of fair cake-cutting. Aziz and Ye (2014) define an allocation robust-fair if it remains fair even when the valuation of an agent changes, as long as its ordinal information remains unchanged. Edmonds and Pruhs (2011) study cake-cutting settings in which agents can only cut the cake with a finite precision.
Let N = [n] := {1, . . . , n} be a set of agents and M denote a set of m indivisible goods. We denote the value of agent i ∈ N for good g ∈ M by v i (g). We assume that the valuation functions are additive, that is, for each subset G ⊆ M , v i (G) = g∈G v i (g), and v i (∅) = 0.foot_1
An instance of the problem is denoted by I = N, M, V , where V = (v 1 , . . . , v n ) is the valuation profile of agents. We assume all agents have a non-negative valuation for each good g ∈ M , that is, v i (g) ≥ 0. An allocation A = (A 1 , . . . , A n ) is an n-partition of M that allocates the bundle of goods in A i to each agent i ∈ N .
It is convenient to assume that the number of goods is sufficiently large. Particularly, some algorithms implicitly assume that m ≥ n, while some algorithms implicitly assume that m ≥ • n. These assumptions are without loss of generality, since if m in the original instance is smaller, we can just add dummy goods with a value of 0 to all agents.
For every agent i ∈ N and integers 1 ≤ < d, the -out-of-d maximin share of i from M , denoted MMS -out-of-d i (M ), is defined as
min
where the maximum is over all partitions of M into d subsets, and the minimum is over all unions of subsets from the partition. We say that an allocation
, and the equality holds if and only if M can be partitioned into d subsets with the same value. Note that MMS -out-of-d i (M ) is a weaklyincreasing function of and a weakly-decreasing function of d.
The value MMS -out-of-d i (M ) is at least as large, and sometimes larger than, •MMS 1-out-of-d i (M ). For example, suppose = 2, there are d -1 goods with value 1 and one good with value
The maximin-share notion is scale-invariant in the following sense: if the values of each good for an agent, say i, are multiplied by a constant c, then agent i's MMS value is also multiplied by the same c, so the set of bundles that are worth for i at least MMS -out-of-d i (M ) does not change.
A general formulation of the Lone Divider algorithm, based on Aigner-Horev and Segal-Halevi (2022), is shown in Algorithm 1. It accepts as input a set M of items and a threshold value t i for each agent i. These values should satisfy the following condition for each agent i ∈ N .
Definition 1 (Reasonable threshold). Given a set M , a value function v i on M , and an integer n ≥ 2, a reasonable threshold for v i is a real number t i ∈ R satisfying the following condition: for every integer k ∈ {0, . . . , n -1} and any
Informally, if any k unacceptable subsets are given away, then i can partition the remainder into n-k acceptable subsets. In particular, the case k = 0 implies that agent i can partition the original set M into n acceptable subsets.
ALGORITHM 1: The Lone Divider algorithm. Based on Kuhn (1967). Input: An instance N, M, V where N is the set of agents, M is the set of items, V is the vector of agents' valuations; and a reasonable threshold vector (t i ) n i=1 as denoted in Definition 1.
1: Some arbitrary agent a ∈ N is asked to partition M into |N | disjoint subsets, (Y j ) j∈N , with ∀j ∈ N : v a (Y j ) ≥ t a .
i=1 of real numbers is called a reasonable threshold vector for I if t i is a reasonable threshold for v i for all i ∈ N .foot_2
Example 1 (Reasonable threshold). Suppose M is perfectly divisible (e.g. a cake), and let t i := v i (M )/n. This threshold is reasonable, since if some k bundles with value less than t i are given away, the value of the remaining cake is more than (n -k)t i . Since the cake is divisible, it can be partitioned into n -k acceptable subsets. This does not necessarily hold when M is a set of indivisible items; hence, finding reasonable thresholds for indivisible items setting is more challenging.
Algorithm Description Algorithm 1 proceeds in the following way: in each step, a single remaining agent is asked to partition the remaining goods into acceptable bundlesbundles whose values are above the divider's threshold. Then, all agents point at those bundles that are acceptable for them, and the algorithm finds an envy-free matching in the resulting bipartite graph. 5 The matched bundles are allocated to the matched agents, and the algorithm repeats with the remaining agents and goods. It is easy to see that, if all threshold values t i are reasonable, then Lone Divider guarantees agent i a bundle with a value of at least t i . For example, when M is a cake, t i = v i (M )/n is a reasonable threshold for every i, so Lone Divider can be used to attain a proportional cake-cutting (Kuhn, 1967).
When M is a set of indivisible goods, Halevi, 2022), so these ordinal approximations can all be computed directly through the Lone Divider algorithm. However, directly applying the Lone Divider algorithm cannot guarantee a better ordinal approximation, as we show next.
Example 2 (Execution of Algorithm 1). For simplicity, we present an example for = 1. We show that, while Algorithm 1 can guarantee (c) The remaining goods, which cannot be combined into n -1 = 3 acceptable bundles. guarantee 1-out-of-(2n -3) MMS. Suppose that there are 4n -6 goods, and that all agents except the first divider value some 2n -3 goods at 1 -ε and the other 2n -3 goods at ε (see Figure 1). Then the 1-out-of-(2n -3) MMS of all these agents is 1.
However, it is possible that the first divider takes an unacceptable bundle containing all 2n -3 goods of value ε. Then, no remaining agent can partition the remaining goods into n-1 bundles of value at least 1. In this instance, it is clear that while MMS
In this section we prove the following theorem.
Theorem 1. Given an additive goods instance, an -out-of-d MMS allocation always exists when
The proof is constructive: we present an algorithm (Algorithm 2) for achieving the above MMS bound. Since the algorithm needs to know the exact MMS thresholds for each agent (which is NP-hard to compute), its run-time is not polynomial. In Section 5 we present a different algorithm to compute -out-of-d MMS allocation when = 1 in polynomial-time.
Algorithm 2 starts with two normalization steps, some of which appeared in previous works and some are specific to our algorithm. For completeness, we describe the normalization steps in Sections 4.1 and 4.2. The algorithm applies to the normalized instance an adaptation of the Lone Divider algorithm, in which the divider in each step must construct a balanced partition. We explain this notion in Section 4.3.
We start by scaling the valuations such that MMS -out-of-d i (M ) = for each agent i. The scale-invariance property implies that such rescalings do not modify the set of bundles that are acceptable for i. Then, for each i we perform an additional scaling as follows.
• Consider a particular d-partition attaining the maximum in the MMS -out-of-d i (M ) definition. Call the d bundles in this partition the MMS bundles of agent i.
• Denote the total value of the -1 least-valuable MMS bundles by x i (or just x, when i is clear from the context). By definition, the value of the -th MMS bundle must be exactly -x, while the value of each of the other d -MMS bundles is at least -x.
• For each MMS bundle with value larger than -x, arbitrarily pick one or more goods and decrease their value until the value of the MMS bundle becomes exactly -x.
Note that this does not change the MMS value.
After the normalization, the sum of values of all goods is
The goal of the algorithm is to give each agent i a bundle A i with v i (A i ) ≥ . We say that such a bundle is acceptable for i.
Example 3 (Scaling). To illustrate the parameter x, consider the following two instances with n = 5, = 3 and d = ( + 1 2 )n = 17.
1. There are 17 goods with the value of 1.
2. There are 16 goods valued 1.2 and one good with the value of 0.6.
Here, each MMS bundle contains a single good. In both cases, the value of every 3 goods is at least 3. In the first case x = 2 and the total value is 5
In the second case, x = 1.8 and the total value is 5
As in previous works (Bouveret & Lemaître, 2016;Barman & Krishna Murthy, 2017;Garg et al., 2018;Huang & Lu, 2021), we apply a preliminary step in which the instance is
Ordering is done as follows:
• Index the goods in M arbitrarily g 1 , . . . , g m .
ALGORITHM 2: Finding an -out-of-( + 1 2 )n MMS allocation. Input: An instance N, M, V and an integer ≥ 1. Output: An -out-of-( + 1 2 )n MMS allocation. 1: Scale the valuations of all agents as explained in Section 4.1. 2: Order the instance as explained in Section 4.2. 3: Run the Lone Divider algorithm (Algorithm 1) with threshold values t i = for all i ∈ N , with the restriction that, in each partition made by the lone divider, all bundles must be -balanced (Definition 2).
• Tell each agent i to adopt, for the duration of the algorithm, a modified value function that assigns, to each good g j , the value of the j-th most valuable good according to i. For example, the new v i (g 1 ) should be the value of i's most-valuable good; the new v i (g m ) should be the value of i's least-valuable good; etc. Ties are broken arbitrarily.
During the execution of the algorithm, each agent answers all queries according to this new value function. For example, an agent asked whether the bundle {g 1 , g 4 , g 5 } is acceptable, should answer whether the bundle containing his best good, 4th-best good and 5th-best good is acceptable. Once the algorithm outputs an allocation, it can be treated as a picking sequence in which, for example, an agent who receives the bundle {g 1 , g 4 , g 5 } has the first, fourth and fifth turns. It is easy to see that such an agent receives a bundle that is at least as good as the bundle containing her best, 4th-best and 5th-best goods. Hence, if the former is acceptable then the latter is acceptable too.
Clearly, given an unordered instance, its corresponding ordered instance can be generated in polynomial time (for each agent i ∈ [n], we need O(m log m) steps for ordering the valuations). Given an allocation for the ordered instance, one can compute the allocation for the corresponding unordered instance in time O(n), using the picking-sequence described above.
In Section 3.3 we illustrated the limitations of the plain Lone Divider algorithm (Algorithm 1). We can improve its performance by restricting the partitions that the lone divider is allowed to make in Step 1 of Algorithm 1. Without loss of generality, we may assume (by adding dummy goods if needed) that m ≥ n • .
For every l ∈ {1, . . . , }, denote G n l := {g (l-1)n+1 , . . . , g ln }. In other words, G n 1 contains the n most-valuable goods; G n 2 contains the n next most-valuable goods; and so on. Since the instance is ordered, these sets are the same for all agents.
Definition 2 ( -balanced bundle). Given an ordered instance and an integer ≥ 1, a nonempty bundle B ⊆ M is called -balanced if
• B contains exactly one good from G n 1 .
• If |B| ≥ 2, then B contains exactly one good from G n 2 .
• If |B| ≥ 3, then B contains exactly one good from G n 3 .
• . . .
Note that an -balanced bundle contains at least goods. The definition of -balanced bundles only constrains the allocation of the first n goods; there may be arbitrarily many additional goods in M \ i=1 G n i , and they may be allocated arbitrarily.
Algorithm 2 requires the lone divider to construct a partition in which all n bundles are -balanced.
Example 4 ( -balanced bundles). Suppose there are five agents (n = 5) and m = 20 goods, where the value of each good j ∈ [20] is precisely j for all agents. Then, a 1-balanced bundle must contain a good j ∈ {20, 19, 18, 17, 16}; a 2-balanced bundle must contain a good from {20, 19, 18, 17, 16} and a good from {15, 14, 13, 12, 11}; a 3-balanced bundle must contain, in addition to these, a good from {10, 9, 8, 7, 6}; and so on.
In order to prove the correctness of Algorithm 2, it is sufficient to prove that the threshold value t i = is a reasonable threshold (see Definition 1) for each agent i, with the additional restriction that all bundles should be -balanced.
To do this, it is sufficient to consider a single divider, Alice. We denote her normalized ordered value measure by v, and the sum of her -1 least-valuable MMS bundles by x. We consider a particular MMS partition for Alice, and refer to the bundles in this partition as the MMS bundles.
Assume that k unacceptable bundles (B c ) k c=1 have already been given to other agents and that all these bundles are -balanced. Therefore, for each c ∈ [k], it must be that v(B c ) < . 6 We have to prove that Alice can use the remaining goods to construct n -k acceptable bundles that are also -balanced. Particularly, we prove below that Alice can construct n -k acceptable bundles, each of which contains exactly 1 remaining good from each of G n 1 . . . , G n .
Given a bundle B a , denote its waste by w(B a ) := v(B a ) -. This is the value the bundle contains beyond the acceptability threshold of . Note that the waste of acceptable bundles is positive and that of unacceptable bundles is negative. The total initial value for Alice is given by (1). The total waste she can afford in her partition is therefore
The first term implies that she can afford an average waste of ( -x)/2 for n-1 bundles; the second term implies that she can afford an average waste of ( -1 -x) for n -1 bundles.
Example 5 (Bounding the waste). Consider Example 3. In case (1), the total value is 17 and we need 5 bundles with a value of 3, so the affordable waste is 2. The average over 4 bundles is 0.5 = (3 -2)/2 + 3 • 0. In case (2), the total value is 19.8, so the affordable waste is 4.8. The average over 4 bundles is 1.2 = (3 -1.8)/2 + 3 • (0.2). In both cases, if there are 4 acceptable bundles with that amount of waste, then the remaining value is exactly 3, which is sufficient for an additional acceptable bundle.
The following lemma formalizes this observation.
Lemma 1. Suppose there exists a partition of M into
• Some t ≥ 0 bundles with an average waste of at most ( -x)/2 + ( -1 -x);
• A subset S of remaining goods, with v(S) < .
Then t ≥ n.
Proof. For brevity, we denote w := ( -x)/2 + ( -1 -x). The total value of the bundles equals their number times their average value. So the total value of the t bundles is at most t • + t • w. After adding v(S) < for the remaining goods, the sum equals v(M ), so
Therefore, at least one of the two terms in the top expression must be larger than the corresponding term in the bottom expression. This means that either (t + 1) > n , or tw > (n -1)w. Both options imply t ≥ n.
Remark 1. The value of each MMS bundle is at most -x. Therefore, any bundle that is the union of exactly such MMS bundles has a waste of at most ( -x) -= ( -1 -x) and thus it satisfies the upper bound of Lemma 1. In particular, this is satisfied for every bundle with at most goods.
Below we show how Alice can find a partition in which the average waste is upper bounded as in Lemma 1. This partition will consist of the following bundles:
• The k previously-allocated bundles, with waste < 0 (since they are unacceptable);
• Some newly-constructed bundles with exactly goods and waste ≤ ( -1 -x) (by Remark 1);
• Some newly-constructed bundles with waste at most ( -x)/2;
• Some pairs of bundles, where the waste in one is larger than ( -x)/2 but the waste in the other is smaller than ( -x)/2, such that the average is at most ( -x)/2.
Recall that before Alice's turn, some k bundles have been allocated, with a value of less than . Hence, their waste is less than 0. Since these bundles are -balanced, they contain exactly one good from each of G n 1 , . . . , G n (and possibly some additional goods). Therefore, exactly n -k goods are available in each of G n 1 . . . , G n . Next, Alice checks all the -tuples containing one good from each of G n 1 . . . , G n (starting from the highest-valued goods in each set). If the value of such an -tuple is at least , then it is acceptable and its waste is at most ( -1 -x) by Remark 1.
After Step 0, there are some k ≥ k bundles with a waste of at most ( -1x), each of which contains exactly one good from each of G n 1 . . . , G n . Of these, k are previously-allocated bundles, and k -k are newly-constructed acceptable bundles. In each of G n 1 . . . , G n , there remain exactly n -k goods. The total value of each -tuple of remaining goods from G n 1 . . . , G n is less than . Alice will now construct from them some n -k bundles with an average waste of at most ( -x)/2 + ( -1 -x). Lemma 1 implies the following lemma on the remaining goods (the goods not in these k bundles):
Lemma 2. Suppose there exists a partition of the remaining goods into • Some t ≥ 0 bundles with an average waste of at most ( -x)/2 + ( -1 -x);
• A subset S of remaining goods, with v(S) < .
Then t ≥ n -k .
Alice's strategy branches based on the number of high-value goods.
We define high-value goods as goods g with v(g) > ( -x)/2. Denote by h the number of high-valued goods in M . Since the instance is ordered, goods g 1 , . . . , g h are high-valued. All MMS bundles are worth at most -x, and therefore may contain at most one high-value good each. Since the number of MMS bundles is n + n/2, we have h ≤ n + n/2.
For each j ∈ [h], we denote
• M j := the MMS bundle containing g j . Since the value of all MMS bundles is at most ( -x), each MMS bundle contains at most one high-value good, so the M j are all distinct.
• R j := the remainder set of g j , i.e., the set M j \ {g j }.
• r j := v(R j ).
We consider three cases, based on the number of high-value goods.
Case #1: h ≤ n. This means that all high-value goods are contained in
Alice constructs the required bundles by bag-filling-a common technique in MMS approximations (e.g. Garg et al. (2018)).
• Repeat at most n -k times:
-Initialize a bag with a good from each of G n 1 . . . , G n (Step 0 guarantees that the total value of these goods is less than ).
-Fill the bag with goods from outside G n 1 . . . , G n . Stop when either no such goods remain, or the bag value raises above . Since all goods used for filling the bag have a value of at most ( -x)/2, the waste of each constructed bundle is at most ( -x)/2. By construction, all these bundles are acceptable except the last one. Apply Lemma 2 with S being the set of goods remaining in the last bag, and t being the number of acceptable bundles constructed by bag-filling. The lemma implies that t ≥ n -k .
Case #2: k ≥ n/2. Alice uses bag-filling as in Case #1.
Here, the waste per constructed bundle might be more than ( -x)/2. However, since the value of a single good is at most -x, the waste of each constructed bundle is at most -x.
In each of the k bundles of Step 0, the waste is at most ( -1 -x). Since k ≥ n/2 ≥ n -k , the average waste per bundle is at most ( -1 -x) + ( -x)/2. Hence Lemma 2 applies, and at least n -k acceptable bundles are constructed.
Case #3: h > n and k < n/2. In this case, Alice will have to construct some bundles with waste larger than ( -x)/2. However, she will compensate for it by constructing a similar number of bundles with waste smaller than ( -x)/2, such that the average waste per bundle remains at most ( -x)/2.
After removing (B c ) k c=1 , exactly h -k high-value goods remain. They can be partitioned into two subsets:
This is the hardest case; to handle this case, we proceed to Step 1 below.
Step 1: Bundling High-value Goods.
Alice constructs at most |H -| bundles as follows.
• Repeat while H -is not empty:
-Initialize a bag with the lowest-valued remaining good from each of G n 1 . . . , G n (Step 0 guarantees that their total value is less than ).
-Fill the bag with goods from H -, until the bag value raises above .
. . , G n is nonempty too, and Alice can indeed repeat. By construction, all filled bags except the last one are valued at least ; it remains to prove that the number of these bags is sufficiently large.
Let s be the number of acceptable bundles constructed once H -becomes empty. Note that, in addition to these bundles, there may be an incomplete bundle -the last bundle, whose construction was terminated while its value was still below .
Let P + ⊆ H + be the set of s goods from H + in the acceptable bundles. Denote by P -⊆ H -the set of s goods from H -that were added last to these s bundles (bringing their value from less-than-to at-least-). Note that the waste in each of these s bundles might be larger than ( -x)/2, but it is at most the value of a single good from P -, so the total waste is at most j∈P -v(g j ).
After this step, besides the s acceptable bundles, there are some (n -k -s) high-value goods remaining in H + (some of these goods are possibly in the incomplete bundle, if such a bundle exists). Alice now has to construct from them some n -k -s acceptable bundles.
Step 2: Using the Remainders.
Alice now constructs acceptable bundles by bag-filling. She initializes each bag with the incomplete bundle from Step 1 (if any), or with an -tuple of unused goods from G n 1 . . . , G n . Then, she fills the bag with low-value goods from the following remainder sets:
• There are k remainder sets that correspond to the k goods allocated within the k unacceptable bundles (B c ) k c=1 . We denote them by R U c,1 , . . . , R U c, and their values by
• There are s + s remainder sets that correspond to the s high-value goods in P + and the s high-value goods in P -. We denote them by R P j and their values by r P j for j ∈ P + ∪ P -.
By definition, the total value of all these remainders is:
For each remainder-set R j , denote by R j , the subset of R j that remains after removing the at most k unacceptable bundles (B c ) k c=1 with more than goods. 7 Each unacceptable bundle B c contains, in addition to the high-value goods g c,l for l ∈ {1, . . . , }, some low-value goods with a total value of less than l=1 r U c,l (since the total value of the unacceptable bundle is less than ). Therefore, the total value of low-value goods included in these unacceptable bundles is at most k c=1 l=1 r U c,l (equality holding iff k = 0). Therefore, the 7. Bundles Bc with at most goods do not consume anything from the remainder-sets Rj, since they contain only high-value goods from G n 1 , . . . , G n . From the same reason, the k -k acceptable bundles constructed in Step 0 do not consume anything from the remainder sets.
total remaining value satisfies
The bag-filling proceeds as follows.
1. Initialize a := 1.
Step 1 (if any), or some unused top goods. We denote the top goods used for initializing bag a by g j
3. Add to the bag the remainder-sets R P j and R U c,l in an arbitrary order. Stop when either no such remainder-sets remain, or the bag value raises above .
4. If there are still some unused remainder-sets and high-value goods, let a := a + 1 and go back to Step 2.
The bag-filling stops when either there are no more high-value goods, or no more remainder-sets. In the former case, Alice has all n -k required bundles (s from Step 1 and n -k -s from Step 2), and the construction is done. We now analyze the latter case.
By construction, we go to the next bag only after the current bag becomes at least . Therefore, all bags except the last one are valued at least . Our goal now is to prove that the number of these "all bags except the last one" is sufficiently large.
Let t be the number of bundles constructed with a value of at least . For each a ∈ [t], The a-th bag contains the high-value goods g j[a,1] , . . . , g j[a, ] and some remainder-sets. How much remainder-sets should it contain? Suppose it contains remainder-sets with a total value of l=1 r j[a,l] . Then, the total bundle value is l=1 v(M j[a,l] ). By assumption, the total value of every MMS bundles is at least , so the bundle value is at least . Therefore, to make bundle a acceptable, it is sufficient to add to it a value of l=1 r j [a,l] .
Denote by j[a, * ] the index of the last remainder-set added to bag a (bringing its value from less-than-to at-least-). The total value of remainder-sets in the bag is thus less than r j[a, * ] + l=1 r j[a,l] .
The total value of remainder-sets in the unfilled (t + 1)-th bag is less than l=1 r j[t+1,l] , where j[t + 1, 1], . . . , j[t + 1, ] are indices of some remaining high-value goods. Therefore, the total value of remainder-sets in all t + 1 bags together satisfies
In the left-hand side there are (t + 1) + t = ( + 1)t + terms, while in the right-hand side there are ( + 1)s terms -+ 1 for each bundle constructed in Step 1. We now show that each term in the left-hand side is equal or smaller than a unique term in the right-hand side. Since the left-hand side is overall larger than the right-hand side, this indicates that the left-hand side must have more terms, that is, ( + 1)t + > ( + 1)s. This implies that t ≥ s, i.e., Alice has successfully constructed from the remainder-sets some s acceptable bundles.
• Consider first the (t + 1) terms r j[a,l] , and compare them to r P j for j ∈ P + . Since the bundles in Step 1 were constructed in ascending order of value, starting at the lowest-valued available goods in each of G n 1 . . . , G n , every index j[a, l] is smaller than any index j ∈ G n l . Therefore, every term r j[a,l] is smaller than some unique term r P j for j ∈ G n l , for every l ∈ [ ].
• Consider now the t terms r j[a, * ] , and compare them to r P j for j ∈ P -. Each of the indices j[a, * ] is an index of some unique remainder-set, so it is either equal to some unique index j ∈ P + ∪ P -, or to some unique index c,l (the index some remainder-set R U c,l of some unacceptable bundle B c ). All indices c,l are in {1, . . . , n}, so they are smaller than the indices j ∈ P -. Therefore, every r j[a, * ] is either equal or smaller than some unique term r P j for j ∈ P -.
So Alice has s new acceptable bundles. The waste of each of these is r j[a, * ] , which -as mentioned above -is equal to or smaller than some unique term r P j for j ∈ P -. Therefore, the total waste of all these s bundles is at most the following sum of s terms:
j∈P -r P j . Recall that the waste of each of the s acceptable bundles from Step 1 was at most v(g j ) for some j ∈ P -. Therefore, the total waste of the 2s acceptable bundles constructed so far is at most
by the normalization (Section 4.1)
Therefore, the average waste per bundle is at most s( -x)/(2s) = ( -x)/2.
Step 3: Plain Bag-Filling.
At this stage, there are no more high-value goods outside H + . Therefore, Alice can construct the remaining bundles by plain bag-filling, initializing each bag with some -tuple of unused goods remaining in H + , and filling it with some low-value goods outside H + . Since the waste in each bundle is at most ( -x)/2, Lemma 2 implies that the total number of constructed bundles is n -k . This completes the proof that is a reasonable threshold for Algorithm 2. Therefore, the algorithm finds the allocation promised in Theorem 1.
To illustrate the limitation of Algorithm 2, we show that it cannot guarantee 1-out-of- (( + 1 2 )n -2) MMS. For simplicity we assume that n is even so that ( + 1 2 )n is an integer.
Example 6 (Tight bound for our technique). Suppose that in the first iteration all agents except the divider have the following MMS bundles:
• n -1 bundles are made of two goods with values 1 -ε and ε.
• One bundle is made of two goods with values 1 -nε and nε.
• n/2 -2 bundles are made of two goods with values 1/2, 1/2.
So their 1-out-of-( n + n/2 -2) MMS equals . However, it is possible that the first divider takes an unacceptable bundle containing -1 goods of value 1-ε, the good of value 1-nε, and the n -1 goods of value ε. Note that this bundle is -balanced. All remaining goods have a value of less than 1, so an acceptable bundle requires at least + 1 goods. However, the number of remaining goods is only n -+ 1 + n -4 = ( + 1)(n -1) -2: n -goods of value 1 -ε, one good of value nε and n -4 goods of value 1/2. Hence, at most n -2 acceptable bundles can be constructed.
Figure 2: An illustration of the goods' values in Example 6, for n = 6 and = 2. Here, ( + 1/2)n -2 = 13. The 2-out-of-13 MMS is 2. Each rectangle represents an MMS bundle containing two goods. The first divider takes the goods marked by a bullet. Note that this is a 2-balanced bundle. The next divider cannot construct 5 bundles of value 2 from the remaining goods.
Algorithm 2 guarantees that each agent receives an -out-of-d MMS allocation for d ≥ ( + 1 2 )n . However, the algorithm requires exact MMS values to determine whether a given bundle is acceptable to each agent. Since computing an exact MMS value for each agent is NP-hard, Algorithm 2 does not run in polynomial-time even for the case of = 1. The objective of this section is to develop polynomial-time approximation algorithms for computing -out-of-d MMS allocations.
We utilize optimization techniques used in the bin covering problem. This problem was presented by Assmann, Johnson, Kleitman, and Leung (1984) as a dual of the more famous bin packing problem. In the bin covering problem, the goal is to fill bins with items of different sizes, such that the sum of sizes in each bin is at least 1, and subject to this, the number of bins is maximized. This problem is NP-hard, but several approximation algorithms are known. These approximation algorithms typically accept a bin-covering instance I as an input and fill at least a • (OP T (I) -b) bins, where a < 1 and b > 0 are constants, and OP T (I) is the maximum possible number of bins in I. Such an algorithm can be used directly to find an ordinal approximation of an MMS allocation when all agents have identical valuations. Our challenge is to adapt them to agents with different valuations.
For the case when = 1, we adapt the algorithm of Csirik et al. (1999), which finds a covering with at least 2 3 • (OP T (I) -1) bins (an approximation with a = 2 3 and b = 1). Algorithm 3 generalizes the aforementioned algorithm to MMS allocation of goods. Thus, the algorithm of Csirik et al. (1999) corresponds to a special case of Algorithm 3 wherein • All agents have the same v i (describing the item sizes); and ALGORITHM 3: Bidirectional bag-filling Input: An instance N, M, V and threshold values (t i ) n i=1 . Output: At most n subsets A i satisfying v i (A i ) ≥ t i .
1: Order the instance in descending order of value as in Section 4.2, so that for each agent i,
Initialize a bag with the good g k .
Add to the bag zero or more remaining goods in ascending order of value, until at least one agent i values the bag at least t i .
Give the goods in the bag to an arbitrary agent i who values it at least t i .
If every remaining agent i values the remaining goods at less than t i , stop. 7: end for • All agents have the same t i (describing the bin size). 8
For this case, we have the following lemma:
Lemma 3 (Lemma 4 of Csirik et al. (1999)). When all agents have the same valuation v and the same threshold t, Algorithm 3 allocates at least 2 3 (OP T (v, t) -1) bundles, where OP T (v, t) is the maximum number that can be filled.
Note that Algorithm 3 works for any selection of the threshold values t i , but if the thresholds are too high, it might allocate fewer than n bundles. Our challenge now is to compute thresholds for which n bundles are allocated. To compute a threshold for agent i, we simulate Algorithm 3 using n clones of i, that is, n agents with valuation v i . We look for the largest threshold for which this simulation allocates at least n bundles.
Definition 3. The 1-out-of-n bidirectional-bag-filling-share of agent i, denoted BBFS n i , is the largest value t i for which Algorithm 3 allocates at least n bundles when executed with n agents with identical valuation v i and identical threshold t i .
The BBFS of agent i can be computed using binary search up to ε, where ε is the smallest difference between values that is allowed by their binary representation. The following lemma relates the BBFS to the MMS. Lemma 4. For any integer n ≥ 1 and agent i ∈ [n],
. By definition of MMS, there is a partition of M into 3 2 n bundles of size at least t i . By Lemma 3, the Bidirectional-Bag-Filling algorithm with valuation v i and bin-size t i fills at least 2 3 ( 3 2 n -1) bundles, which means at least n bundles 8. There is a minor difference: we initialize the first bag with only a single good from the left (g1) before filling it with goods from the right (gm, gm-1, . . .). In contrast, Csirik et al. (1999) fill the first bag with several goods from the left (g1, g2, . . . while its value is less than the bin size), and only then start filling it with goods from the right. However, this difference is not substantial: their proof of the approximation ratio assumes only that each bin has at least one good from the left and one good from the right, so the same proof holds for our variant.
since the number of bundles is an integer. By definition of the BBFS, since Algorithm 3 allocates at least n bundles with threshold t i , we have t i ≤ BBFS n i .
We define an allocation as BBFS-fair if it allocates to each agent i ∈ [n] a bundle with a value of at least BBFS n i . Lemma 4 indicates that a BBFS-fair allocation is also 1-out-of-3n/2 MMS-fair, though the BBFS may be larger than 1-out-of-3n/2 MMS. Lemma 5. A BBFS-fair allocation always exists, and can be found in time polynomial in the length of the binary representation of the problem.
Proof. We first show that, when Algorithm 3 is executed with threshold values t i = BBFS n i for all i ∈ [n], it allocates n bundles. For each j ≥ 1, denote:
• A j -the bundle allocated at iteration j of Algorithm 3 with the true (different) valuations v 1 , . . , v n .
• B i j -the bundle allocated at iteration j of agent i's successful simulation with threshold t i = BBFS n i .
We claim that, for every k ≥ 1, the set of goods allocated before step k by the global algorithm is a subset of the goods allocated before step k during agent i's simulation, .
That is, k-1 j=1 A j ⊆ k-1 j=1 B i j for any remaining agent i. The claim is proved by induction on k. The base is k = 1. Before step 1, both k-1 j=1 A j and k-1 j=1 B i j are empty, so the claim holds vacuously. Let k ≥ 1. We assume the claim is true before iteration k, and prove that it is still true after iteration k. The initial goods g 1 , . . . , g k are obviously allocated in both runs. In agent i's simulation, some additional goods g m , . . . , g s are allocated, for some s ≤ m; in the global run, goods g m , . . . , g r are allocated, for some r ≤ m. The induction assumption implies that r ≥ s (weakly fewer goods are allocated in the global run). In iteration k, both runs initialize the bag with the same good g k . In i's simulation, the bag is then filled with goods g s-1 , . . . , g s for some s < s, such that v i ({g k , g s-1 , . . . , g s }) ≥ t i . In the global run, the bag is filled with goods g r-1 , . . . , g r for some r < r. It is sufficient to prove that r ≥ s . Indeed, if no agent takes the bag until it contains the goods ({g k , g r-1 , . . . , g s }), then because r ≥ s, the bag value is at least v i ({g k , g s-1 , . . . , g s }) ≥ t i . Therefore, it is acceptable to agent i, so the algorithm allocates it (either to i or to another agent).
This completes the proof of the claim. The claim implies that, as long as k < n, the goods in B i n are still available. This means that agent i values the remaining goods at least t i . This is true for every remaining agent; therefore, the global algorithm continues to run until it allocates n bundles.
The binary search and the simulation runs for each agent i take time polynomial in the length of the binary representation of the valuations. Once the thresholds are computed, Algorithm 3 obviously runs in polynomial time. This completes the proof of the lemma.
Theorem 2. There is an algorithm that computes a 1-out-of-3n/2 MMS allocation in time polynomial in the length of the binary representation of the problem.
Example 7 (Computing thresholds). Consider a setting with m = 6 goods and n = 3 agents with the following valuations:
Each player computes a threshold via binary search on [0, v i (M )] for the maximum value t i such that the simulation of Algorithm 3 yields three For agent 1, the simulation with t 1 = 9 yields bundles {g 1 }, {g 2 , g 6 }, {g 3 , g 4 , g 5 }. The corresponding simulation with t 1 = 10 yields bundles {g 1 }, {g 2 , g 5 , g 6 } with {g 3 , g 4 } insufficient to fill a third bundle.
After all thresholds have been determined from simulations, Algorithm 3 computes the circled allocation. Theorem 2 guarantees that this allocation is at least 1-out-of-5 MMS.
Here the circled allocation satisfies 1-out-of-3 MMS.
Remark 2. When n is odd, there is a gap of 1 between the existence result for 1-out-of-3n/2 MMS, and the polynomial-time computation result for 1-out-of-3n/2 MMS.
In experimental simulations on instances generated uniformly at random, Algorithm 3 significantly outperforms the theoretical guarantee of 1-out-of-3n/2 MMS. In Appendix C, we provide detailed experimentations and compare the bidirectional bag-filling algorithm with other bag-filling methods (e.g. the unidirectional bag-filling algorithm).
So far, we could not adapt Algorithm 3 to finding an -out-of-( + 1/2)n MMS allocation for ≥ 2. Below, we present a weaker approximation to MMS, based on the following lemma.
Lemma 6. For all integers d > ≥ 1:
Proof. For the leftmost inequality, Let A 1 , . . . , A d be the optimal d-partition in the definition of MMS 1-out-of-d (M ), and suppose w.l.o.g. that the bundles are ordered by ascending value. Then:
where the last inequality follows from the existence of a d-partition in which the leastvaluable bundles are A 1 , . . . , A .
For the rightmost inequality, let B 1 , . . . , B d be the optimal d-partition in the definition of MMS -out-of-d (M ), and suppose w.l.o.g. that the bundles are ordered by ascending value.
Then:
where the last inequality is proved by the partition with (d -+ 1) bundles:
. . , B d , in which the value of each bundle is at least v i (B ).
For any positive integer d, we can approximate MMS 1-out-of-d (M ) by using an approximation algorithm for bin-covering, which we call Algorithm JS (Jansen & Solis-Oba, 2003).
Lemma 7 (Jansen and Solis-Oba (2003)). For any ε > 0, Algorithm JS runs in time O 1 ε 6 m 2 + 1 ε 8.76 . 9 If the sum of all valuations is at least 13t/ε 3 (where t is the bin size), then Algorithm JS fills at least (1 -ε) • OPT(I) -1 bins.
We can choose ε based on the instance, and get the following simpler guarantee. Proof. If any input value is at least t, then it can be put in a bin of its own, and this is obviously optimal. So we can assume w.l.o.g. that all input values are smaller than t.
Let s be the sum of values, and set ε := (13t/s) 1/3 . The number of bins in any legal packing is at most s/t, so OPT ≤s/t t/s ≤1/OPT ε ≤(13/OPT) 1/3 ≈ 2.35/OPT 1/3 . The ε is chosen such that s = 13t/ε 3 . So by Lemma 7, the number of bins filled by Algorithm JS is at least
Since by assumption each value is smaller than t, we have s < mt, so ε > (13/m) 1/3 and 1/ε ∈ O(m 1/3 ). Therefore, the run-time is in
≈ O m 4 . 9. A more exact expression for the run-time is
, where TM(x) is the run-time complexity of the best available algorithm for matrix inversion, which is currently O(x 2.38 ). We simplified it a bit for clarity, and used O to hide the logarithmic factors.
For the polynomial-time algorithm when = 1, we extend the bin covering algorithm of Csirik et al. (1999). We believe that the interaction between this problem and fair allocation of goods may be of independent interest, as it may open new ways for developing improved algorithms. For example, Csirik et al. (1999) also present a 3/4 approximation algorithm for bin covering, which may potentially be adapted to yield a 1-out-of-4n/3 MMS allocation. Similarly, Csirik, Johnson, and Kenyon (2001) and Jansen and Solis-Oba (2003) present polynomial-time approximation schemes for bin covering, which may yield even better MMS approximations in future work.
Finally, it is interesting to study ordinal maximin approximation for items with nonpositive valuations (i.e. chores), as well as for mixtures of goods and chores. Techniques for allocation of goods do not immediately translate to achieving approximations of MMS when allocating chores, so new techniques are needed (Hosseini, Searns, & Segal-Halevi, 2022).
Our ordinal guarantees may be better than the best known multiplicative MMS approximation (i.e. 3/4) when the number of goods is large compared to the number of agents.
To illustrate, consider the extreme case in which there are infinitely many goods of equal value (alternatively, suppose there are infinitely many goods with values that are independent and identically-distributed random variables). Then 1-out-of-n MMS converges to 1/n (with probability 1, by the law of large numbers). 10 The -out-of-( + 1
2 )n MMS converges to 2 /(2 + 1) of this value, which is larger than 3/4 + 1/(12n) for ≥ 2, and approaches 1 when → ∞.
In this section, we present a simple simulation experiment that compares the value of the -out-of-d MMS guaranteed by Theorem 1 (where d = ( + 1/2)n ) with the best known multiplicative approximation of 1-out-of-n MMS, which is 3 4 + 1 12n (Garg & Taki, 2020). Our results show that the ordinal approximation for ≥ 2 is better than the multiplicative approximation already for m ≈ 20n, when the values are sampled from some natural distributions. We note that the simulations only compare the worst-case guarantees and not the actual algorithm performance.
Since computing the exact MMS is NP-hard, 11 we used a lower bound for our ordinal approximation and an upper bound for the "competition", so that our ratio is a lower bound for the real ratio. For our ordinal approximation, we computed a lower bound using the greedy number partitioning algorithm (Graham, 1966(Graham, , 1969)). This algorithm is known to attain a reasonable approximation of the maximin share both in the worst case (Deuermeyer, Friesen, & Langston, 1982;Csirik, Kellerer, & Woeginger, 1992) and in the average case (Frenk & Kan, 1986). Given an integer d, the algorithm initializes d empty bundles. It iterates over the goods in descending order of their value, and puts the next good in the bundle with the smallest total value so far (breaking ties arbitrarily). Once all goods are allocated, the sum of values in the bundles with the smallest values is a lower bound for the -out-of-d MMS. Taking instead the smallest value times (which approximates
• MMS 1-out-of-d ) yields nearly identical results. For the multiplicative approximation, we just use the proportional share v i (M )/n as an upper bound for agent i's 1-out-of-n MMS.
For various values of m, we chose m random integers to use as the good values. We performed three simulations, in which the values were distributed (a) uniformly at random in [1, 1000], (b) uniformly at random in [1000,2000], and (c) geometrically with mean value of 1000. We modified n between 4 and 20, and m between 4n and 80n. The results for all n were very similar. While our approximation for = 1 is generally worse than 3/4 of the MMS, our approximation for ≥ 2 is better already for m ≈ 20n, and it becomes better as m grows. Figure 3 illustrates these observations. 12 10. An accurate computation of the convergence rate of the MMS to 1/n is beyond the scope of the present paper. We refer the interested reader to Mertens (2001), who studies a closely-related problem: the probability distribution of the smallest difference between the highest-valued bundle and the lowestvalued bundle in an n-partition. 11. Using integer linear programming, we could compute the exact value of 1-out-of-4 MMS for m > 200 goods in reasonable time. However, we were not able to scale our computations for larger values of n. 12. Source code for the experiments is available at https://github.com/erelsgl/ordinal-maximin-share.
the goods are put into bags in decreasing order of their value. For each version we ran two sets of experiments: (i) one experiment where agents threshold values are computed individually, and (ii) one experiment where all agents' thresholds are a common fraction of their proportional share.
In each experiment, we generated 1,000 instances for each pair of n ∈ [3, 20] and m ∈ [n, 100]foot_5 where the valuations were uniformly distributed from [0, 1000] and then ordered.
For each agent, we utilize binary search to find the largest individual threshold where that agent can form at least n bundles in successful simulations, as explained in Section 5. To compare the bidirectional and unidirectional bag-filling approaches, we first compute the value that each agent received, as a fraction of his proportional share P rop i := v i (M )/n. We then plot the minimum ratio any agent received over all 1,000 instances, the average ratio all agents received over 1,000 instances, and the minimum of the average ratios of all agents per instance.
If the valuations were perfectly divisible (say as m → ∞), we would expect that the 1-of-(3n/2 + 1) MMS would equate to approximately v i (M ) 3n/2 ≈ 2/3 v i (M ) n = 2/3P rop i . Since proportionality implies MMS, it is an upper bound for MMS values, each agent's 1-of-(3n/2 + 1) MMS is at most 2/3P rop i .
Figure 4 and Figure 5 show that, while both the bidirectional and unidirectional algorithms exceed the 2/3 ratio on most instances, the bidirectional algorithm averages slightly higher (about 5%), with a higher minimum average. Note that the unidirectional bag-filling algorithm is not guaranteed to give every agent 1-of-(3n/2 + 1) MMS. the picking-sequence dominates the bundle allocated to i by the algorithm on the ordered instance (the picking-sequence implements the injection f ). Similarly, Lemma 5, ensuring the existence of a BBFS-fair allocation, holds for responsive preferences too, since the proof only requires containment of bundles. Therefore, the class of responsive preferences initially seems like a good candidate for generalizing our results. Unfortunately, we show below that, with responsive valuations, no meaningful ordinal approximation is possible, even for two agents. This indicates that the ordinal maximinshare approxiation may be too strong for handling non-additive valuations.
Proposition 1. For any integer d ≥ 1, there is an instance with two agents with responsive valuations, in which no allocation guarantees both agents their 1-out-of-d maximin-share.
Proof. We construct an instance with m = 2 d 2 -1 goods. They are ranked the same for both agents: v i (g 1 ) > . . . > v i (g m ) for i ∈ {1, 2}.
For each j ∈ [d 2 ], we denote by B j the set of bundles that contain a majority of the goods in {g 1 , . . . , g (2 j )-1 }. Note that B j ⊆ 2 M . For example:
• B 1 is the set of all bundles that contain g 1 ;
• B 2 is the set of all bundles that contain at least two goods from {g 1 , g 2 , g 3 };
• B 3 is the set of all bundles that contain at least four goods from {g 1 , . . . , g 7 };
• B d 2 is the set of all bundles that contain at least 2 d 2 -1 goods from M .
Let X, Y be some bundles such that X ∈ B j and Y ∈ 2 M \B j for some j ∈ [d 2 ]. The majority assumption implies that X cannot be dominated by Y : there cannot be an injection from a majority to a minority. Therefore, a responsive valuation may assign a larger value to X than to Y .
Before proceeding with the proof, we exemplify it for the special case d = 2. We define the valuations of two agents as follows.
• For agent 1, we set v 1 (X) = 1 for any X ∈ (B 1 ∩ B 2 ) ∪ (B 3 ∩ B 4 ), and smaller values for other bundles. Then MMS 1-out-of-d 1 = 1, since M can be partitioned into {g 1 , g 2 , g 3 } ∈ B 1 ∩ B 2 and {g 4 , . . . , g 7 , g 8 , . . . , g 15 } ∈ B 3 ∩ B 4 .
• For agent 2, we set v 2 (X) = 1 for any X ∈ (B 1 ∩ B 3 ) ∪ (B 2 ∩ B 4 ), and smaller values for other bundles. Then MMS 1-out-of-d 2 = 1, since M can be partitioned into {g 1 ; g 4 , . . . , g 7 } ∈ B 1 ∩ B 3 and {g 2 , g 3 ; g 8 , . . . , g 15 } ∈ B 2 ∩ B 4 .
Note that the agents' valuations are consistent with responsiveness. For example, consider a bundle Y ∈ (B 1 ∩B 2 )∪(B 3 ∩B 4 ). Then either Y ∈ B 1 ∪B 3 or Y ∈ B 1 ∪B 4 or Y ∈ B 2 ∪B 3 or Y ∈ B 2 ∪ B 4 . In any case, Y cannot dominate any bundle X ∈ (B 1 ∩ B 2 ) ∪ (B 3 ∩ B 4 ). So assigning to X a higher value than to Y is consistent with responsive valuations.
Suppose now that an allocation (A 1 , A 2 ) gives agent 1 a value of at least 1. This means that either A 1 ∈ B 1 ∩ B 2 or A 1 ∈ B 3 ∩ B 4 . If A 1 ∈ B 1 ∩ B 2 , then A 1 contains g 1 and a majority of the goods from {g 1 , g 2 , g 3 }. This means that A 2 cannot contain g 1 and cannot contain a majority of {g 1 , . . . , g 3 }. So A 2 ∈ B 1 and A 2 ∈ B 2 . This means that A 2 ∈ (B 1 ∩ B 3 ) ∪ (B 2 ∩ B 4 ), so the value of agent 2 is less than MMS 1-out-of-d 2 . Similarly, if A 1 ∈ B 3 ∩ B 4 , then A 2 ∈ B 3 and A 2 ∈ B 4 , so again the value of agent 2 is less than MMS 1-out-of-d 2 . We conclude that no allocation gives both agents their 1-out-of-d MMS. We now generalize this construction to any integer d.
• Let v 1 (X) = 1 for any bundle satisfying To compute the agents' MMS, define d 2 bundles as follows. For each j ∈ [d 2 ], let G j = {g 2 (j-1) , . . . , g (2 j )-1 }.
For example, G 1 = {g 1 }, G 2 = {g 2 , g 3 }, G 3 = {g 4 , . . . , g 7 }, and so on. Note that the G j are pairwise-disjoint, and for any j ∈ [d 2 ], G j ∈ B j since it contains the majority of goods in {g 1 , . . . , g (2 j )-1 }. Then:
• MMS 1-out-of-d We conclude that no allocation gives both agents their 1-out-of-d MMS. The proof holds for any positive integer d.
Remark 3. Babaioff et al. (2021) prove that responsive preferences are a subset of submodular preferences. Every submodular preference relation can be represented by a submodular valuation function. Therefore, the impossibility in Proposition 1 extends to submodular valuations too.
In general, ordinal and multiplicative approximations are incomparable from the theoretical standpointeach of them may be larger than the other in some instances (see Appendix A). Therefore, we compare them through simulations using synthetic data.
In Appendix D we complement our results with a non-existence result for the more general class of responsive preferences.
While we use the Lone Divider algorithm for allocating indivisible goods, it is a more general scheme that can also be used to divide chores or mixed items, divisible or indivisible. See Aigner-Horev and Segal-Halevi (2022) for details.
An envy-free matching in a bipartite graph (N ∪ Y, E) is a matching in which each unmatched agent in N is not adjacent to any matched element in Y . The bipartite graph generated by the Lone Divider algorithm always admits a nonempty envy-free matching, and a maximum-cardinality envy-free matching can be found in polynomial time(Aigner-Horev & Segal-Halevi, 2022).
Recall that the Lone Divider algorithm allocates bundles using an envy-free matching. This means that all bundles allocated before Alice's turn are unacceptable to Alice.
Observe that when m < 3n/2 + 1, the 1-of-(3n/2 + 1) MMS is 0 for all agents. Thus any allocation satisfies this property.