The structure and complexity of sports elimination numbers

Identifying the teams that are already eliminated from contention for first place of a sports league, is a classic problem that has been widely used t o illustrate the application of linear programming and network flow. In the classic setting each game is played between two teams and the first place goes to the team with the greatest total wins. Recently, two papers [W], [A EHO] detailed a surprising structural fact in the classic setting: At any p oint in the season, there is a computable threshold IV such that for any te am i, i is eliminated (has no chance to win or tic for first place) if and only if i cannot win W or more games. They used this threshold to speed tip the identification of eliminated teams. In both papers the proofs of the e xistence of a threshold are tied to the computational methods used to find it. In this paper we show that thresholds exist for a wide range of elimination problems (including European football), thus greatly generalizing the clas sic setting; we use a simpler proof which is not connected to any particula r computational method; we resolve the more refined issue (in the classic s etting) of which teams have a chance to be the strict winner of the most ga mes; examine these issues in the context of multidivision leagues with play offs and wildcards; and establish NP-hardness results for certain eliminati on questions.