  We study social choice rules under the utilitarian distortion framework, with
an additional metric assumption on the agents' costs over the alternatives. In
this approach, these costs are given by an underlying metric on the set of all
agents plus alternatives. Social choice rules have access to only the ordinal
preferences of agents but not the latent cardinal costs that induce them.
Distortion is then defined as the ratio between the social cost (typically the
sum of agent costs) of the alternative chosen by the mechanism at hand, and
that of the optimal alternative chosen by an omniscient algorithm. The
worst-case distortion of a social choice rule is, therefore, a measure of how
close it always gets to the optimal alternative without any knowledge of the
underlying costs. Under this model, it has been conjectured that Ranked Pairs,
the well-known weighted-tournament rule, achieves a distortion of at most 3
[Anshelevich et al. 2015]. We disprove this conjecture by constructing a
sequence of instances which shows that the worst-case distortion of Ranked
Pairs is at least 5. Our lower bound on the worst case distortion of Ranked
Pairs matches a previously known upper bound for the Copeland rule, proving
that in the worst case, the simpler Copeland rule is at least as good as Ranked
Pairs. And as long as we are limited to (weighted or unweighted) tournament
rules, we demonstrate that randomization cannot help achieve an expected
worst-case distortion of less than 3. Using the concept of approximate
majorization within the distortion framework, we prove that Copeland and
Randomized Dictatorship achieve low constant factor fairness-ratios (5 and 3
respectively), which is a considerable generalization of similar results for
the sum of costs and single largest cost objectives. In addition to all of the
above, we outline several interesting directions for further research in this
space.
