English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

On Fair Division of Indivisible Items

MPS-Authors
/persons/resource/persons225687

Ray Chaudhury,  Bhaskar
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons202384

Cheung,  Yun Kuen
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44628

Hoefer,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1805.06232.pdf
(Preprint), 579KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Ray Chaudhury, B., Cheung, Y. K., Garg, J., Garg, N., Hoefer, M., & Mehlhorn, K. (2018). On Fair Division of Indivisible Items. Retrieved from http://arxiv.org/abs/1805.06232.


Cite as: http://hdl.handle.net/21.11116/0000-0002-05E7-4
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 $e^{1/e} \approx 1.445$.