Researchers devise an algorithm to combat gerrymandering

As the Supreme Court considers Gill v. Whitford, a challenge to the practice of partisan gerrymandering that may rewrite the rules used to draw congressional districts, a team of computer scientists has come up with a new algorithmic approach to redistricting that's less political and more mathematical.

In a paper posted on arXiv.org, the researchers describe a computerized method for dividing state populations evenly into compact polygonal districts that average six or fewer sides. The neatly arrayed districts are a stark contrast to gerrymandered districts, which are stretched and contorted to provide an overall congressional advantage for one political party or another.

"What we're trying to do is come up with a system that makes it hard to engineer districts for political gain," said Philip Klein, a computer scientist at Brown University and a coauthor of the paper. "It doesn't give the user much freedom in deciding how the lines are drawn, which we view as a good thing because that freedom can be abused."

This certainly isn't the first time researchers have applied computational methods to the problem of redistricting. "I think what our approach offers is a clean, simple mathematical definition of what makes a solution acceptable," Klein said.

The approach that Klein and his colleagues brought to bear in redistricting comes from their research in clustering problems—specifically "k-means" clustering. K-means is generally called on to determine how limited resources can be distributed in an efficient fashion. It can be used, for example, to determine where fire stations should be located to best serve a collection of neighborhoods or where stores can be located to optimize convenience for customers.

K-means clustering makes use of a heuristic—a computational shortcut—known as Lloyd's algorithm. It starts by randomly placing a number of "centers" on a map (the centers might represent something like a fire station in a resource optimization problem) and then executing two simple steps repeatedly.

"For the first step, you assign clients to the center nearest to them," Klein explained. "For the second step, you move the centers to get them closer to the clients that you just assigned. The two steps are repeated until there's no improvement made by either step. When that happens, the algorithm terminates and you have a stable solution."

Once the algorithm produces a stable collection of clients and centers, it's possible to draw lines around those clusters, cordoning them off into discrete geometric regions, which is known as a Voronoi diagram.

Voronoi diagrams have "some lovely properties" that would make them a good approach to making congressional maps, Klein says. They're convex, meaning shapes that don't have any strange dents or divots. They're also compact in that they don't sprawl strangely across the map.

Voronoi diagrams have been suggested previously as a way to draw congressional districts, but there's a problem. "They're not balanced," Klein said. "There's no guarantee that each cell has the same number of clients in it."

So for this new paper, Klein and his colleagues tweaked the first step of Lloyd's algorithm, the step that assigns clients to centers, to ensure an even distribution. They simply take the total number of voters in the state, divide by the number of congressional seats the state has, and stipulate that no center be assigned more or less than that number of voters. The diagrams that result from that process, known as balanced centroidal power diagrams, have all the desirable properties of Voronoi diagrams, but with population balance to boot.

The researchers used the algorithm to produce mock congressional maps of several U.S. states using 2010 census data. The resulting districts differed in population by no more than one voter and remained remarkably compact.

Klein acknowledges that there are significant barriers to using this or other algorithmic approach to redistricting. Many states, for example, have rules stipulating that districts conform to existing political boundaries like county or city borders. Some states require that districts protect communities with common interests from being split apart. The system Klein and his colleagues have come up with is blind to these considerations.

But if the Supreme Court deems partisan gerrymandering unconstitutional, those current rules may be kicked to the curb, and computational approaches may provide a way to fill the void, Klein says. And even if algorithms don't end up drawing the districts themselves, they could provide a standard against which districts are judged to see if gerrymandering has taken place. Another possibility is that algorithms like this one could be used to tweak existing district borders to make them less gerrymandered, Klein says.

In any case, Klein and his colleagues hope their approach will at least spark some renewed conversation about algorithmic approaches to redistricting. They've made their paper and their computer code freely available to the public.

Explore further: Congressional redistricting less contentious when resolved using computer algorithm

More information: Balanced power diagrams for redistricting. arXiv:1710.03358 [cs.DS] arxiv.org/abs/1710.03358