Maximin share

Procaccia and Wang[3] presented an algorithm that always finds an r_n-fraction MMS, where

${\displaystyle r_{n}:={\frac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}={\begin{cases}{\frac {2n}{3n-1}}&n~{\text{ odd}}\\{\frac {2n-2}{3n-4}}&n~{\text{ even}}\end{cases}}}$

where oddfloor(n) is the largest odd integer smaller or equal to n. In particular, r₃ = r₄ = 3/4, it decreases when n increases, and it always larger than 2/3. Their algorithm runs in time polynomial in m when n is constant, but its runtime might be exponential in n.

Amanatidis, Markakis, Nikzad and Saberi[11] presented several improved algorithms:

• A simple and fast 1/2-fraction MMS algorithm;
• A 2/3-fraction MMS algorithm that runs in polynomial time in both m and n;
• A 7/8-fraction MMS algorithm for 3 agents;

Barman and Krishnamurthy[14][15] presented:

• A simple and fast algorithm for 2/3-fraction MMS with additive valuations . Their algorithm is based on "ordering" the instance (i.e., reducing the instance to one in which all agents agree on the ranking of goods), and then running the envy-graph procedure starting at the most valuable good. They prove that the outcome is EFX and guarantees to each agent ${\displaystyle {\frac {2n}{3n-1}}}$ of his MMS, which is at least 2/3.
• A simple algorithm for 1/10-fraction MMS for the more challenging case of submodular valuations - based on round-robin item allocation.

Ghodsi, Hajiaghayi, Seddighin, Seddighin and Yami[16] presented:

• For additive valuations: a proof of existence for 3/4-fraction MMS-fairness.
• For n=4 additive agents: an algorithm for 4/5-fraction MMS-fairness.
• For submodular valuations: a polynomial-time algorithm for 1/3-fraction MMS-fairness, and an upper bound of 3/4-fraction.
• For XOS valuations: a polynomial-time algorithm for 1/8-fraction MMS-fairness, an existence proof for 1/5-fraction, and an upper bound of 1/2-fraction.
• For subadditive valuations: an existence proof for log(m)/10-fraction MMS-fairness, and an upper bound of 1/2-fraction.

Garg, McGlaughlin and Taki[17] presented a simple algorithm for 2/3-fraction MMS-fairness whose analysis is also simple.

Garg and Taki[18] presented:

• A simple algorithm for 3/4-fraction MMS, which does not need to know the MMS value, and thus runs in strongly polynomial time.
• A proof of existence of ${\displaystyle ({\frac {3}{4}}+{\frac {1}{12n}})}$-fraction MMS.

Akrami, Garg, Sharma and Taki[19] improve the analysis of the algorithm presented by Garg and Taki, simplifying the analysis and improving the existence guarantee to ${\displaystyle {\frac {3}{4}}+\min \left({\frac {1}{36}},{\frac {3}{16n-4}}\right)}$.

To date, it is not known what is the largest r such that an r-fraction MMS allocation always exists. It can be any number between ${\displaystyle 3/4}$ and ${\displaystyle 39/40}$.

Multiplicative approximation results for MMS

Valuations	Lower bound			Upper bound		Polynomial-time algorithm
	${\displaystyle n=3}$	${\displaystyle n=4}$	${\displaystyle n\geq 5}$	${\displaystyle n=3}$	${\displaystyle n\geq 4}$
Additive	${\displaystyle 11/12}$[20]	${\displaystyle 4/5}$[16]	${\displaystyle {\frac {3}{4}}+\min \left({\frac {1}{36}},{\frac {3}{16n-4}}\right)}$[19]	${\displaystyle 39/40}$[8]	${\displaystyle 1-{\frac {1}{n^{4}}}}$[8]	${\displaystyle {\frac {3}{4}}+{\frac {1}{12n}}-\epsilon }$[18]
Submodular	${\displaystyle 1/3}$[16]			${\displaystyle 3/4}$[16]		${\displaystyle 1/3}$[16]
XOS	${\displaystyle 1/5}$[16]			${\displaystyle 1/2}$[16]		${\displaystyle 1/8}$[16]
Subadditive	${\displaystyle 1/(10\lceil \log(m)\rceil )}$[16]			${\displaystyle 1/2}$[16]		–

