New Research Reveals Strategic Candidate Placement is Computationally Hard

Researchers Michael C. Chavrimootoo and Aidan Jeansonne from the arXiv paper “The Cost of Failure: On The Complexity of Recampaigning under Fixed Districts” tackle a novel twist in computational social choice: rather than asking how to draw fair districts, they ask what a losing party can do after districts are fixed. They define 'recampaigning' as the problem of strategically placing candidates across predetermined districts to maximize victories. The team models this as a computational problem and analyzes its complexity through three lenses: polynomial-time many-one interreducibilities (showing equivalence to other hard problems), unconditional separations between variants (e.g., when candidate travel costs are considered vs. ignored), and both worst-case and parameterized complexity (revealing that even with natural parameters like number of districts or candidates, the problem remains hard).

The paper systematically evaluates natural variations—such as allowing multiple candidates per district, constraints on candidate resources, and district-specific success probabilities—and classifies each variation's complexity relative to known complexity classes. Their key result: even the simplest recampaigning variant is NP-complete, and adding realistic constraints (like limited campaign budgets or geographic restrictions) pushes the problem into higher complexity classes (e.g., PSPACE). The work also provides fixed-parameter tractable algorithms for certain restricted scenarios (e.g., when the number of parties is small), offering a glimmer of practical use. By flipping the script from redistricting to recampaigning, the authors provide the first formal computational framework for post-districting political strategy, with implications for campaign resource allocation and election modeling.