Bias in the ballot: how votemandering exploits gerrymandering and campaign strategies

Abstract

Gerrymandering—the deliberate manipulation of electoral district boundaries for political advantage—is a persistent challenge in U.S. elections. In this work, we introduce and analyze Votemandering, a strategic blend of gerrymandering and targeted political campaigning devised to gain more seats by circumventing fairness measures. Votemandering leverages accurate demographic and socio-political data, bolstered by advancements in technology and data analytics, to influence voter decisions in pursuit of subtle gerrymandering strategies. We formulate votemandering as a Mixed Integer Program (MIP) that performs fairness-constrained gerrymandering over multiple election rounds. We analyze the influence of various redistricting constraints and parameters on votemandering efficacy. We explore the interconnectedness of gerrymandering, substantial campaign budgets, and strategic campaigning, illustrating their collective potential to generate biased electoral maps. A case study of Wisconsin State Senate redistricting reveals significant votemandering potential. Our findings underscore the need for reforms in the redistricting process beyond enforcing thresholds for specific fairness metrics.

1 Introduction

Partisan gerrymandering is the manipulation of voting district lines for political gain. There is significant evidence of gerrymandering in the US electoral history, giving unfair political advantage to various parties in power (Bickerstaff et al., 2020). To detect and quantify gerrymandering, political scientists have devised various fairness measures, some of which incorporate historical voting data. If a proposed district plan has a fairness measure outside of a typical range, or, more robustly, is an outlier to a fairness measure over a sample of feasible plans, this anomaly provides evidence of partisan gerrymandering. However, federal courts have refrained from endorsing proposed fairness measures as gerrymandering litmus tests, indicating a need for further research on the robustness and trade-offs of such tests (Rucho v. Common Cause 2019).

In addition to gerrymandering, political parties seek to enhance their political representation through large campaign budgets (Horncastle, 2020; Evers-Hillstrom, 2021). Although campaigning alone cannot change the party inclinations of voters, it supports the Get Out The Vote (GOTV) cause, increasing voter turnout (Karp et al., 2008; Imai & Strauss, 2011). Recent GOTV campaigns carefully target specific audiences for optimal impact, using advanced data analytics that use voter data (collected through geographical surveys and the available telemetric data) to convey insights into the political inclination of the audience (Zarouali et al., 2020). Once the targets are clear, personalized campaigns are delivered through direct messages or via social media advertisements. Such campaign efforts have been used in both the 2016 and 2020 U.S. presidential elections, where clear evidence of the effectiveness of the advertisements as well as research scrutinizing the implications of presenting the social choice surfaced (Liberini et al., 2020; Brodnax & Sapiezynski, 2022). The implications of such precise campaign efforts become critical, as historical election data (influenced by the campaigns) are often used to judge the fairness of proposed maps. An important research question is examining how strategic campaign approaches can simultaneously affect immediate elections and future redistricting, and help in securing even higher political representation.

This paper aims to investigate the robustness of fairness measures to strategic campaigning and traditional gerrymandering, which we term votemandering. Votemandering is based on the idea that a party can strategically campaign in an election to alter the voting data and then draw a new district plan that appears fair for a fixed fairness measure, but grants them an unfair advantage in the next election. The focus is on identifying patterns of selective and disproportionate modifications to the representation of social choice through voting, to circumvent fairness measures for redistricting. This manipulation can be critical, particularly when minor deviations in election data can lead to significantly different fairness measure evaluations. On this background, the paper seeks to address the following research questions:

• How vulnerable are popular fairness measures to votemandering?

• How might voter turnout levels and political geography exacerbate or thwart votemandering?

• Can careful combinations of fairness measures and legal constraints promote district plans that are more robust to votemandering?

These questions delve into both social choice theory and practical public policy considerations. A significant concern arises when technological advancements enable greater access to detailed data on voters’ preferences and increase the capacity to influence decisions, thus allowing strategic actors to target specific regions in ways that undermine fairness and equity.

We next present a brief description of the problem: Consider two election rounds with a redistricting cycle falling in between. The majority party in the state legislature, referred to as the “majority party," campaigns in the first election, winning the maximum number of seats while simultaneously ensuring they can draw a desired district plan for the second election, which appears fair. Fairness is measured by a metric that uses past election data, such as the Efficiency Gap (EG), which is influenced by campaigning. Assuming complete information about the opponent party’s Get Out The Vote (GOTV) campaign, the goal of the majority party is to maximize the number of seats won in both rounds. We refer to this as votemandering and formulate an optimization framework that identifies the best campaign strategies with the combined objective of securing maximum wins in both rounds and drawing a desired map that remains valid for many years.

Motivated by practical and often legal constraints on redistricting in the US, we further analyze the special case of imposing proximity constraints for the proposed maps. In practice, such justifications come from maintaining the original community boundaries (e.g., retaining majority/minority districts) as well as structural boundaries (e.g., disallowing county splits) while drawing new district plans on the ground. Legally, states often demand that redistricting plans remain close to the existing plan. For example, Nebraska requires the new plan to “preserve the cores of prior districts” (Nebraska, 2021), and the Wisconsin Supreme Court issued a similar “least-change” order for the 2020 cycle (Wisconsin, 2021). Accordingly, we specifically address the least-change criterion in votemandering, calling it local votemandering, and elucidate the key strategies that facilitate it, further connecting those to general votemandering strategies.

Main contributions of this work are as follows:

• 1. We demonstrate that fairness measures can be susceptible to strategic voter-data alteration, leading to an indirect form of gerrymandering, i.e., votemandering. Therefore, the quality of a fairness measure can also be evaluated by its robustness against such strategies. We formally model this phenomenon and discuss the case of EG.

• 2. We show the fragility of district maps concerning votemandering and establish sufficient conditions for a party to benefit from it. We show how campaign budgets and access to opponents’ campaign information facilitate votemandering, high voter turnout and stricter compactness bounds mitigate the impact, and voter clustering patterns have little effect.

• 3. We propose general and proximity-based algorithmic frameworks for evaluating district plans against votemandering, providing computationally efficient votemandering solutions. Our work is applicable to real-world data, as we demonstrate on the case studies.

Our work connects to a rich body of literature from the perspectives of economics, game theory, optimization, and statistics, starting with the theory of social choice, which examines how individual preferences or votes translate into collective social decisions (Sen, 1986). Our work extends this field by exploring how strategic campaigning can influence political redistricting. Notably, prior studies have established that no multi-player voting system is immune to strategic manipulation (Gibbard, 1973; Satterthwaite, 1975), with some voting rules being identified as particularly vulnerable (Bartholdi et al., 1989).

Plurality voting, a specific domain within voting systems, has been examined from a computational perspective in previous research. This includes exploration of gerrymandering and the challenges it presents (Apollonio et al., 2009; Cohen-Zemach et al., 2018; Ito et al., 2021), geographic manipulation of borders (Lewenberg et al., 2017; Eiben et al., 2020), and influence of information networks on voting outcomes (Stewart et al., 2019). Additionally, the strategic movement of agents and resource allocation for campaigning have been modeled and studied (Lev & Lewenberg, 2019; Behnezhad et al., 2018; Macdonell & Mastronardi, 2015; Behnezhad et al., 2017).

The fairness of district plans is widely researched, due to its legal and societal implications (Swamy et al., 2023; Landau et al., 2009; Chikina et al., 2017; Benadè et al., 2021; Royden & Li, 2017; Court, 2022);?. In light of this, our study proposes a new evaluation criterion that links voting mechanisms and the fairness of district maps to the broader issue of social choice in relation to redistricting.

The potential for manipulating fairness measures is an issue in the field of algorithmic game theory (Adsul et al., 2010; Brânzei et al., 2017; Babaioff et al., 2021). Our work is philosophically the closest to Brubach et al. (2020), which delves into the influence of fairness measures on voting strategies, considering the implications of indirect manipulation via selective vote-updates. Moreover, in line with our exploration of local votemandering, Yablon (2022) examines the scenario of a majority party stabilizing power by subtle changes to the existing map, effectively disguising manipulations as adherence to the ‘least-change’ principle.

The efficiency gap (EG) measure, used to quantify partisan gerrymandering by calculating wasted votes, has gained recognition due to its simplicity and practical applicability (Stephanopoulos & McGhee, 2015; Court, 2018; Missouri, 2022). However, critiques have highlighted its potential flaws, including the risk of increasing polarization, its restrictive range of values, and susceptibility to peculiarly shaped districts (Bernstein & Duchin, 2017; Kean, 2018; Chambers et al., 2017; Cover, 2018; Cho, 2017; Alexeev & Mixon, 2018; Nagle, 2019; Barton, 2018). We note that the main criticism offered by our work is fundamentally independent of the previous work done on evaluating the EG, and our main focus is on the sensitivity of EG and its susceptibility to getting tricked in the broader context of votemandering.

The remainder of the paper is structured as follows. Section 2 formally defines votemandering, expounding the model. Section 3 builds the methods, and presents main results on the computability and efficiency of votemandering specific to the EG. Section 4 defines and analyzes local votemandering, the variation with the constraint that the new district plan is close to the original. Section 5 explores votemandering sensitivity to state-specific factors and nonpartisan redistricting constraints, and further connects the key local votemandering strategies to global votemandering, shedding light on efficacy. Section 6 applies votemandering to the state senate redistricting in Wisconsin, demonstrating votemandering potential with substantial gains for both major parties. In addition, it dissects the case of Ohio redistricting from the votemandering point of view. Finally, Section 7 concludes and outlines directions for future work.

2 Model

In this section, we formally discuss the votemandering model and its assumptions. Section 2.1 provides an overview with a high-level description of the problem and Sect. 2.2 formally expounds the model. Section 2.3 illustrates the concept of votemandering using an example of a 10x10 grid graph.

2.1 High-level votemandering model

We begin by defining a function, $\mathcal {E}:\mathcal {D}\times \mathcal {V}\rightarrow {\mathbb {N}}$, to determine state-wide election winners. This function maps a district plan, $D\in \mathcal {D}$, and voter data (i.e., electoral preferences of voters), $V\in \mathcal {V}$, to the number of districts won by party A in the election. The election function, $\mathcal {E}$, represents a specific electoral system, such as single-member districts with first-past-the-post voting. While voter data, $V$ may be influenced by factors such as migration and political dialogue, $\mathcal {E}$ is deterministic.

In this framework, partisan gerrymandering involves replacing $D$ with ${\tilde{D}}$ to win more districts, i.e., $\mathcal {E}({\tilde{D}}, V) > \mathcal {E}(D, V)$. Similarly, election campaigning modifies $V$ into ${\tilde{V}}$ to secure more districts: $\mathcal {E}(D, {\tilde{V}}) > \mathcal {E}(D, V)$. Note that election campaigning is generally considered appropriate within the confines of the Federal Election Campaign Act.

Existing approaches to limit partisan gerrymandering involve calculating a fairness measure, $f: \mathcal {D}\times \mathcal {V}\rightarrow {\mathbb {R}}$, and rejecting a district plan $D$ if and only if $f(D, V_{0}) > \delta$. Here, $V_{0}$ represents historical voter data, and $\delta$ is a predetermined threshold. This constraint aims to mitigate the impact of gerrymandering on election outcomes. However, as noted by Brubach et al. (2020), partisan agents may manipulate voter data in one election to make a future gerrymandered district plan appear fair. Let $D_0$ represent the current district plan. The manipulative partisan agent, party A, attempts to solve the optimization problem:

$$\begin{aligned} \begin{array}{ll} \begin{array}{c} \textrm{maximize}\\ {{\tilde{D}} \in \mathcal {D}, {\tilde{V}} \in \mathcal {V}} \end{array} & {\mathcal {E}(D_0, {\tilde{V}}) + \mathcal {E}({\tilde{D}}, V_0)}\\ \textrm{subject to} & {f({\tilde{D}}, {\tilde{V}})}{\le \delta.} \end{array} \end{aligned}$$

(1)

Previous research on elections and redistricting has focused on the effects of either ${\tilde{D}}$, ${\tilde{V}}$, or $f$; specifically, either gerrymandering, strategic campaigning, or fairness constraints. In contrast, this paper investigates the efficacy of votemandering, which combines gerrymandering and past or present campaigning, primarily in opposition to a specific partisan bias measure, such as the efficiency gap (EG). The votemandering framework assumes translation of campaign budgets to improved voter turnout and access to other party’s budget allocation information, although it is fairly robust to overcome small data uncertainties, as discussed in Sect. 5.1.

2.2 Model details and terminology

We now expand upon the high-level votemandering optimization problem (1). We set the electoral system, $\mathcal {E}$, as single-member districts with first-past-the-post voting. Function $f$ here is a fairness measure, such as the EG. We refer to $V_0$ as the original data of historical voting patterns and ${\tilde{V}}$ as the new data resulting from GOTV campaign efforts. The original district plan is $D_0$ and the new district plan is ${\tilde{D}}$. We distinguish between plan and ‘attributed’ map, with the former indicating unit-to-district assignments and the latter collective of both a district plan and unit-level voter data. We now explain Votemandering in the US redistricting context and put forth its assumptions.

Fig. 1

The 4 stages of votemandering: First, $(D_0,V_0)$ is the initial map. Round 1 elections use the original district plan, $D_0$, with new voter data post campaigning ${\tilde{V}}$, labeled as the campaigned map $(D_0, {\tilde{V}})$. Then, redistricting creates the new plan ${\tilde{D}}$, which is ‘fair’ on the new data, ${\tilde{V}}$, i.e., on the votemandered map $({\tilde{D}}, {\tilde{V}})$. Finally, Round 2 elections utilize the new plan, ${\tilde{D}}$, while using the original data, $V_0$, i.e., the target map $({\tilde{D}}, V_0)$

• Consider two political parties: the (state legislative) majority party, A, and the minority party, B, each endowed with predetermined campaign budgets. Both parties compete in two rounds of elections with a redistricting cycle in between. Party A is assumed to oversee the redistricting process, as permitted in many U.S. states (Center, 2022).

• Campaigning is assumed to increase voter turnout via a linear budget-to-vote function, homogenous across units, but is upper-bounded by the total party shares. Consequently, the number of additional wins a party can achieve through campaigning is constrained by the available campaign budget and underlying voter distribution.

• Both parties campaign before Round 1 of elections, leading to ‘new data’ ${\tilde{V}}$ of vote shares. Party A then creates a ‘new plan’ ${\tilde{D}}$, which is fair on the ‘new data’ ${\tilde{V}}$. The Round 2 elections then use ${\tilde{D}}$, while returning to the original data, $V_0$. Figure 1 diagrams and labels each stage of votemandering, specifying the associated plan, i.e., $D_0$ or ${\tilde{D}}$ and voter data, i.e., $V_0$ or ${\tilde{V}}$.