Budish[2] showed that the Approximate Competitive Equilibrium from Equal Incomes always guarantees the 1-of-(${\displaystyle n+1}$) MMS, However, this allocation may have excess supply, and - more importantly - excess demand: the sum of the bundles allocated to all agents might be slightly larger than the set of all items. Such an error is reasonable in course allocation, since a small excess supply can be corrected by adding a small number of seats. But the classic fair division problem assumes that items may not be added.

Without excess supply and demand, the following approximations are known:

• A 1-out-of-(2n-2) MMS allocation of goods, and a 1-out-of(2n/3) MMS allocation of chores, using envy-free matching.[21]
• A 1-out-of-(3n/2) MMS allocation of goods,[22]which can be computed in polytime when n<6.
• A 1-out-of-(3n/2) MMS allocation of goods in polynomial time, and a L-out-of-([L+1/2]n) MMS allocation existence result.[15]
• A 1-out-of-(3n/4) MMS allocation of chores.[23]

To date, it is not known what is the smallest d such that a 1-out-of-d MMS allocation always exists. It can be any number between n+1 and 3n/2. The smallest open case is n=4.

Maximizing the product: Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang[24] showed that the max-Nash-welfare allocation (the allocation maximizing the product of utilities) is always ${\displaystyle {\frac {2}{1+{\sqrt {4n-3}}}}}$-fraction MMS fair, and it is tight.

Truthfulness: Amanatidis, Birmpas and Markakis[25] presented truthful mechanisms for approximate MMS-fair allocations (see also Strategic fair division):

• For n agents: an 1/O(m)-fraction MMS.
• For 2 agents: a 1/2-fraction MMS, and a proof that no truthful mechanism can attain more than 1/2.

Cardinality constraints: The items are partitioned into categories, and each agent can get at most k_h items from each category h. In other words, the bundles must be independent sets of a partition matroid.

• Barman and Biswas[26]^: 10 present an algorithm reducing the problem to a problem with no constraints but with submodular valuations, and then use the algorithm of [16] to attain 1/3-fraction MMS-fairness.
• Hummel and Hetland[27] present an improved polynomial-time algorithm for 1/2-fraction MMS-fairness. They adapt the standard techniques and reductions from the unconstrained setting to the setting with constraints, and then apply a variant of a bag-filling procedure.

Conflict graph: Hummel and Hetland[28] study another setting where there is a conflict graph between items (for example: items represent events, and an agent cannot attend two simultaneous events). They show that, if the degree of the conflict graph is d and it is in (2,n), then a 1/d-fraction MMS allocation can be found in polynomial time, and a 1/3-fraction MMS allocation always exists.

Connectivity: the items are located on a graph, and each part must be a connected subgraph.

• Bouveret, Cechlarova, Elkind, Igarashi and Peters[29] prove that, if the graph is acyclic, then an MMS-fair allocation always exists and can be found efficiently. In general graphs an MMS-fair allocation may not exist and may be NP-hard to find.
• Lonc and Truszczynski[30] focus on the case in which the graph is a cycle, and present an algorithm for approximately MMS-fair allocation.

If, for each agent i, all valuations are scaled by a factor ${\displaystyle k_{i}}$ (which can be different for different agents), then the MMS for each agent is scaled by the same factor; therefore, every MMS allocation in the original instance is an MMS allocation in the scaled instance. It is common to scale the valuations such that the MMS of every agent is exactly ${\displaystyle 1}$. After this scaling, the MMS approximation problems can be stated as:

