Approximating Nash Social Welfare by Matching and Local Search
share
For any ε>0, we give a simple, deterministic (6+ε)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents' valuations, and give an (ω + 2 +ε) e-approximation if the ratio between the largest weight and the average weight is at most ω. We also show that the 1/2-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time which is both 1/2-EFX and a (12+ε)-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under 1/2-EFX was linear in the number of agents.
READ FULL TEXT