Estimating the Nash Social Welfare for coverage and other submodular valuations

We study the Nash Social Welfare problem: Given n agents with valuation functions vi : 2 [m] → R+, partition [m] into S1, . . . , Sn so as to maximize ( n i=1 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 1 e (1 -1 e ) 2 -approximation of the optimal value for several classes of submodular valuations: coverage, sums of matroid rank functions, and certain matching-based valuations.