@inproceedings{cbcf8c97301e4ac7b6bc142315a2631a,
title = "Approximating Nash Social Welfare by Matching and Local Search",
abstract = "For any >0, we give a simple, deterministic (4+)-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 + )-approximation if the ratio between the largest weight and the average weight is at most ω. We also show that the 12-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 12-EFX and a (8+)-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under 12-EFX was linear in the number of agents.",
keywords = "Approximation Algorithms, Combinatorial Optimization, Envy-freeness, Fairness, Local Search, Nash Social Welfare",
author = "Jugal Garg and Edin Husi{\'c} and Wenzheng Li and V{\'e}gh, {L{\'a}szl{\'o} A.} and Jan Vondr{\'a}k",
note = "∗JG was supported by NSF Grant CCF-1942321. EH was supported by SNSF Grant 200021 200731/1. JV and WL were supported by NSF Award CCF-2127781. LV received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement no. ScaleOpt– 757481).; 55th Annual ACM Symposium on Theory of Computing, STOC 2023 ; Conference date: 20-06-2023 Through 23-06-2023",
year = "2023",
month = jun,
day = "2",
doi = "10.1145/3564246.3585255",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "1298--1310",
editor = "Barna Saha and Servedio, {Rocco A.}",
booktitle = "STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing",
address = "United States",
}