views:

65

answers:

2

Lets say we have a two players game, where one player always wins (there can't be draw).

The question is: How to divide n players into k divisions if we don't know anything about their skills? Each division should consist of the same number of players, and the best players players should be in first division, worst players in last division, and so on. There is additional constraint - player can't play more than p games (p is greater than k).

PS: This question is inspired by starcraft battle.net.

+1  A: 

Can you do any observations about the players before you divide them into divisions? If not, you have no information and so can only do a random assignment, then adjust what division they're in after a number of games. If we know absolutely nothing about the players, just assign player n to division n mod k.

The "after one round of games" (this may be the p games you mention), there's probably going to be an internal ranking within each division. Since each division is (essentially) random, people who placed well in one (random) division will probably belong in a "higher" division than those who placed badly. So, after an initial round, sort each player according to "wins so far", then assign the n/k first to the first division, then next n/k to the second division and so on.

Vatine
+1  A: 

The best thing you can do is use a swiss-like preliminary round to sort them out, and then you know their skills so you can divide them into divisions accordingly.

I'm doing that and it works great.

Lo'oris
Under one interpretation of the OP's question, the n players will each play p games, and then be divided into the k divisions based on the results. A p-round Swiss tournament sounds like an ideal way to do this.
Tom Anderson