Monday, December 04, 2006

A challenge for algorithm designers

This post inspired by one on Freedom to Tinker.

Every year the national collegiate football championship is a matter of much discussion and bitter dispute. The Bowl Championship Series invariably produces a title game that many vocal partisans object to, saying that it fails to match the top two teams in the country. And every year the formula for selecting the top two teams is modified in response to complaints about the results of the previous year's formula. (Talk about generals always preparing to fight the last war!)

Even if we assume that there is a single "best" college football team each year, determining objectively which team that is presents major problems. Especially in games between nearly equal teams, there is always a factor of chance, i.e., the best team does not always win ("but that's the way to bet"). So what is available is a limited number of not-guaranteed-accurate comparisons between teams ("the regular season") plus the opportunity to stage an even more limited number of chosen, but also not-guaranteed-accurate comparisons (the bowl games).

The challenge is to
  1. Define what it would mean to generate an optimal bowl schedule and an optimal post-bowl ranking of the top teams.
  2. Supply an algorithm that is either provably optimal, or provably within some small epsilon of optimum, to generate a schedule and a ranking.

Labels: ,


Post a Comment