Kemeny Winner Score Problem (COMSOC)

Definition

Kemeny Winner Score Problem (COMSOC)

Input:

• profile $R=({\succ }_1,\dots ,{\succ }_n)$ over alternatives $C$
• an alternative $x\in C$, and
• a positive integer $k$

Question: $\exists {\succ }^{\ast }\in \mathcal{L}(C)$ with Kemeny score at most $k$ such that $x=\text{1st}({\succ }^{\ast })$?