Total Pairwise Kendall-Tau Distance (COMSOC)

Definition

Total Pairwise Kendall–Tau Distance ( COMSOC)

The total pairwise Kendall–tau distance of a profile $R=({\succ }_1,\dots ,{\succ }_n)$ sums the Kendall–tau distances between every pair of voters’ rankings:

$$\mathrm{KT}\text{-}\mathrm{dist}(R):=\sum _{i,j\in [n],i<j}\mathrm{KT}({\succ }_i,{\succ }_j)=\sum _{i,j\in [n],i<j}|\mathrm{disag}({\succ }_i,{\succ }_j)|.$$

Here $\mathrm{disag}$ is the disagreement set. The restriction $i<j$ counts each voter pair once. Different voters remain separate even when they submit identical rankings.

Upper Bound

Let $n$ be the number of voters and $m=|C|$ the number of alternatives. There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ voter pairs. Each pair can disagree on at most the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ pairs of alternatives, so

$$\begin{array}{rl}\mathrm{KT}({\succ }_i,{\succ }_j)& \le \left(\genfrac{}{}{0ex}{}{m}{2}\right),\\ \mathrm{KT}\text{-}\mathrm{dist}(R)& \le \sum _{i,j\in [n],i<j}\left(\genfrac{}{}{0ex}{}{m}{2}\right)\\ & =\underset{\text{voter pairs}}{\underbrace{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}}\underset{\text{maximum disagreements per pair}}{\underbrace{\left(\genfrac{}{}{0ex}{}{m}{2}\right)}}.\end{array}$$

This is an upper bound, not necessarily an attainable total: all voter pairs need not be able to attain their individual maximum simultaneously.

Distinction from the Kemeny Objective

This total compares voters with one another. A Kemeny score instead compares one proposed ranking with every voter. For the ballots $abc,cab,cba$, the profile total is $6$, while the proposal $abc$ has score $5$ and the optimal proposal $cab$ has score $3$. See the two ways to count a proposal’s disagreements.

Example

Three voter pairs

Let the three ballots be $a{\succ }_{1}b{\succ }_{1}c$, $c{\succ }_{2}a{\succ }_{2}b$, and $c{\succ }_{3}b{\succ }_{3}a$. Their disagreement sets have sizes $2,3,1$, so

$$\mathrm{KT}\text{-}\mathrm{dist}(R)=\underset{\text{voters 1,2}}{\underbrace{2}}+\underset{\text{voters 1,3}}{\underbrace{3}}+\underset{\text{voters 2,3}}{\underbrace{1}}=6.$$