COMPUTING SCIENCE
Machine Politics
Brian Hayes
Reapportionment and redistricting are vexing problems of
meta-politics. They are "meta" issues because they concern
the rules of the political process itself—the way the teams
are chosen. In the American political system, a decision about
reapportionment and redistricting helps determine who will make all
other decisions for the next 10 years. It's no surprise, then, that
disputes over these matters have often been rancorous. The first
Presidential veto in American history (handed down by Washington in
1792) rejected a Congressional reapportionment plan. By the 1920s
the reapportionment issue had become so contentious that the decade
ended before Congress could agree on a new formula. More recently,
hundreds of redistricting plans have been challenged in court; two
Supreme Court decisions last summer invalidated Congressional
districts in North Carolina and Texas.
This history of bitter conflict prompts speculation on the
meta-meta-political question of how best to resolve meta- political
questions. In particular: Would it be feasible to take the process
out of politics—indeed to take it out of human hands
altogether? The answer is surely yes. Computer programs could
readily draw legislative districts. Drawing good districts,
however, is a more challenging assignment. And harder still would be
persuading the legal and political establishment to give up control
of the process and accept an algorithmic solution.
Whether or not computerized redistricting would make for good
government, it offers some interesting exercises in mathematics and
computer science. Algorithms for redistricting exploit techniques
from computational geometry, graph theory, combinatorics and
optimization methods. Even if such algorithms are never embodied in
law, perhaps they can suggest some ideas that would be useful in a
more conventional approach to redistricting.
Remaking the House
The U.S. House of Representatives reconstitutes itself every 10
years in a two-part process. The first part is reapportionment, in
which each state is allotted its share of representatives. This is a
purely arithmetical operation, and at first it appears quite simple.
Each state's share of the seats in the House is proportional to its
share of the total population, as enumerated in the decennial
census. But representatives come only in integer units, and so some
rounding of numbers is needed. That's where the trouble lies. There
are many schemes for rounding, some of which favor the larger states
and some the smaller.
From 1790 until 1940, reapportionment was a reliable source of
Congressional acrimony every 10 years. Since 1941, remarkably, it
has become a nonissue. What made the difference was writing an
algorithm into the law and thereby making the reapportionment
process automatic. Once the census returns are in, the allocation of
seats to states is immediately determined just by cranking the
numbers through the algorithm. There is no room for human judgment
or discretion. As it happens, the algorithm chosen is probably not
the best one for the purpose, but no major faction has been
sufficiently disgruntled to mount a serious challenge. This absence
of discord is perhaps the one bit of empirical evidence suggesting
that algorithmic methods might really have something to offer to
political science.
The second part of the decennial legislative makeover is
redistricting. Once a state learns that it will have k seats in
Congress, it must divide its territory into k districts, each of
which will elect one member. This is not an arithmetic procedure but
a geometric one, and it is severely underconstrained. For any
k > 1, there are many, many ways of drawing lines on the
map to create k districts. This superabundance of solutions
is an invitation to political (or meta-political) mischief.
The kind of mischief that comes to mind first is the partisan
gerrymander—a redistricting plan that favors one political
party over another. The term dates back to 1812, when Elbridge
Gerry, as governor of Massachusetts, presided over the creation of a
sinuous legislative district that opponents compared to a
salamander. There is also the "sweetheart" gerrymander,
where incumbents of opposing parties collude on a redistricting plan
to ensure their own re-election. Political gerrymandering is roundly
condemned by civic-interest groups, who argue that it gives an
unfair advantage to those who happen to be in control in a year
divisible by 10. They get to rig the electoral machinery to retain
their advantage throughout the following decade.
The legal status of political gerrymandering is uncertain. No
federal statute explicitly forbids it, and so far the Supreme Court
has never overruled a districting plan because of political bias.
Nevertheless, gerrymandering is widely considered unsporting, and
blatant instances are likely to offend the electorate.
Another form of gerrymandering,
which aims to dilute the political strength of racial and ethnic
minorities, was outlawed by the Voting Rights Act of 1965. Measures
taken to comply with this act were the issue in the recent North
Carolina and Texas litigation. Both states, under instruction from
the Department of Justice, created "minority-majority
districts" where African-American or Hispanic communities would
be able to elect representatives of their choice. The Supreme Court
ruled four of these districts unconstitutional on the grounds that
race or ethnicity had been the predominant consideration in drawing
them. (Note: I live and vote in the soon-to-be-former 12th district
of North Carolina, and the recent commotion over its status is what
inspired me to write on this theme. North Carolina districts serve
as examples in much of the discussion that follows.)
The Good District
There is no consensus on what qualities a good redistricting plan
ought to have, but here are some widely recognized desiderata:
- All the districts within a state should be equal in
population. This is the burden of the "one person, one
vote" rule enunciated in a series of Supreme Court
decisions beginning with Baker v. Carr in 1962. The court has
enforced a remarkably stringent standard of numerical exactness;
in 1983 a New Jersey plan was struck down for numerical
inequities of 0.69 percent. (For comparison, the error in the
1990 census is estimated at 1.4 percent, and from state to state
the average population of a Congressional district varies by
almost 60 percent.)
- Each district should be a
single contiguous territory. At least some states accept the
minimal definition of contiguity, allowing regions connected by
a single point. There are two places in North Carolina where
districts cross each other, which implies that the connecting
isthmus must be a dimensionless point.
- Districts should be compact. Tentacles wriggling across the
landscape arouse suspicions, including those of Supreme Court
justices. (The North Carolina 12th district is 165 miles long
but so narrow that a candidate for the seat remarked, "I
can drive down Interstate 85 with both car doors open and hit
every person in the district.") Compactness is surprisingly
tricky to define and measure. Computational geometry might seem
to offer guidance here, but H. Peyton Young of the University of
Maryland has shown that various mathematical measures of
compactness yield counterintuitive results. For example, a
spiral tract of land that winds around itself like a coiled
snake passes several tests of compactness, but few would
consider it a natural shape for a Congressional
district.
- Districts should recognize existing
communities of interest. This is an argument for homogeneity,
for creating districts that are uniformly urban or rural,
coastal or mountainous, industrial or agrarian, etc.
- Similarly, districts should conform to established natural
and political boundaries whenever possible. Until 1990 North
Carolina districts were always assembled from whole counties,
but that practice has had to yield to other
imperatives.
- Stability and continuity are virtues
in a redistricting plan. A procedure that starts from scratch
and draws an entirely new map every decade is likely to be
unpopular not only with incumbents but also with
constituents.
- Finally, under the Voting Rights
Act a district must not be drawn with the intent or the effect
of excluding minority candidates from election.
Conflicts between these criteria are commonplace. Creating
minority-majority districts may require splitting counties; and the
one-person, one-vote rule can put all the other factors in jeopardy.
When compromise is necessary, the courts have given the highest
precedence to numerical equality.
Point-and-Click Redistricting
The computer is already an essential tool in redistricting; no state
today draws its districts with Magic Markers. The computer tools in
common use are interactive programs. You sit at a display screen
showing a state map that can zoom in on individual counties,
precincts or census tracts. You select a geographic unit on the
screen and then issue a command to assign it to a district or
transfer it from one district to another. The system offers
immediate feedback on the political and demographic consequences of
each move. You see at a glance the population of each district, its
racial and ethnic composition and various indicators of political allegiance.
Underlying this interactive facility is a database linked to the
map. Basic demographic data come from the Census Bureau, with
populations broken down into geographic units as small as the census
block, which generally comprises about a dozen houses. Political
intelligence-such as numbers of registered voters, party
affiliations, voter turnout statistics and the results of key
elections-has to be collected from county boards of elections. The
hardest part of building the database is reconciling data from
different sources. Boundaries of wards and precincts don't
necessarily coincide with the boundaries of census blocks, and so
interpolation is needed. (For the 2000 census, the states and the
Census Bureau are cooperating to make the boundaries more
consistent, which means the next census should be a more efficient
tool for the gerrymanderer.)
The introduction of computers into the redistricting process has
allowed more precise analysis of proposed plans. A map can be
fine-tuned by shifting individual census blocks from one district to
another, whether to equalize populations or to achieve political
goals. It is no accident that in many states both major parties have
access to their own computer systems for redistricting.
For the 1990 round of redistricting most states employed proprietary
software specially designed for the purpose and running on
mainframes or minicomputers. For the 2000 round there is growing
interest in adapting more versatile geographic information systems
to redistricting, and running them on client-server networks of
computers. But these systems too are mere interactive aids to the
human redistricter; they do not make autonomous decisions about
where to draw boundary lines.
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.
Do-It-Yourself Redistricting
Lately I have tried implementing a few elementary redistricting
algorithms, testing them on North Carolina examples. My toy
geographic information system includes county-level demographic data
(downloaded from the Census Bureau Web site), a polygonal outline of
each county (using coordinates cadged from a commercial Postscript
map), and a hand-compiled "touch list" of contiguity data.
(No political information is included.) Maps drawn by this system
cannot be taken seriously as redistricting proposals, in part
because whole counties are too coarse a unit of population to
satisfy the requirements of district equality and the Voting Rights
Act. But even a crude model reveals some of the traps and snares
that always await when you try to specify a process in enough detail
for a machine to do it. (Source code is available.)
The simplest of the algorithms is a cake-cutting method. Imagine
holding a knife over a map of North Carolina, with the blade lined
up north-to-south as it moves slowly from west to east. As soon as
the knife has crossed counties with enough people to make up a
Congressional district, you cut. Then the knife continues westward,
until it has passed over another district's worth of population,
where you make a second cut, and so on. The procedure creates a
series of districts as vertical slices. A variation of the method
was once the subject of a proposed ballot initiative in California.
In describing an algorithm like this one, details are crucial. When
is the knife blade deemed to have passed over a county-when it
touches the westernmost point, the easternmost, the midpoint, the
county seat? How do you adjudicate ties, when two or more counties
lie at the same longitude? Exactly when does the knife blade cut off
a group of counties-just before the district exceeds the ideal size,
or just after, or by some other rule? Decisions on these matters may
be arbitrary, but they have to be stated explicitly.
Maintaining contiguity in the districts turns out to be the
trickiest part of writing a program for the cake-cutting algorithm.
Just because two counties are adjacent in a list sorted in
west-to-east order does not mean the counties are contiguous. I
dealt with this complication as I was writing the program, but a
subtler problem caught me by surprise later, when I first tested it.
The procedure can run into a blind alley, leaving a county stranded
among counties already allocated to other districts. In this
situation the program simply fails: It cannot create the required
k contiguous districts.
Using counties as indivisible units of population, the cake-cutting
algorithm yields pretty ragged-looking districts, with a mean
deviation from the ideal district size of almost 12 percent. If the
same algorithm were applied to census blocks, the results would be
much smoother (North Carolina has 100 counties, compared with almost
230,000 census blocks), but some of the districts would be very long
and skinny.
Another model for a redistricting algorithm is the National Football
League draft, where the team with the worst win- loss record gets to
choose first from the pool of new players. In the redistricting
version of the draft, the district with the smallest population
chooses from the pool of unclaimed counties, always picking the
highest-population county contiguous to its own territory. (In the
argot of computer science this is a "greedy algorithm.")
Again, details such as the handling of ties need careful attention.
Also, getting the procedure started is a potential trouble spot. The
obvious strategy is to begin with empty districts, so that the
k largest counties will be selected as the
"nuclei" of k Congressional districts. This
happens to work reasonably well in North Carolina, but it is easy to
imagine pathological cases where all the largest counties are in a
tight cluster, producing severely deformed districts.
A glance at the output of either the cake-cutting or the greedy
algorithm shows immediate opportunities for improving the map.
Shifting or swapping selected counties would help to equalize
populations or make the districts more compact. This suggests adding
a post-processing stage to optimize the alignments. The Kaiser-Nagel
algorithm is just such a procedure, and so I wrote a program based
on similar principles, using population equality as the function to
be optimized. Single-county moves were attempted repeatedly, in a
specific sequence, until the system reached a stable state, where no
further move would improve the situation. Applied to the output of
the greedy algorithm, the program reduced the mean deviation from
10.1 percent to 4.4 percent.
As noted above, the Kaiser-Nagel procedure is a steepest- descent
method, and therefore vulnerable to getting trapped in a local
optimum. A technique called simulated annealing can overcome this
drawback. The idea is to accept not only all moves that improve
population equality but also a few randomly selected detrimental
moves. In other words, when a county is shifted from one district to
another, the move is always accepted if it yields better population
balance, and in addition it may sometimes be accepted even if it
makes the balance worse. The probability of accepting an unfavorable
move is determined by a parameter analogous to a temperature, and
the system is "annealed" by steadily reducing the
temperature toward zero, where only favorable moves are possible.
The effect is to jiggle the system out of premature local optima,
increasing the chance that it will eventually find the global optimum.
In my first attempt at an annealing program I was again caught
off-guard by contiguity problems. I had not foreseen something that
now seems obvious: that giving away a county can leave a district in
two or more disconnected pieces. When this bug was corrected, the
program worked quite well. The best run in a series of experiments
with various annealing schedules produced a mean population
deviation of under 1 percent. But this improvement comes at a high
price: The algorithm is no longer deterministic. Because the program
has an element of randomness, repeated runs on the same input data
yield different results. This is a loophole the gerrymanderer could
exploit, running the program again and again until the result looks "right."
Beyond Human Control
When computer-aided redistricting was first talked about 30 years
ago, it was supposed to end political gerrymandering. So far, it has
mainly had the opposite effect, providing a better tool for the
manipulation and coordination of political data. As computers and
software systems grow more powerful, gerrymandered districts will
doubtless become both more effective and more subtly hidden.
The algorithmic approach offers an alternative, but it would require
a major shift in attitude and expectations—a meta- political
revolution. No longer would redistricting be an opportunity to seize
political advantage; it would have to be seen as a neutral or
arbitrary event, beyond human control, above politics, subject to
luck, much like the random choice of which candidate's name is
listed first on a ballot. Redistricting would also be lost as an
instrument for achieving social goals, such as creating a more
racially balanced Congress.
If algorithmic redistricting is not to become another form of
high-tech gerrymandering, the mandated algorithm would have to be
spelled out in exacting detail, leaving no discretion to the
programmer or the operator of the computer. The specification of the
algorithm would also have to be openly published, presumably as part
of a statute, so that anyone could write a program to check on the
result of the official computation. And the specification would have
to be so explicit and detailed that every correct implementation of
the algorithm would give identical results on all legal inputs.
Legislators have little experience writing algorithmic
specifications. Even for experts, creating a correct and
ambiguity-free definition of a practical redistricting algorithm
would be a daunting challenge. Of necessity, the algorithm would
have to be a simple one. Elaborate weighing and balancing of
multiple criteria, or complicated hints and heuristics, would leave
too much room for mistakes and mischief. Also, the algorithm would
have to be deterministic, so that it would always yield the same
result on the same input data. And the required inputs themselves
would have to be simple and trusted, perhaps limited to what the
Census Bureau supplies.
After a few weeks of experimenting with redistricting algorithms, am
I prepared to turn the nation's political map over to computers? I'm
unsure. There is no doubt that people can draw much better districts
than any simple program can. Unfortunately, people can also draw
much worse districts. Thus the question of whether we would be
better off with people or machines drawing district lines depends on
one's assessment of the intentions and character of the people or
the machines who would do the drawing.