Michael C. Chavrimootoo

Michael C. Chavrimootoo, Aidan Jeansonne

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.

Huy Vu Bui, Michael C. Chavrimootoo, Kien T. Le et al.

Much research in electoral control -- one of the most studied form of electoral attacks, in which an entity running an election alters the structure of that election to yield a preferred outcome -- has focused on giving decision complexity results, e.g., membership in P, NP-completeness, or fixed-parameter tractability. Approximability on the other hand has received little attention in electoral control, despite its prevalence in the study of other forms of electoral attacks, such as manipulation and bribery. Early work established preliminary results about popular voting rules such as plurality, approval, and Condorcet. In this paper, we completely determine for each of the "standard" control problems under plurality, approval, and Condorcet, whether they are approximable, and we prove our results in both the weighted and unweighted voter settings.