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.
Consider what happens when we cut each piece into smaller sub-pieces:
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!
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.
Now imagine instead of splitting pieces of a puzzle, we split pieces of a state.
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.
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.
With these seeds and sizes, we split a region into contiguous and correctly sized regions using an optimization technique called integer programming.
We keep doing this until the size is equal to 1, as a region with size equal to 1 is a legal district!
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.
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.
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.
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!