Metraipolis › archive › dc_6d3be282aa40

Pessimal Elections for Approximately Dominating Sets — arXiv:2608.06872

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.06872
License (as archived)
CC0-1.0
Archived
2026-10-19T09:50:08.973Z
SHA-256 of the archived text
555386ae5bbbe4741a95cdb7f2a402f633e72694aec5099dc39303543e261e56
Stable URL of this page
https://metraipolis.com/documento/dc_6d3be282aa40

How to cite

Pessimal Elections for Approximately Dominating Sets — arXiv:2608.06872 — arXiv (en), https://arxiv.org/abs/2608.06872 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6d3be282aa40 (Metraipolis archive dc_6d3be282aa40, sha256 555386ae5bbbe4741a95cdb7f2a402f633e72694aec5099dc39303543e261e56)
BibTeX
@misc{dc6d3be282aa40,
  title = {Pessimal Elections for Approximately Dominating Sets — arXiv:2608.06872},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.06872},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6d3be282aa40; sha256 555386ae5bbbe4741a95cdb7f2a402f633e72694aec5099dc39303543e261e56},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06872. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Condorcet's paradox is a foundational result in social choice theory, showing that no matter which candidate wins an election, a majority of voters may prefer some losing candidate. Worse still, even if the election can choose a committee of $k$ winners, some loser may beat every winner in a majority vote. Recent work showed that this obstruction can be sidestepped by relaxing the majority threshold. For all $\varepsilon > 0$, any election can select a committee of $O(1/\varepsilon^2)$ winners such that no loser is preferred to every winner by $\frac12 + \varepsilon$ fraction of voters. We present a simple construction, found by GPT-5.6 Sol Ultra, which proves that this result is tight up to a constant factor.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-10 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.06872 — 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-19T09:49:04.941Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).