1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yoshio Okamoto
    Apr 11, 2011 at 13:09
  • 1
    $\begingroup$ The obvious decision variant is NP-complete trivially, since evaluating the cost of a ranking is easy to do. Did you mean something else ? $\endgroup$
    – Suresh Venkat
    Apr 11, 2011 at 16:10
  • $\begingroup$ Evaluating the cost of a ranking isn't sufficient to verify that it's optimal. Am I misunderstanding what you mean? $\endgroup$
    – DRMacIver
    Apr 12, 2011 at 7:28
  • $\begingroup$ 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. $\endgroup$
    – DRMacIver
    Apr 12, 2011 at 7:29
  • $\begingroup$ @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. $\endgroup$
    – Yoshio Okamoto
    Apr 12, 2011 at 14:22

1 Answer 1

Reset to default
1
$\begingroup$

The following decision problem is NP-complete:
Kemeny Score
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$?

This decision problem is often seen as "natural decision problem" behind Kemeny voting. It is trivially in NP since computing the Kendall-Tau distance is in P. For NP-hardness see for example [Bartholdi, Tovey and Tick, Social Choice and Welfare 1989] or [Dwork, Kumar, Naor, and Sivakumar, WWW 2001].

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.