• The return to the steady state, i.e., $V_0$, in Round 2 implicitly assumes party A can precisely match party B’s allocation, negating any increases in voter turnout since redistricting is now over. By examining this narrow time window, our model studies the short-term implications of campaigning, affecting the Round 1 election and the subsequent map-drawing process.

• To find the strategies of the majority party, we fix party B’s budget allocation across all units and consider party A’s optimization problem (1) of maximizing their total wins in both rounds, i.e., $\mathcal {E}(D_0,{\tilde{V}})$ + $\mathcal {E}({\tilde{D}}, V_0)$. This requires that A remains the majority party after Round 1 elections, and is trivially satisfied if the magnitude of the budget spent by both parties is close as A is the majority to begin with.

Assuming the ability to campaign in future rounds, this process provides a baseline estimate for the strategist party’s objectives if ${\tilde{D}}$ is adopted. We do not model campaign strategies in Round 2 to circumvent added complexity and, crucially, to focus on showcasing the ability to manipulate vote shares for creating a desired map while appearing to uphold fairness.

Party A’s GOTV campaign in Round 1 influences its seat-share in both election rounds: directly through wins in the campaigned map, $\mathcal {E}(D_0,{\tilde{V}})$, and indirectly through wins in the target map, $\mathcal {E}({\tilde{D}}, V_0)$. Round 2 wins are critical as the target map remains effective until the next redistricting phase. To address a full redistricting cycle (such as a 10-year period in U.S. elections), the model can be extended by appropriately adjusting the weight of Round 2 wins. Furthermore, the model accommodates the inclusion of aggregated historical data from multiple elections by adjusting the weight attributed to campaign influence.

As pointed out in (19), it is essential to emphasize that votemandering is fundamentally different from both strategic campaigning and gerrymandering due to its interactions between stages and the imposition of the fairness constraint. As Sect. 6 demonstrates on the state senate voter data from Wisconsin, even a modest budget allocation may lead to substantial vote manipulation outcomes, highlighting the strength of strategic campaigning and gerrymandering combined.

2.3 Illustration

We now illustrate the votemandering model. Consider a hypothetical state comprised of a $10 \times 10$ grid of equipopulous counties to be partitioned into $k=5$ districts. We start with the initial map ($D_0, V_0$) given in Fig. 2a. Both parties have close state-wide total vote proportions ($51\%, 49\%$), spread uniformly throughout the map. The baseline voter turnout in each unit is 50$\%$ without any campaign influence, allowing the remaining to be added through GOTV campaigning. In this case of 5 districts, we call a map ‘fair’ if its |EG| (i.e., the metric of efficiency gap; will be formally defined in Sect. 3) is less than or equal to $20\%$ Stephanopoulos and McGhee (2015). Thus, any map proposed by A for the second round (in the redistricting cycle) must have its EG less than $20\%$.

Fig. 2

Initial map and the proposed map for Round 2. The initial map has EG $7.2\%$ and its party A and B votes shares for each unit are given in red and black color, respectively. Party A wins in 3 districts, made of units marked with ‘A’. The Votemandered map is proposed by Party A, after Round 1 elections and strategic campaigning. It has EG of $19.5\%$, and A wins in 4 districts. The chosen plan retains many unit-to-district assignments from the original plan, i.e., the two plans are not drastically different from each other

Fig. 3

Investments as seen on both plans: See that A majorly invests in the districts it was already winning in the initial map. It also invests a sufficient budget in the districts it initially loses on. This investment is clever: there is no investment in the units that are part of the losing districts in the target map. The budget is allocated in such a way that we win that district (top-right positioned) in Round 1 elections and we again lose it in the target map as well as the votemandered map (after redrawing its boundaries). All investment then becomes a part of the winning districts in Round 2, according to the new plan

Fig. 4

Both round results: In the target map (using original vote shares), A loses in one district and the map attains an EG equal to $28\%$, although the proposed votemandered map (using updated vote shares) got an acceptable score of $19.5\%$. This demonstrates that A can successfully votemander by using strategic campaigning to claim fairness for the votemandered map, while simultaneously winning all 5 seats in Round 1 elections (i.e., campaigned map) and 4 seats in Round 2 (i.e. the target map)

If party A does not plan strategic campaigning or propose a different plan in Round 2, it would win 3 seats in each round, making a total of 6 wins in two rounds. To maintain the EG fairness in its proposal, A needs to lose in at least one district. A may then choose to propose the plan ${\tilde{D}}$ in Fig. 4b, leading to 4 wins in Round 2. However, the EG of ${\tilde{D}}$ using the original vote shares $V_0$, i.e., that of the target map (${\tilde{D}}, V_0$) is $28\%$, making it an unfair proposal. In this case, votemandering allows A to simultaneously advance Round 1 elections, and show fairness of its desired plan.

Using strategic campaigning on $D_0$, A first wins 5 seats in Round 1 (campaigned map $(D_0, {\tilde{V}})$), proposes new plan that is fair on the new data (votemandered map $({\tilde{D}}, {\tilde{V}})$ with EG $\le 20\%$), and wins 4 seats in Round 2 (target map $({\tilde{D}}, V_0)$). We illustrate the strategy implemented by A via Fig. 3. The final results for both rounds can be seen in Fig. 4. In this example, party B adds zero extra votes through campaigning. This is done to illustrate only the effect of A’s campaigning on the election results and the proposed plan for Round 2; party B’s campaigning has a different type of effect on votemandering that we discuss in Sect. 5.

This example shows that using a budget of 250 for a state with a total voter population 5000, i.e., by influencing just $5\%$ of the total voter population, A can successfully votemander by winning 9/10 seats in two rounds, as opposed to 6 without strategic campaigning. Extending this approach to multiple election rounds within a redistricting cycle would lead to starker differences.

3 Methods

The votemandering model motivates an optimization framework for exploring potential campaign and redistricting strategies for party A. Consequently, we translate (1) into an optimization problem (MIP), and detail the entire formulation as (19) in Appendix B.1. Given a fair initial map, the MIP finds the optimal campaign allocation for the strategist party, as well as a fair new district plan, while maximizing the overall objective of wins in two election rounds, which is extendable to any number of rounds.

Although (19) gives an exact solution, solving the optimization framework becomes computationally challenging due to its complex map-making constraints and the combinatorial explosion of the district plans. For most fairness constraints, an exact approach is only feasible for small-sized grids. The complexity arises from the interplay between the four votemandering stages. Campaigning decisions depend on the first and third stages (the initial and votemandered maps), whereas the objective depends on the second and fourth stages (the campaigned and target maps). Additionally, the framework accounts for the budget, voter turnout, and feasible map-making constraints such as contiguity and population balance.

To address this complexity, we develop an efficient heuristic approach by breaking the problem into two parts: find a district plan ${\tilde{D}}$ that satisfies the map-making constraints, then optimize Round 1 wins while maintaining the fairness of the votemandered map. For a fixed district plan, the MIP (19) now reduces to finding Round 1 optimal allocation for the strategist party while maintaining feasibility, if possible. This creates a general global framework for testing the vulnerability of electoral district maps against votemandering–a higher objective, tested against an extensive pool of maps, would imply a higher fragility of the map towards votemandering.

In the remaining section, we present the efficiency of votemandering, both computationally and theoretically. First, Section 3.1 builds the two-stage heuristic approach to find votemandering objectives. We next establish the efficiency of this heuristic in Sect. 3.2, with EG as our fairness metric, leading up to a global votemandering framework for assessing votemandering efficacy. Section 3.3 then examines the impact of campaigning on fairness and votemandering objectives. We show that votemandering, as obtained via (19), is guaranteed under specified conditions.

3.1 A sampling-based global votemandering heuristic

A brute-force method of checking all possible new plans ${\tilde{D}} \in \mathcal {D}$ is computationally infeasible due to the size of $\mathcal {D}$, i.e., the combinatorial explosion of possible redistricting plans. Instead, sampling is used to reduce the new plan search space from the set $\mathcal {D}$ of all district plans satisfying nonpartisan redistricting constraints to a smaller pool of district plans, denoted as $\mathcal {P}\subset \mathcal {D}$. To quickly sample a small but diverse pool $\mathcal {P}$, we may use the popular Recombination Markov chain (DeFord et al., 2021). The proposed algorithm considers each prospective plan in $\mathcal {P}$ according to a priority order, stopping when a pool-optimal plan, $D^*$, is found. The optimal solution within the pool may not be unique, and experiments suggest a large number of pool-optimal plans exist. The number of wins for party A in $D^*$ with the original data, $\mathcal {E}({\tilde{D}}, V_0)$, is a valid lower bound on the global optimum across all of $\mathcal {D}$. Although Recombination sampling may miss optimal new plans, this two-stage heuristic is tractable for typical instances, such as U.S. states. It provides practical solutions that effectively utilize votemandering strategies and show measurable improvements in the number of seats won (Sect. 6).

Let $\mathcal {P}\subset \mathcal {D}$ be a pool of prospective new plans, expressed as $\mathcal {P}\equiv \left\{ D_1, D_2, \ldots, D_{|\mathcal {P}|} \right\}$. The choice of new plan $D_i$ combined with the original voter data $V_0$ determines the number of wins in the target map, $\mathcal {E}\left( D_i, V_0 \right)$. Hence the best new plan for A can be determined by finding, for each plan $D_i \in \mathcal {P}$, the maximum number of Round 1 wins for A by spending budget ${\mathcal {B}}^A$ such that the votemandered map ($D_i, {\tilde{V}})$ fools the fairness constraint. By decoupling the Round 1 and Round 2 contributions to the objective function of our MIP in (19), the heuristic efficiently returns the optimal new plan from the pool. Algorithm 1 provides a high-level description of the heuristic.

Algorithm 1

Votemandering Heuristic: Select Optimal Plan from a Pool

Proposition 1

Algorithm 1 returns a district plan in $\mathcal {P}\equiv \left\{ D_1, D_2, \ldots, D_{|\mathcal {P}|} \right\}$ that, when used for the votemandered and target maps, maximizes the total number of wins for party A across the two election rounds.

Proof

Algorithm 1 is an explicit loop over all prospective plans in $\mathcal {P}$. For each plan $D_i$, Line 9 computes the optimal objective value of (19) when $D_i$ is used. The $\texttt {best\_plan}$ variable maintains the prospective plan with maximum objective value, $\texttt {best\_obj}$best_obj, among plans considered so far.

It remains to prove the correctness of the termination condition in Line 6. The objective of (19) decomposes into Round 1 wins in the campaigned map, (defined as $s^1 \equiv \sum _{i \in K} {\hat{s}}_{i}^{1} \equiv \mathcal {E}(D_0, {\tilde{V}})$), and Round 2 wins in the target map, (defined $s^2 \equiv \sum _{i \in K} {\hat{s}}_{i}^{2} \equiv \mathcal {E}({\tilde{D}}, V_0)$). Fixing ${\tilde{D}} = D_i$ determines $s^2$ (via the $z_{ik}^A$ district assignment variables in (19)), while $s^1$ varies based on budget allocation variables ($b_k^A$). The value of q in Line 3 represents the maximum number of additional districts that party A can win in Round 1 using budget ${\mathcal {B}}^A$. It is obtained by removing the fairness constraints from (19) and optimizing only for additional Round 1 wins. Thus, $\mathcal {E}\left( D_0,V_0 \right) + q$ upper-bounds the total possible Round 1 wins $s^1$ for any plan $D_i$.

Suppose the loop in Algorithm 1 terminates in iteration j with $\texttt {best\_plan} = D_{i^*}$ for some $i^* < j$. For any $\ell \in \left\{ j, j+1, \ldots,|\mathcal {P}| \right\}$, the maximum objective value using new plan $D_\ell$ is

$$\begin{aligned} s^2 + \max _{\left\{ b_k^A \right\} _k: \text { feasible in (19) with } D_\ell } \left( s^1 \right)&\le \mathcal {E}\left( D_0,V_0 \right) + q + s^2\\&= \mathcal {E}\left( D_0,V_0 \right) + q + \mathcal {E}\left( D_\ell, V_0 \right) \\&\le \mathcal {E}\left( D_0,V_0 \right) + q + \mathcal {E}\left( D_j, V_0 \right) & \text {(by sorting of}\ \mathcal {P})\\&< \texttt {best}\_\texttt {obj} & \text {(by Line 6)}\\&= s^1_{i^*} + \mathcal {E}\left( D_{i^*}, V_0 \right). \end{aligned}$$

Hence none of the prospective plans omitted from consideration by loop termination could achieve a larger objective value for (19) than $\texttt {best\_plan}$. This completes the proof of Proposition 1. $\square$

3.1.1 General framework for votemandering check

Algorithm 1 finds an optimal solution within a pool of target maps. In practice, the algorithm is efficient (as we will show in Theorem 1), and the returns diminish as the size of the pool increases. One may question the probability that a globally optimal solution exists within a pool generated by running a Recombination chain for $|\mathcal {P}|$ steps. However, given the difficulty of finding a globally optimal solution, a bound on this probability is unlikely to be determined.

As algorithm 1 works given any inputs of the initial map and campaign budget, it establishes a general framework that can be used to test the robustness of any district plan or pool of maps against votemandering. This framework is used in later sections to compare the effects of various state characteristics and external redistricting conditions on votemandering. An ideal map would have a lower objective when tested against a wide pool of target maps, e.g., a pool generated via the recombination procedure, satisfying the redistricting requirements of the electoral region. The higher the budget required to votemander, the better the robustness, and lower the fragility.

We now detail the computations involved in this framework. The main computational effort in Algorithm 1 occurs in Line 9. With the target map fully determined, the objective of (1) simplifies to maximize the campaigned map (Round 1) wins over all possible budget allocations while maintaining the fairness of the votemandered map. We call Line 9 the fairness step, as it focuses on maximizing wins while ensuring plan $D_i$ appears fair as the votemandered map. Henceforward, we use a specific fairness measure, the efficiency gap (EG), which we formally define in Eq (3). We next expound on the simplified version of the optimization framework solved with the fairness step specific to EG.

3.1.2 Incorporating EG into the Fairness Step

