Logo IMG
HOME > PAST ISSUE > Article Detail


Machine Politics

Brian Hayes

Algorithmic Redistricting

In the 1960s there was a brief flurry of interest in automated redistricting. This was at a time when the electronic computer was still a novel and oracular machine, widely viewed as a kind of magical question-answering and problem-solving service. Even so, algorithmic methods met with resistance or indifference, and they were used in only a few small-scale demonstration projects.

One of the more sophisticated redistricting algorithms was devised by James B. Weaver and Sidney W. Hess of Atlas Chemical Industries in Delaware. They based their approach on a problem in operations research: If you want to build a number of warehouses (or telephone switching centers, or pizza shops) to serve a dispersed population of customers, where are the best places to put them? Methods for answering this question are mainly iterative; they work by progressive refinement of an initial guess, converging on a solution that minimizes the sum of the distances from each warehouse to all the customers in its territory. In the redistricting case the actual warehouse locations are not of interest; it is the territories surrounding them that the algorithm is meant to calculate. The method puts heavy emphasis on compactness.

Henry F. Kaiser of the University of Wisconsin and Stuart Nagel of the University of Illinois developed another early redistricting program. It does not create a map de novo but instead works to improve an existing map by shifting population units from one district to another. A district can either give away a unit, or else two neighboring districts can swap units. In either case, the change is accepted only if it improves population equality (or some other measure of the plan's fitness). The Kaiser- Nagel procedure is a "steepest-descent" algorithm. It works like a marble rolling over a hummocky landscape, always moving downhill. The principal weakness of such schemes is that the marble can get stuck in a local trough and never find the global optimum-the lowest point on the entire landscape.

A few state legislative districts were drawn by computer programs in Iowa in 1967 and in Delaware in 1968. As far as I know, computer-automated redistricting has not been given a serious trial since then.

comments powered by Disqus


Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Computing Science: Clarity in Climate Modeling

Feature Article: Candy Crush's Puzzling Mathematics

Subscribe to American Scientist