- Source: Maximin share
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:
Alice's MMS is still
7
{\displaystyle 7}
as above;
George's MMS is
8
{\displaystyle 8}
, by the partition
{
1
,
7
}
,
{
2
,
6
}
,
{
8
}
{\displaystyle \{1,7\},\{2,6\},\{8\}}
(all these bundles are equivalent for him);
Dina's MMS is
3
{\displaystyle 3}
, by the partition
{
1
,
1
,
1
}
,
{
4
}
,
{
17
}
{\displaystyle \{1,1,1\},\{4\},\{17\}}
.
Here, an allocation is MMS-fair if it gives Alice a value of at least
7
{\displaystyle 7}
, George a value of at least
8
{\displaystyle 8}
, and Dina a value of at least
3
{\displaystyle 3}
. For example, giving George the first two items
{
1
,
7
}
{\displaystyle \{1,7\}}
, Alice the next two items
{
5
,
6
}
{\displaystyle \{5,6\}}
, and Dina the last item
{
17
}
{\displaystyle \{17\}}
, is MMS-fair.
Interpretation. The 1-out-of-
n
{\displaystyle 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 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
C
{\displaystyle C}
be a set representing the resource to be allocated. Let
v
{\displaystyle v}
be any real-valued function on subsets of
C
{\displaystyle C}
, representing their "value". The 1-out-of-n maximin-share of
v
{\displaystyle v}
from
C
{\displaystyle C}
is defined as:
MMS
v
1
-out-of-
n
(
C
)
:=
max
(
Z
1
,
…
,
Z
n
)
∈
Partitions
(
C
,
n
)
min
j
∈
[
n
]
v
(
Z
j
)
{\displaystyle \operatorname {MMS} _{v}^{1{\text{-out-of-}}n}(C):=~~~\max _{(Z_{1},\ldots ,Z_{n})\in \operatorname {Partitions} (C,n)}~~~\min _{j\in [n]}~~~v(Z_{j})}
Here, the maximum is over all partitions of
C
{\displaystyle C}
into
n
{\displaystyle n}
disjoint subsets, and the minimum is over all
n
{\displaystyle n}
subsets in the partition. In the above examples,
C
{\displaystyle C}
was a set of integers, and
v
{\displaystyle v}
was the sum function, that is,
v
(
Z
)
{\displaystyle v(Z)}
was defined as the sum of integers in
Z
{\displaystyle Z}
. For example, we showed that
MMS
v
1
-out-of-
3
(
{
1
,
3
,
5
,
6
,
9
}
)
:=
7
{\displaystyle \operatorname {MMS} _{v}^{1{\text{-out-of-}}3}(\{1,3,5,6,9\}):=7}
, where the maximizing partition is
{
1
,
6
}
,
{
3
,
5
}
,
{
9
}
{\displaystyle \{1,6\},\{3,5\},\{9\}}
. In a typical fair allocation problem, there are some
n
{\displaystyle n}
different agents with different value functions
v
1
,
…
,
v
n
{\displaystyle v_{1},\dots ,v_{n}}
over the same resource
C
{\displaystyle C}
. The 1-out-of-
n
{\displaystyle n}
MMS value of agent
i
{\displaystyle i}
is denoted by
MMS
i
1
-out-of-
n
(
C
)
:=
MMS
v
i
1
-out-of-
n
(
C
)
{\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C):=\operatorname {MMS} _{v_{i}}^{1{\text{-out-of-}}n}(C)}
. An allocation is a vector of n pairwise-disjoint subsets of
C
{\displaystyle C}
-- one subset per agent. An allocation
Z
1
,
…
,
Z
n
{\displaystyle Z_{1},\dots ,Z_{n}}
is called MMS-fair, or simply an MMS allocation, if for every agent
i
{\displaystyle i}
,
v
i
(
Z
i
)
≥
MMS
i
1
-out-of-
n
(
C
)
{\displaystyle v_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}
.An allocation is called an MMS partition of agent
i
{\displaystyle i}
if it holds that
v
i
(
Z
j
)
≥
MMS
i
1
-out-of-
n
(
C
)
{\displaystyle v_{i}(Z_{j})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}
for all
j
{\displaystyle j}
, i.e., the allocation is one of the partitions that maximizes the formula for
i
{\displaystyle i}
's MMS.
Lower bound
Hill proved that, if the value of every item for an agent is at most
α
{\displaystyle \alpha }
times the value of all items, then the 1-out-of-n MMS of that agent is at least
V
n
(
α
)
{\displaystyle V_{n}(\alpha )}
, where
V
n
(
α
)
{\displaystyle V_{n}(\alpha )}
is the following piecewise-linear function:
V
n
(
α
)
=
1
−
k
⋅
(
n
−
1
)
⋅
α
{\displaystyle V_{n}(\alpha )=1-k\cdot (n-1)\cdot \alpha }
for all
α
∈
[
1
k
(
n
−
1
/
(
k
+
1
)
)
,
1
k
(
n
−
1
/
k
)
]
{\displaystyle \alpha \in \left[{\frac {1}{k(n-1/(k+1))}},{\frac {1}{k(n-1/k)}}\right]}
, for all
k
≥
1
{\displaystyle k\geq 1}
.Note that
V
n
(
α
)
{\displaystyle V_{n}(\alpha )}
is a continuous and non-increasing function of
α
{\displaystyle \alpha }
, with
V
n
(
0
)
=
1
/
n
{\displaystyle V_{n}(0)=1/n}
and
V
n
(
1
)
=
0
{\displaystyle V_{n}(1)=0}
(see the paper for a plot of
V
2
(
α
)
{\displaystyle V_{2}(\alpha )}
and
V
3
(
α
)
{\displaystyle V_{3}(\alpha )}
)
Hill also proved that, for every n and
α
{\displaystyle \alpha }
, and for any n agents who value each item at most
α
{\displaystyle \alpha }
times the total value, there exists a partition in which each agent receives a value of at least
V
n
(
α
)
{\displaystyle V_{n}(\alpha )}
. Moreover, this guarantee is tight: for every n and
α
{\displaystyle \alpha }
, there are cases in which it is impossible to guarantee more than
V
n
(
α
)
{\displaystyle V_{n}(\alpha )}
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
n
=
3
{\displaystyle n=3}
agents and
m
=
12
{\displaystyle m=12}
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
V
n
(
α
)
{\displaystyle V_{n}(\alpha )}
. In their instance, there are
12
{\displaystyle 12}
objects, indexed by
i
∈
[
3
]
{\displaystyle i\in [3]}
and
j
∈
[
4
]
{\displaystyle j\in [4]}
. Each agent
k
{\displaystyle k}
values each object
(
i
,
j
)
{\displaystyle (i,j)}
by:
v
k
(
i
,
j
)
=
1
,
000
,
000
+
1
,
000
⋅
T
i
,
j
+
E
i
,
j
(
k
)
{\displaystyle v_{k}(i,j)=1,000,000+1,000\cdot T_{i,j}+E_{i,j}^{(k)}}
where
T
,
E
(
1
)
,
E
(
2
)
,
E
(
3
)
{\displaystyle T,E^{(1)},E^{(2)},E^{(3)}}
are particular 3-by-4 matrices with values smaller than
100
{\displaystyle 100}
. They prove that every agent can partition the objects into
3
{\displaystyle 3}
subsets of
4
{\displaystyle 4}
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
n
≥
3
{\displaystyle n\geq 3}
there is such an instance with
3
n
+
4
{\displaystyle 3n+4}
items.
Feige, Sapir and Tauber improved the non-existence result, constructing an instance with
n
=
3
{\displaystyle n=3}
agents and
m
=
9
{\displaystyle m=9}
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
n
≥
3
{\displaystyle n\geq 3}
, there is an instance with
3
n
+
3
{\displaystyle 3n+3}
items for which an MMS allocation does not exist. If
n
{\displaystyle n}
is even, they improve the bound to
3
n
+
1
{\displaystyle 3n+1}
items. For these instances, the worst of agent can at most receive a
1
−
1
/
n
4
{\displaystyle 1-1/n^{4}}
share of their MMS.
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:
m
≥
α
⋅
n
ln
n
{\displaystyle m\geq \alpha \cdot n\ln {n}}
for some constant
α
{\displaystyle \alpha }
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:
m
<
n
8
/
7
{\displaystyle m
[note that this case partially overlaps the previous case]. 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 (1) the probability that the matched draft succeeds goes to 1 as
n
{\displaystyle n}
goes to infinity. (2) 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 (all agents have the same MMS partitions). A slightly more general case in which an MMS allocation exists is when some
n
−
1
{\displaystyle n-1}
agents have identical valuations. An MMS allocation can then be found by divide and choose: the
n
−
1
{\displaystyle n-1}
identical agents partition the items into
n
{\displaystyle n}
bundles each of which is at least as good as their MMS; the
n
{\displaystyle n}
-th agent chooses the bundle with the highest value; and the identical agents take the remaining
n
−
1
{\displaystyle n-1}
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 (values it at
1
{\displaystyle 1}
) or dislikes it (values it at
0
{\displaystyle 0}
).
Identical multisets – agents may value the items differently, but the multisets of the agents' values are the same.
Few items –
m
≤
n
+
3
{\displaystyle m\leq n+3}
.
The latter result was later improved to
m
≤
n
+
4
{\displaystyle m\leq n+4}
by Kurokawa, Procaccia and Wang and
m
≤
n
+
5
{\displaystyle m\leq n+5}
by Feige, Sapir and Tauber. Due to the negative example with three agents and nine items, this is the largest constant
c
{\displaystyle c}
that exists, such that all instances with
n
{\displaystyle n}
agents and
m
≤
n
+
c
{\displaystyle m\leq n+c}
items always have MMS allocations, no matter the value of
n
{\displaystyle n}
. Hummel further showed that MMS allocations exist in the following cases:
There are
m
≤
n
+
6
{\displaystyle m\leq n+6}
items and
n
≠
3
{\displaystyle n\neq 3}
agents.
There are
m
≤
n
+
7
{\displaystyle m\leq n+7}
items and
n
≥
8
{\displaystyle n\geq 8}
agents.
There are
m
≤
n
+
c
{\displaystyle m\leq n+c}
items and
n
≥
⌊
0.6597
c
(
c
!
)
⌋
{\displaystyle n\geq \lfloor 0.6597c(c!)\rfloor }
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.
Approximations
Budish introduced an approximation to the 1-of-n MMS—the 1-of-(
n
+
1
{\displaystyle n+1}
) MMS - each agent receives at least as much as he could get by partitioning into n+1 bundles and getting the worst one. In general, for any d > n, one can consider the 1-of-d MMS as an approximation to the 1-of-n MMS, and look for an allocation in which, for each agent i:
V
i
(
Z
i
)
≥
MMS
i
1
-out-of-
d
(
C
)
{\displaystyle V_{i}(Z_{i})\geq \operatorname {MMS} _{i}^{1{\text{-out-of-}}d}(C)}
Note that the value of the 1-of-d MMS is a weakly decreasing function of d. This is called an ordinal approximation, since it depends only on the ranking of the bundles, and not on their precise values.
Procaccia and Wang 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:
V
i
(
Z
i
)
≥
r
⋅
MMS
i
1
-out-of-
n
(
C
)
{\displaystyle V_{i}(Z_{i})\geq r\cdot \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C)}
Suppose one can choose between two algorithms: the first guarantees a multiplicative approximation (e.g. 3/4-fraction MMS), while the second guarantees an ordinal approximation (e.g. 1-out-of-(3n/2) MMS). Which of the two guarantees is higher? The answer depends on the values.
The multiplicative approximation is higher, for example, when there are n identical goods with a value of 1. Then, the 1-of-
d
{\displaystyle d}
MMS is 0 for any d>n, but the 1-of-
n
{\displaystyle n}
MMS is 1, so any positive multiplicative approximation of it is better.
The ordinal approximation is higher, for example, when there are d identical goods with a value of 1, for some d in {n+1,...,2n-1}. Then, the 1-of-d MMS is 1, and the 1-of-
n
{\displaystyle n}
MMS is 1 too, so any r-multiplicative approximation of it with r<1 is worse.
In general, for any integer k, the 1-of-n MMS as at least k times the 1-of-nk MMS: take an optimal 1-of-nk MMS partition, and group the bundles into n super-bundles, each of which contains k original bundles. Each of these super-bundles is worth at least k times the smallest original bundle. Therefore, a 1/k-multiplicative approximation is at least as large as a 1-of-nk ordinal approximation, but may be smaller than 1-of-(nk-1) ordinal approximation, as in the above example. In particular, any r-multiplicative approximation for r ≥ 1/2 is at least as good as 1-of-(2n) ordinal approximation, but might be worse than 1-of-(2n-1) ordinal approximation.
MMS-fair allocation of goods
= Multiplicative approximations
=Procaccia and Wang presented an algorithm that always finds an rn-fraction MMS, where
r
n
:=
2
⋅
oddfloor
(
n
)
3
⋅
oddfloor
(
n
)
−
1
=
{
2
n
3
n
−
1
n
odd
2
n
−
2
3
n
−
4
n
even
{\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, r3 = r4 = 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 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 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. Their algorithm can be seen as an adaptation of the Longest-processing-time-first scheduling algorithm for agents with different valuations. They prove that the outcome is EFX and guarantees to each agent
2
n
3
n
−
1
{\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 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 presented a simple algorithm for 2/3-fraction MMS-fairness whose analysis is also simple.
Garg and Taki 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
(
3
4
+
1
12
n
)
{\displaystyle ({\frac {3}{4}}+{\frac {1}{12n}})}
-fraction MMS.
Akrami, Garg, Sharma and Taki improve the analysis of the algorithm presented by Garg and Taki, simplifying the analysis and improving the existence guarantee to
3
4
+
min
(
1
36
,
3
16
n
−
4
)
{\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
3
/
4
{\displaystyle 3/4}
and
39
/
40
{\displaystyle 39/40}
.
= Ordinal approximations
=Budish showed that the Approximate Competitive Equilibrium from Equal Incomes always guarantees the 1-of-(
n
+
1
{\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.
A 1-out-of-(3n/2) MMS allocation of goods,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.
A 1-out-of-(3n/4) MMS allocation of chores.
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.
= Additional constraints
=Maximizing the product: Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang showed that the max-Nash-welfare allocation (the allocation maximizing the product of utilities) is always
2
1
+
4
n
−
3
{\displaystyle {\frac {2}{1+{\sqrt {4n-3}}}}}
-fraction MMS fair, and it is tight.
Truthfulness: Amanatidis, Birmpas and Markakis 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 kh items from each category h. In other words, the bundles must be independent sets of a partition matroid.
Barman and Biswas: 10 present an algorithm reducing the problem to a problem with no constraints but with submodular valuations, and then use the algorithm of to attain 1/3-fraction MMS-fairness.
Hummel and Hetland 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 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 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 focus on the case in which the graph is a cycle, and present an algorithm for approximately MMS-fair allocation.
MMS-fair allocation of chores
Aziz, Rauchecker, Schryen and Walsh 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:
A proof that an MMS allocation may not exist for chores;
A 2-fraction MMS algorithm for chores;
Algorithms for finding the optimal MMS approximation of a given instance, based on algorithms for multiway number partitioning.
Barman and Krishnamurthy presented an algorithm attaining 4/3-fraction MMS (precisely,
4
n
−
1
3
n
{\displaystyle {\frac {4n-1}{3n}}}
). The algorithm can be seen as a generalization of the LPT algorithm for identical-machines scheduling.
Huang and Lu prove that a 11/9-fraction MMS-fair allocation for chores always exists, and a 5/4-fraction MMS allocation can be found in polynomial time. Their algorithm can be seen as a generalization of the Multifit algorithm for identical-machines scheduling.
Kulkarni, Mehta and Taki study MMS-fair allocation with mixed valuations, i.e., when there are both goods and chores. They prove that:
No multiplicative approximation is possible. They extend the example of Procaccia and Wang by adding three chores with a value of -4,054,999.75. The 1-out-of-3 MMS of each agent is 0.25 (each MMS bundle contains four goods with a sum of 4,055,000, and one chore). However, every allocation of the goods gives at least one agent, a value of at most 4,054,999 from the goods. We must give one chore to each agent; therefore, at least one agent has a negative value.
They also present conditions under which computing an α-MMS and Pareto-optimal allocation, for the best possible α in a specific instance, can be done in polynomial time.
Ebadian, Peters and Shah 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).
Techniques and algorithms
Various normalizations can be applied to the original problem without changing the solution. Below, O is the set of all objects.
= Scaling
=If, for each agent i, all valuations are scaled by a factor
k
i
{\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
1
{\displaystyle 1}
. After this scaling, the MMS approximation problems can be stated as:
r
{\displaystyle r}
-fraction MMS: the total value of
O
{\displaystyle O}
is at least
n
{\displaystyle n}
; we need to give each of
n
{\displaystyle n}
agents a bundle worth at least
r
{\displaystyle r}
.
1-of-d MMS: the total value of
O
{\displaystyle O}
is at least
d
{\displaystyle d}
; we need to give each of
n
{\displaystyle n}
agents a bundle worth at least
1
{\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:
r
{\displaystyle r}
-fraction MMS: the total value of
O
{\displaystyle O}
is exactly
n
{\displaystyle n}
; the MMS is at most
1
{\displaystyle 1}
; we need to give each of
n
{\displaystyle n}
agents a bundle worth at least
r
{\displaystyle r}
.
1-of-d MMS: the total value of
O
{\displaystyle O}
is exactly
d
{\displaystyle d}
; the MMS is at most
1
{\displaystyle 1}
; we need to give each of
n
{\displaystyle n}
agents a bundle worth at least
1
{\displaystyle 1}
.
= Allocating one object
=If we remove one object
o
{\displaystyle o}
from
O
{\displaystyle O}
. Then for each agent, the
1
{\displaystyle 1}
-out-of-(
n
−
1
{\displaystyle n-1}
) MMS w.r.t. the remaining set
O
∖
o
{\displaystyle O\setminus o}
is at least his
1
{\displaystyle 1}
-out-of-
n
{\displaystyle n}
MMS w.r.t. the original set
O
{\displaystyle O}
. This is because, in the original MMS partition,
n
−
1
{\displaystyle n-1}
parts remain intact. Now, suppose we aim to give each agent a value of
r
{\displaystyle r}
. If some object
o
1
{\displaystyle o_{1}}
is worth at least
r
{\displaystyle r}
to at least one agent, then we can give
o
1
{\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:
r
{\displaystyle r}
-fraction MMS : the value of each object for all agents is less than
r
{\displaystyle r}
.
1
{\displaystyle 1}
-of-
d
{\displaystyle d}
MMS : the value of each object for all agents is less than
1
{\displaystyle 1}
.
This normalization works even with the fast scaling, and with arbitrary monotone valuations (even non-additive).
= Bag filling
=Denote an object, that is valued by at most
s
{\displaystyle s}
by all agents, as an "
s
{\displaystyle s}
-small object". Suppose that all objects are
s
{\displaystyle s}
-small. Take an empty bag and fill it with object after object, until the bag is worth at least
r
{\displaystyle r}
to at least one agent. Then, give the bag to one such agent arbitrarily. Since all objects are
s
{\displaystyle s}
-small, the remaining agents value the bag at most
r
+
s
{\displaystyle r+s}
; if this value is sufficiently small, then the remaining value is sufficiently large so that we can proceed recursively. In particular, bag-filling gives as the following solutions:
1/2-fraction MMS : take
s
=
r
=
1
/
2
{\displaystyle s=r=1/2}
; note that by the previous normalization we can assume that all objects are
1
/
2
{\displaystyle 1/2}
-small. Initially, there are n agents and the total value is at least
n
{\displaystyle n}
for them. After a bag is allocated, the remaining
n
−
1
{\displaystyle n-1}
agents value the remaining objects at least
n
−
(
r
+
s
)
=
n
−
1
{\displaystyle n-(r+s)=n-1}
, so we can proceed recursively.
1-of-(2n) MMS : take
s
=
r
=
1
{\displaystyle s=r=1}
; note that by the previous normalization we can assume that all objects are
1
{\displaystyle 1}
-small. Initially, there are
n
{\displaystyle n}
agents and the total value is at least
2
n
{\displaystyle 2n}
for them. After a bag is allocated, the remaining
n
−
1
{\displaystyle n-1}
agents value the remaining objects at least
2
n
−
(
r
+
s
)
=
2
n
−
2
=
2
(
n
−
1
)
{\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. In fact, both algorithms can be stated without mentioning the MMS at all:
Every agent for whom each object is worth at most
1
/
(
2
n
)
{\displaystyle 1/(2n)}
of the total value, receives at least
1
/
(
2
n
)
{\displaystyle 1/(2n)}
of the total value.
Modified bag filling: The condition that all objects are
s
{\displaystyle s}
-small can be relaxed as follows. Take some
s
<
r
{\displaystyle s
. Denote an object that is not
s
{\displaystyle s}
-small (i.e., valued at least
s
{\displaystyle s}
by at least one agent) as an "
s
{\displaystyle s}
-large object". Suppose at most
n
{\displaystyle n}
objects are
s
{\displaystyle s}
-large. Take one
s
{\displaystyle s}
-large object
o
1
{\displaystyle o_{1}}
, put it in a bag, and fill it with
s
{\displaystyle s}
-small objects until one agent indicates that it is worth for him at least
r
{\displaystyle r}
. There must be at least one such agent, since some agent
i
{\displaystyle i}
values
o
1
{\displaystyle o_{1}}
at some
x
>
s
{\displaystyle x>s}
. For this agent, there are at most
n
−
1
{\displaystyle n-1}
remaining
s
{\displaystyle s}
-large objects. By the previous normalization, these objects are still
r
{\displaystyle r}
-small, so their total value for
i
{\displaystyle i}
is at most
r
(
n
−
1
)
{\displaystyle r(n-1)}
, so the value of remaining
s
{\displaystyle s}
-small objects is at least
n
−
r
(
n
−
1
)
−
x
=
r
(
n
−
1
)
+
r
−
x
≥
r
−
x
{\displaystyle n-r(n-1)-x=r(n-1)+r-x\geq r-x}
.
= Ordering
=An instance is ordered if all agents have the same ordinal ranking on the objects, i.e, the objects can be numbered
o
1
,
…
,
o
m
{\displaystyle o_{1},\dots ,o_{m}}
such that, for each agent
i
{\displaystyle i}
,
v
i
(
o
1
)
≥
⋯
≥
v
i
(
o
m
)
{\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 is ordered - the order of the objects is determined by the matrix
T
{\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
r
{\displaystyle r}
-fraction MMS allocation. Now, we are given a general item-allocation instance
P
{\displaystyle P}
. We solve it in the following way.
Construct an ordered instance
o
r
d
(
P
)
{\displaystyle \mathrm {ord} (P)}
in the following way: for every agent i, define
v
i
(
o
j
)
{\displaystyle v_{i}(o_{j})}
in
o
r
d
(
P
)
{\displaystyle \mathrm {ord} (P)}
as the
j
{\displaystyle j}
-th highest value in the set of values of agent
i
{\displaystyle i}
in
P
{\displaystyle P}
. This requires
O
(
n
m
lg
m
)
{\displaystyle O(nm\lg m)}
time.
Find an
r
{\displaystyle r}
-fraction MMS allocation
o
r
d
(
A
)
{\displaystyle \mathrm {ord} (A)}
in
o
r
d
(
P
)
{\displaystyle \mathrm {ord} (P)}
.
Construct a picking sequence in which the agent who received
o
1
{\displaystyle o_{1}}
in
o
r
d
(
A
)
{\displaystyle \mathrm {ord} (A)}
picks first, the agent who received
o
2
{\displaystyle o_{2}}
in
o
r
d
(
A
)
{\displaystyle \mathrm {ord} (A)}
picks second, etc.
Let agents pick their best items according to the picking-sequence. Let
A
{\displaystyle A}
be the resulting allocation. In
A
{\displaystyle A}
, each agent receives exactly the same number of items as in
o
r
d
(
A
)
{\displaystyle \mathrm {ord} (A)}
. Moreover, each agent who received
o
j
{\displaystyle o_{j}}
in
o
r
d
(
A
)
{\displaystyle \mathrm {ord} (A)}
, receives one of his top
j
{\displaystyle j}
items in
A
{\displaystyle A}
. Therefore, his value for each item he got in
A
{\displaystyle A}
is at least as large as his value for the corresponding item in
o
r
d
(
A
)
{\displaystyle \mathrm {ord} (A)}
. Therefore, the value of every agent in
A
{\displaystyle A}
is at least as high as in
o
r
d
(
A
)
{\displaystyle \mathrm {ord} (A)}
. Since the ordering does not change the MMS values, the new allocation
A
{\displaystyle A}
is still
r
{\displaystyle r}
-fraction MMS.
So when looking for
r
{\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.
= Allocating two objects
=Suppose we find two objects o1 and o2, 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.: Lem.3.2
Moreover, suppose that the instance is ordered, and suppose we remove from O the two objects on, on+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 {o1, ..., on+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 on, on+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 on, on+1 for all agents is less than r . In particular, the value of on+1 and all objects after it in the ordering is less than r/2.
1-of-d MMS : the total value of od, od+1 for all agents is less than 1. In particular, the value of od+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.
As long as a single object is worth at least 2/3 to some agent, allocate it.
Order the instance.
As long as on, on+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 o1 is worth at most 2/(3n) of the total value and on + on+1 are worth together at most 2/(3n) of the total value, receives at least 2/(3n) of the total value.
Algorithmic problems
Several basic algorithms related to the MMS are:
Computing the 1-of-n MMS of a given agent. This is an NP-hard optimization problem, but it has several approximation algorithms; see Multiway number partitioning and Identical-machines scheduling.
Deciding whether a given allocation is MMS-fair is co-NP complete for agents with additive valuations (it is in co-NP, since it is possible to prove in polynomial time that a given allocation is not MMS-fair, given the MMS partition of one of the agents, which shows that the agent's MMS value is larger than his value in the given allocation).
Deciding whether a given instance admits any MMS allocation, given the MMS values of all agents. It is in NP since it can be verified in polynomial time given the allocation; its exact runtime complexity is unknown.
Therefore, deciding whether a given instance admits any MMS allocation is in
N
P
N
P
{\displaystyle NP^{NP}}
, i.e., it can be solved in nondeterministic-polynomial time using an oracle to an NP problem (the oracle is needed to calculate the MMS of an agent). However, the exact computational complexity of this problem is still unknown: it may be level 2 or 1 or even 0 of the polynomial hierarchy.
The decision problem of checking if there exists a minimax share allocation is NP-hard. Both problems can be approximated by a PTAS, assuming that the number of agents is fixed. When agents' valuations are binary, or additive and based on Borda score, maximin share allocations can always be found efficiently. When their valuations are nonadditive, there are instances in which an r-fraction MMS allocation does not exist for any positive r. However, for a class of symmetric submodular utilities, there exists a tight 1/2-fraction MMS allocation, and it can be approximated to within a factor of 1/4.
Relation to other fairness criteria
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. An EF0 allocation is simply called envy-free. EF1 allocations can be found, for example, by round-robin item allocation or by the envy-graph procedure.
An allocation is called proportional-except-c-items (PROP*c) for an agent i if there exists a set of at most c items outside i's bundle that, if removed from the set of all items, then i values his bundle at least 1/n of the remainder. A PROP*0 allocation is simply called proportional.
EF0 implies PROP*0, and EF1 implies PROP*(n-1). Moreover, for any integer c 0, EFc implies PROP*((n-1)c).: Lem.2.3 The opposite implication is true when n=2, but not when n>2.
The following maximin-share approximations are implied by PROP*(n-1), hence also by EF1:: Lem.2.7
Multiplicative approximation: 1/n-fraction MMS (the 1/n is tight);: Prop.3.6
Ordinal approximation: 1-of-(2n-1) MMS (the 2n-1 is tight). Similarly, for every integer c, PROP*c implies 1-of-(c+n) MMS.
MMS when the value function is binary. The opposite implication holds too.
The above implications are illustrated below:
An allocation is called envy-free-except-any-item (EFx) for an agent i if, for every other agent j, for any single item removed from j's bundle, i does not envy the remainder. EFx is strictly stronger than EF1. It implies the following MMS approximations:: Prop.3.3-3.4
2/3-fraction MMS for 2 or 3 agents (it is tight);
4/7-fraction MMS for any number of agents (it is not known whether it is tight; the current upper bound is 8/13).
MMS for groups
An allocation is called pairwise-maximin-share-fair (PMMS-fair) if, for every two agents i and j, agent i receives at least his 1-out-of-2 maximin-share restricted to the items received by i and j. It is not known whether a PMMS allocation always exists, but a 0.618-approximation always exists.
An allocation is called groupwise-maximin-share-fair (GMMS-fair) if, for every subgroup of agents of size k, each member of the subgroup receives his/her 1-out-of-k maximin-share restricted to the items received by this subgroup.
With additive valuations, the various fairness notions are related as follows:
Envy-freeness implies GMMS-fairness;
GMMS-fairness implies MMS-fairness (by taking the subgroup of size n) and PMMS-fairness (by taking subgroups of size 2);
PMMS-fairness implies 2/3-MMS-fairness for three agents, and 4/7-MMS-fairness in general;
PMMS-fairness implies EFX, which implies EF1.
EF1 implies 1/2-PMMS and EFX implies 2/3-PMMS.: Prop.3.7-3.8 Hence, a 1/2-PMMS allocation can be found in polynomial time.
MMS-fairness and PMMS-fairness do not imply each other.
GMMS allocations are guaranteed to exist when the valuations of the agents are either binary or identical. With general additive valuations, 1/2-GMMS allocations exist and can be found in polynomial time.
MMS for agents with different entitlements
When agents have different entitlements (also termed: unequal shares or asymmetric rights), MMS fairness should be adapted to guarantee a higher share to agents with higher entitlements. Various adaptations have been suggested. Below, we assume that the entitlements are given by a vector
t
=
(
t
1
,
…
,
t
n
)
{\displaystyle t=(t_{1},\ldots ,t_{n})}
, where
t
i
{\displaystyle t_{i}}
represents the entitlement of agent
i
{\displaystyle i}
.
= Weighted-MMS fairness
=Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin and Seddigin introduce the Weighted Maximin Share (WMMS), defined by:
WMMS
i
t
(
C
)
:=
max
(
Z
1
,
…
,
Z
n
)
∈
Partitions
(
C
,
n
)
min
j
∈
[
n
]
t
i
t
j
V
(
Z
j
)
=
t
i
⋅
max
(
Z
1
,
…
,
Z
n
)
∈
Partitions
(
C
,
n
)
min
j
∈
[
n
]
V
(
Z
j
)
t
j
{\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
WMMS
1
t
(
{
1
,
3
,
5
,
6
,
9
}
)
=
4
{\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
i
{\displaystyle i}
equals
24
t
i
{\displaystyle 24t_{i}}
. By the same partition,
WMMS
2
t
=
11
{\displaystyle \operatorname {WMMS} _{2}^{t}=11}
and
WMMS
3
t
=
9
{\displaystyle \operatorname {WMMS} _{3}^{t}=9}
. When all n entitlements are equal,
WMMS
i
t
≡
MMS
i
1
-out-of-
n
{\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
WMMS
i
t
(
C
)
{\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,
WMMS
i
t
=
t
i
{\displaystyle \operatorname {WMMS} _{i}^{t}=t_{i}}
for all agents i (for comparison, note that
MMS
i
1
-out-of-
n
=
ϵ
=
t
i
{\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=\epsilon =t_{i}}
for the small agents, but
MMS
i
1
-out-of-
n
=
[
1
−
(
n
−
1
)
ϵ
]
/
n
=
t
i
/
n
{\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
WMMS
i
t
{\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
t
i
/
WMMS
i
t
{\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
WMMS
i
t
/
2
{\displaystyle \operatorname {WMMS} _{i}^{t}/2}
) who values it the most. This algorithm allocates to each agent i at least
WMMS
i
t
/
2
{\displaystyle \operatorname {WMMS} _{i}^{t}/2}
and at most
WMMS
i
t
{\displaystyle \operatorname {WMMS} _{i}^{t}}
. In practice, a WMMS-fair allocation almost always exists.
= Ordinal-MMS fairness
=Babaioff, Nisan and Talgam-Cohen present a natural extension of the ordinal MMS approximation to agents with different entitlements. For any two integers
l
,
d
{\displaystyle l,d}
, set C and value function V, define
MMS
V
l
-out-of-
d
(
C
)
:=
max
P
∈
Partitions
(
C
,
d
)
min
Z
∈
Unions
(
P
,
l
)
V
(
Z
)
{\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
d
{\displaystyle d}
disjoint subsets, and the minimum is over all unions of
l
{\displaystyle l}
parts. For example,
MMS
V
2
-out-of-
3
(
{
1
,
3
,
5
,
6
,
9
}
)
=
15
{\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:
OMMS
i
t
(
C
)
:=
max
l
,
d
:
l
/
d
≤
t
i
MMS
i
l
-out-of-
d
(
C
)
{\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
l
,
d
{\displaystyle l,d}
satisfying with
l
/
d
≤
t
i
{\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. An allocation Z1,...,Zn is called OMMS-fair for entitlement-vector w if the value of each agent i is at least
OMMS
i
t
(
C
)
{\displaystyle \operatorname {OMMS} _{i}^{t}(C)}
.
The OMMS can be higher or lower than the WMMS, depending on the values:
As an example in which WMMS is higher, suppose C = {40, 60} and t = (0.4, 0.6). Then clearly WMMS1=40 and WMMS2=60, so the only WMMS-fair allocation gives the 40 to 1 and the 60 to 2. However, OMMS1=0, since the fractions satisfying
l
/
d
≤
0.4
{\displaystyle l/d\leq 0.4}
are 1/3, 2/5, 3/7, etc., and in all cases, in any partition of C into
d
{\displaystyle d}
subsets, there are at least
l
{\displaystyle l}
empty subsets. Also, OMMS2=40, since the fractions satisfying
l
/
d
≤
0.6
{\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
d
{\displaystyle d}
subsets, the
l
{\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 WMMSi=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, OMMS1=OMMS2=0. However, OMMS3=40 by the pair
l
/
d
=
1
/
2
{\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.
= AnyPrice-Share fairness
=Babaioff, Ezra and Feige 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:
APS
V
t
(
C
)
:=
max
P
∈
AllowedBundleSets
(
C
,
t
i
)
min
Z
∈
P
V
(
Z
)
{\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 ti. There is a polyomial-time algorithm that guarantees to each agent at least 3/5 of his APS.
The APS is always at least as high as the OMMS: given an optimal l-out-of-d partition, with l/d ≤ ti, 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 ti. 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 ti = 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 ti = 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 WMMS1=40 and WMMS2=60. But APS1=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, APS2=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 WMMSi=0 for all i. Similarly, APS1=APS2=0 as above. However, APS3=40 e.g. by the weights 0.5*{40}, 0.5*{60}.
Maximin share as a function of the largest item value
Theodore Hill presented a version of the MMS that depends on the largest item value.
See also
Bin covering problem and Bin packing problem - two well-studied optimization problems that can be seen as special cases of indivisible goods allocation and indivisible chores allocation, respectively. Many techniques used for these problems are useful in the case of maximin share item allocation, too.
Egalitarian item allocation - often called by the very similar name "max-min item allocation", but its definition and the allocations it yields are very different than maximin share fairness.
References
Kata Kunci Pencarian:
- Maximin share
- Fair item allocation
- List of unsolved problems in fair division
- Egalitarian item allocation
- Saint-Maximin-la-Sainte-Baume
- Entitlement (fair division)
- Envy-free item allocation
- Multiway number partitioning
- Greedy number partitioning
- Identical-machines scheduling
