13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want to test the null hypothesis that all the players have the same strength, or check the fit of a model of player strength? $\endgroup$ – onestop Jan 19 '11 at 14:58
  • $\begingroup$ @onestop: All the players having the same strength would be very improbable, wouldn't it? Why do you suggest this as the hypothesis? $\endgroup$ – endolith Oct 19 '14 at 22:44
10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ (+1) To help the OP with additional searching on this model, here are a few additional points. (1) This model is often called the Bradley-Terry model (though it goes back to at least some work of Zermelo). (2) Letting $s_A = \exp(\lambda_A)$, the predicted probability of $A$ beating $B$ is $s_A/(s_A + s_B)$. (3) If a full round-robin tournament is played (which isn't the case here), the rankings of the strengths will coincide exactly with the winning percentage of each player. (4) The goodness-of-fit is related to flows over the graph with players as nodes and games as edges. $\endgroup$ – cardinal Nov 9 '11 at 17:53
  • $\begingroup$ (cont.) Lester R. Ford, Jr. even has an article discussing a fitting algorithm based on this idea in an Amer. Math Monthly piece from 1957 written in honor of his father. $\endgroup$ – cardinal Nov 9 '11 at 17:57
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (+1) It's funny, I just realized that this Stata command might be used for transmission/disequilibrium test in genetics :) I discussed R packages in an earlier response, stats.stackexchange.com/questions/5171/…. $\endgroup$ – chl Jan 19 '11 at 18:21
  • $\begingroup$ Indeed, the TDT is one application discussed in the Stata help I linked above. It's also the context in which I first came across this test. Thanks for the link to that previous Q - looks like I was busy with other Qs when it was posted. $\endgroup$ – onestop Jan 19 '11 at 18:38
  • $\begingroup$ Although the question does refer to hypothesis testing, its choice of emphasis is on the goodness of fit question: does a single numerical (scalar) strength effectively model the results of the matches between players? $\endgroup$ – whuber Nov 9 '11 at 15:03
1
$\begingroup$

Have you checked some of Mark Glickman's publications? Those seem relevant. http://www.glicko.net/

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.

http://en.wikipedia.org/wiki/Elo_rating_system (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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To be more specific. I have 8 players and only 18 games. So, there a lot of pair of players that did not play with each other and there a lot of pairs that played only one with each other. As a consequence, I cannot estimate the probability of win for a given pair of players. I also see, for example that there is a player that won 6 times in 6 games. But may be it is just a coincidence. $\endgroup$ – Roman Jan 19 '11 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.