Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

On Fair Division of Indivisible Items

MPG-Autoren
/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;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:1805.06232.pdf
(Preprint), 579KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: https://hdl.handle.net/21.11116/0000-0002-05E7-4
Zusammenfassung
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$.