How to select fair teams

If you remember back to High School (or maybe you’re still in school), you might have played an ad-hoc game of soccer, football, frisbee, basketball, volleyball, hockey …

Typically, there was a random collection of people who wanted to play, and no organized structure for who plays on which of the two teams.

In order to make the teams, typically two captains (let’s call them A and B) were nominated and they alternated calling people to join their respective teams. Using this protocol, the selections went like this: ABABAB …

It’s assumed that each captain wants to win, and thus will select the most skillful player still in the unclassified pool when it’s their turn to pick next. In the above protocol, clearly captain A has an advantage as they have first pick of everyone left at every turn. Alternating certainly helps balancing things a little, but can we divine a system that is fairer?

For instance, if captain A gets to pick first, should B be allowed to pick the next two selections instead of one? How about three? I know it sounds crazy, but maybe it is fairer to allow A to pick the first three players, then B to have free reign to pick, say, the next six picks? How about seven?, How about alternating two picks, then three, and switching over? Or any of the other combinations in between? Should there be symmetry?

Let’s take a look at games of varying sizes. We need to model things by appreciating that each of the people in the pool will have a different ‘skill’ level. When I first looked at modelling this, I gave each player a random floating point skill score in the range [0,1] and averaged millions of iterations to look at the results. I then repeated the experiment using just a linear ranking of the skills from [0,1] for the players and found I got (within random error) exactly the same results. With linear ranking, I only need to run the simulation once per trial, so it’s much quicker.

I appreciate that, in real life, skills probably follow more of a Gaussian distribution, with less likely outliers at the extremes, and the majority being closer to a mean but, realistically, skill is not really something that is fantastically accurate to linearly combine anyway. After all, is a player with a ‘skill’ of 0.8 twice as good a player with a skill of 0.4? Are the two players [0.75, 0.25], equal to the two players [0.60, 0.40]? or three players with skills [0.10, 0.20, 0.70]? Of course not, but we have to make some assumptions and simplifications to model this.

What we have is a partitioning problem. We have a set of 2N players, and we wish to subdivide this into two sets of N players such that the difference between the sum of the skills in each set is as small as possible.

Another way to think about this is like a balance beam scales problem. Instead of players having skill, imagine they are masses instead. We need to place an equal number of ‘players’ on each side of the scales to minimize the deflection (to either side).

We are assuming there will always be an even number sized pool of players, and both final teams will be the same size. As stated earlier, we’re also assuming that each captain, when it is their turn to pick, selects the most skillful player remaining in the pool.

Let's look at teams of increasing sizes.

This is trivial but included for completeness. One person is selected for one team, the other goes on the other. There are no choices in the picking protocol.

There are 4C2 = 6 possible ways to select two players from four: AABB, ABAB, ABBA, BAAB, BABA, BBAA. However, with symmetry, (for instance AABB ==  BBAA) there are only three distinct combinations: AABB, ABAB, ABBA.

Ever without math, we can see AABB is the least fair as A gets to pick the best two players, and B is stuck with what is left.

Let’s give the players a linear skill distribution and look at the other two selection methods. If we give the players the skills [1.00, 0.75, 0.50, 0.25], then we can sum up the scores for each team and calculate the absolute difference between the two teams’ total scores. We find that for ABAB the difference is 0.50 and for ABBA the difference is 0.00 (a perfect balance!) For comparison, AABB has an imbalance of 1.00

For four players, the fairest system is for the picks to follow the schema ABBA.

Even at four players, alternating ABAB is not the optimal strategy.

A game of doubles tennis has two players on each team.

There are 6C3 = 20 possible ways to select three players from six, but again, with symmetry this reduces to ten distinct groups: AAABBB, AABABB, AABBAB, AABBBA, ABAABB, ABABAB, ABABBA, ABBAAB, ABBABA, ABBBAA

Assigning the skills of the player pool as [6/6, 5/6, 4/6, 3/6, 2/6, 1/6] we get the following results for the imbalance between the teams (absolute value of difference between sum of skills on each team).

Again, no surprise that AAABBB is the least fair (with a delta of what is equivalent to 1.5 times the skill of the best player). The alternating system ABABAB reduces this to a delta for 0.50 (a score it shares with AABBBA and ABBBAA), but three strategies are fairer, these are ABABBA, ABBAAB, and ABBABA which each reduce the delta down to 0.1667 (1/n).

Croquet is a game that can be played with three players per team.

There are 35 distinct ways teams of four can be pulled from eight players (8C4)/2 = 35.

Again, assigning linear distribution of skills gives the following results:

ABABABAB (the simple alternating strategy) results in delta of 0.50

There are four ‘perfect’ selection patterns: AABBBBAA, ABABBABA, ABBAABBA, ABBABAAB

