Search in Co-Wiki

Maximin share

game-theory 6362 tokens 11 outbound links

Maximin share

Motivation and examples Identical items. Suppose first that <math>m</math> identical items have to be allocated fairly among <math>n</math> people. Ideally, each person should receive <math>m/n</math> items, but this may be impossible if <math>m</math> is not divisible by <math>n</math>, as the items are indivisible. A natural second-best fairness criterion is to round <math>m/n</math> down to the nearest integer, and give each person at least <math>\lfloor m/n \rfloor</math> items. Receiving less than <math>\lfloor m/n \rfloor</math> items is "too unfair" - it is an unfairness not justified by the indivisibility of the items.

The set <math>\{1, 6\}</math> 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 <math>3</math> 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 <math>7</math>.

Now, each agent has a different MMS:

Here, an allocation is MMS-fair if it gives Alice a value of at least <math>7</math>, George a value of at least <math>8</math>, and Dina a value of at least <math>3</math>. For example, giving George the first two items <math>\{1, 7\}</math>, Alice the next two items <math>\{5, 6\}</math>, and Dina the last item <math>\{17\}</math>, is MMS-fair.

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 MMS-fairness in 2011, in the context of [[course-allocation]]. He presented the [[approximate-competitive-equilibrium-from-equal-incomes|A-CEEI]] mechanism, which attains an approximately MMS-fair allocation if it is allowed to add some goods. In 2014, Procaccia and Wang 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 <math>n = 3</math> agents and <math>m = 12</math> 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 <math>V_n(\alpha)</math>. In their instance, there are <math>12</math> objects, indexed by <math>i\in[3]</math> and <math>j\in[4]</math>. Each agent <math>k</math> values each object <math>(i,j)</math> by:<blockquote><math>v_k(i,j) = 1,000,000 + 1,000\cdot T_{i,j} + E_{i,j}^{(k)}</math></blockquote>where <math>T, E^{(1)}, E^{(2)}, E^{(3)}</math> are particular 3-by-4 matrices with values smaller than <math>100</math>. They prove that every agent can partition the objects into <math>3</math> subsets of <math>4</math> 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 <math>n \ge 3</math> there is such an instance with <math>3n + 4</math> items.

Feige, Sapir and Tauber showed that this holds true for two cases:

There are many items: <math>m \geq \alpha\cdot n \ln{n}</math> for some constant <math> \alpha</math> 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: <math>m < n^{8/7}</math> [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 <math>n</math> 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 proved that MMS allocations exist in the following cases:

Binary valuations – each agent either likes an item (values it at <math>1</math>) or dislikes it (values it at <math>0</math>). Identical multisets – agents may value the items differently, but the multisets of the agents' values are the same. Few items* – <math>m \le n + 3</math>. The latter result was later improved to <math>m \le n + 4 </math> by Kurokawa, Procaccia and Wang Due to the negative example with three agents and nine items, this is the largest constant <math>c </math> that exists, such that all instances with <math>n </math> agents and <math>m \le n + c </math> items always have MMS allocations, no matter the value of <math>n </math>. Hummel further showed that MMS allocations exist in the following cases:

Amanatidis, Markakis, Nikzad and Saberi 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** 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 <math>\frac{2n}{3n-1}</math> 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:

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 <math>\frac{3}{4} + \min\left(\frac{1}{36}, \frac{3}{16n - 4}\right)</math>.

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 <math>3/4</math> and <math>39/40</math>.

}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.

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** presented truthful mechanisms for approximate MMS-fair allocations (see also [[strategic-fair-division]]):

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:

