The price of neutrality for the ranked pairs method

The complexity of the winner determination problem has been studied for almost all common voting rules. A notable exception, possibly caused by some confusion regarding its exact definition, is the method of ranked pairs. The original version of the method, due to Tideman, yields a social pref-erence function that is irresolute and neutral. A variant intro-duced subsequently uses an exogenously given tie-breaking rule and therefore fails neutrality. The latter variant is the one most commonly studied in the area of computational so-cial choice, and it is easy to see that its winner determina-tion problem is computationally tractable. We show that by contrast, computing the set of winners selected by Tideman’s original ranked pairs method is NP-complete, thus revealing a trade-off between tractability and neutrality. In addition, several known results concerning the hardness of manipula-tion and the complexity of computing possible and necessary winners are shown to follow as corollaries from our findings.