Thursday, June 18, 2009

Inconsistent Bracketology and Non-Transitivity

Does anyone who routinely does NCAA playoff brackets know the answer to this one? Can you fill in a bracket inconsistently, so that you have (let's say) team A beating team B and team C beating team D in the first round, and yet you have either team B or team D coming out of the second round?

Because it's not hard for the probabilities to come out that way. One simple way is for A and C to be mild favorites over B and D, respectively, but for B and D to be prohibitive favorites over C and A respectively. (Matchups between A and C, or between B and D, can be pick-ems.) So you fill out your bracket to have A and C come out of the first round, but either B or D to come out of the second round. This requires a certain amount of non-transitivity in the teams: For instance, A edges B, which trounces C, which edges D, which trounces A again. But that's hardly unknown in the basketball world, and is usually trotted out as the inevitable "matchup issue" between two teams.

Somewhat more surprising is that it's possible for the same inconsistency to happen without any non-transitivity. Suppose A is a huge favorite over B in the first round, while C is a mild favorite over D in the second round. So you have A and C come out of the first round. But suppose C is also a mild favorite over A, but D is a huge favorite over A. There's no non-transitivity—you can place the teams in the total ordering C > D > A > B—but D is nevertheless the favorite to come out of the second round, despite not being the favorite to come out of the first.

Even though there's no non-transitivity in the second example, it's vaguely unsatisfying because it doesn't match our intuition. We'd like to think that since C beats D, C should be a bigger favorite over A than D is. But the inconsistent bracket result only comes about here because that intuition is violated. So, the semi-open question ("semi-open" because I suspect it won't be that difficult to resolve): Is it possible for a set of tournament contestants to fall under a total ordering in the intuitive way suggested above, and still yield an inconsistent playoff bracket in a binary, single-elimination tournament? It need not be limited to a four-team bracket, but it does have to be 2n for some n.


  1. No, you are not typically allowed to make brackets that cannot happen in reality, although that is an interesting strategy to use.

  2. @FCF: Ahh, that's too bad. Although, of course, I wouldn't expect such a situation to come up very often...