Redistricting Utopia/Redistricting@Home
Walker Lindley and Dr. Randy Bentson
Gerrymandering is a serious problem facing American politics today. To solve this problem some states use bi-partisan or non-partisan redistricting commissions, while other states allow partisan politicians in the legislature to do it. These practices lead to serious problems like those seen in Texas in 2003 where a Republican-controlled legislature passed a redistricting plan that reduced the number of seats held by Democrats in the next election. This kind of biased redistricting, or gerrymandering, is harmful because it can shut the minority party out of the political process for an extremely long time and often does not accurately represent the will of the voters.
We propose using computers to impartially create fair redistricting plans. Most states define fair as good apportionment (the idea of "one person, one vote") and compact districts. Good apportionment is simply even population distribution, so it's clear that having a roughly equal number of people in each district satisfies this requirement. However, different states have different standards that must be met, though. For instance, Washington state requires that a district cannot deviate from perfectly even distribution by more than 0.5%. While most states require compact districts, few define what that means. Since there is no consensus on measuring compactness, we have decided to use a measure of compactness we call the gerrymander factor. It is defined as the perimeter squared over the area (GF = (P^2) / A) of the district with smaller numbers being better. This has several nice properties including being scale-invariant and being relatively fast to compute.
Given the large number of possible redistricting plans (especially if you consider ones that do not meet the fairness requirements), it would be difficult at best to create a formal algorithm for finding the most fair redistricting plan for a given set of precincts. Therefore, we are using a genetic algorithm to find good solutions quickly. We do this by representing a redistricting plan as a series of 1's and 0's that is analogous to a strand of DNA. We can then rate the quality of this DNA using a fitness function. Finally, we create many random solutions and run a simulation of evolution using the principle of survival of the fittest to increase the quality of our solutions until an acceptable one is found. Not surprisingly, this can take a very long time, especially for large datasets. To help speed up this simulation, we are using distributed computing. Each computer is treated as a separate island on which evolution is taking place with solutions from one island occasionally migrating to another island. We have converted the GIS data provided by King County (the county Seattle is in) to a format we can use. Creating fair districts for so many precincts is much more difficult and distributed computing has been essential in speeding up that work.
Links for Summer 2007 to the present:
Links for Summer 2006: