Kangning Wang, Rutgers University

Abstract

This talk will be about metric distortion in social choice. I will cover several major results (by us and others) in this area, and discuss open questions and directions.

In a standard social choice scenario, voters express their preferences over candidates through votes, and then a voting rule aggregates those votes and selects one winning candidate. These votes can often be in the ranked-choice form, meaning that each voter submits her ranking of all the candidates. How efficient/effective can ranked-choice voting be?

In the metric distortion framework, we assume all voters and candidates reside in the same metric space, and each voter bears a cost equal to the distance between her and the elected candidate. The goal is to minimize the sum of costs over the voters. Various classical ranked-choice voting rules and novel ones can give the following guarantee: its sum of costs will be at most a constant times the true optimal sum of costs. Improving this guarantee has been the center of this research area, and this talk will review the progress.

See: https://theory.cs.rutgers.edu/theory_seminar