License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.25
URN: urn:nbn:de:0030-drops-99242
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9924/
Go to the corresponding LIPIcs Volume Portal

Chaudhury, Bhaskar Ray ; Cheung, Yun Kuen ; Garg, Jugal ; Garg, Naveen ; Hoefer, Martin ; Mehlhorn, Kurt

On Fair Division for Indivisible Items

pdf-format:
LIPIcs-FSTTCS-2018-25.pdf (0.6 MB)

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}} ~~ 1.445. The computed allocation is Pareto-optimal and approximates envy-freeness up to one item up to a factor of 2 + epsilon.

BibTeX - Entry

@InProceedings{chaudhury_et_al:LIPIcs:2018:9924,
  author =	{Bhaskar Ray Chaudhury and Yun Kuen Cheung and Jugal Garg and Naveen Garg and Martin Hoefer and Kurt Mehlhorn},
  title =	{{On Fair Division for Indivisible Items}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9924},
  URN =		{urn:nbn:de:0030-drops-99242},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.25},
  annote =	{Keywords: Fair Division, Indivisible Goods, Envy-Free}
}

Keywords: Fair Division, Indivisible Goods, Envy-Free
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI