Estimating the Nash Social Welfare for coverage and other submodular valuations
share
We study the Nash Social Welfare problem: Given n agents with valuation functions v_i:2^[m]→ℝ, partition [m] into S_1,…,S_n so as to maximize (∏_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 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.
READ FULL TEXT