Kendall-Tau Distance (COMSOC)

comsoc

Definition

Kendall-Tau Distance

In COMSOC, the Kendall-Tau distance between two preference rankings is the number of unordered pairs of alternatives on which the two rankings disagree.

Let $C$ be a set of alternatives and let ${\succ }_i,{\succ }_j\in \mathcal{L}(C)$ be two rankings. Define

$$\mathrm{disag}({\succ }_i,{\succ }_j):=\left\{\{x,y\}:x,y\in C,x\ne y,x{\succ }_{i}y\text{ and }y{\succ }_{j}x\right\}.$$

The Kendall-Tau distance is

$$\mathrm{KT}({\succ }_i,{\succ }_j):=|\mathrm{disag}({\succ }_i,{\succ }_j)|.$$

For a ranking $\succ \in \mathcal{L}(C)$ and a preference profile $R=({\succ }_1,\dots ,{\succ }_n)$, its distance to the profile is

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

This profile distance is also called the Kemeny score of $\succ$.

Alternative form

For each pair $x,y\in C$, let

$$R(x,y):=\{i:x{\succ }_{i}y\}$$

be the set of voters who rank $x$ above $y$. Then

$$\mathrm{KT}(\succ ,R)=\sum _{x\succ y}|R(y,x)|.$$

Each ordered pair $x\succ y$ in the proposed consensus pays one unit for every voter who ranks the pair in the opposite order.

Example

Distance to a profile

Let

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

For the ranking $abc$, the disagreements are

$$\mathrm{KT}(abc,abc)=0,\mathrm{KT}(abc,cab)=2,\mathrm{KT}(abc,cba)=3.$$

Hence

$$\mathrm{KT}(abc,R)=0+2+3=5.$$

Equivalently,

$$\mathrm{KT}(abc,R)=|R(b,a)|+|R(c,a)|+|R(c,b)|=1+2+2=5.$$