Rank aggregation is a problem with many important applications and naive approaches to it go wrong in subtle ways.
Let’s say that your national Quidditch league is dominated by five major wizard sports newspapers. Yes, the ones with moving images and everything. Every week after the games, each of them publishes a ranking of the star players. For now, let’s suppose that the set of players under investigation is always the same, as the problem becomes a bit more complicated otherwise.
The Athletic Wizard: Alicia Spinnet, Ginny Weasley, Gwendolyn Morgan, Robin Higgy, Debbie Muntz
The Daily Prophet: Alicia, Ginny, Robin, Gwendolyn, Debbie
Quidditch News: Robin, Ginny, Gwendolyn, Debbie, Alicia
Seeker Weekly: Gwendolyn, Ginny, Robin, Debbie, Alicia
The Quibbler: Debbie, Ginny, Robin, Gwendolyn, Alicia
As you can see, there’s quite a bit of disagreement and personal taste involved. You didn’t get to watch all of the games, but you’d like to make a decision on who the best players were, by somehow aggregating the opinions of the popular newspapers. An easy option would be to pretend that each newspaper votes for the player that they rank #1, and ignore the rest. As Alicia Spinnet is the only player getting two nominations for best player, she should win best player, right?
Upon closer inspection, Alicia seems very controversial, loved by two but hated by five of the newspaper. Ginny, on the other hand, didn’t stand out as best player to anybody, but she was uniformly considered runner-up. There should be some way to account for this. It would be nice if we would have a method of finding an optimal ranking that maximizes some sort of agreement with the opinions we are trying to aggregate.
Kendall’s Tau distance
One of the most interesting ways to measure disagreement between rankings is the Tau statistic introduced by Kendall. It essentially measures the number of pairwise disagreements between two rankings. Since you can think of it as the number of flips you need to perform on a ranking to turn it into the other, it is sometimes called bubble-sort distance.
While the closely-related Tau correlation coefficient is implemented in Scipy as scipy.stats.kendalltau, let’s code it ourselves in a simpler way.
Now we can represent a rank as a numpy vector, with missing values.
Two rankings that agree completely should have a distance of 0.
The Athletic Wizard seems to be closer to the Daily Prophet than to Seeker Weekly.
Kemeny-Young rank aggregation
Now that we have a distance metric, we can formulate a loss function to minimize in rank-space. We are looking for a ranking \(\hat\tau\) that satisfies \[ \sum_i d(\hat\tau, \tau_i) \leq \sum_i d(\tau, \tau_i) \text{ for all } \tau \]
This aggregation method was proposed by John Kemeny [1], and later shown by Peyton Young to be a maximum likelihood estimator of pairwise preferences under the assumption that a voter will randomly flip two candidates from the true ranking is the same \(p < 0.5\) [2].
For rankings of small length, one way to compute this optimal aggregation is by comparing the scores of all possible rankings, in other words, a brute-force approach:
The brute-force approach is, as you can see, simple to understand and quick to code. However, the number of total ranks of size \(n\) is \(n!\), so this approach quickly becomes infeasible for real-world problems. Unfortunately, it turns out that this problem (along with many related problems in rank-world) is NP-hard even for only four voters [3]. There have been quite a few approaches and approximations. In many cases, such as search results aggregation, approximations are good enough. For the cases where an exact solution is required, a formulation as a constrained integer program is given in [4].
We build a weighted directed graph \(G = (V, E)\) with the candidates as vertices. The edges are defined as such: for every pair of candidates \(i, j\), let \(\#\{i > j\}\) denote the number of voters who rank \(i\) higher than \(j\). Draw an edge \(e\) between each \(i, j\) with weight \(w_e = |\#\{i > j\} - \#\{j > i\}|\) (if nonzero, of course). The orientation of the edge is from the less preferred to the more preferred node.
The formulation is based on the alternative interpretation of the Kemeny optimal aggregation as the ranking that minimizes the weights of edges it disagrees with:
\[
\operatorname{minimize} \sum_{e \in E} w_e x_e \
\operatorname{subject to} \
\forall i \neq j \in V, x_{ij} + x_{ji} = 1 \
\forall i \neq j \neq k \neq i \in V, x_{ij} + x_{jk} + x_{ki} \geq 1 \]
In the above problem, all variables are integer, and effectively binary under the other constraints. The interpretation is that \(x_{ij} = 1\) if, in the aggregated rank, \(i\) is ranked lower than \(j\).
The constraints essentially impose that the variables define a total order. The first set of constraints enforce antisymmetry and totality: either \(i\) is ranked lower than \(j\) or the other way around. The second set of constraints enforce transitivity.
Now, let’s solve the linear program with the LGPL-licensed lpsolve. It conveniently comes with a Python interface.
We get the same result as in the brute-force case. However, it’s much faster. Let’s verify this, and in the process, also test that we always get the same result.
You can see that the brute force approach is a bit worse than exponential, while the integer programming approach is more reasonable and also is less sensitive to the number of voters being aggregated. We therefore have a reasonably fast efficient exact solution to the rank aggregation problem on small datasets.
References
[1] J Kemeny. Mathematics without numbers, 1959
[2] HP Young. Condorcet’s theory of voting, 1988
[3] JJ Bartholdi III, CA Tovey, MA Trick. The computational difficulty of manipulating an election, 1989
[4] V Conitzer, A Davenport, J Kalagnanam. Improved bounds for computing Kemeny rankings, 2006