Computing Slater Rankings Using Similarities Among Candidates∗Vincent ConitzerComputer Science DepartmentCarnegie Mellon UniversityPittsburgh, PA 15213, [email protected] (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 ofcandidates such that the ranking disagrees with the pairwisemajority vote on these two candidates. The use of the Slaterrule has been hindered by a lack of techniques to computeSlater rankings. In this paper, we show how we can decom-pose the Slater problem into smaller subproblems if there is aset of similar candidates. We show that this technique sufficesto 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 similarcandidates. We provide experimental results that show thatthis technique significantly (sometimes drastically) speeds upsearch algorithms. Finally, we also use the technique of sim-ilar sets to show that computing an optimal Slater ranking isNP-hard, even in the absence of pairwise ties.IntroductionIn multiagent systems with self-interested agents, often theagents need to arrive at a joint decision in spite of differ-ent preferences over the available alternatives. Voting (orrank aggregation) is a general method for doing so. Ina rank aggregation setting, each voter ranks all the differ-ent alternatives (or candidates), and a voting rule maps thevotes to a single ranking of all the candidates. Rank ag-gregation has applications outside the space of preferenceaggregation as well: for example, we can take the rank-ings that different search engines provide over a set of web-pages and produce an aggregate ranking from this. Otherapplications include collaborative filtering [22] and planningamong automated agents [17; 18]. Recent work in artifi-cial intelligence and related areas has studied the complex-ity of executing voting rules [19; 7; 14; 12; 1]; the com-plexity of manipulating elections [9; 16; 15]; eliciting thevotes efficiently [8]; adapting voting theory to the setting∗This material is based on work done while the author wasvisiting IBM’s T.J. Watson Research Center in the context of anIBM Ph.D. Fellowship. The author thanks Andrew Davenport andJayant Kalagnanam for a significant amount of valuable directionand feedback.Copyrightc° 2006, American Association for Artificial Intelli-gence (www.aaai.org). All rights reserved.where the candidates vote over each other by linking toeach other (as in the context of the World Wide Web) [4;3]; and interpreting common voting rules as maximum like-lihood estimators of a “correct” ranking [10].The design of voting rules has been guided by the ax-iomatic approach: decide on a set of criteria that a goodvoting rule should satisfy, and determine which (if any) vot-ing rules satisfy all of these criteria. One well-known cri-terion is that of independence of irrelevant alternatives.Inits strongest form, this criterion states that the relative rank-ing of two candidates by a voting rule should not be affectedby the presence or absence of other candidates. That is, ifa is ranked higher than b by a voting rule that satisfies in-dependence of irrelevant alternatives, then the voting rulewill still rank a higher than b after the introduction of an-other candidate c. Arrow’s impossibility result [5] precludesthe existence of any reasonable voting rule satisfying thiscriterion. Intuitively, when independence of irrelevant al-ternatives is satisfied, whether candidate a or b is preferredshould depend only on whether more votes prefer a to b thanb to a—that is, the winner of the pairwise election should beranked higher. Unfortunately, as noted by Condorcet [13],there can be cycles in this relationship: for example, it canbe the case that a defeats b, b defeats c, and c defeats a inpairwise elections. If so, no ranking of the candidates willbe consistent with the outcomes of all pairwise elections.The Slater voting rule is arguably the most straightfor-ward resolution to this problem: it simply chooses a rankingof the candidates that is inconsistent with the outcomes of asfew pairwise elections as possible. Unfortunately, as we willdiscuss later in this paper, computing a Slater ranking is NP-hard. This suggests that we need a search-based algorithmto compute Slater rankings.1In this paper, we introduce a powerful preprocessing tech-nique that can reduce the size of instances of the Slater prob-lem before the search is started. We say that a subset of thecandidates consists of similar candidates if for every candi-date outside of the subset, all candidates inside the subsetachieve the same result in the pairwise election against thatcandidate. Given a set of similar candidates, we can recur-1Another approach is to look for rankings that are approxi-mately optimal in the Slater sense [1; 11]. Of course, this is notentirely satisfactory as it is effectively changing the voting rule.sively solve the Slater problem for that subset, and for theoriginal set with the entire subset replaced by a single can-didate, to obtain a solution to the original Slater problem. Inaddition, we also make the following contributions:• We show that if the results of the pairwise elections havea particular hierarchical structure, the preprocessing tech-nique is sufficient to solve the Slater problem in linear time.• For the general case, we give a polynomial-time algo-rithm for finding a set of similar candidates (if it exists). Thisalgorithm is based on satisfiability techniques.• We exhibit the power of the preprocessing techniqueexperimentally.• We use the concept of a set of similar candidates to givethe first straightforward reduction (that is, not a randomizedreduction or a derandomization thereof) showing that theSlater problem is NP-hard in the absence of pairwise ties.DefinitionsWe use C to denote the set of candidates. We say that can-didate a defeats candidate b in their pairwise election, de-noted by a → b, if the number of votes ranking a above bis greater than the number of votes ranking b above a. TheSlater rule is defined as follows: find a ranking  on thecandidates that minimizes the number of ordered pairs (a, b)such that a  b but b defeats a in their pairwise