Impractical districting idea, complexity
A private post by Forest Simmons made me realize that finding the proper
boundaries for districts given their centers is the same problem as
finding the assignment of voters to candidates in Monroe's method for a
particular winning assembly.
Monroe (the cardinal version) works like this: Each voter rates each
candidate. The quality of some given winning assembly is the sum of
ratings that each voter gives to his assigned winning candidate, under
the following constraints:
- each candidate must be assigned the same number of voters
- this rating sum should be as high as possible.
So we can imagine a bipartite graph with all the voters on the left, the
winning candidates on the right, and we want to pick one edge from each
voter to one of the candidate to maximize the sum of the edge weights
(the ratings), under the constraints given.
But the districting problem is just the same, except we're minimizing
instead of maximizing: let the "rating" of voter x for "winner" y be the
squared distance from person x to center y. We want to assign people to
districts so that the sum of squared distances is minimized, under the
constraint that each district must have the same number of inhabitants.
Since minimization and maximization is equally hard, that means that all
the algorithm results Warren give on
https://rangevoting.org/MonroeMW.html apply to the districting problem.
(Furthermore, the construction doesn't need the metric to obey any sort
of nice property. So if you'd like to make the distance from point x to
y some estimate of the time it would take to walk from x to y, then you
can get naturally-shaped districts... if so desired. Maybe not so
practical for political redistricting, but perhaps if you want to draw
county maps for a fictional country?)
The reduction is better than using linear programming... but it doesn't
help.
If there are k districts and the state population is p, then there are
(p+k) nodes in the graph and m=p*k edges. The complexity of the
assignment algorithm is just about O(p^2k + p^2 log p). The p^2 is the
killer. Suppose we have a population of a million, then p^2 = 1e12. Ouch.
Other stuff/ideas:
https://www.bowaggoner.com/courses/2019/csci5454/docs/approx.pdf gives
the approximation factor for maximum matching with the simple greedy
algorithm of always admitting the person who's closest to some center,
to that center, until everybody's assigned. (But this doesn't have
capacity constraints? I'm not sure?)
https://people.cs.vt.edu/~sharathr/as_match.pdf gives approximate
matching with metric costs, but there's still an n^2 (i.e. p^2) term to
its complexity.
Sampling would seem to be the obvious solution (just look at 1000
people or so), but as I understand it, the population constraints on
districting are exact: districts are not allowed to have even the
smallest difference in populations, which excludes approaches based on
randomness.
-km
Kristofer,
In your original "impractical" suggestion, you had a contest to see who
could come up with the best set of district centers. At worst you would
have a few thousand of these to check.
Wouldn't some polytime greedy algorithm make this practical?
El jue., 9 de jun. de 2022 2:41 p. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
A private post by Forest Simmons made me realize that finding the proper
boundaries for districts given their centers is the same problem as
finding the assignment of voters to candidates in Monroe's method for a
particular winning assembly.
Monroe (the cardinal version) works like this: Each voter rates each
candidate. The quality of some given winning assembly is the sum of
ratings that each voter gives to his assigned winning candidate, under
the following constraints:
- each candidate must be assigned the same number of voters
- this rating sum should be as high as possible.
So we can imagine a bipartite graph with all the voters on the left, the
winning candidates on the right, and we want to pick one edge from each
voter to one of the candidate to maximize the sum of the edge weights
(the ratings), under the constraints given.
But the districting problem is just the same, except we're minimizing
instead of maximizing: let the "rating" of voter x for "winner" y be the
squared distance from person x to center y. We want to assign people to
districts so that the sum of squared distances is minimized, under the
constraint that each district must have the same number of inhabitants.
Since minimization and maximization is equally hard, that means that all
the algorithm results Warren give on
https://rangevoting.org/MonroeMW.html apply to the districting problem.
(Furthermore, the construction doesn't need the metric to obey any sort
of nice property. So if you'd like to make the distance from point x to
y some estimate of the time it would take to walk from x to y, then you
can get naturally-shaped districts... if so desired. Maybe not so
practical for political redistricting, but perhaps if you want to draw
county maps for a fictional country?)
The reduction is better than using linear programming... but it doesn't
help.
If there are k districts and the state population is p, then there are
(p+k) nodes in the graph and m=p*k edges. The complexity of the
assignment algorithm is just about O(p^2k + p^2 log p). The p^2 is the
killer. Suppose we have a population of a million, then p^2 = 1e12. Ouch.
Other stuff/ideas:
https://www.bowaggoner.com/courses/2019/csci5454/docs/approx.pdf
gives
the approximation factor for maximum matching with the simple greedy
algorithm of always admitting the person who's closest to some center,
to that center, until everybody's assigned. (But this doesn't have
capacity constraints? I'm not sure?)
https://people.cs.vt.edu/~sharathr/as_match.pdf gives approximate
matching with metric costs, but there's still an n^2 (i.e. p^2) term to
its complexity.
Sampling would seem to be the obvious solution (just look at 1000
people or so), but as I understand it, the population constraints on
districting are exact: districts are not allowed to have even the
smallest difference in populations, which excludes approaches based on
randomness.
-km
Election-Methods mailing list - see https://electorama.com/em for list
info
What would be the best rule to keep bots from overwhelming the suggestions?
El jue., 9 de jun. de 2022 3:58 p. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:
Kristofer,
In your original "impractical" suggestion, you had a contest to see who
could come up with the best set of district centers. At worst you would
have a few thousand of these to check.
Wouldn't some polytime greedy algorithm make this practical?
El jue., 9 de jun. de 2022 2:41 p. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
A private post by Forest Simmons made me realize that finding the proper
boundaries for districts given their centers is the same problem as
finding the assignment of voters to candidates in Monroe's method for a
particular winning assembly.
Monroe (the cardinal version) works like this: Each voter rates each
candidate. The quality of some given winning assembly is the sum of
ratings that each voter gives to his assigned winning candidate, under
the following constraints:
- each candidate must be assigned the same number of voters
- this rating sum should be as high as possible.
So we can imagine a bipartite graph with all the voters on the left, the
winning candidates on the right, and we want to pick one edge from each
voter to one of the candidate to maximize the sum of the edge weights
(the ratings), under the constraints given.
But the districting problem is just the same, except we're minimizing
instead of maximizing: let the "rating" of voter x for "winner" y be the
squared distance from person x to center y. We want to assign people to
districts so that the sum of squared distances is minimized, under the
constraint that each district must have the same number of inhabitants.
Since minimization and maximization is equally hard, that means that all
the algorithm results Warren give on
https://rangevoting.org/MonroeMW.html apply to the districting problem.
(Furthermore, the construction doesn't need the metric to obey any sort
of nice property. So if you'd like to make the distance from point x to
y some estimate of the time it would take to walk from x to y, then you
can get naturally-shaped districts... if so desired. Maybe not so
practical for political redistricting, but perhaps if you want to draw
county maps for a fictional country?)
The reduction is better than using linear programming... but it doesn't
help.
If there are k districts and the state population is p, then there are
(p+k) nodes in the graph and m=p*k edges. The complexity of the
assignment algorithm is just about O(p^2k + p^2 log p). The p^2 is the
killer. Suppose we have a population of a million, then p^2 = 1e12. Ouch.
Other stuff/ideas:
https://www.bowaggoner.com/courses/2019/csci5454/docs/approx.pdf
gives
the approximation factor for maximum matching with the simple greedy
algorithm of always admitting the person who's closest to some center,
to that center, until everybody's assigned. (But this doesn't have
capacity constraints? I'm not sure?)
https://people.cs.vt.edu/~sharathr/as_match.pdf gives approximate
matching with metric costs, but there's still an n^2 (i.e. p^2) term to
its complexity.
Sampling would seem to be the obvious solution (just look at 1000
people or so), but as I understand it, the population constraints on
districting are exact: districts are not allowed to have even the
smallest difference in populations, which excludes approaches based on
randomness.
-km
Election-Methods mailing list - see https://electorama.com/em for list
info
On 6/10/22 12:58 AM, Forest Simmons wrote:
Kristofer,
In your original "impractical" suggestion, you had a contest to see who
could come up with the best set of district centers. At worst you would
have a few thousand of these to check.
Wouldn't some polytime greedy algorithm make this practical?
The complexity I gave is for the algorithm that, given center locations,
provides the optimal districting with these given centers. So every time
someone proposes say, four district centers for a four-district state,
the system has to do O(p^2 * 4 + p^2 log p) operations to draw the
actual districts and figure out how good the proposal is.
Finding optimal centers is harder still.
The most manageable approach would seem to be to find some kind of
approximation to the "given centers, find districts" problem. But it has
to be good enough to preserve desirable properties (e.g. districts not
being disconnected).
The obvious greedy variant is to just sort all the edges by distance
(takes O(pk log pk) time, or p log p if the k is vanishingly small
compared to p), and then go down the list, admitting (center, person)
pairs until the given center is full (which takes O(pk) time). But this
is kinda just a flood fill and could result in failure in pathological
situations - e.g. a linear state with three centers next to each other,
like this
=================+
|
A B C |
=================+
where B flood-fills fast enough to cut C off from A, thus making it
impossible to preserve the population constraint. (The optimal solution
would have a very thin sliver going from B in the direction of A, so
that C would be kind of triangular or banana-shaped. This would indicate
that it's a pretty poor choice of centers.)
There may exist better approximations that are not too slow, but I
couldn't find any and I had to go, so I just tossed some links at the
end of my post :-)
If I'm to investigate the problem further, I also have to find out how
Warren can impose capacity constraints and still use just the ordinary
assignment algorithm. As shown above, the greedy algorithm doesn't
preserve the capacity constraints, but it would (I think) approximately
solve the assignment problem... so perhaps a transformation of the
problem is needed before passing it to the assignment algorithm.
-km
On 6/10/22 1:03 AM, Forest Simmons wrote:
What would be the best rule to keep bots from overwhelming the suggestions?
It's kind of impractical, but perhaps:
- You send a request form to the local authority, from your registered
mailing address (where official documents are sent). - The authority gives you a code that identifies you.
- It then sets the request rate so that it isn't overwhelmed. Say it has
issued a thousand codes and checking the quality of the solution takes a
second. Then any given code has to wait 1000 seconds (around 17 minutes)
before trying again.
If the authority is hostile or the users' privacy needs to be protected,
then it gets more complex (the latter requires blind signatures, the
former is harder still). Not having a registered mailing address (e.g.
homeless) would be a problem too.
(I'm not sure if all states have a concept of a registered mailing
address either, so this scheme would possibly need to be changed to e.g.
showing up at an office or something similar. I'm far from an expert in
American law.)
It's also possible to offload some of the computation to the user. If
the user submits a set of centers and the (center, inhabitant)
assignments, then the optimality of the assignment for the given centers
can be checked in O(kp + p log p) time.
(Checking optimality prevents the users from submitting a gerrymandered
assignment and hoping nobody comes up with a better one by the sum of
squares metric. Not only does the assignment have to be good, but it
must also be the optimal for the given set of centers.)
-km
Kristofer,
It seems to be easier (in the virtual setting) to save the "district"
center's for last.
Start with a singular value decomposition of the scatter plot to get an
ellipsoidal approximation of the ballot distribution.
Make hyperplane cuts perpendicular to the ellipsoidal axes starting with
the longest axis, in such a way that each region so delineated has the same
number of voters, and that the regions are as compact as possible given the
constraint of cutting only perpendicular to the axes.
Then find the best allocation of candidates to districts. If there is a
district with no candidate interior to it, then the representative will
have to be from outside the district. If a representative cannot be
interior to the district she represents, that's not her fault: the problem
is a substantial void without any voter from that region willing to run.
-Forest
El vie., 10 de jun. de 2022 3:12 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 6/10/22 1:03 AM, Forest Simmons wrote:
What would be the best rule to keep bots from overwhelming the
suggestions?
It's kind of impractical, but perhaps:
- You send a request form to the local authority, from your registered
mailing address (where official documents are sent). - The authority gives you a code that identifies you.
- It then sets the request rate so that it isn't overwhelmed. Say it has
issued a thousand codes and checking the quality of the solution takes a
second. Then any given code has to wait 1000 seconds (around 17 minutes)
before trying again.
If the authority is hostile or the users' privacy needs to be protected,
then it gets more complex (the latter requires blind signatures, the
former is harder still). Not having a registered mailing address (e.g.
homeless) would be a problem too.
(I'm not sure if all states have a concept of a registered mailing
address either, so this scheme would possibly need to be changed to e.g.
showing up at an office or something similar. I'm far from an expert in
American law.)
It's also possible to offload some of the computation to the user. If
the user submits a set of centers and the (center, inhabitant)
assignments, then the optimality of the assignment for the given centers
can be checked in O(kp + p log p) time.
(Checking optimality prevents the users from submitting a gerrymandered
assignment and hoping nobody comes up with a better one by the sum of
squares metric. Not only does the assignment have to be good, but it
must also be the optimal for the given set of centers.)
-km
On 6/11/22 6:49 AM, Forest Simmons wrote:
Kristofer,
It seems to be easier (in the virtual setting) to save the "district"
center's for last.
Start with a singular value decomposition of the scatter plot to get an
ellipsoidal approximation of the ballot distribution.
Make hyperplane cuts perpendicular to the ellipsoidal axes starting with
the longest axis, in such a way that each region so delineated has the
same number of voters, and that the regions are as compact as possible
given the constraint of cutting only perpendicular to the axes.
Then find the best allocation of candidates to districts. If there is a
district with no candidate interior to it, then the representative will
have to be from outside the district. If a representative cannot be
interior to the district she represents, that's not her fault: the
problem is a substantial void without any voter from that region willing
to run.
This sounds like a virtual k-tau space version of the splitline
algorithm :-)
-km