News, Science & Research

Algorithms can help in redistricting, scientists say

Mathematic diagrams can divide states into equally populated districts, say U. researcher in paper

Contributing Writer
Thursday, October 26, 2017

Gerrymandering — the redrawing of voting districts for political gain — has been a problem in the United States for over two centuries. However, with the Supreme Court’s hearing on Gill v. Whitford concerning a controversial redistricting plan in Wisconsin, the issue has once again emerged as a pertinent topic for national debate. One University professor believes that solutions to the problem can be found using computer algorithms.

“I’ve been thinking for years, really, about the problem of redistricting,” said Philip Klein, professor of computer science. Klein recently co-authored a paper describing a method for dividing states into equally-populated districts using so-called “balanced centroidal power diagrams.”

Klein co-authored the paper along with Neal Young, professor of computer science at the University of California at Riverside, and Vincent Cohen-Addad, a post-doc  in computer science at the University of Copenhagen.

Klein and Cohen-Addad worked together on many of the principles that they later implemented in the paper. Cohen-Addad said he and Klein saw the potential for adapting their work for the purpose of dividing states into equal partitions, which led them to devise their redistricting algorithm.

The algorithm Klein and his team offered first finds a center point for each proposed district, then tries to minimize the distance of people in the state to each of these centers, all while maintaining balance between the populations assigned to each center point, Klein said. By completing this process, the algorithm can give relatively simple district shapes, each containing a similar number of people.

“One of the advantages of this method is it provides very little scope for politicians to engineer it,” Klein said.

Klein’s vision for the future of political redistricting involves using data and computer models to draw boundaries. He admits, however, that there are various requirements — among them those set forth by the Voting Rights Act — which are difficult to account for in an algorithm.

This is an important qualification, according to Moon Duchin, mathematician at Tufts University and orchestrator of the Tufts’ Metric Geometry and Gerrymandering Group. She points out that in addition to the racial and ethnic complexities of the Voting Rights Act, the computational approach in question does not account for laws aimed at preserving county, city and town borders or what locales referred to in the law as “communities of interest.”

Such legal requirements make the process of drawing district boundaries much more complicated, said Justin Solomon, assistant professor at MIT and a member of the Metric Geometry and Gerrymandering Group. Solomon points to the example of communities of interest: “This is one of these phrases that, unfortunately, is difficult for mathematicians to work with.” According to Solomon, a “community of interest” could be anything from a minority group to people who own waterfront property in Florida, making it hard to represent mathematically.

“Redistricting is a famous example of what we call an NP-hard problem in the computational world,” Solomon said, noting that it’s unreasonable to expect software to produce a single, ideal districting plan given the current list of criteria. But he doesn’t discount the idea of using computer models as part of the procedure. “Coming up with a fair redistricting process probably is a sort of a partnership between humans, machines and mathematical modeling.”

While math can generate many possibilities for districting plans,  Duchin stressed that the shaping of political districts will always be a human process. The idea that drawing boundaries could ever be left entirely up to computers is dubious, Duchin said. But there could be value in enumerating possible districting schemes, using models like Klein’s, so that legal qualifications could be examined, she added.