Why your round robin keeps giving you the same opponents
Engineering ·If you run round robins, you have probably heard someone say “didn’t we just play these guys?” For a long time I assumed that was just what happens in a small event. Then I measured it, and it turned out the app was causing it, for a reason I should have caught earlier.
What I measured
The event was an 18-player mixed doubles round robin with 8 rounds on 4 courts, so 16 players on court each round and 2 sitting out.
Teammate uniqueness was perfect. Nobody partnered with the same person twice, which is the hard constraint in the algorithm, and it held every time.
Opponents were a different story. 16 pairs of players faced each other twice in a single night. For that configuration, a good schedule can put almost everyone against everyone else exactly once, so this was a real problem and not a rounding error. Players notice it, and it makes an 8-round night feel like a 4-round night.
What the algorithm was doing
The scheduler builds each round in two steps. The first step pairs teammates by picking male-female pairs and scoring them against a history matrix that penalizes repeat partners. That part worked well, which is why teammate uniqueness came out clean.
The second step decides who plays whom. It takes the 8 paired teams and assigns them to 4 courts, and this is where things went wrong, in two separate ways.
Bug 1: greedy assignment that mutated state as it went
The court assignment was sequential. It found the two teams with the least shared history and put them on court 1, then picked court 2 from the remaining teams, then court 3, then court 4.
Each individual pick was the best option available at that moment, and that turned out to be the problem. Court 1 took the best matchup and in doing so used up the flexibility that courts 2 through 4 needed. By the time you get to court 4 there are four teams left and no choices at all, so whatever repeats remain, you’re stuck with them.
Underneath that was a subtler issue. The opponent history matrix was being updated in place while candidates were still being evaluated. Court 3 wasn’t being scored against what happened in previous rounds. It was being scored against previous rounds plus the two courts that had just been tentatively assigned in the current round. The search was effectively reading its own scratch work as history.
Bug 2: 100 attempts, scored on the wrong metric
This one stung a bit. The scheduler already generated 100 complete candidate schedules and kept the best one. The problem was how it picked the winner. It minimized repeat teammates and nothing else. It also calculated repeat opponents for every candidate, and then never used that number.
So the machinery to fix this had been running the entire time. A hundred candidate schedules per event, some of which were certainly better on opponent diversity, and the selection step never looked at that. It was optimizing hard for a constraint that was already satisfied.
The actual problem
Once you stop assigning courts sequentially, the second step is a well-known problem. You have 2C teams and you need to split them into C matches. Every possible pairing of two teams is an edge, weighted by how many times those four players have already faced each other, and you want the set of C disjoint edges that covers every team at the minimum total weight. That’s minimum-weight perfect matching, and greedy is just a poor way to solve it.
The obvious fix is to check every possible matching and pick the best one. That works right up until it doesn’t:
| Courts | Teams | Perfect matchings |
|---|---|---|
| 2 | 4 | 3 |
| 3 | 6 | 15 |
| 4 | 8 | 105 |
| 5 | 10 | 945 |
| 6 | 12 | 10,395 |
| 7 | 14 | 135,135 |
| 8 | 16 | 2,027,025 |
| 9 | 18 | 34,459,425 |
| 10 | 20 | 654,729,075 |
The count is the double factorial (2C-1)!!, and it grows the way double factorials grow. Seven courts is 135,135 candidates, which takes a couple of milliseconds. Eight courts is two million. Ten courts is 654 million, per round, on someone’s phone, while 14 people stand around waiting to be told where to go.
What shipped
The fix uses a different approach on each side of that line.
For seven courts or fewer, which is up to 28 players and covers almost every real event, it enumerates every matching. Four courts is 105 candidates scored in under a millisecond, and the result is provably optimal. There’s no heuristic to tune and nothing clever to get wrong.
For eight courts or more, it uses a randomized multi-start approach. Shuffle the teams, run the greedy matcher, record the score, and repeat 200 times, keeping the best result. Greedy’s weakness is that it depends heavily on the order it sees the teams in, so 200 different orderings shake most of that out. If a candidate hits zero repeats it stops early, since nothing is going to beat zero.
The change that made both approaches trustworthy is that candidates never touch the real state anymore. Every attempt gets its own clone of the opponent matrix, mutates that freely, and is scored against the original. Only the winning assignment is committed.
Finally, the outer loop was fixed to use the number it had been computing all along. Scoring is now lexicographic, so it minimizes repeat teammates first and then, among schedules tied on that, minimizes repeat opponents.
The part organizers can actually use
Digging through this turned up something more useful than the fix itself. A lot of repeat opponents aren’t bugs at all. They’re arithmetic. Past a certain point, no algorithm can help, because the schedule you asked for doesn’t exist.
For mixed doubles, the rules of thumb are roughly:
- If rounds are less than or equal to players per gender, everyone can meet at most once.
- If rounds are less than or equal to players per gender times two, everyone meets at most twice, which is fine and nobody complains.
- If rounds exceed players per gender times two, some pairs will meet three or more times no matter what.
The sweet spot is 16 players and 8 rounds, where every pair meets exactly once.
So if you’re running 8 rounds with 12 people, the repeats you’re seeing were guaranteed before anyone opened the app. You don’t need better software. You need one fewer round or four more players. Dink+ now warns you when your configuration is in that corner, which turned out to be a more useful feature than making the solver a few percent smarter.
What I took from it
The matchmaking logic itself was never wrong. Both bugs were about sequencing. One was committing to court 1 before knowing what it would cost courts 2 through 4, and the other was letting an evaluation write to the state it was evaluating against. The domain logic was fine, and the order of operations was doing the damage.
The fix that mattered most wasn’t the exhaustive search or the multi-start. It was three lines in the selection step, using a number the code had been carefully computing and then discarding for months. It’s worth asking of your own code what you’re already measuring and not looking at.