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

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 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 a moment, 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 percentage of probability that a team has the ball is the eigenpoints of that team. 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.

Math

Eigenpoints are defined by a mapping from a positive (N x N) results matrix to an N-vector of positive numers that add up to 100. Eigenranking is the rank order of the players by their eigenpoints.

The results matrix R has the points won by player i from player j at element ij. For eigenpoints to be defined, the results have to define a connected graph.

Calculating Eigenpoints

i. The dominance matrix P is defined asMATHThe element $P_{ij}$ gives the dominance points earned by i from j.

ii. The normalized dominance matrix is M defined asMATH

iii. Dominance shares are defined asMATHThey give the normalized win percentage of team i. Normalization means that pair that played each other gets equal weight in the matrix, regardless of how many times they played each other.

iv. The normalized points matrix is MATH

v. Eigenpoints are given by the dominant eigenvector of W. It is rescaled for convenience, so that total eigenpoints add up to 100.

Notes

If there are multiple teams with a perfect record, then W has multiple unit eigenvalues and there is no single dominant eigenvector. An alternative method of calculating eigenpoints is robust to this special case. Take the matrix power of Wt, with t high enough that the result does not change if t is increased further; then premultiply Wt by a vector [1/N,...,1/N]. The resulting vector is the vector of eigenpoints.

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

Palacios-Huerta, Ignacio and Oscar Volij (2004). "Measurement of Intellectual Influence." Econometrica, 72(3), pages 963-977.

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.

Slutzki, Giora and Oscar Volij (2005). "Ranking Participants in Generalized Tournaments." International Journal of Game Theory, 33(2), pages 255-270.

More references at Eigenfactor.org.