[EM] Districting Quests: Quixotic vs Practical
Joe Weinstein
jweins123 at hotmail.com
Wed Jan 21 19:06:04 PST 2004
DISTRICTING QUESTS: QUIXOTIC VS PRACTICAL
On this list we’ve 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
of computers.
To date, most messages on districting have concerned very focused topics
such as:
(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
realizable goals.
For help on these issues, we owe thanks to Jurij Toplak (message 13058) for
his mention of and link to Altman’s dissertation. Everyone who is keen on
‘automated districting’ might FIRST read Altman’s 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.
Altman’s 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 can’t we expect to get a provably optimum plan
P0, but we can’t even expect to realize a far more modest-sounding goal:
finding a plan P which is provably ‘near optimum’, or provably ‘optimum for
practical purposes’.
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 can’t be sure of G0,
we can’t 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 Altman’s 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,
Altman’s 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
plans.
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 DON’T 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 plan’s 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
concerns.
However, I suggest that we at least partly meet Altman’s 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
final-decision-making body.
Joe Weinstein
_________________________________________________________________
Check out the coupons and bargains on MSN Offers!
http://shopping.msn.com/softcontent/softcontent.aspx?scmId=1418
More information about the Election-Methods
mailing list