A Multi-Objective Algorithm for Redistricting

Abstract. Redistricting is the redrawing of the boundaries of legislative districts for electoral purposes in such a way that the generated districts fulfill federal and state requirements such as contiguity, population equality and compactness. In this paper we solve the problem by means of a single objective and a multiobjective simulated annealing algorithm. These algorithms were applied in two real examples in Mexico. The results show that the performance of the multiobjective approach is better, leading to higher quality zones.

The Mathematics and Statistics of Voting Power

Abstract. In an election, voting power—the probability that a single vote is decisive—is affected by the rule for aggregating votes into a single outcome. Voting power is important for studying political representation, fairness and strategy, and has been much discussed in political science. Although power indexes are often considered as mathematical definitions, they ultimately depend on statistical models of voting. Mathematical calculations of voting power usually have been performed under the model that votes are decided by coin flips. This simple model has interesting implications for weighted elections, two-stage elections (such as the U.S. Electoral College) and coalition structures. We discuss empirical failings of the coin-flip model of voting and consider, first, the implications for voting power and, second, ways in which votes could be modeled more realistically. Under the random voting model, the standard deviation of the average of n votes is proportional to 1/sqrt(n), but under more general models, this variance can have the form c*n^(-a) or sqrt(a − b*log(n)). Voting power calculations under more realistic models present research challenges in modeling and computation. Key words and phrases: Banzhaf index, decisive vote, elections, electoral college, Ising model, political science, random walk, trees.

In Defense of Automated Districting:
A Comparative Study of Redistricting Procedures and Gerrymandering Prevention Measures

This is an excellent book on automated districting by Jurij Toplak. I highly recommend it to anyone interested in the topic.

Unintentional Gerrymandering: Political Geography and Electoral Bias in Legislatures

This is a great paper by Jowei Chen and Jonathan Rodden that explains how party-blind redistricting systematically disenfranchises voters in urban areas.

"Unintentional Gerrymandering: Political Geography and Electoral Bias in Legislatures"


While conventional wisdom holds that partisan bias in U.S. legislative elections results from intentional partisan and racial gerrymandering, we demonstrate that substantial bias can also emerge from patterns of human geography. We show that in many states, Democrats are inefficiently concentrated in large cities and smaller industrial agglomerations such that they can expect to win fewer than 50% of the seats when they win 50% of the votes. To measure this "unintentional gerrymandering," we use automated districting simulations based on precinct-level 2000 presidential election results in several states. Our results illustrate a strong relationship between the geographic concentration of Democratic voters and electoral bias favoring Republicans.

Seats, Votes, and Gerrymandering: Estimating Representation and Bias in State Legislative Redistricting

These are two papers by Robert Browning, Gary King, and Bernard Grofman that explain how you can use a "seats / votes curve" to differentiate gerrymandering from normal variations in the popular vote and election outcomes. They also explain how you can use this as a judicial test. The seats / votes asymmetry mentioned in these papers is minimized by the "Seats / votes asymmetry" criteria in Auto-Redistrict.

"Seats, Votes, and Gerrymandering: Estimating Representation and Bias in State Legislative Redistricting"


The Davis v. Bandemer case focused much attention on the problem of using statistical evidence to demonstrate the existence of political gerrymandering. In this paper, we evaluate the uses and limitations of measures of the seat votes relationship in the Bandemer case. We outline a statistical method we have developed that can be used to estimate bias and the form of representation in legislative redistricting. We apply this method to Indiana state House and Senate elections for the period 1972 to 1984 and demonstrate a maximum bias of 6.2% toward the Republicans in the House and a 2.8% bias in the Senate.
"The Future of Partisan Symmetry as a Judicial Test for Partisan Gerrymandering after LULAC v. Perry"


