# Resolving the Optimal Metric Distortion Conjecture

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

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

- [Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?](https://mlsanity.com/paper/2505.23749/) (2025)
- [Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion](https://mlsanity.com/paper/2206.07098/) (2022)
- [Fair and Efficient Resource Allocation with Partial Information](https://mlsanity.com/paper/2105.10064/) (2021)
- [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)
- [Proportional Representation in Metric Spaces and Low-Distortion Committee Selection](https://mlsanity.com/paper/2312.10369/) (2023)
- [Optimizing Multiple Simultaneous Objectives for Voting and Facility Location](https://mlsanity.com/paper/2212.03467/) (2022)
- [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)

We study the following metric distortion problem: there are two finite sets of points, V and C, that lie in the same metric space, and our goal is to choose a point in C whose total distance from the points in V is as small as possible. However, rather than having access to the underlying distance metric, we only know, for each point in V, a ranking of its distances to the points in C. We propose algorithms that choose a point in C using only these rankings as input and we provide bounds on their distortion (worst-case approximation ratio). A prominent motivation for this problem comes from voting theory, where V represents a set of voters, C represents a set of candidates, and the rankings correspond to ordinal preferences of the voters. A major conjecture in this framework is that the optimal deterministic algorithm has distortion 3. We resolve this conjecture by providing a polynomial-time algorithm that achieves distortion 3, matching a known lower bound. We do so by proving a novel lemma about matching voters to candidates, which we refer to as the ranking-matching lemma. This lemma induces a family of novel algorithms, which may be of independent interest, and we show that a special algorithm in this family achieves distortion 3. We also provide more refined, parameterized, bounds using the notion of α-decisiveness, which quantifies the extent to which a voter may prefer her top choice relative to all others. Finally, we introduce a new randomized algorithm with improved distortion compared to known results, and also provide improved lower bounds on the distortion of all deterministic and randomized algorithms.