# Improving Randomized Metric Distortion to 2.1441

arXiv: https://arxiv.org/abs/2608.29308 · HTML: https://mlsanity.com/paper/2608.29308/

## 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 (most cited first, 17 of 17)

- [Optimized Distortion and Proportional Fairness in Voting](https://mlsanity.com/paper/2205.15760/) (2022)
- [Group Fairness in Committee Selection](https://mlsanity.com/paper/1905.04438/) (2019)
- [Resolving the Optimal Metric Distortion Conjecture](https://mlsanity.com/paper/2004.07447/) (2020)
- [Approximately Stable Committee Selection](https://mlsanity.com/paper/1910.14008/) (2019)
- [Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties](https://mlsanity.com/paper/1612.02912/) (2016)
- [Improved Metric Distortion for Deterministic Social Choice Rules](https://mlsanity.com/paper/1905.01401/) (2019)
- [Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries](https://mlsanity.com/paper/1907.08165/) (2019)
- [Communication, Distortion, and Randomness in Metric Voting](https://mlsanity.com/paper/1911.08129/) (2019)
- [Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion](https://mlsanity.com/paper/2206.07098/) (2022)
- [Metric Distortion Bounds for Randomized Social Choice](https://mlsanity.com/paper/2111.03694/) (2021)
- [An Analysis Framework for Metric Voting based on LP Duality](https://mlsanity.com/paper/1911.07162/) (2019)
- [Best of Both Distortion Worlds](https://mlsanity.com/paper/2305.19453/) (2023)
- [Breaking the Metric Voting Distortion Barrier](https://mlsanity.com/paper/2306.17838/) (2023)
- [On the Randomized Metric Distortion Conjecture](https://mlsanity.com/paper/2111.08698/) (2021)
- [Generalized Veto Core and a Practical Voting Rule with Optimal Metric Distortion](https://mlsanity.com/paper/2305.19632/) (2023)
- [Metric Distortion for Tournament Voting and Beyond](https://mlsanity.com/paper/2505.13630/) (2025)
- [An improved bound for the randomized metric distortion problem](https://mlsanity.com/paper/2608.17863/) (2026)

## 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.