Approximating optimal social choice under metric preferences (Q668776)

In this work, the authors study the quality of the outcomes produced by a variety of common voting rules. The quality is measured by what they refer to as the distortion, which is an assessment of the social cost determined by the distances from candidate or alternative to voters or agents. This distance is initially given by the sum of all agent costs for the alternative. Another objective function defines the quality of the alternative as the median of its agent costs. The findings indicate that, while some commonly used rules exhibit high distortion, there are important voting rules for which distortion is bounded by a small constant or grows slowly with the number of alternatives. A lower bound is specified for the performance of all deterministic voting rules that operate on ranked ballots. It is demonstrated that no such rule can have worst-case distortion that is better than 3 (for the sum objective), or better than 5 (for the median objective). For common positional scoring rules, such as plurality and Borda, the worst-case distortion can be as high as $2m-1$, where m is the number of alternatives. For $k$-approval with $k>1$ and for veto, the worst-case distortion can be unbounded. On the other hand, the distortion of every voting rule that always outputs a subset of the uncovered set does not exceed 5; this upper bound holds true for both the sum and the median objective. Several voting rules possess this property, including the Copeland rule. A lower bound is established for the distortion of the Copeland rule with respect to the sum objective, showing that it cannot achieve the best possible distortion. The ranked pairs rule is also examined, and a range of scenarios is defined in which the distortion of this rule with respect to the sum objective does not exceed 3, thereby matching the lower bound. Another rule examined is the single transferable vote (STV). For the sum objective, the distortion of STV is upper-bounded by $O(\ln m)$, and it provides acceptable distortion when the number of alternatives is not too large. On the other hand, it is shown that the distortion of STV is lower-bounded by $(\sqrt{\ln m})$, implying that STV does not perform quite as well as the Copeland rule. Besides the median, more general percentile objectives are considered, where the quality of an alternative is set to be the cost of the voter at the $x$-th percentile. It is examined how the distortion of various rules changes with $x$, and it is established that Copeland remains the rule with the least distortion for most values of $x$.