The price to pay for forgoing normalization in fair division of indivisible goods

We study the complexity of fair division of indivisible goods and consider settings where agents can have nonzero utility for the empty bundle. This is a deviation from a common normalization assumption in the literature, and we show that this inconspicuous change can lead to an increase in complexi...

Full description

Saved in:
Bibliographic Details
Published in:Annals of mathematics and artificial intelligence 2020-07, Vol.88 (7), p.817-832
Main Authors: Lange, Pascal, Nguyen, Nhan-Tam, Rothe, Jörg
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Backup software
Complex Systems
Complexity
Computer Science
Egalitarianism
Elitism
Mathematics
Multiplication & division
Optimization
Polynomials
Utility functions
Valuation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the complexity of fair division of indivisible goods and consider settings where agents can have nonzero utility for the empty bundle. This is a deviation from a common normalization assumption in the literature, and we show that this inconspicuous change can lead to an increase in complexity: In particular, while an allocation maximizing social welfare by the Nash product is known to be easy to detect in the normalized setting whenever there are as many agents as there are resources, without normalization it can no longer be found in polynomial time, unless P = NP. The same statement also holds for egalitarian social welfare. Moreover, we show that it is NP-complete to decide whether there is an allocation whose Nash product social welfare is above a certain threshold if the number of resources is a multiple of the number of agents. Finally, we consider elitist social welfare and prove that the increase in expressive power by allowing negative coefficients again yields NP-completeness.
ISSN:1012-2443
1573-7470
DOI:10.1007/s10472-019-09659-1