Wow, this proposed approach to drawing districts without gerrymandering is fascinating! In the spirit of "I cut you choose", the proposal is "One party defines 2N equal-population sub-districts, and the other party chooses pairs of adjacent sub-districts to combine, to form N districts."
The analysis in the body of the paper focuses on simulations of each party's optimal strategy in the context of some real-world maps of US voting precincts, while an appendix proves a few theorems giving bounds in the alternate context where the pairs of districts that get combined don't need to be geographically adjacent. (If this idea catches on, I'd bet someone will produce theoretical bounds in the presence of the geography constraint.)
A Partisan Solution to Partisan Gerrymandering: The Define–Combine Procedure
@Log3overLog2 I wonder if a generalization exists for N paper l parties? Can you start with 4N districts, have party 2 combine, then party 3 combine again?
I’m guessing no, since in the extreme case you have log2(population) parties, the “define” party is forced to define 1-person districts and is effectively left out of the process…
@pganssle Problems "like this" get much more complex when there are N>2 players, and indeed even the definition of success is much more subtle. See https://en.wikipedia.org/wiki/Envy-free_cake-cutting and https://en.wikipedia.org/wiki/Proportional_division for an introduction.
But once you're in a political system with more than two parties, you should be thinking about how to move away from winner-take-all districts to multi-member representation and something like https://en.wikipedia.org/wiki/Single_transferable_vote.