Metraipolis › archive › dc_600508da388c
Sequential Phragmén Guarantees 2-Approximate Core Stability — arXiv:2609.29646
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.29646
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T04:52:13.696Z
- SHA-256 of the archived text
2107e03afb17b46b00ea440d2ee35f530b0c336eb9243ffdda505b590692c555- Stable URL of this page
https://metraipolis.com/documento/dc_600508da388c
How to cite
Sequential Phragmén Guarantees 2-Approximate Core Stability — arXiv:2609.29646 — arXiv (en), https://arxiv.org/abs/2609.29646 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_600508da388c (Metraipolis archive dc_600508da388c, sha256 2107e03afb17b46b00ea440d2ee35f530b0c336eb9243ffdda505b590692c555)
BibTeX
@misc{dc600508da388c,
title = {Sequential Phragmén Guarantees 2-Approximate Core Stability — arXiv:2609.29646},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.29646},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_600508da388c; sha256 2107e03afb17b46b00ea440d2ee35f530b0c336eb9243ffdda505b590692c555},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29646. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In an approval-based committee election, a committee of size $k$ is selected from a set of candidates to represent voters of total weight $n$, each of whom has positive weight and approves a subset of the candidates. A size-$k$ committee is $\lambda$-stable if, for every nonempty subset $T$ of candidates, the total weight of voters who strictly prefer $T$ is less than $\lambda$ times the proportional share $n|T|/k$. Whether there exists a committee that is exactly stable, corresponding to $\lambda=1$, remains a major open problem in approval-based committee voting. Thus, a natural objective is to identify small values of $\lambda>1$ for which $\lambda$-stability can always be guaranteed. We prove that weighted sequential Phragmén, a classical and natural rule, always returns a $2$-stable committee of size $k$. Since the $\lambda$-core is the set of all $\lambda$-stable committees, our result implies that the $2$-core is always nonempty. This improves upon the previously best-known guarantee, due to Gao, Sun, and Vondrák~[EC~2026], that a $3.651$-stable committee always exists. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-25 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.29646 — 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-08T04:29:42.575Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).