Egalitarian item allocation: Difference between revisions

Content deleted Content added

Inline

Revision as of 00:41, 22 November 2020

Max-min item allocation is a fair item allocation problem, in which 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. Another term for a max-min allocation is egalitarian-optimal.

Max-min item allocation is a generalization of multiway number partitioning (the latter corresponds to the special case in which all agents have the same valuations), which is itself a generalization of the partition problem (the latter corresponds to the special case of two agents). Therefore, it is NP-hard in general.

Note the difference between max-min item allocation and maximin share item allocation. The former is an optimization problem, while the latter is a satisfaction problem: the goal is to guarantee that each agent receives a value above a certain threshold.

Algorithms

Below, n is the number of agents and m is the number of items. For agents with additive valuations:

Asadpour and Saberi^[1] gave a polynomial-time algorithm that approximates the optimal solution within a factor of $O({\sqrt {n}}\cdot \log ^{3}n)$ . Their algorithm uses an iterative method for rounding a fractional matching on a tree. They also provide better bounds when it is allowed to exclude a small fraction of people from the problem.

Chakrabarty, Chuzoy and Khanna^[2] improved this bound to $O(n^{\varepsilon })$ , with a run-time of $O(n^{1/\varepsilon })$ , for any $\varepsilon \in \Omega \left({\frac {\log \log n}{\log n}}\right)$ .
Golovin^[3] gives an algorithm by which, for every integer $k$ , a $(1-1/k)$ fraction of the agents receive utility at least $OPT/k$ . This result is obtained from rounding a suitable linear programming relaxation of the problem, and is the best possible result for this linear program.

For agents with general cardinal valuations:

With two classes of goods, an $O({\sqrt {n}})$ approximation exists.
With submodular utility functions, an $(m-n+1)$ approximation exists.
Nguyen, Roos and Rothe^[4]^[5] present some stronger hardness results.

The special case of optimizing egalitarian welfare with additive utilities is called "the Santa Claus problem".^[6] The problem is still NP-hard and cannot be approximated within a factor > 1/2, but there is an $O(n)$ approximation^[7] and a more complicated $O({\sqrt {n}}\cdot \log ^{3}{n})$ approximation.^[8] See also ^[9] for a branch-and-bound algorithm for two partners.

The Decreasing Demand procedure returns an egalitarian-optimal division in an ordinal sense: it maximizes the rank, in the linear-ranking of bundles, of the agent with the lowest rank. It works for any number of agents with any ordering of bundles.

References

^ Asadpour, Arash; Saberi, Amin (2010-01-01). "An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods". SIAM Journal on Computing. 39 (7): 2970–2989. doi:10.1137/080723491. ISSN 0097-5397.
^ Chakrabarty, D.; Chuzhoy, J.; Khanna, S. (2009-10-01). "On Allocating Goods to Maximize Fairness". 2009 50th Annual IEEE Symposium on Foundations of Computer Science: 107–116. doi:10.1109/FOCS.2009.51.
^ Golovin, Daniel (2005). "Max-min fair allocation of indivisible goods". CMU. Retrieved 27 August 2016.
^ Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation". Annals of Mathematics and Artificial Intelligence. 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497. doi:10.1007/s10472-012-9328-4.
^ Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Computational complexity and approximability of social welfare optimization in multiagent resource allocation". Autonomous Agents and Multi-Agent Systems. 28 (2): 256. doi:10.1007/s10458-013-9224-2.
^ Bansal, Nikhil; Sviridenko, Maxim (2006). "The Santa Claus problem". Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06. p. 31. doi:10.1145/1132516.1132522. ISBN 1595931341.
^ Bezáková, Ivona; Dani, Varsha (2005). "Allocating indivisible goods". ACM SIGecom Exchanges. 5 (3): 11. CiteSeerX 10.1.1.436.18. doi:10.1145/1120680.1120683.
^ Asadpour, Arash; Saberi, Amin (2010). "An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods". SIAM Journal on Computing. 39 (7): 2970. doi:10.1137/080723491. S2CID 47262973.
^ Dall'Aglio, Marco; Mosca, Raffaele (2007). "How to allocate hard candies fairly". Mathematical Social Sciences. 54 (3): 218. CiteSeerX 10.1.1.330.2617. doi:10.1016/j.mathsocsci.2007.04.008.

