Researchers devise an algorithm to combat gerrymandering

November 8, 2017 by Kevin Stacey
A new algorithm divvies up Congressional districts evenly while making the processes difficult to manipulate for partisan gain. Credit: Brown University

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.

An un-gerrymandered Florida. Credit: Brown University

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."

An un-gerrymandered Florida. Credit: Brown University

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 borders to make them less gerrymandered, Klein says.

In any case, Klein and his colleagues hope their 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

Related Stories

Can math solve the congressional districting problem?

August 4, 2015

Lost amidst the frenzy of coverage of the Supreme Court's rulings about the Affordable Care Act and same-sex marriage was a case involving the constitutionality of an independent commission to draw congressional districts ...

Recommended for you

Volvo to supply Uber with self-driving cars (Update)

November 20, 2017

Swedish carmaker Volvo Cars said Monday it has signed an agreement to supply "tens of thousands" of self-driving cars to Uber, as the ride-sharing company battles a number of different controversies.

13 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

ab3a
5 / 5 (2) Nov 08, 2017
This is very interesting. However, it is strictly based upon polygons with six or fewer sides. It is not aligned with roads, with voting centers, or anything practical. It seems to me that the next step is to make MINOR adjustments (less than a few hundred feet) to account for various polling places and transportation access. It would be in keeping with the spirit of the concept, but allowing for people to vote at places that may be closer to where they live.
dnatwork
not rated yet Nov 08, 2017
I've been thinking of something like this (without the math to do it) for years. But I would start from a population density map.

Place the first district in the center of the highest density, fill it with voters (divide total population by reps, as these folks did). Then move out from the borders of that area iteratively until you've filled the state with districts.

You could easily stop at lines like major roads or city/country borders, but you probably couldn't and shouldn't obey those strictly. Even distribution should win out. And the lines should be "straight" (no arbitrary hoops and loops, as pointed out in the article).
dnatwork
not rated yet Nov 08, 2017
Also it would need an algorithm to ensure the smallest possible circumference of every district.
KBK
3 / 5 (6) Nov 08, 2017
If they can implement this then they can vote with paper. paper that is kept for years, votes that are never lost, cameras on the entire process.

Oh yes, and FORCE voting. $1000 fine for not voting. No escape, no way out.

Paper voting, cameras on the counting, 100% strictly enforced voter turnout. And more initiatives..obviously.

And for the first time in probably 100+ years, the USA might have a president and congress/senate --- that was actually voted into office.
ab3a
5 / 5 (2) Nov 08, 2017
... and FORCE voting. $1000 fine for not voting. No escape, no way out.


Others have suggested just the opposite. See https://www.faceb...67893377

I am not a fan of forcing the ignorant or indifferent to vote. That often causes voting process artifacts, such as which candidate or side of an issue is listed first on a ballot, to affect the result.

We need more than just a clean-up of gerrymandered districts to improve the voting process.
edshort4
1 / 5 (2) Nov 08, 2017
Having Wyoming get as many federal Senators as does California is even worse than gerrymandering. Small states like Wyoming should get only 1 Senator.
Caliban
not rated yet Nov 08, 2017

Others have suggested just the opposite. See https://www.faceb...67893377

I am not a fan of forcing the ignorant or indifferent to vote. That often causes voting process artifacts, such as which candidate or side of an issue is listed first on a ballot, to affect the result.

We need more than just a clean-up of gerrymandered districts to improve the voting process.


Who cares what Mike Rowe's Hollywood Opinion is one this issue? Even if your personal preference is that only competent and informed citizens cast votes, the fact remains that there are multiple bars to full enfranchisement.

Gerrymandering is a big one, though, and lies at the heart of the issue. Access, time off, automatic registration, voter intimidation, and voter exclusion tactics round out the list, not even addressing State and National party rules and the Electoral College.

Elimination of gerrymandering would be a brave start to the process.
aksdad
2.3 / 5 (3) Nov 09, 2017
Not mentioned in this discussion are a couple critical issues.

First, the Founders designed Congress with two houses to balance representation of the interests of the states with the interests of the people by assigning 2 senators from each state in one house and representatives apportioned by population in the other. This was done on purpose because, being students of the effects of different types of previous government systems, they recognized that a purely democratic system often leads to the tyranny of the majority over the minority. They could foresee the country being ruled by large populations concentrated in a few big cities. City dwellers are often unsympathetic and ignorant of the issues important to rural citizens.

Second, it is unconstitutional to gerrymander districts based on race, but not by "politics", which is a nebulous term. Incidenatally, there are more than 2 parties in the United States.
petersonwalter
4.5 / 5 (2) Nov 09, 2017
It might be easier simply to elect all Representatives in a state at-large with a voting method that distributes the winners in a manner more representative of the voters, such as ranked choice voting, cumulative voting or approval voting.
Da Schneib
5 / 5 (1) Nov 10, 2017
Part of the point of the bicameral system is to prevent the tyranny of the majority. Currently it's being tilted to ensure the tyranny of the minority; this too shall pass.

The Senate ensures that none of the states face a disadvantage due to low population; the House ensures that every small district has representation by a local power. The problem is that this system devised by the founders has been hacked. Gerrymandering is hacking. The mere existence of the system proposed in this article should give the courts the evidence to stop this pernicious practice and restore the system the founders envisioned.
lengould100
5 / 5 (4) Nov 11, 2017
aksdad: We always hear of " the tyranny of the majority" but never of the tyrany of the minority, which accurately describes the US now.
dlethe
4.5 / 5 (2) Nov 11, 2017
Tyranny of the minority is worse. Imagine carving out a district so people of a certain race have a better chance of electing somebody of that same race.

That is pure racism on all levels. The practice is built on the premise that people of that minority are racists who will vote against somebody strictly because of race.
eachus
4 / 5 (3) Nov 12, 2017
A much more practical system would start with either voting places or state legislature districts and use a greedy algorithm (the next assignment is the one which chooses the addition which incresases the RMS from the district centers the least). The starting points for the districts could be the current districts.

The problem with that is that states where the number of representatives increases or decreases, need a workable rule for selecting the starting points. Incidentally this is the same problem as the method described here has. Picking starting points can result in gerrymandering.

Perhaps the best we can hope for is a measure of the compactness of the districts, such that each plan has a single compactness population balance measure. Then the courts could decide, for example that a plan that is 3% worse than the best on offer is acceptable, but 20% is not. (This is after deciding that the basis should be state legislature districts, polling places, or whatever.)

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.