Constructing a loser's bracket in a seeded double elimination tournament for maximum fairness for N teams

Question

I'm having trouble figuring out an algorithm for constructing a loser's bracket in a double elimination tournament. A naive approach would give something like this

But implementing it this way creates a problem: teams could potentially play repeat matches early in bracket. For example, if Team 9 loses their first match, then wins their subsequent loser's match, and Team 8 wins their first match and loses their next, Teams 8 and 9 will end up playing for a second time in bracket in loser's round 2 for 9th place. This could potentially result in a team getting a low placing while losing to the winner of the bracket twice. A loser's bracket that is more "fair" would have the lowest placing a team can get while losing to the first place team be as high as possible.

The first step of fixing this should be easy. If you reverse the order of which winner's matches map to loser's matches in loser's round to (in the example, switch L1 Loser with L4 Loser and L2 Loser with L3 Loser), then the lowest placement a team could get while losing to only the first place team goes from 9th to 5th, which is an improvement.

The real problem is that I can't figure out how to make this generalizable and work for larger tournaments, or even what approach I can take to get that answer. Any help would be appreciated.

Answer 1

I'll just do this for powers of 2.

If the tournament has size 2^n then you can represent the initial placement of each team as a n bits. Drop the last bit, line them up, pair them off. Repeat for winners.

Set k = n/2. When a winner loses they drop the last bit and flip the kth remaining bit. From then on you lose a bit with further wins in the loser bracket.

This works for the first n-k rounds and puts losers into brackets where they won't meet anyone they played in the winning bracket for at least half the tournament. (Because different bits get flipped after each round.) But when the top bit got flipped for losers, cut k in half and continue the strategy. Thereby trying to make sure that there is a long time between losing in the winning side and facing them again in the losing side.