Logo image
Back
Resolving the Optimal Metric Distortion Conjecture
Conference proceeding   Open access

Resolving the Optimal Metric Distortion Conjecture

Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah and IEEE
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), v 2020-, pp 1427-1438
Nov 2020
DOI: https://doi.org/10.1109/FOCS46700.2020.00134
url
https://arxiv.org/abs/2004.07447View
SubmittedOpen Access (License Unspecified),  Open

Abstract

Approximation algorithms Bipartite graph Computer science Distortion Indexes Linear programming Measurement metric voting
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.

Metrics

15 Record Views
57 citations in Web of Science
66 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Computer Science, Theory & Methods
Logo image