• ${\displaystyle r}$-fraction MMS: the total value of ${\displaystyle O}$ is at least ${\displaystyle n}$; we need to give each of ${\displaystyle n}$ agents a bundle worth at least ${\displaystyle r}$.
• 1-of-d MMS: the total value of ${\displaystyle O}$ is at least ${\displaystyle d}$; we need to give each of ${\displaystyle n}$ agents a bundle worth at least ${\displaystyle 1}$.

The above scaling requires to compute the MMS of each agent, which is an NP-hard problem (multiway number partitioning). An alternative scaling, that can be done faster, is:[17]

• ${\displaystyle r}$-fraction MMS: the total value of ${\displaystyle O}$ is exactly ${\displaystyle n}$; the MMS is at most ${\displaystyle 1}$; we need to give each of ${\displaystyle n}$ agents a bundle worth at least ${\displaystyle r}$.
• 1-of-d MMS: the total value of ${\displaystyle O}$ is exactly ${\displaystyle d}$; the MMS is at most ${\displaystyle 1}$; we need to give each of ${\displaystyle n}$ agents a bundle worth at least ${\displaystyle 1}$.

If we remove one object ${\displaystyle o}$ from ${\displaystyle O}$. Then for each agent, the ${\displaystyle 1}$-out-of-(${\displaystyle n-1}$) MMS w.r.t. the remaining set ${\displaystyle O\setminus o}$ is at least his ${\displaystyle 1}$-out-of-${\displaystyle n}$ MMS w.r.t. the original set ${\displaystyle O}$. This is because, in the original MMS partition, ${\displaystyle n-1}$ parts remain intact.[12] Now, suppose we aim to give each agent a value of ${\displaystyle r}$. If some object ${\displaystyle o_{1}}$ is worth at least ${\displaystyle r}$ to at least one agent, then we can give ${\displaystyle o_{1}}$ to one such agent arbitrarily, and proceed to allocate the remaining objects to the remaining agents. Therefore, we can assume w.l.o.g. that:

• ${\displaystyle r}$-fraction MMS : the value of each object for all agents is less than ${\displaystyle r}$.
• ${\displaystyle 1}$-of-${\displaystyle d}$ MMS : the value of each object for all agents is less than ${\displaystyle 1}$.

This normalization works even with the fast scaling, and with arbitrary monotone valuations (even non-additive).[16]

Denote an object, that is valued by at most ${\displaystyle s}$ by all agents, as an "${\displaystyle s}$-small object". Suppose that all objects are ${\displaystyle s}$-small. Take an empty bag and fill it with object after object, until the bag is worth at least ${\displaystyle r}$ to at least one agent. Then, give the bag to one such agent arbitrarily. Since all objects are ${\displaystyle s}$-small, the remaining agents value the bag at most ${\displaystyle r+s}$; if this value is sufficiently small, then the remaining value is sufficiently large so that we can proceed recursively.[17] In particular, bag-filling gives as the following solutions:

• 1/2-fraction MMS : take ${\displaystyle s=r=1/2}$; note that by the previous normalization we can assume that all objects are ${\displaystyle 1/2}$-small. Initially, there are n agents and the total value is at least ${\displaystyle n}$ for them. After a bag is allocated, the remaining ${\displaystyle n-1}$ agents value the remaining objects at least ${\displaystyle n-(r+s)=n-1}$, so we can proceed recursively.[16]
• 1-of-(2n) MMS : take ${\displaystyle s=r=1}$; note that by the previous normalization we can assume that all objects are ${\displaystyle 1}$-small. Initially, there are ${\displaystyle n}$ agents and the total value is at least ${\displaystyle 2n}$ for them. After a bag is allocated, the remaining ${\displaystyle n-1}$ agents value the remaining objects at least ${\displaystyle 2n-(r+s)=2n-2=2(n-1)}$, so we can proceed recursively.

These bag-filling algorithms work even with the fast scaling, so they run in polynomial time - they do not need to know the exact MMS value.[17] In fact, both algorithms can be stated without mentioning the MMS at all:

• Every agent for whom each object is worth at most ${\displaystyle 1/(2n)}$ of the total value, receives at least ${\displaystyle 1/(2n)}$ of the total value.

