<p>The following decision problem is NP-complete:<br>
<strong>Kemeny Score</strong><br>
<strong>Input:</strong> An election ($n$ partial or full rankings of $m$ candidates) and a positive integer $k$.<br>
<strong>Question:</strong>: Is there a ranking with $\sum_i d(r, q_i) \leq k$?</p>

<p>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].</p>

<p>However, the problem you describe above looks more like an optimization problem. To answer your question I refer to the <strong>Kemeny Winner</strong> 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.</p>

CC BY-SA 3.0
2012-03-15T10:49:16.760Z
2012-03-15T10:49:16.760Z
RBredereck
<p>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|$).</p>

<p>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?</p>

CC BY-SA 3.0
2011-04-11T13:09:18.173Z
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
CC BY-SA 3.0
2011-04-11T16:10:08.953Z
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
CC BY-SA 3.0
2011-04-12T07:28:13.930Z
Evaluating the cost of a ranking isn't sufficient to verify that it's optimal. Am I misunderstanding what you mean?
DRMacIver
CC BY-SA 3.0
2011-04-12T07:29:03.663Z
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
CC BY-SA 3.0
2011-04-12T14:22:49.640Z
@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
<ds.algorithms><np-hardness>
Efficient verification of Kemeny-optimal rankings
DRMacIver
# Efficient verification of Kemeny-optimal rankings

(Asked by: username_0 on 2011-04-11)

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?

**Tags:** ds.algorithms, np-hardness

> **Comments:**
> **username_1**: 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.  
> **username_2**: The obvious decision variant is NP-complete trivially, since evaluating the cost of a ranking is easy to do. Did you mean something else ?  
> **username_0**: Evaluating the cost of a ranking isn't sufficient to verify that it's optimal. Am I misunderstanding what you mean?  
> **username_0**: 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.  
> **username_1**: @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.  

---

## 1 answers

### Answer by username_3 on 2012-03-15. Score: 1

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.


---

