Computing Slater Rankings Using Similarities Among Candidates

Abstract

Voting (or rank aggregation) is a general method for aggre-gating the preferences of multiple agents. One important vot-ing rule is the Slater rule. It selects a ranking of the alter-natives (or candidates) to minimize the number of pairs of candidates such that the ranking disagrees with the pairwise majority vote on these two candidates. The use of the Slater rule has been hindered by a lack of techniques to compute Slater rankings. In this paper, we show how we can decom-pose the Slater problem into smaller subproblems if there is a set of similar candidates. We show that this technique suffices to compute a Slater ranking in linear time if the pairwise ma-jority graph is hierarchically structured. For the general case, we also give an efficient algorithm for finding a set of similar candidates. We provide experimental results that show that this technique significantly (sometimes drastically) speeds up search algorithms. Finally, we also use the technique of sim-ilar sets to show that computing an optimal Slater ranking is NP-hard, even in the absence of pairwise ties.