Breaking the Metric Voting Distortion Barrier
Moses Charikar, Kangning Wang, Prasanna Ramakrishnan, Hongxun Wu
Abstract
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 significant gap in our understanding: Even though the best lower bound is substantially lower at 2.112, the best upper bound is still 3, which is attained even by simple rules such as Random Dictatorship. Finding a randomized rule that guarantees distortion 3 -ε for some constant ε has been a major challenge in computational social choice, as prevalent approaches to designing voting rules are known to be insufficient. In particular, 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 careful randomization between Maximal Lotteries and any of the novel rules can.
C.1 Distortion for (Weighted) Uncovered Set Rules 33 C.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
9 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information cites Metric Distortion Bounds for Randomized Social Choice
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information cites An Analysis Framework for Metric Voting based on LP Duality
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information cites Resolving the Optimal Metric Distortion Conjecture
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information cites The Metric Distortion of Multiwinner Voting
- Metric Distortion Bounds for Randomized Social Choice cites Communication, Distortion, and Randomness in Metric Voting
- Metric Distortion Bounds for Randomized Social Choice cites An Analysis Framework for Metric Voting based on LP Duality
- Metric Distortion Bounds for Randomized Social Choice cites Resolving the Optimal Metric Distortion Conjecture
- Can a Few Decide for Many? The Metric Distortion of Sortition cites Resolving the Optimal Metric Distortion Conjecture
- Constant-Factor Distortion Mechanisms for k-Committee Election cites Low-Distortion Clustering with Ordinal and Limited Cardinal Information
- Constant-Factor Distortion Mechanisms for k-Committee Election cites Metric Distortion Bounds for Randomized Social Choice
- Constant-Factor Distortion Mechanisms for k-Committee Election cites Communication, Distortion, and Randomness in Metric Voting
- Constant-Factor Distortion Mechanisms for k-Committee Election cites Resolving the Optimal Metric Distortion Conjecture
- Constant-Factor Distortion Mechanisms for k-Committee Election cites The Metric Distortion of Multiwinner Voting
- Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences? cites Resolving the Optimal Metric Distortion Conjecture
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting cites Metric Distortion Bounds for Randomized Social Choice
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting cites Communication, Distortion, and Randomness in Metric Voting
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting cites Resolving the Optimal Metric Distortion Conjecture
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting cites The Metric Distortion of Multiwinner Voting
- Communication, Distortion, and Randomness in Metric Voting cites An Analysis Framework for Metric Voting based on LP Duality
- An Analysis Framework for Metric Voting based on LP Duality cites Communication, Distortion, and Randomness in Metric Voting
- Resolving the Optimal Metric Distortion Conjecture cites Communication, Distortion, and Randomness in Metric Voting
- Resolving the Optimal Metric Distortion Conjecture cites An Analysis Framework for Metric Voting based on LP Duality
- The Metric Distortion of Multiwinner Voting cites Metric Distortion Bounds for Randomized Social Choice
- The Metric Distortion of Multiwinner Voting cites Communication, Distortion, and Randomness in Metric Voting
- The Metric Distortion of Multiwinner Voting cites An Analysis Framework for Metric Voting based on LP Duality
- The Metric Distortion of Multiwinner Voting cites Resolving the Optimal Metric Distortion Conjecture
Cited by top-tier papers9
- Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?Paul Gölz, Nika Haghtalab, Kunhe YangNeurIPS 2025 · 29 citations
- Can a Few Decide for Many? The Metric Distortion of SortitionIoannis Caragiannis, Evi Micha, Jannik PetersICML 2024 · 11 citations
- Low-Distortion Clustering with Ordinal and Limited Cardinal InformationJakob Burkhardt, Ioannis Caragiannis, Karl Fehrs, Matteo Russo et al.AAAI 2024 · 8 citations
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed VotingMohammad Ali Abam, Davoud Kareshki, Marzie Nilipour, Mohammad Hossein Paydar et al.NeurIPS 2025 · 3 citations
- Constant-Factor Distortion Mechanisms for k-Committee ElectionHaripriya Pulyassary, Chaitanya SwamyAAAI 2025 · 1 citation
Builds on5
- The Metric Distortion of Multiwinner VotingIoannis Caragiannis, Nisarg Shah, Alexandros A. VoudourisAAAI 2022 · 49 citations
- Communication, Distortion, and Randomness in Metric VotingDavid KempeAAAI 2020 · 45 citations
- Resolving the Optimal Metric Distortion ConjectureVasilis Gkatzelis, Daniel Halpern, Nisarg ShahFOCS 2020 · 44 citations
- An Analysis Framework for Metric Voting based on LP DualityDavid KempeAAAI 2020 · 37 citations
- Metric Distortion Bounds for Randomized Social ChoiceMoses Charikar, Prasanna RamakrishnanSODA 2022 · 18 citations
Related papers
- Metric Distortion of Small-Group DeliberationAshish Goel, Mohak Goyal, Kamesh MunagalaSTOC 2025 · 1 citation
- Bi-Criteria Metric DistortionKiarash Banihashem, Diptarka Chakraborty, Shayan Chashm Jahan, Iman Gholami et al.ICLR 2026
- Worst-Case Voting When the Stakes Are HighAnson Kahng, Gregory KehneAAAI 2022 · 3 citations
- Improved Metric Distortion via Threshold ApprovalsElliot Anshelevich, Aris Filos-Ratsikas, Christopher Jerrett, Alexandros A. VoudourisAAAI 2024 · 10 citations
- Dimensionality and Coordination in Voting: The Distortion of STVIoannis Anagnostides, Dimitris Fotakis, Panagiotis PatsilinakosAAAI 2022 · 7 citations