Modified bag filling: The condition that all objects are ${\displaystyle s}$-small can be relaxed as follows.[17] Take some ${\displaystyle s<r}$. Denote an object that is not ${\displaystyle s}$-small (i.e., valued at least ${\displaystyle s}$ by at least one agent) as an "${\displaystyle s}$-large object". Suppose at most ${\displaystyle n}$ objects are ${\displaystyle s}$-large. Take one ${\displaystyle s}$-large object ${\displaystyle o_{1}}$, put it in a bag, and fill it with ${\displaystyle s}$-small objects until one agent indicates that it is worth for him at least ${\displaystyle r}$. There must be at least one such agent, since some agent ${\displaystyle i}$ values ${\displaystyle o_{1}}$ at some ${\displaystyle x>s}$. For this agent, there are at most ${\displaystyle n-1}$ remaining ${\displaystyle s}$-large objects. By the previous normalization, these objects are still ${\displaystyle r}$-small, so their total value for ${\displaystyle i}$ is at most ${\displaystyle r(n-1)}$, so the value of remaining ${\displaystyle s}$-small objects is at least ${\displaystyle n-r(n-1)-x=r(n-1)+r-x\geq r-x}$.

An instance is ordered if all agents have the same ordinal ranking on the objects, i.e, the objects can be numbered ${\displaystyle o_{1},\dots ,o_{m}}$ such that, for each agent ${\displaystyle i}$, ${\displaystyle v_{i}(o_{1})\geq \dots \geq v_{i}(o_{m})}$. Intuitively, ordered instances are hardest, since the conflict between agents is largest. Indeed, the negative instance of [3] is ordered - the order of the objects is determined by the matrix ${\displaystyle T}$, which is the same for all agents. This can also be proved formally. Suppose we have an algorithm that finds, for every ordered instance, an ${\displaystyle r}$-fraction MMS allocation. Now, we are given a general item-allocation instance ${\displaystyle P}$. We solve it in the following way.[12][14]

1. Construct an ordered instance ${\displaystyle \mathrm {ord} (P)}$ in the following way: for every agent i, define ${\displaystyle v_{i}(o_{j})}$ in ${\displaystyle \mathrm {ord} (P)}$ as the ${\displaystyle j}$-th highest value in the set of values of agent ${\displaystyle i}$ in ${\displaystyle P}$. This requires ${\displaystyle O(nm\lg m)}$ time.
2. Find an ${\displaystyle r}$-fraction MMS allocation ${\displaystyle \mathrm {ord} (A)}$ in ${\displaystyle \mathrm {ord} (P)}$.
3. Construct a picking sequence in which the agent who received ${\displaystyle o_{1}}$ in ${\displaystyle \mathrm {ord} (A)}$ picks first, the agent who received ${\displaystyle o_{2}}$ in ${\displaystyle \mathrm {ord} (A)}$ picks second, etc.
4. Let agents pick their best items according to the picking-sequence. Let ${\displaystyle A}$ be the resulting allocation. In ${\displaystyle A}$, each agent receives exactly the same number of items as in ${\displaystyle \mathrm {ord} (A)}$. Moreover, each agent who received ${\displaystyle o_{j}}$ in ${\displaystyle \mathrm {ord} (A)}$, receives one of his top ${\displaystyle j}$ items in ${\displaystyle A}$. Therefore, his value for each item he got in ${\displaystyle A}$ is at least as large as his value for the corresponding item in ${\displaystyle \mathrm {ord} (A)}$. Therefore, the value of every agent in ${\displaystyle A}$ is at least as high as in ${\displaystyle \mathrm {ord} (A)}$. Since the ordering does not change the MMS values, the new allocation ${\displaystyle A}$ is still ${\displaystyle r}$-fraction MMS.

So when looking for ${\displaystyle r}$-fraction MMS allocations, we can assume w.l.o.g. that:

• The ordinal ranking of the objects is the same for all agents.

Suppose we find two objects o₁ and o₂, that one agent i values at least r, while the other agents value at most 1. Then these two objects can be allocated to i. For the other agents, the 1-out-of-(n-1) MMS w.r.t. the remaining set is at least his 1-out-of-n MMS w.r.t. the original set O. This is because, in the original MMS partition, at least n-2 parts remain intact, while the two parts that are not intact can be combined to form a single part with a value of at least 1. This normalization works only with additive valuations.[16]^: Lem.3.2

Moreover, suppose that the instance is ordered, and suppose we remove from O the two objects o_n, o_n+1 (i.e., the n-th and (n+1)-th highest-valued items). Then for each agent, the 1-out-of-(n-1) MMS w.r.t. the remaining set is at least his 1-out-of-n MMS w.r.t. the original set O. This is because, by the pigeonhole principle, at least one MMS part of each agent must contain two or more objects from the set {o₁, ..., o_n+1}. These items can be used to replace the objects given away, which results in n-1 parts with a value of at least 1. This means that, if the objects o_n, o_n+1 have a value of at least the MMS for some agent i, we can give them to i and proceed to allocate the remaining objects to the remaining agents. Therefore, we can assume w.l.o.g. that:

• r-fraction MMS: the total value of o_n, o_n+1 for all agents is less than r . In particular, the value of o_n+1 and all objects after it in the ordering is less than r/2.
• 1-of-d MMS : the total value of od, o_d+1 for all agents is less than 1. In particular, the value of o_d+1 and all objects after it in the ordering is less than 1/2.

This normalization works even with the fast scaling. Combining it with modified bag-filling leads to the following simple algorithm for 2/3-fraction MMS.[17]

• As long as a single object is worth at least 2/3 to some agent, allocate it.
• Order the instance.
• As long as o_n, o_n+1 are worth at least 2/3 to some agent, allocate them.
• Finally, there are at most n objects with value at least 1/3; allocate them using modified bag-filling.

The guarantee of this algorithm can be stated even without mentioning MMS:

• Every agent, for whom o₁ is worth at most 2/(3n) of the total value and o_n + o_n+1 are worth together at most 2/(3n) of the total value, receives at least 2/(3n) of the total value.

Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin and Seddigin[39] introduce the Weighted Maximin Share (WMMS), defined by:

${\displaystyle \operatorname {WMMS} _{i}^{t}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {t_{i}}{t_{j}}}V(Z_{j})=~~~t_{i}\cdot \max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~{\frac {V(Z_{j})}{t_{j}}}}$

Intuitively, the optimal WMMS is attained by a partition in which the value of part j is proportional to the entitlement of agent j. For example, suppose all value functions are the sums, and the entitlement vector is t=(1/6, 11/24, 9/24). Then ${\displaystyle \operatorname {WMMS} _{1}^{t}(\{1,3,5,6,9\})=4}$ by the partition ({1,3},{5,6},{9}); it is optimal since the value of each part ${\displaystyle i}$ equals ${\displaystyle 24t_{i}}$. By the same partition, ${\displaystyle \operatorname {WMMS} _{2}^{t}=11}$ and ${\displaystyle \operatorname {WMMS} _{3}^{t}=9}$. When all n entitlements are equal, ${\displaystyle \operatorname {WMMS} _{i}^{t}\equiv \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}}$.

An allocation of C is called WMMS-fair for entitlement-vector t if the value of each agent i is at least ${\displaystyle \operatorname {WMMS} _{i}^{t}(C)}$. When all n agents have identical valuations, a WMMS-fair allocation always exists by definition. But with different valuations, the best possible multiplicative approximation is 1/n. The upper bound is proved by the following example with 2n-1 goods and n agents, where ε>0 is a very small constant:

All agents have an optimal WMMS partition: for the "small" agents (1, ..., n-1) it is the partition ({1}, ..., {n-1}, {n}) and for the "large" agent (n) it is ({n+1}, ..., {2n-1}, {1,...,n}). Therefore, ${\displaystyle \operatorname {WMMS} _{i}^{t}=t_{i}}$ for all agents i (for comparison, note that ${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=\epsilon =t_{i}}$ for the small agents, but ${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=[1-(n-1)\epsilon ]/n=t_{i}/n}$ for the large agent).

