On the Average-Case Complexity of Predicting Round-Robin Tournaments

Round-robin tournaments are, besides single-elimination tournaments, by far the most prominent and widely used tournament format in sports and other competitions. We study the average-case complexity of two problems related to the prediction of roundrobin tournaments, namely first the problem of calculating the championship probability of a team and second the well-known sports elimination problem where one has to decide whether a team still has the possibility to become champion. We show that, under certain assumptions, these problems are solvable in expected polynomial time for a distribution which, for the algorithm used, seems to dominate the distribution of real instances in terms of complexity, despite their computational worst-case hardness.