Much like Tuthur, as they said in their excellent post, I recently(-ish) learned that creating pools for team tournaments was being done manually. Specifically, I found out when Amaranth complained that it took a lot of effort, and that it very much seemed like the kind of thing computers were better suited for than humans, but somehow the problem had not yet been solved. I like algorithmic challenges, so I set out to explore!
This will be a very long post, because in my exploration I found a lot of stuff that I think is interesting. If you don't find it interesting you can skip ahead to the conclusion.
We'll start with the problem definition:
The problem statement
Many team tournaments use a "pool system" to create matchups. That is, the players are divided into groups in which they play a small round robin. This is done so that there's some of the benefit of a group stage system (a player can still top a group!), but without the drawback of a possible "group of death", as different players in the same team face different teams. Creating these pools such that there is no large disparity in the amount of times each pair of teams faces off is the crux of the issue. When we consider mixed-tier tournaments, the pools cannot cross into multiple slots, so we can only create pools by partitioning the teams once for each slot. Formally:
The Social Golfer Problem
If R in the above definition is at most 1, then we would want a solution in which no team ever faces another twice. This specific case is a semi-famous mathematical problem called the Social Golfer Problem (SGP). It came into being when someone asked a usenet newsgroup for researchers (this was in the previous millennium) if there was a way to divide 32 golfers into 8 groups for 10 weeks, such that no two golfers were in the same group twice. This is exactly our problem with P=8, S=4, and T=10, and indeed this is known as the "8-4-10 SGP instance". Note also that this is exactly the problem of making WCoP pools if there were 32 teams!
A solution with 9 weeks was almost immediately found, and it's simple to prove that 11 is impossible (for example by using that R>1 in that case), but whether 10 weeks was possible was an unsolved problem for years until Alejandro Aguado published a solution in a very short paper, applying techniques already developed before the original question was posed.
Best I can tell, the eminent researcher of the problem was an Australian computer scientist by the name of Warwick Harvey. His research is largely behind a paywall, but he also kept a compendium of the best-known solutions on his university home page until his retirement. Unfortunately this has partially been lost to time, but the internet archive has a snapshot from August 2005. This snapshot even captured a note that new developments would move to another page, but that page has not been archived. Someone else more recently tried to find all known optimal solutions, and their efforts demonstrate its difficulty.
Regardless, we can learn two things from this. First, we have good solutions to some instances, which we can use out-of-the-box. For example, a world cup format with 16 teams would see each team face each other twice. This can be solved by taking the 4-4-5 solution listed on Harvey's page and using it twice. Second, we can see that it's been proven that not every optimal solution exists. If we take 6 groups of 6 golfers, we might expect to be able to go 7 weeks (R=1) before we have to repeat a matchup. In actual fact, you can't even do 4! This is a problem, but we'll get back to that. First, on to some solutions:
Evolutionary algorithms
My idea for a solution was to take the human approach, and speed it up with a computer. When humans make these partitions, I imagine they start by making essentially random partitions until one looks fairly good, and then, when they see that a certain pairing is too frequent or not frequent enough, make small adjustments to improve. This combination of random (global) search and guided (local) search can be captured simply in an evolutionary algorithm.
Essentially, we define what it means for a solution to be "good", which in our case means having matchup counts as close as possible to R. Then we make a whole bunch of random pools to start, and only keep the best ones around. This is our population. Then we iterate, and every iteration we spawn a bunch of new possible solutions, some of them random, and some "mutations" from our existing population (for example, we might shuffle the pools of one or two slots, or we might combine two good solutions to see if they fit well together), and finally we cull the population down to size by once again keeping only the best.
There is a bunch of cleverness possible, and much has been written about evolutionary algorithms, but through trial-and-error I found nothing that spectacularly boosted performance. The power of this technique is in the brute force, as it can check millions of permutations with minimal human effort.
The advantage of the evolutionary algorithm is that it always works to some degree. It will keep searching, and at the end spit out the best solution it found. Furthermore, it's theoretically guaranteed to eventually find the best possible solution, though this can take arbitrarily long.
The drawback is that doesn't generally find the best solution in a reasonable timeframe. If we take the main stage of the current WCoP as an example, we have 10 formats and 5 pools of 4 teams, which means R is between 1 and 2 (~1.6) and so we would like every matchup to occur once or twice. After leaving it running for a couple hours it found a solution where that was true for the vast majority, but there were still 8 teams that fought thrice, and one matchup never occurred. On the one hand this is not a big issue: the unfairness caused by a small amount of over-sampled matchups is negligible compared to the general luck of the draw. On the other hand, it's not very mathematically satisfying. Another drawback is that we don't know whether the found solution is (close to) optimal.
All that being said, tournaments that used pools created with this method include the 1v1 World Cup and the PU World Cup.
Integer Linear Programming
Integer Linear Programming (ILP) is a particular form of the more general constraint programming family of computing paradigms. The idea of these paradigms is that many problems can be fit into the same general mold, and we can then use highly optimized solvers for these particular molds. In particular, many problems can be rewritten as "find values for variables X out of possible values D such that constraints C all hold". In the case that all possible values D are integers and all constraints C are linear, this is an ILP problem. For what such a transformation roughly looks like I'll refer to Tuthur's post.
Because the Social Golfer Problem is used as a benchmark for ILP solvers and many instances are as of yet unsolved despite researchers working on them and despite their use of strong hardware, and because we know from the theory of the SGP that a perfect solution does not always exist, I figured using these methods would not yield results for a hobby project on a modestly powered computer. Therefore, I did not pursue this avenue at all until Tuthur showed highly promising results.
The advantage of this method is obvious: it gives optimal results. Problems arise when it doesn't give results at all. The exact method of encoding the problem, as well as the choice of solver, can have a very large effect on how long it takes to solve an instance. Because of the black-box nature of the solvers it's very difficult to predict how modifications will affect the runtime, thus requiring arduous trial-and-error. In addition, solving decently sized instances is generally intractable. It can find a solution, but when it doesn't it tends not to terminate as searching the whole space is infeasible. Thus, when a solution is not found, we don't know if a solution exists or not. It probably only finds solutions to problems where solutions are relatively dense in the space.
To circumvent the problem of a perfect solution not existing, it's possible to relax the constraints to allow for a non-perfect solution, and combine it with an optimization function (turning it into constraint optimization programming). The solver will then find the solution that satisfies the constraints and maximizes the optimization function. This would always give the best possible solution, but in practice it is much harder to solve, and I've not found any success with it. Relaxing the constraints makes it much harder for the solver to cut the search space, thus worsening performance.
When it works, however, ILP is highly satisfying. Where the evolutionary algorithm was able to find an okay-ish solution for the WCoP pools, ILP was able to find the perfect solution. Indeed, the main stage of WCoP this year used pools created by this method. The solution found is attached to this post as an example of the format.
Further work
I want to get the ILP solver working in such a way that it uses the relaxed constraints while optimizing the objective function, but in such a way that it reports on intermediate solutions. This should be possible, but I've been struggling getting it to work. There's a chance that this method would consistently outperform the evolutionary algorithm, rendering that method obsolete. That would certainly help simplify the approach. If I can get that to work, I'd like to clean up the code and put it on git if I have the time.
I'm already keeping track of all the solutions found so that they may be re-used, which will hopefully continue to grow. Open-sourcing that would also allow others to submit solutions, which would be helpful (and fun).
Conclusion
Computationally creating pools for team tournaments with mixed tiers is possible, but there is no one method that is guaranteed to give perfect results. Using existing literature and an ensemble of methods, however, pools that are good enough can be generated. We also mustn't overstate the importance of a perfect solution. For example, the PUWC OP said that "Divisions will be assigned randomly and each team will play each other team at least once and not more than twice". This was not true, as there were 12 matchups that occurred three times. To my knowledge, no one actually even noticed this.
The most important take-away from this post is to not make pools by hand. Your time is more valuable than that. If you're hosting a mini-pools based team tour with mixed tiers, or with a single tier but you're okay with treating them all as different, feel free to hit me up for an at least decent schedule.
If you've read this whole post, I hope you found it at least a bit interesting
This will be a very long post, because in my exploration I found a lot of stuff that I think is interesting. If you don't find it interesting you can skip ahead to the conclusion.
We'll start with the problem definition:
The problem statement
Many team tournaments use a "pool system" to create matchups. That is, the players are divided into groups in which they play a small round robin. This is done so that there's some of the benefit of a group stage system (a player can still top a group!), but without the drawback of a possible "group of death", as different players in the same team face different teams. Creating these pools such that there is no large disparity in the amount of times each pair of teams faces off is the crux of the issue. When we consider mixed-tier tournaments, the pools cannot cross into multiple slots, so we can only create pools by partitioning the teams once for each slot. Formally:
- We consider a tournament with pool size S, number of pools P and team size T. This implies there are S*P teams.
- We only allow solutions of the form: T partitions of the S*P teams, into P sets of size S. Two teams battle when they are in the same set for a particular partition.
- We define a rate R which is the average amount of times any two teams face each other. This is equal to (S-1) * T / (S*P-1).
- We want the actual count of each matchup to be as close as possible to R. Specifically it should be either k or k+1 where k ≤ R < k+1.
The Social Golfer Problem
If R in the above definition is at most 1, then we would want a solution in which no team ever faces another twice. This specific case is a semi-famous mathematical problem called the Social Golfer Problem (SGP). It came into being when someone asked a usenet newsgroup for researchers (this was in the previous millennium) if there was a way to divide 32 golfers into 8 groups for 10 weeks, such that no two golfers were in the same group twice. This is exactly our problem with P=8, S=4, and T=10, and indeed this is known as the "8-4-10 SGP instance". Note also that this is exactly the problem of making WCoP pools if there were 32 teams!
A solution with 9 weeks was almost immediately found, and it's simple to prove that 11 is impossible (for example by using that R>1 in that case), but whether 10 weeks was possible was an unsolved problem for years until Alejandro Aguado published a solution in a very short paper, applying techniques already developed before the original question was posed.
For those wondering, the complexity class of the SGP is unknown, but the "completion problem" that asks if a partial schedule can be completed to become a solution is known to be NP-Complete, see e.g. here.
Note that the regular problem is not trivially in NP, as the size of a full schedule is exponential in the size of the input so the simple verification does not suffice.
Note that the regular problem is not trivially in NP, as the size of a full schedule is exponential in the size of the input so the simple verification does not suffice.
Best I can tell, the eminent researcher of the problem was an Australian computer scientist by the name of Warwick Harvey. His research is largely behind a paywall, but he also kept a compendium of the best-known solutions on his university home page until his retirement. Unfortunately this has partially been lost to time, but the internet archive has a snapshot from August 2005. This snapshot even captured a note that new developments would move to another page, but that page has not been archived. Someone else more recently tried to find all known optimal solutions, and their efforts demonstrate its difficulty.
Regardless, we can learn two things from this. First, we have good solutions to some instances, which we can use out-of-the-box. For example, a world cup format with 16 teams would see each team face each other twice. This can be solved by taking the 4-4-5 solution listed on Harvey's page and using it twice. Second, we can see that it's been proven that not every optimal solution exists. If we take 6 groups of 6 golfers, we might expect to be able to go 7 weeks (R=1) before we have to repeat a matchup. In actual fact, you can't even do 4! This is a problem, but we'll get back to that. First, on to some solutions:
Evolutionary algorithms
My idea for a solution was to take the human approach, and speed it up with a computer. When humans make these partitions, I imagine they start by making essentially random partitions until one looks fairly good, and then, when they see that a certain pairing is too frequent or not frequent enough, make small adjustments to improve. This combination of random (global) search and guided (local) search can be captured simply in an evolutionary algorithm.
Essentially, we define what it means for a solution to be "good", which in our case means having matchup counts as close as possible to R. Then we make a whole bunch of random pools to start, and only keep the best ones around. This is our population. Then we iterate, and every iteration we spawn a bunch of new possible solutions, some of them random, and some "mutations" from our existing population (for example, we might shuffle the pools of one or two slots, or we might combine two good solutions to see if they fit well together), and finally we cull the population down to size by once again keeping only the best.
There is a bunch of cleverness possible, and much has been written about evolutionary algorithms, but through trial-and-error I found nothing that spectacularly boosted performance. The power of this technique is in the brute force, as it can check millions of permutations with minimal human effort.
The advantage of the evolutionary algorithm is that it always works to some degree. It will keep searching, and at the end spit out the best solution it found. Furthermore, it's theoretically guaranteed to eventually find the best possible solution, though this can take arbitrarily long.
The drawback is that doesn't generally find the best solution in a reasonable timeframe. If we take the main stage of the current WCoP as an example, we have 10 formats and 5 pools of 4 teams, which means R is between 1 and 2 (~1.6) and so we would like every matchup to occur once or twice. After leaving it running for a couple hours it found a solution where that was true for the vast majority, but there were still 8 teams that fought thrice, and one matchup never occurred. On the one hand this is not a big issue: the unfairness caused by a small amount of over-sampled matchups is negligible compared to the general luck of the draw. On the other hand, it's not very mathematically satisfying. Another drawback is that we don't know whether the found solution is (close to) optimal.
All that being said, tournaments that used pools created with this method include the 1v1 World Cup and the PU World Cup.
Integer Linear Programming
Integer Linear Programming (ILP) is a particular form of the more general constraint programming family of computing paradigms. The idea of these paradigms is that many problems can be fit into the same general mold, and we can then use highly optimized solvers for these particular molds. In particular, many problems can be rewritten as "find values for variables X out of possible values D such that constraints C all hold". In the case that all possible values D are integers and all constraints C are linear, this is an ILP problem. For what such a transformation roughly looks like I'll refer to Tuthur's post.
ILP is NP-Complete. In fact, the variation where every variable is either 1 or 0 (which our problem can be, depending on the encoding) was one of the 21 original problems shown to be such by Karp, in his famous paper which is foundational to the interest in P vs NP.
Because the Social Golfer Problem is used as a benchmark for ILP solvers and many instances are as of yet unsolved despite researchers working on them and despite their use of strong hardware, and because we know from the theory of the SGP that a perfect solution does not always exist, I figured using these methods would not yield results for a hobby project on a modestly powered computer. Therefore, I did not pursue this avenue at all until Tuthur showed highly promising results.
The advantage of this method is obvious: it gives optimal results. Problems arise when it doesn't give results at all. The exact method of encoding the problem, as well as the choice of solver, can have a very large effect on how long it takes to solve an instance. Because of the black-box nature of the solvers it's very difficult to predict how modifications will affect the runtime, thus requiring arduous trial-and-error. In addition, solving decently sized instances is generally intractable. It can find a solution, but when it doesn't it tends not to terminate as searching the whole space is infeasible. Thus, when a solution is not found, we don't know if a solution exists or not. It probably only finds solutions to problems where solutions are relatively dense in the space.
To circumvent the problem of a perfect solution not existing, it's possible to relax the constraints to allow for a non-perfect solution, and combine it with an optimization function (turning it into constraint optimization programming). The solver will then find the solution that satisfies the constraints and maximizes the optimization function. This would always give the best possible solution, but in practice it is much harder to solve, and I've not found any success with it. Relaxing the constraints makes it much harder for the solver to cut the search space, thus worsening performance.
When it works, however, ILP is highly satisfying. Where the evolutionary algorithm was able to find an okay-ish solution for the WCoP pools, ILP was able to find the perfect solution. Indeed, the main stage of WCoP this year used pools created by this method. The solution found is attached to this post as an example of the format.
Further work
I want to get the ILP solver working in such a way that it uses the relaxed constraints while optimizing the objective function, but in such a way that it reports on intermediate solutions. This should be possible, but I've been struggling getting it to work. There's a chance that this method would consistently outperform the evolutionary algorithm, rendering that method obsolete. That would certainly help simplify the approach. If I can get that to work, I'd like to clean up the code and put it on git if I have the time.
I'm already keeping track of all the solutions found so that they may be re-used, which will hopefully continue to grow. Open-sourcing that would also allow others to submit solutions, which would be helpful (and fun).
Conclusion
Computationally creating pools for team tournaments with mixed tiers is possible, but there is no one method that is guaranteed to give perfect results. Using existing literature and an ensemble of methods, however, pools that are good enough can be generated. We also mustn't overstate the importance of a perfect solution. For example, the PUWC OP said that "Divisions will be assigned randomly and each team will play each other team at least once and not more than twice". This was not true, as there were 12 matchups that occurred three times. To my knowledge, no one actually even noticed this.
The most important take-away from this post is to not make pools by hand. Your time is more valuable than that. If you're hosting a mini-pools based team tour with mixed tiers, or with a single tier but you're okay with treating them all as different, feel free to hit me up for an at least decent schedule.
If you've read this whole post, I hope you found it at least a bit interesting
