Maximin share (MMS) 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 n {\displaystyle n} parts and taking the part with the minimum value. An allocation of items among n {\displaystyle 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 is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split ( 1 / n {\displaystyle 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 {\displaystyle m} identical items have to be allocated fairly among n {\displaystyle n} people. Ideally, each person should receive m / n {\displaystyle m/n} items, but this may be impossible if m {\displaystyle m} is not divisible by n {\displaystyle n} , as the items are indivisible. A natural second-best fairness criterion is to round m / n {\displaystyle m/n} down to the nearest integer, and give each person at least ⌊ m / n ⌋ {\displaystyle \lfloor m/n\rfloor } items. Receiving less than ⌊ m / n ⌋ {\displaystyle \lfloor m/n\rfloor } 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 {\displaystyle n=3} and m = 5 {\displaystyle m=5} and the items' values are 1 , 3 , 5 , 6 , 9 {\displaystyle 1,3,5,6,9} , adding up to 24 {\displaystyle 24} . If the items were divisible, we would give each person a value of 24 / 3 = 8 {\displaystyle 24/3=8} (or, if they were divisible only to integer values as in the preceding paragraph, at least ⌊ 24 / 3 ⌋ = 8 {\displaystyle \lfloor 24/3\rfloor =8} ), but this is not possible. The largest value that can be guaranteed to all three agents is 7, by the partition { 1 , 6 } , { 3 , 5 } , { 9 } {\displaystyle \{1,6\},\{3,5\},\{9\}} . Informally, 7 {\displaystyle 7} is the total value divided by n {\displaystyle n} "rounded down to the nearest item". The set { 1 , 6 } {\displaystyle \{1,6\}} 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 {\displaystyle 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 {\displaystyle 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 {\displaystyle 1,3,5,6,9} ; George values them at 1 , 7 , 2 , 6 , 8 {\displaystyle 1,7,2,6,8} ; Dina values them at 1 , 1 , 1 , 4 , 17 {\displaystyle 1,1,1,4,17} . Now, each agent has a different MMS:
… excerpt ends here. Continue reading the full article.
