About

Auto-Redistrict is a free and open source computer program that automatically creates fair and compact electoral districts. Simply open a shapefile, load in census and election data (if not already included in the shapefile), and hit "Go".

Auto-Redistrict uses a genetic algorithm to design districts that meet multiple criteria, namely:

  • Geometry
    • Equal population
    • Contiguous
    • Compact
    • Minimal county / municipality splits
  • Equality
    • Competitive
    • Proportional
    • Minimal partisan gerrymandering (maximal "partisan symmetry")
    • Minimal racial gerrymandering (maximal voting power equality)

So essentially the goal of the software is to eliminate gerrymandering by fully automating the redistricting process. It replaces the manual drawing process with automated search and analysis.

How it works

To find the number one best map, one would have to search through and evaluate every possible map. This is not computationally feasible. So instead, a heuristic search algorithm is used to evaluate only those maps that are probably good.

  1. Initialize. First, the population of potential maps is initialized. It could either start off totally random, or you could use the current electoral district shapes to start it off.
  2. Evaluate. Then the fitness of each map is evaluated on each of the criteria (in our case, compactness, equal population, competitiveness, proportional representation, etc.)
  3. Select. The best scoring maps are selected for reproduction,
  4. Recombine. and randomly recombined to form new maps, that are hybrids of the best maps.
  5. Mutate. Finally these maps are "mutated" slightly so that other potential maps that are similar to them are explored.
  6. (Repeat). This is the new population of potential maps. The process repeats from step 2.

The Geometric Criteria - Compact and Equal

The geometric criteria are standard criteria that are required by constitutional law. Well, 2 out of 3 of them are. Compactness is not a requirement in the U.S. Constitution, or most state constitutions. But we include it because it helps to fight gerrymandering by limiting the range of acceptable maps, and also it makes for more practical districts. So let me briefly go over how each score is evaluated (measured):

  • Equal population. To measure population balance, the program calculates the statistical variance of the populations of the districts. Since population selection is a Bernoulli process, the populations will take on a Normal distribution. So the variance of the population is just the square of the standard deviation. We want this score to be minimized.
  • Contiguous. To measure contiguity, or the amount of disconnected population, we count the total population that is not connected to the most populated fully-connected region. We want this score to be minimized.
  • Compact. To measure compactness, we calculate the Isoperimetric Quotient. Basically we divide the area by the square of the length of the perimeter. But we want a grand total, so we add together the reciprocals of this for each district, and then take the reciprocal of that. This gives us a weighted average. We want this score to be maximized.
  • Minimal county / municipality splits. This is essentially a trade-off with compactness. To measure split reduction, we count the number of different districts in each county, and subtract the number of counties. We want this score to be minimized.

The Fairness Criteria - Proportional and Competitive

As unequivocally demonstrated by Jowei Chen and Jonathan Rodden's paper "Unintentional Gerrymandering: Political Geography and Electoral Bias in Legislatures", party-blind redistricting results in unintentional gerrymanderying. To counteract this effect, as well as to undo deliberate gerrymandering, election data must be used in a redistricting process to ensure equal protection to both parties.

To this end, election data is used to calculate measures of fairness which enables a person - or a computer - to make an informed decision about which districing maps best represent the wills of the citizens.

The fairness criteria are designed to measure both how proportional the representation is to the popular vote, and how competitive the elections are. In other words, they measure how closely the "One person, one vote." requirement mandated by the U.S. Constitution is met, and also try to make each vote count as much as possible, by maximizing its ability to determine the elected delegates. Let me briefly go over how each score is evaluated (measured):

  • Competitive. To measure wasted votes, we count the number of votes above the amount necessary to win, for each district and each party. The more wasted votes an election had, the less competitive it was. We want this score to be minimized.
  • Proportional. To measure proportional representation, we measure the total deviation of the seats-votes curve from the diagonal. We want this score to be minimized. Note: this is how to measure partisan gerrymandering in multi-winner elections (such as ranked choice voting). We want this score to be minimized.
  • Minimal partisan gerrymandering. Seats / votes asymmetry is the total absolute deviation from a symmetric seats / votes curve. If you look at the "Seats / votes curve" in the program, it's the total darkened area. This measure was inspired by "Partisan Symmetry" as defined by Grofman and King in these papers: "Seats, Votes, and Gerrymandering: Estimating Representation and Bias in State Legislative Redistricting" and "The Future of Partisan Symmetry as a Judicial Test for Partisan Gerrymandering after LULAC v. Perry". Note: this is how one measures partisan gerrymandering for single-winner elections. We want this score to be minimized.
  • Minimal racial gerrymandering. We define voting power as the ability to elect a candidate of one's choosing. Another way to state this is the ability to effect the outcome of one or more elections. For a single district, this can be summarized by taking the margin of victory (in votes) and dividing it by the total votes cast. To total this up by ethnicity, we take the weighted sum of this over all elections. For example, for hispanics, we take the total number of votes in an election, multiply by the fraction of that district that is hispanic, and total that up over all districts. Then we do the same for margin of victory. Then we divide the margin of victory total by the votes cast total, and that gives us an estimate of the average voting power for that ethnicity. We want to minimize how much this varies between ethnicities, so we take the average of this over the entire population, and calculate the mean absolute deviation (M.A.D.) of the ethnicities from this. This gives us a summary of how uneven voting power is distributed among the ethnicities. We want this score to be minimized.


Normalization

Each of these scores will have vastly different ranges. For instance, compactness varies from 0 to 1, while population imbalance could be in the tens of thousands. But we want each score to be "weighed" about the same, or, rather, in proportion to where the sliders are set. So we have to get them all on the same scale. We call this "normalizing" the scores.

To normalize a score, we first sort the population according to one criteria, then we replace each score with their "rank" in the sorted list, and divide by the size of the population. We use this as the new, normalized score for that criteria. Another way to say this is that we replace a raw score with it's "percentile". We do this one at a time for all criteria.

Then we multiply each score by where its corresponding slider is set, and then again by where the geometry/fairness slider is set (starting from left or right, depending on whether it's a geometry score or a fairness score). We then add these all together, and this gives us a final single-number score for a map.

Selection

The best maps are selected using what's called "Truncation selection". The bottom 50% are discarded. The top 50% are recombined and mutated. After the selected maps are recombined and mutated, the process repeats.

This software is one of a kind!

To my knowledge, while there are some programs out there that automatically redistrict, and some that use heuristic search algorithms such as the genetic algorithm, this is the first, and, so far, only program that also includes fairness criteria, such as proportional representation, competitiveness, and wasted votes.

This is also, to my knowledge, the only automated redistricting program that can design multi-member proportional representation districts.