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.