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
https://www.cambridge.org/core/journals/political-analysis/article/partisan-solution-to-partisan-gerrymandering-the-definecombine-procedure/B0792DD0A49332944F2AF5FF6828E275
@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.