An impractical suggestion for redistricting
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
https://arxiv.org/pdf/2107.07083.pdf
https://mggg.org/research
Just linking further reading for those interested in quantifying &
mitigating gerrymandering.
On Wed, Jun 8, 2022 at 9:09 AM Kristofer Munsterhjelm km_elmet@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
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)...
In the UK, constituencies are adjusted by a commission. I don't suppose
it's perfectly fair but in practice the errors it gives rise to are
tolerably small. There's a bigger problem: constituencies are either
rural or urban. If rural constituencies favour party A by a small
majority and urban constituencies favour B by a large majority, then A
has an in-built advantage. I'm not aware of anything in k-means
clustering which guards against this.
Kristofer's final comment was "PR is the better choice". I don't favour
PR but I sympathise with his sentiment: if you're going to judge an
electoral system by the fairness of where it ultimately puts power, then
you're unlikely to get anything satisfactory starting from the design
premise of fairness by constituency, however ingenious your implementation.
CJC
On 6/10/22 12:52 PM, Colin Champion wrote:
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)...
In the UK, constituencies are adjusted by a commission. I don't suppose
it's perfectly fair but in practice the errors it gives rise to are
tolerably small. There's a bigger problem: constituencies are either
rural or urban. If rural constituencies favour party A by a small
majority and urban constituencies favour B by a large majority, then A
has an in-built advantage. I'm not aware of anything in k-means
clustering which guards against this.
It doesn't, no. It replaces engineered biases with natural ones (which
seem to be less severe, e.g. https://arxiv.org/abs/1410.8796).
Any constituency-based majoritarian system has a fundamental limitation
in that it doesn't give parties who have a little representation
everywhere its share of the seats. Presumably better single-winner
voting methods like Condorcet would allow these minor factions to drag
the center in their direction, but it wouldn't give them direct
representation.
You could add a districting step to a Monroe-type multiwinner election
so that it draws "districts" of voters each candidate is accountable to,
after the fact, but I don't really see what the point would be :-)
Imposing the required geographic contiguity constraints would lower the
proportionality of the result, as well.
-km
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