@inproceedings{cbaa3b350dd3415d9ad35377ea8fce52,
title = "On fair division for indivisible items",
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 + ε.",
keywords = "Envy-free, Fair division, Indivisible goods",
author = "Chaudhury, {Bhaskar Ray} and Cheung, {Yun Kuen} and Jugal Garg and Naveen Garg and Martin Hoefer and Kurt Mehlhorn",
note = "Publisher Copyright: {\textcopyright} Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn.; 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 ; Conference date: 11-12-2018 Through 13-12-2018",
year = "2018",
month = dec,
doi = "10.4230/LIPIcs.FSTTCS.2018.25",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Sumit Ganguly and Paritosh Pandya",
booktitle = "38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018",
}