Computing Slater Rankings Using Similarities among Candidates

Vincent Conitzer

Abstract

Computing Slater rankings is a fundamental problem in social choice theory, but its NP-hard nature often makes it computationally prohibitive. This paper presents a novel preprocessing technique based on identifying sets of "similar candidates"—subsets that share identical relationships with all external candidates. By proving that an optimal Slater ranking always places these similar candidates contiguously, the authors decompose the problem into smaller subproblems. Experimental results on synthetic spatial models demonstrate that this approach leads to massive speedups, often solving instances instantly where standard search algorithms fail.

Introduction

In multiagent systems, aggregating conflicting preferences into a single consensus ranking is a critical task. The Slater rule is a popular method for this, aiming to find a ranking that minimizes the number of disagreements with pairwise majority outcomes. However, the presence of the Condorcet paradox—where majority preferences form cycles (e.g., $A > B > C > A$)—makes finding the optimal Slater ranking NP-hard. As the number of candidates increases, the search space for the minimum number of edge flips in a tournament graph grows exponentially, rendering standard algorithms impractical.

The Similarity Preprocessing Technique

The core contribution of this work is a preprocessing method that exploits structural similarities within candidate sets. A subset of candidates $S$ is defined as similar if every member of $S$ has the same relationship (win or loss) with any candidate $c$ outside of $S$.

The author introduces three key technical pillars:

  1. The Contiguity Theorem: It is proven that an optimal Slater ranking exists where similar candidates appear as a contiguous block. This allows for problem decomposition: solving the internal ranking of the similar set and then treating the entire set as a single "super-candidate" in the global ranking.
  2. Efficient Detection: Identifying these sets is performed in polynomial time by transforming the search into a Horn-satisfiability (Horn-SAT) problem.
  3. Hierarchical Decomposition: For "valid candidate trees," where candidates are organized into nested similar sets, the Slater problem can be solved in linear time.
A valid candidate tree structure illustrating how similar candidates (e.g., {a, b, c}) can be grouped into hierarchical super-candidates.

Experimental Evaluation

The effectiveness of this preprocessing was tested across various synthetic datasets, including 1D, 2D, and 10D spatial models, as well as party-based models where candidates are naturally clustered. These models simulate a range of voting environments, from highly structured single-peaked preferences to complex, high-dimensional political landscapes.

The results show that the time spent on Horn-SAT preprocessing is negligible compared to the search time it saves. In many cases, particularly in the 1D spatial model, the preprocessing step solves the problem entirely before the search algorithm even begins.

Performance comparison showing the exponential growth of search time without preprocessing versus the near-instant solutions provided by the proposed technique as the number of candidates increases.

Conclusion and Future Work

This research demonstrates that "hidden" structures like similar sets are prevalent even in complex preference models. By exploiting these structures, the proposed algorithm achieves drastic speedups and provides a simpler deterministic proof for the NP-hardness of the Slater problem in tournaments.

Future work includes extending these techniques to the Kemeny rule, which requires a stricter definition of similarity, and validating the approach on real-world datasets such as movie rankings or search engine results. Additionally, further investigation into performance in tie-heavy environments would enhance the robustness of the method.

Summary updated

Abstract

Voting (or rank aggregation) is a general method for aggregating the preferences of multiple agents. One important voting rule is the Slater rule. It selects a ranking of the alternatives (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 decompose 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 majority 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 similar sets to show that computing an optimal Slater ranking is NP-hard. even in the absence of pairwise ties.
BibTeX
@inproceedings{conitzer2006computing,
  author = {Vincent Conitzer},
  title = {{Computing Slater Rankings Using Similarities among Candidates}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure