Kendall-Tau Distance (COMSOC)

Definition

Kendall– Distance (COMSOC)

The Kendall– distance between two complete, strict rankings over the same alternatives counts the pairs they order differently:

Here is the disagreement set: each pair ranked oppositely contributes one. This distance is a metric on the set of complete, strict rankings. Summing it over all voter pairs gives the total pairwise distance of a profile.

Intuition

Count pairs that reverse order, not candidates that change positions. Compare the current ranking with the fixed target:

Both rankings agree on and on everyone being above . Only ‘s order relative to and differs, so the distance is . Swap the boxed neighbours in the current ranking.

Now is above , as required. This swap fixes exactly that pair; is still above , so one disagreement remains. Swap the boxed neighbours .

The rankings now agree. Two adjacent swaps suffice, and fewer cannot: each adjacent swap reverses only one pair, while the original rankings disagreed on two. Thus their Kendall– distance is .

The same argument applies generally: each disagreement requires a swap, and swapping adjacent pairs that disagree with the target removes one disagreement at a time. Hence the distance equals the minimum number of adjacent swaps.

Maximum Distance

There are unordered pairs of distinct alternatives, each contributing at most one:

Identical rankings attain zero. Reversing a ranking reverses every pair and attains the maximum.

Example

Two pairwise disagreements

Compare

Only the pairs and reverse order. Thus , realised by two adjacent swaps:

In contrast, reverses all pairs of the first ranking and has distance from it.