Don Coppersmith, Lisa Fleischer and Atri Rudra

Ordering by Weighted Number of Wins Gives a Good Ranking for Weighted Tournaments

Abstract : Consider a sports tournament where some number of players play each other. After all the games are completed, one would like to rank the players with as few inconsistencies as possible. By an inconsistency we mean a higher ranked player actually lost to a lower ranked player. This problem was shown to be NP-hard recently. A natural heuristic to generate such a ranking is to rank the players according to their number of wins (with ties broken in some manner). We show that the above efficient scheme results in a solution that has at most 5 times as many inconsistencies as the optimal solution. We also show that our analysis is tight, that is, there are tournaments on which ranking by number of wins can have 5 times as many upsets as the optimal ranking. Our results also hold for the more general case when each pair of players play each other multiple number of times (this number has to be the same for all pairs). This has implications for the related NP-hard problem of rank aggregation. In rank aggregation the inputs are rankings of some candidates. The goal is to output a single ranking that is as consistent as possible with the all input rankings. Our work proves that a method called the Borda's method, a heuristic which was proposed more than a century ago, provably has at most 5 times as many inconsistencies as the optimal solution.
Versions