[EM] A computationally feasible method (algorithmic redistricting)

[Raph Frank]

On Wed, Sep 3, 2008 at 8:35 PM, Kristofer Munsterhjelm
<km-elmet at broadpark.no> wrote:
> If you use a Mercator projected map, you're just hiding the quantization.
> All maps have some distortion, and since the map projection uses
> trigonometric functions, you can just use the Haversine distance directly.
> If you need the precision and an exact measurement of error, you could use a
> rational number class with sine and cosine approximation tables (or Taylor
> series), but I think real error like the Earth not being perfectly spherical
> will get you before the rounding errors do.

True ofc.  However, what I want is that the census bureau provides a
definition of the state.

For each block, there is a population and location.

Similarly, there is a boundary file that defines the boundary as lots
of line segments.

Somebody has to actually collect that info, and there will be errors.
State boundaries aren't actually made up of line segments and
populations are concentrated at the centres of their blocks.

However, once that info is provided, the ideal situation is that there
is a unique solution to the problem.

If you have to change projection, you convert rational numbers into
real numbers.

Hmm, perhaps if the original locations were given in gnomonic, I am
not sure if there would be a need for real numbers, I will need to
think about it (I have memories of a square root being required
somewhere anyway).

Ofc, then the boundary info would be great circles rather than line
segments, which shouldn't be a problem (and is probably more
accurate).

> The surrounding district would score pretty badly on the all-pairs distance
> measure, and also on a similar convexity measure (given as the probability
> of the line between two random points being entirely inside the district, or
> where it is outside of the district, being so only over water or outside of
> the state).

> If it's best, the earlier measures are not adequate to discover it.

Yeah, it is more an aesthetic thing. If there is 2 cities and 3
districts, I think it would be best to have 1 district per city and
the rest as a district.

I am not sure if that can be phrased in maths.

Another thought is that the map must have the shortest sum of
perimeters, but perimeters are weighted by population density.  This
would run lines though low population regions.

> Within limits, of course. If you have districts A, B, and C, next to each
> other, then increasing the size of B will make it "eat into" both A and C.
> Thus altering the size of B (to transfer population from A to B, say) would
> also impact C. Trying to correct this by adjusting C's weight could in turn
> impact a D district (and perhaps A as well, if D borders E which borders...
> which borders Z which borders A).

Right, but the district having its weight adjusted either gains
territory or loses territory, it never ends up gaining some and losing
some elsewhere.

Another interesting point is that if you increase the weight of a
group of districts by the same amount, then it will never result in
any of the districts gaining or losing population from another member
of the group.

I think it should be possible to balance district populations to
within the minimum block size just by modifying the weights, no matter
how they are arranged.

Basically:

1) Set the threshold to the (max population + min population)/2

2) Split districts into 2 groups using 1) as threshold

3) Increase weight of all the low population group's districts by the
maximum (same for each district) amount such that (max-min) increases

4) goto 1)

The method of increasing the weight will depend on how the calculation
is performed.  Either they will all have the same value
added/subtracted from them (if it is an additive weight) or they will
all be multiplied by a constant (if it is a multiplicative weight).

> I did just that today with a toy program that "redistricts" the entire
> world. It does seem to converge, but it's not good enough (to use for
> redistricting purposes) if the courts demand +/- 1 proportionality of the
> districts, as the fryer paper states (footnote 12).
>

Yeah, they are pretty amazing in their accuracy.  If there is an
objective rule, they can comply with it, while still gerrymandering as
effectively as desired.

However, a simple rule probably couldn't match that.  It would have to
be followed by a balancing step.

This would swap border block groups between districts in order to
balance the populations.

> The commission would be more robotic than that. The idea I considered was to
> have the default map drawn in some simple manner - splitline would work.
> Then that map becomes the reference for all future maps in the "contest".
> Any map that doesn't strictly improve all relevant measures with respect to
> the default map is excluded from consideration. That way, the people can be
> sure that whatever happens, the map will be at least no worse than the
> default.

It might be defined as moving block groups from district to district
to balance population.

To replace the current 'champion' your map must

- have equal or better population balance (max pop - min pop)
- have a greater number of residents in the same district as the
original algorithm produced

In most cases, the population imbalance would end up as 1, i.e.
population in the largest district is one greater than the population
in the smallest district.

After that, you would need to try to come up with a solution that
matches the default map as closely as possible.

>
> The maximum change limitation would make sense, since it'd keep the
> districts from wildly oscillating, but if you set the limit too high, the
> districting process may get locked into a local optimum.
>

Well, that idea was assuming that there was a pretty effective and
simple algorithm, but is sometimes made 'stupid' errors.  If you look
at the splitline algorithm results on the rangevoting site, some of
the results have a tiny piece of land across a river as part of an
unconnected district.