Barman and Krishnamurthy** 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:

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 <math>k_i</math> (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 <math>1</math>. After this scaling, the MMS approximation problems can be stated as:

<math>r</math>-fraction MMS: the total value of <math>O</math> is at least <math>n</math>; we need to give each of <math>n</math> agents a bundle worth at least <math>r</math>. 1-of-d MMS: the total value of <math>O</math> is at least <math>d</math>; we need to give each of <math>n</math> agents a bundle worth at least <math>1</math>. 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: 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 <math>NP^{NP}</math>, 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.

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 js bundle, then i does not envy the remainder. An EF0 allocation is simply called [[envy-free-item-allocation|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 (PROPc*) for an agent *i* if there exists a set of at most *c* items outside *is bundle that, if removed from the set of all items, then i values his bundle at least 1/n of the remainder. A PROP0 allocation is simply called proportional*.

EF0 implies PROP0, and EF1 implies PROP(n-1). Moreover, for any integer c 0, EFc implies PROP((n-1)c). 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: 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 js bundle, i does not envy the remainder. EFx is strictly stronger than EF1. It implies the following MMS approximations:*

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; introduce the Weighted Maximin Share (WMMS), defined by:<blockquote><math>\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}</math></blockquote>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 <math>\operatorname{WMMS}_{1}^{t}(\{1,3,5,6,9\}) = 4 </math> by the partition ({1,3},{5,6},{9}); it is optimal since the value of each part <math>i</math> equals <math>24 t_i</math>. By the same partition, <math>\operatorname{WMMS}_{2}^{t}= 11 </math> and <math>\operatorname{WMMS}_{3}^{t} = 9 </math>. When all n* entitlements are equal, <math>\operatorname{WMMS}_{i}^{t} \equiv \operatorname{MMS}_i^{1\text{-out-of-}n} </math>.

An allocation of C is called WMMS-fair for entitlement-vector t if the value of each agent i is at least <math>\operatorname{WMMS}_{i}^{t}(C) </math>. 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, <math>\operatorname{WMMS}_{i}^{t} = t_i </math> for all agents i (for comparison, note that <math>\operatorname{MMS}_{i}^{1\text{-out-of-}n} = \epsilon = t_i </math> for the small agents, but <math>\operatorname{MMS}_{i}^{1\text{-out-of-}n} = [1-(n-1)\epsilon] / n = t_i/n </math> 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 <math>\operatorname{WMMS}_{i}^{t} </math>, 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 <math>t_i / \operatorname{WMMS}_{i}^{t} </math>; and in each iteration, an item is given to an unsatisfied agent (an agent with value less than <math>\operatorname{WMMS}_{i}^{t}/2 </math>) who values it the most. This algorithm allocates to each agent i at least <math>\operatorname{WMMS}_{i}^{t}/2 </math> and at most <math>\operatorname{WMMS}_{i}^{t} </math>. In practice, a WMMS-fair allocation almost always exists. present a natural extension of the ordinal MMS approximation to agents with different entitlements. For any two integers <math>l,d</math>, set *C* and value function *V*, define<blockquote><math>\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)</math></blockquote>Here, the maximum is over all partitions of *C* into <math>d</math> disjoint subsets, and the minimum is over all *unions* of <math>l</math> parts. For example, <math>\operatorname{MMS}_{V}^{2\text{-out-of-}3}(\{1,3,5,6,9\}) = 15 </math> by the partition ({1,6},{3,5},{9}). Now, the Ordinal Maximin Share (OMMS)** is defined by:<blockquote><math>\operatorname{OMMS}_{i}^{t}(C) := ~~~ \max_{l,d:~l/d \leq t_i} \operatorname{MMS}^{l\text{-out-of-}d}_i(C)</math></blockquote>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 <math>l,d</math> satisfying with <math>l/d\leq t_i</math>, 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 *Z*1,...,*Zn* is called *OMMS-fair for entitlement-vector w* if the value of each agent i is at least <math>\operatorname{OMMS}_{i}^{t}(C) </math>.

The OMMS can be higher or lower than the WMMS, depending on the values: 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: <blockquote><math>\operatorname{APS}_{V}^{t}(C) := ~~~\max_{P \in \operatorname{AllowedBundleSets}(C,t_i)} ~~~ \min_{Z\in P} ~~~ V(Z)</math> </blockquote>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. 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 <references />