Fair matchmaking for online games

Question

Most online games arbitrarily form teams. Often times its up to the user, and they'll choose a fast server with a free slot. This behavior produces unfair teams and people rage quit. By tracking a player's statics (or any statics that can be gathered) how can you choose teams that are as fair as possible?

Answer 1

One of the more well-known systems now is Microsoft's TrueSkill algorithm.

People have also attempted to adapt the Elo system for team matchmaking, though it's more designed for 1-v-1 pairings.

Answer 2

After my previous answer, I realized that if you wanted to get really fancy you could use a really simple but powerful idea: Markov Chains.

The intuitive idea behind using a Markov Chain goes something like this:

1. Create a graph G=(V,E)
2. Let each vertex in V represent an entity
3. Let each edge in E represent a transitioning probability between entities. This means that the sum of the out degrees of each vertex must be 1.
4. At the start (time t=0) assign each entity a unit value of 1
5. At each time step, transition form entity i, j by the transition probability defined in 3.
6. Let t->infinity then the value of each entity at t=infinity is the equilibrium (that is the chance of a transition into an entity is the same as the total chance of a transition out of an entity.)

This idea has for example been used successfully to implement Google's page rank algorithm. To describe how you can use it consider the following:

1. V = players E = probability of transitioning form player to player based on relative win/loss ratios
2. Each player is a vertex.
3. An edge from player A to B (B is not equal to A) has probability X/N where N is the total number of games played by A and X is the total games lost to B. Add an edge from A to A with probability M/N where M is the total number of games won by A.
4. Assign a skill level of 1 to each player at the start.
5. Use the Power Method to find the dominant eigenvector of the link matrix constructed from the probabilities defined in 3.
6. The dominant eigenvector is the amount of skill each player has at t=infinity, that is the amount of skill each player has once the markov chain has come to equilibrium. This is a very robust measure of each players skill using the topology of the win/loss space.

Some caveats: there are several problems when applying this directly, the biggest problem will be seperated webs (that is your markov chain will not be irreducible and so the power method will not be guaranteed to converge.) Lucky for you, google has dealt with all these problems and more when implementing their page rank algorithm and all that remains for you is to look up how they circumvent these problems if you are so inclined.