Best algorithm for matchmaking for a crowd sourced rankings?

Question

I'd like to set up a system that crowd sources the best 10 items from a set that can vary from 20-2000 items (the ranking amoung the top ten is not important). There is an excellent stackoverflow post on algorithms for doing the actual sort at How to rank a million images with a crowdsourced sort. I am leaning toward asking users which they like best between two items and then using the TrueSkill algorithm.

My question is given I am using something like TrueSkill, what is the best algorithm for deciding which pairs of items to show a user to rate? I will have a limited number of opportunities to ask people which items they like best so it is important that the pairs presented will give the system the most valuable information in identifying the top 10. Again, I am mostly interested in finding the top ten, less so how the rest of the items rank amongst themselves or even how the top ten rank amongst themselves.

Meritocracy

Answer 1

This problem is very similar to organizing a knock-out tournament where skills of the players are not well known and number of players is very high (think school level tennis tournaments). Since round robin ( O(n^2) matches) is very expensive, but a simple knock-out tournament is too simplistic, the usual option is to go with k-elimination structure. Essentially, every player (in your context a item) is knocked out of contention after losing k games. Take a look at the double elimination structure: http://en.wikipedia.org/wiki/Double-elimination_tournament .

Perhaps you can modify it sufficiently to meet your needs.

Demonic

Answer 2

Another well known algorithm for this was produced to calculate rankings in Go or Chess tournaments. You can have a look at the MacMahon Algorithms which calculate such pairings and the ranks at the same time. It should be possible to truncate this algorithm, so that it will only produce a set of 10 best Items.

You can find more details in Christian Gerlach's thesis, where he describes the actual optimization algorithm (unfortunately the thesis is in German).

Reeve