While the Supreme Court in Bandemer v. Davis found partisan gerrymandering to be justiciable, no challenged redistricting plan in the subsequent 20 years has been held unconstitutional on partisan grounds. Then, in Vieth v. Jubilerer, five justices concluded that some standard might be adopted in a future case, if a manageable rule could be found. When gerrymandering next came before the Court, in LULAC v. Perry, we along with two of our colleagues filed an Amicus Brief (King et al., 2005), proposing the test be based in part on the partisan symmetry standard. Although the issue was not resolved, our proposal was discussed and positively evaluated in three of the opinions, including the plurality opinion, and for the first time for any proposal the Court gave a clear indication that a future legal test for partisan gerrymandering will likely include partisan symmetry. A majority of Justices now appear to endorse the view that the measurement of partisan symmetry may be used in partisan gerrymandering claims as “a helpful (though certainly not talismanic) tool” (Justice Stevens, joined by Justice Breyer), provided one recognizes that “asymmetry alone is not a reliable measure of unconstitutional partisanship” and possibly that the standard would be applied only after at least one election has been held under the redistricting plan at issue (Justice Kennedy, joined by Justices Souter and Ginsburg). We use this article to respond to the request of Justices Souter and Ginsburg that “further attention . . . be devoted to the administrability of such a criterion at all levels of redistricting and its review.” Building on our previous scholarly work, our Amicus Brief, the observations of these five Justices, and a supporting consensus in the academic literature, we offer here a social science perspective on the conceptualization and measurement of partisan gerrymandering and the development of relevant legal rules based on what is effectively the Supreme Court’s open invitation to lower courts to revisit these issues in the light of LULAC v. Perry.

How the Voting Rights Act Hurts Democrats and Minorities

I wasn't able to find academic papers, as I would like, but I did find two pretty thorough news pieces on how the GOP use the Voting Rights Act to justify racial and partisan gerrymandering. I strongly believe that this practice of packing "communities of interest" into one district and thus diluting their voting power -- all in the guise of protecting their voting power -- needs to be stopped once and for all.

Alabama's legislative districts are 'racially gerrymandered,' Supreme Court rules published in (unknown author)

In Alabama Legislative Black Caucus v. Alabama, the U.S. Supreme Court rejected numerical quotas as a means of satisfying the Voting Rights Act.

In a dissent of his own, Thomas ‒ the Supreme Court’s only black justice ‒ focused on the effective racism that resulted as a consequence of Section 5 and the Supreme Court’s role in creating Alabama’s current redistricting problems.

"The practice of creating highly packed ‒ 'safe' ‒ majority-minority districts is the product of our erroneous jurisprudence, which created a system that forces States to segregate voters into districts based on the color of their skin” he wrote. “Nor does this Court have clean hands.”

"I do not pretend that Alabama is blameless when it comes to its sordid history of racial politics. But, today the State is not the one that is culpable. Its redistricting effort was indeed tainted, but it was tainted by our voting rights jurisprudence and the uses to which the Voting Rights Act has been put,” Thomas added. “Long ago, the DOJ and special-interest groups like the [American Civil Liberties Union] hijacked the Act, and they have been using it ever since to achieve their vision of maximized black electoral strength, often at the expense of the voters they purport to help."
How the Voting Rights Act Hurts Democrats and Minorities by Steven Hill (published in The Atlantic)

But just in time for the redistricting in 1990, some enterprising Republicans began noticing a rather curious fact: The drawing of majority-minority districts not only elected more minorities, it also had the effect of bleeding minority voters out of all the surrounding districts. Given that minority voters were the most reliably Democratic voters, that made all of the neighboring districts more Republican. The black, Latino, and Asian representatives mostly were replacing white Democrats, and the increase in minority representation was coming at the expense of electing fewer Democrats. The Democrats had been tripped up by a classic Catch-22, as had minority voters: Even as legislatures were becoming more diverse, they were ironically becoming less friendly to the agenda of racial minorities.

Newt Gingrich embraced this strategy of drawing majority-minority districts for GOP advantage, as did the Bush Administration Justice Department prior to the 1991 redistricting, even as GOP activists like now-Chief Justice John Roberts campaigned against the VRA because they opposed any race-based remedies. The tipping point was the 1994 midterm elections, when the GOP captured the U.S. House of Representatives for the first time in 35 years and Gingrich because speaker. Many experts on both the left and the right, from The Nation's Ari Berman and prominent GOP election lawyer Ben Ginsberg (who spearheaded the 1991 effort to maximize the number of majority-minority districts), attribute the Republican success that year to the drawing of majority-minority districts; indeed, African-American membership in the House reached its highest level ever, at 40.

