MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split (
Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations.
attaining this maximin value is called the "1-out-of-3 maximin-share" - it is the best subset of items that can be constructed by partitioning the original set into
An alternative interpretation is: the most preferred bundle the agent could guarantee as divider in divide and choose against adversarial opponents: the agent proposes her best allocation and leaves all the other ones to choose one share before taking the remaining one.
Note that the actual maximin-share might be higher than the lower bound, so the allocation found by Hill's method might not be MMS-fair.
He presented the A-CEEI mechanism, which attains an approximately MMS-fair allocation if it is allowed to add some goods.
In 2014, Procaccia and Wang[3] proved that an exact MMS-fair allocation among three or more agents may not exist.
Gourves, Monnot and Tlilane[5] extended the algorithm of Markakis and Psomas to gain a tighter fairness guarantee, that works for the more general problem of allocating a basis of a matroid.
Feige, Sapir and Tauber[8] improved the non-existence result, constructing an instance with
Kurokawa, Procaccia and Wang[9] showed that this holds true for two cases: Amanatidis, Markakis, Nikzad and Saberi[11] also prove that, in randomly-generated instances, MMS-fair allocations exist with high probability.
Bouveret and Lemaître[12] proved that MMS allocations exist in the following cases: The latter result was later improved to
Hummel[13] further showed that MMS allocations exist in the following cases: Amanatidis, Markakis, Nikzad and Saberi[11] showed that MMS allocations exist and can be found in polynomial time for the case of ternary valuations, in which each items are valued at 0, 1 or 2.
Procaccia and Wang[3] introduced a different kind of approximation - the multiplicative approximation to MMS: an allocation is r-fraction MMS-fair, for some fraction r in [0,1], if each agent's value is at least a fraction r of the value of his/her MMS, that is, for each agent i:
where oddfloor(n) is the largest odd integer smaller or equal to n. In particular, r3 = r4 = 3/4, it decreases when n increases, and it always larger than 2/3.
Budish[2] showed that the Approximate Competitive Equilibrium from Equal Incomes always guarantees the 1-of-(
Without excess supply and demand, the following approximations are known: To date, it is not known what is the smallest d such that a 1-out-of-d MMS allocation always exists.
Truthfulness: Amanatidis, Birmpas and Markakis[27] presented truthful mechanisms for approximate MMS-fair allocations (see also Strategic fair division): Cardinality constraints: The items are partitioned into categories, and each agent can get at most kh items from each category h. In other words, the bundles must be independent sets of a partition matroid.
Aziz, Rauchecker, Schryen and Walsh[33] extended the MMS notion to chores (items with negative utilities).
Note that, for chores, the multiplicative approximation factors are larger than 1 (since fewer chores have higher utility), and the ordinal approximation factors are smaller than n. They presented: Barman and Krishnamurthy[16] presented an algorithm attaining 4/3-fraction MMS (precisely,
Kulkarni, Mehta and Taki[35] study MMS-fair allocation with mixed valuations, i.e., when there are both goods and chores.
They prove that: Ebadian, Peters and Shah[36] prove that an MMS allocation always exists in bivalued instances, when each agent i partitions the chores to "easy" (valued at 1 for everyone) or "difficult" (valued at some integer pi > 1).
that: This normalization works even with the fast scaling, and with arbitrary monotone valuations (even non-additive).
[18] In fact, both algorithms can be stated without mentioning the MMS at all: Modified bag filling: The condition that all objects are
[18] The guarantee of this algorithm can be stated even without mentioning MMS: Several basic algorithms related to the MMS are: An allocation is called envy-free-except-c-items (EFc) for an agent i if, for every other agent j, there exists a set of at most c items that, if removed from j's bundle, then i does not envy the remainder.
With general additive valuations, 1/2-GMMS allocations exist and can be found in polynomial time.
Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin and Seddigin[42] introduce the Weighted Maximin Share (WMMS), defined by:
Intuitively, the optimal WMMS is attained by a partition in which the value of part j is proportional to the entitlement of agent j.
, 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
Babaioff, Nisan and Talgam-Cohen[43] present a natural extension of the ordinal MMS approximation to agents with different entitlements.
Babaioff, Ezra and Feige[45] introduced a third criterion for fairness, which they call AnyPrice Share (APS).