Weighted wins 2

I've been interested in using weighted wins as a statistic for a while. The idea is that by considering the strength of an opponent, an algorithm could handicap the results: a win against a good opponent counts for more than a win against a middling opponent. Of course, the algorithm has to base the calculation of how good an opponent is on how well it did against its opponents, so the algorithm must be based on the whole set of results. Therefore, I looked at a debate tournament and an N.F.L. season. The process can continue infinitely, although usually, after a couple times, things settle down and the handicapping doesn't change much upon further iterations. This is a kind of Markov chain technique.

One assumption that this depends on is that a team has an invariant strength. Clearly, this is suspect for debate (differing strengths on the affirmative and negative sides) and the other N.F.L. (the defense and offense are, literally, two different teams). Is it possible to use the same idea but adapt it to recognize the split-strengths?

I input total offensive yards from each 2011 N.F.L. game. A lot of yards against a weak defense is good; a lot of yards against a strong offense is better. By using only this information -- offensive yards for each team vs. each opponent -- a few matrix operations yielded a weighted offensive yards statistic and a defensive strength score for each team's offense and defense, respectively:

For example, against the "average" defense, the Saints would have earned 460 yards. The Steelers defense would have cut that to 82%, to 377 yards. Or so say these statistics. They never actually played.

How well did these statistics work? Well, as predictions, terribly. But, compared to reputable sports statisticians, fairly well. This is a comparison of my rank versus football outsiders rank (before the playoffs began) [offense on left, defense on right]:

On offensive, the difference was on average 3 ranks. On defense, the difference was on average 5.3 ranks. So, the rankings I generated from nothing other than actual yards in regular season games compared moderately closely to the ranks based on a complex calculation they call the DVOA (Defense-adjusted Value Over Average).

The same idea would work for debate tournaments: affirmative strength and negative strength could be treated as two separate variables for each team.

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