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

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 ?