Approximating the Nash Social Welfare with Indivisible Items
Authors:
- Richard ColeRCRichard Cole
- Vasilis GkatzelisVGVasilis Gkatzelis
- 1 January 2018
- journal article
- conference paper
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 47 (3) , 1211-1236
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 i...Keywords
Funding Information
- Office of Naval Research
- National Science Foundation (CCF-1217989, CCF-1215965, CCF-1527568)
This publication has 30 references indexed in Scilit:
- The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal IncomesJournal of Political Economy, 2011
- Compactly representing utility functions using weighted goals and the max aggregatorArtificial Intelligence, 2010
- Market equilibrium via a primal--dual algorithm for a convex programJournal of the ACM, 2008
- Allocating indivisible goodsACM SIGecom Exchanges, 2005
- Charging and rate control for elastic trafficEuropean Transactions on Telecommunications, 1997
- The Efficient Allocation of Individuals to PositionsJournal of Political Economy, 1979
- The Nash Social Welfare FunctionEconometrica, 1979
- Equity, envy, and efficiencyJournal of Economic Theory, 1974
- Consensus of Subjective Probabilities: The Pari-Mutuel MethodThe Annals of Mathematical Statistics, 1959
- The Bargaining ProblemEconometrica, 1950