Resolving the Optimal Metric Distortion Conjecture

Resolving the Optimal Metric Distortion Conjecture (via Zoom)

Abstract: The axiomatic approach to aggregating ranked votes is full of impossibilities, the most famous one being Arrow's theorem. The recently proposed metric distortion framework provides a way around these impossibilities by quantifying the performance of voting rules, thus enabling the design of optimal voting rules. In this framework, it is assumed that voters and candidates lie in an underlying metric space, and each voter ranks the candidates by their distance from her. The goal of the voting rule is to pick a candidate, based only on voters' rankings, that approximately minimizes the total distance to voters, and the worst-case approximation ratio is called distortion. A major conjecture is that the optimal deterministic voting rule has distortion 3. We resolve this positively by constructing a new voting rule with distortion 3. We do so by proving a novel lemma about matching rankings of candidates to candidates, which may be of independent interest. We also provide parametric distortion bounds and improved bounds for randomized rules.

Joint work with Vasilis Gkatzelis and Nisarg Shah.

Bio: I am a first-year PhD student in the EconCS group at Harvard University, where I am fortunate to be advised by Ariel Procaccia. My research interests lie at the intersection of theoretical computer science and economics, paticularly in fair division and computational social choice. Prior to joining Harvard, I completed an undergraduate degree in computer science at the University of Toronto where I had the great pleasure of working under the supervision of Nisarg Shah.