constructing a NCAA basketball tournament bracket is NP-hard

I continue to receive a lot of questions about Wisconsin’s 8 seed (read the blog post here). The NCAA men’s basketball selection committee doesn’t just assign seeds to teams, it also puts the teams into the bracket, which involves assigning a team a seed, assigning other teams to the regions, and assigning locations to each game. This is an NP-hard problem that involves balancing several interdependent decisions.  You can formulate the problem as an integer programming model subject to many assignment and distance constraints. Cole Smith, Barbara Fraticelli and Chase Rainwater published a paper on optimization models to design good tournaments that balances these constraints while getting the seeds right. As far as I know, the committee constructs the bracket by hand.

Below are the official rules for the final part of constructing the tournament called “Building the Bracket.” The emphasis is mine–I boldfaced the major rules that constrain how the bracket is built. There are a lot of rules, so many that even identifying a feasible solution may be difficult. Near the end: “A team may be moved up or down one (or in extraordinary circumstances) two lines from its true seed line when it is placed in the bracket if necessary to meet the principles.” I suspect Wisconsin was given an 8 seed to conform to all the rules. It’s worth pointing out that Wisconsin’s low seed was ultimately unfair to top seed Villanova, who had an extremely second round opponent (sorry not sorry, ‘Nova). Optimization models and algorithms could have constructed a bracket that was more fair to the teams.

III. BUILDING THE BRACKET

Sixteen levels are established (i.e., the seeds, 1 through 16) in the bracket that cross the four regions, permitting evaluation of four teams simultaneously on the same level.  Teams on each seed line (No. 1, No. 2, No. 3, etc.) should be as equal as possible.

Each region is divided into quadrants with four levels in each, permitting the evaluation of four different sections within each region against the same sections in each of the other regions.

The committee will assign all four teams in each bracket group (seeds 1, 16, 8, 9), (4, 13, 5, 12), (2, 15, 7, 10), (3, 14, 6, 11) to the same first-/second-round site. There will be two ”pods‟ at each first-/second-round site which may feed into different regional sites.

Each of the first four teams selected from a conference shall be placed in different regions if they are seeded on the first four lines.

Teams from the same conference shall not meet prior to the regional final if they played each other three or more times during the regular season and conference tournament.

Teams from the same conference shall not meet prior to the regional semifinals if they played each other twice during the regular season and conference tournament.

Teams from the same conference may play each other as early as the second round if they played no more than once during the regular season and conference tournament.

Any principle can be relaxed if two or more teams from the same conference are among the last four at-large seeded teams participating in the First Four.

To recognize the demonstrated quality of such teams, the committee shall not place teams seeded on the first four lines at a potential “home-crowd disadvantage” in the first round.

The last four at-large teams on the overall seed list, as well as teams seeded 65 through 68, will be paired to compete in the First Four games on Tuesday and Wednesday following the announcement of the field. (If allowed, the last at-large team on the seed list  will be paired with the second-to-last at-large team on the seed list. The other First Four games will consist of the third-to-last at-large team on the seed list playing the fourth-to-last at-large team on the seed list, as well as seed 65 versus 66; and seed 67 versus 68).

The winners of the First Four games will advance to a first- and second-round site to be determined by the committee during selection weekend. In the event a First Four site is also a first- and second-round site, the winners of the First Four games may be assigned to that site, regardless of the days of competition.

Teams will remain in or as close to their areas of natural interest as possible. A team moved out of its natural area will be placed in the next closest region to the extent possible. If two teams from the same natural region are in contention for the same bracket position, the team ranked higher in the seed list shall remain in its natural region.

A team will not be permitted to play in any facility in which it has played more than three games during its season, not including exhibitions and conference postseason tournaments.

A host institution’s team shall not be permitted to play at the site where the institution is hosting. However, the team may play on the same days when the institution is hosting.

Teams may play at a site where the conference of which it is a member is serving as the host.

A team may be moved up or down one (or in extraordinary circumstances) two lines from its true seed line (e.g., from the 13 seed line to the 12 seed line; or from a 12 seed line to a 13 seed line) when it is placed in the bracket if necessary to meet the principles.

 

Procedures for Placing the Teams into the Bracket
(a procedure for ensuring that the regions are roughly balanced)

1. The committee will place the four No. 1 seeds in each of the four regions, thus determining the Final Four semifinals pairings (overall 1 vs. 4; 2 vs. 3).

2. The committee will then place the No. 2 seeds in each region in true seed list order. The committee may relax the principle of keeping teams as close to their area of natural interest for seeding teams on the No. 2 line to avoid, for example, the overall No. 5 seed being sent to the same region as the overall No. 1 seed. The committee will not compromise the principle of keeping teams from the same conference in separate regions.

3. The committee will then place the No. 3 seeds in each region in true seed list order.

4. The committee will then place the No. 4 seeds in each region in true seed list order.

5. After the top four seed lines have been assigned, the committee will review the relative strengths of the regions by adding the “true seed” numbers in each region to determine  if  any  severe  numerical imbalance exists. Generally, no more than five points should separate the lowest and highest total.

6. In “true seed” order, the committee then assigns  each  team  (and,  therefore,  all teams in its bracket group—e.g., seeds 1, 8, 9, 16) to first-/second-round sites.

7. The committee will then place seeds Nos. 5-16 in the bracket, per the principles. The four  teams  assigned  to  the  seed  line,  5 through 16, will have the same numerical
value.

Additional Considerations

1. If possible, rematches of non-conference regular-season games should be avoided in the First Four and first round.

2. If possible, after examining the previous two years’ brackets, teams or conferences will not be moved out of its natural region or geographic area an inordinate number of times.

3. If  possible, rematches from the previous two tournaments should be avoided in the first round.

You can read the official rules for selection and seeding for the men’s tournament is here. I did not find nearly so many rules or information about selecting and seeding the women’s tournament.

Go Badgers!