How to prove that Elo rating or Page ranking have a meaning for my set?

Question

I have a set of players. They play against each other (pairwise). Pairs of players are chosen randomly. In any game, one player wins and another one loses. The players play with each other a limited number of games (some players play more games, some less). So, I have data (who wins against whom and how many times). Now I assume that every player has a ranking that determines the probability of winning.

I want to check if this assumption is actually truth. Of course, I can use the Elo rating system or the PageRank algorithm to a calculate rating for every player. But by calculating ratings I do not prove that they (ratings) actually exist or that they mean anything.

In other words, I want to have a way to prove (or to check) that players do have different strengths. How can I do it?

ADDED

To be more specific, I have 8 players and only 18 games. So, there a lot of pairs of players who did not play against each other and there a lot of pairs that played only once with each other. As a consequence, I cannot estimate the probability of a win for a given pair of players. I also see, for example, that there is a player who won 6 times in 6 games. But maybe it is just a coincidence.

Answer 1

You need a probability model.

The idea behind a ranking system is that a single number adequately characterizes a player's ability. We might call this number their "strength" (because "rank" already means something specific in statistics). We would predict that player A will beat player B when strength(A) exceeds strength(B). But this statement is too weak because (a) it is not quantitative and (b) it does not account for the possibility of a weaker player occasionally beating a stronger player. We can overcome both problems by supposing the probability that A beats B depends only on the difference in their strengths. If this is so, then we can re-express all the strengths is necessary so that the difference in strengths equals the log odds of a win.

Specifically, this model is

$$\mathrm{logit}(\Pr(A \text{ beats } B)) = \lambda_A - \lambda_B$$

where, by definition, $\mathrm{logit}(p) = \log(p) - \log(1-p)$ is the log odds and I have written $\lambda_A$ for player A's strength, etc.

This model has as many parameters as players (but there is one less degree of freedom, because it can only identify relative strengths, so we would fix one of the parameters at an arbitrary value). It is a kind of generalized linear model (in the Binomial family, with logit link).

The parameters can be estimated by Maximum Likelihood. The same theory provides a means to erect confidence intervals around the parameter estimates and to test hypotheses (such as whether the strongest player, according to the estimates, is significantly stronger than the estimated weakest player).

Specifically, the likelihood of a set of games is the product

$$\prod_{\text{all games}}{\frac{\exp(\lambda_{\text{winner}} - \lambda_{\text{loser}})}{1 + \exp(\lambda_{\text{winner}} - \lambda_{\text{loser}})}}.$$

After fixing the value of one of the $\lambda$, the estimates of the others are the values that maximize this likelihood. Thus, varying any of the estimates reduces the likelihood from its maximum. If it is reduced too much, it is not consistent with the data. In this fashion we can find confidence intervals for all the parameters: they are the limits in which varying the estimates does not overly decrease the log likelihood. General hypotheses can similarly be tested: a hypothesis constrains the strengths (such as by supposing they are all equal), this constraint limits how large the likelihood can get, and if this restricted maximum falls too far short of the actual maximum, the hypothesis is rejected.

---

In this particular problem there are 18 games and 7 free parameters. In general that is too many parameters: there is so much flexibility that the parameters can be quite freely varied without changing the maximum likelihood much. Thus, applying the ML machinery is likely to prove the obvious, which is that there likely are not enough data to have confidence in the strength estimates.

Answer 2

If you want to test the null hypothesis that each player is equally likely to win or lose each game, I think you want a test of symmetry of the contingency table formed by tabulating winners against losers.

Set up the data so that you have two variables, 'winner' and 'loser' containing the ID of the winner and loser for each game, i.e. each 'observation' is a game. You can then construct a contingency table of winner vs loser. Your null hypothesis is that you'd expect this table to be symmetric (on average over repeated tournaments). In your case, you'll get an 8×8 table where most of the entries are zero (corresponding to players that never met), ie. the table will be very sparse, so an 'exact' test will almost certainly be necessary rather than one relying on asymptotics.

Such an exact test is available in Stata with the symmetry command. In this case, the syntax would be:

symmetry winner loser, exact

No doubt it's also implemented in other statistics packages that I'm less familiar with.

Answer 3

You want to test the hypothesis that probability of a result depends on the matchup. $H_0$, then, is that every game is essentially a coin flip.

A simple test for this would be calculating the proportion of times the player with more previous games played will win, and comparing that to the binomial cumulative distribution function. That should show the existence of some kind of effect.

If you're interested about the quality of the Elo rating system for your game, a simple method would be to run a 10-fold crossvalidation on the predictive performance of the Elo model (which actually assumes outcomes aren't iid, but I'll ignore that) and comparing that to a coin flip.

Answer 4

Probably most famous example for testing how accurate is the method of estimation in rating system was Chess ratings - Elo versus the Rest of the World competition on Kaggle, which structure was the following:

Competitors train their rating systems using a training dataset of over 65,000 recent results for 8,631 top players. Participants then use their method to predict the outcome of a further 7,809 games.

Winner was Elo++.

It seems to be a good test scheme for your needs, theoretically, even if 18 matches are not a good test base. You can even check differences between results for various algorithms (here's a comparison between rankade, our ranking system, and most known, including Elo, Glicko and Trueskill).

Answer 5

Have you checked some of Mark Glickman's publications? Those seem relevant.

Implicit in the standard deviation of the ratings is an expected value of a game. (This standard deviation is fixed at a specific number in basic Elo, and variable in the Glicko system). I say expected value rather than the probability of a win because of draws. The key things to understand about whatever Elo ratings you have is the underlying distribution assumption (normal or logistic, for example) and the standard deviation assumed.

The logistic version of the Elo formulas suggests that the expected value of a rating difference of 110 points is .653, for example player A with 1330 and player B with 1220.

$$E_A= \frac{1}{1+10^{(R_B-R_A)/400}}$$

(OK,that's a Wikipedia reference but I've already spent too much time on this answer.)

So now we have an expected value for each game based on each player's rating, and an outcome based on the game.

At this point, the next thing I'd do would be to check this out graphically by arranging the gaps from low to high, and totalling the expected and actual results. So, for the first 5 games we might have total points of 2, and expected points of 1.5. For the first 10 games, we might have total points of 8, and expected points of 8.8, etc.

By graphing these two lines cumulatively (as you would for a Kolmogorov-Smirnov test) you can see whether the expected and actual cumulative values track each other well or badly. It's likely someone else can provide a more formal test.