Matching people with similar rating?

Question

Suppose you have a collection of people with a sample size of 10,000. Each person in the collection has a rating score in the form of a winning percentage: 0.00 < x < 1.00.

Currently my system randomly picks two people and matches them together. I would like to improve matchmaking by pairing up people who have a high winning percentage with others that have a high winning percentage.

Have you ever played World of Warcraft arenas? Typically if you are in 2000 bracket you are matched with teams who are in 2000 bracket. If you are in 1500 bracket, you are matched with people who have similar ranking.

What is the the easiest way to implement such matchmaking system? While implementation doesn't really matter, even a pseudo-code would help, but I would greatly appreciate if you can guide me in the right direction using JavaScript, Backbone, and Underscore as a toolbelt.

Answer 1

Place everybody in a balanced binary tree (if you'll be frequently adding and removing people) or in a sorted array (if the data set is more or less static), using their winning percentage as the sort key. To match somebody, locate them in the tree or array, then match them with somebody within, say, +/- 10 rankings using a random number generator (e.g., if you're using an array and the person is in the ith index, then match them with the person at the i + rand(10) + 1 index).

I'm assuming that somebody's winning percentage will only change by small increments, which means that updating the tree or array will usually be a constant time operation since you'll just be swapping adjacent elements.