Let plan ${\mathcal {I}} = \{I_1,..I_{n}\}$, written as the set of districts, be the original plan (Round 1) such that each district $I_i$ is a set of units from K. Sets $I_i$ satisfy $I_i \cap I_j = \emptyset$ as no unit can belong to two districts in any round. Let ($V_{0,I}^{A}$, $V_{0,I}^{B}$) and (${\tilde{V}}_{I}^{A}$, ${\tilde{V}}_{I}^{B}$) denote the number of pre-campaign votes, i.e., from original data $V_0$, and post-campaign votes, i.e., from new data ${\tilde{V}}$, respectively, in district I. Thus, ${\tilde{V}}_{I}^{A}$ equals $V_{0,I}^{A} \ +$ campaign added votes in district $I \in {\mathcal {I}}$. Similarly, ${\mathcal {J}}= \{J_1,..J_{n}\}$ be the new plan (Round 2), with ($V_{0,J}^{A}$, $V_{0,J}^{B}$) and (${\tilde{V}}_{J}^{A}$, ${\tilde{V}}_{J}^{B}$) denoting pre and post-campaigning votes in district $J \in {\mathcal {J}}$. Let ${\hat{x}}_{I_i}$, indexed using sets $I_i \in {\mathcal {I}}$ and ${\hat{y}}_{J_j}$, indexed using sets $J_j \in {\mathcal {J}}$ be the indicator variables denoting the wins in the campaigned map (Round 1) and the votemandered map (Round 2), respectively.

The Efficiency Gap (EG) measures the fairness of a district plan ${\mathcal {I}}$ by comparing the difference in wasted votes—votes that are either for losing candidates or excess votes for winning candidates—between two parties, normalized by the total votes cast. Let ${\mathcal {W}}$ represent the difference in wasted votes between party $B$ and party $A$. For a given voter dataset $V_0$ and district $I$, this difference is expressed as ${\mathcal {W}}_{I, V_0}$.

$$\begin{aligned} {\mathcal {W}}_{I, V_0}= {\left\{ \begin{array}{ll} \frac{3V_{0,I}^{B} - V_{0,I}^{A}}{2}, & \text {if } V_{0,I}^{A} > V_{0,I}^{B}\ (A\ \text {wins})\\ \frac{V_{0,I}^{B} - 3V_{0,I}^{A} }{2}, & \text {if } V_{0,I}^{A} < V_{0,I}^{B}\ (B\ \text {wins})\\ \end{array}\right. } \end{aligned}$$

(2)

Using this definition, we write the constraint of EG being less than a particular constant, such as $8\%$, as suggested by Stephanopoulos and McGhee (2015). Let ${\mathcal {W}}_{{\mathcal {I}}, V_0} = \sum _{I\in {\mathcal {I}}} {\mathcal {W}}_{I, V_0}$ be the total difference in wasted votes between party B and A, for plan ${\mathcal {I}}$.

$$\begin{aligned} \text {EG}({\mathcal {I}}) = \left| \left( \sum _{I\in {\mathcal {I}}} {\mathcal {W}}_{I, V_0}\right) / \left( \sum _{I\in {\mathcal {I}}} V_{0,I}^A+V_{0,I}^B \right) \right| = \left| {\mathcal {W}}_{{\mathcal {I}}, V_0} / \left( \sum _{I\in {\mathcal {I}}} V_{0,I}^A+V_{0,I}^B \right) \right| \le 0.08 \end{aligned}$$

(3)

Incorporating EG as the fairness step leads to a simpler MIP formulation that solves Line 9 ensuring the fairness of the votemandered map. The MIP is described in Appendix B.2.

3.2 Computational efficiency

We now establish the complexity of the votemandering heuristic. It takes a pool of maps $\mathcal {P}$ and budget ${\mathcal {B}}^A$ as inputs, and outputs the target map in $\mathcal {P}$ maximizing the votemandering objective with respect to the given initial map, i.e., it finds the target map with the maximum votemandering bonus. Proposition 1 establishes that Algorithm 1 converges to the optimal target map within the defined constraints. Theorem 1 demonstrates that the votemandering heuristic operates efficiently for the given problem space.

Theorem 1

Let $\mathcal {P}$ be a pool of feasible, but not necessarily fair, n-district plans. In the initial map, let q be the maximum number of additional districts that can be won using ${\mathcal {B}}^A$. A plan in $\mathcal {P}$ that maximizes the votemandering bonus may be found in $poly (|\mathcal {P}|, n^{q})$ time.

Proof

See Appendix B.3. $\square$

While the time complexity is $O(n^{q})$, where q is the maximum number of additional districts a party can win using its GOTV budget, it is important to note that q is typically small in practical scenarios. For q to be large, it would require both a significantly higher budget and a scenario where voter turnout leaves substantial room for improvement.

3.3 Sufficient conditions for votemandering

We first analyze the strategy space of party A, which can add new votes to the units via campaigning in Round 1 and/or effectively gerrymander to shift votes from a winning (W) district to a losing (L) district or vice versa. We discuss these key effects in Lemma 1 and build over these to derive sufficient conditions for votemandering in Theorem 2.

Lemma 1

Given any district plan ${\mathcal {I}}$ with voter data V, campaigning and vote shifts impact the total difference in wasted votes (${\mathcal {W}}$), as shown in Table 1.

Table 1 Impact of Campaigning and Vote Shifts on the Difference in Wasted Votes (EG)

Proof

See Appendix B.4. $\square$

We now examine the total impact on the change in wasted votes, i.e., ${\mathcal {W}}$, as a new district plan is drawn over the same voter data: As the total number of votes does not change, the change in ${\mathcal {W}}$ can be tracked through a reshuffle of units into winning and losing districts. For district plan ${\mathcal {I}}$, the difference between the wasted votes ${\mathcal {W}}_{{\mathcal {I}}, V_0}$ is

$$\begin{aligned} {\mathcal {W}} _{{\mathcal {I}}, V_0}&= \alpha \left( \sum _{I \in {\mathcal {I}}_{V_0}(W)} \frac{3V_{0,I}^{B}-V_{0,I}^{A}}{2} \right) + \alpha \left( \sum _{i\in {\mathcal {I}}_{V_0}(L)}\frac{V_{0,I}^{B} - 3V_{0,I}^{A}}{2} \right) \nonumber \\&= \alpha \left( \sum _{I \in {\mathcal {I}}} \frac{V_{0,I}^{B}-V_{0,I}^{A}}{2} \right) + \alpha \left( \sum _{i\in {\mathcal {I}}_{V_0}(W)}V_{0,I}^{B} - \sum _{I\in {\mathcal {I}}_{V_0}(L)}V_{0,I}^{A} \right) \end{aligned}$$

(4)

where ${\mathcal {I}}_{V_0}(W)$ and ${\mathcal {I}}_{V_0}(L)$ are the sets of winning and losing districts for data $V_0$, respectively. Then, after reshuffling to district plan ${\mathcal {J}}$, the change in ${\mathcal {W}}$ (defined as $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$):

$$\begin{aligned}&\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0} = \alpha \left( \sum _{J\in {\mathcal {J}}_{V_0}(W)}V_{0,J}^{B} - \sum _{J\in {\mathcal {J}}_{V_0}(L)}V_{0,J}^{A} \right) -\alpha \left( \sum _{I\in {\mathcal {I}}_{V_0}(W)}V_{0,I}^{B} - \sum _{I\in {\mathcal {I}}_{V_0}(L)}V_{0,I}^{A} \right) \end{aligned}$$

(5)

Now, the final ${\mathcal {W}}$ for plan ${\mathcal {J}}$, if campaigning updates $V_0$ to ${\tilde{V}}$, may be derived using Table 1.

$$\begin{aligned}&{\mathcal {W}} _{{\mathcal {J}}, {\tilde{V}}} = {\mathcal {W}} _{{\mathcal {I}}, V_0} + \Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0} + \text {[Wasted votes from campaign additions]} \end{aligned}$$

(6)

To conclude, Eq. (6) exhibits that a campaign budget can be distributed (potentially updating $V_{0,I}^A, V_{0,I}^B$ to ${\tilde{V}}_I^A, {\tilde{V}}_I^B$) to achieve fairness of a target map, given that the distribution also satisfies the budget and voter-turnout constraints. Then votemandering can potentially be achieved through two interdependent ways: (1) (win-now) fixing ${\mathcal {J}}$ and putting appropriate budget to satisfy the fairness bound, whilst benefiting from campaigning in Round 1, and (2) (win-later) designing a target map with ${\mathcal {J}}$ that leads to a higher number of wins in Round 2 (i.e., gerrymandering), but while maintaining the fairness of the votemandered map. To evaluate votemandering efficacy, we define the votemandering bonus ($\Delta$), which quantifies the additional wins achieved through votemandering strategies. For a target plan ${\tilde{D}}$ and campaigning resulting with ${\tilde{V}}$,

$$\begin{aligned} \text {Votemandering bonus } \Delta = \mathcal {E}(D_0,{\tilde{V}}) + \mathcal {E}({\tilde{D}},V_0) - 2 \mathcal {E}\left( D_0,V_0 \right) \end{aligned}$$

(7)

Under this definition, a positive votemandering bonus indicates a successful application of votemandering. We now characterize the sufficient conditions for successful votemandering using the win-later way of improving the objective. Notably, we do not restrict party B’s strategies. A target map must outperform the initial map, and baseline voter turnout must be sufficient for effective GOTV efforts.

Theorem 2

For any voter data $V_0$ and a corresponding fair initial map with district plan ${\mathcal {I}}$, the existence of strategies leading to a positive votemandering bonus for the majority party is guaranteed if both of the following conditions are satisfied:

• 1. A feasible, contiguous district plan ${\mathcal {J}}$ exists leading to a higher number of wins on $V_0$ than the initial map.

• 2. The voter turnout $\alpha$ satisfies

  $$\begin{aligned} \alpha \le 1- \left( \frac{2 \Delta {\mathcal {W}}_{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}}{\sum _{J\in {\mathcal {J}}_{V_0}(W)} \sum _{j \in J} p_j^A} \right), \end{aligned}$$

  where $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$ is the change in the difference between wasted votes from plan I to J with voter data $V_0$, and $p_j^A$ is party A’s total voter population, in the unit j.

Proof

We prove this by achieving fairness of the map with district plan ${\mathcal {J}}$ using a strategic allocation of budget, thereby establishing the existence of strategies. We show this by constructively satisfying equation (6). We provide the details in Appendix B.5. $\square$

In practice, it is generally much easier to votemander than Theorem 2 suggests, as we demonstrate in Sect. 5.1 and through case studies in Sect. 6. However, it becomes difficult under extremal conditions such as near $100\%$ voter turnout and nearly all voters favoring a single party. The win-now way of votemandering, as discussed above, also allows for a positive bonus to be achieved through an increase in wins in the first round, as long as the voter turnout allows for such campaigning to occur in a fair way. The campaigning effects on fairness, as translated from the additional number of wins, can be dissolved in the votemandered map through reorganization of the campaigned map. While the win-now way of votemandering is easier to achieve in practice, its dependence on the particular construction of map ${\mathcal {J}}$ (relative to map ${\mathcal {I}}$) makes it difficult to establish sufficient conditions for a positive votemandering bonus. We construct specific votemandering strategies using the win-now way in Sect. 4.

4 ‘Least-change’ local votemandering

The votemandering methods in Section 3 allow district lines in the target map to deviate significantly from those in the initial map. Inspired by the least-change requirements that states often impose, we now restrict the strategy space of the votemandering party to small changes to existing district boundaries. We explore such strategies using a local votemandering heuristic that conducts a local search within smaller map sections, as presented in Sect. 4.1. The heuristic, implemented through an optimization framework in Sect. 4.2, generates new plans that satisfy local proximity requirements while maintaining global fairness and budget constraints. The heuristic aims to maximize the votemandering objective by identifying key strategies, as detailed in Sect. 4.3. Local votemandering employs deeper local search using the initial map information for achieving a positive votemandering bonus. While local votemandering may achieve a lower votemandering bonus, it is often faster and scales better with expanding state sizes, partly due to its ability to parallelize.

4.1 Local votemandering methods

The local votemandering heuristic generates new target plans by applying small changes to boundaries, or local perturbations, to existing plans between pairs of neighboring districts. These perturbations involve exchanging units between two districts, such as reallocating precincts, while adhering to proximity and redistricting constraints. Unlike the top-down approach in Sect. 3 (i.e., the global votemandering heuristic), this bottom-up approach strategically employs local perturbations to increment the votemandering bonus by one. A district adjacency graph is formed (where nodes = districts), with edges that have a potential positive bonus—containing at least one district with initial status L—assigned weights representing (budget, fairness) costs associated with the perturbations.

The primary objective is to maximize the votemandering bonus by identifying a maximum-sized matching of edges while adhering to budget and fairness constraints. The resulting target plan is created by applying perturbations corresponding to the maximum matching. Matchings are utilized because they enable mutually exclusive perturbations between district pairs.

The new target plan remains similar to the initial plan in terms of unit-to-district assignments, with alterations only involving districts that expect positive bonuses. Since matchings are used, the difference is quantified as, at most, $\frac{n}{2}$ independent recombination steps away from the initial map, where n is the number of districts. The heuristic considers perturbations only between district pairs to avoid the complexity of perturbations within an arbitrary number of districts, to create plans closer to the initial plan, and to maintain the highest improvement ratio over the number of perturbed districts. Although it is technically feasible to generalize the heuristic to consider perturbing three or more districts simultaneously, the current approach focuses on pairs.

Generating bonuses within submaps—regions restricted to two adjacent districts—exposes the functionality of votemandering’s key strategies, as illustrated in Fig. 5. These strategies encompass a first-round win in the campaigned map and either of the second-round wins in the target map: with or without winning in the votemandered map. Depending on the initial map, any of the key strategies could be more cost-effective in terms of budget and/or fairness (or be infeasible). Given cost information about edges, we first formulate an optimization framework that produces the maximum-matching solution and subsequently discuss the formation and cost computation of the key strategies in Sect. 4.3.

Fig. 5

The three key strategies to locally improve the votemandering bonus. The shaded districts show an improvement in the number of wins of the strategist party. All three strategies have different fairness and budget costs, and they form up to 3 edges between every pair of neighbors in the district adjacency graph. The matching over the entire graph picks the optimal edges

4.2 The optimization framework

As illustrated in Section 4.1, the objective is to select the maximum number of mutually exclusive edges while adhering to the budget and fairness constraints. An edge in the optimal solution may correspond to any of the three strategies depicted in Fig. 5, and will have a weight vector informing its budget and fairness costs. We assume the budget ${\mathcal {B}}^A$ is less than the total number of votes that can be added to losing districts via GOTV in Round 1, as a larger budget would trivialize the optimization problem.

