# Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 14 Jun 2022.

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

- [Distortion in Social Choice Problems: The First 15 Years and Beyond](https://mlsanity.com/paper/2103.00911/) (2021)
- [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)
- [Randomized Social Choice Functions Under Metric Preferences](https://mlsanity.com/paper/1512.07590/) (2015)
- [Relating Metric Distortion and Fairness of Social Choice Rules](https://mlsanity.com/paper/1810.01092/) (2018)
- [Comparing Election Methods Where Each Voter Ranks Only Few Candidates](https://mlsanity.com/paper/1901.10848/) (2019)
- [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)
- [Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice](https://mlsanity.com/paper/1811.04786/) (2018)
- [Approval-Based Elections and Distortion of Voting Rules](https://mlsanity.com/paper/1901.06709/) (2019)
- [Favorite-Candidate Voting for Eliminating the Least Popular Candidate in Metric Spaces](https://mlsanity.com/paper/1911.12109/) (2019)

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

- [Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?](https://mlsanity.com/paper/2505.23749/) (2025)
- [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)
- [The Distortion of Binomial Voting Defies Expectation](https://mlsanity.com/paper/2306.15657/) (2023)
- [Compatibility of Max and Sum Objectives for Committee Selection and k-Facility Location](https://mlsanity.com/paper/2507.17063/) (2025)
- [Improving Randomized Metric Distortion to 2.1441](https://mlsanity.com/paper/2608.29308/) (2026)

## Abstract (arXiv)

The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search. Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead. We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k < n rounds; then, a candidate is chosen with probability proportional to his residual score. This general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output. We show that for all k, this rule has distortion at most 3.