Fair Allocation of Indivisible Goods: Improvement

• 成果类型: Article
• 署名作者: Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi
• 署名单位: Sharif University of Technology; Institute for Research in Fundamental Sciences IPM; University System of Maryland; University of Maryland College Park
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1096
• 发表日期: 2021
• 页码: 1038-1053

摘要

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.