# [EM] An impractical suggestion for redistricting

Andy Dienes andydienes at gmail.com
Wed Jun 8 06:58:44 PDT 2022

```https://arxiv.org/pdf/2107.07083.pdf
https://mggg.org/research

mitigating gerrymandering.

On Wed, Jun 8, 2022 at 9:09 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220608/d55e646d/attachment.html>
```