Approximating Nash Social Welfare by Matching and Local Search
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912985368231936 |
|---|---|
| author | Garg, Jugal Husić, Edin Li, Wenzheng Végh, László A. Vondrák, Jan |
| author_facet | Garg, Jugal Husić, Edin Li, Wenzheng Végh, László A. Vondrák, Jan |
| contents | For any $\varepsilon>0$, we give a simple, deterministic $(4+\varepsilon)$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. 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 $e (ω+ 2 + \varepsilon)$-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 that is both $1/2$-EFX and a $(8+\varepsilon)$-approximation to the symmetric NSW problem under submodular valuations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_03883 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Approximating Nash Social Welfare by Matching and Local Search Garg, Jugal Husić, Edin Li, Wenzheng Végh, László A. Vondrák, Jan Computer Science and Game Theory Data Structures and Algorithms For any $\varepsilon>0$, we give a simple, deterministic $(4+\varepsilon)$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. 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 $e (ω+ 2 + \varepsilon)$-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 that is both $1/2$-EFX and a $(8+\varepsilon)$-approximation to the symmetric NSW problem under submodular valuations. |
| title | Approximating Nash Social Welfare by Matching and Local Search |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.03883 |