Some of these should not be a surprise. After all, we know from 4 player analysis that ABBA is perfect distribution, so recursively, if we pull ABBA off first (balanced), we know what is left is just the same thing (another balanced set of four; a self-similar problem with a smaller set).

There are four players per team in the sport of Polo.

The combinations are getting larger now. There are 126 distinct ways to arrange ten players into two teams.

Using a linear skill distribution of [1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1] there are twenty optimal picking strategies that result in an absolute error of 0.1 (compared to the delta for the simple alternating patter of 0.5)

AABBABBBAA AABBBABABA AABBBABBAA AABBBBAAAB AABBBBAABA ABAABBBBAA ABABABBABA ABABABBBAA ABABBAABBA ABABBABAAB ABABBABABA ABABBBAAAB ABBAABABBA ABBAABBAAB ABBAABBABA ABBABAABAB ABBABAABBA ABBABABAAB ABBBAAAABB ABBBAAABAB

It’s interesting in that some of these optimal strategies allow captain A to pick the first two players. The more people there are to pick from, the closer the skills of any adjacent pair becomes.

There are five players, per side, in a game of basketball.

There are 462 distinct ways to arrange twelve players into two teams of six.

Of these there are 29 optimal solutions with an absolute delta of zero (Because of how I’m generating the linear ramp of skills, you may have noticed that if there is an even number of players in each team, then the minimum delta will be zero. If there are an odd number of players, then the minimum delta is 1/n).

Here are the optimal picking strategies for twelve players:

AAABBBBBBAAA AABABBBBABAA AABBABBABBAA AABBABBBAABA AABBBAABBBAA AABBBABABABA AABBBABBAAAB AABBBBAAABBA AABBBBAABAAB ABAABBBABBAA ABAABBBBAABA ABABABABBBAA ABABABBABABA ABABABBBAAAB ABABBAABBABA ABABBABAABBA ABABBABABAAB ABABBBAAABAB ABBAAABBBBAA ABBAABABBABA ABBAABBAABBA ABBAABBABAAB ABBABAABABBA ABBABAABBAAB ABBABABAABAB ABBABBAAAABB ABBBAAAABBBA ABBBAAABABAB ABBBAABAAABB

It’s fascinating to see that there is an optimal solutionin which captain A gets to pick the first three! (and the last three). It’s refreshing to see the solutions which repeat ABBA (or the canonical BAAB), as well as the weird ones like ABBBAABAAABB

There are six players, per side, in a volleyball game (and ice hockey).

There are 1,716 distinct ways to arrange 14 players into two teams of seven, and this results in 169 optimal picking strategies with a delta of 1/n ≈ 0.071429