Let N represent the set of nodes, i.e., districts, and E denote the set of edges between neighboring nodes, forming a district adjacency graph of the state. Let $E_{i}$ represent a set of edges (corresponding to the strategies in Fig. 5) incident on node $i\in N$, with $\cup _{i \in N}E_i = E$. Let $b_e, f_e$ denote budget and fairness costs associated with an edge e, and let b represent the remaining budget that may be spent to satisfy the fairness constraint. Let $V_0$ also include party $B$’s allocation, which is assumed to be provided. Using Equation (3) and (6), the maximum allowed fairness cost is $\delta = EG \text { (e.g. 0.08)} \times \text { (total votes) } - {\mathcal {W}} _{{\mathcal {I}}, V_0}$, where ${\mathcal {W}} _{{\mathcal {I}}, V_0}$ is the difference between wasted votes for initial map. In other words, the fairness cost $\delta$ gives the maximum change in the difference between wasted votes, i.e. $\Delta {\mathcal {W}} _{{\mathcal {I}}\rightarrow {\mathcal {J}}, V_0}$, that a feasible matching solution ${\mathcal {J}}$ can correspond to. The goal is to select the largest matching, defined as a set of edges without shared vertices. This is achieved through decision variables $x_e$, which are set to 1 if edge $e \in E$ is chosen in the matching.

As budget ${\mathcal {B}}^A$ cannot turn all losing districts into wins, the strategist party may always choose to spend b on losing districts, which contributes a total of 3b/2 to the fairness cost. This is because spending z amount on a losing district has z/2 fairness cost, but 3z/2 when spent on a winning district (per Lemma 1), thus, making 3b/2 as the maximum achievable fairness cost. The MIP formulation for the local votemandering heuristic can then be expressed as:

$$\begin{aligned} \max \ \sum _{e \in E} x_e \nonumber \\ s.t. \, \,&\sum _{e\in E} b_e x_e + b \le {\mathcal {B}}^A \nonumber \\&\sum _{e \in E} f_e x_e - \frac{3}{2}b \le \ \delta \nonumber \\&\sum _{e \in E_{i}} x_e \le 1&\forall i \in N \nonumber \\&x_{e} \in \{0,1\}&\forall e \in E \end{aligned}$$

(8)

Note that (8) is equivalent to finding a maximum cardinality matching with two knapsack constraints. Although (8) is computationally challenging, it significantly simplifies the variable space by discarding unit-specific variables in (19). In practice, the adjacency graph instance has |N| nodes and only those edges with a positive bonus, making the instance sparse and the problem tractable. We provide an example of this heuristic in Sect. C.1 and apply it in the case of Wisconsin in Sect. 6.

4.3 Local votemandering key strategies

As exhibited in (1), securing a win in Round 1 is only possible through budget investment, while winning in Round 2 can only be achieved through target plan design, which considers the original vote shares. A strategist party utilizes the following strategies from Fig. 5 to generate bonuses using its budget and redistricting abilities:

• 1. Strategy-1: Secure a votemandering bonus with an extra win only in the campaigned map, using A’s budget investment. The edge weight vector is of the form: ($b_e,f_e$) = (significant budget, insignificant fairness cost). The main challenge is the budget required to overcome the vote margin in L districts while ensuring the W/L status remains unchanged in the votemandered map.

• 2. Strategy-2: Secure an extra win only in the target map using B’s budget investment. The edge weight vector is: ($b_e,f_e$) = (zero budget, insignificant fairness cost). The challenge lies in finding perturbations that allow B to win in the votemandered map with minimal investment, enabling A to win in the target map using original vote shares.

• 3. Strategy-3: Use boundary perturbations to secure an extra win in the target map while also achieving an additional win in the votemandered map. The edge weight vector is: ($b_e,f_e$) = (insignificant budget, significant fairness cost). The key limitation is the increased fairness cost associated with securing an additional win in the votemandered map.

Other strategies, where A wins in a different set of maps than shown in Fig. 5, may be considered. However, these are expensive and dominated by the key strategies when feasible. For example, winning in both campaigned and votemandered maps incurs significantly higher fairness costs than Strategy-1 while providing the same bonus. Winning in both campaigned and target maps combines strategies 1 and 2, making it less likely than either. Therefore, for practical purposes, we only illustrate the three key strategies here and note the generalization of additional types.

Consequently, up to three edges may exist between any two districts, each associated with a specific weight vector. Strategy-2 is particularly important because it only uses information about party B’s budget and virtually imposes no cost on party A. Appendix C.2 provides more details and exact calculations of edge weights.

To determine the optimal edge weights as inputs for (8), i.e., costs $(b_e, f_e)$ for all three strategies, optimal boundary perturbations must be specified while adhering to redistricting constraints, e.g., contiguity, population balance. To find such perturbations, we may again use the randomized recombination technique. As with the global heuristic, we separate the problems of finding local perturbations and optimizing costs by creating a pool of plausible submaps for each edge.

For each strategy, we can now examine this pool and select the best edge—i.e., the perturbations leading to a new pair of districts with minimal costs. Finally, given a district adjacency graph, we add up to three edges for each pair of neighboring districts, with costs equal to those of the best pairs from the corresponding pool. This local search in submaps is parallelizable, potentially yielding computationally faster results compared to the global heuristic as instance sizes grow. After performing the local search for all edges, the corresponding adjacency graph of the initial map incorporates budget and fairness bounds as variable inputs in the optimization program (8). This overall allows for a targeted approach to votemandering, taking advantage of the information about districts in the initial map.

5 Results and analysis

We now examine the efficacy of votemandering under various conditions. In Sect. 5.1, we experimentally investigate the dependence of various factors on votemandering, such as the budget of Party A and Party B, compactness, voter turnout, and the spacial concentration index Moran’s I. Section 5.2 explores the relationship between local and global votemandering, highlighting the role of key strategies in determining efficacy.

5.1 Factors impacting votemandering

Although the conditions for votemandering may be easily satisfied in practice (Theorem 2), the required budget to ensure a positive bonus can vary. The votemandering objective depends on several factors, including the initial vote share distribution across the state, the initial district plan, and the available campaign budget for parties A and B. Furthermore, it may be influenced by various externally imposed constraints on the redistricting process, such as the Efficiency gap, compactness, the number of majority-minority districts, proportionality, etc. As a result, we opt for a randomized approach, i.e., Algorithm 1, for a pool of maps to examine the dependence on these factors and, in turn, demonstrate the efficacy of votemandering under various conditions. The pool of plans is randomly generated using Recombination and contains plans that all satisfy the externally imposed constraints. We fix a randomly generated vote share distribution across a grid with $20 \times 20$ units such that each unit i has a population $p_i$ uniformly chosen between $350-400$ and party-wise vote shares $(p_{i}^A/p_i, p_{i}^B/p_i)$ between $20-80\%$ for each party. Each feasible map from the pool provides a unit-to-district assignment, mapping the 400 units to 10 districts, with district populations allowed to deviate $1\%$ from the average district population.

5.1.1 Impact of increasing budget

Fig. 6

Party A’s votemandering bonus, with an increase in both budgets: As opposed to a clear steady increase in 6a, increasing ${\mathcal {B}}^B$ does not ensure a steady decrease in the bonus in 6b. The bonus for ${\mathcal {B}}^A=100$ in 6a represents the objective Party A can achieve by strategically using information about Party B’s budget investments while exerting minimal campaigning effort. Figure 6b shows that although increasing ${\mathcal {B}}^B$ may impact Party A’s chances of first-round wins, A may use this information to create better districts in the second round

Figure 6 illustrates how increasing the campaign budget enhances votemandering efficacy. The budget represents the number of additional votes that can be influenced beyond the baseline voter turnout, capped by the total party affiliation shares. Figure 6 plots Party A’s votemandering bonus as the parties increase their budget uniformly. In experiments for Fig. 6a, Party B’s budget ${\mathcal {B}}^B$ is fixed at 400, and Party A’s budget ${\mathcal {B}}^A$ is varied, whereas for Fig. 6b, ${\mathcal {B}}^B$ is varied, and ${\mathcal {B}}^A$ is fixed at 400. Recall that we do not assume any campaigning strategies from Party B. Given any budget allocation of B, if A has access to the allocation information, then the algorithm finds the best strategies for A. Here, we let B invest most straightforwardly, making its budget investment proportional to each unit’s population, allowing fractional investments.

Figure 6a shows a steady increase in the bonus through the means and medians shifting upwards with the increase in ${\mathcal {B}}^A$. Note that the increase in bonus in Fig. 6a is not linear. Improving the allowed budget has diminishing returns in the form of objectives. This is expected since the objective, and therefore the bonus, is capped by the total number of seats available in both rounds.

Most interestingly, the bonus has a counterintuitive relation with increasing ${\mathcal {B}}^B$ as shown in Fig. 6b, as A uses B’s budget allocation to better redistrict. This is achieved by letting Party B win some districts in the votemandered map, only to lose those in the target map as the campaign effects diminish. Because of this trade-off, the decreasing trend is not obvious: Party A’s votemandering bonus remains largely unaffected until ${\mathcal {B}}^B$ reaches 500.

5.1.2 Impact of increasing compactness

The compactness metric aligns with the idea of creating districts that minimize the physical distance between units within a district. The salamander-shaped district in the first gerrymander suggested rejecting freehand-shaped districts and asking for compactness as a proxy for partisan neutrality (Polsby & Popper, 1991). Yet the consideration of internal community-wise or geographic features (for example, the requirement to respect pre-existing political subdivisions, i.e., counties and voting precincts as with 44 states in the US), is often used to justify oddly shaped districts (Chambers & Miller, 2013). Although some literature suggests that compactness is orthogonal to fairness measures (Gurnee & Shmoys, 2021), we demonstrate that imposing tighter compactness bounds limits the ability of votemandering. This leads to fairer and more robust maps in general. We achieve this by comparing votemandering objectives on two separate pools of plans, generated through Recombination: one with looser and one with tighter compactness constraints. Compactness is measured by the number of cut-edges in a state’s unit adjacency graph, with fewer cut-edges indicating higher compactness, following (DeFord et al., 2021). A cut-edge is an edge with endpoints belonging to different districts. For instance, a $20\times 20$ grid graph with each district composed of two adjacent columns — making 10 districts overall — will have $9\times 20=180$ cut-edges. To show the effects of compactness, the first pool has the maximum number of cut-edges equal to $2 \times 180 = 360$, and the second pool has a bound of $0.75\times 180 = 135$ cut-edges.

Figure 7 presents results demonstrating that more compact districting plans correlate with fewer seats gained through votemandering. The insights into how compactness affects votemandering strategies are further explored in Sect. 5.2. Note that Fig. 7 compares votemandering objectives, as opposed to bonuses shown in Fig. 6, as here two different pools are used, which also significantly affects the distribution of wins in the initial maps, and thereby the bonuses.

Fig. 7

Higher compactness lowers Party A’s votemandering objective: Per Lemma 1, investing in a losing district is thrice as effective in achieving fairness compared to campaigning in a district already inclined to win. This motivates campaigning in targeted units and then reassigning them to losing districts as an advantageous strategy to circumvent fairness. However, compactness constrains this approach by limiting arbitrary district shapes, thereby reducing the ability to target specific units for campaign and reassignment

5.1.3 Impact of voter turnout

Fig. 8

Increase in A’s votemandering bonus with voter turnout: An increase in $\alpha$ provides less flexibility to votemander, as it more accurately represents the true vote share, putting less weight on the campaigned votes and limiting their effectiveness

Intuitively, the ability to votemander is a function of how efficiently and thus also, how disproportionately we can allocate budget across the units. The parameter $\alpha$ captures the voter turnout in elections. The selective campaigning by a strategist adds more party votes, bounded above by the total vote share of that party in every unit. Thus, increasing $\alpha$ makes it difficult to votemander, as we show in Fig. 8 where we plot the votemandering bonus with respect to increasing $\alpha$. With both the means and medians shifting downwards with increasing $\alpha$, this demonstrates that a higher voter turnout supports a better representation of social choice through not only higher volume and election credibility but also through disallowing political parties to votemander.

5.1.4 Impact of spatial autocorrelation of voters (Moran’s I)

Fig. 9

Votemandering bonus with increasing Moran’s I: This illustrates that clustering of this data (as captured by Moran’s I) does not have a very significant effect on the votemandering bonus. The insensitivity of the votemandering bonus to variations in Moran’s I support the experimental design decision of keeping Moran’s I near zero when varying the other redistricting factors in Sects. 5.1.1, 5.1.2, and 5.1.3

One may question if the current experimental setting of a geographically uniformly spread voter population is reasonable, as we often see clusters of societies divided across political and geographic lines. To demonstrate the effects of clustering, we use a popular spacial auto-correlation metric called Moran’s I (Duchin & Walch, 2021). This is a measure of the overall clustering of the spatial data. For $(v_1,..v_K)$ as the vector of vote shares for |K| units, ${{\bar{v}}}$ as the average vote share, $y_{ij}$ as a binary variable indicating adjacency of units i, j and $Y = \sum _{i,j}^{|K|} y_{ij}$ as the number of total adjacencies, Moran’s I is defined as

$$\begin{aligned} I = \frac{|K|}{Y} \frac{\sum _{i=1}^{|K|} \sum _{j=1}^{|K|} y_{ij} (v_i-{{\bar{v}}}) (v_j-{{\bar{v}}})}{\sum _{i=1}^K (v_i-{{\bar{v}}})^2} \end{aligned}$$

(9)

Moran’s I is usually used to measure the segregation of geospatial data and it varies between [$-1,1$] with -1 indicating anti-segregation, 0 with no segregation, and 1 with extreme segregation. The randomly generated voter patterns used in Sect. 5.1.1, 5.1.2, and 5.1.3 produce Moran’s I values in the range $(-0.01, 0.01)$. For the current set of experiments, we generate voter distributions with varying Moran’s I values, group those into nine bins, and plot the votemandering bonuses in Fig. 9. Note that the overall party vote-shares are kept around the same value while increasing the clustering of data.

In summary, campaign budgets affect the votemandering bonus, but with diminishing marginal improvements. High voter turnout and stricter compactness bounds curtail votemandering effectiveness, while voter clustering patterns have little impact. Moreover, these factors together establish the robustness of votemandering objectives to smaller uncertainties in voter data: For the strategist party, assuming base voter inclinations at the lower end of their confidence intervals when devising votemandering strategies provides a conservative practical estimate. While access to the opposing party’s budget allocation information is essential, its slow rate of effect on the votemandering objective—whether uniformly decreased or increased—means that stochastic information can still be useful.

