<div dir="ltr"><a href="https://arxiv.org/pdf/2107.07083.pdf">https://arxiv.org/pdf/2107.07083.pdf</a><br><div><a href="https://mggg.org/research">https://mggg.org/research</a><br></div><div><br></div><div>Just linking further reading for those interested in quantifying & mitigating gerrymandering.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jun 8, 2022 at 9:09 AM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de">km_elmet@t-online.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I was reading <a href="https://arxiv.org/pdf/1901.04628.pdf" rel="noreferrer" target="_blank">https://arxiv.org/pdf/1901.04628.pdf</a>, which gives an<br>
approximation to hard capacitated k-means clustering (basically,<br>
districting with the constraint that each district population should be<br>
the same).<br>
<br>
On page 4 the authors give a linear program that finds the optimally<br>
compact capacitated clustering by Euclidean distance if the district<br>
centers are given.<br>
<br>
So this suggests the following algorithm: let the legislature (or the<br>
public through a contest) choose k such centers. Solve the linear<br>
program where each point is a person, and then use the assignments to<br>
draw the districts.<br>
<br>
The idea is that the degrees of freedom, the knobs that the legislature<br>
can tweak, are limited to such a degree that gerrymandering becomes very<br>
difficult. For instance, there probably does not exist *any* centroid<br>
assignment that would reproduce the infamous Illinois earmuff district.<br>
<br>
<br>
In practice, this is kind of useless because:<br>
        - while strictly speaking polytime, the linear program has O(kn)<br>
variables (k being the number of districts, n the state population), so<br>
the linear program will be very large for large states,<br>
        - US redistricting is limited to whole zip code regions (if I recall<br>
correctly), while this program would cut across them. Perhaps replacing<br>
individual points with weighted points representing one region each<br>
would both solve this and the previous problem, but I'm not sure that<br>
the resulting problem would be totally unimodular any longer,<br>
        - the legislators probably wouldn't accept it (turkeys don't vote for<br>
Christmas),<br>
        - even if it were implemented, minor parties would still be cracked due<br>
to their diffuse support. PR is the better choice.<br>
<br>
But as a mathematical observation, it's pretty neat!<br>
<br>
-km<br>
----<br>
Election-Methods mailing list - see <a href="https://electorama.com/em" rel="noreferrer" target="_blank">https://electorama.com/em</a> for list info<br>
</blockquote></div>