The Cost of Failure: On The Complexity of Recampaigning under Fixed Districts
For computational social choice researchers, this paper formalizes a novel problem of post-redistricting strategy, but the results are primarily theoretical and incremental.
This work introduces and analyzes the computational complexity of 'recampaigning,' where a political party, given fixed districts, strategically places candidates to maximize wins. The study provides interreducibilities, separations, and complexity results for various model variations.
Redistricting efforts have gathered contemporary attention in both popular and scholarly debates, particularly in the United States where efforts to redraw congressional districts to favor either of the two major parties in 12 states -- such as California, Texas, and Ohio -- have captured the public eye. The treatment of redistricting in computational social choice has essentially focused on the process of determining "appropriate" districts. In this work, we are interested in understanding the gamut of options left for the "losing" party, and so we consider the flip side of the problem: Given fixed/predetermined districts, can a given party still make their candidates win by strategically placing them in certain districts? We dub this as "recampaigning" to capture the intuition that a party would redirect their campaigning efforts from one district to another. We model recampaigning as a computational problem, consider natural variations of the model, and study those new models through the lens of (1) (polynomial-time many-one) interreducibilities, (2) separations/collapses (both unconditional and axiomatic-sufficient), and (3) both worst-case and parametrized complexity.