On fair division for indivisible items

Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric mean of the utilities of the agents. Each good comes in multiple items or copies, and the utility of an agent diminishes as it receives more items of the same good. The utility of a bundle of items for an agent is the sum of the utilities of the items in the bundle. Each agent has a utility cap beyond which he does not value additional items. We give a polynomial time approximation algorithm that maximizes Nash social welfare up to a factor of e1/e ≈ 1.445. The computed allocation is Pareto-optimal and approximates envy-freeness up to one item up to a factor of 2 + ε.

Original languageEnglish (US)
Title of host publication38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
EditorsSumit Ganguly, Paritosh Pandya
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770934
DOIs
StatePublished - Dec 2018
Event38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 - Ahmedabad, India
Duration: Dec 11 2018Dec 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume122
ISSN (Print)1868-8969

Conference

Conference38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
CountryIndia
CityAhmedabad
Period12/11/1812/13/18

Keywords

  • Envy-free
  • Fair division
  • Indivisible goods

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'On fair division for indivisible items'. Together they form a unique fingerprint.

  • Cite this

    Chaudhury, B. R., Cheung, Y. K., Garg, J., Garg, N., Hoefer, M., & Mehlhorn, K. (2018). On fair division for indivisible items. In S. Ganguly, & P. Pandya (Eds.), 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 [25] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 122). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FSTTCS.2018.25