COMPUTING SCIENCE
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.
» Post Comment