Metraipolis › archive › dc_792bf0d98fa1
EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments — arXiv:2609.03846
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.03846
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T02:00:55.878Z
- SHA-256 of the archived text
632af457b3bb80de1b8837e2ab3cf2fe5a37cabaed8bfd72a4f1fe569216ace4- Stable URL of this page
https://metraipolis.com/documento/dc_792bf0d98fa1
How to cite
EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments — arXiv:2609.03846 — arXiv (en), https://arxiv.org/abs/2609.03846 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_792bf0d98fa1 (Metraipolis archive dc_792bf0d98fa1, sha256 632af457b3bb80de1b8837e2ab3cf2fe5a37cabaed8bfd72a4f1fe569216ace4)
BibTeX
@misc{dc792bf0d98fa1,
title = {EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments — arXiv:2609.03846},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.03846},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_792bf0d98fa1; sha256 632af457b3bb80de1b8837e2ab3cf2fe5a37cabaed8bfd72a4f1fe569216ace4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03846. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the allocation of indivisible goods among agents with identical additive valuations, focusing on envy-freeness up to one good (EF1) and Nash social welfare (NSW). Since every maximum-NSW allocation is EF1 under additive valuations, the associated threshold problem inherits the known strong NP-hardness of NSW maximization under identical additive valuations and is strongly NP-complete. We therefore focus on welfare guarantees satisfied by arbitrary EF1 allocations. Although every such allocation is known to achieve an $e^{-1/e}$-approximation to the unrestricted optimal NSW, we identify conditions yielding stronger guarantees. Under uniform valuations, every EF1 allocation is NSW-optimal. Under an $\varepsilon$-small-item condition, every EF1 allocation achieves an explicit approximation ratio $\rho_n(\varepsilon)$ satisfying $\rho_n(\varepsilon) = 1-O(\varepsilon^2)$ as $\varepsilon\to 0$ for fixed $n$. We further consider the stronger sequential requirement that $\operatorname{EF1}$ be maintained after every item assignment. For this setting, we introduce \emph{PriorityNet}, a deep reinforcement learning framework trained with Proximal Policy Optimization (PPO) and equipped with prospective $\operatorname{EF1}$ action masking, which guarantees prefix-wise $\operatorname{EF1}$ by construction. Across 3,000 test instances in each of the offline full-information and random-order online regimes ($n\in[2,20]$, $m\in[5,100]$), PriorityNet achieves mean normalized $\operatorname{NSW}$ values of $0.9911$ and $0.9701$, respectively. Relative to the offline Longest Processing Time (LPT) heuristic and the online least-valued-bundle rule, it attains instance-wise win-minus-loss rates of $+27.10\%$ and $+17.87\%$. Its aggregate welfare matches the offline LPT baseline to four decimal places and modestly improves upon the online baseline, from $0.9694$ to $0.9701$.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-04 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.03846 — 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-10-17T01:13:00.912Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).