Kemeny Rule (COMSOC)

Definition

Kemeny Rule ( COMSOC)

The Kemeny rule is the voting rule selecting every alternative that appears first in at least one Kemeny consensus. For a profile $R$ over alternatives $C$,

$${\lambda }_{\mathrm{Kemeny}}(R):=\{x\in C:x\text{ is first in some Kemeny ranking of }R\}.$$

These alternatives are the Kemeny winners. The optimisation concerns whole rankings; the rule returns their possible first alternatives. If several alternatives qualify, they are co-winners unless a further tie-break selects one.

Intuition

Compare a proposed collective ranking with every voter’s ranking using Kendall–tau distance, then add the distances. Minimise this total over all complete, strict rankings. Finally, collect the first alternatives of all minimising rankings—not just the first optimum found.

Condorcet Consistency

Condorcet consistency

If $x$ is the Condorcet winner of $R$, every Kemeny consensus places $x$ first. Hence

$${\lambda }_{\mathrm{Kemeny}}(R)=\{x\},$$

so the rule is Condorcet consistent.

Move the Condorcet winner to the front

Let $R=({\succ }_1,\dots ,{\succ }_n)$ be a profile of complete, strict rankings over $C$, and assume $x\in C$ is a Condorcet winner. With $N_R$ denoting the pairwise support function,

$$\forall y\in C\setminus \{x\}:N_R(x,y)>\frac{n}{2}.$$

For each opponent, a strict majority prefers $x$ to that opponent; the majority may differ between opponents.

(1) Construct a competing ranking

Suppose, for contradiction, that some Kemeny ranking ${\succ }^{\ast }$ does not place $x$ first. Write it as below and obtain ${\succ }^{\prime }$ by moving only $x$ to the front:

\begin{array}{r@{\quad}c@{\;}c@{\;}c@{\;}c@{\;}c@{\;}c@{\;}c} \succ' : & x & \succ' & a_1 & \succ' & \cdots & \succ' & a_s\\ \succ^* : & a_1 & \succ^* & \cdots & \succ^* & a_s & \succ^* & x \end{array} \;{\color{orange} \overset{\text{fixed for both}}{\boxed{ \begin{array}{c@{\;}c@{\;}c@{\;}c@{\;}c@{\;}c} \succ' & b_1 & \succ' & \cdots & \succ' & b_t\\ \succ^* & b_1 & \succ^* & \cdots & \succ^* & b_t \end{array} }}} \qquad s\geq1,\quad t\geq0.

The $b$-list is empty when $t=0$. This construction gives a complete, strict ranking ${\succ }^{\prime }$; we do not assume that it is a Kemeny ranking.

The voters stay fixed; only the proposal changes

The profile $R=({\succ }_1,\dots ,{\succ }_n)$ contains the voters’ submitted rankings. It is not the pair of proposals $({\succ }^{\ast },{\succ }^{\prime })$. The rankings ${\succ }^{\ast }$ and ${\succ }^{\prime }$ are candidate collective rankings, each evaluated against all the same voters:

$$\begin{array}{rl}\mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\ast },R)& =\sum _{i=1}^n\mathrm{KT}(\underset{\text{old proposal}}{\underbrace{{\succ }^{\ast }}},\underset{\text{fixed ballot}}{\underbrace{{\succ }_i}}),\\ \mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\prime },R)& =\sum _{i=1}^n\mathrm{KT}(\underset{\text{new proposal}}{\underbrace{{\succ }^{\prime }}},\underset{\text{same ballot}}{\underbrace{{\succ }_i}}).\end{array}$$

Moving $x$ changes only the proposed group order, not any voter’s ballot. Consequently, $R$ and every count $N_R(u,v)$ stay fixed throughout the proof. What changes is which of these voters disagree with the proposal.

(2) Separate changed and unchanged pairs

Exactly the pairs $\{x,a_j\}$, for $j\in \{1,\dots ,s\}$, reverse their order. Every other pair keeps its order and therefore its contribution to the Kemeny score. Let $Q$ be the sum of these unchanged contributions, i.e.,

$$Q:=\underset{\text{pairs not involving }x}{\underbrace{\sum _{\begin{array}{c}u,v\in C\setminus \{x\}\\ u{\succ }^{\ast }v\end{array}}{N}_R(v,u)}}+\underset{\text{unchanged pairs }\{x,b_k\}}{\underbrace{\sum _{k=1}^t{N}_R(b_k,x)}}.$$

Since a proposal ordering $u$ above $v$ disagrees with precisely the $N_R(v,u)$ voters who prefer $v$ to $u$,

$$\begin{array}{rl}\mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\ast },R)& =Q+\sum _{j=1}^s\underset{\text{opposing }{a}_j{\succ }^{\ast }x}{\underbrace{N_R(x,a_j)}},\\ \mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\prime },R)& =Q+\sum _{j=1}^s\underset{\text{opposing }x{\succ }^{\prime }{a}_j}{\underbrace{N_R(a_j,x)}}.\end{array}$$

Here $N_R(u,v)$ counts voters who prefer $u$ to $v$; it does not count changes between the two proposed rankings. Thus an unchanged pair need not contribute zero to either score. If both proposals place $u$ above $v$, its contributions are

$$\begin{array}{rl}\text{to the score of }{\succ }^{\ast }& :N_R(v,u),\\ \text{to the score of }{\succ }^{\prime }& :N_R(v,u),\\ \text{to their difference}& :N_R(v,u)-N_R(v,u)=0.\end{array}$$

