The Impossibility of Strategyproof Rank Aggregation

In rank aggregation, the goal is to combine multiple input rankings into a single output ranking. In this paper, we analyze rank aggregation methods, so-called social welfare functions (SWFs), with respect to strategyproofness, which requires that no agent can misreport her ranking to obtain an output ranking that is closer to her true ranking in terms of the Kemeny distance. As our main result, we show that no anonymous SWF satisfies unanimity and strategyproofness if there are at least four alternatives. This result is proved using SAT solving, a computer-aided theorem-proving technique, and verified using Isabelle/HOL, a highly trustworthy interactive proof assistant. Moreover, we show by hand that strategyproofness is incompatible with majority-consistency, a variant of Condorcet-consistency for SWFs. Lastly, we analyze the incentive ratio of SWFs, which measures the worst-case ratio between a voter's utility when manipulating and when voting honestly. Unfortunately, we show that many natural SWFs have a large incentive ratio and are thus severely manipulable. Specifically, we prove that, if there are $m\geq 4$ alternatives, all positional scoring rules have an unbounded incentive ratio, and all distance scoring rules have an incentive ratio of roughly ${m\choose 2}$. Moreover, we identify an SWF called the Minimal Compromise rule, which has an incentive ratio of $m-2$.