Who's Number 1? Hodge Theory Will Tell UsThis article describes a method, proposed by Jiang, Lim, Yao, and Ye, that uses Hodge theory to rank a large number of alternatives...David Austin
IntroductionLife is full of choices. Particularly in our datarich world, we are often presented with a wide variety of alternatives from which we would like to choose the best possible. Which website has the best answer to my question, where should I go for lunch, which movie should we watch tonight. Times were simpler when the choice boiled down to John or Paul. To help make decisions, we often rely on a ranking of the alternatives and choose the ones with the highest rank. For instance, when I search for "Condorcet paradox," Google tells me there are 115,000 results. Like most people, I will most likely rely on Google's ranking and be satisfied with what I find among the top ten. There is, however, an inherent difficulty in making decisions in which several criteria are condensed into a single ranking. For instance, imagine you have three choices for lunch. The food at Macho Taco is lackluster, but it's cheap, fast, and conveniently located. The food is somewhat better at Chez Fromage and it's affordable and close, but the service is terrible. Meanwhile, Thai One On has good food and service, but it's expensive and far away. It would not be unreasonable if I preferred Macho Taco over Chez Fromage, If we are to have a ranking system, we would expect the rankings to be transitive; that is, if choice A is rated higher than B, and B is rated higher than C, then A is also rated higher than C. However, our lunch preferences are clearly not transitive, a situation known as the Condorcet paradox. This paradox may appear when a single voter compares alternatives based on several factors or when groups of voters are asked to make rankings collectively. The Condorcet paradox occurs frequently when ranking sports teams. For instance, in the 2010 college football season, Oklahoma beat Texas Tech, 45  6, In which order should the three teams be ranked? This article describes a method, proposed by Jiang, Lim, Yao, and Ye, that uses Hodge theory to rank a large number of alternatives in which the Condorcet paradox may appear. Besides providing a ranking, this method will also create a means of measuring how reliable the ranking is. The data sets that Jiang et al aim to rank have other complications. Think of restaurant reviews on yelp.com or movies reviewed on Netflix.
Finally, humans are not very good at ranking large numbers of alternatives. In a seminal paper in cognitive psychology, George Miller demonstrated that we have a hard time evaluating more than seven options. This may be why yelp and Netflix only allow us five stars. Pairwise comparison graphsTo construct a ranking, we build a pairwise comparison graph $G$ as follows. Suppose that we have a set of objects $V=\{1,2,\ldots,n\}$ to be ranked and a set of voters, each of whom has compared pairs of objects and expressed a preference for one object in each pair. Examples include:
Sometimes, preferences between pairs may be inferred from other rating data. For instance, if a voter has rated movie $i$ in the Netflix movie database with four stars and movie $j$ with two stars, we may infer a preference for movie $i$ over $j$. We define $w^\alpha_{ij} = 1$ if voter $\alpha$ has made a comparison between item $i$ and $j$, and $w^\alpha_{ij} = 0$ if not. The number of voters who have compared $i$ and $j$ is $w_{ij}=\sum_\alpha w^\alpha_{ij}$. In the pairwise comparison graph $G$, the set of objects $V$ to be ranked forms the vertex set. An (undirected) edge joins items $i$ and $j$ if at least one voter has compared $i$ and $j$, that is, if $w_{ij}> 0$. The set of edges will be denoted by $E$, and individual edges will be denoted by a set of vertices, such as $\{i,j\}\in E$. To each voter $\alpha$ is associated a matrix $Y^\alpha_{ij}$ measuring that voter's "degree of preference" for alternative $i$ over $j$. The degree to which $i$ is preferred over $j$ will be minus the amount that $j$ is preferred over $i$. In other words, $Y^\alpha_{ij} = Y^\alpha_{ji}$. If voter $\alpha$ has not compared $i$ and $j$, then $Y^\alpha_{ij} = 0$. In any case, since for all $i$ and $j$, $Y^\alpha_{ij} = Y^\alpha_{ji}$, $Y^\alpha$ is called a skewsymmetric matrix. The preferences of individual voters are aggregated into a single preference matrix $Y_{ij}$ by, perhaps, averaging the preferences of all the voters who have compared $i$ and $j$. In this case, $Y$ is also skewsymmetric. The matrix $Y$ belongs to the vector space $C^1$ of all skewsymmetric $n\times n$ matrices $X$ where $X_{ij} = 0$ if $\{i,j\}$ is not an edge of $G$. Such a matrix will be called an edge flow, terminology that calls attention to its interpretation as the flow of "preference" along an edge from higher to lower preference. Preference will flow out of vertices with a higher ranking and into vertices with a lower ranking. In this way, we may imagine a motivating comparison between edge flows and vector fields on, say, ${\Bbb R}^3$ that describe the flow of a gas from an area of high pressure to one of low pressure. In search of a potentialArmed with our pairwise comparison graph, we would like to find a ranking of the objects $V$ that is compatible with the pairwise comparisons. In particular, we would like to assign to each object $i$ a ranking $s_i$ such that $Y_{ij} = s_is_j$ if a comparison has been made between $i$ and $j$. In other words, the ranks of two objects should differ by the amount that one is preferred over the other. Let's put this into a larger framework and define the vector space $C^0$ to be ${\Bbb R}^n$, which we think of as the set of functions on $V$. We may define the gradient as a map
by \[{\rm grad} (s)_{ij} = s_js_i.\] Given our preference matrix $Y$, our desired ranking function will be a potential $s$ such that $Y = {\rm grad}(s)$. Consideration of the Condorcet paradox shows that a potential function is not guaranteed, or even likely, to exist. Remember that the Condorcet paradox says that it is possible to prefer $i$ to $j$, $j$ to $k$, and $k$ to $i$. In other words, we could have
However, if $Y={\rm grad}(s)$, then
For this reason, we need to consider the set of triangles $T$ on the graph $G$. A triangle is a subset $\{i,j,k\}$ of $V$ where $\{i,j\}$, $\{j,k\}$, and $\{k,i\}$ are edges of $G$. We also introduce the vector space $C^2$ of hypermatrices $\Phi_{ijk}$, where $\{i,j,k\}$ is a triangle, along with the symmetry condition
We may now define the function ${\rm curl}:C^1\longrightarrow C^2$ by
Using our preference edge flow $Y$, a triangle with ${\rm curl}(Y)_{ijk} \neq 0$ is called a triangular inconsistency because the voters' preferences are not transitive along that triangle. Putting everything together, we have
and ${\rm curl}({\rm grad}(s)) = 0$. At this point, there is a lot of notation so let's briefly summarize where we are. Individual voters' preferences are aggregated into an edge flow $Y\in C^1$. We are seeking a ranking of the objects in $V$, which will be given by a potential function $s \in C^0$, where $Y={\rm grad}(s)$. If a potential function exists, our preference edge flow must satisfy ${\rm curl}(Y) = 0$. The Hodge decompositionHodge theory gives us a useful decomposition of $C^1$. First, we will consider ${\cal G}$, which is the image of ${\rm grad}$ in $C^1$. That is, ${\cal G} = {\rm im}({\rm grad})$ meaning that ${\cal G}$ consists of all edge flows $X$ where $X={\rm grad}(s)$ for some potential $s$. The preference edge flow $Y$ given by aggregating voters' preferences is in $C^1$. If a ranking $s$ exists, then $Y={\rm grad}(s)$ should lie in ${\cal G}\subset C^1$. The Condorcet paradox, however, indicates that this may not happen. Instead, we seek a ranking function $s$ such that ${\rm grad}(s)$ is the closest possible to $Y$. To measure distances in $C^1$, we need to introduce an inner product. For edge flows $X, Y \in C^1$, we define:
Using this inner product, we will see that $C^1$ admits an orthogonal decomposition, known as the Hodge decomposition.
This decomposition is rather elementary and is demonstrated by a couple of points, including the determination of ${\cal G}$, ${\cal H}$, and ${\cal I}$, that we will bullet below.
Applying the Hodge decompostion to rankingsHow does this help us to develop a ranking from our preference edge flow $Y$? Since $Y\in C^1$, we may decompose $Y$ as
where the three terms have the following significance:
Computing the decompositionWe will now describe a simple method for computing the decomposition of the preference edge flow $Y$, beginning with the computation of $s$. We seek the potential that minimizes $\parallel Y({\rm grad}(s))\parallel^2=\parallel Y+{\rm grad}(s)\parallel^2$ among all $s\in C^0$. Therefore, if $r$ is any other potential,
which implies that
This is known as the normal equation that arises in the solution of a leastsquares problem, and there are standard techniques for solving it. The map ${\rm grad}^*\circ {\rm grad}$ is sometimes called the Helmholtzian and denoted $\Delta_0$. The normal equation in this form is:
In the same way, we may find $\Phi$ by minimizing $\parallel Y{\rm curl}^*(\Phi)\parallel^2$. This leads to the normal equation
which may also be solved with standard techniques. The BCS college football standingsWhen reading Jiang et al's paper, I wanted to find a data set that I could use to explore the ideas computationally. There are plenty of places where these ideas apply, and Jiang et al describe several. Wanting a relatively small data set that I could analyze quickly on my laptop, however, I chose to look at the 2010 college football season. Besides, as The New York Times recently pointed out, any yokel with a computer has a college football ranking system, and, well, I have a computer. Under my system, the objects $V$ to be ranked are the 120 Division I college football teams. The voters are games between two Division I teams, which create pairwise comparisons. There are many ways in which games could be used to create a comparison between teams. In computer rankings used in the BCS (Bowl Championship Series) standings, however, the NCAA does not allow the margin of victory to be used. Therefore, I used a simple comparison, where $Y^\alpha_{ij} = 1$ if team $i$ beat team $j$ in game $\alpha$. I also experimented with other possibilities that included the margin of victory, which sometimes had significant effects on the rankings. This seems like an appropriate, though perhaps not ideal, application of our Hodge theoretic ideas. Here are some facts about the comparison graph $G$.
At the end of the regular season, college football teams are ranked according to the BCS standings, which combine a number of computer ranking systems along with polls of sportswriters and football coaches. Based on these rankings, the top two teams advance to a national championship game, the winner of which is declared to be the national champion. The 2010 season was somewhat controversial since, when the regular season ended, three teamsAuburn, Oregon, and Texas Christianwere undefeated yet only two could advance to the national championship game. The final BCS standings, announced on December 5, 2010, the day after the regular season ended, had Auburn and Oregon in the top two positions, much to the displeasure of Texas Christian fans. Shown below is a comparison of the BCS ranking and our Hodgetheoretic ranking, as of December 5, 2010. I have normalized the Hodge theoretic rankings so that the highest ranked team has a score of 100 and the lowest ranked team has 0.
Interestingly, the Hodgetheoretic ranking promoted Oklahoma, a team with two losses to highlyranked Missouri and Texas A&M, over Texas Christian, a team with no losses. This has nothing to do with this author growing up in a family of diehard Oklahoma fans. Rather, the effect of the two losses is mitigated by their appearance in three triangles in which $A$ beat $B$ who beat $C$ who beat $A$. The figure below shows the pairwise comparison graph $G$. Edges are shown in gray, and triangles in which $A$ beat $B$ beat $C$ beat $A$ are in blue. The height of vertex $i$ in the figure is equal to $s_i$.
For the sake of completeness, I feel compelled to report that lowly Akron earned the minimal score of 0.0, thereby justifying their team name, the Zips. Of course, the Hodgetheoretic approach gives us more than just the ranking since we have a decomposition of the preference edge flow $Y$ as
For the data set above, I computed
Remember that $H$ is a measure of the global inconsistencies in $Y$. It is unreasonable to expect $H$ to be too small since there will certainly be long loops of inconsistencies. Still, its size is modest compared to the gradient term so we may have some degree of confidence in our ranking. Also, ${\rm curl}^*(\Phi)$ measures the triangular inconsistencies. Since every triangle is inconsistent due to the fact that $Y_{ij}=\pm1$, we should expect this component to be significant. After the bowl games were played, the final rankings look like this:
SummaryReaders familiar with vector calculus will no doubt be struck by the use of the terms gradient, curl, and divergence, which originate in a study of functions and vector fields in Euclidean space. In fact, Hodge theory was originally developed in this context as a means of measuring global topological features of Euclideanlike spaces. It has found important and varied applications in topology, algebraic geometry, electricity and magnetism, and a range of other disciplines. The novel contribution of Jiang et al's paper is to recognize how the Hodge decomposition applies in this combinatorial setting to create rankings and a measurement of their reliability in cases where the data set is incomplete and imbalanced. Careful readers will have noticed that our ranking depends on several choices. In the specific example I looked at, $Y_{ij}$ is a measurement of the quality of a victory in a football game, and there is an endless variety of ways to perform this measurement. In other situations that require aggregating many voters' preferences, there are also several options that should be considered. Finally, the Hodge decomposition depends on the choice of an inner product on the spaces $C^0$, $C^1$, and $C^2$. There are clearly other choices, which will lead to different rankings. Rankings have been the inspiration for a great deal of mathematical investigation and are related to important problems in voting theory and social choice, more generally. I have not attempted to place these ideas in the context of this literature. However, in their extremely readable paper, Jiang and his coauthors describe how the Hodge theoretic ranking, along with suitable choices for the inner products, generalize more widely known constructions, such as the Borda count and Kemeny optimal ranking. ThanksThanks to my west Michigan sports authority Trevor "TDime" Deimel for help in thinking about how to measure the quality of a football win. References
David Austin The AMS encourages your comments, and hopes you will join the discussions. We review comments before they're posted, and those that are offensive, abusive, offtopic or promoting a commercial product, person or website will not be posted. Expressing disagreement is fine, but mutual respect is required.

Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance 