DRAFT

Center for Social Information Sciences (CSIS) Seminar

Friday, December 2, 2022
12:00pm to 1:00pm
Add to Cal
Baxter 127
Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion
Fatih Erdem Kızılkaya, Research Assistant, USC,

Abstract: The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i.e., has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search.

Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead.

For more information, please contact Letty Diaz by phone at 626-395-1255 or by email at letty.diaz@caltech.edu.