Metraipolis › archive › dc_ebce65444ecf

A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls — arXiv:2608.28340

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.28340
License (as archived): CC0-1.0
Archived: 2026-10-17T10:57:09.531Z
SHA-256 of the archived text: 25295eb3a034bde673304bd128f8ff65e4bf341b7e3674a4bc53a7396868daea
Stable URL of this page: https://metraipolis.com/documento/dc_ebce65444ecf

How to cite

A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls — arXiv:2608.28340 — arXiv (en), https://arxiv.org/abs/2608.28340 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ebce65444ecf (Metraipolis archive dc_ebce65444ecf, sha256 25295eb3a034bde673304bd128f8ff65e4bf341b7e3674a4bc53a7396868daea)

BibTeX

@misc{dcebce65444ecf,
  title = {A Constant Metric Distortion Protocol for Approval Voting Given Plurality Polls — arXiv:2608.28340},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.28340},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ebce65444ecf; sha256 25295eb3a034bde673304bd128f8ff65e4bf341b7e3674a4bc53a7396868daea},
  year = {2026}
}

Archived text

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

Approval voting is a simple and well-regarded voting rule: voters submit approval ballots (subsets of the candidates) and the candidate receiving the most approvals wins. One major limitation of approval voting is that it is not clear which candidates voters should approve if they have an underlying strict order over the candidates. In this paper, we initiate the study of approval voting under a simple kind of information: plurality polls. That is, we assume that for each candidate we know the share of voters who rank this candidate as their top choice. Using these plurality polls, we suggest a simple protocol parameterized by a fraction $k \in (0,1)$: every voter should approve the smallest prefix of their preference list containing the first choices of at least a fraction $k$ of the voters. We evaluate this protocol via the framework of metric distortion and show that for the optimal choice of $k$, this rule achieves a metric distortion of $2 + \sqrt{5} \simeq 4.236$. The proof techniques we use for this statement also show that the Bucklin voting rule has a metric distortion of at most $5$. Finally, we evaluate the robustness of our protocol to noise and show that the upper bounds obtained for our protocol are tight.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-31 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2608.28340 — 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-17T10:48:51.064Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).