Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

When is a Team Eliminated?

Student-Run Research Seminar

Speaker: Chip Martel, CS, UC Davis
Location: 593 Kerr
Start time: Mon, Oct 9 2000, 2:10PM

Joint work with Dan Gusfield CS UCD. 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 cite{KW98} and cite{AH} detailed a surprising structural fact in the classic. setting: At any point in the season, there is a computable threshold $W$ such that a team is eliminated (has no chance to win or tie for first place) if and only if it 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 and greatly generalizing the classical setting), via a simpler proof 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 {it strict} winner of the most games; examine these issues in the context of multi-division leagues with playoffs and wildcards; and establish NP-hardness results for certain elimination questions.