AAABBBABBBBAAA AAABBBBABBABAA AAABBBBABBBAAA AAABBBBBAABBAA AAABBBBBABAABA AAABBBBBABABAA AAABBBBBBAAAAB AAABBBBBBAAABA AABABABBBBBAAA AABABBABBBABAA AABABBABBBBAAA AABABBBABABBAA AABABBBABBAABA AABABBBABBABAA AABABBBBAABABA AABABBBBAABBAA AABABBBBABAAAB AABABBBBABAABA AABABBBBBAAAAB AABBAABBBBABAA AABBAABBBBBAAA AABBABABBABBAA AABBABABBBAABA AABBABABBBABAA AABBABBAABBBAA AABBABBABABABA AABBABBABABBAA AABBABBABBAAAB AABBABBABBAABA AABBABBBAAABBA AABBABBBAABAAB AABBABBBAABABA AABBABBBABAAAB AABBBAABABBBAA AABBBAABBABABA AABBBAABBABBAA AABBBAABBBAAAB AABBBAABBBAABA AABBBABAABBABA AABBBABAABBBAA AABBBABABAABBA AABBBABABABAAB AABBBABABABABA AABBBABABBAAAB AABBBABBAAABAB AABBBABBAAABBA AABBBABBAABAAB AABBBBAAABABBA AABBBBAAABBAAB AABBBBAAABBABA AABBBBAABAABAB AABBBBAABAABBA AABBBBAABABAAB AABBBBABAAAABB AABBBBABAAABAB AABBBBBAAAAABB ABAAABBBBBBAAA ABAABABBBBABAA ABAABABBBBBAAA ABAABBABBABBAA ABAABBABBBAABA ABAABBABBBABAA ABAABBBAABBBAA ABAABBBABABABA ABAABBBABABBAA ABAABBBABBAAAB ABAABBBABBAABA ABAABBBBAAABBA ABAABBBBAABAAB ABAABBBBAABABA ABAABBBBABAAAB ABABAABBBABBAA ABABAABBBBAABA ABABAABBBBABAA ABABABABABBBAA ABABABABBABABA ABABABABBABBAA ABABABABBBAAAB ABABABABBBAABA ABABABBAABBABA ABABABBAABBBAA ABABABBABAABBA ABABABBABABAAB ABABABBABABABA ABABABBABBAAAB ABABABBBAAABAB ABABABBBAAABBA ABABABBBAABAAB ABABBAAABBBBAA ABABBAABABBABA ABABBAABABBBAA ABABBAABBAABBA ABABBAABBABAAB ABABBAABBABABA ABABBAABBBAAAB ABABBABAABABBA ABABBABAABBAAB ABABBABAABBABA ABABBABABAABAB ABABBABABAABBA ABABBABABABAAB ABABBABBAAAABB ABABBABBAAABAB ABABBBAAAABBBA ABABBBAAABABAB ABABBBAAABABBA ABABBBAAABBAAB ABABBBAABAAABB ABABBBAABAABAB ABABBBABAAAABB ABBAAABBABBBAA ABBAAABBBABABA ABBAAABBBABBAA ABBAAABBBBAAAB ABBAAABBBBAABA ABBAABAABBBBAA ABBAABABABBABA ABBAABABABBBAA ABBAABABBAABBA ABBAABABBABAAB ABBAABABBABABA ABBAABABBBAAAB ABBAABBAABABBA ABBAABBAABBAAB ABBAABBAABBABA ABBAABBABAABAB ABBAABBABAABBA ABBAABBABABAAB ABBAABBBAAAABB ABBAABBBAAABAB ABBABAAABBBABA ABBABAAABBBBAA ABBABAABABABBA ABBABAABABBAAB ABBABAABABBABA ABBABAABBAABAB ABBABAABBAABBA ABBABAABBABAAB ABBABABAAABBBA ABBABABAABABAB ABBABABAABABBA ABBABABAABBAAB ABBABABABAAABB ABBABABABAABAB ABBABABBAAAABB ABBABBAAAABBAB ABBABBAAAABBBA ABBABBAAABAABB ABBABBAAABABAB ABBABBAABAAABB ABBBAAAABBABBA ABBBAAAABBBAAB ABBBAAAABBBABA ABBBAAABAABBBA ABBBAAABABABAB ABBBAAABABABBA ABBBAAABABBAAB ABBBAAABBAAABB ABBBAAABBAABAB ABBBAABAAABBAB ABBBAABAAABBBA ABBBAABAABAABB ABBBAABAABABAB ABBBAABABAAABB ABBBABAAAABABB ABBBABAAAABBAB ABBBABAAABAABB ABBBBAAAAAABBB ABBBBAAAAABABB

A netball team has seven players per side (as does waterpolo, and ultimate frisbee).

There are 6,435 distinct ways to arrange 16 players into two teams of eight, resulting in 263 optimal strategies (I’ll refrain from enumerating them all here).

There are eight players, per side, in a game of kickball (minimum).

There are 24,310 distinct ways to arrange 18 players into two teams of nine. There are 1,667 optimal picking strategies.

There are nine players, per side, in a game of baseball.

There are 92,378 distinct ways to arrange 20 players into two teams of ten. There are 2,724 optimal picking strategies.

There are ten players, per side, in a game of lacrosse (mens).

There are 352,716 distinct ways to arrange 22 players into two teams of eleven. There are 18,084 optimal picking strategies.

There are eleven players, per side, in a game of soccer (or hockey, or cricket).

There 12 players aside in women’s lacrosse, 15 players a side in Rugby, and 18 players a side in Australian football.

Here’s a table for the number of distinct team arrangements for two team games up to 20 players a side.

It is not a surprise that the delta for the strategy ABABAB … is always 0.50 for a linear distribution of skill. With 2n players, we are partioning the set so that all the odd fractions go on one team, and all the even fractions go on the other [1/2n, 3/2n, 5/2n … (2n-1)/2n] and [2/2n, 4/2n, 6/2n … 2n/2n].

The formula for the sum of the first n odd numbers is just n² and for the first n even numbers is n(n-1) so:

We’ve learned that, whatever the team size, simple alternating picking ABABAB is never the optimal strategy.

Based on this analysis, and the simplification that players are linearly distributed in skill (and that skill is a linear transitive parameter that can be simply added), the pattern ABBA is simple to remember. Simply repeat this selection pattern until there are no players left! (If the number of players required in a team is odd, after applying this pattern you end up with two players left. Arbitrarily allocate them to a team each, and this minimizes the advantage delta; you can’t do better).

An alternative way to think of this strategy is that the first captain picks one player, then the captains alternate in picking team members a pair at a time: A BB AA BB AA BB … A

A topic for a future posting would be to expand this analysis to different numbers of teams. Rather than just having two teams, AB, what is the strategy if you wanted to allocate players between three teams, ABC? Or how to make four ‘balanced’ teams ABCD for your next trivia night …