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/.

Triangular Numbers and Magic Squares

It sometimes takes years—even decades—to solve a seemingly simple problem. The October American Mathematical Monthly features the solution to a problem originally posed 66 years ago—one that concerns triangular numbers and magic squares.

A triangular number can be represented as a triangular grid of points, in which the first row contains one element and each succeeding row has one more element than the previous one. The first few triangular numbers are 1, 3, 6, 10, 15, and 21. If you include 0 as the first number, the nth triangular number is given by the formula n(n – 1)/2.


Triangular numbers depicted as triangular arrays of dots. Courtesy of Christian Boyer.

A magic square consists of a set of distinct integers arranged in the form of a square so that the numbers in each row, column, and diagonal all add up to the same total.

In 1941, the American Mathematical Monthly published the following problem, posed by Royal Vale Heath, widely known for creating ingenious mathematical puzzles: "What is the smallest value of n for which the n² triangular numbers 0, 1, 3, 6, 10, . . . n²(n² – 1)/2 can be arranged to form a magic square?"

At that time, the journal's "Problems and Solutions" section was edited by Otto Dunkel, Orrin Frink Jr., and H.S.M. Coxeter.

A year later, Heath himself proposed a partial solution. He noted that a magic square that is still magic after the original entries are all squared (a bimagic square) can itself be used directly to construct a magic square of triangular numbers. Heath wrote, "Clearly, the magic property will still be retained if each of the original numbers is subtracted from its square. The resulting numbers are all even, and their halves are the triangular numbers."

Starting with a known bimagic square of order 8 (an eight-by-eight array), Heath then constructed a magic square of 64 triangular numbers, from 0 to 2016, with magic sum of 5460. He admitted, however, that a smaller set of distinct triangular numbers might also form a magic square.

So, Heath's puzzle remained unsolved until it finally came to the attention of Christian Boyer, who has recently put a lot of time and effort into exploring magic squares. Boyer proved that magic squares of triangular numbers are impossible for orders 3, 4, and 5. He did, however, discover magic squares using 36 triangular numbers from 0 to 630 (with a magic sum equal to 1295).

Here's an example.


Boyer also found that there are magic squares of order 7, which use the first 49 triangular numbers, starting with 0. Furthermore, you can obtain magic squares of orders 6 and 7 when you start with 1 instead of 0.

What is the smallest order n possible if you allow the use of any triangular numbers rather than consecutive ones? Boyer has found the first four-by-four and five-by-five magic squares of distinct triangular numbers.


But it is still unknown whether a three-by-three magic square of distinct triangular numbers exists.

References:

Boyer, Christian. 2007. Better late than never (Solution to problem E 496). American Mathematical Monthly 114(October):745-746. Expanded version of this solution.

Heath, R.V. 1942. A magic square of triangular numbers (Solutions: E 496). American Mathematical Monthly 49(August-September):476.

______. 1941. Problems for solution: E 496. American Mathematical Monthly 48(December):699.

Peterson, I. 2005. Magic squares of squares. MAA Online (June 27).