5.2 Efficacy via key strategies

We next detail the thread between local and global votemandering and elucidate the efficacy of votemandering with respect to the key strategies. To do so, we first decompose the votemandering bonus, $\Delta$, into three components (Equation 10).

$$\begin{aligned} \Delta&= \mathcal {E}(D_0,{\tilde{V}}) + \mathcal {E}({\tilde{D}},V_0) - 2 \mathcal {E}\left( D_0,V_0 \right) \nonumber \\&= [\mathcal {E}(D_0,{\tilde{V}}) - \mathcal {E}\left( D_0,V_0 \right) ] + [\mathcal {E}({\tilde{D}},V_0) - \mathcal {E}({\tilde{D}},{\tilde{V}})] + [\mathcal {E}({\tilde{D}},{\tilde{V}}) - \mathcal {E}\left( D_0,V_0 \right) ] \end{aligned}$$

(10)

The three components of the votemandering bonus in Equation (10) depend on different factors: The first, $[\mathcal {E}(D_0, {\tilde{V}}) - \mathcal {E}(D_0, V_0)]$, captures the difference between wins in campaigned and initial maps while keeping the original district map fixed. This component depends on the optimal allocation of Party A’s campaign budget, as their campaigning efforts modify voter preferences $({\tilde{V}})$. The second component, $[\mathcal {E}({\tilde{D}}, V_0) - \mathcal {E}({\tilde{D}}, {\tilde{V}})]$, captures the difference between the wins of target and votemandered maps. This component depends on Party B’s campaign budget allocation (fixed while finding A’s strategies), as only B’s campaigning can potentially induce positive changes in $V_0 - {\tilde{V}}$, as seen on the new plan ${\tilde{D}}$. The third component, $[\mathcal {E}({\tilde{D}}, {\tilde{V}}) - \mathcal {E}(D_0, V_0)]$, captures the net change in wins between votemandered and initial maps. However, this component is essentially bounded (Cho, 2017), as the redrawn $({\tilde{D}})$ and original $(D_0)$ district plans can only differ by a few discrete EG values.

Comparing $\Delta$ for global votemandering maxima to one obtained via local votemandering, Equation (10) highlights the same three areas where the local heuristic operates (approximating the optimal) through its key strategies. Each strategy seeks to optimize a component objective (i.e., getting at most 1 increment) while operating with 2 districts locally. This suggests that the efficiency of votemandering can be explained using the generalized versions of local key strategies, i.e., without necessarily restricting to two districts. While the global heuristic achieves similar outcomes if the local optimal plan is within its map pool, local votemandering’s targeted approach among neighboring districts and exploiting the information of the initial map may sometimes produce outlier plans more effectively. As seen in Sect. 6, the local votemandering heuristic outperforms the global heuristic in one case.

Equation (10) reemphasizes that increasing district compactness reduces the effectiveness of votemandering. Compactness, characterized by fewer cut edges or a smaller shared boundary between districts, limits the ease of exchanging units across these borders. The efficiency of votemandering hinges on strategically exchanging units between districts, as outlined in strategies 1 and 2 and further supported by Lemma 1. These approaches involve investing to win in a campaigned map and then reshaping this investment to favor a losing district in a votemandered map. Consequently, a mandated reduction in cut edges between districts makes it more challenging to find exchangeable units, leading to a decreased ability to votemander effectively.

In conclusion, the global heuristic bypasses the matching constraints and works without narrowing the search to two districts, while the local has strengths in efficient parallel search at the district level and in generating plans that closely resemble the original ones. At the core, the heuristics primarily build upon the key strategies, with the strategic exchange of units and the local vote-share distribution being crucial to improving the objective while maintaining fairness. Depending on the political geography, one may surpass the other, as we present in the case of Wisconsin in Sect. 6. Further emphasizing the discussion in Sect. 5.1.1, the fusion of gerrymandering and strategic campaigning separates the effects of pure campaigning strategies from votemandering strategies, enabling a more robust dependence of budgets and voter inclinations on votemandering outcomes. Overall, the key to successful votemandering is access to vote share information and targeted delivery of campaigns, both continually boosted by advancements in data analytics.

6 Votemandering strategies on real data

This section demonstrates votemandering strategies through two real-world case studies. First, we analyze Wisconsin state senate redistricting after the 2020 census, applying both global and local votemandering approaches to quantify potential partisan advantages for the two major parties. We then briefly examine Ohio’s 2020 redistricting cycle, which illustrates how strategic selection of historical voting data can influence fairness assessments in practice.

6.1 Wisconsin state senate redistricting after 2020: illustrations

The 2020 redistricting cycle in Wisconsin was delayed due to lawsuits, prompting the Wisconsin state legislature and the governor’s People’s Maps Commission to propose state and congressional district plans. The Wisconsin Supreme Court eventually approved the state senate and house maps drawn by the legislature (Ballotpedia, 2022).

Wisconsin’s balanced partisan composition provides a suitable environment for exploring the feasibility of votemandering. The state senate has 33 seats, with approximately half up for election every two years. The Republican party (R) controls the state senate with a 21-11 majority (excluding a vacancy) and had a $51.1\%$ statewide senate election vote share in previous elections. Conversely, the Democratic party (D) won the 2020 presidential election in Wisconsin by a $0.63\%$ margin, and the state’s governor is a Democrat. The Democratic governor’s veto power over redistricting proposals from the Republican state legislature ensures that both parties influence the final state senate map. Additionally, the state constitution mandates that districts be compact, contiguous, and “bounded by county, precinct, town, or ward lines where possible" (Wisconsin, 2022).

Throughout this section, we consider the 2021 governor’s state senate plan ($\texttt {GOV2021}$) as the initial map. Rated as fair with an ‘A’ score by the Princeton Gerrymandering Project (2022), $\texttt {GOV2021}$ serves as a reasonable starting point for our votemandering case study, despite not being enacted.

The $\texttt {GOV2021}$ plan incorporates state senate election data from 2018 and 2020 (for 17 and 16 seats, respectively). According to the 2020 census, the ideal population for each senate district is 178,598. We assume a statewide voter turnout of $65\%$, the average from the 2018 and 2020 elections. Both parties receive a budget to influence 13,734 voters, constituting a $1\%$ total investment of the expected votes cast. The votemandering party strategizes its campaign investment, while the other party is assumed to allocate its investment proportionally to unit populations.

Section 6.1.1 investigates global votemandering effects for each major party, revealing that although both parties can benefit, the Democratic party achieves a more substantial votemandering bonus given $\texttt {GOV2021}$ as the initial map. Section 6.1.2 illustrates local votemandering strategies that align with the Wisconsin Supreme Court’s goal of minimizing changes to the previous district plan. Both parties continue to benefit within this restricted strategy space, and the votemandering bonus even increases for one party.

6.1.1 Wisconsin global votemandering

Fig. 10

Distribution of votemandering objectives over the pool of maps

Fig. 11

Distribution of Efficiency Gap measure over the pool of maps

The global votemandering heuristic expounded in Sect. 3 is applied to Wisconsin state senate redistricting, using a pool of 80,000 prospective target maps ($1\%$ population deviation) generated via Recombination. Figure 10 shows the distribution of votemandering bonuses for each party. Each histogram shows the number of maps yielding a specific votemandering bonus for the votemandering party when fixed as the target map. The EG of $\texttt {GOV2021}$, 0.1409, indicates more wasted votes for the Democratic party, giving the Democratic party more room to gain seats while maintaining a safe EG. Hence the Democratic party tends to achieve a greater votemandering bonus than does the Republican party, i.e., the distribution in Fig. 10b is shifted to the right of the distribution in Fig. 10a. The relatively high EG of $\texttt {GOV2021}$ does not necessarily indicate partisan gerrymandering. Figure 11 shows the distribution of EG for the pool of maps. Due to the spatial distribution of voters in Wisconsin, Recombination tends to generate maps with positive (i.e., Republican-leaning) EG values. Based on the EG value of $\texttt {GOV2021}$ and the pool’s EG distribution, we impose a fairness bound of $0.0 \le \text {EG} \le 0.15$ throughout the case study.

Table 2 Wisconsin Global Votemandering Characteristics: The Republican Party gets a votemandering bonus of 5 while the Democratic Party gets a bonus of 8

To show an illustration of how these votemandering objectives are attained, we next describe optimal target maps with both parties as strategists. Table 2 shows the characteristics of votemandering stages specific to our examples. Figures 12 and 13 visually show the initial and target maps, strategic investment of the Republican party, and the various stages of votemandering on the real state data of Wisconsin. Figures 14 and15 show the same for the Democratic party.

For the Republican votemandering, the objective is 47 seats across two rounds, against 42 with no strategic investment. The Democratic votemandering bonus is 8, showing a larger improvement for the Democratic party as explained above. The proposed Republican map would show an EG of 0.1285 with the previous election data (apparently fairer than the initial map), with the actual value being 0.1915. This is reflected in the difference of 2 seats between the votemandered and target map. While the investment leads to three new seats in the campaigned map, the new plan negates this effect entirely.

In these cases, both parties choose outlier maps as the target maps and make the votemandered maps fair. Strategic investment for both cases is allocated across the map by carefully selecting units: the bottom-left part in Fig. 14c is largely uniform (to make a difference only in Round 1), the top-half part in both Figs. 12c and 14c is non-uniform (to only affect units that remain part of losing districts in the target map) and finally, the bottom-half part in Fig. 12c is sporadic, with the right corner serving as an investment made to satisfy the fairness bound.

Fig. 12

Republican Global Votemandering: The initial map, the chosen target map, and the strategic investment of budget (with intensity indicated by the darker color)

Fig. 13

The Four Stages of Republican Global Votemandering, (with red and blue indicating the districts won by the Republican and Democratic parties, respectively)

Fig. 14

Democratic Global Votemandering: The initial map, the chosen target map, and the strategic investment of budget (with intensity indicated by the darker color)

Fig. 15

The Four Stages of Democratic Global Votemandering, (with red and blue indicating the districts won by the Republican and Democratic parties, respectively)

6.1.2 Wisconsin local votemandering

When forced to decide the final state senate district plan, the Wisconsin Supreme Court announced that it would seek to make as few changes as possible to the existing map. In accordance with this goal, this section applies the bottom-up local votemandering heuristic to find strategies for both parties which produce target maps close to $\texttt {GOV2021}$.

Table 3 Local Votemandering Characteristics: The Republican Party gets a votemandering bonus of 4 while the Democratic Party gets a bonus of 10

Both parties can gain advantages from local votemandering, although each party employs a significantly different approach. Figure 16 illustrates the $\texttt {GOV2021}$ district adjacency graph (16a), the best Republican strategy discovered (16b), and the best Democratic strategy discovered (16c). Node colors represent the party with a higher vote-share in each district. Edges with nonzero weights indicate Strategy-1 edges, while 0 weights correspond to Strategy-2, and ‘FC’ denotes fairness costs associated with Strategy-3.

Fig. 16

Local Votemandering: The district adjacency graph and the maximum matching solutions

The maximum matching solution for the Republican party (Fig. 16b) yields a votemandering bonus of four seats through Strategy-2 improvements (i.e., without incurring monetary or fairness costs). Consequently, the Republicans’ local votemandering bonus, which results in 46 seats across the two elections, is one seat fewer than their global votemandering bonus of 47 seats. The maximum matching solution for the Democratic party (Fig. 16c) attains a votemandering bonus of ten seats, surpassing their global votemandering bonus of eight, via two Strategy-1, six Strategy-2, and two Strategy-3 edges. Strategy-1 edges consume a budget of 11,347 to boost Democratic voter turnout. Table 3 details the map characteristics for each stage of local votemandering by each party, while Figs. 19, 20, 21 and 22 in Appendix D display the corresponding maps and campaign strategies.

Local votemandering strategies for both parties generate target maps closer to $\texttt {GOV2021}$. As described in Sect. 4, the closeness parameter is adjustable, allowing for the optimization of the bonus while producing maps as close to the initial map as desired. Notably, local votemandering relies extensively on Strategy-2 improvements, which exploit the other party’s campaign investments. Given the political geography, both parties’ votemandering strategies are substantially different. Overall, the study demonstrates substantial gains for both political parties, showing the vulnerability of Wisconsin state senate redistricting, and in particular, $\texttt {GOV2021}$, to global and local votemandering.

6.2 The case of Ohio redistricting after 2020: discussion

After the 2020 census, the Ohio redistricting cycle saw multiple formal map proposals, new map enactments, and several adopted redistricting plans challenged and overturned in the Supreme Court (Ballotpedia, 2023). The Ohio Constitution mandates the districts to be compact, neutral, and crucially, closely proportional to the state-wide share, “based on statewide state and federal partisan general election results during the last ten years” (Ohio Laws, 2021). In 2022, The Ohio Supreme Court rejected maps on their inability to strictly follow proportionality (League of Women Voters, 2023), considering it as the primary fairness metric.

The last 10-year share is to be considered for redistricting, and the statewide share of the Republican party varied from 46.2$\%$ to 59.7$\%$. Moreover, given the ambiguity in the interpretation of data to be used, there were conflicting opinions on how to aggregate the past election data (page 43 of Ohio Supreme Court (2022), page 9 of Ohio Supreme Court (2021)). Parties attempted to downplay their better performance, as the map disproportionality increases with an increasing fraction of the statewide vote won by the majority party. The commission’s use of election data was pointed out by the Supreme Court and supported the court’s decision to reject proposed maps (page 28 of League of Women Voters of Ohio (2021)). The final maps that were enacted still miscalculated the party shares for measuring fairness, as caught in the 2022 elections. On this background, the Ohio Citizens Redistricting Commission Amendment (2024) asked for strict proportionality based on the median of election results in the last 6 years (Ballotpedia, 2024).

From a votemandering point of view, the specific use of data indicating the competitor’s better performance in computing fairness, is philosophically similar to Strategy-2, as explained in Sect. 4. There, a strategist party accesses its competitor’s increased vote share to show fairness, while in reality, the district is won by the strategist. Similarly, downplaying the strategist party’s better performance for gauging the proposed map’s fairness is reminiscent of Strategy-1. The distinction is that in the Ohio case, the strategist also controlled (at least initially) the set of past election data used in measuring fairness, in addition to redistricting. Moreover, the Ohio case demonstrates that fielding weaker candidates in races where losing is all but guaranteed may offer parties strategic advantages in future redistricting cycles (Pelzer, 2022).

