Breaking the Metric Voting Distortion Barrier

作者：Moses Charikar, Kangning Wang, Prasanna Ramakrishnan, Hongxun Wu · 发表于：Society for Industrial and Applied Mathematics eBooks · 年份：2024 · DOI：10.1137/1.9781611977912.65 · 被引用次数：10 · 研究领域：Game Theory and Voting Systems、Auction Theory and Applications、Experimental Behavioral Economics Studies

We consider the following well studied problem of metric distortion in social choice. Suppose we have an election with n voters and m 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 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)?