[EM] Impractical districting idea, complexity

[Kristofer Munsterhjelm]

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