Note that this paper contains no optimality proofs.
There's a lot of mathy-looking stuff, but then instead of a proof we get "yeah we took this one particular Markov-chain algorithm and had it play against itself and it failed to generate a gerrymander".
If deployed in real life, an immense amount of power -- and therefore money -- will be at stake: certainly more than enough money to hire persons with intelligence equal to or greater than the creator of "the ShotBurst Algorithm" as consultants.
If an optimality proof is not possible, the only alternative is to test using real humans and (very substantial) real rewards.
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.
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.
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.
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.
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".
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.
I believe fair cake-cutting algorithms are up there in terms of runtime complexity. O(n^n^n) or so?
It would be computationally feasible for small numbers, but not if the algorithm requires a human to try strategise and act in its own interest for every single step.
Yes, looks like there's an advantage (they argue only a small advantage) to the first mover:
The defined subdistrict plan selected by the Democrats results in three seats for Democrats and two seats for Republicans. [...] Similarly, if the Republicans move first, then in equilibrium the Republicans win three seats and the Democrats win two seats. Thus [...] under DCP there is only a one-seat difference depending on who draws the define-stage map.
Note that this paper contains no optimality proofs.
There's a lot of mathy-looking stuff, but then instead of a proof we get "yeah we took this one particular Markov-chain algorithm and had it play against itself and it failed to generate a gerrymander".
If deployed in real life, an immense amount of power -- and therefore money -- will be at stake: certainly more than enough money to hire persons with intelligence equal to or greater than the creator of "the ShotBurst Algorithm" as consultants.
If an optimality proof is not possible, the only alternative is to test using real humans and (very substantial) real rewards.