Kemeny Score (COMSOC)

Definition

Kemeny Score ( COMSOC)

The Kemeny score of a proposed ranking $\succ$ is its total Kendall–tau distance to the voters’ rankings. For a profile $R=({\succ }_1,\dots ,{\succ }_n)$ over the same alternatives,

$$\mathrm{KT}\text{-}\mathrm{dist}(\succ ,R):=\sum _{i\in [n]}\mathrm{KT}(\succ ,{\succ }_i)=\sum _{x\succ y}{N}_R(y,x)$$

Each voter contributes one distance. Smaller scores mean less total pairwise disagreement; a Kemeny consensus is a ranking attaining the minimum over all complete, strict rankings.

This compares one proposal with a profile, not voters with one another as in the total pairwise distance.

Count by Voter or by Alternative Pair

Fix a proposed ranking $\succ$. Each disagreement involves one voter and one pair of alternatives. If the proposal puts $x$ above $y$, precisely the $N_R(y,x)$ voters preferring $y$ to $x$ disagree. Here $N_R$ is the pairwise support function. Counting these same disagreements in two orders gives

$$\mathrm{KT}\text{-}\mathrm{dist}(\succ ,R)=\underset{\text{voter by voter}}{\underbrace{\sum _i\mathrm{KT}(\succ ,{\succ }_i)}}=\underset{\text{alternative pair by alternative pair}}{\underbrace{\sum _{x\succ y}{N}_R(y,x)}}.$$

The proposal’s order chooses one orientation of each pair, so the last sum counts each pair once.

Proposal: a before b before c

Use the ballots $abc,cab,cba$, where $abc$ means $a\succ b\succ c$. A cell is $1$ when its voter disagrees with the column’s order.

Count the same five cells by row or column:

$$\mathrm{KT}\text{-}\mathrm{dist}(abc,R)=\underset{\text{by voter}}{\underbrace{0+2+3}}=\underset{\text{by alternative pair}}{\underbrace{1+2+2}}=5.$$

This is the proposal’s Kemeny score, not the profile total of $6$.

Proposal: c before a before b

Reverse the columns $a\succ c$ and $b\succ c$. In each, two disagreements become one; the $a\succ b$ column stays unchanged.

The Kemeny score drops to $1+1+1=3$. Every pair splits the voters $2:1$, so any ranking incurs at least one disagreement per pair. This ranking attains that lower bound and is a Kemeny consensus.

This works because the three majority choices form a ranking. If they formed a cycle, no ranking could follow them all.