The Cost of Failure: On The Complexity of Recampaigning under Fixed Districts
Pith reviewed 2026-05-22 12:21 UTC · model grok-4.3
The pith
A losing party can sometimes win an election with fixed districts by strategically reassigning its candidates, but determining whether this works is computationally hard in many model variants.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We model recampaigning as a computational problem, consider natural variations of the model, and study those new models through the lens of polynomial-time many-one interreducibilities, separations and collapses both unconditional and axiomatic-sufficient, and both worst-case and parametrized complexity.
What carries the argument
The recampaigning decision problem and its natural variants, connected by polynomial-time many-one reductions that establish equivalence or hardness relationships.
If this is right
- Models that are interreducible share the same complexity status, so an efficient algorithm for one applies to the others.
- Some restricted variants admit polynomial-time solutions while the general versions remain hard.
- Parameterized results identify parameters such as number of districts or candidates that make the problem tractable when small.
- Unconditional separations prove that certain model variants are inherently different in difficulty without relying on unproven assumptions.
Where Pith is reading between the lines
- If the models are realistic, parties facing fixed districts would need approximation methods or heuristics rather than exact optimal strategies.
- The same reduction techniques could apply to related resource-allocation tasks such as targeted voter outreach under fixed boundaries.
- Computational intractability adds a hidden cost to post-loss strategy that compounds the original electoral defeat.
Load-bearing premise
The natural variations of the recampaigning model capture the real strategic placement options available to parties when districts are already fixed.
What would settle it
An explicit polynomial-time algorithm for one of the NP-hard model variants on a non-trivial family of instances would show the claimed hardness does not hold for that variant.
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the recampaigning problem: given fixed districts and a voting rule, a party assigns its candidates to districts to maximize the number of wins. It defines several natural variants of this model and analyzes them via polynomial-time many-one interreducibilities, unconditional and axiomatic separations/collapses, and both classical and parameterized complexity.
Significance. If the variants faithfully capture strategic placement options, the results supply a complexity map of post-redistricting options for losing parties. The explicit use of many-one reductions and FPT analysis is a strength; the work is among the first to treat recampaigning as a distinct computational problem rather than a side-effect of redistricting.
major comments (3)
- [§3] §3 (Model Definitions): the central claim that the variants encode 'natural' strategic options rests on the assumption that candidate-to-district assignment is unconstrained except for the win condition. Residency rules, filing deadlines, and per-district resource limits are omitted; adding any of these would likely invalidate the district-independence exploited in the many-one reductions and FPT algorithms.
- [§5] §5 (Interreducibility Results): the parsimonious reductions between variants A and B (e.g., the construction mapping an instance of one to the other while preserving yes/no answers) rely on the absence of cross-district constraints. If residency or budget parameters are introduced, these reductions cease to be parsimonious and the claimed equivalence may collapse.
- [§6] §6 (Parameterized Complexity): the FPT results for parameter k (number of districts or candidates) exploit independent per-district decisions. The paper does not show that the same parameterization remains FPT once realistic constraints (e.g., total campaign budget) are added; this is load-bearing for the 'cost of failure' narrative.
minor comments (2)
- [Abstract] The abstract lists three analysis lenses but does not name the concrete variants studied; a one-sentence enumeration would improve readability.
- [§3] Notation for the voting rule and win threshold is introduced without a consolidated table; readers must hunt across sections to compare variants.
Simulated Author's Rebuttal
We thank the referee for their constructive comments, which help clarify the scope and limitations of our model. We address each major comment in turn, providing clarifications and indicating where revisions will be made to the manuscript.
read point-by-point responses
-
Referee: [§3] §3 (Model Definitions): the central claim that the variants encode 'natural' strategic options rests on the assumption that candidate-to-district assignment is unconstrained except for the win condition. Residency rules, filing deadlines, and per-district resource limits are omitted; adding any of these would likely invalidate the district-independence exploited in the many-one reductions and FPT algorithms.
Authors: We agree that our model abstracts away from additional real-world constraints such as residency requirements and resource limits. The variants are defined as natural within this abstract framework to isolate the computational complexity of candidate assignment. We will revise Section 3 to explicitly discuss these modeling choices and their implications, noting that extensions incorporating such constraints are left for future work. revision: partial
-
Referee: [§5] §5 (Interreducibility Results): the parsimonious reductions between variants A and B (e.g., the construction mapping an instance of one to the other while preserving yes/no answers) rely on the absence of cross-district constraints. If residency or budget parameters are introduced, these reductions cease to be parsimonious and the claimed equivalence may collapse.
Authors: The interreducibility results hold for the variants as formalized in the paper, which do not include cross-district constraints. We will add a remark in Section 5 clarifying that these equivalences are specific to the current model and may not extend directly to enriched models with additional constraints. revision: partial
-
Referee: [§6] §6 (Parameterized Complexity): the FPT results for parameter k (number of districts or candidates) exploit independent per-district decisions. The paper does not show that the same parameterization remains FPT once realistic constraints (e.g., total campaign budget) are added; this is load-bearing for the 'cost of failure' narrative.
Authors: The FPT algorithms rely on the independence in the current model. We acknowledge that incorporating global constraints like a total budget would change the parameterized complexity landscape. We will include a discussion in Section 6 on how such constraints might affect the results and suggest this as an avenue for further research. revision: partial
Circularity Check
No circularity: standard complexity analysis of a newly defined problem
full rationale
The paper introduces the recampaigning problem as a formal computational model of candidate assignment to fixed districts under a voting rule, then derives interreducibility, separation, and complexity results using standard many-one reductions and parameterized analysis. These steps rely on explicit problem definitions and established proof techniques rather than any fitted parameter, self-referential equation, or load-bearing self-citation that collapses the claim back to its inputs. The derivation chain is self-contained against external benchmarks in complexity theory.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard polynomial-time many-one reductions and complexity class separations hold as defined in computational complexity theory.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.