6
$\begingroup$

Stats noob here working on an algorithm for ranking players in a tournament.

I have a test set of players, each with a "skill" value. My algorithm simulates a "tournament", in which players play against each other (1v1) in some order (e.g. Swiss pairing). At the end of the tournament, I have each player's resulting rank.

For example, a sample data set could be something like:

Name | Tournament Rank | "True" Rank
Alex |        5        |      7
John |        1        |      2
Mike |        3        |      1
...

So John won the tournament even though he was the second best player there, and Mike is actually the best player, but happened to finish third due to luck or whatever.

Given each player's "true" skill and their rank in the tournament, how can I best quantify how well my tournament algorithm performed in ranking everyone? e.g. I'm looking to be able to say things like "With this set of input parameters, my tournament simulator places people 10% more accurately than with this other set of input parameters"

(Bonus question:)

Also, arguably more important than the exact ranking to me is that players are in the correct "bucket" of players. For example, if I split the results into 5 sections (top 20%, 60th-80th percentile, etc.), I need my tournament algorithm to reliably place people into the bucket they deserve to have ended up in. Would you do anything differently than above to check the correctness of how people end up in buckets?

$\endgroup$
3
  • $\begingroup$ Your example data shows two people equal third in the tournament, is this sort of tied result a typo or is it going to be possible? (a minor complication if it is) $\endgroup$ Jul 21, 2013 at 9:25
  • $\begingroup$ In the limit of an infinite number of trials the sample "player ranking" is going to asymptote to the true skill. In the presense of a few trials you will be a victim of "... time and chance" - you will have some noise in the signal. It sounds like an interesting challenge in optimal design of experiments. $\endgroup$ Jul 21, 2013 at 14:28
  • $\begingroup$ @PeterEllis - Whoops, yeah it was a typo. $\endgroup$
    – numegil
    Jul 21, 2013 at 20:44

1 Answer 1

4
$\begingroup$

If I understand correctly, what you would like to have is a measure to compare the underlying true ranking $\pi$ and the predicted ranking (i.e., the tournament ranking, or the simulated ranking) $\sigma$, where $\sigma$ is a function of some input parameters.

In the statistics literature, there are a number of distance functions for rankings. I will list some of them below. Let $\pi(i)$ and $\sigma(i)$ be the ranks of item $i$ in $\pi$ and $\sigma$, respectively (e.g., $\pi(``\text{John}")=2$ and $\sigma(``\text{John}")=1$ in your example). The Kendall distance is defined as $$ K(\pi,\sigma) = \# \lbrace \; (i,j) \, \vert \, \pi(i)>\pi(j) \text{ and } \sigma(i)<\sigma(j) \; \rbrace \, . $$ The Spearman distance is defined as $$ S(\pi,\sigma) = \sum_i \left( \pi(i) - \sigma(i)\right)^2 \, . $$ The Spearman footrule distance is defined as $$ F(\pi,\sigma) = \sum_i \lvert \pi(i) - \sigma(i)\rvert \, . $$ These are three widely used distance functions for rankings. You could think of the distance as the loss the predicted ranking suffers w.r.t. the true ranking, so the lower the distance, the better. If you need an accuracy (the larger the better) instead of a loss, these distances can be easily normalized to different types of correlation coefficients for rankings.

Regarding the bonus question:

I think there are a lot of different ways to do it. For example, after you divide the items in the true rankings into several groups, you can use the C-index to measure the performance of the predicted ranking. In the study of multipartite ranking, C-index is commonly used. It is a kind of extension of AUC (area under the ROC curve). You can check Section 4 of this paper, where a short introduction of C-index is given.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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