The Rose Report on algorithmic redistricting

The Rose Report discusses algorithmic approaches to redistricting such as the shortest-splitline algorithm.

The Rose report points out that these algorithms could be unconstitutional and seems to consider algorithmic redistricting approaches to be politically naive.

A recent letter-to-the-editor in The Appeal-Democrat suggested we just draw district lines according to latitude across the state to create the areas our legislators represent. Many people say such things, not unreasonably, because they are ignorant of the fact that such districts would inevitably be unconstitutional.

The idea behind such proposals is simple: people want to take the “politics” out of redistricting politics in a complete and total manner. Of course, in practice, trying to take the politics out of politics is as nonsensical and impossible as the verbal formulation. Further, such reforms might cause more problems than they would ever solve. Such exercises can be valuable as thought experiments, but realistic reforms strive for something much more moderate and, for lack of a better word, political.

I disagree with the assertions made by the Rose report that algorithmic approaches to redistricting are forever unrealistic reforms.

The Rose report directly and indirectly references a number of other algorithmic redistricting proposals that have been made. Not surprisingly the shortest-splitline algorithm is not the first such proposal.

A list of references (caveat: I have only read a few of these):

  • The Rose Report post which includes excerpts from an interview with Barry Keene:

    HICKE: Ah, yes, there comes the Elections Committee again. [Laughter]

    KEENE: Yes, it’s redistricting time, so you get to do redistricting.
    Well, the politics of redistricting was fascinating, and it was coming up, but it was not really my cup of tea. Having power over the survival of lots of legislators by drawing districts is a source of great power, but it s also not where I wanted to be.

    HICKE: Did you propose redistricting by computer, or was that just something that happened?

    KEENE: Yes, I did. I ve always felt that redistricting more than anything else poisoned the well in the legislature, particularly the assembly, where Republicans felt that they would never be permitted to become a majority, and decided that they would throw bombs within the institution and bring the institution to a halt. They were probably correct in their judgment on the first part, that under redistricting by Democrats they would never be permitted to become a majority.

    People didn’t like commissions, because they always figure that no matter how much you try to balance commissions, there’s always going to be that odd vote that s going to be the deciding factor

    So I said, “What else can we do?” And maybe borrowing on my-why I borrowed on it, I’ll never know-on my coin-tossing experience as a way of producing staff reduction, [laughter] we were going to create redistricting by computer, and use something called a random number generator to resolve differences. So after all of the criteria had been applied, the criteria of equal numbers of districts, the criteria of minority representation-there’s some federal criteria on that-after all of the attempts to consolidate areas of interest and not cross too many jurisdictional boundaries, you would still be faced with the capacity to create an infinite number of districts. It would just be a smaller infinity than you had before.

    So how do you resolve that? You do it with a random number generator. Well, nobody understood this business. I shouldn’t say nobody. Most legislators said, “Well, we can’t turn redistricting over to a computer, its not politically good for us, and we don’t understand what it is that you’re proposing.” John Garamendi, I believe, in one of his moments of appealing to the television spotlight, got up and said, “You know the old saying, Barry: it’s garbage in, garbage out.”

    Well, it died a fairly uneventful death.

  • Letter to the editor of The Appeal-Democrat proposing just using latitude lines
  • Brian Olson’s “fair redistricting” algorithm
    Olson redistricting of CA
  • George L Clark’s redistricting algorithm
  • PDF with redistricting proposal by Roland Fryer and Richard Holden
  • political science dissertation by Micah Altman on redistricting formulations ( I have not read this but I understand that he describes desirable properties of redistricting and then demonstrates that the finding an optimal solution is computationally complex (NP hard) )
  • A pair of posts by the Geomblog on algorithmic redistricting. post 1, post 2
Advertisements

6 responses to “The Rose Report on algorithmic redistricting

  1. Academically fascinating, but if people are unhappy about the politics of district boundaries, perhaps their time might be better spent in the pursuit of democratic reform. In Canada, mixed member proportional representation and abolition (or at least election) of the senate would be two examples.

  2. You should take a look at the “shortest splitline
    algorithm”
    http://rangevoting.org/SplitLR.html
    and associated pages. This is the simplest
    automatic districting proposal.

    Concerning constitutionality, read these blog posts:
    http://groups.yahoo.com/group/RangeVoting/message/6345
    http://groups.yahoo.com/group/RangeVoting/message/6346
    http://groups.yahoo.com/group/RangeVoting/message/6349

    and they refer to the text of the voting rights act,
    available here:

    http://rangevoting.org/VRAtext.html

    I’d love it if you’d endorse and/or join rangevoting.org
    (click “endorse”, “join” etc on
    its front page).

  3. And another:
    http://electionmathematics.org/ (‘Drawing Districts’ link)

  4. Years ago, I came up with an idea for redistricting I called “Sandbox”. Think of a sandbox in the shape of a state. Inside the box, have little walls for County and City borders. Pour in (by computer simulation) sand at the center of each district, depending on the needed population. I hope that using sandbox as a start, local minima problems are avoided. If interested, send me an Email

  5. Prop 11 creates a microcosm of the legislature, and gridlocks with 6 votes, which should protect most of the gerrymandering.
    If this is too long, just delete it. Dug this up, haven’t looked at it in a long while. Not much interest in it. The reality is that the Democrats threatened to spend $10 million in California to oppose such an algorithmic initiative.
    REDISTRICTING: At the start of each decade, the Census Bureau divides the United States into small areas called Census Blocks. The number of people in each Block is then counted. This data is used to determine legislative districts, with each district having equal population. The goal here is to create a computer program that will take the census data as input and then create the districts as output. Geometry, not gerrymandering. See Businessweek magazine, June 14, 2004, page 65.
    UNBIASED: To prevent Gerrymandering, the input data shall not include anyone’s race, gender, religion, political party, occupation, or financial status. All input data should come only from the Census Bureau. The software should stand the test of time, and not need lots of changes due to Operating System or hardware “upgrades”. FORTRAN, not Visual Basic. The software shall be posted for public scrutiny.
    SOAP BUBBLES: When the bubbles touch each other, they form walls between themselves. If a narrow straw is inserted and used to blow additional air into a bubble, the other bubbles will be pushed aside and the walls reconfigured according to geometry. For this task, consider this geometry occurring in only two dimensions over the surface of the map of California.
    SAND BOXES: A large box with high walls is subdivided inside with lower walls into a number of irregular compartments. A funnel placed above a spot in the box drops sand. The sand will form an expanding cone on the spot in the bottom of the compartment. The edge of the cone will reach the edge of the compartment. That wall will block the sand, causing the sand to assume at the bottom the shape of the compartment. Eventually, since the wall is only so high, enough sand will overflow the wall and start filling an adjacent compartment.
    MAKING POINTS: To simplify computation, the area of each Census Block is approximated as a point within its area, with a latitude, a longitude, and a population.
    RASTER: Analog black and white television sets produce a picture by drawing 480 lines on a screen. By forcing each Census Block to be on a line, it makes the computer memory compact and searchable. Unfortunately, 480 lines gives inadequate resolution for a State the size of California; 4800 lines is minimal.
    PIXELS: Each line is divided into grid squares for roughly square pixels. The information for each Census Block point is stored in memory inside the grid square at the lower left corner. To maintain accuracy, the offset between the lower left corner grid intersection and the Census Block point in the line is also stored in memory. If there are two Census Blocks in the same grid square, they can be averaged. If averaged grid squares happen too often, the grid is obviously too coarse.
    GRID: Each intersection on the grid is addressed in memory as a row and column, and contains integers. To speed comparisons, instead of a string, use an integer for each County, subcounty (or water district, fire protection district, or other intercity area), City, and subcity (or boroughs or neighborhoods or whatever). The other integers are population, offset, and assigned district.
    ALLOCATOR: The allocator uses the census data for the particular State to size all the arrays in the program for that State. Details on the allocator are not included to keep this brief. Since California is the State, then the arrays can be sized manually to conserve limited resources. Note that the Census Block graphic files furnished by the Census Bureau are not needed until after redistricting.
    IMPLIED BORDERS: Instead of marking the location of borders (except for the State boundary), a border is assumed when a change occurs in the integer for County, subcounty, City or Subcity from that of the adjacent grid square.
    CUMULATIONS LIST: The Cumulations List has each district’s number. It is kept bubble sorted so the district with the lowest population grows until it overtakes the next lowest district on the list.
    STEPS: The number of steps is divided into the desired population for all districts. This quotient is the Step Integer. A zero in the Cumulations List points to the Step Population. Initially, the Step Population is set equal to the Step Integer. Whenever the Step Population is less than the population of all the districts, a new step is created. The Step Integer is added to the current Step Population, and the new step is bubble sorted into the Cumulations List.
    DISTRICTS: Each district has the following: a keystone (trapezoid correction) coefficient, a current total population, x and y coordinates for the district’s center, an Included (areas) List for each new border crossing, a Current Radius, a vectors table for up to sixteen i and j vector forces and their districts of origin, a few status integers, a district color to make a screen display or printout pretty.
    COREMAKER: By having the core memory size the same for all Districts, the one CoreMaker is used for all districts. A standard radius makes a circle around a District Center. Recall that for a triangle, the base squared plus the height squared equals the hypotenuse squared.
    COREMAKER ARRAY: Take a triangle and point it upwards with the point at the District Center of a circle and the radius equal to the hypotenuse. If the angle of the triangle at the center of the circle is almost zero, you see a vertical line going straight up from the bottom of the circle to the center. Increase the angle until the vertical line is one grid square less than the radius. The horizontal side (The sine side) of this triangle is the square root of quantity the radius squared minus the square of the vertical line. This value is recorded into the Coremaker Array. The vertical line is shortened by another grid square, and the next value is recorded. When the angle is 90 degrees, the last value is equal to the radius. Thus, the array furnishes horizontal values for a quarter circle of standard radius.
    CORE: A Standard radius Circle is placed with its center at the grid intersection by the District Center. Each grid square inside the circle is checked for a census point. If found, a record is created with the grid row and column, the assigned district, and the distance from the District Center to the census point. These records are bubble sorted into the district’s Core Array with the lowest distance from the District Center first. The Core Array has a County Pointer, a City Pointer, a Subcity Pointer, a Boundary Pointer, a top of array pointer, a (top of the) Included List Pointer, and an Adjacent District pointer.
    BIRTH: The District Center x coordinate could start as simply halfway between the point furthest to the west in the District and the point furthest to the east in the old District. An area centroid (averaging thin rectangular slices) would be more complex to compute. Districts start by accumulating Census Blocks as their pointers go up their core arrays. A Points Remaining variable for all districts is decremented.
    BREACH POINT: The first point found on the other side of a border is the Breach Point. A distance from the breach Point is computed for the rest of the points found on the other side, and the maximum distance is the Group Size Integer. The Ruler Integer originally is kept equal to the Current Radius Integer. After several groups are on the Included List, the Ruler Integer equals the smaller of the Current Radius Integer or the Group Size Integer.
    BREACH DISTANCE: Breaching doesn’t happen until the Current Radius exceeds the Breach Distance, or there is a memory overflow in the district. The Breach Distance is computed from the Current Radius and the Ruler Integer, and then stored for future comparisons. If it is a subcity border, the Breach Distance is the Current Radius plus the Ruler Integer. If it is a city border, the Breach Distance is the Current Radius plus the Ruler Integer. If it is a subcounty border, the Breach Distance is double the Current Radius plus double the Ruler Integer. If it is a county border, the Breach Distance is double the Current Radius plus double the Ruler Integer.
    CORE BREACHES: When a border is crossed, all the similar points found on the other side will be written to a group, and those points will at the same time be zeroed from the core array. The group is bubble sorted by distance to each point from the Breach Point. If the Core Memory allocation overflows, the nearest subcity border is breached. If there is no subcity border to breach, then the nearest city border is breached. If there is no city border to breach, then the nearest county border is breached.
    CORE MEMORY ALLOCATION: With a Core, memory is divided up roughly as follows: 0% to 1% (growing upward) for the Included List, 1% to 62% for the Core Array; 75% down to 62% for group A, 75% to 87% for group B; and 99% down to 87% for group C. Group D has a pointer into the core array instead of some memory. Each group is kept sorted. If group B or C grow too large, first they grow into the other’s memory space; if more space is required, the oversized group can be switched with group A. If group A becomes larger than 12%, then the Core Array is condensed downward by removing the zeroes. Group A can then grow downward below 62%.
    FIRST CONTACT: When a district first finds a Census Block in the Grid Array assigned to another district, the Adjacent District Pointer goes from zero to pointing to that record in the district’s own core array. The next find of another district while the Adjacent District Pointer is nonzero ends the birth phase for the software program, and vector forces begin.
    VECTORS: When a district finds a point that is already assigned to another district, both districts push against each other’s center with a vector force depending on how short of population they are. When a district finds a State border, it counts and averages the out of bounds points to create a vector force against that district.
    MOVEMENT: The District Center of the Cores are pushed to a new location by the vectors when a step happens. The magnitude of the movement vector is added to the magnitude of the Current Radius variable, and if that exceeds the Standard Radius variable, a new core is made. Otherwise, every point in the core memory is resorted for the new District Center.
    OCTAGONS: After the District outgrows its Core, it is replaced by an octagon shape. The octagon has a size integer, a direction (of movement) integer, row and column of the last grid square acquired, the vectors table, and the District Center coordinates. Octagons grow by one grid square at a time, in an order determined by a selected algorithm. The size of an octagon is determined by a size integer which indicates the number of grid squares from the top to the bottom.
    OCTAGON SIZE: If the Size Integer is an odd number, then the horizontal and vertical faces of the odd octagon will be an odd number of grid squares. The Face Size Integer is an odd integer just less than the tangent of 22.5 degrees (about 0.4) multiplied times the Size Integer. The District Center will be in the center of a grid square.
    ODDS: When the size integer increases from even to odd number, the face size is recomputed, and therefore will grow or shrink a square. The District Center moves to the grid center NE, SE, SW, or NW of the intersection depending on the force vectors. Note that the District Center moves less than a grid square at a time, and the octagon grows in thickness by one grid square when going from even to odd, or odd to even.
    EVENS: The Size Integer increases by one to form an even octagon, and each horizontal and vertical face is increased by one grid square. The District Center moves ponderously to the grid intersection NE, SE, SW, or NorthWest. Thus, the octagon grows in a direction depending on the force vectors.
    PAC-MAN: Since the octagon grows in thickness by one grid square, only the grid squares on the perimeter need checking for Census Block points. Think of a PAC-MAN starting at the left side of the top face of the octagon chewing east across the face. When he reaches the right side of the top face (as indicated by the Face Size Integer), he then goes down one square and checks, then right one square and checks, then goes down one square and checks, then right one square and checks, and so on to check the NorthEast diagonal of the octagon. Position Integers keep track of where he is, so he knows where to go next.
    LOCATION ALGORITHM: Actually, he doesn’t have to go to the adjacent grid square, it’s just easier to visualize; hopping around according to some algorithm to help round out the Octagon is fine. When he reaches the starting point, the octagon size integer is increased by one to grow the octagon, and the District Center is moved.
    OCTAGON BREACHES: An octagon breach array is created similar to the core breach array. If the breach radius reaches maximum, or if the breach grows across 2 borders, the breach array is cleared, and the core resumes growing including in the breached-into area.
    SURROUNDED: If the perimeter of the district consists of points all of which have been acquired by other districts, then a check of all grid squares just outside of the perimeter are checked. If none are available, then the district is deemed surrounded.
    CANNIBALISM: When push comes to shove, a hungry surrounded district will chew off some Census Block points from the district indicated by the Closest Adjacent District Pointer. An arc is formed at the indicated point, and the hungry district swallows from the ends of the arc.
    AUDIT POINTS: If the audit variable is not zero, then depending on status or if triggered by a Quality Assurance check failure, the arrays and variables are dumped to the hard drive for autopsy. At equilibrium, the grid is checked to verify there are no grid points unassigned, and the district with the greatest population doesn’t have more than 1% population above that of the district with the least population.
    BALANCING: When growth is done, the district with the highest population and next highest population will trade census blocks with neighboring districts to shed some of the excess population. Likewise, the district with the least and the next least population will trade census blocks. These trades sacrifice some compactness to gain more equal population.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s