Max-min item allocation

From HandWiki

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 item allocation.

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.

The special case in which the value of each item j to each agent is either 0 or some constant vj is called the santa claus problem: santa claus has a fixed set of gifts, and wants to allocate them among children such that the least-happy child is as happy as possible.

Algorithms

Below, n is the number of agents and m is the number of items.

For the special case of the santa claus problem:

  • Bansal and Sviridenko[1] gave a [math]\displaystyle{ O(\log{\log{n}}/\log{\log{\log{n}}}) }[/math]-approximation algorithm, based on rounding a linear program.
  • Feige[2] proved that a polynomial-time constant-factor approximation algorithm exists, but the proof used Lovász local lemma and was non-constructive.
  • Asadpour, Feige and Saberi[3] gave an actual constant-factor approximation algorithm, using hypergraph matching. They could not prove that it converges in a finite number of steps.
  • Annamalai, Kalaitzis and Svensson[4] gave a polynomial-time 13-approximation algorithm.

For the general case, for agents with additive valuations:

  • Bezakova and Dani[5] gave a [math]\displaystyle{ (m - n + 1) }[/math] -approximation algorithm.
  • Asadpour and Saberi[6] gave a [math]\displaystyle{ O(\sqrt{n} \cdot \log^3 n) }[/math]-approximation algorithm. 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[7] gave an [math]\displaystyle{ O(m^{\varepsilon}) }[/math] -approximation algorithm with a run-time of [math]\displaystyle{ O(m^{1/\varepsilon}) }[/math] , for any [math]\displaystyle{ \varepsilon\in \Omega\left(\frac{\log\log m}{\log m}\right) }[/math] . For the special case in which every item has nonzero utility for at most two agents, they gave a 2-factor approximation algorithm, and proved that it is hard to approximate to any better factor.
  • Golovin[8] gave an algorithm by which, for every integer [math]\displaystyle{ k }[/math], a [math]\displaystyle{ (1 - 1/k) }[/math] fraction of the agents receive utility at least [math]\displaystyle{ 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. He also gave an [math]\displaystyle{ O(\sqrt{n}) }[/math] -approximation algorithm for the special case with two classes of goods.
  • Dall'Aglio and Mosca[9] gave an exact, branch-and-bound algorithm for two agents, based on an adaptation of the Adjusted winner procedure.

For agents with submodular utility functions:

  • Golovin[8] gave an [math]\displaystyle{ (m - n + 1) }[/math] -approximation algorithm, and some inapproximability results for general utility functions.
  • Goemans, Harvey, Iwata and Mirrkoni[10] give a [math]\displaystyle{ O(\sqrt{m} \cdot n^{1/4} \cdot \log n\cdot \log^{3/2} m) }[/math]-approximation algorithm
  • Nguyen, Roos and Rothe[11][12] present some stronger hardness results.

For general ordinal ranking on subsets of items:

  • 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

  1. ↑ Bansal, Nikhil; Sviridenko, Maxim (2006). "Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06". pp. 31. doi:10.1145/1132516.1132522. ISBN 1595931341. 
  2. ↑ Feige, Uriel (2008-01-20). "On allocations that maximize fairness". Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. SODA '08 (San Francisco, California: Society for Industrial and Applied Mathematics): 287–293. https://dl.acm.org/doi/abs/10.5555/1347082.1347114. 
  3. ↑ Asadpour, Arash; Feige, Uriel; Saberi, Amin (2008). Goel, Ashish; Jansen, Klaus; Rolim, José D. P. et al.. eds. "Santa Claus Meets Hypergraph Matchings" (in en). Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science (Berlin, Heidelberg: Springer): 10–20. doi:10.1007/978-3-540-85363-3_2. ISBN 978-3-540-85363-3. https://link.springer.com/chapter/10.1007/978-3-540-85363-3_2. 
  4. ↑ Annamalai, Chidambaram; Kalaitzis, Christos; Svensson, Ola (2017-05-26). "Combinatorial Algorithm for Restricted Max-Min Fair Allocation". ACM Transactions on Algorithms 13 (3): 37:1–37:28. doi:10.1145/3070694. ISSN 1549-6325. https://doi.org/10.1145/3070694. 
  5. ↑ Bezáková, Ivona; Dani, Varsha (2005). "Allocating indivisible goods". ACM SIGecom Exchanges 5 (3): 11. doi:10.1145/1120680.1120683. 
  6. ↑ 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. https://epubs.siam.org/doi/abs/10.1137/080723491. 
  7. ↑ 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. https://ieeexplore.ieee.org/abstract/document/5438640. 
  8. ↑ 8.0 8.1 Golovin, Daniel (2005). "Max-min fair allocation of indivisible goods". CMU. http://repository.cmu.edu/compsci/2348/. 
  9. ↑ Dall'Aglio, Marco; Mosca, Raffaele (2007). "How to allocate hard candies fairly". Mathematical Social Sciences 54 (3): 218. doi:10.1016/j.mathsocsci.2007.04.008. 
  10. ↑ Goemans, Michel X.; Harvey, Nicholas J. A.; Iwata, Satoru; Mirrokni, Vahab (2009-01-04), "Approximating Submodular Functions Everywhere", Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings (Society for Industrial and Applied Mathematics): pp. 535–544, doi:10.1137/1.9781611973068.59, ISBN 978-0-89871-680-1, https://epubs.siam.org/doi/abs/10.1137/1.9781611973068.59, retrieved 2020-11-22 
  11. ↑ 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. doi:10.1007/s10472-012-9328-4. 
  12. ↑ 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. 




Retrieved from "https://handwiki.org/wiki/index.php?title=Max-min_item_allocation&oldid=127132"