Estimating the Nash Social Welfare for coverage and other submodular valuations

Abstract

We study the Nash Social Welfare problem: Given $n$ agents with valuation functions $v_i:2^{[m]}\to \mathbb{R}$, partition $[m]$ into $S_1,\dots ,S_n$ so as to maximize $({\prod }_{i=1}^n{v}_i(S_i){)}^{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 $\frac{1}{e}(1-\frac{1}{e}{)}^2$-approximation of the {\em optimal value} for several classes of submodular valuations: coverage, sums of matroid rank functions, and certain matching-based valuations.