[1] Asadpour, Arash; Saberi, Amin (2010-01-01). "An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods". SIAM Journal on Computing. 39 (7): 2970–2989. doi:10.1137/080723491. ISSN 0097-5397.

[2] Chakrabarty, D.; Chuzhoy, J.; Khanna, S. (2009-10-01). "On Allocating Goods to Maximize Fairness". 2009 50th Annual IEEE Symposium on Foundations of Computer Science: 107–116. doi:10.1109/FOCS.2009.51.

[g05-3] Golovin, Daniel (2005). "Max-min fair allocation of indivisible goods". CMU. Retrieved 27 August 2016.

[nrr13-4] Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation". Annals of Mathematics and Artificial Intelligence. 68 (1–3): 65–90. CiteSeerX 10.1.1.671.3497. doi:10.1007/s10472-012-9328-4.

[nnrr14-5] Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Computational complexity and approximability of social welfare optimization in multiagent resource allocation". Autonomous Agents and Multi-Agent Systems. 28 (2): 256. doi:10.1007/s10458-013-9224-2.

[bs06-6] Bansal, Nikhil; Sviridenko, Maxim (2006). "The Santa Claus problem". Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06. p. 31. doi:10.1145/1132516.1132522. ISBN 1595931341.

[bd05-7] Bezáková, Ivona; Dani, Varsha (2005). "Allocating indivisible goods". ACM SIGecom Exchanges. 5 (3): 11. CiteSeerX 10.1.1.436.18. doi:10.1145/1120680.1120683.

[as10-8] Asadpour, Arash; Saberi, Amin (2010). "An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods". SIAM Journal on Computing. 39 (7): 2970. doi:10.1137/080723491. S2CID 47262973.

[dm07-9] Dall'Aglio, Marco; Mosca, Raffaele (2007). "How to allocate hard candies fairly". Mathematical Social Sciences. 54 (3): 218. CiteSeerX 10.1.1.330.2617. doi:10.1016/j.mathsocsci.2007.04.008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
 {{Distinguish|Maximin share}}
-'''Max-min item allocation''' is a [[fair item allocation]] problem, in which 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. This problem is a generalization of [[multiway number partitioning]] (the latter corresponds to the special case in which all agents have the same valuations). Therefore, it is [[NP-hard]] in general. However, several approximation algorithms are known.
+'''Max-min item allocation''' is a [[fair item allocation]] problem, in which 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. Another term for a max-min allocation is '''egalitarian-optimal'''.
+Max-min item allocation is a generalization of [[multiway number partitioning]] (the latter corresponds to the special case in which all agents have the same valuations), which is itself a generalization of the [[partition problem]] (the latter corresponds to the special case of two agents). Therefore, it is [[NP-hard]] in general.
 Note the difference between max-min item allocation and ''[[Maximin share|maximin share item allocation]]''. The former is an optimization problem, while the latter is a satisfaction problem: the goal is to guarantee that each agent receives a value above a certain threshold.
 == Algorithms ==
