# 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. Apr 11, 2011 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 ? Apr 11, 2011 at 16:10
• Evaluating the cost of a ranking isn't sufficient to verify that it's optimal. Am I misunderstanding what you mean? Apr 12, 2011 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. Apr 12, 2011 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. Apr 12, 2011 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.