# Using Darwin to Rank: Bracket Advice from Kathryn Pedings-Behling

Kathryn Pedings-Behling is is a high school math teacher by day and a graduate student by night. She teaches math at the Charleston Charter School for Math and Science where she heads the math department and the AP math program. She graduated from the College of Charleston in 2008 with a B.S. in Mathematics where she met Dr. Amy Langville who became her master’s thesis adviser. Kathryn will graduate with an M.S. in Mathematics from the College of Charleston in May. In her post below, she explains how Darwin comes into play when ranking sports teams.

It sounds crazy, doesn’t it? What in the world does Darwin have to do with ranking sports teams? This was the same question I asked myself as I entered an independent study course with Dr. Amy Langville on the topic of evolutionary optimization. Okay, so now you are possibly seeing the connection: Darwin and evolution. But you are still stuck on this ranking thing. How is it related?

The process of evolutionary optimization takes Darwinian ideas of mating, mutating, fitness, and survival of the fittest and puts them in the context of ranking. I must admit that I am a total sucker for topics like this. The hardest part of making math your life is trying to have conversations with non-math folks about what it is that you are passionate about in this field. However, this was something that I knew “normal” people could wrap their head around. Any person who has been through an acceptable level of education knows the basics about evolution. The members of a population continue to mate and have offspring. Every now and then a mutation is thrown in. Only the fittest population members survive to then create more offspring. If you know these things, you can understand my ranking method! It’s that simple!

Before getting to the meat of the ranking method, there are a few important fundamental concepts. The members of your population are each a different possible ranking of your teams that is expressed mathematically as a permutation vector. You can mate these rankings by performing any of the rank aggregation methods found in the book Who’s #1?, such as average rank or Borda count. Mutating uses much simpler, random actions such as switching two teams or swapping the order of a group of teams, and is much more cost effective to perform on a large set of teams.

How do you know if your mating and mutating has produced a good offspring? This leads to a much deeper question: how do you define what it means to have a quality ranking? Well, if I knew the exact to answer that question, I would win the ESPN March Madness Bracketology Competition every single year, significantly boosting my popularity as a high school math teacher. However, we believe that we have a way to measure the relative quality of a ranking.

To understand this measure (which in Darwinian terms is the fitness of our population members), you need a new linear algebra definition called hillside form of a matrix. Hillside form is very easy to understand: the entries of each row are increasing from left to right, the entries of each column are decreasing from top to bottom, and the lower triangular of the matrix is filled with zeros (this last part of the definition is optional based on what type of data matrix you start with). Below you will find an example of a matrix in hillside form:

Hillside form makes sense in the context of ranking sports teams because, in a perfect scenario, you want the first place team to beat the second place team by a little, the third place team by a little more, etc. Unfortunately, the reality is that no season is perfect so all we can do is find the ranking that symmetrically reorders the columns and rows of a data matrix to be as close to hillside form as possible. This is the motivating factor behind our ranking method.

Now you are ready for the steps of the evolutionary optimization ranking method:

1. Collect the data matrix you will use for your ranking – I tended to use game score data to make my head-to-head matrix, but that doesn’t have to be the case.
2. Gather your original population – This can be done randomly or using the rankings of other methods you can learn about in Who’s #1?.
3. Using each of your original population members, symmetrically reorder your data matrix and count the number of violations you have to hillside form. The lower the number, the better the ranking!
4. Now it’s time to make an offspring! Either mate or mutate members of your population.
5. Repeat step three for that offspring.
6. If your offspring has a lower number of violations to hillside form than the weakest member of your population, congratulations – it made the cut! Drop the weakest member from your population. However, if the offspring did not make the cut, it’s history.
7. Repeat steps 4 – 6 until you have a satisfactory solution – we chose to continue gathering offspring until the change in our fitness values got very small. Just realize when you are setting your stopping criteria that the longer you allow your algorithm to run, the better your solution will be since this method is constantly finding a solution that is getting closer and closer to hillside form.

There you have it! It’s really as easy as these seven steps. The thing I really love about this process is that it is so bare bones that you can pick any of those steps and make it as sophisticated as you like! Just remember two things before you start doing that: 1. Evolutionary optimization requires a certain amount of randomization in order to find “good” solutions. 2. The more sophisticated the method; the longer it will take to run.

Before ending this post, I need to share a deep, dark secret with you. I’m not a fan of sports. It’s true. Now, don’t get me wrong, I enjoy attending a live sporting event as much as the next person, but I actively dislike watching sports on television. I just can’t seem to get interested. However, what I am a fan of is ranking methods. So with that being said, don’t ask me if the bracket you’ve created is good because I have no idea, just be ready to talk to me about the math behind your ranking. That is something I can follow any day of the week.