VRA districts undoubtedly played a role in the GOP takeover, but they were not the only factor, since Republicans made big gains that year in lots of places outside the South. But in the hardscrabble battles of the 50-50 nation, any advantage at all was embraced, and prominent Republicans like Ginsberg and Gingrich became the loudest proponents of drawing majority-minority districts. Many Republicans still promote this strategy today, and it's the only race-based remedy the GOP has supported in the modern era. The party has been more than willing to shelve its ideology when it suited their naked political interests.
How the GOP Is Resegregating the South by Ari Berman (published in The Nation)

Meanwhile, just as they’re seeking to declare Section 5 unconstitutional, Republicans are also invoking the VRA as a justification for isolating minority voters. "There’s no question that’s an unintended consequence," says Jankowski of the RSLC (which takes no position on Section 5). "Republicans benefit from the requirement of these majority-minority districts. It has hurt the Democratic Party’s ability to compete in the South.” But Kareem Crayton, a redistricting expert at the UNC School of Law, argues that Republicans “clearly decided to ignore what federal law requires," noting that "a party that doesn’t like federal mandates all of a sudden getting religion and talking about the importance of federal voting rights is more than a little ironic."

The VRA states that lawmakers must not diminish the ability of minority voters to participate in the political process or elect a candidate of their choice. "There’s nothing out there that says a state can’t draw a 42 percent black district instead of a 50 percent black district as long as black voters still have the opportunity to elect a candidate of choice,” argues Paul Smith, a prominent redistricting lawyer at Jenner & Block in Washington. The VRA, in other words, did not compel Republicans to pack minority voters into heavily Democratic districts. “Using the Voting Rights Act to justify racial discrimination is anathema to the purpose of the Voting Rights Act,” says Stacey Abrams.

But it’s also difficult for voting rights advocates to prove in federal court that packing minority voters into majority-minority districts diminishes their ability to elect candidates of choice. That’s why the Justice Department has pre-cleared redistricting plans in every Southern state so far except Texas, much to the chagrin of civil rights activists. (Plaintiffs may have better luck in state court in places like North Carolina, where the court has acknowledged that civil rights groups have raised “serious issues and arguments about, among other things, the extent to which racial classifications were used.”) “I have not been at all satisfied with the civil rights division of the Justice Department under the Obama administration,” says Joe Reed, a longtime civil rights activist and redistricting expert in Alabama.

A slideshow on Redistricting Algorithms

This is a good slideshow I found that goes over the basics of redistricting algorithms. It's put together by M.I.T. Director of Research Micah Altman.

My response to "The Promise and Perils of Computers in Redistricting"

There's a paper written by Micah Altman and Micheal McDonald, called "The Promise and Perils of Computers in Redistricting". I'm posting a link to it and excerpts here, not because I think it's a good resource -- though it is a good survey of software at that time -- but because I strongly disagree with its conclusions. I am listing in here my responses as a resource. My apologizes in advance to Micah and Micheal if I sound off-puting. That's not the intent. The intent is to inform.

Starting on page 84, authors assert:

Legal and academic scholars suggest many plausible criteria for evaluating the quality of districts, none of which are commonly implemented in fully-automated redistricting systems. For example, social scientists have suggested that the following criteria, among others, should be incorporated in redistricting: * Neutrality or symmetry of the projected seats-vote curve. * Range of responsiveness or the range of possible vote shares across which electoral results would change. * Competitiveness, maximizing the number of districts with competitive margins * Consumer surplus or minimize the number of votes for a losing candidate. * Clustering, per se. * Continuity of representative relationship, (implying some degree of incumbency protection). -- start with last map as base map. only mutate it a little. * Non-quantitatively defined communities of interest.

The authors state that "none of [these] are commonly implemented in fully-automated redistricting systems". However, none of these are commonly implemented in non-automated redistricting systems. Indeed, upon brief reflection, the reason for this is clear: these measures all require a lot of calculation from detailed data. This kind of thing isn't practical to do by hand. Normally one uses a computer to do this kind of thing. One writes a computer program and runs it on the data. In other words, one automates it.

These criteria, far from being reasons against automation, are reasons for automation. If there is not currently a program written to calculate these scores, well that is not an argument against writting one, it is an argument for writting one.

