# Item

ITEM ACTIONSEXPORT

Released

Paper

#### On Fair Division of Indivisible Items

##### MPS-Authors

##### 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$.