In any multiplicative approximation of WMMS, all agents have to get a positive value. This means that the small agents take at least n-1 of the items 1,...,n, so at most one such item remains for the large agent, and his value is approximately 1/n rather than almost 1.

A 1/n-fraction WMMS-fair allocation always exists and can be found by round-robin item allocation. In a restricted case, in which each agent i values each good by at most ${\displaystyle \operatorname {WMMS} _{i}^{t}}$, a 1/2-fraction WMMS-fair allocation exists and can be found by an algorithm similar to bag-filling: the valuations of each agent i are multiplied by ${\displaystyle t_{i}/\operatorname {WMMS} _{i}^{t}}$; and in each iteration, an item is given to an unsatisfied agent (an agent with value less than ${\displaystyle \operatorname {WMMS} _{i}^{t}/2}$) who values it the most. This algorithm allocates to each agent i at least ${\displaystyle \operatorname {WMMS} _{i}^{t}/2}$ and at most ${\displaystyle \operatorname {WMMS} _{i}^{t}}$. In practice, a WMMS-fair allocation almost always exists.[39]

Babaioff, Nisan and Talgam-Cohen[40] present a natural extension of the ordinal MMS approximation to agents with different entitlements. For any two integers ${\displaystyle l,d}$, set C and value function V, define

${\displaystyle \operatorname {MMS} _{V}^{l{\text{-out-of-}}d}(C):=~~~\max _{P\in \operatorname {Partitions} (C,d)}~~~\min _{Z\in \operatorname {Unions} (P,l)}~~~V(Z)}$

Here, the maximum is over all partitions of C into ${\displaystyle d}$ disjoint subsets, and the minimum is over all unions of ${\displaystyle l}$ parts. For example, ${\displaystyle \operatorname {MMS} _{V}^{2{\text{-out-of-}}3}(\{1,3,5,6,9\})=15}$ by the partition ({1,6},{3,5},{9}). Now, the Ordinal Maximin Share (OMMS) is defined by:

${\displaystyle \operatorname {OMMS} _{i}^{t}(C):=~~~\max _{l,d:~l/d\leq t_{i}}\operatorname {MMS} _{i}^{l{\text{-out-of-}}d}(C)}$

For example, if the entitlement of agent i is any real number at least as large as 2/3, then he is entitled to at least the 2-out-of-3 MMS of C. Note that, although there are infinitely many pairs ${\displaystyle l,d}$ satisfying with ${\displaystyle l/d\leq t_{i}}$, only finitely-many of them are not redundant (not implied by others), so it is possible to compute the OMMS in finite time.[41] An allocation Z₁,...,Z_n is called OMMS-fair for entitlement-vector w if the value of each agent i is at least ${\displaystyle \operatorname {OMMS} _{i}^{t}(C)}$.

The OMMS can be higher or lower than the WMMS, depending on the values:[41]

• As an example in which WMMS is higher, suppose C = {40, 60} and t = (0.4, 0.6). Then clearly WMMS₁=40 and WMMS₂=60, so the only WMMS-fair allocation gives the 40 to 1 and the 60 to 2. However, OMMS₁=0, since the fractions satisfying ${\displaystyle l/d\leq 0.4}$ are 1/3, 2/5, 3/7, etc., and in all cases, in any partition of C into ${\displaystyle d}$ subsets, there are at least ${\displaystyle l}$ empty subsets. Also, OMMS₂=40, since the fractions satisfying ${\displaystyle l/d\leq 0.6}$ are 1/2, 2/4, 3/5, 4/7, etc., and in all cases, in any partition of C into ${\displaystyle d}$ subsets, the ${\displaystyle l}$ least-valuable subsets do not contain the 60. Therefore, an OMMS-fair allocation might give the 40 to 2 and the 60 to 1, or give nothing to 1, both of which seem unfair.
• As an example in which OMMS is higher, suppose C = {40, 60} and t = (0.2, 0.2, 0.6). Then WMMS_i=0 for all i, since in any 3-partition of C, at least one bundle is empty. So the WMMS-fairness criterion is useless. Similarly, OMMS₁=OMMS₂=0. However, OMMS₃=40 by the pair ${\displaystyle l/d=1/2}$ and the partition ({40},{60}), so OMMS-fairness requires to give at least one item to agent 3, which seems fairer.