The investigative efforts needed to produce empirical evidence of votemandering strategies (as conceived in this paper) in the Ohio case are beyond the scope of this paper. Nevertheless, the Ohio case highlights the importance of considering strategic behavior in the context of evaluating district plan fairness, which is a core contribution of our votemandering framework.

7 Conclusion and future directions

In this study, we introduce the concept of votemandering, a combination of strategic campaigning and gerrymandering to deceive fairness measures and increase seat-share across multiple elections. Focusing on the efficiency gap (EG) as a fairness metric, we establish sufficient conditions for a positive votemandering bonus (Theorem 2) and present an efficient heuristic for identifying votemandering strategies (Algorithm 1, Proposition 1, Theorem 1).

Through computational experiments, we investigate the impact of campaign budget, compactness, voter turnout, and spatial autocorrelation of voters on votemandering efficacy. Our findings indicate that enhancing voter turnout and compactness, parameters seemingly unrelated to partisan fairness, can potentially mitigate the influence of votemandering. A case study of Wisconsin state senate redistricting illustrates practical votemandering strategies for both parties. We also briefly discuss the 2020 Ohio redistricting cycle, which provides a real-world example in which the choice of which voter data are used to measure fairness affects the conclusion.

To further demonstrate the practicality of votemandering, we introduce local votemandering, which allows the party controlling redistricting to make minor adjustments to a limited number of district boundaries. This leads to our second heuristic, which efficiently discovers profitable district maps with minimal district pair recombination. In the Wisconsin case study, local votemandering yields a higher votemandering bonus for one party compared to the global, pool-based heuristic. The global and local votemandering methods present a combined efficient framework to test the vulnerability of redistricting maps toward votemandering.

Future research may explore votemandering in the context of alternative fairness measures by utilizing the general framework outlined here. Determining the most effective fairness measure, or a combination thereof, to prevent votemandering remains an open question. Our votemandering model assumptions may be strengthened to derive more practical implications. The model currently allows for strategic campaigning only in the first election; expanding it to include the second election would increase our model’s validity at the expense of greater complexity. Further extensions might examine votemandering across more than two election rounds. This would necessitate accounting for migration patterns and shifts in voter sentiment. Introducing uncertainty in the knowledge of vote shares gives an important practical direction. Moreover, allowing both parties to strategically allocate their campaign budgets would introduce a generalized version of the colonel Blotto game in the redistricting context, presenting challenges such as breaking ties and addressing computational complexity.

Finally, our work carries significant policy and practical implications. We demonstrate that strategic campaigning can substantially impact redistricting outcomes despite the presence of fairness constraints and that the sole use of EG as a fairness measure may be insufficient. Our results advocate for additional measures that account for strategic behavior and policies that curtail manipulative campaigning practices. Ultimately, this study underscores the importance of considering strategic behavior when designing and evaluating redistricting processes, and the need for ongoing research on political manipulation in democratic systems.

Appendices

Notation

Table 4 Parameters, decision variables, and performance metrics for the votemandering model

Section 3 Details

1.1 Optimization framework for votemandering

In this section, we explain the optimization framework we use to model the votemandering process. Table 4 in Appendix A lists the notation built.

1.1.1 State characteristics

Let K denote the set of units in a state with n districts. Each district designates one unit as its center. The district assignment of each unit $j \in K$ in each round $r \in \left\{ 1,2 \right\}$ is represented by the indicator variables