-Below, ''n'' is the number of agents and ''m'' is the number of items.
+Below, ''n'' is the number of agents and ''m'' is the number of items. For agents with [[Additive utility|additive valuations]]:
-For agents with [[Additive utility|additive utility functions]]:
 * '''Asadpour and Saberi'''<ref>{{Cite journal|last=Asadpour|first=Arash|last2=Saberi|first2=Amin|date=2010-01-01|title=An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods|url=https://epubs.siam.org/doi/abs/10.1137/080723491|journal=SIAM Journal on Computing|volume=39|issue=7|pages=2970–2989|doi=10.1137/080723491|issn=0097-5397}}</ref> gave a polynomial-time algorithm that approximates the optimal solution within a factor of <math>O(\sqrt{n} \cdot \log^3 n)</math>. Their algorithm uses an iterative method for rounding a [[fractional matching]] on a [[Tree (graph theory)|tree]]. They also provide better bounds when it is allowed to exclude a small fraction of people from the problem.
-* '''Chakrabarty, Chuzoy and Khanna'''<ref>{{Cite journal|last=Chakrabarty|first=D.|last2=Chuzhoy|first2=J.|last3=Khanna|first3=S.|date=2009-10-01|title=On Allocating Goods to Maximize Fairness|url=https://ieeexplore.ieee.org/abstract/document/5438640|journal=2009 50th Annual IEEE Symposium on Foundations of Computer Science|volume=|pages=107–116|doi=10.1109/FOCS.2009.51|via=}}</ref> improved this bound to <math>O(m^{\varepsilon})</math>.
+* '''Chakrabarty, Chuzoy and Khanna'''<ref>{{Cite journal|last=Chakrabarty|first=D.|last2=Chuzhoy|first2=J.|last3=Khanna|first3=S.|date=2009-10-01|title=On Allocating Goods to Maximize Fairness|url=https://ieeexplore.ieee.org/abstract/document/5438640|journal=2009 50th Annual IEEE Symposium on Foundations of Computer Science|volume=|pages=107–116|doi=10.1109/FOCS.2009.51|via=}}</ref> improved this bound to <math>O(n^{\varepsilon})</math> , with a run-time of <math>O(n^{1/\varepsilon})</math> , for any <math>\varepsilon\in \Omega\left(\frac{\log\log n}{\log n}\right)</math>.
+*'''Golovin'''<ref name="g05">{{cite web|last1=Golovin|first1=Daniel|year=2005|title=Max-min fair allocation of indivisible goods|url=http://repository.cmu.edu/compsci/2348/|accessdate=27 August 2016|publisher=CMU}}</ref> gives an algorithm by which, for every integer <math>k</math>, a <math>(1 - 1/k)</math> fraction of the agents receive utility at least <math>OPT/k</math>. This result is obtained from rounding a suitable linear programming relaxation of the problem, and is the best possible result for this linear program.
+For agents with general cardinal valuations:
+* With two classes of goods, an <math>O(\sqrt{n})</math> approximation exists.
+* With [[Submodular set function|submodular utility functions]], an <math>(m - n + 1)</math> approximation exists.
+* Nguyen, Roos and Rothe<ref name="nrr13">{{cite journal|last1=Nguyen|first1=Trung Thanh|last2=Roos|first2=Magnus|last3=Rothe|first3=Jörg|year=2013|title=A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation|journal=Annals of Mathematics and Artificial Intelligence|volume=68|issue=1–3|pages=65–90|citeseerx=10.1.1.671.3497|doi=10.1007/s10472-012-9328-4}}</ref><ref name="nnrr14">{{cite journal|last1=Nguyen|first1=Nhan-Tam|last2=Nguyen|first2=Trung Thanh|last3=Roos|first3=Magnus|last4=Rothe|first4=Jörg|year=2013|title=Computational complexity and approximability of social welfare optimization in multiagent resource allocation|journal=Autonomous Agents and Multi-Agent Systems|volume=28|issue=2|pages=256|doi=10.1007/s10458-013-9224-2}}</ref> present some stronger hardness results.
+The special case of optimizing egalitarian welfare with additive utilities is called "the Santa Claus problem".<ref name="bs06">{{cite conference|last1=Bansal|first1=Nikhil|last2=Sviridenko|first2=Maxim|year=2006|title=Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06|pages=31|doi=10.1145/1132516.1132522|isbn=1595931341|chapter=The Santa Claus problem}}</ref> The problem is still NP-hard and cannot be approximated within a factor > 1/2, but there is an <math>O(n)</math> approximation<ref name="bd05">{{cite journal|last1=Bezáková|first1=Ivona|last2=Dani|first2=Varsha|year=2005|title=Allocating indivisible goods|journal=ACM SIGecom Exchanges|volume=5|issue=3|pages=11|citeseerx=10.1.1.436.18|doi=10.1145/1120680.1120683}}</ref> and a more complicated <math>O(\sqrt{n}\cdot \log^3{n})</math> approximation.<ref name="as10">{{cite journal|last1=Asadpour|first1=Arash|last2=Saberi|first2=Amin|year=2010|title=An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods|journal=SIAM Journal on Computing|volume=39|issue=7|pages=2970|doi=10.1137/080723491|s2cid=47262973}}</ref> See also <ref name="dm07">{{cite journal|last1=Dall'Aglio|first1=Marco|last2=Mosca|first2=Raffaele|year=2007|title=How to allocate hard candies fairly|journal=Mathematical Social Sciences|volume=54|issue=3|pages=218|citeseerx=10.1.1.330.2617|doi=10.1016/j.mathsocsci.2007.04.008}}</ref> for a branch-and-bound algorithm for two partners.
+The [[Decreasing Demand procedure]] returns an egalitarian-optimal division in an ordinal sense: it maximizes the rank, in the linear-ranking of bundles, of the agent with the lowest rank. It works for any number of agents with any ordering of bundles.
 == References ==