I recently read about how the World Cup draw, as currently designed, can frequently create unbalanced groups. Some countries end up in very challenging groups; other groups are much weaker, overall. A French mathematician, Julien Guyon, describes an alternative method that is more likely to result in balanced groups. His method does seem to result in more balanced groups -- although I am always very edgy about measuring a group's strength merely looking at the average strength. One way to achieve an average strength group is by putting very strong and very weak teams together. Another way to achieve an average strength group is by putting all mediocre teams together. But I would hardly call these two groups balanced. Ideally, we should be looking at each group's average AND its standard deviation. The high-low method will yield a high standard deviation; the mediocre teams methods will yield a low standard deviation, and it would be rejected for this reason. I looked at Guyon's method and found that it did produce groups with high standard deviations, so his method resulted in fairly balanced groups.
I applied my own method to the task to see how it would fare.
Step 1: Pick the eight middle teams.
Step 2: Match the top eight teams to the middle teams. I did so by looking at the standard deviation of each match. If team A had a world rank of 1 and team J had a world rank of 9, this match would have a standard deviation of 4. If team K had a world rank of 11, then an A - K match would have a standard deviation of 5. If two teams were not allowed to compete in the same group because the teams were from the same region of the world, then the standard deviation was set to zero. A computer picked the set of eight matches that had the largest overall standard deviations. That could mean the single highest match for a particular team was not chosen so that the overall standard deviations would be as large as possible. For example, team A might not be matched against K so that K could be matched against a better opponent country.
Step 3: Repeat for the next eight teams, looking at the standard deviation of the the group of three teams.
Step 4: Repeat for the bottom eight teams.
The groups are balanced compared to each other as a byproduct of trying to force each group to have a maximum standard deviation. My one trial came out very slightly ahead of one trial of Guyon's method; they are quite comparable.
Here's the download.
I've written about this method before.
Showing posts with label balancing. Show all posts
Showing posts with label balancing. Show all posts
Wednesday, June 4, 2014
Wednesday, February 2, 2011
A method to create balanced groups
I like for my students to work together in groups. Unfortunately, they always choose to sit with their friends. So I have to assign their groups.
Let's say on the first day of class, I give them a 20 point quiz to see how much of last year's math they remember. I can also use that information to create balanced groups; I don't want to put all the weak students in one group and all the strong students in another. Rather, I would like each group to include weak students, strong students, and average students.
One way to look at this problem is that I want each group's average to be close to the class average. One could design an algorithm to create the groups this way. But I realized as I was designing it that one has to make ad hoc rules that throw out (a) groups composed of entirely average students and (b) groups composed evenly of strong and weak students but no average ones. I wanted a more elegant algorithm.
The other way to look at the problem is that I want each group to be as diverse as possible. If one maximizes each group's standard deviation, then (a) groups are ruled out. It is true that (b) groups would have the largest standard deviation possible -- but the magic here is that standard deviation is non-linear. Let's say that you have starting forming two groups -- group 1 {S, W, W} and group 2 {S, A, A} -- you have two more students to assign {S, A}. It is true that assigning the strong student to group 1 {S, S, W, W} makes its standard deviation bigger than assigning to it the average student {S, A, W, W}. In other words, std. dev. 1s > std. dev. 1a. But the key is that it makes a much bigger difference to group 2: std. dev. 2s is much, much bigger than std. dev. 2a.
Algebraically, (std. dev. 1s - std. dev. 1a) < (std. dev. 2s - std. dev. 2a). Equivalently, (std. dev. 1s + std. dev. 2a) < (std. dev. 2s + std. dev. 1a). Without algebra, the point is that (b) groups would never happen if you try to maximize the standard deviation of each group -- overall, you're always better to maximize the standard deviation of the least diverse group first. With this fact in mind, this becomes a simple maximization problem. This is an extremely powerful idea: to create the most balanced groupings, you make each group as diverse as possible. Below is an example. A fictional class of six will be divided into two groups.
As you can see, each colored line represents a possible set of groupings. The worst groupings are highlighted in red, the mediocre groupings are highlighted in yellow, and the good groupings are highlighted in green. The first cell under a group is its standard deviation, and the second cell is the group's average. I ranked the groupings by creating a geometric average (a b) ^ 0.5 of the two groups' standard deviations. I do generally agree with the rankings. In the red groupings, the groups are skewed: all strong students in one, all weak students in the other. As a result, both groups have low standard deviations. In the yellow groupings, one group is skewed, and the other group includes too many average students. As a result, one group has a high standard deviation, while the other has a low standard deviation. In the green groupings, both groups are balanced, so both have decent standard deviations.
As you'll notice, even for the best groupings, the average standard deviation of the groups doesn't exceed the standard deviation of the entire class. That's as it should be, but I'll leave that proof to an industrious reader.
Another, more realistic (though still fictional) example follows: dividing a 16-student class into four groups. There are too many possible groupings to list (more than 2.6 million), so I used an algorithm to pick a reasonably good solution. (I started by putting the four students in the very middle in different groups, then given that initial condition, the algorithm then assigned the remaining students in a way that attempted to maximize each group's standard deviation.) You can see the results below:
I lettered the students from A to P, strongest to weakest, and indicated a percentage grade for each. The four middle students were G, H, I, and J. You can see that the algorithm was able to do a decent job of maximizing each group's standard deviation (its explicit task); some came out slightly ahead, but they're all relatively large. But you can see how well the algorithm did creating balanced groups: 82.2, 82.4, 84, and 84.2. Remember, this result is an accidental byproduct of trying to create a solution that maximizes each group's standard deviation.
Why do I care so much about this? For one, I really do like having an algorithm that creates evenly balanced groups in my class. But two, I want to build this algorithm into a tabulation program -- for partial round robins. In a partial round robin, each team should hit a representative cross-section of the pool. Consider a 12-team round robin with 6 preliminary rounds. It's too tight to run a regular tournament and respect win-loss brackets. But if you can rank the teams before they arrive, then using my algorithm, each team could debate six opponents that are strong, mediocre, and weak.
Let's say on the first day of class, I give them a 20 point quiz to see how much of last year's math they remember. I can also use that information to create balanced groups; I don't want to put all the weak students in one group and all the strong students in another. Rather, I would like each group to include weak students, strong students, and average students.
One way to look at this problem is that I want each group's average to be close to the class average. One could design an algorithm to create the groups this way. But I realized as I was designing it that one has to make ad hoc rules that throw out (a) groups composed of entirely average students and (b) groups composed evenly of strong and weak students but no average ones. I wanted a more elegant algorithm.
The other way to look at the problem is that I want each group to be as diverse as possible. If one maximizes each group's standard deviation, then (a) groups are ruled out. It is true that (b) groups would have the largest standard deviation possible -- but the magic here is that standard deviation is non-linear. Let's say that you have starting forming two groups -- group 1 {S, W, W} and group 2 {S, A, A} -- you have two more students to assign {S, A}. It is true that assigning the strong student to group 1 {S, S, W, W} makes its standard deviation bigger than assigning to it the average student {S, A, W, W}. In other words, std. dev. 1s > std. dev. 1a. But the key is that it makes a much bigger difference to group 2: std. dev. 2s is much, much bigger than std. dev. 2a.
Algebraically, (std. dev. 1s - std. dev. 1a) < (std. dev. 2s - std. dev. 2a). Equivalently, (std. dev. 1s + std. dev. 2a) < (std. dev. 2s + std. dev. 1a). Without algebra, the point is that (b) groups would never happen if you try to maximize the standard deviation of each group -- overall, you're always better to maximize the standard deviation of the least diverse group first. With this fact in mind, this becomes a simple maximization problem. This is an extremely powerful idea: to create the most balanced groupings, you make each group as diverse as possible. Below is an example. A fictional class of six will be divided into two groups.
As you can see, each colored line represents a possible set of groupings. The worst groupings are highlighted in red, the mediocre groupings are highlighted in yellow, and the good groupings are highlighted in green. The first cell under a group is its standard deviation, and the second cell is the group's average. I ranked the groupings by creating a geometric average (a b) ^ 0.5 of the two groups' standard deviations. I do generally agree with the rankings. In the red groupings, the groups are skewed: all strong students in one, all weak students in the other. As a result, both groups have low standard deviations. In the yellow groupings, one group is skewed, and the other group includes too many average students. As a result, one group has a high standard deviation, while the other has a low standard deviation. In the green groupings, both groups are balanced, so both have decent standard deviations.
As you'll notice, even for the best groupings, the average standard deviation of the groups doesn't exceed the standard deviation of the entire class. That's as it should be, but I'll leave that proof to an industrious reader.
Another, more realistic (though still fictional) example follows: dividing a 16-student class into four groups. There are too many possible groupings to list (more than 2.6 million), so I used an algorithm to pick a reasonably good solution. (I started by putting the four students in the very middle in different groups, then given that initial condition, the algorithm then assigned the remaining students in a way that attempted to maximize each group's standard deviation.) You can see the results below:
I lettered the students from A to P, strongest to weakest, and indicated a percentage grade for each. The four middle students were G, H, I, and J. You can see that the algorithm was able to do a decent job of maximizing each group's standard deviation (its explicit task); some came out slightly ahead, but they're all relatively large. But you can see how well the algorithm did creating balanced groups: 82.2, 82.4, 84, and 84.2. Remember, this result is an accidental byproduct of trying to create a solution that maximizes each group's standard deviation.
Why do I care so much about this? For one, I really do like having an algorithm that creates evenly balanced groups in my class. But two, I want to build this algorithm into a tabulation program -- for partial round robins. In a partial round robin, each team should hit a representative cross-section of the pool. Consider a 12-team round robin with 6 preliminary rounds. It's too tight to run a regular tournament and respect win-loss brackets. But if you can rank the teams before they arrive, then using my algorithm, each team could debate six opponents that are strong, mediocre, and weak.
Subscribe to:
Posts (Atom)