[EM] An impractical suggestion for redistricting

Richard Lung voting at ukscientists.com
Sat Jun 11 00:00:22 PDT 2022

```Enid Lakeman said "affirmative gerrymandering" is "an exercise in futility."

Proportion is a purely mathematical concept (equality of ratios) which
has fallen foul of party political prejudice, on all sides.

On 08/06/2022 14:09, Kristofer Munsterhjelm wrote:
> I was reading https://arxiv.org/pdf/1901.04628.pdf, which gives an
> approximation to hard capacitated k-means clustering (basically,
> districting with the constraint that each district population should be
> the same).
>
> On page 4 the authors give a linear program that finds the optimally
> compact capacitated clustering by Euclidean distance if the district
> centers are given.
>
> So this suggests the following algorithm: let the legislature (or the
> public through a contest) choose k such centers. Solve the linear
> program where each point is a person, and then use the assignments to
> draw the districts.
>
> The idea is that the degrees of freedom, the knobs that the legislature
> can tweak, are limited to such a degree that gerrymandering becomes very
> difficult. For instance, there probably does not exist *any* centroid
> assignment that would reproduce the infamous Illinois earmuff district.
>
>
> In practice, this is kind of useless because:
> 	- while strictly speaking polytime, the linear program has O(kn)
> variables (k being the number of districts, n the state population), so
> the linear program will be very large for large states,
> 	- US redistricting is limited to whole zip code regions (if I recall
> correctly), while this program would cut across them. Perhaps replacing
> individual points with weighted points representing one region each
> would both solve this and the previous problem, but I'm not sure that
> the resulting problem would be totally unimodular any longer,
> 	- the legislators probably wouldn't accept it (turkeys don't vote for
> Christmas),
> 	- even if it were implemented, minor parties would still be cracked due
> to their diffuse support. PR is the better choice.
>
> But as a mathematical observation, it's pretty neat!
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info
```