> Details

Chaudhury, Bhaskar Ray [Author]; Cheung, Yun Kuen [Author]; Garg, Jugal [Author]; Garg, Naveen [Author]; Hoefer, Martin [Author]; Mehlhorn, Kurt [Author] ; Bhaskar Ray Chaudhury and Yun Kuen Cheung and Jugal Garg and Naveen Garg and Martin Hoefer and Kurt Mehlhorn [Contributor]

On Fair Division for Indivisible Items

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: E-Article; Text; Electronic Conference Proceeding
  • Title: On Fair Division for Indivisible Items
  • Contributor: Chaudhury, Bhaskar Ray [Author]; Cheung, Yun Kuen [Author]; Garg, Jugal [Author]; Garg, Naveen [Author]; Hoefer, Martin [Author]; Mehlhorn, Kurt [Author]
  • imprint: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.25
  • Keywords: Fair Division ; Envy-Free ; Indivisible Goods
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access