[1]: https://static.cambridge.org/content/id/urn%3Acambridge.org%...
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.
The real problem with this strategy is that it accepts self-interested gerrymandering, rather than starting by rejecting it as wrong; immoral; anti-productive.
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".
Of course, the chromatic polynomial is #P-complete, so this may pose some difficulty.
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.
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.