Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911248274161664 |
|---|---|
| author | Feng, Yuda Hu, Yang Li, Shi Zhang, Ruilong |
| author_facet | Feng, Yuda Hu, Yang Li, Shi Zhang, Ruilong |
| contents | We study the problem of assigning items to agents so as to maximize the \emph{weighted} Nash Social Welfare (NSW) under submodular valuations. The best-known result for the problem is an $O(nw_{\max})$-approximation due to Garg, Husic, Li, Végh, and Vondrák~[STOC 2023], where $w_{\max}$ is the maximum weight over all agents. Obtaining a constant approximation algorithm is an open problem in the field that has recently attracted considerable attention.
We give the first such algorithm for the problem, thus solving the open problem in the affirmative. Our algorithm is based on the natural Configuration LP for the problem, which was introduced recently by Feng and Li~[ICALP 2024] for the additive valuation case. Our rounding algorithm is similar to that of Li~[SODA 2025] developed for the unrelated machine scheduling problem to minimize weighted completion time. Roughly speaking, we designate the largest item in each configuration as a large item and the remaining items as small items. So, every agent gets precisely 1 fractional large item in the configuration LP solution. With the rounding algorithm in Li~[SODA 2025], we can ensure that in the obtained solution, every agent gets precisely 1 large item, and the assignments of small items are negatively correlated. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02942 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations Feng, Yuda Hu, Yang Li, Shi Zhang, Ruilong Computer Science and Game Theory Data Structures and Algorithms We study the problem of assigning items to agents so as to maximize the \emph{weighted} Nash Social Welfare (NSW) under submodular valuations. The best-known result for the problem is an $O(nw_{\max})$-approximation due to Garg, Husic, Li, Végh, and Vondrák~[STOC 2023], where $w_{\max}$ is the maximum weight over all agents. Obtaining a constant approximation algorithm is an open problem in the field that has recently attracted considerable attention. We give the first such algorithm for the problem, thus solving the open problem in the affirmative. Our algorithm is based on the natural Configuration LP for the problem, which was introduced recently by Feng and Li~[ICALP 2024] for the additive valuation case. Our rounding algorithm is similar to that of Li~[SODA 2025] developed for the unrelated machine scheduling problem to minimize weighted completion time. Roughly speaking, we designate the largest item in each configuration as a large item and the remaining items as small items. So, every agent gets precisely 1 fractional large item in the configuration LP solution. With the rounding algorithm in Li~[SODA 2025], we can ensure that in the obtained solution, every agent gets precisely 1 large item, and the assignments of small items are negatively correlated. |
| title | Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.02942 |