Therefore $Q$ is the common contribution to each score, not a contribution to their difference. Subtracting the scores cancels $Q-Q=0$, leaving only the contributions from the reversed pairs $\{x,a_j\}$. Unchanged means equal contributions, not zero contributions.

See exactly which contributions belong to Q

Take three voters with ballots

$$\begin{array}{rl}{\succ }_1& :x\succ a\succ b,\\ {\succ }_2& :x\succ a\succ b,\\ {\succ }_3& :b\succ a\succ x.\end{array}$$

Compare the Kemeny proposals $a\succ x\succ b$ and $x\succ a\succ b$: these are candidate collective rankings, not additional voters’ ballots. Each cell below shows the proposal’s order for one pair and the number of voters who disagree with it. The first proposal is not assumed optimal in this numerical illustration.

The third voter opposes both unchanged orders, so these pairs contribute $Q=2$, not zero, to each score. Only their contribution to the score difference is zero.

(3) Compare one reversed pair

Fix any $j\in \{1,\dots ,s\}$. Since $a_j\ne x$, the Condorcet assumption gives $N_R(x,a_j)>n/2$. Every voter ranks exactly one of $x,a_j$ above the other: completeness rules out incomparability, and strictness rules out ties. Hence

$$\begin{array}{rl}{N}_R(x,a_j)+N_R(a_j,x)& =n,\\ N_R(a_j,x)& =n-N_R(x,a_j)\\ & <n-\frac{n}{2}=\frac{n}{2}.\end{array}$$

Combining the two bounds yields

$$\underset{>n/2}{\underbrace{N_R(x,a_j)}}-\underset{<n/2}{\underbrace{N_R(a_j,x)}}>0.$$

(4) Sum the decreases

Subtracting the score expressions from step 2 gives

$$\begin{array}{rl}& \mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\ast },R)-\mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\prime },R)\\ & =\left(Q+\sum _{j=1}^s{N}_R(x,a_j)\right)-\left(Q+\sum _{j=1}^s{N}_R(a_j,x)\right)\\ & =\sum _{j=1}^s\underset{>0}{\underbrace{(N_R(x,a_j)-N_R(a_j,x))}}\\ & >0.\end{array}$$

The last inequality holds because $s\ge 1$: the sum contains at least one term, and every term is positive. Thus

$$\mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\prime },R)<\mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\ast },R).$$

But ${\succ }^{\ast }$ is a Kemeny ranking, so its score is minimal among all complete, strict rankings, including ${\succ }^{\prime }$:

$$\mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\ast },R)\le \mathrm{KT}\text{-}\mathrm{dist}({\succ }^{\prime },R).$$

This is a contradiction. Therefore every Kemeny ranking places $x$ first. At least one minimum exists because the set of rankings is finite and non-empty, so

$${\lambda }_{\mathrm{Kemeny}}(R)=\{x\}.$$

Neutrality

Kemeny’s rule is neutral. Renaming alternatives by a permutation $\pi$ preserves which pairs two rankings disagree on. Thus every proposal retains its Kemeny score:

$$\mathrm{KT}\text{-}\mathrm{dist}(\pi (\succ ),\pi (R))=\mathrm{KT}\text{-}\mathrm{dist}(\succ ,R).$$

Renaming is a bijection on possible rankings, so it also renames exactly the minimisers. Writing $F(R)$ for the set of Kemeny consensuses,

$$F(\pi (R))=\pi (F(R)),{\lambda }_{\mathrm{Kemeny}}(\pi (R))=\pi ({\lambda }_{\mathrm{Kemeny}}(R)).$$

The second equality follows because renaming preserves positions: the first alternative is simply renamed too. An additional tie-breaking rule need not preserve neutrality.

Reinforcement

Kemeny’s consensus-ranking rule is reinforcing. Let $F(R)$ again denote the set of optimal whole rankings. For two profiles over the same alternatives, merging the ballots adds each proposal’s scores:

$$\mathrm{KT}\text{-}\mathrm{dist}(\succ ,R_1\uplus R_2)=\mathrm{KT}\text{-}\mathrm{dist}(\succ ,R_1)+\mathrm{KT}\text{-}\mathrm{dist}(\succ ,R_2).$$

Let $s_1,s_2$ be the minimum scores in the two profiles. A ranking optimal for both attains $s_1+s_2$. Any other ranking exceeds at least one minimum and cannot compensate by going below the other. Hence

$$F(R_1)\cap F(R_2)\ne \varnothing ⟹F(R_1\uplus R_2)=F(R_1)\cap F(R_2).$$

This establishes reinforcement for consensuses. It must not be conflated with reinforcement of the alternative-valued rule ${\lambda }_{\mathrm{Kemeny}}$: two electorates can share a first-place candidate without sharing an optimal whole ranking. The argument above requires agreement on a ranking, not merely its first alternative.

Winner Determination

The decision problem asks whether a given alternative $x$ is first in some minimum-total-distance ranking of the submitted profile. Determining this is NP-hard.

For $n$ voters and $m$ alternatives, one proposed ranking can be scored by checking all $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ pairs against every voter, using $O(n{m}^2)$ time under unit-cost arithmetic. The difficulty is finding a globally optimal ranking, not evaluating one proposal. Exhaustively checking all $m!$ rankings is one possible approach, but its running time alone is not a proof of NP-nardness.