Yuda Feng ; Shi Li - A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

theoretics:14642 - TheoretiCS, August 14, 2025, Volume 4 - https://doi.org/10.46298/theoretics.25.17
A Note on Approximating Weighted Nash Social Welfare with Additive ValuationsArticle

Authors: Yuda Feng ; Shi Li

    We give the first $O(1)$-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is $e^{1/e} + ε\approx 1.445 + ε$, which matches the best known approximation ratio for the unweighted case. Both our algorithm and analysis are simple. We solve a natural configuration LP for the problem, and obtain the allocation of items to agents using a randomized version of the Shmoys-Tardos rounding algorithm developed for unrelated machine scheduling problems. In the analysis, we show that the approximation ratio of the algorithm is at most the worst gap between the Nash social welfare of the optimum allocation and that of an EF1 allocation, for an unweighted Nash Social Welfare instance with identical additive valuations. This was shown to be at most $e^{1/e} \approx 1.445$ by Barman, Krishnamurthy and Vaish, leading to our approximation ratio.


    Volume: Volume 4
    Published on: August 14, 2025
    Accepted on: June 9, 2025
    Submitted on: October 30, 2024
    Keywords: Computer Science and Game Theory,Data Structures and Algorithms