mlsanityData to 14 Oct 2026

Improving Randomized Metric Distortion to 2.1441

arXiv 2608.29308 ↗First posted 29 Aug 2026cs.GT cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

In metric social choice, voters rank candidates by their distances in an unknown metric space. A voting rule uses these rankings to select a candidate or a lottery over candidates, aiming to minimize the average distance to voters. Distortion measures the worst-case approximation ratio. While the best distortion of deterministic rules is 3, prior work pins down the best distortion of randomized rules to [2.1126,2.5]. We improve the upper bound to 2.1441, closing over 90% of this gap. The proof introduces random-size stable lotteries, proves their existence, and derives the new bound through a potential argument. All the proofs were obtained using GPT-5.6-Sol with significant guidance from the author, who verified them and simplified the exposition.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 17 of its 32 references that are in the map. First posted on arXiv 29 Aug 2026.

Builds on

17 of 32 references.

References · 17

  1. 2022Optimized Distortion and Proportional Fairness in Votingcited by 12
  2. 2019Group Fairness in Committee Selectioncited by 10
  3. 2020Resolving the Optimal Metric Distortion Conjecturecited by 10
  4. 2019Approximately Stable Committee Selectioncited by 7
  5. 2016Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Propertiescited by 6
  6. 2019Improved Metric Distortion for Deterministic Social Choice Rulescited by 6
  7. 2019Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queriescited by 6
  8. 2019Communication, Distortion, and Randomness in Metric Votingcited by 6
  9. 2022Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortioncited by 6
  10. 2021Metric Distortion Bounds for Randomized Social Choicecited by 4
  11. 2019An Analysis Framework for Metric Voting based on LP Dualitycited by 3
  12. 2023Best of Both Distortion Worldscited by 3
5 more
  1. 2023Breaking the Metric Voting Distortion Barriercited by 3
  2. 2021On the Randomized Metric Distortion Conjecturecited by 2
  3. 2023Generalized Veto Core and a Practical Voting Rule with Optimal Metric Distortioncited by 2
  4. 2025Metric Distortion for Tournament Voting and Beyondcited by 2
  5. 2026An improved bound for the randomized metric distortion problemcited by 1

Built on by

Not cited yet.