6
$\begingroup$

This question was posed by my colleague Torbjörn Lundh in his paper Which Ball is the Roundest? A Suggested Tournament Stability Index, Journal of Quantitative Analysis in Sports 2(3), 2006. We have discussed it a number of times without finding a solution.

The context is a tournament, where $n$ players or teams meet pairwise in games. We assume for simplicity that each game results in one team winning and the other losing (no ties). Given the results of all $n \choose 2$ games, the task is to produce a ranking of the teams, that is, to order them from best to worst.

This sort of problem goes back at least to the 19th century, and arises when a number of subjects are asked to rank for instance the taste of different wines. It's hard to directly produce an ordering of say ten glasses of wine based on tasting them. It's much easier to repeatedly make pairwise comparisons, is wine A better or worse than wine B? But the final answers need not be consistent, and we arrive at the problem of interpreting a series of such pairwise comparisons.

One possibility is the method used in sports tournaments, where teams are ranked according to the number of won games (with various tiebreak rules when the scores are equal). But we might also be interested in the ranking that minimizes the number of inconsistencies, that is, minimizes the number of games that are won by the lower ranked team.

Is there a polynomial time algorithm that finds, from a table of results of all $n \choose 2$ games, a ranking with minimum number of inconsistencies?

It's easy to see that a ranking that minimizes the number of inconsistencies might have to place a team with fewer victories above a team with more victories. This is because a ranking minimizing the number of inconsistencies can have no inconsistencies between teams adjacent in the ranking (if there were, we could improve by just switching them). So suppose in a tournament that team A loses to team B and wins all other games, team B loses two other games and all other teams win fewer games. Then it can't be optimal in the sense of minimizing the number of inconsistencies to rank A first and B second. Another example is shown in Torbjörn's paper.

There are various superficially similar problems that are known to be NP-complete (Torbjörn mentions in his paper the directed optimal linear arrangement and the quadratic assignment problem), and therefore it would be quite surprising if there were an efficient algorithm for finding a ranking that minimizes the number of inconsistencies. But we haven't been able to encode any known NP-complete problem in terms of a tournament requiring a ranking.

$\endgroup$
  • 2
    $\begingroup$ Did you look at the feedback arc set problem for tournaments ? It was proved to be NP-hard by Alon :tau.ac.il/~nogaa/PDFS/paley.pdf‎ and separately Charbit, Thomassé and Yeo: liafa.jussieu.fr/~charbit/Recherche/publis/minfastour.ps $\endgroup$ – Arnaud Jan 14 '14 at 14:36
  • $\begingroup$ Arnaud, thanks! No, we weren't aware of those papers. I haven't looked at them in detail yet, but from the introductions it seems they settle the question (well, apart from the P vs NP issue of course). $\endgroup$ – Johan Wästlund Jan 14 '14 at 17:08
  • $\begingroup$ In relation to the paper by Alon see also here: cs.cmu.edu/~conitzer/slater.pdf - "a more direct proof of this result" $\endgroup$ – Waldemar Jan 14 '14 at 18:11
  • $\begingroup$ Arnaud and Waldemar, thank you for the links! Arnaud, if you make your comment an answer, I would be happy to accept it. $\endgroup$ – Johan Wästlund Jan 17 '14 at 9:19
3
$\begingroup$

The problem you are looking for is called the Feedback Arc Set problem for tournaments (FAST). It was proved to be NP-hard by Alon:

http://www.tau.ac.il/~nogaa/PDFS/paley.pdf

and separately Charbit, Thomassé and Yeo:

http://www.liafa.jussieu.fr/~charbit/Recherche/publis/minfastour.ps

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.