Random Walks to Football Rankings

The national championship of U.S. college football is decided at the end of the season in a climactic game that is supposed to match the top two NCAA Division I (FBS) teams. Year after year, controversy has dogged the selection of those two teams.

The selection process is hampered by the fact that the 119 teams that belong to the division play only 10 to 13 games. Each team doesn't play every other team. Moreover, not all schedules are created equal. Some teams play against much stronger opponents than others do. And it's not even clear what "top two" means. Is it the two teams with the best overall record for the season or the two teams playing best at the end of the season?

The year 1998 saw the introduction of a complex mathematical formula to determine which two teams play for the national championship. The formula produced the Bowl Championship Series (BCS) standings, and the winner of the final bowl game matching the top two teams in the standings became the national champion.

Over the years, the formula has been tweaked and the system modified to remove flaws and better match human expectations. In its latest iteration, the BCS system simply averages a given set of polls and computer rankings. And the results continue to arouse skepticism.

Mathematically and computationally inclined football fans have proposed a variety of alternative ranking schemes—many quite complicated—that purportedly give "fairer" results. One interesting contender is a scheme developed by Thomas Callaghan, now a graduate student at Stanford University, Peter J. Mucha of the University of North Carolina at Chapel Hill, and Mason A. Porter of the University of Oxford.

"A simply-explained algorithm constructed by crudely mimicking the behavior of voters can provide reasonable rankings," Callaghan, Mucha, and Porter claim. They describe their scheme in the November American Mathematical Monthly.

In their ranking model, the mathematicians start with a collection of random walkers (voters), each of which declares its preference for a particular team. Each voter then repeatedly selects a game at random from its preferred team's schedule and decides whether to change its preference to the opposing team as biased by the game's outcome. So, if team i beats team j, the average rate at which a walker voting for team j changes its allegiance to team i is proportional to p, and the rate at which a walker already voting for team i switches to team j is proportional to 1 – p. The scheme hinges on the selection of an appropriate value for p. Note that the algorithm doesn't take into account the date on which games are played, a factor that some human analysts like to include.

Overall, the total number of votes cast for each team by all random-walking voters repeating this process indefinitely adds up to a ranking of the top teams. Remarkably, this simplistic ranking algorithm yields reasonable results.

Here's the current 2007 random walker top 10 (with p = 0.75), taking into account games played through Saturday, Nov. 10.


When compared with the BCS standings, the random walker algorithm shuffles the order a little (Oregon ranks higher than LSU, for example), and includes Florida instead of Virginia Tech. Nonetheless, there's a remarkably close match between the two rankings.

The following weekend, Oregon and Oklahoma lost. These results reshuffled the standings. The random walker model put LSU at the top, followed by Arizona State, Oregon, West Virginia, Georgia, Missouri, Kansas, Ohio State, Boston College, and Florida.

We'll see what happens as the regular season ends and the bowl games begin.

Last year, the random walker algorithm put Florida at the top at the end of the regular season, followed by USC. But the two teams didn't end up playing each other in the BCS national championship game. Instead, Florida defeated Ohio State in the championship game and USC beat Michigan.

"We remain committed to the proposition that the use of algorithmic rankings for determining the college football postseason will only become widely accepted when those rankings have been reasonably explained to the general public," Callaghan, Mucha, and Porter conclude. "In that context, the random walker rankings . . . provide reasonable ways to rank teams algorithmically with methods that can be easily explained and broadly understood."

References:

Callaghan, T., P.J. Mucha, and M.A. Porter. 2007. Random walker ranking for NCAA Division I-A football. American Mathematical Monthly 114(November):761-777.

______. 2004. The Bowl Championship Series: A mathematical review. Notices of the American Mathematical Society 51(September):887-893.

Peterson, I. 2004. College football, rankings, and wandering monkeys. MAA Online (Sept. 6).

______. 1998. Who's really no. 1? MAA Online (Dec. 14).

Information about rankings of U.S. college football teams can be found at http://homepages.cae.wisc.edu/~dwilson/rsfc/rate/.