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