Footrule method
The footrule method is a rank-aggregation or single-winner voting method that returns the social order (ranking of candidates) that minimizes the average Spearman footrule distance to the voters' ballots.
The Spearman footrule distance is defined as the sum of the absolute distances between candidates in the rankings being compared.[1] For instance, when comparing the ranking A>B>C>D and B>C>A>D, the footrule distance is calculated in this way:
| Candidate | Rank in first ranking | Rank in second ranking | Absolute distance |
|---|---|---|---|
| A | 1 | 3 | 2 |
| B | 2 | 1 | 1 |
| C | 3 | 2 | 1 |
| D | 4 | 4 | 0 |
The footrule distance is .
The problem of finding the optimal social order can be reduced to minimum weight bipartite matching, which can be solved by the Hungarian algorithm in time, where is the number of candidates.[2]
The method is not well known as a voting method, so little work has been done in determining its criterion compliances. However, since the footrule distance is at most twice the Kendall-tau distance, the social order has a Kemeny distance at most twice that of the one produced by the Kemeny-Young method. It has thus gained some attention in the field of web search as a polynomial-time approximation to the Kemeny method.
This page is a stub - please add to it.
References
- ↑ * Kendall, Maurice G. (1948). Rank correlation methods. Griffin.
- ↑ Dwork, Cynthia; Kumar, Ravi; Naor, Moni; Sivakumar, D. (2001). Rank aggregation methods for the Web. New York, New York, USA: ACM Press. doi:10.1145/371920.372165.