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 -