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?

Solution 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.

Solution 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.

Solution 3

One way would be to simply create a list of players looking for matches at any given time, sorted by player rank. Once you've reached enough people to start a new match (or perhaps, two less than the required), group them as such:

1. Remove best and worst player and put them on team 1
2. Remove now-best and now-worst player (really second-best and second worst) and put them on team 2
3. If there are only two players left, place each one on different teams, depending on who has the lowest combined score. Otherwise, repeat:
4. Remove now-best and now-worst and put them on team 1
5. Remove now-best and now-worst and put them on team 2

etc. etc. etc. until your teams are filled.

If you decided to start a new match with less than the required, then here it is time to let the players wait for new people to join. As soon as a new person joins, you're going to want to put them on the open team with the least combined score.

Alternatively, if you wanted to avoid games that combined good and bad players on the same team, you could split up everyone into tiers, (groups based on their ranking) and only match people within the same tier. This would require a new open/sorted list for each extra tier.

Example

Game is 4v4

A - 1000 pnts

B - 800 pnts

C - 600 pnts

D - 400 pnts

E - 200 pnts

F - 100 pnts

As soon as you get these six, group them into teams as such:

Team 1: A, F, D (combined score 1500)

Team 2: B, E, C (combined score 1600)

Now, we wait for two more players to join.

First, player E comes along with 500 pnts. He goes to Team 1, because they have a lower combined score.

Then, player F comes with 800 pnts. He goes to Team 2, because are the only open team left.

Total teams:

Team 1: A, F, D, E (combined score 2000)

Team 2: B, E, C, F (combined score 2400)

Note that the teams were actually pretty fair until the last two came in. To be honest, the best way would be to only create the match when you have enough players to start it. But then the wait times might be too long for the player.

Adjust with how much you need before forming the match. Lower = less wait time, more possibly unfair. Higher = more wait time, less possibly unfair.

If you have a pre-game screen, lower would also offer more time for people to chat and talk with their to-be teammates while waiting.

Solution 4

It is difficult to estimate the skill of any one player by a single metric and such a method is prone to abuse. However, if you only care about implementing something simple that will work well try the following:

1. keep track of wins and losses
2. use the percentage of wins vs losses as the statistic to match players ( in some sense of the word match, i.e. group players with similar percentages)

This has the obvious downfall of the case where a player may have a win-loss ratio of 5-0 and another of 50-20, the first has an infinite percentage while the other has a more reasonable percentage. It makes sense for the matching system to acknowledge this and be far more confident that the latter player has actual more skill because of the consistency required; however, pitting the two players against each other would probably be a good thing because the 5-0 player is probably trying to work the system by playing versus weaker players so pitting him against a consistently good player would do everyone good.

Note, I speak from experience from playing only strategy games such as Warcraft 3 where this is the typical match making behaviour. It seems to me like the percentage of wins over losses is a great metric by which to match players.

View more solutions

Comments

[Amber]

Putting the best and worst players on the team will often frustrate both, because the overall mix of skill levels in the game will be so large that some players will get dominated by others, even if the overall team balance is okay. Sure, the worst player might be on the winning team, but their personal experience will probably be terrible as the 2nd-best player fights against them, and the #1 player will be annoyed at having to put up with the worst player being on their team.

[Peter Recore]

this doesn't work so great unless all the matches are randomly arranged. If I have a 1-2 record in chess against Gary Kasparov, that is almost always much better than you having a 100-1 record against a preschooler. But your algorithm would rank you much higher than me.

[ldog]

@Peter Recore: by the wording of the question, I assumed that what he intended for was the system to do automatic or "random" matching as you call it.

[Peter Recore]

But once you start assigning matches based on skill level, then you can't use the winning % as a useful metric anymore. winning 50% of games against a pro is not the same as winning 50% of games against a newb.

[Amber]

Microsoft Research is actually one of the better research divisions in its field - the rest of the company just doesn't always follow suit.