In this post, we’ll revisit the (deterministic) metric distortion conjecture in voting theory, which was recently proved by Gkatzelis, Halpern, and Shah [GHS20], and elegantly re-proved by Kempe and Kizilkaya [KK22].

The conjecture concerns the following question. Suppose we have an election with voters and candidates who lie in a metric space, but the only information we have is the voters’ ranking of the candidates in increasing order of distance. The cost of a candidate is their total distance to the voters. Can we design a voting rule that always selects a candidate whose cost is close to the minimum possible? (Ideally, only worse than the minimum by a small factor, known in the literature as the distortion.) A priori, this may seem like an impossible task. How could you possibly do this without knowing the actual distances? It turns out that knowing the relative ordering of distances together with triangle inequality suffices to get distortion that is at most a constant. What is the smallest constant that can be achieved?

A simple example, depicted below, shows that it is impossible to get better than distortion 3. Imagine an election with two candidates (the red points), and two voters with opposite rankings over the candidates (the blue points, labeled with their rankings). Then consider two realizations of the metric on the line where one voter is co-located with their preferred candidate and the other voter is halfway between the two candidates. No matter which candidate the rule picks, in one of the metrics the other candidate has one third the cost.

[ABP15], who originally introduced the problem, showed that the Copeland rule achieves distortion 5 and conjectured that there exists a voting rule with distortion at most 3, matching the simple lower bound. The first progress towards this was made by [MW19] who designed a novel rule with distortion . They also formulated a nice combinatorial conjecture whose proof would imply the existence of a voting rule with distortion 3. [Kem20] found a different path to the same conjecture based on an LP duality framework, and suggested some other formulations as well. Finally, [GHS20] proved the combinatorial conjecture, thus resolving the metric distortion conjecture. But this wasn’t the end of the story — [KK22] were able to find an elegant voting rule which gives a simple one-paragraph proof of the combinatorial conjecture. Taking their proof, and weaving it into [GHS20]’s proof that the combinatorial conjecture implies distortion 3 eliminates the need for the intermediate conjecture, and gives the following very short self-contained proof.

Theorem. Suppose that we have an election with candidates and voters who lie in a metric space with distance metric . In the election, each voter gives a ranking of the candidates in order of distance (if then ). Then there is a deterministic voting rule that chooses a candidate such that for any candidate ,

Proof. Consider the following voting rule, Plurality Veto, introduced by [KK22]. Each candidate has a score which is initially the number of voters who rank that candidate first. Then, following an arbitrary ordering of the voters, each voter decrements (vetoes) the score of their least favorite candidate with positive score. The candidate vetoed by the last voter is the winner.

Let be the candidate vetoed by voter , and let be the final chosen candidate. Let be the set of voters that rank candidate first and let . Since has positive score until the very end, it must be the case that for each , . Then we have that for any candidate ,

as desired.

The figure below is an example instance illustrating the sequence of inequalities at the end. The candidates are red points inside the circle labeled 1, 2, 3, 4. The voters are blue points along the circle and are labeled with their rankings over the candidates. The ordering of the voters used for Plurality Veto is clockwise starting from the top, and for each voter , is highlighted in red. Candidate 2 ends up being the winner so , and their cost is being compared to candidate (who would have been the optimal choice). The total distances that the edges represent is below each picture, and the way that one particular edge is bounded is highlighted in orange to show how each step either replaces an edge with a longer one, or applies the triangle inequality.

A natural question is: what happens if we allow the rule to be randomized? The same two candidate example shows that it is impossible to get better than distortion 2 (in expectation). One might expect this to be the right answer again, but this was disproven independently by [CR22] and [PS21] using more sophisticated election instances. The former gave a lower bound of 2.112 which is the best known. It is indeed possible to get better than distortion 3 — recently in [CRWW23], we showed that distortion 2.753 is possible. The gap between these remains an open area of research. Is there another page of the book waiting to be found here?

Acknowledgments. Thanks to Moses Charikar and Kangning Wang for helpful feedback on a draft of this post!

References

[ABP15] Elliot Anshelevich, Onkar Bhardwaj, and John Postl. Approximating optimal social choice under metric preferences. AAAI 2015.

[CR22] Moses Charikar and Prasanna Ramakrishnan. Metric distortion bounds for randomized social choice. SODA 2022.

[CRWW23] Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu. Breaking the metric voting distortion barrier. arXiv preprint, 2023.

[GHS20] Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric distortion conjecture. FOCS 2020.

[Kem20] David Kempe. An analysis framework for metric voting based on LP duality. AAAI 2020.

[KK22] Fatih Erdem Kizilkaya and David Kempe. Plurality Veto: A simple voting rule achieving optimal metric distortion. IJCAI 2022.

[MW19] Kamesh Munagala and Kangning Wang. Improved metric distortion for deterministic social choice rules. EC 2019.

[PS21] Haripriya Pulyassary and Chaitanya Swamy. On the randomized metric distortion conjecture. arXiv preprint, 2021.