[EM] Re: Automated districting

[Ernest Prabhakar]

Hi Matt,

On Jan 11, 2004, at 3:25 PM, matt at tidalwave.net wrote:
> To summarize:  All of the non-bias burden then falls on the method for 
> assembling the districts.  Census tracts are excellent for unbiased, 
> unmanipulatable methods.  I would argue that the most unbiased, 
> unmanipulatable methods are those based purely on abstractions such as 
> geometry as exemplified by district compactness.  The issue then 
> becotmes one of whether or not a gerrymander resistent result is 
> sufficient or a bias free result is more important.  You argue in 
> favor of the bias of respecting "natural communities" which I think is 
> an ill-defined concept.  You also argue in favor of maintaining 
> stability across re-districtings.  Here we agree - people do want 
> predictability and that is lost if districts change substantially 
> every ten years.

I agree. Those are fundamentally political issues, rather than 
technical, so there's no well-defined answer.  Does anyone know of 
places that have proposed automated districting, and what the public 
(and politician) response has been?

> If database format electronic versions of historical census district 
> maps are freely available in a then it would be possible to run an 
> experiment and see how much the districts change every ten years using 
> compactness optimization hueristics.  This could then be compared with 
> road count minimization for stability of districts, but you would then 
> also need the road information in the map database.  Do you know how 
> to represent map information like that in a data structure or data 
> base for this purpose?  Do you know if information in such format, or 
> convertable to such a format, is freely available?  If not, are you 
> sure you are prepared to enter such information manually?

I wasn't planning to create an actual database. I  think we could at 
least validate some of the basic notions, and the algorithm, using 
sample data.  Its easy enough to create a list of N nodes, which data 
of the form:

# 113 {size = 15313, weight = {112:4, 114:6, 103:2, 123:7}}

Where each number (e..g,113) is the number of the tract, and weights 
represent the connections between nodes.  We could also assign a 
%Republican/%Democract for each node, to show us whether the resulting 
district has a gerrymandering-bias.

> I believe that compactness optimization and road count minimization 
> optimization could be identical hueristics.  The edges for compactness 
> optimization would be respresented by adjoining perimeter segment 
> length.  If you think you are up to the task of coding such a 
> hueristic I say go for it.  But that isn't an easy task.  I think this 
> task requires optimization modeling training such as graduate degree 
> in Operations Research.  And it will require a substantial investment 
> in time unless you can find some pre-existing models that fit.  It is 
> the sort of project that may  be food for final semester OR graduate 
> students.  And it may require very expensive software to this 
> properly.

It depends on how sophisticated you want to be (and for the record, I 
have a Ph.D. in particle physics).   But I think one could get a fairly 
good algorithm coded in, say, Python with < 50 man-hours of work.  It 
may not be very efficient, but it could at least generate reasonably 
equal districts, and allow us to test gerrymandering ideas.  For 
example, it could answer questions like:

a) Does building new roads change the pattern in any predictable way
b) Does skewing the tracts towards a particular ration affect the 
overall gerrymandering
c) If 'heavily-weighted nodes' (probably urban) vote a particular way, 
does this generate manipulable bias

Of course, none of these technical issues answer what is probably the 
most important question - what are the political criteria needed to 
make such a method acceptable.    Does anybody have historical 
information that would help answer that?

-- Ernie P.