The computational complexity of automated redistricing: is automation the answer?

• Author: Altman, Micah

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)

1. 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 "optimal" 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 "optimal" 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.

2. 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.

   1. 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.(8) With no further human input, plans would be created automatically from census blocks to meet the goal function. In essence then, automated redistricting is an attempt to push all decision-making to the beginning of the redistricting process.

      Vickrey asserted that automated redistricting provides a simple and straightforward method of eliminating gerrymandering.(9) More recently, Michelle Browdy elaborated on Vickrey's arguments, creating what seems to be the best model for automated redistricting.(10) Five main arguments are offered in the literature:

      1) Automated redistricting creates a neutral and unbiased district map;(11)

      2) Automated redistricting prevents manipulation by denying political actors the opportunity to choose district plans, while simultaneously producing districts that meet specified social goals;(12)

      3) Automated redistricting promotes fair outcomes by forcing political debate over the general goals of redistricting, and not over particular plans, where selfish interests are most likely to be manifest;(13)

      4) Automated procedures provide a recognizably fair process by meeting any representational goals that are chosen by the political process.(14) Browdy argues that such procedural fairness will help to curtail legal challenges to district plans;(15) and

      5) Automated redistricting eases judicial and public review because the goals and methods of the districting process are open to view and because the automation process creates a clear separation between the intent and effect of redistricting.(16)

   2. Criticisms of Automated Redistricting

      Authors have raised two central objections to automated redistricting: (1) automatic redistricting should not be viewed as inherently objective, and (2) because it is up to legislators to select among automation plans, political bias is unavoidable.(17) John Appel argues that redistricting standards and processes embody political values and that automation of this process hides the fundamental conflict over values.(18) Robert Dixon points out that automated processes, even if based on nonpolitical criteria, may have politically significant results.(19) Recently, Arthur Anderson and William Dahlstrom have cautioned that political consequences of redistricting goals makes redistricting, whether it is automated or not, inescapably political.(20)

      The idea that automated redistricting is not inherently objective seems both correct and unavoidable. Automation is a process for obtaining a given set of redistricting goals. Neutrality, however, is a function of three factors--the process selected, the goals themselves, and the effects of seeking to obtain those goals in a particular set of demographic and political circumstances. Since there is no general consensus over what objectively neutral goals are, or whether they exist at all, no amount of automation can make the redistricting process objectively neutral.(21)

      This objection only relates to the claim that neutrality can be achieved through computer redistricting. Many proponents do not claim that automated redistricting is objectively neutral, but instead explicitly acknowledge the political nature of redistricting goals. They propose that the automated process be used neutrally and effectively to meet goals previously generated by a political process.(22) For example, Robert Dixon, who concluded that automated redistricting could not be objectively neutral, nonetheless freely promoted its use in this context. Anderson and Dahlstrom, echoing Dixon, provide a second critique of automated redistricting by drawing attention to the legislative process used to select automatically generated plans.(23) They argue that the legislature's willingness to accept plans generated by an automated process will be politically motivated, reintroducing political bias into the process.(24)

      Although Anderson and Dahlstrom's criticism seems valid, there is a simple cure. Any attempt to reintroduce political bias can be prevented by mandating legislative acceptance of the results in advance. In general, however, researchers have largely underestimated the potential for political biases to become part of the automation process.(25)

   3. The Core Argument: Automation as a "Veil of Ignorance"

      Among its proponents, automation essentially plays the role of a Rawlsian "veil of ignorance" which creates fairness by hiding each actor's position in the final outcome.(26) The "veil of automation" attempts to hide the final outcome (i.e., redistricting plans) from those bargaining over the social contract (i.e., redistricting goals and procedures). Thus, advocates of the automation process claim to prevent manipulation by promoting a recognizably fair method that will, on average, promote fair outcomes.

      In this vein, Vickrey emphasizes that in order for automation to be successful at promoting fairness, it must be sufficiently unpredictable.(27) It should not be possible for political actors to deduce the results of the redistricting goals over which they bargain.(28) Without unpredictability the choice of objective functions collapses into a choice of individual plans, and the incentive to gerrymander remains unameliorated by the automation process. If actors can predict the plans that will result from specific values, the veil of automation could be pierced.(29)

      While proponents of automated redistricting recognize the need for unpredictability, they do not always consider the danger from unpredictable results. An automated process for creating districts in accordance with agreed upon values must predictably achieve (or at least approach) the goals that were agreed upon in the bargaining stage, or otherwise lose legitimacy.

      The automated redistricting process must maintain a delicate balance. To prevent manipulation while maintaining fairness, the automated process must predictably implement the redistricting goals agreed upon in the bargaining process, but it must be unpredictable in every other dimension of interest to the bargaining agents. These requirements are difficult to satisfy when bargaining agents seek specific, hand-tailored gerrymanders. Such requirements become even more...