# Breaking the Metric Voting Distortion Barrier

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 58 references that are in the map.
- First posted on arXiv 30 Jun 2023.

## Builds on (most cited first, 23 of 23)

- [Distortion in Social Choice Problems: The First 15 Years and Beyond](https://mlsanity.com/paper/2103.00911/) (2021)
- [Optimized Distortion and Proportional Fairness in Voting](https://mlsanity.com/paper/2205.15760/) (2022)
- [On Voting and Facility Location](https://mlsanity.com/paper/1512.05868/) (2015)
- [Resolving the Optimal Metric Distortion Conjecture](https://mlsanity.com/paper/2004.07447/) (2020)
- [The Metric Distortion of Multiwinner Voting](https://mlsanity.com/paper/2201.13332/) (2022)
- [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)
- [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)
- [Randomized Social Choice Functions Under Metric Preferences](https://mlsanity.com/paper/1512.07590/) (2015)
- [Metric Distortion Bounds for Randomized Social Choice](https://mlsanity.com/paper/2111.03694/) (2021)
- [Distortion Under Public-Spirited Voting](https://mlsanity.com/paper/2305.11736/) (2023)
- [Ordinal Approximation for Social Choice, Matching, and Facility Location Problems given Candidate Positions](https://mlsanity.com/paper/1805.03103/) (2018)
- [An Analysis Framework for Metric Voting based on LP Duality](https://mlsanity.com/paper/1911.07162/) (2019)
- [A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching](https://mlsanity.com/paper/2009.06543/) (2020)
- [Best of Both Distortion Worlds](https://mlsanity.com/paper/2305.19453/) (2023)
- [Of the People: Voting Is More Effective with Representative Candidates](https://mlsanity.com/paper/1705.01736/) (2017)
- [On the Distortion of Voting with Multiple Representative Candidates](https://mlsanity.com/paper/1711.07600/) (2017)
- [Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice](https://mlsanity.com/paper/1811.04786/) (2018)
- [On the Randomized Metric Distortion Conjecture](https://mlsanity.com/paper/2111.08698/) (2021)
- [Distortion in metric matching with ordinal preferences](https://mlsanity.com/paper/2305.12119/) (2023)
- [Generalized Veto Core and a Practical Voting Rule with Optimal Metric Distortion](https://mlsanity.com/paper/2305.19632/) (2023)
- [Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship](https://mlsanity.com/paper/1602.08023/) (2016)

## Built on by (most cited first, 3 of 3)

- [Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?](https://mlsanity.com/paper/2505.23749/) (2025)
- [LLMs Judge Themselves: A Game-Theoretic Framework for Human-Aligned Evaluation](https://mlsanity.com/paper/2510.15746/) (2025)
- [Improving Randomized Metric Distortion to 2.1441](https://mlsanity.com/paper/2608.29308/) (2026)

## Abstract (arXiv)

We consider the following well-studied problem of metric distortion in social choice. Suppose we have an election with n voters and m candidates located in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, the voting rule obtains, from each voter, a ranked list of the candidates in order of distance. Can we design a rule that regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion)? A long line of work culminated in finding optimal deterministic voting rules with metric distortion 3. However, for randomized voting rules, there is still a gap in our understanding: Even though the best lower bound is 2.112, the best upper bound is still 3, attained even by simple rules such as Random Dictatorship. Finding a randomized rule that guarantees distortion 3 - ε has been a major challenge in computational social choice, as prevalent approaches to designing voting rules are known to be insufficient. Such a voting rule must use information beyond aggregate comparisons between pairs of candidates, and cannot only assign positive probability to candidates that are voters' top choices. In this work, we give a rule that guarantees distortion less than 2.753. To do so we study a handful of voting rules that are new to the problem. One is Maximal Lotteries, a rule based on the Nash equilibrium of a natural zero-sum game which dates back to the 60's. The others are novel rules that can be thought of as hybrids of Random Dictatorship and the Copeland rule. Though none of these rules can beat distortion 3 alone, a randomization between Maximal Lotteries and any of the novel rules can.