IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v46y2021i3p1038-1053.html
   My bibliography  Save this article

Fair Allocation of Indivisible Goods: Improvement

Author

Listed:
  • Mohammad Ghodsi

    (Department of Computer Engineering, Sharif University of Technology, Tehran 11365-11155, Iran)

  • Mohammad Taghi Hajiaghayi

    (School of Computer Science, Institute for Research in Fundamental Sciences, Tehran 19538-3351, Iran)

  • Masoud Seddighin

    (Department of Computer Engineering, Sharif University of Technology, Tehran 11365-11155, Iran)

  • Saeed Seddighin

    (School of Computer Science, Institute for Research in Fundamental Sciences, Tehran 19538-3351, Iran)

  • Hadi Yami

    (School of Computer Science, Institute for Research in Fundamental Sciences, Tehran 19538-3351, Iran)

Abstract

We study the problem of fair allocation for indivisible goods. We use the maximin share paradigm introduced by Budish [Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom . 119(6):1061–1103.] as a measure of fairness. Kurokawa et al. [Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8.] were the first to investigate this fundamental problem in the additive setting. They showed that in delicately constructed examples, not everyone can obtain a utility of at least her maximin value. They mitigated this impossibility result with a beautiful observation: no matter how the utility functions are made, we always can allocate the items to the agents to guarantee each agent’s utility is at least 2/3 of her maximin value. They left open whether this bound can be improved. Our main contribution answers this question in the affirmative. We improve their approximation result to a 3/4 factor guarantee.

Suggested Citation

  • Mohammad Ghodsi & Mohammad Taghi Hajiaghayi & Masoud Seddighin & Saeed Seddighin & Hadi Yami, 2021. "Fair Allocation of Indivisible Goods: Improvement," Mathematics of Operations Research, INFORMS, vol. 46(3), pages 1038-1053, August.
    • Handle: RePEc:inm:ormoor:v:46:y:2021:i:3:p:1038-1053
    DOI: 10.1287/moor.2020.1096
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2020.1096
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2020.1096?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:46:y:2021:i:3:p:1038-1053. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.