A non-automated system implements NONE of these scores, and thus an automated redistricting system need only implement any single one of them to be superior. Auto-Redistrict implements ALL of them.

In sum, authors' argument is upside-down and backwards.

Next quote:

Practically, automated redistricted systems are not driven by any recognized measure of district quality but by the inability to calculate measures of chosen district qualities. Calculating any measure of districts or a redistricting plan as a whole may require sifting through a large amount of data. These calculations can quickly become expensive, which limits the speed by which an algorithm can search for a solution.

This is categorically false. These calculations do not quickly become expensive. The worst of them grow no faster than O(N) (aka linear time), which is very good, and many of them are sub-linear or even constant (no growth at all). Indeed, if it wasn't manageable it would be even harder for a human to do it accurately, which would be all the more reason to use a computer to do it. So not only is the premise here categorically false, but the logic isn't valid, either.

Authors continue along this line:

The commonly recognized compactness measures that are used in automated systems are typically modified ad-hoc or new measures are created without rigorous peer-review concerning their strengths and weaknesses so as to increase computational speed.

I use isoperimietric quotient. It is very well peer-reviewed. And it is stable and convex. And it is simple and quick to calculate: area / perimeter2. That's O(1) aka constant computation time. There isn't even any way to "increase computational speed" from that. It is the absolute fastest possible.

Also, even if this wasn't categorically wrong, well then the same would be said for non-automated systems, wouldn't it? And actually I know that humans usually use measures that are inferior to isoperimetric quotient, such as convex hull (which is neither stable NOR convex).

All in all, authors manage to once again assert a conclusion that is the exact opposite of the truth.

Next quote:

In theory, fully-automated redistricting merely implements unambiguous redistricting criteria in the service of accepted representational goals. In practice, fully-automated redistricting criteria are modified for the sake of computational speed and to encode the representational goals of the system designer.

Well, no. Two things here:

  • I didn't have to modify any of the criteria for computational speed because they are all at worst O(N) (aka linear time) to compute.
  • "The representational goals of the system designer?!?!" I'm not even sure what this means or how would presume to argue that it's not the case when you use a black-box method such as hand-drawing. In auto-redistrict, all the criteria increase either fairness or practicality or both (and this is in fact true for ALL automated redistricting software.), and you can tweak which criteria you want to optimize. Those are the "representational goals".

And last but certainly not least:

Thus, fully automated redistricting solutions put the proverbial cart before the proverbial horse.

I don't even know what is meant by this. This is the process:

  1. make a map or some maps
  2. use geo-coded data to compute statistics on the map
  3. select a map or some maps based on those statistics
  4. repeat as desired
What part of that is the horse and what part the cart? Because there's no other way to arrange it!
  • You can't put step 2 before step 1.
  • You can't put step 3 before step 2.
  • And the only place you can put step 4 is last.
The is only one ordering that satisfies those rules. You can't put a cart before a horse here, it wouldn't even make any sense. There is only one available procedure.

Gaming the Vote: Why Elections Aren't Fair (and What We Can Do About It) , by William Poundstone

At least five U.S. presidential elections have been won by the second most popular candidate, but these results were not inevitable. In fact, such an unfair outcome need never happen again, and as William Poundstone shows in Gaming the Vote, the solution is lurking right under our noses.

In all five cases, the vote was upset by a "spoiler"―a minor candidate who took enough votes away from the most popular candidate to tip the election to someone else. The spoiler effect is more than a glitch. It is a consequence of one of the most surprising intellectual discoveries of the twentieth century: the "impossibility theorem" of the Nobel laureate economist Kenneth Arrow. His theorem asserts that voting is fundamentally unfair―a finding that has not been lost on today's political consultants. Armed with polls, focus groups, and smear campaigns, political strategists are exploiting the mathematical faults of the simple majority vote. The answer to the spoiler problem lies in a system called range voting, which would satisfy both right and left, and Gaming the Vote assesses the obstacles confronting any attempt to change the U.S. electoral system.

The latest of several books by Poundstone on the theme of how important scientific ideas have affected the real world, Gaming the Vote is both a wry exposé of how the political system really works and a call to action.

available on Amazon

Other Sites

Advocacy and Info


Data sources

Redistricting commissions