Breaking the Metric Voting Distortion Barrier
Prasanna Ramakrishnan (Stanford University)
Monday, May 6th 2024, 2-3pm
Abstract:
We consider the following well-studied problem of metric distortion in social choice. Suppose we have an election with voters and candidates who lie in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, each voter gives us a ranked list of the candidates in order of distance. Can we design a voting rule that, regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion)?
A long line of work culminated in finding deterministic voting rules with metric distortion 3, which is the best possible for deterministic rules and many other classes of voting rules. However, without any restrictions, there is still a significant gap in our understanding. Even though the best lower bound is substantially lower at 2.112, finding a randomized rule that guarantees distortion $3 - \epsilon$ for some constant $\epsilon$ has been a major challenge in computational social choice.
In this work, we give a rule that guarantees distortion less than 2.753 by carefully randomizing between Maximal Lotteries, a natural game-theoretical voting rule dating back to the 60's, and new voting rules that we introduce.
Based on joint work with Moses Charikar, Kangning Wang, and Hongxun Wu, which won a Best Paper Award at SODA 2024.