# Estimating the Nash Social Welfare for coverage and other submodular valuations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2021.

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

- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)

## Abstract (arXiv)

We study the Nash Social Welfare problem: Given n agents with valuation functions vi:2[m] rightarrow mathbb R, partition [m] into S1,ldots,Sn so as to maximize (prodi=1n vi(Si))1/n. The problem has been shown to admit a constant-factor approximation for additive, budget-additive, and piecewise linear concave separable valuations; the case of submodular valuations is open. We provide a frac1e (1-frac1e)2-approximation of the em optimal value for several classes of submodular valuations: coverage, sums of matroid rank functions, and certain matching-based valuations.