Balancing teams according to Elo rating

Question

I was wondering how you would go about creating a balancing system for a game based upon the Elo system.

I've read a couple of posts on here regarding a similar system. I do the balancing system based upon sorting a list and then assigning odd players to one team and even to the other.

The problem I've found is that sometimes if I do a list like that and there is a massive gap in player Elo rating. The teams are somewhat unbalanced.

Example:

A list sorted as 1700,1500,1500,1300,1300,1400,1400,1400,1200,1200

The teams would look like

• Team 1: 1700,1500,1300,1400,1200
• Team 2: 1500,1300,1400,1400,1200

The averages would come out to an unbalanced team.

I'm not too sure on how you would make a better balancing system. I can provide what I have written down so far but it's not much. Any help would be appreciated.

Answer 1

Your question has the following two parts:

Rating Problem
You need to use a rating system which takes care of rating each player playing as part of the team. Microsoft Research has created a TrueSkill system for the same which is an improved version of Elo Rating for multiplayer games.

The page also talks about it being an improved version of Glicko rating system. This is widely used in online chess forums as well.

Team Formation

You have a sorted list and you want to create two teams that are balanced (in terms of total rating). You need to look at Partition Problem. You leverage Dynamic Programming Solution which is pseudo-polynomial in time.