Fair Allocation of Indivisible Goods: Improvement

Mohammad Ghodsi (), Mohammad Taghi Hajiaghayi (), Masoud Seddighin (), Saeed Seddighin () and Hadi Yami ()
Additional contact information
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

Mathematics of Operations Research, 2021, vol. 46, issue 3, 1038-1053

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.

Keywords: Primary: 91B32; secondary: 68W25; Primary: game theory/economics/social and behavioral sciences; fairness; maximin share; approximation (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1096 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:3:p:1038-1053

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().