# A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

arXiv: https://arxiv.org/abs/2404.15607 · HTML: https://mlsanity.com/paper/2404.15607/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2024.

## Built on by (most cited first, 1 of 1)

- [EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments](https://mlsanity.com/paper/2609.03846/) (2026)

## Abstract (arXiv)

We give the first O(1)-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is e1/e + ε ≈ 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 e1/e ≈ 1.445 by Barman, Krishnamurthy and Vaish, leading to our approximation ratio.