Approximating Nash Social Welfare under Rado Valuations
Abstract
The Nash social welfare problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. The problem is NP-complete already for additive valuations, where constant-factor approximations have been obtained using diverse approaches, such as market relaxation, real stable polynomials, and price envy-freeness. We give a constant-factor approximation for the case when the agents have Rado valuations, a rich subclass of submodular valuations that include assignment (OXS) valuations and weighted matroid rank functions. The algorithm is based on a new mixed integer programming relaxation approach, combining a matching with a fractional solution to a convex program. This is joint work with Jugal Garg and Edin Husić. Subsequent to our paper, this approach was further strengthened by Li and Vondrák to obtain a constant-factor approximation for submodular valuations.
Bio
László Végh is a professor in the Mathematics Department at the London School of Economics. He received his Ph.D. from Eötvös University, Budapest in 2010, and was a postdoc at Georgia Tech in 2011-12. His research addresses fundamental questions in algorithms and optimization. He received the best student paper award at STOC in 2010 for a paper on connectivity augmentation, and a STOC best paper award in 2018 for a paper on the asymmetric travelling salesman. He is an associate editor at journals including Operations Research, Mathematical Programming, and Mathematics of Operations Research, and has served on the program committee for a number of conferences, including FOCS, SODA, and IPCO. His work is supported by an European Research Council Grant.