$$\begin{aligned} z_{ij}^{r}= {\left\{ \begin{array}{ll} 1, & \text {if unit}\ j\ \text {is assigned to the district centered at unit}\ i\ \text {in round}\ r \\ 0, & \text {otherwise.} \end{array}\right. } \end{aligned}$$

Moreover, $z_{ii}^{r} = 1$ if i is a district center in round r. The original district plan, $D_0$, fixes the values of $z_{ij}^1$ and are thus known, while $z_{ij}^{2}$ are decision variables.

The following constraints enforce the proper formation of districts in Round 2.

$$\begin{aligned}&\sum _{k \in K} z_{ki}^{2} = 1&\forall i \in K \end{aligned}$$

(11)

$$\begin{aligned}&\sum _{k \in K} z_{kk}^{2} = n \end{aligned}$$

(12)

Constraint (11) ensures every unit is assigned to some district, and constraint (12) ensures exactly n units are chosen as district centers.

1.1.2 Budget and campaigning

The unit populations and the corresponding party affiliations, i.e., the maximum number of voters for each party in each unit are known: The maximum vote counts for party A (B) are given by $p_{k}^A$ ($p_{k}^B$) in unit $k \in K$, such that the total unit population is $p_k = p_{k}^A+p_{k}^B$. Let $\alpha \in \left[ 0,1 \right]$ denote the fractional baseline voter turnout, assumed constant across all units and fixed a priori. The number of votes for party $A$ in unit $k$ is the sum of the baseline turnout, $\alpha p_k^A$ (denoted as $v_{0, k}^A$), and additional votes generated through GOTV campaigning. The vote shares $p_{k}^A, p_k^B$, and $\alpha$ are fixed for all rounds, the actual voting turnout may vary depending on campaigning. These values are typically informed by publicly available data, including historical vote shares, registered voters, and campaign spending trends.

Let ${\mathcal {B}}^A$, ${\mathcal {B}}^B$ denote the parties’ GOTV campaign budgets in terms of the total number of their supporters they can convince to show up to the polls. Budget allocations in unit k by party $P \in \left\{ A,B \right\}$ may linearly push their actual number of votes above the baseline turnout $v_{0,k}^{P}$, but their total number of votes cannot exceed $p_{k}^P$. (Hence if $\alpha = 1$, then GOTV budget allocations have no effect.) We then define ${\tilde{v}}_k^{A}$ as the actual voter turnout for party A in unit k, and it is linearly proportional to the budget spent $b_k^A$:

$$\begin{aligned}&{\tilde{v}}_k^{A} = v_{0,k}^{A} + b_k^A & \forall k \in K \end{aligned}$$

(13)

$$\begin{aligned}&{\tilde{v}}_k^{B} = v_{0,k}^{B} + b_k^B & \forall k \in K \end{aligned}$$

(14)

$$\begin{aligned}&b_k^A \le (1/\alpha -1) v_{0,k}^{A} & \forall k \in K \end{aligned}$$

(15)

$$\begin{aligned}&\sum _{k \in K} b_{k}^A \le {\mathcal {B}}^A \end{aligned}$$

(16)

The relationship between budget and increased turnout may be extended to a general linear function (${\tilde{v}}_k^A \propto c_1 b_k^A + c_2$, with $c_1, c_2$ as constants) as widely modeled in the literature (Jacobson, 1990; Gerber & Green, 2000; Levitt, 1994), e.g., using different scaling constants for incumbent and challenger candidates. Non-linear effects may be modeled (Lipsitz & Padilla, 2024), leading to increased complexity.

By assumption, party B’s campaign allocation, and therefore the values $b_k^B, {\tilde{v}}_k^B$, are known to party A, while $b_k^A$ are decision variables showing A’s campaign allocation over the state.

1.1.3 Winning districts

A party must win more than half of the votes in a district to secure a win, which we enforce using the big-M method. We define indicator variables ${\hat{s}}_i^1$ and ${\hat{s}}_i^{2}$ (with ${\hat{s}}_i^{r} = 1$ meaning party A’s win in round r) for campaigned and target maps, i.e. Round 1 and Round 2, respectively.

$$\begin{aligned}&1-M(1-{\hat{s}}_i^{1}) \le \sum _{k \in K} z_{ik}^{1} \left( {\tilde{v}}_k^A- {\tilde{v}}_k^B\right) \le M {\hat{s}}_i^{1}&\forall i \in K \end{aligned}$$

(17)

$$\begin{aligned}&1-M(1-{\hat{s}}_i^{2}) \le \sum _{k \in K} z_{ik}^{2} \left( v_{0,k}^A- v_{0,k}^B\right) \le M {\hat{s}}_i^{2}&\forall i \in K \end{aligned}$$

(18)

Note that constraints (17) and (18) are both linear: $z_{ik}^{1}$ show the unit-to-district assignments in the initial map and are given, although variables ${\tilde{v}}_k^A$ depend on the budget spent. For (18), we know the values of $v_{0,k}^A, v_{0, k}^B$, but variables $z_{ik}^{2}$ depend on the plan that we make for Round 2. Thus, the values of ${\hat{s}}_i^{1}$ and ${\hat{s}}_i^{2}$ are dependent on the decision variables $z_{ik}^{2}$ and $b_k^A$ (which fix ${\tilde{v}}_k^A$ via (13)).

1.1.4 The votemandering MIP

The objective function of (1) is now represented by the sum of individual district wins in both rounds, i.e., ${\hat{s}}_i^{1}$ and ${\hat{s}}_i^{2}$ for every unit i. As described in (1), a fairness measure constraint $f({\tilde{D}}, {\tilde{V}}) \le \delta$ is implemented, here precisely represented as a function of the decision variables (updated vote shares ${\tilde{v}}_{k}^A$) and the second-round district assignment variables ($z_{ij}^{2}$). Using our notation, this constraint refers to the fairness constraint on the votemandered map. Furthermore, the Round 2 plan, i.e., $z_{ij}^{2}$, must also satisfy nonpartisan constraints of contiguity and population balance for making districts. Additional constraints may be enforced per state requirements; for instance, compactness is often necessary and can be achieved using the notion of cut-edges as done in the work on recombination in redistricting DeFord et al. (2021). For the rest of the paper, we include contiguity and population balance in our feasible map-making constraints and additionally enforce compactness whenever stated.

Finally, given $v_{0,k}^{A}, v_{0, k}^{B}$, $z_{ij}^{1}$, ${\tilde{v}}_{k}^B$, ${\mathcal {B}}^A$ and $\delta$, a mixed-integer programming (MIP) formulation of party A’s optimization problem is

$$\begin{aligned} \begin{array}{ll} \begin{array}{c} \textrm{maximize} \\ {\left\{ b_k^A \right\} _k, \left\{ z_{ik}^{2} \right\} _{i,k}} \end{array} & {\mathop {\sum }\limits _{i\in K }{\hat{s}}_i^{1} +\mathop {\sum }\limits _{i\in K} {\hat{s}}_i^{2}}\\ \textrm{subject to} & \qquad {\text {constraints } (11)-(18)},\\ & \qquad {z_{ik}^{2}, {\hat{s}}_i^{1}, {\hat{s}}_i^{2}}{\in \left\{ 0,1 \right\} \quad \forall i,k\in K},\\ & \qquad {b_i^A}{\ge 0 \quad \forall i\in K},\\ & \qquad {f\left( z_{ik}^{2}, {\tilde{v}}_{k}^{A} \right) }{\le \delta },\\ & \qquad {\left\{ z_{ik}^{2} \right\} \text { satisfy nonpartisan constraints.}} \end{array} \end{aligned}$$

(19)

This concludes the description of the optimization problem (19).

1.1.5 Solving MIP (19)

Solving the MIP in (19) involves finding a feasible district map (${\tilde{D}}$) for the second round elections and an allocation of campaign resources to increase voter turnout (${\tilde{V}}$) in the first round. The objective is to maximize the combined results across both rounds while ensuring that ${\tilde{D}}$ is fair with respect to ${\tilde{V}}$. Constraints (11) and (12) ensure unit-to-district allocation in the new map; constraints (13)-(16) capture the campaign allocation in units and subsequent changes to the voter turnout, ensuring the turnout is upper-bounded by the total vote shares per party and at most ${\mathcal {B}}^A$ budget is spent. Constraints (20)-(21) represent the wins and losses by party A in both rounds, after updates from campaigning and the new Round 2 map. Finally, the remaining constraints from (19) ensure feasible map-making by enforcing fairness (via $f, \delta$), contiguity, population balance, and other desired features, e.g., compactness.

The feasibility of MIP (19) then implies that a contiguous, population-balanced, n-district map exists, such that it satisfies desired fairness constraints on voter turnout data which is additively reachable from the original turnout data, given the additions respect vote-share caps in every unit and the total budget constraint. See that if the initial map is fair and B allocates no budget, the MIP (19) is always feasible with zero budget allocation in all units. However, the same may not be guaranteed given B’s allocation, as the initial may become unfair.

1.2 Simplified MIP formulation for EG

Here, we describe the MIP we use to ensure the fairness of the proposed map (with plan ${\mathcal {J}}$) in Round 2, i.e., the votemandered map. This is built on the optimization problem (19), where the plan-making constraints for Round 2 are dropped and the fairness constraints are specific to EG.

Letting $\tau _{J}, \ \forall J \in {\mathcal {J}}$ denote the difference between wasted votes in J’s district, i.e., ${\mathcal {W}} (I)$, we have:

$$\begin{aligned} \max \ \sum _{I\in {\mathcal {I}}} {\hat{x}}_{I} \nonumber \\ s.t. \, \,&\text {Constraints (15), (16)} \nonumber \\&{\tilde{V}}_{I}^{A} = \sum _{k \in I} v_{0,k}^{A} + b_k^A&\forall I \in {\mathcal {I}} \nonumber \\&{\tilde{V}}_{J}^{A} = \sum _{k \in J} v_{0,k}^{A} + b_k^A&\forall J \in {\mathcal {J}}\nonumber \\&1-M(1-{\hat{x}}_{I}) \le ({\tilde{V}}_I^{A}- {\tilde{V}}_I^{B}) \le M {\hat{x}}_{I}&\forall I \in {\mathcal {I}} \end{aligned}$$

(20)

$$\begin{aligned}&1-M(1-{\hat{y}}_{J}) \le ({\tilde{V}}_J^{A}- {\tilde{V}}_J^{B}) \le M {\hat{y}}_{J}&\forall J \in {\mathcal {J}} \end{aligned}$$

(21)

$$\begin{aligned}&0 \le - \tau _{J}+ \left( \frac{3 {\tilde{V}}_J^B - {\tilde{V}}_J^A}{2} \right) \le M (1-{\hat{y}}_{J})&\forall J \in {\mathcal {J}} \end{aligned}$$

(22)

$$\begin{aligned}&0 \le \tau _{J} - \left( \frac{ {\tilde{V}}_J^B - 3{\tilde{V}}_J^A}{2} \right) \le M {\hat{y}}_{J}&\forall J \in {\mathcal {J}} \end{aligned}$$

(23)

$$\begin{aligned}&-0.08 \le \sum _{J \in {\mathcal {J}}} \tau _{J}/\left( \sum _{J\in {\mathcal {J}}} {\tilde{V}}_J^A+{\tilde{V}}_J^B \right) \le 0.08 \end{aligned}$$

(24)

$$\begin{aligned}&{\hat{x}}_{I}, {\hat{y}}_{J} \in \{0,1\}, \ \ \ b_k^A \ge 0&\forall k \in K, J \in {\mathcal {J}} \end{aligned}$$

(25)

The constraints involving $\tau _{J}$ are meaningful because, for $y_{J}$ equal to either 0 or 1, the middle part of the constraint is always positive, as required. This is verified using the definitions of wasted votes in case of party A winning or losing.

1.3 Proof of Theorem 1

Theorem 1

Let $\mathcal {P}$ be a pool of feasible, but not necessarily fair, n-district plans. In the initial map, let q be the maximum number of additional districts that can be won using ${\mathcal {B}}^A$. A plan in $\mathcal {P}$ that maximizes the votemandering bonus may be found in $poly (|\mathcal {P}|, n^{q})$ time.

Proof

Following Algorithm 1, the main complexity lies in the fairness step (9) of the MIP in Sect. 3.1.2. We show that each target map can be verified in time $O(n^{q+1} \cdot t_{lp}(n))$, where $t_{lp}(n)$ is a polynomial representing the complexity of solving the LP relaxation in a branch-and-bound solver. This allows for rapid iteration through the pool until convergence.

In summary, our approach solves the MIP in Appendix B.2 as follows: We first formulate a mixed-integer linear program (MILP), where the only integer variables, ${\hat{x}}_I$, indicate which districts are won in Round 1 based on campaign allocation. The total number of continuous variables is reduced from $|K|$ (total units) to $n^2$, corresponding to the distinct regions in the district plans for Rounds 1 and 2. The MILP fixes the number of wins in the votemandered map (${\hat{y}}_I$) at each iteration, requiring at most $n$ iterations to cover all feasible instances. With at most $q$ non-zero ${\hat{x}}_I$ variables, a general branch-and-bound method solves the MILP in $O(n^q \cdot t_{lp}(n))$ time, yielding an overall complexity of $O(n^{q+1} \cdot t_{lp}(n))$.

We now elaborate our approach. Careful observation of the simplified MIP in Appendix B.2 reveals that the first set of constraints (13)-(16) track the effects of budget on updating vote shares, the second set of constraints (20)-(21) translates these effects into the W/L status of campaigned and votemandered map, the third set (22)-(23) further translates this into the EG fairness evaluation of the districts and finally the district plan in (24). WLOG, we consider party B’s campaign additions as part of $V_0$, while A’s additions lead to ${\tilde{V}}$. This works since the only consideration of B’s voter data at $V_0$ is in Round 2 votemandering objective, and it is fixed as plan J is fixed.

We simplify the space of variables $b_k$ to represent the campaign budget, defined as the linear capture of votes added through campaigning (as described in Sect. B.1.2), within pieces formed by the overlap of each district in ${\mathcal {I}}$ with each district in ${\mathcal {J}}$. Let $z_{IJ}$ denote the campaign budget allocated to the set of units belonging to district $I$ in Round 1 and district $J$ in Round 2. The spending capacity of each piece is defined as $c_{IJ} = \min$ (division voter-turnout capacity, budget required to win the Round 2 district it belongs to, if it is a losing district).

Further, when we fix the W/L status in the votemandered map, i.e., fix variables ${\hat{y}}_J$, we simplify constraints (22)-(23) by setting the $\tau$ variables. They are then substituted in constraint (24) to capture the fairness cost using $\delta = \text { EG (e.g., 0.08) }\times (\text {total votes}) - {\mathcal {W}} _{{\mathcal {J}}}$, i.e., maximum new wasted votes to be allowed by the EG and plan ${\mathcal {J}}$’s wasted votes. The MIP is now reduced to:

$$\begin{aligned} \max \ \sum _{I\in {\mathcal {I}}(L)} {\hat{x}}_{I} \nonumber \\ s.t. \, \,&1-M(1-{\hat{x}}_{I}) \le (\sum _{J\in {\mathcal {J}}} z_{IJ} + V_{0, I}^{A}- V_{0, I}^{B}) \le M {\hat{x}}_{I}&\forall I \in {\mathcal {I}}_{V_0}(L) \nonumber \\&\sum _{I\in {\mathcal {I}}} z_{IJ} \le V_{0,J}^B-V_{0,J}^A&\forall J \in {\mathcal {J}}_{V_0}(L) \nonumber \\&\sum _{I, J \in \mathcal {I, J}} z_{IJ} \le {\mathcal {B}}^A&\nonumber \\&\frac{1}{2}\sum _{J\in {\mathcal {J}}_{V_0}(W)} \sum _{I\in {\mathcal {I}}}z_{IJ} +\frac{3}{2}\sum _{J\in {\mathcal {J}}_{V_0}(L)}\sum _{I\in {\mathcal {I}}} z_{IJ} \le \delta \nonumber \\&\sum _{I \in {\mathcal {I}}_{V_0}(L)} {\hat{x}}_{I}\le q&\nonumber \\&0\le z_{IJ} \le c_{IJ}&\forall I, J \in \mathcal {I, J} \nonumber \\&{\hat{x}}_{I} \in \{0,1\}&\forall I \in {\mathcal {I}}_{V_0}(L) \end{aligned}$$

After solving this MILP, we check if the optimal solution involves a tight $\sum _{I\in {\mathcal {I}}} z_{IJ'} \le V_{0, J'}^B-V_{0,J'}^A$ for a $J' \in {\mathcal {J}}_{V_0}(L)$. If not, this implies that the optimal investment leading to maximum seats in Round 1 doesn’t need to change the W/L status of any district in the votemandered map. Otherwise, a tight constraint implies a change in W/L status of a district, i.e., $\hat{y_{J}}$ towards optimality which changes the fairness significantly and non-continuously. We thus make the required change in constraints and solve the updated linear program again. Corresponding to district $J'$, the updates include replacing $\sum _{I\in {\mathcal {I}}} z_{IJ'} \le V_{0,J'}^B-V_{0,J'}^A$ with

$$\begin{aligned} \sum _{I\in {\mathcal {I}}} z_{IJ'} \ge V_{0,J'}^B-V_{0,J'}^A \end{aligned}$$

and replacing the fairness constraint with

$$\begin{aligned} \frac{1}{2}\sum _{J\in {\mathcal {J}}_{V_0}(W) \cup J'} z_{IJ} - \frac{1}{2} (V_{0,J'}^B-V_{0,J'}^A) +\frac{3}{2}\sum _{J\in {\mathcal {J}}_{V_0}(W)/J'} z_{IJ} \le \delta - \frac{3V_{0,J'}^B+V_{0,J'}^A}{2} \end{aligned}$$

or

$$\begin{aligned} \frac{1}{2}\sum _{J\in {\mathcal {J}}_{V_0}(W) \cup J'} z_{IJ} +\frac{3}{2}\sum _{J\in {\mathcal {J}}_{V_0}(W)/J'} z_{IJ} \le \delta - 2V_{0,J'}^B \end{aligned}$$

Having two (or more) tight constraints at any step indicates a sufficient budget to win the corresponding districts, but the wins may lead to substantial fairness costs. Thus, fairness being the only bottleneck in this case, we greedily choose the district $J'$ that has the least fairness cost in terms of $\frac{3V_{0,J'}^B+V_{0,J'}^A}{2}$. This way, we have to solve at most n linear programs to reach an optimal solution to the MIP, which is the case when every update to the linear program produces an optimal solution that improves the objective.

Finally, it remains to address the complexity of solving the MILP. Since we have at most q variables ${\hat{x}}_{I}$ assuming value 1, the number of nodes that a branch and bound solver may have to traverse is at most $\left( {\begin{array}{c}n\\ q\end{array}}\right)$, i.e. $O(n^{q})$ feasible solutions (Table 5). Then, it would solve $O(n^{q})$ linear programs with $O(t_{lp}(n))$ complexity as there are $O(n^2)$ linear constraints. Therefore, the overall worst-case complexity gets bounded by $O(n^{q+1}\cdot t_{lp}(n))$. $\square$

1.4 Proof of Lemma 1

Lemma 1

Given any district plan ${\mathcal {I}}$ with voter data V, campaigning and vote shifts impact the total difference in wasted votes (${\mathcal {W}}$), as shown in Table 1.

Table 5 Impact of Campaigning and Vote Shifts on the Difference in Wasted Votes (EG)

Proof

We discuss each action from Table 1 and its impact on the difference between wasted votes below.

• 1. Wasting an additional vote on a winning district I: Before adding the extra vote, with votes $V_{I}^{A}$ and $V_{I}^{B}$ for both parties, the wasted votes for each party are as follows

  $$\begin{aligned} w^A_I = V_{I}^{A}- \frac{V_{I}^{A}+V_{I}^{B}}{2}, \ \quad w_I^B = V_{I}^{B} \end{aligned}$$

  (26)

  Then, the initial difference between wasted votes is

  $$\begin{aligned} {\mathcal {W}} _{init}(I) = V_{I}^{B} - V_{I}^{A} +\frac{V_{I}^{A}+V_{I}^{B}}{2} \end{aligned}$$

  (27)

  After adding a vote to party A, the wasted votes are updated as

  $$\begin{aligned} w^A_I = V_{I}^{A}+1- \frac{V_{I}^{A}+1+V_{I}^{B}}{2}, \ \quad w^B_I = V_{I}^{B} \end{aligned}$$

  (28)

  Then,

  $$\begin{aligned} {\mathcal {W}} _{final} (I) = V_{i}^{B}-V_{i}^{A}+ \frac{V_{i}^{A}+V_{i}^{B}}{2} - \frac{1}{2} = {\mathcal {W}} _{init}(I)-\frac{1}{2} \end{aligned}$$

  (29)

  Resulting in $\Delta {\mathcal {W}} = -\frac{1}{2}$ post the addition. In words, if party A adds a vote to a winning district, the difference between wasted votes changes by half a vote.

• 2. Wasting an additional vote on a losing district: Before adding the extra vote, with votes $P_A$ and $P_B$ for both parties, the wasted votes are as follows:

  $$\begin{aligned} w^A_I = V_{I}^{A}, \ \quad w^B_I = V_{I}^{B}- \frac{V_{I}^{A}+V_{I}^{B}}{2} \end{aligned}$$

  (30)

  Then,

  $$\begin{aligned} {\mathcal {W}} _{init}(I) = V_{I}^{B}- \frac{V_{I}^{A}+V_{I}^{B}}{2}- V_{I}^{A} \end{aligned}$$

  (31)

  After adding a vote to party A, the wasted votes are updated:

  $$\begin{aligned} w^A_I = V_{I}^{A}+1, \ \quad w_I^B = V_{I}^{B}- \frac{V_{I}^{A}+V_{I}^{B}+1}{2} \end{aligned}$$

  (32)

  Then,

  $$\begin{aligned} {\mathcal {W}} _{final}(I) = V_{I}^{B}- \frac{V_{I}^{A}+V_{I}^{B}}{2}- V_{I}^{A} - \frac{3}{2} = {\mathcal {W}} _{init}(I)-\frac{3}{2} \end{aligned}$$

  (33)

  Resulting in $\Delta {\mathcal {W}} = -\frac{3}{2}$. For each vote added by A in a losing district, the difference between wasted votes changes by $-3/2$ votes. Clearly, if A wants to decrease W to satisfy the EG bound, it is more beneficial to waste votes in a losing district.

• 3. Winning a district through campaigning: To win district I, A just needs to add $V_{I}^{B}- V_{I}^{A}$ votes (assuming ties break in favor of A). Initially, the wasted votes difference can be computed as:

  $$\begin{aligned} w^A_I = V_{I}^{A}, \ \quad w^B_I = V_{I}^{B} - \frac{V_{I}^{A}+V_{I}^{B}}{2} \end{aligned}$$

  (34)
  $$\begin{aligned} {\mathcal {W}} _{init}(I) = V_{I}^{B} - \frac{V_{I}^{A}+V_{I}^{B}}{2} - V_{I}^{A} \end{aligned}$$

  (35)

  After party A adds $V_{I}^{B} - V_{I}^{A}$ votes to win the district, the difference between wasted votes is updated as:

  $$\begin{aligned} w^A_I = 0 \ \quad w^B_I = V_{I}^{B} \end{aligned}$$

  (36)
  $$\begin{aligned} {\mathcal {W}} _{final}(I) = V_{I}^{B} \end{aligned}$$

  (37)

  Then, the change in W is computed as:

  $$\begin{aligned} \Delta {\mathcal {W}} = V_{I}^{B} - ( V_{I}^{B} - \frac{V_{I}^{A}+V_{I}^{B}}{2} - V^{A}_I) = \frac{3V_{I}^{A}+V_{I}^{B}}{2} \end{aligned}$$

  (38)

  Thus, given the initial vote count for district I, we can compute the change in the difference between wasted votes as $\frac{3V_{I}^{A}+V_{I}^{B}}{2}$.

• 4. Shift x votes from a winning to a losing district: Using the analysis for $\Delta {\mathcal {W}}$ when A wastes votes on a winning district, we can compute ${\mathcal {W}}$ when its reverse operation is performed. That is, when A removes x extra votes from district i, the change in ${\mathcal {W}}$ is:

  $$\begin{aligned} \Delta {\mathcal {W}} = \frac{x}{2} \end{aligned}$$

  (39)

  Further, when A distributes these votes in B’s winning district J, $\Delta {\mathcal {W}}$ is updated as:

  $$\begin{aligned} \Delta {\mathcal {W}} = \frac{x}{2} +\frac{-3}{2}\times x = -x \end{aligned}$$

  (40)

  If A chooses to redistribute these votes to another A’s winning district l, we get:

  $$\begin{aligned} \Delta {\mathcal {W}} = \frac{x}{2} + \frac{-1}{2}\times x = 0 \end{aligned}$$

  (41)

• 5. Shift x votes from a losing to a winning district: Similar to the previous case, shift from a losing to a winning district results in a difference of $\Delta {\mathcal {W}} = x$.

This concludes the discussion of the strategy space of A and its impact on the difference between wasted votes. $\square$

1.5 Proof of Theorem 2

Theorem 2

For any voter data $V_0$ and a corresponding fair initial map with district plan ${\mathcal {I}}$, the existence of strategies leading to a positive votemandering bonus for the majority party is guaranteed if both of the following conditions are satisfied:

• 1. A feasible, contiguous district plan ${\mathcal {J}}$ exists leading to a higher number of wins on $V_0$ than the initial map.

• 2. The voter turnout $\alpha$ satisfies

  $$\begin{aligned} \alpha \le 1- \left( \frac{2 \Delta {\mathcal {W}}_{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}}{\sum _{J\in {\mathcal {J}}_{V_0}(W)} \sum _{j \in J} p_j^A} \right), \end{aligned}$$

  where $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$ is the change in the difference between wasted votes from plan I to J with voter data $V_0$, and $p_j^A$ is party A’s total voter population, in the unit j.

Proof

We prove this in two parts: First, we constructively show that the fairness of plan ${\mathcal {J}}$ with altered vote shares (i.e., the votemandered map) is guaranteed under condition (2). Second, we show that the resulting allocation strategy suffices for party A to remain the majority in Round 1, resulting in the same or more wins than the initial map. Condition (1) assures that the target map (with plan ${\mathcal {J}}$) has more wins for the majority party and we show that the campaigned map has at least the same number of wins as the initial map. Hence, the corresponding votemandering bonus is always positive, and strategies are guaranteed whenever both parts hold true.

For a map with district plan ${\mathcal {J}}$, we now establish the fairness by showing (Eq (6))

$$\begin{aligned} {\mathcal {W}} _{{\mathcal {J}}, {\tilde{V}}} = {\mathcal {W}} _{{\mathcal {I}}, V_0} + \Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0} + \text {[campaign wasted votes]}\le \text {EG bound} \end{aligned}$$

(42)

We know that the initial map is fair, i.e., ${\mathcal {W}} _{{\mathcal {I}}, V_0} \le$ $\text {EG bound}$. Since ${\mathcal {J}}$ has higher number of wins than ${\mathcal {I}}$, WLOG, $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$ is considered positive. If it’s negative and makes ${\mathcal {W}} _{{\mathcal {J}}, V_0} \le - \text {EG bound}$, we naturally establish that the map gives more advantage to the minority party as compared to the initial map (and is acceptable), making a trivial case. If ${\mathcal {W}} _{{\mathcal {J}}, V_0} \ge \text {EG bound}$, then we use Table 1 to spend budget to satisfy the bound. However, the budget allocation is not trivial: the allocation should not change the W/L status of the districts in ${\mathcal {J}}$ and it needs to satisfy the individual unit voter-turnout constraints. Intuitively, the constraints may get violated under special cases like very high voter turnout or the election mandate hugely tilting towards a party. We next deduce sufficient conditions that allow such budget allocation to occur.

For districts in ${\mathcal {J}}_{V_0}(W), {\mathcal {J}}_{V_0}(L)$, i.e., the winning and losing districts respectively, the capacities of budget allocation can be written as

$$\begin{aligned} \text {Total capacity of winning districts}&= \sum _{J\in {\mathcal {J}}_{V_0}(W)} \sum _{j \in J} (1-\alpha )p_j^A = c_1 \end{aligned}$$

(43)

$$\begin{aligned} \text {Total capacity of losing districts}&=\sum _{J\in {\mathcal {J}}_{V_0}(W)} \min \{ \sum _{j \in J} (1-\alpha )p_j^A, \ V_{0,J}^B-V_{0,J}^A\} = c_2 \end{aligned}$$

(44)

Both $c_1$ and $c_2$ can be computed using the plan ${\mathcal {J}}$. Using Table 1, this translates to a bound on the effect on wasted votes:

$$\begin{aligned} \text {Max. achievable difference in}\ {\mathcal {W}}\ \text {through budget allocation } = -\frac{1}{2}c_1- \frac{3}{2}c_2 \end{aligned}$$

Then, the sufficient condition for votemandering becomes

$$\begin{aligned} {\mathcal {W}} _{{\mathcal {I}}, V_0} + \Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0} -\frac{1}{2}c_1- \frac{3}{2}c_2 \le \text {EG}_{max} \end{aligned}$$

(45)

We simplify this condition further to deduce a (comparatively stringent) sufficient condition on $\alpha$ by asking if allocating only on ${\mathcal {J}}(W)$ can satisfy the bound:

$$\begin{aligned} 0&\ge \Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0} -\frac{1}{2}c_1 \nonumber \\ c_1&= \sum _{J\in {\mathcal {J}}_{V_0}(W)} \sum _{j \in J} (1-\alpha )p_j^A \ge 2 \Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0} \nonumber \\ (1-\alpha )&\ge \left( \frac{2 \Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}}{\sum _{J\in {\mathcal {J}}_{V_0}(W)} \sum _{j \in J} p_j^A} \right) \nonumber \\ \therefore \alpha&\le 1- \left( \frac{2 \Delta {\mathcal {W}}_{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}}{\sum _{J\in {\mathcal {J}}_{V_0}(W)} \sum _{j \in J} p_j^A} \right) \end{aligned}$$

(46)

This is exactly condition (2). The lesser the difference between the wasted votes of ${\mathcal {I}}$ and ${\mathcal {J}}$, i.e., $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$, the higher the voter turnout votemandering strategies can handle.

Note that we do not explicitly assume any restrictions on B’s budget allocation. Party B’s allocation has implications on fairness and Round 1 wins. Round 2 wins aren’t affected by B’s allocation and are fixed by the plan ${\mathcal {J}}$. Following Lemma 1, party B’s allocation to ${\mathcal {J}}_{V_0}(W), {\mathcal {J}}_{V_0}(L)$ will make additions of $+3/2$ or $+1/2$ to $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$, i.e., the numerator in condition (2), respectively. However, if the additions make party B win a seat in Round 2 (votemandered map), then $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$ will decrease, increasing the upper bound on $\alpha$. Since B’s allocation is known, wlog, the fairness effects may be considered within $\Delta {\mathcal {W}} _{{\mathcal {I}} \rightarrow {\mathcal {J}}, V_0}$ for deriving a bound on $\alpha$, i.e., assuming updated vote shares at the beginning.

We now show that party $A$ can maintain its majority in Round 1 or ensure that party $B$ does not secure an additional win in Round 1. Party $A$’s derived allocation distributes its budget across districts in ${\mathcal {J}}_{V_0}(W)$. In Round 1, this distribution may include districts from both ${\mathcal {I}}_{V_0}(W)$ and ${\mathcal {I}}_{V_0}(L)$. Since party $B$’s strategies are unrestricted, we focus on ensuring that party $A$ can satisfy the fairness constraint for the votemandered map and maintain a winning strategy for Round 1. For ${\mathcal {I}}_{V_0}(L)$, party $A$’s allocation can either increase or retain its objective, regardless of party $B$’s allocation. For districts in ${\mathcal {I}}_{V_0}(W)$, the initial map (prior to campaigning) must satisfy $\sum _{i \in I} \alpha p_i^A > \sum _{i \in I} \alpha p_i^B$ for all $I \in {\mathcal {I}}_{V_0}(W)$. To ensure this remains true after campaigning, the allocation capacity must also satisfy $\sum _{i \in I} (1-\alpha ) p_i^A > \sum _{i \in I} (1-\alpha ) p_i^B$ for all $I \in {\mathcal {I}}_{V_0}(W)$. This guarantees that party $A$ can always match party $B$’s allocation in ${\mathcal {I}}_{V_0}(W)$, maintaining its majority in Round 1. Since party $A$ is merely matching party $B$ in this case, it will not secure an additional win in districts from ${\mathcal {J}}_{V_0}(L)$. Consequently, the effects on fairness only increase the upper bound on $\alpha$.

$\square$

Section 4 details

1.1 Local votemandering example

Here we illustrate the local votemandering heuristic through a grid graph example. We consider a $20 \times 20$ grid with fixed vote shares for parties A and B, forming 10 districts, with other parameters the same as our settings in section 3. The initial map is given in Fig. 17, in which A wins 4 seats.

Fig. 17

Local Votemandering: Initial and Target Maps

Fig. 18

Local Votemandering: Heuristic

For each pair of neighbors in the initial map, we find strategy 1,2, and 3 edges and their corresponding weights. The edge weights are computed using recombination local search. Finally, the matching problem and its solution are shown in Fig. 18. The edges with nonzero weights signify Strategy-1 edges, 0 weights correspond to Strategy-2, and ‘FC’ refers to fairness costs from Strategy-3. Once the maximum matching solution is obtained, we implement the perturbations between neighbors induced by each edge in the solution and create a new district plan that differs from the original map only in the selected perturbations. Figure 17 shows the final target map for this example. This local votemandering solution gives a votemandering bonus of 3, spending a budget of 174.

1.2 Local votemandering strategies: cost computations

We now discuss the computation of budget and fairness costs $(b_e, f_e)$ associated with the strategies.

Strategy-1:

Consider a submap of a pair of neighboring districts $(I_1, I_2)$. In this strategy, we allocate sufficient budget in a currently losing district $I_1$ (change $I_1$ status from $L \rightarrow W$ in the first round elections i.e. in the campaigned submap) and propose perturbations with its neighbor $I_2$ so that it again loses in the second round (mark $I_1$ status as L in the second round i.e. in the votemandered/target submap). We thus increase the votemandering bonus by 1, via a campaigned map win at $I_1$. The budget required here is simply the margin with which $I_1$ loses in the campaigned map (referred to as $margin(I_1$)) with no investment. Naturally, the perturbations for the new submap involve exchanging units across districts $I_1, I_2$ that nullify the effect of budget investment and regain the L status of $I_1$ in the votemandered submap. Let this imply a movement of $V_A^T$ party A votes and $V_B^T$ party B votes from $I_2$ to $I_1$. If $(I_1, I_2)$ have status (L, W) in the initial submap, Lemma 1 implies:

$$\begin{aligned} \Delta {\mathcal {W}} _i \text { for } (L, W) \text { districts }= -V_A^T - V_B^T -\frac{a_1}{2}-\frac{3a_2}{2}+\frac{b_2}{2}+\frac{3b_1}{2} \end{aligned}$$

(47)

where, $a_i, b_i$ is the budget allocation in district $d_i$ (in the initial submap) by party A and B respectively. Equation (47) may be explained as follows: Per Lemma 1, movement of $V_A^T$ from a winning to a losing district (for A) implies change of $-V_A^T$. Movement of $V_B^T$ from $B'$s losing to B’s winning has $V_B^T$ change in $\Delta {\mathcal {W}}(A-B)_i$, i.e., $-V_B^T$ change in $\Delta {\mathcal {W}} _i$. Further, A investing $a_1,a_2$ in losing, winning districts has $-1/2,-3/2$ effect per investment, respectively. Party B’s investment has similar effect on $\Delta {\mathcal {W}}(A-B)_i$, implying $1/2b_2, 3/2b_1$ effect on $\Delta {\mathcal {W}} _i$.

Similarly, if the current status is (L, L), we have:

$$\begin{aligned} \Delta {\mathcal {W}} _i \text { for } (L, L) \text { districts } = -V_A^T - V_B^T -\frac{a_1}{2}-\frac{a_2}{2}+\frac{3b_2}{2}+\frac{3b_1}{2} \end{aligned}$$

(48)

Strategy-1 edge weight is then given as (budget cost $b_e$, fairness $f_e$) = ($margin(I_1), \Delta {\mathcal {W}} _i$). This fairness cost is insignificant since the votemandered submap retains the W/L status of both districts, maintaining the same number of wins as the initial submap.

Strategy-2:

In this strategy, we let party B win $I_1$ in campaigned and the votemandered submap and propose perturbations between $I_1, I_2$ such that $I_1$ wins in the second round (mark from $L\rightarrow W$ in the target submap). The target submap is chosen such that the votemandered submap leads to no change in the wins, but the target submap (using original vote shares) secures a votemandering bonus of 1. This is possible when $margin(I_1)$ is smaller than B’s budget allocation in $I_1$. This also suggests that with an increase in B’s budget allocation, A can specifically use Strategy-2 to votemander more efficiently. The change in $\Delta {\mathcal {W}}$ for this setting is exactly the same as for Strategy-1, giving Strategy-2 edge weight as $(b_e,f_e) =$ ($0, \Delta {\mathcal {W}} _i$). Moreover, we don’t expect $\Delta {\mathcal {W}}$ to change a lot here as well, since there is no change in the number of wins where the fairness constraint is concerned, i.e. in the votemandered submap.

Strategy-3:

In this strategy, we let party B win a district in the first round but propose perturbations such that A wins in both the votemandered as well as the target submaps (mark from $L\rightarrow W$ in the second round elections). The difference with Strategy-2 is that here we don’t depend on B’s budget allocation to secure a win, but achieve only via the changes in the district boundaries i.e. the local perturbations. The target submap is chosen such that both the votemandered submap and the target submap have $I_1$ as a winning district. Naturally, here we expect $\Delta {\mathcal {W}}$ to change significantly that of the initial map, as A’s number of wins increases in the votemandered submap.

If $(I_1, I_2)$ have status (L, W) and $V_{A}^1, V_B^1$ are the original vote shares of district $I_1$, Lemma 1 implies:

$$\begin{aligned} \Delta {\mathcal {W}} _i \text { for } (L, W) \text { districts } = -V_A^1 - V_B^1 -\frac{a_1}{2}-\frac{3a_2}{2}+\frac{b_2}{2}+\frac{3b_1}{2} \end{aligned}$$

(49)

where, $a_i, b_i$ are the budget allocations in district $d_i$ by party A and B respectively. Similarly, if the status is (L, L), we have:

$$\begin{aligned} \Delta {\mathcal {W}} _i \text { for } (L, L) \text { districts } = -V_A^1 - V_B^1 -\frac{a_1}{2}-\frac{a_2}{2}+\frac{3b_2}{2}+\frac{3b_1}{2} \end{aligned}$$

(50)

The edge weight is given as ( $b_e$, $f_e$) = ($0, \Delta {\mathcal {W}} _i$), with $\Delta {\mathcal {W}} _i$) computed as above.

Section 5 Details

We include the visualization of local votemandering strategies for both Republican and Democratic parties in Figs. 19, 20, 21 and 22.

Fig. 19

Republican Local Votemandering: The initial map, the created target map, and the strategic investment (here, zero investment followed by all Strategy-2 improvements)

Fig. 20

The Four Stages of Republican Local Votemandering, (with red and blue indicating the districts won by the Republican and Democratic parties, respectively)

Fig. 21

Democratic Local Votemandering: The initial map, the created target map, and the strategic investment

Fig. 22

The Four Stages of Democratic Local Votemandering