Kemeny's Rule (COMSOC)

comsoc

Definition

Kemeny's Rule

In COMSOC, Kemeny’s Rule is a voting rule that chooses rankings with minimum Kendall-Tau distance to the voters’ preference profile, and then selects the alternatives that can appear first in such rankings.

Let $C$ be a set of alternatives and let

$$R:=({\succ }_1,\dots ,{\succ }_n)$$

be a preference profile. A Kemeny consensus is a ranking

$${\succ }^{\ast }\in \mathcal{L}(C)$$

that minimises

$$\mathrm{KT}({\succ }^{\ast },R):=\sum _{i=1}^n\mathrm{KT}({\succ }^{\ast },{\succ }_i).$$

An alternative $x\in C$ is a Kemeny winner if there exists a Kemeny consensus ${\succ }^{\ast }$ that ranks $x$ first. Equivalently,

$${\lambda }_{\mathrm{Kemeny}}(R):=\{x\in C:\exists {\succ }^{\ast }\in \arg \underset{\succ \in \mathcal{L}(C)}{\min }\mathrm{KT}(\succ ,R)\text{ with }x\text{ first in }{\succ }^{\ast }\}.$$

Mechanism

Median ranking

Kemeny’s Rule searches for a ranking that is closest to all voter rankings in total Kendall-Tau distance. Each pairwise disagreement between the consensus and a voter contributes one unit to the score.

Example

Kemeny consensus

Let

$$R:=(abc,cab,cba).$$

The Kendall-Tau distances of all rankings to $R$ are:

ranking	distance to $R$
$abc$	$5$
$acb$	$4$
$bac$	$6$
$bca$	$5$
$cab$	$3$
$cba$	$4$

Thus $cab$ is the unique Kemeny consensus, and $c$ is the unique Kemeny winner.

Properties

Condorcet consistency

Kemeny’s Rule is a Condorcet consistent voting rule. If a Condorcet winner exists, then it is first-ranked in every Kemeny consensus.

Neutrality and reinforcement

The lecture notes state the Young—Levenglick characterisation: Kemeny’s Rule is the only voting rule satisfying neutrality, reinforcement, and Condorcet consistency.

Computational hardness

The lecture notes state that determining a Kemeny winner is NP-hard. The associated Kemeny Score decision problem is NP-complete.