Ranking with eigenpoints

Eigenpoints measure the dominance of teams in incomplete tournaments. This is an eigenvalue method, many of which are commonly used to measure the influence or centrality in citation networks (PageRank by Google being the most famous example). Here conceding points to an opponent is analogous to citing a document. Points won are interpreted as equally informative self-citations. All pairwise relationships receive the same weight, regardless of the number matches played.

The idea

The purpose is to rank a set of teams that have played each other in a way that forms a "connected network." This means that, even if not all teams have played each other directly, all teams can be linked through matches played by other teams. For example, teams in the top four tiers of English football form such a network, when matches played in the FA and League cup are taken into account. Similarly, all clubs from leagues that have any participants in UEFA competitions can be connected.

The determination of eigenpoints can be illustrated with a parable of a randomly wandering ball. First, let's consider the usual case where no teams have a perfect record. Let's start by giving the ball to a randomly chosen team in the network. The team gets to hold the ball for one period, after which an opponent is drawn from the set of teams that it has played. Each opponent is chosen with the same probability, regardless of how many times it has been played. If the holder of the ball has a perfect record against the opponent that is drawn then it gets to keep the ball, if the holder has lost all matches against the opponent then it has to pass the ball to the opponent. If the teams have a mixed record, then the ball is allocated randomly between them with the probabilities proportional to the points won in the pairwise matches. For example, if both teams had won once then it is a fifty-fifty lottery, whereas if the holder has won twice and there has been one draw, then the holder has won (3+3+1) points against one point by its opponent, and so gets to keep the ball with probability 7/8.

The ball is then passed along using this same procedure again and again. Eventually the probability that the ball is at any given time at any given team converges, which means that it does not depend on who got the ball first. The probability that a team has the ball is the eigenpoints of that team; percentage form for convenience. Thus eigenpoints always add up to 100.

Notice that when a team with a perfect record gets the ball it will never give it up. If there is exactly one team with a perfect record, then it has 100 eigenpoints and all others have zero. If there are multiple teams with a perfect record (not unusual in the early days of a competition) then what happens in the end could depend on who gets the ball first. For this reason the initial draw is made so that all teams have the equal chance of getting the ball. The ball will eventually end up at one of the teams with a perfect record, and the probability of it ending up at a given perfect-record team gives the eigenpoints for that team.

A team that did not win any points obviously gets zero eigenpoints--it could be the first to get the ball, but once it gives away the ball it can never get it back.

A team that only won points from teams that did not beat anyone will also get zero eigenpoints. Notice that you can only get the ball from a team that you won points from, so if you only beat teams that didn't beat anyone then once you lose the ball you can never get it back. Same applies if you only beat teams that only beat teams that didn't win any points, and so on... There can be a whole set of teams, who have won points only from each other, and have only lost points to the rest of the teams. Any teams in such a set of losers get zero eigenpoints, no matter how well they performed within the set of losers. This is a feature, not a bug.

The math: how to calculate eigenpoints

Eigenpoints are defined by a mapping from a positive (n × n) results matrix to an n-vector of positive numbers that add up to 100. Eigenranking is the rank order of the teams by their eigenpoints.

The aim is calculate the eigenpoints for a set of n teams that have all played at least one match. The required data is the n × n points-won matrix R, where the element R_ij gives the number of points won by team i in its matches against team j. While a valid results matrix requires only that all teams have played at least one match, eigenpoints are in general sensible only if the results matrix represents a connected graph.

First the results data is transformed into the pairwise dominance matrix P = R ⊘ (R + R^′) where ⊘ denotes robust Hadamard division; here “robust” means that the element-wise division yields zero if the divisor is zero. The element P_ij gives the share of team i out of all points earned in matches between teams i and j. The matrix P suffices for the data needed to calculate eigenpoints; in fact its upper (or lower) triangle would suffice as P_ij = 1 − P_ji by definition.

Suppose the points earned and conceded by team i are multiplied by the same k > 0. This means that ith row and ith column of R are multiplied by k. Clearly this leaves P and therefore also eigenpoints unaffected. Thus eigenpoints are invariant to the number of games played by a team, as long as its pairwise performance relative to all of its opponents is unaffected.

The connection count vector is m = (P + P^′)1 where 1 is the vector of ones. The element m_i gives the number of teams that team i has played at least once.

Probability of the “random ball” transiting from team i to team j ≠ i is the typical element U_ij of U =  diag(m)^− 1P^′ where the diag operator transforms a vector to a diagonal matrix. Probability of the “random ball” staying at the current team i is what remains. s = (I − U)1 The complete transition matrix for the “random ball” is W = U + diag(s)

The eigenpoints vector is the limiting probability distribution of the Markov chain defined by this transition matrix, when the initial distribution is uniform over all teams. p = (¹⁰⁰⁄_n) lim _{T → ∞} (W′^T) 1 The final scaling transforms the units to percentage probabilities. Notice that, if W is nicely connected, then p can also be obtained as the dominant eigenvector of W^′ after a similar transformation of the units. The initial uniform distribution is needed for the general case where W may be irreducible.

Literature

There are many eigenvalue-based methods for ranking vertices in networks, such as Eigenfactor and Google's PageRank. Eigenpoints are just one variant in this family of methods. The specific purpose of Eigenpoints is to be useful also for ranking teams that mostly participate in separate leagues, but are also connected through some participation in inter-league competitions. In these situations the number of matches played between different team pairs can be very unbalanced. The randomly wandering ball parable is based on the "random surfer" parable used by Brin and Page (1998) to explain PageRank.

Brin, Sergey and Lawrence Page (1998). "The Anatomy of a Large-Scale Hypertextual Web Search Engine." Computer Networks and ISDN Systems, 30, pages 107-117. https://doi.org/10.1016/S0169-7552(98)00110-X

Palacios-Huerta, Ignacio and Oscar Volij (2004). "Measurement of Intellectual Influence." Econometrica, 72(3), pages 963-977. https://doi.org/10.1111/j.1468-0262.2004.00519.x

Pinski, Gabriel and Francis Narin (1976). "Citation influence for Journal Aggregates of Scientific Publications: Theory, with Application to the Literature of Physics." Information Processing and Management, 12(5), pages 297-312. https://doi.org/10.1016/0306-4573(76)90048-0

Slutzki, Giora and Oscar Volij (2005). "Ranking Participants in Generalized Tournaments." International Journal of Game Theory, 33(2), pages 255-270. https://doi.org/10.1007/s00182-005-0197-5

More references at Eigenfactor.org.