Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've briefly read about rating systems that provide rankings to players based only on their performance wrt other players, in the context of chess. (for example, elo). When there is a lot of connectivity - players playing many other players - I can see how this makes sense.

But what about when there is not so much connectivity - in a degenerate case, {A1..An} all play each other often, and {B1..Bn} all play each other, but no $A_i$ plays $B_j$. So then each of $A_i$ has a score, and each of $B_i$ has a score, but, it seems to me, that the scores of $A_i$ and $B_j$ cannot at all be compared.

In between, there are cases where there is some amount of cross over between two cohorts(?) so there is some exchange of information going on - is there any investigation of how much connectivity is needed for comparisions to be meaningful?

share|improve this question
I just want to comment that in at least one case, the scenario described in your second paragraph has been debated endlessly: the National and American Leagues of baseball, until around 1997, didn't play against each other in regular-season play, but existed in the same geographical territory and competed for fans, and so it was natural for people to try to compare them. (Hence the All-Star game and the World Series, although both suffer from small sample size.) –  Michael Lugo May 24 '10 at 12:34
There is a very good Wikipedia page on the ELO rating system used in chess and elsewhere, containing a good preliminary discussion of such issues as rating inflation and issues with pairing. en.wikipedia.org/wiki/Elo_rating_system –  Joel David Hamkins May 24 '10 at 13:06
add comment

3 Answers

In machine learning, problems of this nature have been studied a fair bit. a canonical example is in machine translation/categorization, where you might have lots of text categorized by subject in English, and lots of uncategorized data in French, and a few translation keys, the problem being to similarly categorize the data in French.

There are a number of different techniques for this: one is called domain adaptation, and another is called transfer learning. They are different, but subtlely so: this blog post has a very nice explanation of the difference, and reading it indicates that transfer learning is closer to what you want.

One of the points of the theoretical work in this area (of which there isn't too much alas), is to quantify the amount of linked data (the graph linkage in your case) is needed to help with the classification task, and how similar the domains need to be (in the case of NL and AL, probably they are fairly similar, modulo DH rules).

share|improve this answer
add comment

If this were a problem I had to solve, and if there were no overlap between the two sets, I would consider examining as much domain-specific information as possible. For example, if they were runners competing against each other in races, you have finishing times to compare. Even if you can't find a metric that obvious, you might be able to combine information from other metrics which are correlated with winning percentages, for example runs scored or errors made.

If connections are limited, to gauge how much confidence to have in your ratings you might want to look into the Wilson score interval which will give you information about confidence intervals for the probabilities of binary outcomes where the number of trials is small. If you combine Wilson with a time-weighted decay function you can create a ratings system for competition over time, along with information about how confident you should be in your rankings.

share|improve this answer
add comment

Another perspective that may help here comes from Bayesian statistics. You can model the outcome of competition between any two players using an unknown strength variable (say , $S_i$ ). Then, define:

Prob($i$ wins over $k$) = Prob($S_i$ > $S_k$).

You can use the logistic/normal distribution to model the above probability (like how the wiki page for ELO mentions. See the link provided by Joel).

As you pointed out, in the degenerate case, estimation of the strengths among all players in the set $A$ and all the players in the set $B$ would be possible but the estimates would not be comparable between a player from $A$ and a player from $B$.

The above suggests that we have to introduce some 'connections' between the sets $A$ and $B$ that would be informative about the outcomes between two players from these sets using either statistical or context-specific approaches to make the scores comparable. A few thoughts along those lines (one could use one or more of the following approaches):

  1. Fix the mean and scale of the strengths to the same value for both groups.

    Both the mean and the scale are not identifiable when you have relative ordering.

  2. Use Latent Class segmentation approaches along with information about the competitive context.

    For example, in the context of chess, we could classify players as 'Amateurs', 'Master', 'Grand Master' etc. We then impose some conditions on the outcomes of competition between any two players from these 3 classes. As an example, a 'Grand Master' will defeat an 'Amateur' 99% of the time or perhaps in 25 moves or less and so on.

    Bringing context-specific information such as the above would enrich the data we have which would help makes the scores comparable.

  3. Use Hierarchical Bayesian approaches to stabilize estimates with low amounts of data.

    If players (between the cohorts $A$ and $B$) have not played that often hierarchical estimation would help stabilize the estimate of their relative strengths.

You could then investigate the extent to which you have to introduce 'connections' between the two sets to get a meaningful comparison. You would still need to define what you mean by meaningful comparison in your context. (Perhaps, define a meaningful comparison as one where you are able to correctly predict the outcome of competition between two players 95% of the time?)

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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