Why debate tournaments have been doing side assignment wrong

Side assignment is easy, right? In odd rounds, assign teams to sides at random. In even rounds, assign each team to the opposite side as the previous round. What could be easier?

The problem is that this makes even rounds harder to pair. Any tournament director can tell you that even rounds often "lock up" and that one has to break brackets to make matches. I know I've sat at a screen, wishing the two 5-0s that are both due Aff could hit, instead of each getting a pull-up.

I stumbled on an alternative, what I call the constrained side equalization (C.S.E.) method. Instead of balancing Aff-Neg rounds at the end of even rounds, this method works its magic at the end of odd rounds. Here's the C.S.E. in action:

Rd 1 - paired at random
Rd 2 - paired at random, ignoring sides. If both teams were Aff in round 1, or both Neg in round 1, it's a computer flip-for-sides. If one team was Aff and the other was Neg, then the sides are equalized.

At the end of round 2, about 25% of teams will have two Affs, 25% two Negs, and 50% will be balanced. (It depends on the random pairings.)

Rd 3 - Teams with two Affs must go Neg; teams with Negs must go Aff. The balanced teams are not assigned to either side. If a balanced team is matched against a two-Aff team, then the two-Aff team goes Neg. Likewise, if a balanced team is matched against a two-Neg team, then the two-Neg team goes Aff. If a two-Aff team is matched against a two-Neg team, then the sides are equalized. And if a balanced team is matched against a balanced team, then it's a computer flip-for-sides.

At the end of round 3, every team will either have had two Affs and one Neg, or two Negs and one Aff. In other words, at the end of an odd round, the sides are "equalized."

The cycle repeats. Round 4 is paired at random, ignoring sides. Round 5 has the constraint that teams with three Affs must go Neg and teams with three Negs must go Aff; otherwise, any team can be paired against any other. If the tournament ends on an odd round, there's no special other consideration. If the tournament ends on an even round, you'd want to pair teams in the typical way for the final prelim.

Mathematically, it is as simple as this rule:

If the Aff rounds - Neg rounds is 2 or -2, then the team is assigned a side first, then paired with an opponent; otherwise, a team is assigned an opponent first, then assigned a side (to equalize if necessary).

This works in odd or even rounds.

But why go to all this bother? The reason is simple: constraints.

	Odd	Even	Avg.
Trad.	100%	50%	75%
Alt.	87.5%	100%	94%

In a traditional method, in odd rounds, 100% of possible matches-- 0.5 * (n (n - 1)) --could be considered. There are no side constraints in odd rounds, so anyone could be matched against anyone. But in an even round, a tournament is limited to a fourth of (n (n - 1)). A due-Aff team can only be matched against a due-Neg team. This is a huge constraint.

Using the C.S.E. method, in odd rounds, teams with more Affs must go Neg and vice versa. Aside from this small constraint (only about one-eighth of possible matches ruled out), nearly anyone can debate anyone. And in even rounds, it's 100% of possible matches that can be considered. The C.S.E. method has much lower overall constraints than the traditional method.

In other words, the odd C.S.E. round is considerably easier to pair than the even traditional round (21 times better odds of finding a good pairing, in fact). If a side assignment for C.S.E. happens to not turn up a suitable pairing, why, you can reshuffle the teams--switching some randomly selected teams' side, excepting the couple side-constrained teams--and try again. This works whether it's an odd or an even round. In the traditional method, you can only reshuffle with an odd round. You're stuck with the even round side assignments you get with the traditional method. This inability to reshuffle the teams means the tournament can lock up. In the C.S.E. method, because any round can be reshuffled, there's always another chance to find a good pairing.

I worked out an example here. At the end of five rounds of C.S.E., every team had either two or three Affs. The method yielded side "equivalence."

But, intriguingly, the teams took different paths to get there. Some went Aff two times in a row. Some alternated. Although all the paths end with one of two correct results--two or three Affs--there were more path types to get there and thus more options to pair the teams. More paths = more flexibility. We've been doing side assignment the hard way!

Side assignment algorithm found!

One of the most vexing problems in running a small tournament is assigning sides in odd rounds. If you assign the sides incorrectly in an odd round, there may be nothing but bad options left for the subsequent even round: break side constraints (a team is aff. rounds 3 and 4), break school constraints (force two teams from the same school to debate), or re-match two teams (two teams that have already met have to debate again).

For a round robin, there are very few possible solution in the third to last round. Say you have 8 teams, so before round 5 is paired, team A has three opponents remaining: B, C, and D. If A is assigned to the aff, then 2/3 of {B, C, and D} must be assigned to the neg side -- otherwise, it will be impossible to honor side constraints for rounds 5 and 6. This sounds easy until you realize that B, C, and D all have three opponents each remaining, 2/3 of whom must be assigned to the opposite side... There ends up being just a few ways to pair round 5 that are consistent with all side constraints and re-match constraints for round 6 too.

The complexity of this problem has lead tab programs to include a "schedule round robin" option that executes before any rounds have happened at all. Although round robins are the epitome of this problem, many small tournaments with heavy school constraints (many teams from the same school) also experience it, leading to late round pairings that violate many constraints -- and there's no option yet programmed that solves that. Even big tournaments suffer from a similar problem. Although there's no risk of a big tournament violating any constraints, there is always the question of how well mixed a tournament is. If the same group of teams always is aff in odd rounds {A, B, C, D, E...}, then there's no chance that A can debate B, B debate C, etc. The tournament is better mixed if round 1 affs are {A, B, C, D, E...} and round 3 affs are {A, C, E...} and so on. The current assumption is that randomness is sufficient to mix a tournament well, which might be true, but it's nice to have an algorithm in hand that guarantees that.

Now, you may be tempted to think that a computer program can solve this sequentially: pair round 3, then have it look ahead to round 4 and see if there are any problems. This may just work at a tiny tournament, but the number of possibilities becomes daunting quickly, before becoming downright impossible, even for a supercomputer (and I don't believe many tab rooms would want to book time on the Roadrunner supercomputer). If you set a pairing for round 3, then look at all the possible round 4 options that follow, there are (n/2)! options, where n = number of teams. For 40 teams, there are 2.43 E 18 options. The world's fastest computer, by my rough estimation, would take 37 minutes to verify that all the options for round 4 were bad. To put it in perspective, 2.43 E 18 is about how many stars we can see in the sky. There is a better way, and it's to do a clever simultaneous approach.

Here's the gist of what I found. The mixing issue and the constraints issue are actually two sides of the same coin. If in round 1 team A aff. defeats team B neg., and in round 2 team B aff. defeats C neg., then the computer should be able to reject several possible side assignments out of hand. The best mixed, least conflicted option is actually to put {A, B, C} on the aff. for round 3. A and B can't debate again, so they might as well be on the same side; ditto for B and C. The only possible round that's lost is A vs. C, but any other way to assign the sides rules out more possible rounds. A smart use of this fact enables the algorithm to quickly toss out many possible options and reduce it to a manageable number.

Does the algorithm actually work? Yes. I tested it on a regular laptop, and it will pair a round robin on the fly. Without giving the program any prior knowledge that a tournament will be a round robin, it just picks the best round each time in a few seconds -- and pairs the round robin correctly and completely. The algorithm itself is not complex, but I'll save it for this document:

Side Assignment Algorithm