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 to 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 detailed a surprising structural fact in the classic setting: At any point in the season, there is a computable threshold W such that for any team i , i is eliminated (has no chance to win or tie for first place) if and only if i cannot win W or more games. They used this threshold to speed up the identification of eliminated teams. In both papers the proofs of the existence 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 classic setting; we use a simpler proof which is not connected to any particular computational method; we resolve the more refined issue (in the classic setting) of which teams have a chance to be the strict winner of the most games; examine these issues in the context of multidivision leagues with playoffs and wildcards; and establish NP-hardness results for certain elimination questions.