Metraipolis › archive › dc_7c0982d47601

Computational Aspects of Distortion — arXiv:2611.05257

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05257
License (as archived)
CC0-1.0
Archived
2026-11-04T21:46:26.069Z
SHA-256 of the archived text
e853d0b695931051fa0d4c4e4e35587b7df3bdbe8dcd99083b45687713170e39
Stable URL of this page
https://metraipolis.com/documento/dc_7c0982d47601

How to cite

Computational Aspects of Distortion — arXiv:2611.05257 — arXiv (en), https://arxiv.org/abs/2611.05257 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7c0982d47601 (Metraipolis archive dc_7c0982d47601, sha256 e853d0b695931051fa0d4c4e4e35587b7df3bdbe8dcd99083b45687713170e39)
BibTeX
@misc{dc7c0982d47601,
  title = {Computational Aspects of Distortion — arXiv:2611.05257},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05257},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7c0982d47601; sha256 e853d0b695931051fa0d4c4e4e35587b7df3bdbe8dcd99083b45687713170e39},
  year = {2026}
}

Archived text

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

The distortion framework in social choice theory allows quantifying the efficiency of (randomized) selection of an alternative based on the preferences of a set of agents. We make two fundamental contributions to this framework. First, we develop a linear-programming-based algorithm for computing the optimal randomized decision on a given instance, which is simpler and faster than the state-of-the-art solutions. For practitioners who may prefer to deploy a classical decision-making rule over the aforementioned optimal rule, we develop an algorithm based on non-convex quadratic programming for computing the exact distortion of any (and the best) randomized positional scoring rule. For a small number of alternatives, we find that the exact distortion bounds are significantly better than the asymptotic upper bounds established in prior literature and lead to different recommendations on which rules to use. These results rely on a novel characterization of the instances yielding the worst distortion, which may be of independent interest.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.05257 — 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-11-04T21:37:19.382Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).