volleyball 4 on 4, balanced teams

[ndodge]

I will be hosting a volleyball event that has one court and will have 10, 11, or 12 players.  I hope to create balanced teams, 4 on 4.  I can rate my players in strength from 1 to X (X=10,11, or 12) and that number for each player can be a "weight" used for a player.  I would like to make balanced teams where the weight adds up to something close the same.  For example, team1= 1/4/5/8 vs team2=2/3/6/7 have teams of the same weight (i.e. 18).  I believe I can get every player having the same number of games if I do 10 rounds with 10 players, 11 rounds with 11 players, or 9 rounds with 12 players.  My hope is that someone can help me come up with 3 schedules where the team weight is closely balanced (e.g., within 2 or 3) and that the times people play WITH someone is fairly distributed (I'm not so concerned about how often you play against someone), but, if possible, as a final wish, ideally the top 2 players would play very little (ideally not at all) with the bottom 2 players-- or something similar where the top N players play little if at all with the bottom N players.

Thank you,
Nathan

[Ian Wakeling]

The team weightings make this a hard problem and I don't see any way of solving this without writing a special search algorithm. I think your criteria pull in different directions to some extent.  On the one hand you are saying you want pairs of players to play on the same team as each other equally often, and on the other hand you are saying you want to have only games that involve all high ability players or all low ability players.  So there is a difficult compromise that has to be made.

[Richard A. DeVenezias]

...as a final wish, ideally the top 2 players would play very little (ideally not at all) with the bottom 2 players...

If you are able to make the event one for charity the weights could all be 1

[ndodge]

Is there a sample algorithm that I could look at which might show a basic structure of such an algorithm ?  I used to do programming.  I have not spent much thought on how this might be done, but if shown a typical structure I could probably adjust to my situation.

Thanks,
Nathan

[Ian Wakeling]

Nathan,

I think the simplest solution would be a two-stage process.  So first find a basic schedule for 4 vs 4.  For example the following:

  ( 1  8 11  3 v  4  2  5  9)  (10  7  6)
  ( 2  9  1  4 v  5  3  6 10)  (11  8  7)
  ( 3 10  2  5 v  6  4  7 11)  ( 1  9  8)
  ( 4 11  3  6 v  7  5  8  1)  ( 2 10  9)
  ( 5  1  4  7 v  8  6  9  2)  ( 3 11 10)
  ( 6  2  5  8 v  9  7 10  3)  ( 4  1 11)
  ( 7  3  6  9 v 10  8 11  4)  ( 5  2  1)
  ( 8  4  7 10 v 11  9  1  5)  ( 6  3  2)
  ( 9  5  8 11 v  1 10  2  6)  ( 7  4  3)
  (10  6  9  1 v  2 11  3  7)  ( 8  5  4)
  (11  7 10  2 v  3  1  4  8)  ( 9  6  5)

which has all pairs of players with each other either two or three times.  It also has all pairs against each other either three or four times.

You could evaluate this schedule according to your weight system and calculate a criterion that is the total absolute difference in weight for all 11 games.  
If the player numbers are permuted in any way, say all the player 1s become player 2 and vice versa,  then the new schedule will have a different criterion.  With 11 players and about 40 million permutations to check, then it would be possible to take a brute force approach and evaluate all of them, picking the permutation that gives the smallest criterion.

None of this has addressed your desire to keep the high and low ability players apart, but I still think this is an unrealistic expectation, if each game involves 8 out of the 11 players, and you want to have teams of four with equal weight then you will need to mix high and low ability on the same team.

Hope that helps and please keep us posted if you implement something like this.

Ian.

PS Suitable starter schedules for 10 and 12 players are below (the 12 player one does not have best possible opponent balance so it may not be optimal).

 ( 10  4  2  9 v  7  5  6  3)  ( 8  1)
 (  6  5  3 10 v  8  1  7  4)  ( 9  2)
 (  7  1  4  6 v  9  2  8  5)  (10  3)
 (  8  2  5  7 v 10  3  9  1)  ( 6  4)
 (  9  3  1  8 v  6  4 10  2)  ( 7  5)
 ( 10  4  1  5 v  2  6  7  9)  ( 8  3)
 (  6  5  2  1 v  3  7  8 10)  ( 9  4)
 (  7  1  3  2 v  4  8  9  6)  (10  5)
 (  8  2  4  3 v  5  9 10  7)  ( 6  1)
 (  9  3  5  4 v  1 10  6  8)  ( 7  2)
 
  (12  3  4  5 v  2  8 10  1)  (9 11  7  6)
  (10  1  5  6 v  3  9 11  2)  (7 12  8  4)
  (11  2  6  4 v  1  7 12  3)  (8 10  9  5)
  ( 6  7 12  9 v  5  8  1  3)  (4 10 11  2)
  ( 4  8 10  7 v  6  9  2  1)  (5 11 12  3)
  ( 5  9 11  8 v  4  7  3  2)  (6 12 10  1)
  (12  8 11  6 v  4  2  5  9)  (3  1 10  7)
  (10  9 12  4 v  5  3  6  7)  (1  2 11  8)
  (11  7 10  5 v  6  1  4  8)  (2  3 12  9)
  ( 9 11  7  1 v 12 10  2  5)  (6  8  4  3)
  ( 7 12  8  2 v 10 11  3  6)  (4  9  5  1)
  ( 8 10  9  3 v 11 12  1  4)  (5  7  6  2)