Metraipolis › archive › dc_877bf0a200fe
Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations — arXiv:2611.05229
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05229
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T19:07:44.639Z
- SHA-256 of the archived text
1a0cc6da8dd769a0237a69c8df3aecd13a7e683c4b8c5cfbe26344820fa7530e- Stable URL of this page
https://metraipolis.com/documento/dc_877bf0a200fe
How to cite
Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations — arXiv:2611.05229 — arXiv (en), https://arxiv.org/abs/2611.05229 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_877bf0a200fe (Metraipolis archive dc_877bf0a200fe, sha256 1a0cc6da8dd769a0237a69c8df3aecd13a7e683c4b8c5cfbe26344820fa7530e)
BibTeX
@misc{dc877bf0a200fe,
title = {Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations — arXiv:2611.05229},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05229},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_877bf0a200fe; sha256 1a0cc6da8dd769a0237a69c8df3aecd13a7e683c4b8c5cfbe26344820fa7530e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05229. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study two fairness objectives for allocating $m$ indivisible items among $n$ agents with subadditive valuations: the max-min objective, also known as the Santa Claus problem, which maximizes the smallest value of an agent, and the weighted Nash social welfare, which maximizes the weighted geometric mean of the agents' values. For the max-min allocation problem, we give a randomized polynomial-time $O(\sqrt n)$-approximation algorithm for subadditive valuations with demand queries, improving the $2n-1$ bound of Khot and Ponnuswami. For additive valuations and for submodular valuations with value queries, we give simpler $O(\sqrt n)$-approximation algorithms. For additive valuations, this improves the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan. For these two classes, $O(m^\varepsilon)$-approximation algorithms are also known for every constant $\varepsilon>0$. Our ratios depend only on $n$ and match, up to constants, the $\Omega(\sqrt n)$ integrality gap of the configuration LP. For the weighted Nash social welfare problem with subadditive valuations and demand queries, we give an $O(\Gamma(w))$-approximation algorithm, where $\Gamma(w)=\exp\bigl((\ln n-H(w))/2\bigr)$ and $H(w)$ is the entropy of the weight vector $w$. The factor $\Gamma(w)$ equals $1$ for equal weights and is at most $\sqrt n$ for all weights. We show that this ratio is tight for algorithms analyzed against the configuration LP: for every weight vector, the configuration LP has an integrality gap of $\Theta(\Gamma(w))$, even for XOS valuations, and this gap is $\Omega(\sqrt n)$ when one agent has almost all the weight. For submodular valuations, the configuration LP has a constant integrality gap for all weights.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05229 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:40:52.485Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).