Approximating Maximin Share Allocations

Authors Jugal Garg, Peter McGlaughlin, Setareh Taki



PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.20.pdf
  • Filesize: 388 kB
  • 11 pages

Document Identifiers

Author Details

Jugal Garg
Peter McGlaughlin
Setareh Taki

Cite AsGet BibTex

Jugal Garg, Peter McGlaughlin, and Setareh Taki. Approximating Maximin Share Allocations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 20:1-20:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.SOSA.2019.20

Abstract

We study the problem of fair allocation of M indivisible items among N agents using the popular notion of maximin share as our measure of fairness. The maximin share of an agent is the largest value she can guarantee herself if she is allowed to choose a partition of the items into N bundles (one for each agent), on the condition that she receives her least preferred bundle. A maximin share allocation provides each agent a bundle worth at least their maximin share. While it is known that such an allocation need not exist [Procaccia and Wang, 2014; Kurokawa et al., 2016], a series of work [Procaccia and Wang, 2014; David Kurokawa et al., 2018; Amanatidis et al., 2017; Barman and Krishna Murthy, 2017] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times their maximin share. Recently, [Ghodsi et al., 2018] improved the approximation guarantee to 3/4. Prior works utilize intricate algorithms, with an exception of [Barman and Krishna Murthy, 2017] which is a simple greedy solution but relies on sophisticated analysis techniques. In this paper, we propose an alternative 2/3 maximin share approximation which offers both a simple algorithm and straightforward analysis. In contrast to other algorithms, our approach allows for a simple and intuitive understanding of why it works.
Keywords
  • Fair division
  • Maximin share
  • Approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms (TALG), 13(4):52, 2017. Google Scholar
  2. Siddharth Barman and Sanath Kumar Krishna Murthy. Approximation algorithms for maximin fair division. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 647-664. ACM, 2017. Google Scholar
  3. Sylvain Bouveret and Michel Lemaître. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2):259-290, 2016. Google Scholar
  4. Sylvain Bouveret and Michel Lemaître. Efficiency and sequenceability in fair division of indivisible goods with additive preferences. arXiv preprint arXiv:1604.01734, 2016. Google Scholar
  5. Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011. Google Scholar
  6. Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvement and generalization. In EC, 2018. Google Scholar
  7. David Kurokawa, Ariel D Procaccia, and Junxing Wang. When can the maximin share guarantee be guaranteed? In AAAI, volume 16, pages 523-529, 2016. Google Scholar
  8. David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair Enough: Guaranteeing Approximate Maximin Shares. J. ACM, 65(2):8:1-8:27, 2018. Google Scholar
  9. Ariel D Procaccia and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 675-692. ACM, 2014. Google Scholar
  10. Hugo Steinhaus. The problem of fair division. Econometrica, 16:101-104, 1948. Google Scholar
  11. Gerhard J Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4):149-154, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail