[EM] Districting Quests: Quixotic vs Practical
jweins123 at hotmail.com
Wed Jan 21 19:06:04 PST 2004
DISTRICTING QUESTS: QUIXOTIC VS PRACTICAL
On this list weve lately posted a number of messages concerning
districting. At one point we called the topic automated districting - but
it should be clear that automation is a possible means, not an end, in the
design of an effective districting process. The goal is neither automated
nor manual operation as such, but rather a process whose efficiency and
efficacy are aided, insofar possible, by the intelligent and checkable use
To date, most messages on districting have concerned very focused topics
(1) The definition of a compactness component of the merit or goodness
function G to be used for evaluating the goodness G(P) of any proposed
districting plan P;
(2) Efficient ways to compute initial or revised compactness values, for
specific compactness functions.
(3) Specific a priori personal geometric preferences for the shapes or
alignments of districts.
This message is an attempt to look at a few broader issues: just what might
be the goals of districting, to what extent are these realizable, and in
particular what districting process(es) could be suggested for attaining
For help on these issues, we owe thanks to Jurij Toplak (message 13058) for
his mention of and link to Altmans dissertation. Everyone who is keen on
automated districting might FIRST read Altmans Chapter 5.
Altman argues that (what he calls) automated districting is in general
infeasible !! Considering the ingredients of his argument his result is not
surprising, but it IS an extremely useful and important reminder.
Namely, the agent (computer) that is supposed to carry out automated
districting is supposed thereby to generate and designate as winner a plan
P0 which is (in my lingo) PROVABLY OPTIMUM, in the sense that earlier-proved
software properties guarantee that G(P0)=G0, where G0 is defined as the
maximum value of G(P) over ALL legal plans P.
As Altman argues, this requirement is fatal, assuming that the criterion G
of merit is non-trivial, so that different plans really do have different
merit values. For, in general, checking all a priori legitimate plans, in
order to find a provably best one, will require examining far too many plans
to be practical, even with many lightning-fast computers at beck and call,
and likely even with sophisticated heuristics and prune and search routines.
Altmans discussion softly notes an even worse bit of news: in general,
infeasibly much brute-force checking is needed just to work out what IS the
highest attainable merit value G0.
As a consequence, not only cant we expect to get a provably optimum plan
P0, but we cant even expect to realize a far more modest-sounding goal:
finding a plan P which is provably near optimum, or provably optimum for
In detail: suppose we agree on a suitable small positive value J -
signifying jnd, just noticeable difference. A near-optimum plan P
would be one satisfying G(P) > G0-J. As in general we cant be sure of G0,
we cant be sure whether a given plan P is near-optimum.
[Technical Aside. For some uses with the Weber-Fechner law of
psychophysics, jnd means a constant proportional difference rather than a
constant arithmetic difference. However, we can always take jnd as an
arithmetic difference: just replace the measure G by the measure log G.]
So, where do we go now? Well, it turns out that these impossibility results
have force only if you go with Altmans presumption that true automated
districting must realize the ambitious performance goal of ABSOLUTE
optimality: getting a plan P0 which is provably optimal or near-optimal
among ALL possible plans.
In my opinion, this absolutist goal is anyhow overly ambitious, and is not
required for a practical acceptable process of districting. To my thinking,
Altmans extended argument against HIS picture of automated districting
just beats a long-dead horse. Whether or not districting is automated, we
never need nor expect to get a provably optimal plan, nor even a provably
near-optimal plan, in an absolute sense, i.e. considering ALL possible
Instead all we really need is RELATIVE optimality: a districting process
which is open to submission of sufficiently many - but not impossibly many -
independently crafted well-defined plans, among which the finally chosen
plan P1 must be provably optimal or near-optimal.
WE DONT NEED ANY PLAN THAT BEATS THE BEST WHICH WE OURSELVES ACTUALLY
DEVISE in OPEN and AMPLE competition.
In other words, what we need is that districting be an OPEN process, one
which encourages submission of sufficiently many independent-source proposed
plans. An authority will be designated to receive submitted plans and see
to their evaluation for legality and merit. From that authority, anyone in
the public who cares should be able readily to get definitive information on
required format, legal constraints, and merit criteria - and then would be
able to join in the competition to produce and submit a winning plan.
Moreover, the authority would be required to ensure that all its data,
specifications, software, etc. are OPEN, so that its findings and decisions
are subject to independent verification and challenge.
Of course, all information provided by the authority will depend on advance
decisions (themselves constituting public policy, hence to be decided by a
suitable public body) about the criteria for format, legality and merit of
plans. For instance, for tractability, one requirement could be that the
required S districts be assembled from a fixed set of T territorial atoms,
identified and coded by the integers 1 through T. Then, a submitted plan
could be any T-tuple of integers in the range 1 through S. Evaluation of
the legality and merit of the plan would depend only on open published data
giving values of certain functions of the atoms. One-place functions used
might include population size (and possibly certain partisan or ethnic
sub-population sizes) and centroid coordinates. Two-place functions might
include inter-atomic distances or boundary lengths. Well-documented
algorithms would use these data to determine each submitted plans legality
and evaluate its merit.
In order fairly to encourage submission of many but not unmanageably many
plans, every citizen must be entitled to be a part-sponsor (signatory) on at
least one plan, with an appropriate number of signatures to be required.
Altman worries that any prior-defined and quantified measure G(P) of
goodness of a districting plan P will in fact be inadequate to express the
nuances of reasonable human judgements of merit which may arise in staring
at actual plans after the formal criteria have been defined. I am more
optimistic on that score, and believe that with care and anticipation the
goodness criterion can be defined carefully to include reasonable objective
However, I suggest that we at least partly meet Altmans concern as follows.
Suppose that among the legal submitted plans, the highest merit value is
G1,and let P1 be a legal submitted plan of merit G1. Define a legal
submitted plan P to be (relatively) near-optimal if G(P)>G1-J, i.e. if for
practical purposes P is formally about as meritorious as P1. It should
suffice to adopt as winning plan not necessarily P1 but rather any desired
near-optimal plan preferred by an appropriately constituted human
Check out the coupons and bargains on MSN Offers!
More information about the Election-Methods