How it Works

prev

Part 1/3: Imagine a Puzzle

next

The simplest optimization algorithm is brute force: create a very large number of legal maps and then just pick the best one! That might not sound like a novel idea, but we can leverage the structure of the redistricting problem to create a HUGE number of maps in not all that much time.

To give you the intuition, imagine a puzzle. Each piece of this puzzle is shaped so that it fits precisely together with the other pieces to create a clean rectangle.

A four piece puzzle

Consider what happens when we cut each piece into smaller sub-pieces:

Enumeration of piece division

Any division of a given piece is compatible with any division of the other pieces, because each division adds up to a correctly shaped puzzle piece, and the puzzle pieces add up to a correctly shaped puzzle!

A four piece puzzle partitioned into sub-pieces

In creating only 16 puzzle piece divisions, we create 256 possible ways to assemble the puzzle (44). If we sliced up each of the sub-puzzle pieces into sub-sub-pieces, the exponentiation compounds and we get 444 (over 4 billion) distinct ways to construct the puzzle.

prev

next

prev

Part 2/3: Creating Districts

next

Now imagine instead of splitting pieces of a puzzle, we split pieces of a state.

A sample tree of district divisions

We create a tree of random partitions that achieves exponentiation just like the puzzle! The leaves of the tree are legal districts that we can compose into a HUGE number of distinct plans.

Sample tree enumeration

Depending on the size of the state, on a full size tree playing at 20 frames per second like above, it could take the age of the universe to watch the full enumeration.

The problem then becomes how do we actually go about splitting a state into smaller pieces to eventually make legal (i.e. contiguous and population balanced) districts?

We do this by randomly selecting region “seeds” which act like the center of a region. With each seed, we also sample the region size, the number of districts that the region ultimately contains. For example, the 3 in the figure below indicates that region should have population sufficient for 3 districts.

Region center selection

With these seeds and sizes, we split a region into contiguous and correctly sized regions using an optimization technique called integer programming.

Region partition

We keep doing this until the size is equal to 1, as a region with size equal to 1 is a legal district!

Generation animation

prev

next

prev

Part 3/3: Selecting a Map

next

Using past statewide election data from a number of years and offices, we can estimate the probability that an arbitrary congressional district will be occupied by a Democrat or a Republican.

Probability of Republican district

Therefore we can estimate what the likely outcome is for every district we generate, and consequently every plan we implicitly generate. Using these estimates we can calculate the expected efficiency gap, a popular fairness metric that calculated the difference in the number of wasted votes.

Because we implicitly generate a huge number of combinations, we can’t actually just score every map and pick the best one. To get around this we solve an additional optimization problem (more integer programming) to find a diverse set of fair maps. This makes it relatively fast (a few minutes or hours) to filter thousands of fair maps from the trillions (or quintillions or more) that we generate. With this set of fair maps, we can further filter on secondary criteria like competitiveness or compactness to pick the final map.

Good and bad district plans

To summarize, we generate a huge number of maps to maximize the probability that one of them is really good. We go through a first filtering step to go from trillions of random maps to thousands of fair maps. Then we do a second filtering step to go from thousands of fair maps to tens or hundreds of fair maps that are compact and competitive, while also satisfying the other criteria from a state’s redistricting laws.

prev

next


Want to know more?

For more technical information about our redistricting algorithm, check out this talk presented by Fairmandering’s founder, Wes Gurnee, which won him the INFORMS Undergraduate Research Prize!