Metraipolis › archive › dc_287e1e9396cd
Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules — arXiv:2608.15247
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.15247
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T19:08:01.877Z
- SHA-256 of the archived text
73c5ee9a7ab1f60c6efcd524859525535cf3aded11e3daae53089b01a9fc3817- Stable URL of this page
https://metraipolis.com/documento/dc_287e1e9396cd
How to cite
Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules — arXiv:2608.15247 — arXiv (en), https://arxiv.org/abs/2608.15247 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_287e1e9396cd (Metraipolis archive dc_287e1e9396cd, sha256 73c5ee9a7ab1f60c6efcd524859525535cf3aded11e3daae53089b01a9fc3817)
BibTeX
@misc{dc287e1e9396cd,
title = {Improved Metric Distortion Bounds for Deterministic Weighted-Tournament Voting Rules — arXiv:2608.15247},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.15247},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_287e1e9396cd; sha256 73c5ee9a7ab1f60c6efcd524859525535cf3aded11e3daae53089b01a9fc3817},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15247. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In metric social choice, voters and candidates lie in a common but unknown metric space, voters rank candidates by distance, and a voting rule seeks to minimize total distance to the voters. Its distortion is the worst-case approximation ratio relative to the minimum possible total distance. We study weighted-tournament rules (also known as C2 rules), which observe only the fraction of voters who prefer $a$ to $b$ for each pair of candidates $a,b$. These frequencies form a weighted tournament on candidates, a compressed representation that omits voter identities and the association of comparisons with individual voters. Prior work placed the optimal distortion of deterministic C2 rules between $3.1128$ and $3.9312$ [Charikar et al., EC 2025]. We introduce the Path-Unblanketed Set rule, a polynomial-time deterministic C2 rule with distortion at most $1+2\sqrt{2}\approx3.8284$ for every finite number of candidates. For elections with no more than six candidates, we prove with computer assistance that the distortion is at most $3.3346$. Furthermore, using an exact computer-assisted certificate, we provide a lower bound of $3.1828$ for deterministic C2 rules as a byproduct.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-18 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2608.15247 — 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-18T18:12:50.740Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).