Maximin share (MMS) is a criterion of
fair item allocation
Fair item allocation is a kind of a fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whol ...
. Given a set of items with different values, the ''1-out-of-n maximin-share'' is the maximum value that can be gained by partitioning the items into ''n'' parts and taking the part with the minimum value.
An allocation of items among ''n'' agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-''n'' maximin-share. MMS fairness was invented by Eric Budish
as a relaxation of the criterion of
proportionality - each agent gets a bundle that is at least as good as the equal split (1/''n'' of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different.
Motivation and examples
Identical items. Suppose first that ''m'' identical items have to be allocated fairly among ''n'' people. Ideally, each person should receive ''m''/''n'' items, but this may be impossible if ''m'' is not divisible by ''n'', as the items are indivisible. A natural second-best fairness criterion is to round ''m''/''n'' down to the nearest integer, and give each person at least floor(''m''/''n'') items. Receiving less than floor(''m''/''n'') items is "too unfair" - it is an unfairness not justified by the indivisibility of the items.
Different items. Suppose now that the items are different, and each item has a different value. For example, suppose ''n''=3 and ''m''=5 and the items' values are 1, 3, 5, 6, 9, adding up to 24. If the items were divisible, we would give each person a value of 24/3 = 8 (or, if they were divisible only to integer values as in the preceding paragraph, at least floor(24/3) = 8), but this is not possible. The largest value that can be guaranteed to all three agents is 7, by the partition ,,. Informally, 7 is the total value divided by ''n'' "rounded down to the nearest item".
The set 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 3 parts and taking the least valuable part. Therefore, in this example, an allocation is MMS-fair iff it gives each agent a value of at least 7.
Different valuations. Suppose now that each agent assigns a ''different'' value to each item, for example:
* Alice values them at 1,3,5,6,9;
* George values them at 1,7,2,6,8;
* Dina values them at 1,1,1,4,17.
Now, each agent has a different MMS:
* Alice's MMS is still as above;
* George's MMS is or or , by the partition ,, (all these bundles are equivalent for him);
* Dina's MMS is , by the partition ,,.
Here, an allocation is MMS-fair if it gives Alice a value of at least 7, George a value of at least 8, and Dina a value of at least 3. For example, giving George the first two items , Alice the next two items , and Dina the last item , is MMS-fair.
Interpretation. The 1-out-of-''n'' MMS of an agent can be interpreted as the maximal utility that an agent can hope to get from an allocation if all the other agents have the ''same'' preferences, when he always receives the worst share. It is the minimal utility that an agent could feel entitled to, based on the following argument: if all the other agents have the same preferences as me, there is at least one allocation that gives me this utility, and makes every other agent (weakly) better off; hence there is no reason to give me less.
An alternative interpretation is: the most preferred bundle the agent could guarantee as divider in
divide and choose
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
against adversarial opponents: the agent proposes her best allocation and leaves all the other ones to choose one share before taking the remaining one.
MMS-fairness can also be described as the result of the following negotiation process. A certain allocation is suggested. Each agent can object to it by suggesting an alternative partition of the items. However, in doing so he must let all other agents chose their share before he does. Hence, an agent would object to an allocation only if he can suggest a partition in which ''all'' bundles are better than his current bundle. An allocation is MMS-fair iff no agent objects to it, i.e., for every agent, in every partition there exists a bundle which is weakly worse than his current share.
Formal definition
Let ''C'' be a set representing the resource to be allocated. Let ''V'' be any real function on subsets of ''C'', representing their "value". The 1-out-of-''n'' maximin-share of ''V'' from ''C'' is defined as:
Here, the maximum is over all partitions of ''C'' into ''n'' disjoint subsets, and the minimum is over all ''n'' subsets in the partition. In the above examples, ''C'' was a set of integers, and ''V'' was the sum function, that is, V(Z) was defined as the sum of integers in ''Z''. For example, we showed that
, where the maximizing partition is (,,).
In a typical fair allocation problem, there are some ''n'' different agents with different value functions ''V''
1,...,''V
n'' over the same resource ''C''. The 1-out-of-''n'' MMS value of agent ''i'' is denoted by
. An ''allocation'' is a vector of ''n'' pairwise-disjoint subsets of ''C --'' one subset per agent. An allocation ''Z''
1,...,''Z
n'' is called ''MMS-fair'' if for every agent i,
.
Existence of MMS-fair allocations
When all ''n'' agents have identical valuations, an MMS-fair allocation always exists by definition.
A slightly more general case in which an MMS-fair allocation exists is when some ''n''-1 agents have identical valuations. An MMS-fair allocation can then be found by
divide and choose
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
: the ''n''-1 identical agents partition the items into ''n'' bundles each of which is at least as good as their MMS; the ''n''-th agent chooses a bundle with a highest value; and the identical agents take the remaining ''n''-1 bundles. In particular, with two agents, an MMS-fair allocation always exists.
Bouveret and Lemaître
performed extensive randomized simulations for more than 2 agents, and found that MMS-fair allocations exist in every trial. They proved that MMS allocations exist in the following cases:
* ''Binary valuations'' - each agent either likes an item (values it at 1) or dislikes it (values it at 0).
* ''Identical multisets'' - agents may value the items differently, but the multisets of the agents' values are the same.
* ''Few items'' - ''m'' ≤ ''n''+3.
Procaccia and Wang
and Kurokawa constructed an instance with n=''3'' agents and ''m''=12 items, in which no allocation guarantees to each agent the 1-out-of-3 MMS. In their instance, there are 12 objects, indexed by