I belong to a volleyball league which has a problem. When teams sign up, they have mark themselves as "beginner", "intermediate", or "advanced". After the league starts, beginners only play beginners, intermediates only play intermediates and advanceds only play advanceds. This is a major drawback because sometimes naive beginner teams sign up in the advanced division and then get slaughtered all season long (among other issues).
So, I'd like to design a fair system of play that puts all teams into one giant division and learns the skill level of teams as matches are recorded, and results in having good teams play good teams and weak teams play weak teams regardless of the initial seeding. How can this be done assuming the following conditions:
- There will be N teams playing over the course of W weeks.
- Each team plays one game per week (or potentially 0 games if a "bye" is necessary.)
- Teams will be seeded (1, 2, ... N) before the league starts. You can expect the initial seeds to be better than random guessing, but not perfect.
- No two teams should play each other twice within $k$ weeks. For example if $k=3$ and team A plays B in week 1, they should NOT play each other until week 4 at the earliest.
- Ties don't exist
Also, assume that all games for a given week are played at the same time as opposed to assuming a continuous feed of information throughout the week.
Obviously there can be multiple solutions to this problem. (For that reason, I think this question might be against the rules but I'm not sure.) Nonethless, finding a single good solution has proven to be challenging.