I haven’t read all of the recent discussion, but I just wanted to comment on this.
Thue-Morse is just a heuristic method and does not always properly solve the partition problem.
Example: partition the set { 6, 5, 4, 3, 3, 1 } into two groups of three with the same average (or sum).
- Thue-Morse selection yields the unbalanced sets { 6, 3, 1 } and { 5, 4, 3 }
- A greedy scheme (“smaller selects next”) also yields unbalanced partitioning
- The optimal and balanced partition is { 6, 4, 1 } and { 5, 3, 3 }
Adapted from relevant discussion here: Thue-Morse (Fair Sharing) Sequence: A possible alternative to komi? - #69 by yebellz
From the Wikipedia article:
Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called “the easiest hard problem”
Of course, a whole other question is how to characterize and compare the strengths of two teams made up of mixed ranks. It’s not necessarily the case that a simple average fully captures this. However, even with such a simplifying assumption, the computation problem is non-trivial.