# Efficient verification of Kemeny-optimal rankings

The problem of finding a Kemeny optimal aggregation is as follows: Given items $1 \ldots n$ and a list of partial rankings $q_i$ (i.e. permutations of subsets) of these items, find a ranking $r$ of $1\ldots n$ that minimizes $\sum_i d(r, q_i)$. Where $d(r, q)$ is defined as a count of the number of pairs on which $r$ and $q$ agree, scaled so that complete agreement is 1 (i.e. scaled by $k(k-1)/2$ where $k = |q|$).

Finding a Kemeny-optimal solution is known to be NP-hard in n (not surprising, it's an optimisation problem on a search space of size $n!$). What I'm wondering is if it's in fact NP-complete - if there's an (efficient?) polynomial time algorithm for verifying if a given ranking is in fact Kemeny optimal. I've seen a paper or two claiming it is, but I've not been able to find any papers which prove it. (Possibly because I live and work outside the academic firewall). Any references / ideas?

• NP is a class of decision problems. But I don't see which decision problem you're talking about, because your problem looks like an optimization problem. It'd be helpful if you could give references to the papers you've seen. – Yoshio Okamoto Apr 11 '11 at 13:09
• The obvious decision variant is NP-complete trivially, since evaluating the cost of a ranking is easy to do. Did you mean something else ? – Suresh Venkat Apr 11 '11 at 16:10
• Evaluating the cost of a ranking isn't sufficient to verify that it's optimal. Am I misunderstanding what you mean? – DRMacIver Apr 12 '11 at 7:28
• I suppose focusing on the NP-complete nature of this is a red herring. Really all I'm interested in is if there's a more efficient way to verify if a given ranking is optimal than actually trying to optimise it. – DRMacIver Apr 12 '11 at 7:29
• @DRMaclver: That's why you need to specify which decision problem you're talking about. "The obvious decision variant" is "Given items, a list of partial rankings q_i over the items and a number b, decide whether there exists a ranking r such that the sum of d(q_i,r) is at most b". If you're talking about this decision problem, I have nothing to add more than the comment of Suresh. – Yoshio Okamoto Apr 12 '11 at 14:22

Input: An election ($n$ partial or full rankings of $m$ candidates) and a positive integer $k$.
Question:: Is there a ranking with $\sum_i d(r, q_i) \leq k$?
However, the problem you describe above looks more like an optimization problem. To answer your question I refer to the Kemeny Winner problem which is $P_{||}^{NP}$-complete (see [Hemaspaandra, Spakowski, Vogel, TCS 2005]). Thus, already deciding whether a candidate is an (optimal) winner in Kemeny's system is presumable not in NP.