Deterministic Metric Distortion of Top-2 Voting

Abstract

We give tight bounds on the metric distortion of top-2 deterministic voting mechanisms. We first exploit the restrictive structure of top-2 voting to reduce the space of worst-case metrics from the continuum of biased metrics to $2^n$ subset metrics, where every candidate has distance $0$ or $1$ to the optimal candidate and $n$ is the number of candidates. We then reduce these further to just $2n$ polar metrics: $n$ of these have a single optimal candidate, and the other $n$ have a single sub-optimal candidate. This reduction yields an efficient algorithm that computes the exact distortion of every candidate on a given profile and runs in $\mathcal{O}(n^2)$ time. As a corollary, we can derive the exact worst-case distortion for top-2 voting for all values of $n$, for which previous work had non-matching lower and upper bounds.

arXiv comment9 pages