Maximin share


Maximin share is a criterion of fair item allocation. 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 parts and taking the part with the minimum value. An allocation of items among 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 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. 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 identical items have to be allocated fairly among people. Ideally, each person should receive items, but this may be impossible if is not divisible by, as the items are indivisible. A natural second-best fairness criterion is to round down to the nearest integer, and give each person at least items. Receiving less than 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 and and the items' values are, adding up to. If the items were divisible, we would give each person a value of , but this is not possible. The largest value that can be guaranteed to all three agents is 7, by the partition. Informally, is the total value divided by "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 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.
Different valuations. Suppose now that each agent assigns a different value to each item, for example:
  • Alice values them at ;
  • George values them at ;
  • Dina values them at.
Now, each agent has a different MMS:
  • Alice's MMS is still as above;
  • George's MMS is, by the partition ;
  • Dina's MMS is, by the partition.
Here, an allocation is MMS-fair if it gives Alice a value of at least, George a value of at least, and Dina a value of at least. 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- 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 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 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.

History

Theodore Hill studied the maximin-share in 1987. He presented a lower bound for the maximin-share of an agent as a function of the largest item value, and proved that there always exists an allocation in which each agent receives at least this lower bound. 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.
Budish studied MMS-fairness in 2011, in the context of course allocation. 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 proved that an exact MMS-fair allocation among three or more agents may not exist.

Formal definition

Let be a set representing the resource to be allocated. Let be any real-valued function on subsets of, representing their "value". The 1-out-of-n maximin-share of from is defined as:
Here, the maximum is over all partitions of into disjoint subsets, and the minimum is over all subsets in the partition. In the above examples, was a set of integers, and was the sum function, that is, was defined as the sum of integers in. For example, we showed that, where the maximizing partition is. In a typical fair allocation problem, there are some different agents with different value functions over the same resource. The 1-out-of- MMS value of agent is denoted by. An allocation is a vector of n pairwise-disjoint subsets of -- one subset per agent. An allocation is called MMS-fair, or simply an MMS allocation, if for every agent,
.
An allocation is called an MMS partition of agent if it holds that for all, i.e., the allocation is one of the partitions that maximizes the formula for 's MMS.

Lower bound

Hill proved that, if the value of every item for an agent is at most times the value of all items, then the 1-out-of-n MMS of that agent is at least, where is the following piecewise-linear function:
for all , for all.
Note that is a continuous and non-increasing function of, with and
Hill also proved that, for every n and, and for any n agents who value each item at most times the total value, there exists a partition in which each agent receives a value of at least. Moreover, this guarantee is tight: for every n and, there are cases in which it is impossible to guarantee more than to everyone, even when all valuations are identical.
Markakis and Psomas strengthened Hill's guarantee, and provided a polynomial-time algorithm for computing an allocation satisfying this stronger guarantee. They also showed that no truthful mechanism can obtain a 2/3-approximation to this guarantee, and present a truthful constant-factor approximation for a bounded number of goods. Gourves, Monnot and Tlilane 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.
Li, Moulin, Sun and Zhou have extended Hill's lower bound to bads, and presented a more accurate bound that depends also on the number of bads. They also presented a polynomial-time algorithm attaining this bound.

Existence of MMS-fair allocations

An MMS-fair allocation might not exist. Procaccia and Wang and Kurokawa constructed an instance with agents and items, in which no allocation guarantees to each agent the 1-out-of-3 MMS. Note that this does not contradict Hill's result, since the MMS of all agents may be strictly larger than Hill's lower bound. In their instance, there are objects, indexed by and. Each agent values each object by:
where are particular 3-by-4 matrices with values smaller than. They prove that every agent can partition the objects into subsets of objects each, such that the sum of values in each subset is 4,055,000, which is therefore the MMS of all agents. They prove that every MMS allocation must give exactly 4 particular objects to every agent, but such an allocation does not exist. Thus, every allocation gives at least one agent a value of at most 4,054,999. They generalized this instance and showed that for every there is such an instance with items.
Feige, Sapir and Tauber improved the non-existence result, constructing an instance with agents and items, in which there is no MMS allocation. In this instance each agent has an MMS of 40, but it is only possible to guarantee the worst off agent items with combined value of 39. They also show that for any, there is an instance with items for which an MMS allocation does not exist. If is even, they improve the bound to items. For these instances, the worst of agent can at most receive a share of their MMS.
Agent\Item123456789
1262319161210941
226222016139941
3252320151310941

While MMS allocations are not guaranteed to exist, it has been proved that in random instances, MMS allocations exist with high probability. Kurokawa, Procaccia and Wang showed that this holds true for two cases:
  • There are many items: for some constant that depends on the probability distribution. Then, by a previous result, an envy-free item allocation exists with high probability; such an allocation is always MMS.
  • There are few items: . For this case, they present an algorithm called matched draft. It is based on constructing a bipartite graph of agents vs. items, and finding in it a perfect matching. They prove that the probability that the matched draft succeeds goes to 1 as goes to infinity. If the matched draft succeeds, then the value of each agent is at least his MMS.
Amanatidis, Markakis, Nikzad and Saberi also prove that, in randomly-generated instances, MMS-fair allocations exist with high probability.
For many classes of instances, it has been proven that MMS allocations always exist. When all n agents have identical valuations, an MMS allocation always exists by definition. A slightly more general case in which an MMS allocation exists is when some agents have identical valuations. An MMS allocation can then be found by divide and choose: the identical agents partition the items into bundles each of which is at least as good as their MMS; the -th agent chooses the bundle with the highest value; and the identical agents take the remaining bundles. In particular, with two agents, an MMS allocation always exists.
Bouveret and Lemaître proved that MMS allocations exist in the following cases:
  • Binary valuations – each agent either likes an item or dislikes it.
  • Identical multisets – agents may value the items differently, but the multisets of the agents' values are the same.
  • Few items –.
The latter result was later improved to by Kurokawa, Procaccia and Wang and by Feige, Sapir and Tauber. Due to the negative example with three agents and nine items, this is the largest constant that exists, such that all instances with agents and items always have MMS allocations, no matter the value of. Hummel further showed that MMS allocations exist in the following cases:
  • There are items and agents.
  • There are items and agents.
  • There are items and agents.
Amanatidis, Markakis, Nikzad and Saberi 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.
Uriel Feige proved that MMS allocations always exists in bivalued instances, in which there are some two values a and b, and each agent values every item at either a or b.