# On the Randomized Metric Distortion Conjecture

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2021.

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

- [Breaking the Metric Voting Distortion Barrier](https://mlsanity.com/paper/2306.17838/) (2023)
- [Improving Randomized Metric Distortion to 2.1441](https://mlsanity.com/paper/2608.29308/) (2026)

## Abstract (arXiv)

In the single winner determination problem, we have n voters and m candidates and each voter j incurs a cost c(i, j) if candidate i is chosen. Our objective is to choose a candidate that minimizes the expected total cost incurred by the voters; however as we only have access to the agents' preference rankings over the outcomes, a loss of efficiency is inevitable. This loss of efficiency is quantified by distortion. We give an instance of the metric single winner determination problem for which any randomized social choice function has distortion at least 2.063164. This disproves the long-standing conjecture that there exists a randomized social choice function that has a worst-case distortion of at most 2.