Maximin share

Last updated

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

Contents

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 (or, if they were divisible only to integer values as in the preceding paragraph, at least ), 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:

Now, each agent has a different MMS:

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 (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 [1] 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 [2] 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 [3] 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 [1] 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 (see the paper for a plot of 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 [4] 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 [5] 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 [6] 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 [3] and Kurokawa [7] 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 [8] 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.

Valuations in negative example of Feige, Sapir and Tauber with agents and items
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 [9] showed that this holds true for two cases:

Amanatidis, Markakis, Nikzad and Saberi [11] 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 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 [12] proved that MMS allocations exist in the following cases:

The latter result was later improved to by Kurokawa, Procaccia and Wang [9] and by Feige, Sapir and Tauber. [8] 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 [13] further showed that MMS allocations exist in the following cases:

Amanatidis, Markakis, Nikzad and Saberi [11] 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 [14] 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 [2] introduced an approximation to the 1-of-n MMS—the 1-of-() 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:

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 [3] 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:

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.

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 [3] presented an algorithm that always finds an rn-fraction MMS, where

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 [11] presented several improved algorithms:

Barman and Krishnamurthy [15] [16] presented:

Ghodsi, Hajiaghayi, Seddighin, Seddighin and Yami [17] presented:

Garg, McGlaughlin and Taki [18] presented a simple algorithm for 2/3-fraction MMS-fairness whose analysis is also simple.

Garg and Taki [19] presented:

Akrami, Garg, Sharma and Taki [20] improve the analysis of the algorithm presented by Garg and Taki, simplifying the analysis and improving the existence guarantee to .

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

Multiplicative approximation results for MMS
ValuationsLower boundUpper boundPolynomial-time algorithm
Additive [21] [17] [20] [8] [8] [19]
Submodular [17] [17] [17]
XOS [22] [17] [17]
Subadditive [17] [17]

Ordinal approximations

Budish [2] showed that the Approximate Competitive Equilibrium from Equal Incomes always guarantees the 1-of-() 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:

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 [26] showed that the max-Nash-welfare allocation (the allocation maximizing the product of utilities) is always -fraction MMS fair, and it is tight.

Truthfulness: Amanatidis, Birmpas and Markakis [27] presented truthful mechanisms for approximate MMS-fair allocations (see also Strategic fair division):

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.

Conflict graph: Hummel and Hetland [30] 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.

MMS-fair allocation of chores

Aziz, Rauchecker, Schryen and Walsh [33] 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 [16] presented an algorithm attaining 4/3-fraction MMS (precisely, ). The algorithm can be seen as a generalization of the LPT algorithm for identical-machines scheduling.

Huang and Lu [34] 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 [35] study MMS-fair allocation with mixed valuations, i.e., when there are both goods and chores. They prove that:

Ebadian, Peters and Shah [36] 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 (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 . After this scaling, the MMS approximation problems can be stated as:

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: [18]

Allocating one object

If we remove one object from . Then for each agent, the -out-of-() MMS w.r.t. the remaining set is at least his -out-of- MMS w.r.t. the original set . This is because, in the original MMS partition, parts remain intact. [12] Now, suppose we aim to give each agent a value of . If some object is worth at least to at least one agent, then we can give 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:

This normalization works even with the fast scaling, and with arbitrary monotone valuations (even non-additive). [17]

Bag filling

Denote an object, that is valued by at most by all agents, as an "-small object". Suppose that all objects are -small. Take an empty bag and fill it with object after object, until the bag is worth at least to at least one agent. Then, give the bag to one such agent arbitrarily. Since all objects are -small, the remaining agents value the bag at most ; if this value is sufficiently small, then the remaining value is sufficiently large so that we can proceed recursively. [18] In particular, bag-filling gives as the following solutions:

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. [18] In fact, both algorithms can be stated without mentioning the MMS at all:

Modified bag filling: The condition that all objects are -small can be relaxed as follows. [18] Take some . Denote an object that is not -small (i.e., valued at least by at least one agent) as an "-large object". Suppose at most objects are -large. Take one -large object , put it in a bag, and fill it with -small objects until one agent indicates that it is worth for him at least . There must be at least one such agent, since some agent values at some . For this agent, there are at most remaining -large objects. By the previous normalization, these objects are still -small, so their total value for is at most , so the value of remaining -small objects is at least .

Ordering

An instance is ordered if all agents have the same ordinal ranking on the objects, i.e, the objects can be numbered such that, for each agent , . Intuitively, ordered instances are hardest, since the conflict between agents is largest. Indeed, the negative instance of [3] is ordered - the order of the objects is determined by the matrix , 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 -fraction MMS allocation. Now, we are given a general item-allocation instance . We solve it in the following way. [12] [15]

  1. Construct an ordered instance in the following way: for every agent i, define in as the -th highest value in the set of values of agent in . This requires time.
  2. Find an -fraction MMS allocation in .
  3. Construct a picking sequence in which the agent who received in picks first, the agent who received in picks second, etc.
  4. Let agents pick their best items according to the picking-sequence. Let be the resulting allocation. In , each agent receives exactly the same number of items as in . Moreover, each agent who received in , receives one of his top items in . Therefore, his value for each item he got in is at least as large as his value for the corresponding item in . Therefore, the value of every agent in is at least as high as in . Since the ordering does not change the MMS values, the new allocation is still -fraction MMS.

So when looking for -fraction MMS allocations, we can assume w.l.o.g. that:

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. [17] :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:

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. [18]

The guarantee of this algorithm can be stated even without mentioning MMS:

Algorithmic problems

Several basic algorithms related to the MMS are:

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). [39] :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: [39] :Lem.2.7

The above implications are illustrated below:

Envy-freeProportionalMaximin-share
1/n-fraction MMS
EF1PROP*(n-1)MMS for binary valuation
1-out-of-(2n-1) MMS
EFcPROP*((n-1)c)1-out-of-((n-1)c+n) MMS

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: [40] :Prop.3.3-3.4

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. [26]

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. [41]

With additive valuations, the various fairness notions are related as follows:

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. [41]

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 , where represents the entitlement of agent .

Weighted-MMS fairness

Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin and Seddigin [42] introduce the Weighted Maximin Share (WMMS), defined by:

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 by the partition ({1,3},{5,6},{9}); it is optimal since the value of each part equals . By the same partition, and . When all n entitlements are equal, .

An allocation of C is called WMMS-fair for entitlement-vector t if the value of each agent i is at least . 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:

AgentEntitlementValue for items 1, ..., n-1Value for item nValue for items n+1, ..., 2n-1
1, ..., n-1εε1-(n-1)ε0
n1-(n-1)ε[1-(n-1)ε] / n[1-(n-1)ε] / nε

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, for all agents i (for comparison, note that for the small agents, but 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 , 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 ; and in each iteration, an item is given to an unsatisfied agent (an agent with value less than ) who values it the most. This algorithm allocates to each agent i at least and at most . In practice, a WMMS-fair allocation almost always exists. [42]

Ordinal-MMS fairness

Babaioff, Nisan and Talgam-Cohen [43] present a natural extension of the ordinal MMS approximation to agents with different entitlements. For any two integers , set C and value function V, define

Here, the maximum is over all partitions of C into disjoint subsets, and the minimum is over all unions of parts. For example, by the partition ({1,6},{3,5},{9}). Now, the Ordinal Maximin Share (OMMS) is defined by:

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 satisfying with , only finitely-many of them are not redundant (not implied by others), so it is possible to compute the OMMS in finite time. [44] An allocation Z1,...,Zn is called OMMS-fair for entitlement-vector w if the value of each agent i is at least .

The OMMS can be higher or lower than the WMMS, depending on the values: [44]

AnyPrice-Share fairness

Babaioff, Ezra and Feige [45] 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:

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. [45]

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:

The APS can be higher or lower than the WMMS; the examples are the same as the ones used for OMMS vs WMMS:

Maximin share as a function of the largest item value

Theodore Hill [1] presented a version of the MMS that depends on the largest item value.

See also

Related Research Articles

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

In economics, philosophy, and social choice theory, a person's entitlement refers to the value of goods they are owed or deserve, i.e. the total value of the goods or resources that a player would ideally receive. For example, in party-list proportional representation, a party's seat entitlement is equal to its share of the vote, times the number of seats in the legislature.

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle they received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

In computer science, greedy number partitioning is a class of greedy algorithms for multiway number partitioning. The input to the algorithm is a set S of numbers, and a parameter k. The required output is a partition of S into k subsets, such that the sums in the subsets are as nearly equal as possible. Greedy algorithms process the numbers sequentially, and insert the next number into a bin in which the sum of numbers is currently smallest.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.

In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset of n integers and a positive integer m representing the number of subsets. The goal is to construct, from the input integers, some m subsets. The problem has several variants:

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.

References

  1. 1 2 3 Hill, Theodore P. (1987). "Partitioning General Probability Measures". The Annals of Probability. 15 (2): 804–813. doi: 10.1214/aop/1176992173 . ISSN   0091-1798. JSTOR   2244076.
  2. 1 2 3 Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061–1103. doi:10.1086/664613. S2CID   154703357.
  3. 1 2 3 4 5 6 Procaccia, AD; Wang, J (2014). "Fair enough: guaranteeing approximate maximin shares". EC '14 Proceedings of the Fifteenth ACM Conference on Economics and Computation. pp. 675–692. doi:10.1145/2600057.2602835. ISBN   9781450325653. S2CID   53223172.
  4. Markakis, Evangelos; Psomas, Christos-Alexandros (2011). "On Worst-Case Allocations in the Presence of Indivisible Goods". In Chen, Ning; Elkind, Edith; Koutsoupias, Elias (eds.). Internet and Network Economics. Lecture Notes in Computer Science. Vol. 7090. Berlin, Heidelberg: Springer. pp. 278–289. doi:10.1007/978-3-642-25510-6_24. ISBN   978-3-642-25510-6.
  5. Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015-07-19). "Worst case compromises in matroids with applications to the allocation of indivisible goods". Theoretical Computer Science. 589: 121–140. doi:10.1016/j.tcs.2015.04.029. ISSN   0304-3975.
  6. Li, Bo; Moulin, Hervé; Sun, Ankang; Zhou, Yu (2023). "On Hill's Worst-Case Guarantee for Indivisible Bads". arXiv: 2302.00323 [cs.GT].
  7. "Archived copy" (PDF). Archived from the original (PDF) on 2019-07-28. Retrieved 2019-11-29.{{cite web}}: CS1 maint: archived copy as title (link)
  8. 1 2 3 4 Feige, Uriel; Sapir, Ariel; Tauber, Laliv (2021-10-19). "A tight negative example for MMS fair allocations". arXiv: 2104.04977 [cs.GT].
  9. 1 2 Kurokawa, David; Procaccia, Ariel; Wang, Junxing (2016-02-21). "When Can the Maximin Share Guarantee be Guaranteed?". Proceedings of the AAAI Conference on Artificial Intelligence. 30 (1). doi: 10.1609/aaai.v30i1.10041 . ISSN   2374-3468. S2CID   7556264.
  10. Dickerson, John; Goldman, Jonathan; Karp, Jeremy; Procaccia, Ariel; Sandholm, Tuomas (2014-06-21). "The Computational Rise and Fall of Fairness". Proceedings of the AAAI Conference on Artificial Intelligence. 28 (1). doi: 10.1609/aaai.v28i1.8884 . ISSN   2374-3468. S2CID   3178022.
  11. 1 2 3 Amanatidis, Georgios; Markakis, Evangelos; Nikzad, Afshin; Saberi, Amin (2017-12-04). "Approximation Algorithms for Computing Maximin Share Allocations". ACM Transactions on Algorithms. 13 (4): 1–28. arXiv: 1503.00941 . doi:10.1145/3147173. S2CID   13366555.
  12. 1 2 3 4 Bouveret, Sylvain; Lemaître, Michel (2015). "Characterizing conflicts in fair division of indivisible goods using a scale of criteria". Autonomous Agents and Multi-Agent Systems. 30 (2): 259. doi:10.1007/s10458-015-9287-3. S2CID   16041218.
  13. Hummel, Halvard (2023-02-01). "On Lower Bounds for Maximin Share Guarantees". arXiv: 2302.00264 [cs.GT].
  14. https://www.wisdom.weizmann.ac.il/~feige/mypapers/MMSab.pdf [ bare URL PDF ]
  15. 1 2 Barman, Siddharth; Krishnamurthy, Sanath Kumar (2017-03-06). "Approximation Algorithms for Maximin Fair Division". arXiv: 1703.01851 [cs.GT].
  16. 1 2 3 Barman, Siddharth; Krishnamurthy, Sanath Kumar (2020-03-06). "Approximation Algorithms for Maximin Fair Division". ACM Transactions on Economics and Computation. 8 (1): 5:1–5:28. arXiv: 1703.01851 . doi:10.1145/3381525. ISSN   2167-8375. S2CID   217191332.
  17. 1 2 3 4 5 6 7 8 9 10 11 12 13 Ghodsi, Mohammad; Hajiaghayi, Mohammadtaghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (2018-06-11). "Fair Allocation of Indivisible Goods: Improvements and Generalizations". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. New York, NY, USA: Association for Computing Machinery. pp. 539–556. doi:10.1145/3219166.3219238. ISBN   978-1-4503-5829-3. S2CID   450827.
  18. 1 2 3 4 5 6 Garg, Jugal; McGlaughlin, Peter; Taki, Setareh (2018). Fineman, Jeremy T.; Mitzenmacher, Michael (eds.). "Approximating Maximin Share Allocations". 2nd Symposium on Simplicity in Algorithms (SOSA 2019). OpenAccess Series in Informatics (OASIcs). 69. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 20:1–20:11. doi: 10.4230/OASIcs.SOSA.2019.20 . ISBN   978-3-95977-099-6.
  19. 1 2 Garg, Jugal; Taki, Setareh (2020-07-13). "An Improved Approximation Algorithm for Maximin Shares". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 379–380. arXiv: 1903.00029 . doi:10.1145/3391403.3399526. ISBN   978-1-4503-7975-5. S2CID   67855844.
  20. 1 2 Akrami, Hannaneh; Garg, Jugal; Sharma, Eklavya; Taki, Setareh (2023-03-29). "Simplification and Improvement of MMS Approximation". arXiv: 2303.16788 [cs.GT].
  21. Feige, Uriel; Norkin, Alexey (2022-05-11). "Improved maximin fair allocation of indivisible items to three agents". arXiv: 2205.05363 [cs.GT].
  22. Akrami, Hannaneh; Melhorn, Kurt; Seddighin, Masoud; Shahkarami, Golnoosh (2023-12-15). "Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations" (PDF). Advances in Neural Information Processing Systems. 36: 58821–58832. arXiv: 2308.14545 .
  23. Aigner-Horev, Elad; Segal-Halevi, Erel (2022). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv: 1901.09527 . doi:10.1016/j.ins.2021.11.059. S2CID   170079201.
  24. Hosseini, Hadi; Searns, Andrew (2020-12-01). "Guaranteeing Maximin Shares: Some Agents Left Behind". arXiv: 2105.09383 [cs.GT].
  25. Hosseini, Hadi; Searns, Andrew; Segal-Halevi, Erel (2022-01-19). "Ordinal Maximin Share Approximation for Chores". arXiv: 2201.07424 [cs.GT].
  26. 1 2 Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-01). "The Unreasonable Fairness of Maximum Nash Welfare" (PDF). ACM Trans. Econ. Comput. 7 (3): 12:1–12:32. doi:10.1145/3355902. ISSN   2167-8375. S2CID   202729326.
  27. Amanatidis, Georgios; Birmpas, Georgios; Markakis, Evangelos (2016-05-12). "On Truthful Mechanisms for Maximin Share Allocations". arXiv: 1605.04026 [cs.GT].
  28. Barman, Siddharth; Biswas, Arpita (2018-04-25). "Fair Division Under Cardinality Constraints". arXiv: 1804.09521 [cs.GT].
  29. Hummel, Halvard; Hetland, Magnus Lie (2021-06-14). "Guaranteeing Half-Maximin Shares Under Cardinality Constraints". arXiv: 2106.07300 [cs.GT].
  30. Hummel, Halvard; Hetland, Magnus Lie (2022). "Fair allocation of conflicting items". Autonomous Agents and Multi-Agent Systems. 36. arXiv: 2104.06280 . doi:10.1007/s10458-021-09537-3. S2CID   233219836.
  31. Bouveret, Sylvain; Cechlárová, Katarína; Elkind, Edith; Igarashi, Ayumi; Peters, Dominik (2017-06-06). "Fair Division of a Graph". arXiv: 1705.10239 [cs.GT].
  32. Lonc, Zbigniew; Truszczynski, Miroslaw (2019-05-09). "Maximin share allocations on cycles". arXiv: 1905.03038 [cs.SI].
  33. Aziz, Haris; Rauchecker, Gerhard; Schryen, Guido; Walsh, Toby (2016-04-05). "Approximation Algorithms for Max-Min Share Allocations of Indivisible Chores and Goods". arXiv: 1604.01435 [cs.GT].
  34. Huang, Xin; Lu, Pinyan (2019-07-10). "An algorithmic framework for approximating maximin share allocation of chores". arXiv: 1907.04505 [cs.GT].
  35. Kulkarni, Rucha; Mehta, Ruta; Taki, Setareh (2021-04-05). "Indivisible Mixed Manna: On the Computability of MMS + PO Allocations". arXiv: 2007.09133 [cs.GT].
  36. Ebadian, Soroush; Peters, Dominik; Shah, Nisarg (2022-02-03), How to Fairly Allocate Easy and Difficult Chores, arXiv: 2110.11285
  37. Lang, Jérôme; Rothe, Jörg (2016). "Fair Division of Indivisible Goods". In Rothe, Jörg (ed.). Economics and Computation. Springer Texts in Business and Economics. Springer Berlin Heidelberg. pp. 493–550. doi:10.1007/978-3-662-47904-9_8. ISBN   9783662479049.{{cite book}}: |journal= ignored (help)
  38. Heinen, Tobias; Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Rothe, Jörg (2018-11-01). "Approximation and complexity of the optimization and existence problems for maximin share, proportional share, and minimax share allocation of indivisible goods". Autonomous Agents and Multi-Agent Systems. 32 (6): 741–778. doi:10.1007/s10458-018-9393-0. ISSN   1573-7454. S2CID   49479969.
  39. 1 2 Segal-Halevi, Erel; Suksompong, Warut (2019-12-01). "Democratic fair allocation of indivisible goods". Artificial Intelligence. 277: 103167. arXiv: 1709.02564 . doi:10.1016/j.artint.2019.103167. ISSN   0004-3702. S2CID   203034477.
  40. 1 2 3 4 Amanatidis, Georgios; Birmpas, Georgios; Markakis, Evangelos (2018-07-13). "Comparing approximate relaxations of envy-freeness". Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI'18. Stockholm, Sweden: AAAI Press: 42–48. arXiv: 1806.03114 . ISBN   978-0-9992411-2-7.
  41. 1 2 3 Barman, Siddharth; Biswas, Arpita; Krishnamurthy, Sanath Kumar; Narahari, Y. (2017-11-20). "Groupwise Maximin Fair Allocation of Indivisible Goods". arXiv: 1711.07621 [cs.GT].
  42. 1 2 Farhadi, Alireza; Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Lahaie, Sébastien; Pennock, David; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (2019-01-07). "Fair Allocation of Indivisible Goods to Asymmetric Agents". Journal of Artificial Intelligence Research. 64: 1–20. arXiv: 1703.01649 . doi: 10.1613/jair.1.11291 . ISSN   1076-9757. S2CID   15326855.
  43. Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (2021-01-27). "Competitive Equilibrium with Indivisible Goods and Generic Budgets". Mathematics of Operations Research. 46 (1): 382–403. arXiv: 1703.08150 . doi:10.1287/moor.2020.1062. ISSN   0364-765X. S2CID   8514018.
  44. 1 2 Segal-Halevi, Erel (2019-12-18). "The Maximin Share Dominance Relation". arXiv: 1912.08763 [math.CO].
  45. 1 2 Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2021-06-06). "Fair-Share Allocations for Agents with Arbitrary Entitlements". arXiv: 2103.04304 [cs.GT].