Approximating optimal social choice under metric preferences

摘要

We consider voting under metric preferences: both voters and alternatives are associated with points in a metric space, and each voter prefers alternatives that are closer to her to ones that are further away. In this setting, it is often desirable to select an alternative that minimizes the sum of distances to the voters, i.e., the utilitarian social cost, or other similar measures of social cost. However, common voting rules operate on voters' preference rankings and therefore may be unable to identify an optimal alternative. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of an alternative selected by the rule and that of an optimal alternative. Thus, distortion measures how good a voting rule is at approximating an alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that they form a metric space. The goal of our paper is to quantify the distortion of well-known voting rules. We first establish a lower bound on the distortion of any deterministic voting rule. We then show that the distortion of positional scoring rules cannot be bounded by a constant, and for several popular rules in this family distortion is linear in the number of alternatives. On the other hand, for Copeland and similar rules the distortion is bounded by a factor of 5. These results hold both for the sum of voters' cost and the median voter cost. For Single Transferable Vote (STV), we obtain an upper bound of O(ln⁡m) with respect to the sum of voters' costs, where m is the number of alternatives, as well as a lower bound of Ω(ln⁡m); thus, STV is a reasonable, though not a perfect rule from this perspective. Our results for median voter cost extend to more general objective functions.