Picking fair teams - and the math to prove it

Question

Application: similar to picking playground teams.

I must divide a collection of n sequentially ranked elements into two teams of n/2. The teams must be as "even" as possible. Think of "even" in terms of playground teams, as described above. The rankings indicate relative "skill" or value levels. Element #1 is worth 1 "point", element #2 is worth 2, etc. No other constraints.

So if I had a collection [1,2,3,4], I would need two teams of two elements. The possibilities are

[1,2] & [3,4]

[1,3] & [2,4]

[1,4] & [2,3]

(Order is not important.)

Looks like the third option is the best in this case. But how can I best assess larger sets? Average/mean is one approach, but that would result in identical rankings for the following candidate pair which otherwise seem uneven:

[1,2,3,4,13,14,15,16] & [5,6,7,8,9,10,11,12]

I can use brute force to evaluate all candidate solutions for my problem domain.

Is there some mathematical/statistical approach I can use to verify the "evenness" of two teams?

Thanks!

Answer 1

The pattern from above. Team A: 1, 4, 5, 8, 9, 12, 13, 16 Team B: 2, 3, 6, 7, 10, 11, 14, 15 Snakes through the list using the pattern A-B-B-A; A-B-B-A; etc. This selection is pretty easy to code. Place all the ordered list of players into pairs. Reverse every odd # pair (assumes 1st pair is 0th group). However, there is a "better" way to make teams using the Thue-Morse algorithm. For a more in-depth description of of this algorithm see: https://www.youtube.com/watch?v=prh72BLNjIk

Answer 2

Firs one selects 1. From then on they take turns choosing 2.

Assuming:

• An even number of elements to choose
• Every chooser gives the same value to each element
• The value of the elements is very similar but different
• Lower is better

[BEST] Firs one selects 1. From then on they take turns choosing 2:

16 items                             average
Team 1: 1, 4, 5, 8, 9, 12, 13, 16      8.5
Team 2: 2, 3, 6, 7, 10, 11, 14, 15     8.5

14 items                             average
Team 1: 1, 4, 5, 8, 9, 12, 13          7.42857
Team 2: 2, 3, 6, 7, 10, 11, 14         7.57143

Choosing first 1, second 2 and then 1 each:

16 items                             average
Team 1: 1, 4, 6, 7, 10, 11, 14, 15     8.875
Team 2: 2, 3, 5, 8, 9, 12, 13, 16      8.125

14 items                             average
Team 1: 1, 4, 5, 8, 9, 12, 13          7.42857
Team 2: 2, 3, 6, 7, 10, 11, 14         7.57143

[WORST] Comparing with selecting 1 each:

16 items                             average
Team 1: 1, 3, 5, 7, 9, 11, 13, 15      8
Team 2: 2, 4, 6, 8, 10, 12, 14, 16     9

16 items                             average
Team 1: 1, 3, 5, 7, 9, 11, 13          7
Team 2: 2, 4, 6, 8, 10, 12, 14         8

Answer 3

Aren't the teams equal if each "round" of picking is simply done in reverse order of the preceding round? If there are 10 players whose talent is 1-10 and we are creating 5 teams (2 players each), the first round through, the first pick would obviously pick the best player (talent level 10). Then next pick would be 9, and so on. The 5th pick would get the play with the talent level of 6. In the second round, the pick order is reversed, so the team that just got talent level 6 would pick talent level 5 (the highest left) and so on until the captain who picked first in the 1st round would get the last player (talent level 1). Thus each team has a talent level of 11, with one team having 10 and 1, the next having 9 and 2, and so on. This would work for as many players/teams as there are.

Answer 4

You need an iterative ranking approach, with automated picking to produce evenly ranked teams on each iteration. This works even when the mix of participants changes to some extent over time. I created a tool to do just this for my 5-a-side group and then opened it up to allcomers if you google for "Fair Team Picker"

Answer 5

I don't think there's enough information to determine an answer.

What does it really mean for someone to be #1 vs #2? Are they 50% better, or 10% better or 1% better? How much better is #1 vs #5? It's really the algorithm to assign a value that needs to be accurate, and the distribution algorithm needs to reflect this properly.

For example, like I said, if you have Kobe Bryant mixed in with a bunch of high school basketball kids, what would the relative values be? Because in basketball, Kobe Bryant could single-handedly beat all the high school kids. So would his rank be #1, and the rest of the kids be #1000+?

As well, you have to assume that the value determination takes into account the size of a team. Does the team only need 2 players? Or does it need 10? In latter case, then in your second example, the 2nd team seems okay because the top 4 players would be playing with 6 much worse players, which could affect the success.

If all you are doing is distributing values, and if the notion of "fairness" is built into the value system, then the mean values seem to be a fair way to distribute the players.

Answer 6

The numbers represent rankings? Then no, there is no algorithm to get fair teams, because there's not enough information. It could be that even the match-up

[1] & [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

is stacked against the large-team. This would be the case, for example, for chess-teams, if the difference between [1] and [2] was large.

Even the matchup you mentioned as being "unfair":

[1,2,3,4,13,14,15,16] & [5,6,7,8,9,10,11,12] 

Could be completely fair in a game like baseball. After all, players 13-16 still need to bat!

---

So, probably the most fair thing to do would be to just pick teams randomly. That would also avoid any form of "gaming" the system (like my friends and I did in gym class in high school :) )

Answer 7

Your second, longer example, does not seem uneven (or unfair) to me. In fact, it accords with what you seem to think is the preferred answer for the first example.

Therein lies the non-programming-related nub of your problem. What you have are ordinal numbers and what you want are cardinal numbers. To turn the former into the latter you have to define your own mapping, there is no universal, off-the-shelf approach.

You might, for example, compare each element of the 2 sets in turn, eg a1 vs b1, a2 vs b2, ... and regard the sets as even enough if the number of cases where a is better than b is about the same as the number of cases where b is better than a.

But for your application, I don't think you will do better than use the playground algorithm, each team leader chooses the best unchosen player and turns to choose alternate. Why do you need anything more complicated ?