Calculating scores from incomplete league tables

Question

When I was in high school and learning about matrices, we were shown a technique that would help in a situation like this:

There are a number of chess players in a league, and they need to determine a ranking for all of them, but don't have enough time for every player to play every other person. If it ends up that Player A beats Player B, and Player B beats Player C, you can say with some level of certainty that Player A is better than Player C and therefore award some points to player A in lieu of them actually playing each other.

As I said, this was a little while ago and I can't remember how to actually perform the algorithm, but I think it was called something like a "domination matrix". Searching the web for that has been fruitless and scary at times, so I don't think that's right.

Can anyone give me some help? Ideally an algorithm I can use for this program I'm working on, but even just a pointer to some more information about the procedure.

Answer 1

It sounds like you are remembering a presentation of the Perron-Frobenius theorem - which is at least a safer search term :-). One such is at http://www.math.utah.edu/~keener/lectures/rankings.pdf Chess players use the Elo system, described at http://en.wikipedia.org/wiki/Elo_rating_system and http://www.chesselo.com/, which would be easier to implement. It is possible that there is no good ranking even if you know everything - see http://en.wikipedia.org/wiki/Nontransitive_dice. People modelling soccer games usually keep track of defensive and offensive strengths separately.

Answer 2

What it sounds like you are describing is a Swiss System tournament or a very similar variation all described on the linked Wikipedia entry. Although rather than given an incomplete tournament to calculate ratings it is a way to organize a tournament to pair the best chess players with the best and the worst chess players with the worst to determine a ranking without the need for everyone to play everyone else.

Answer 3

Maybe some type of PageRank algorithm might work for you.

Imagine every person has a webpage in which they hyperlink to every person who defeated them.

Running the page rank algorithm on this data would give you give you the steady state of your link matrix which might indicate to you the relative importance of each person (I guess).

For example a person who played only one game but, in that, defeated someone who defeated lots of people might have a higher page rank than somebody who defeated 10 people who in turn have not won a single game.