[EM] Districting Quests: Quixotic vs Practical

[Joe Weinstein]

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