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!

 

Advertisements

One response to “constructing a NCAA basketball tournament bracket is NP-hard

  • prubin73

    I think the NCAA is making the bracketing problem NP-harder than it need be.

    First, the business about assigning teams to their “natural regions” might be a bit more compelling if the venues in the rounds prior to the Sweet 16 aligned with those regions. This year Buffalo and Orlando counted as both East and West (?!), Tulsa as both Midwest and East (?!), Sacramento as both Midwest (?!) and South (?!) but apparently _not_ as West (I’m now frantically clicking on Google Maps) and Milwaukee as both Midwest and South (perhaps because it is south of Canada).

    Second, the thing about avoiding have two teams from the same conference meet prior to the regional final if they played each other three times (counting a conference tournament) makes intuitive sense when you’re only doling out bids to two or three teams from any one conference. This year, the ACC got nine bids, the Big East and Big Ten seven each (all richly deserved in the case of the Big Ten, of course), the Big 12 got six, the SEC got five (they play basketball in the SEC?) and the Pac 12 got four. I haven’t done the math, but I wouldn’t be surprised if nine bids for the ACC forced some peculiar seedings.

    As a side note, the ACC went 7-8 in the first two rounds (counting a play-in game that Wake Forest lost), and 0-3 against the Big Ten (which went 8-4 with two fewer entrants) (and might have gone 9-3 if Northwestern had had a bit more luck with the refs). Only UNC is still alive from the ACC; your Badgers, the Boilermakers and the (I’m going to force myself to type this) Wolverines are still in the running for the Big Ten. Nothing in this paragraph directly applies to the difficulty of bracketing, per se. It does suggest that the committee faces other problems besides bracketing (such as finding an adequate supply of coffee before issuing the bids).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: