English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

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;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
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: https://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$.