Babaioff, Ezra and Feige[42] introduced a third criterion for fairness, which they call AnyPrice Share (APS). They define it in two equivalent ways; one of them is clearly a strengthening of the maximin share. Instead of partitioning the items into d disjoint bundles, the agent is allowed to choose any collection of bundles, which may overlap. But, the agent must then assign a weight to each bundle such that the sum of weights is at least 1, and each item belongs to bundles whose total weight is at most the agent's entitlement. The APS is the value of the least valuable positive-weight bundle. Formally:

${\displaystyle \operatorname {APS} _{V}^{t}(C):=~~~\max _{P\in \operatorname {AllowedBundleSets} (C,t_{i})}~~~\min _{Z\in P}~~~V(Z)}$

where the maximum is over all sets of bundles such that, for some assignment of weights to the bundles, the total weight of all bundles is at least 1, and the total weight of each item is at most t_i. There is a polyomial-time algorithm that guarantees to each agent at least 3/5 of his APS.[42]

The APS is always at least as high as the OMMS: given an optimal l-out-of-d partition, with l/d ≤ t_i, one can assign a weight of 1/d to the union of parts 1,...,l, the union of parts 2,...,l+1, and so on (in a cyclic way), such that each part is included in exactly l unions. Therefore, each item belongs to bundles whose total weight is at most l/d, which is at most t_i. The agent is guaranteed the least valuable such bundle, which is at least the l-out-of-d MMS.

In some cases, the APS is strictly higher than the OMMS. Here are two examples:

• A simple example with different entitlements: let C = {2,1,1,1,0} and t_i = 2/5. The OMMS is at most 1 (it is sufficient to check l/d in {1/3, 2/5}). But the APS is 2, by the following weights: 0.4*{2}, 0.2*{1,1}, 0.2*{1,1}, 0.2*{1,1}. Note that the sum of weights is 1. The 2 appears in a single set with weight 0.4, while each of the 1's appears in two sets with weight 0.2, 0.2.
• A more complex example with equal entitlements: let C = {5, 5, 5, 7, 7, 7, 11, 17, 23, 23, 23, 31, 31, 31, 65} and t_i = 1/3. The OMMS equals the 1-out-of-3 MMS, and it is at most 96; this can be verified by checking all 3-partitions. The APS is 97, since it is possible to construct 6 bundles of 5 items each, with a total value of 97, such that each item appears in exactly two bundles. Then, one can assign a weight of 1/6 to each bundle.
  • This example also shows that an APS allocation might not exist even for 3 agents with identical valuations and equal entitlements. This is in contrast to the OMMS, which always exists with identical valuations and equal entitlements, and the WMMS, which always exists with identical valuations and arbitrary entitlements.

The APS can be higher or lower than the WMMS; the examples are the same as the ones used for OMMS vs WMMS:

• WMMS is higher: C = {40, 60} and t = (0.4, 0.6). Then WMMS₁=40 and WMMS₂=60. But APS₁=0, since each item must have a weight of at most 0.4, so the empty bundle must have a weight of at least 0.2. Also, APS₂=40, since each item must have a weight of at most 0.6, so {40} and the empty bundle must have a total weight of at least 0.4.
• APS is higher: C = {40, 60} and t = (0.2, 0.2, 0.6). Then WMMS_i=0 for all i. Similarly, APS₁=APS₂=0 as above. However, APS₃=40 e.g. by the weights 0.5*{40}, 0.5*{60}.