Will Gilroy

Thesis Advisor: Dr. Jaime Haddock (Harvey Mudd College - Department of Mathematics)

Second Reader: Dr. Heather Zinn-Brooks (Harvey Mudd College - Department of Mathematics)

Contact: wgilroy@hmc.edu

Check Yourself Before You WREK Yourself: Algorithmic Approaches to the Ranking Problem

Let's suppose you and a friend are queuing up for food. You begin to discuss "For sure we agree that the salmon is better than the bisque, but I think the quesadillas are tastier than the garlic bread!" to which your friend responds "Actually I like the garlic bread more than the quesadillas", another friend passing by, "one more vote for the garlic bread over the quesadillas!"

Given that you and your friend are both nerds you begin to wonder how you could use these comparisons to rank each of the foods.
One way is to assign a rating to each food such that "salmon is better than bisque" is captured by salmon having a higher rating than bisque.
To find the ratings we can set up a linear system which uses our comparisons to solve for the ratings. Sometimes we get lucky and we can find ratings to perfetly explain every comparison; often we find that comparisons have probabalistic error and so we expect our system to be inconsistent.

The go-to tool for solving inconsistent linear system is to find the least squares solution --- find the solution which minimizes the square deviation from each requirement of our linear system. However, the least squares solution for the rating problem has some flaws: it is sensitive to upsets (aka corruptions), it assumes that every comparison has the same consensus, it is strongly subject to comparison topology, and it is static.

To do one better we have invented a stochastical algorithm Weighted Randomized Extended Kaczmarz (WREK) to solve the ranking problem.

Together let's unravel the behaviour of WREK on the ranking problem. We will prove its convergence properties, experiment with various reweighting functions, and explore connections to the underlying geometry and algebraic properties of the rating problem.