[maxpalmer]

We have an analytic solution in the supplementary materials [1]. One of the biggest challenges to optimality proofs is how to capture the importance of geography as a constraint. I don't believe there are any papers on redistricting that include geographic constraints in analytic/formal solutions. That's why we prefer simulations for our main results.

[1]: https://static.cambridge.org/content/id/urn%3Acambridge.org%...

[yorwba]

Requiring geometric contiguity allows almost-unchanged gerrymandering through the backdoor.

Here's the Stonewall algorithm to gerrymandering with contiguous Define-Combine:

1. Start by gerrymandering a map with N contiguous districts the usual way.

2. Pick one of the districts to be your "mortar", the others are your "bricks".

3. Shrink all bricks minimally to open gaps between them without changing the population or election outcome.

4. Fill in the gaps with your mortar, so that all bricks are completely enveloped.

6. Split all bricks and the mortar in half, ensuring that one of the mortar halves does not touch any bricks. This gives you your final map of 2N contiguous districts for the second mover to combine.

Then the mortar half that doesn't touch any bricks can only be combined with the other mortar half. And since all bricks are completely surrounded by mortar (which they can no longer be combined with) the second mover can only combine a brick half with the other half of the same brick.

This leads to a map with the same outcome as the original gerrymandered map.

Of course it would be blindingly obvious if anyone actually attempted to do that, but there might be subtler ways to use contiguity to create a forced-choice situation.

[scythe]

That's a clever argument, though I wonder if it would be defeated by some restrictions on the chromatic polynomial. In your example, the number of 3-colorings up to isomorphism is extremely large, because the colors of any brick and its cobrick can be switched, and the mortar condition implies the districts are 3-colorable.

Of course, the chromatic polynomial is #P-complete, so this may pose some difficulty.

[irq-1]

Concentric circles, or pie chart design would be problematic also.

The real problem with this strategy is that it accepts self-interested gerrymandering, rather than starting by rejecting it as wrong; immoral; anti-productive.

[jfengel]

The whole gist of democracy is to start with the assumption that people are immoral and anti-productive. But if we pit them against each other, half of the immoral people will cancel out the other half. It takes only a tiny fraction of informed, intelligent people all arriving at the same solution (because it's correct) to nudge the result in the right way, most of the time.

It would be nice for that to work, because it means that you don't have to overcome the automatic argument of "I'm not immoral and anti-productive, you're immoral and anti-productive". You never have to tell anybody they're wrong or bad. You only have to tell them that they're not in the majority, which is an objective statement.

It would similarly be nice if we could have an objective but blame-free way to resolve the meta-question of electing representatives. Or at least, to have people say to their own partisans, "Hey, this is obviously unfair, could we tone it down a bit?" But the reply is always "If we don't do this unfair thing, the other people will do MORE unfair things, and then it will get even worse".

[crotchfire]

This is a great example of why the paper's methodology is so utterly bogus. A Markov chain algorithm isn't going to come up with strategies like this, but humans certainly will.