TY - GEN

T1 - Approximating the Nash social welfare with budget-additive valuations

AU - Garg, Jugal

AU - Hoefer, Martin

AU - Mehlhorn, Kurt

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every " > 0, our algorithm obtains a (2:404 + ϵ)-approximation in time polynomial in the input size and 1=". Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [17]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.

AB - We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of submodular functions. They have attracted a lot of research interest in recent years due to many interesting applications. For every " > 0, our algorithm obtains a (2:404 + ϵ)-approximation in time polynomial in the input size and 1=". Our algorithm relies on rounding an approximate equilibrium in a linear Fisher market where sellers have earning limits (upper bounds on the amount of money they want to earn) and buyers have utility limits (upper bounds on the amount of utility they want to achieve). In contrast to markets with either earning or utility limits, these markets have not been studied before. They turn out to have fundamentally different properties. Although the existence of equilibria is not guaranteed, we show that the market instances arising from the Nash social welfare problem always have an equilibrium. Further, we show that the set of equilibria is not convex, answering a question of [17]. We design an FPTAS to compute an approximate equilibrium, a result that may be of independent interest.

UR - http://www.scopus.com/inward/record.url?scp=85045582881&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045582881&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.150

DO - 10.1137/1.9781611975031.150

M3 - Conference contribution

AN - SCOPUS:85045582881

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2326

EP - 2340

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -