4 ms·

You cut, I choose becomes I choose, you un-cut. Note that this paper contains no optimality proofs. There's a lot of mathy-looking stuff, but then instead of

You cut, I choose becomes I choose, you un-cut. 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.

madcaptenor 3y ago
I haven't digested the paper, but one thing I wonder - does it matter which party goes first?
- iainmerrick 3y ago
  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.
maxpalmer 3y ago
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%3Aid%3Aarticle%3AS1047198723000396/resource/name/S1047198723000396sup001.pdf https://static.cambridge.org/content/id/urn%3Acambridge.org%...
- yorwba 3y ago
  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.
  - crotchfire 3y ago
    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.
  - scythe 3y ago
    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 3y ago
    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.
mrkeen 3y ago
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.

madcaptenor 3y ago

I haven't digested the paper, but one thing I wonder - does it matter which party goes first?

iainmerrick 3y ago
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.

maxpalmer 3y ago

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%3Aid%3Aarticle%3AS1047198723000396/resource/name/S1047198723000396sup001.pdf https://static.cambridge.org/content/id/urn%3Acambridge.org%...

yorwba 3y ago
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.
- crotchfire 3y ago
  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.
- scythe 3y ago
  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 3y ago
  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.

mrkeen 3y ago

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.