Redrawing Maryland’s 2012 congressional map from 1,849 precincts with a rounding algorithm

Researchers took the 1,849 precincts of Maryland, ran them through a randomized algorithm on an ordinary computer, and drew eight congressional districts. The fictitious District 7 looks very different from the sixth district that raised the gerrymandering issue in 2019. The paper, posted to arXiv, redraws the state's 2012 map as a case study for a new method of solving the political districting problem.

The problem

Gerrymandering is drawing electoral maps to manipulate the voter population for advantage. The authors write that it has troubled American democracy for nearly its entire history. The word comes from Governor Elbridge Gerry's March 1812 Massachusetts map, which the Boston Gazette called "a new species of monster," nicknamed for its salamander-like shape. The paper says the practice is older, traceable to 18th century England, and that it grew after the Civil War, when Southern politicians used it to weaken African American votes. In the 1960s the Supreme Court, led by Chief Justice Earl Warren, ruled that districts must be roughly equal in population and redrawn every 10 years based on the census.

Maryland's 2012 map

Maryland's 2012 lines were drawn in 2011, following a plan proposed by the Democrats, and were controversial. Republican critics scrutinized the sixth district in particular, calling it a case of cracking Republican support, which gave Democrats one more seat in Congress. Governor Lawrence J. Hogan Jr. filed an amicus brief supporting the plaintiffs. In 2019 the Supreme Court threw out the case, saying federal courts have no place settling partisan gerrymandering claims and that state legislators should draw the maps.

How the method works

The political districting problem splits indivisible population units, such as counties or precincts, into a set number of districts. Each district must be contiguous and geographically compact, and its population must fall within a set range of the mean (typically 5% either way).

The authors model Maryland as a graph: each unit is a node weighted by its population, joined by an edge to each neighbor. Following earlier work by Mehrotra, Johnson and Nemhauser, they score each district's non-compactness with a "gerrymander score," based on how many units one must pass through to reach a central unit. Lower is more compact.

Earlier, Chopra, Park and Shim had redrawn the map using only 46 coarse population units. Real districting uses 1,849 precincts, and an efficient integer linear program from other researchers could not even solve its root simplex on supercomputers in 50 hours. The authors instead use adaptive randomized rounding:

• Rounding: turn a fractional solution into the nearest whole-district plan.
• Randomizing: nudge a starting "seed" randomly and try again many times, keeping the best plan.
• Moving the seed: shift it toward the best plan found, slowing as it gets close, and reset it if it keeps finding the same plan.
• Two phases: first find any plan that meets the population limits, then improve it by lowering the gerrymander score.

Figure 6 of the paper: the procedure as a flowchart. Authors' figure, CC BY 4.0, shown here as published.

The redrawn map

On an ordinary digital computer, the procedure found a plan meeting all population limits, then improved it to a gerrymander score of 10,152, on average about 5.5 from a central precinct. The paper numbers its districts 0 to 7. The new District 7 has a shape very different from the sixth district that raised the issue in 2019. The authors note that the original shape matched the optimal plan from Chopra and colleagues' coarse model.

Figure 7 of the paper: the redrawn map. Authors' figure, CC BY 4.0, shown here as published.

Sources

• Noah Lee, Hyunwoo Park and Sangho Shim, "Redrawing the 2012 map of the Maryland congressional districts," arXiv:2312.03901, https://arxiv.org/abs/2312.03901, CC BY 4.0. Changed here: condensed and reworded; Figures 6 and 7 kept; the rounding-example figures, appendix table and mathematical detail left out; rewritten in hubnx's own words.