TY - GEN

T1 - Approximating Nash social welfare under rado valuations

AU - Garg, Jugal

AU - Husić, Edin

AU - Végh, László A.

N1 - Funding Information:
∗Supported by NSF Grant CCF-1942321 (CAREER). †Supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. ScaleOpt–757481).
Publisher Copyright:
© 2021 ACM.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to n agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of the agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. Subsequent work has obtained constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and O(n)-approximation algorithms for subadditive valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.

AB - We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to n agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of the agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. Subsequent work has obtained constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and O(n)-approximation algorithms for subadditive valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.

KW - approximation algorithm

KW - Nash social welfare

KW - Rado valuations

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

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

U2 - 10.1145/3406325.3451031

DO - 10.1145/3406325.3451031

M3 - Conference contribution

AN - SCOPUS:85108141555

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1412

EP - 1425

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -