The computational complexity of automated redistricting : Is automation the answer ?
Micah Altman · Rutgers computer & technology law journal · 1997
There is only one way to do reapportionment-feed into the computer all the factors except political registration. --Ronald Reagan(1) The rapid advances in computer technology and education during the last two decades make it relatively simple to draw contiguous districts of equal population [and] at the same time to further whatever secondary goals the State has. --Justice William Brennan(2) I. REDISTRICTING AND COMPUTERS Ronald Reagan and Justice Brennan have both suggested that computers can remove the controversy and politics from redistricting.(3) In fact proponents of automated redistricting claim that the districting plan can be determined, given any set of specified values. The Supreme Court has expressed a similar sentiment by addressing such mechanical principles as contiguity and compactness in two recent redistricting cases, Shaw v. Reno(4) and Miller v. Johnson.(5) Will we soon be able to write out a function that captures the social value of a districting arrangement, plug this function into a computer, and wait for the redistricting plan to emerge from our laser-printers? This rosy future is unlikely to be realized soon, if at all, because the three problems that face automated redistricting are unlikely to be solved. First, current methods of redistricting are flawed in that they consist primarily of trial and error. Second, redistricting problems are computationally complex, so they will not be solved with the use of faster computers. Third, automated redistricting cannot meaningfully capture the social worth of political districts. Part II of this Article illustrates how current redistricting methods are not adequate for the purposes of automated redistricting. Current automation techniques must resort to unproven guesswork in order to handle the size of real redistricting plans. Consequently, before automated redistricting produces trustworthy results, large gaps in the process must be filled. Proponents of automation assume that despite current shortcomings, finding the optimal redistricting plan simply requires the development of faster computers. Parts III and IV will demonstrate that this assumption is false-in general, redistricting is a far more difficult mathematical problem than has been recognized. In fact, the redistricting problem is so computationally complex that it is unlikely that any mere increase in the speed of computers will solve it. Even if these difficulties can be overcome, automated redistricting still faces a serious limitation: to use automated redistricting, a function must be written which is rigid enough for computer processing but subtle enough to meaningfully capture the social worth of districts. Part V argues that such a function will necessarily have to ignore values that are based on the subtle patterns of community and representation which cannot be captured mechanically. II. CURRENT RESEARCH ON AUTOMATED REDISTRICTING Although the literature on automated redistricting is at least thirty-five years old, it has seen a recent resurgence. This research generally falls into two categories: the first addresses the merits of automated redistricting per se, and the second suggests methods we can use to create districts automatically.(6) This part briefly summarizes the prior research in each of these two categories. A. Arguments for Automating the Redistricting Process In 1961, William Vickrey, in one of the earliest papers on this subject, proposed that districting be automated, and that this automation process be based upon two specific values: population equality and geographical compactness.(7) Under his proposal political actors would be permitted to specify or add criteria to a goal function for redistricting, but would not be permitted to submit specific redistricting plans. …