2019-05-16 | Kangning Wang：Improved Metric Distortion for Deterministic Social Choice Rules
We study the metric distortion of deterministic social choice rules that choose a winning candidate from a set of candidates based on voter preferences. In this setting, voters and candidates are located in an underlying metric space. A voter has cost equal to her distance to the winning candidate. Ordinal social choice rules only have access to the ordinal preferences of the voters that are assumed to be consistent with the metric distances. Our goal is to design an ordinal social choice rule with minimum distortion, which is the worst-case ratio, over all consistent metrics, between the social cost of the rule and that of the optimal omniscient rule with knowledge of the underlying metric space.
The distortion of the best deterministic social choice rule was known to be between 3 and 5. It had been conjectured that any rule that only looks at the weighted tournament graph on the candidates cannot have distortion better than 5. We disprove it by presenting a weighted tournament rule with distortion of 4.236. We design this rule by generalizing the classic notion of uncovered sets, and further show that this class of rules cannot have distortion better than 4.236. We then propose a new voting rule, via an alternative generalization of uncovered sets. We show that if a combinatorial conjecture holds, then choosing such a candidate yields a distortion bound of 3, matching the lower bound.
Joint work with Kamesh Munagala.
Kangning Wang is a second-year Ph.D. student in Computer Science at Duke University. He is advised by Prof. Kamesh Munagala. His research interests include computational economics and theoretical computer science. Prior to joining Duke, he got his bachelor's degree from Yao Class, Tsinghua University. His work "A Simple Mechanism for a Budget-Constrained Buyer" with Yu Cheng, Nick Gravin and Kamesh Munagala won the best paper award at WINE 2018.