Journal article
APPROXIMATING THE NASH SOCIAL WELFARE WITH INDIVISIBLE ITEMS
SIAM journal on computing, v 47(3), pp 1211-1236
01 Jan 2018
Abstract
We study the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents' valuations, i.e., the Nash social welfare. This problem is known to be NP-hard, and our main result is the first efficient constant-factor approximation algorithm for this objective. We first observe that the integrality gap of the natural fractional relaxation is exponential, so we propose a different fractional allocation which implies a tighter upper bound and, after appropriate rounding, yields a good integral allocation. An interesting contribution of this work is the fractional allocation that we use. The relaxation of our problem can be solved efficiently using the Eisenberg-Gale program, whose optimal solution can be interpreted as a market equilibrium with the dual variables playing the role of item prices. Using this market-based interpretation, we define an alternative equilibrium allocation where the amount of spending that can go into any given item is bounded, thus keeping the highly priced items under-allocated and forcing the agents to spend on lower priced items. The resulting equilibrium prices reveal more information regarding how to assign items so as to obtain a good integral allocation.
Metrics
Details
- Title
- APPROXIMATING THE NASH SOCIAL WELFARE WITH INDIVISIBLE ITEMS
- Creators
- Richard Cole - NYU, Courant Inst, New York, NY 10012 USAVasilis Gkatzelis - Drexel University
- Publication Details
- SIAM journal on computing, v 47(3), pp 1211-1236
- Publisher
- Siam Publications
- Number of pages
- 26
- Grant note
- 1527568 / Division of Computing and Communication Foundations; National Science Foundation (NSF); NSF - Directorate for Computer & Information Science & Engineering (CISE) ONR PECASE award CCF-1217989; CCF-1215965; CCF-1527568 / NSF; National Science Foundation (NSF)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000437012600020
- Scopus ID
- 2-s2.0-85049447863
- Other Identifier
- 991019302020504721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied