Definition 1

A territory is a set S = of voters v ∈ (−1,1). The total population of the territory is the cardinality P_S := |S|.

Definition 2

A territorial unit T = is a subset of the territory T ⊂ S such that S = ∪_iT_i. and T_i ∩T_j = ∅ for i ≠ j. The population in a given territorial unit is P_T := |T|.

Definition 3

A district is a union of territorial units D = ∪T_i ⊂ S.

I am interested in cases where the territory is partition into a set of equal population districts, thus I introduce the following definition:

Definition 4

A valid districting is a set of n_D disjoint districts {D_i} for 1 ≤ i ≤ n_D such that S = ∪_i≤nD D_i and −t ≤ |D_i| −|D_j| ≤ t for 1 ≤ i, j ≤ n_D and t ∈ ℝ.

The quantity n_D is the total number of districts in S. I call t the population tolerance, which allows for variations in population between districts. Characteristically, I will take t ∼ 0.01 × P_S/n_D, such that differences are percent-level. The above definitions do not rely on the spatial distributions of voters. Including geometric data in the problem means imposing a relation between the territorial units (sets of voters), and notions of adjacency and connected, such that the set of territorial units form a connected territory. Such spatial relationships can be intuitively introduced via a lattice model, in which each territorial unit is associated to a single lattice site:

Definition 5

A lattice territory Sn is an n×n lattice on Z² and a lattice territorial unit T_{i, j} is a lattice site (i, j) ∈ S_n, it is characterized by its population P_{i, j} ∈ ℕ. Thus, the total population is P_Sn = ∑_{(i, j)} P_{i, j}.

Then, a district is simply a sub-lattice of the lattice territory Sn, and the definition of valid districting for lattice territories carries over from Definition 4.

Definition 6

A lattice district is a set of territorial units D = {T_i} ⊂ S_n; its population is P _D = ∑_{(i, j)∈D} P_{i, j}.

Definition 7

Territorial units at (i, j) and (k,l) are adjacent if i = k ±1, j = l xor j = l ±1,i = k.

Definition 8

A territorial unit T₁ is reachable from T₂ if there exists a sequence of adjacent territorial units beginning at T₁ and ending at T₂. A lattice district D is connected if any T ∈ D is reachable ∀T_i ∈ D.

Assigning a population value to each territorial unit T _{i, j} ∈ S _n defines a population distribution, however I want to consider population distribution which well model real world population spreads. In this work I focus on a quasi-Gaussian distribution of population much as would be appropriate in a large city in which the population is highly dense towards the center and becomes diffuse at large radial distances.

Realistic population models can be constructed on a lattice S_n with n ∈ Z^odd. To approximate a Gaussian population spread with random fluctuation, I implemented a walker function (see e.g. Shiffman (2012)), as follows: I first designate a starting populating size P_S = |S_n|, each element v_i ∈ S_n takes a value in (−1,1), but I leave these values undetermined at this stage.

I designate the central lattice site (0,0). Then, to implement the walker function, I fix the starting distribution P_T0,0 = P_S and P_{Ti, j} = 0 for (i, j) ≠ (0,0), and the walker function assigns each voter v a fixed number of moves. In each step, each element v ∈ S_n will move from its current unit to any adjacent units with equal probability, with the restriction that the element remains within S_n. Once an element v has taken its prescribed number of moves, it remains in its terminal unit. The move counts across all constituents follow a normal distribution centered at the number of moves needed to reach a corner from the origin. The population spread due to this walker algorithm well approximates a two dimensional Gaussian distribution; an example is shown in Figure 2.

With a working lattice model of population distributions, I now introduce a flexible manner of introducing a partisan bias within the population and defining the premise of voting and electoral events.

Definition 9 The net territory vote (or popular vote) of a territory is N_S:= ∑_v∈Sv.

We assume all voters cast ballots, so each v > 0 corresponds to a single vote cast for the red party with probability v ∈ (0,1). Conversely, each v < 0 corresponds to a vote cast for the blue party with probability |v|. I also assume that the gerrymanderer knows how individuals will vote with certainty, although this could be relaxed in future studies.

Definition 10

Red is said to win the popular vote in S if N_S > 0; conversely, blue wins (red loses) the popular vote if N_S < 0. A territory is called balanced if N_S ≈ 0.

However, rather than the popular vote of the whole territory, what is typically most important is the district-wise overall vote.

Definition 11

The net vote of a territorial unit is N_T= ∑_v∈T v. Similarly, the net vote of district D is N_D = ∑_Ti∈D N_Ti= ∑_v∈Dv.

Definition 12

I say that red wins the district vote for district D_iif N_Di> 0; conversely, I say that blue wins (red loses) the district vote if N_Di < 0. A district is called red-safe if N_Di > w, where w ∈ Z is called the vote tolerance (conversely for blue-safe).

Without loss of generality, I let the gerrymanderer’s party (the proponent) corresponds to positive extremity:

Definition 13

The proponent (opponent) is the party which benefits (loses) from gerrymandering. A territorial unit T is a proponent unit if N_T > 0, an opponent unit if N_T < 0, or neutral if N_T = 0.

Hence the gerrymanderer favors the v > 0 voters, and the ‘positive’ or ‘red’ party.

Since elections are dynamic and inherently uncertain, the gerrymanderer risks losing if they plan to win a district by only a single vote. Hence, the vote threshold w ensures that the gerrymanderer’s party wins a given district with a minimum margin of votes. I typically take w ∼ 0.01×P_S/n_D, where n_D is the number of districts. One could also define w_i district-by-district, such that the requirement is weaker or stronger depending on the demographics of the district.

The distinction between the district vote and the popular vote implies that a given party can lose the latter, while securing the most districts. Typically the most important outcome is the number of districts won by each party. Thus, gerrymandering fundamentally exploits the differences between the local and global properties of distributions.

Definition 14

A source point is a pair E = ((i, j), e) characterized by its location (i, j) ∈ S_n and magnitude e ∈ R of the source. I require that any set of sources {E_i} gives |N_Tk| ≤ 1 ∀T_k ∈ S_n. I call E a red source for e > 0 and a blue source for e < 0.

Source points are located at arbitrary lattice sites, and the voter preference at a given territorial unit T is a function of the distance d from these source points, following a 1/d power law:

Definition 15

The vote contribution ∆T_k,l from a source point E((i,j),e) to the net vote of territorial unit T_k,l, where (i, j) and (k,l) are separated by a distance d(T_{i, j},T_k,l) is

I take a simple euclidean definition of the distance

This implies that the vote contribution from a given source falls linearly with distance d from the source. This will be sufficient for my purposes, however, in principle one could study other power laws or, indeed, consider sources each with different d dependencies.

Note that each source E influences all lattice points in S_n. Moreover, the net vote of the territorial unit T_{i, j} coincident with the source point E_{i, j} is not simply the magnitude of the source e but rather includes contributions from other sources. Because of the 1/d power law, the source points typically represent local maxima of the voter preference, with sign(e) indicating the favored party. It should also be highlighted that in principle two source points E₁, E₁ could be located at the same lattice site, say E₁ = ((i, j), e₁) and E₂ = ((i, j), e₂), however in this case the two sources can always be replaced with a single source as follows:

In a sample execution, I select the territorial units immediately left and right of the origin (0,0) to serve as blue and red source points, respectively. Specifically, I consider a set of two sources {E_B, E_R} with E_B = ((1,0),−1) and E_R = ((−1,0),1). The combination of the symmetric quasi-Gaussian population distribution, as shown in Figure 2, and the sources {E_B, E_R} produces the voter preference distribution shown in Figure 3. The red/blue intensity indicates the magnitude of the net voter preference N_Ti ∈ (−1,1), with the center of these colored regions corresponding to the positions of the two source points E_B and E_R. In my subsequent analysis I shall consider two specific benchmark models with certain source point distributions. Table 1 specifies these benchmark models:

Note that the partisan spread of model #1 is illustrated in Figure 3 and models #2- #5 are shown in Figure 4. These models demonstrate that the code can implement a wide variety of voter distributions.

Definition 16

A connected component C ⊆ D is a (non-empty) set of T_i ∈ D such that for T_i ∈C then T_j ∈C if and only if T_i is reachable from T_j.

A district can be decomposed into connected components: D = ∪_i≤rC_i, where r is the number of connected components. If any territorial unit in D is reachable from all other territorial units in D, then C = D and r = 1, so D is connected. The number of connected components is important for the analysis of the spatial distributions arising through the algorithms studied.

Definition 17

The target population P_D± := (P_S/n_D ± t) for n_D the designated number of districts.

This requirement ensures that all districts have approximately equal populations. The value of P_D ± is computed before the algorithm is executed and used as an input. For my studies of redistricting, I take t = 0.05×P_S/n_D, unless stated otherwise.

I assume nD ~ ϭ(1), and as a characteristic value I use n_D= 5. The algorithm iteratively assigns single unassigned units to a district, one district at a time.

Definition 18

An unassigned unit is a territorial unit not yet assigned to a district. I denote the set of unassigned units U.

Once the algorithm is satisfied with the composition of a given district it proceeds to form the next district, until all n_D districts are formed. Specifically, each district should satisfy the population threshold

P _D− ≤ P _Di ≤ P _D+

and all district except the last (which much have an opponent bias if the vote is balanced) should satisfy the vote threshold

N_Di > w.

For an Sn territory I initially have n ² unassigned territorial units, which I enumerate {T_i} for 1 ≤ i ≤ n ² and n_D(empty) districts. Each T _i stores the values of N _Ti to evaluate how many more votes for a particular party are expected from each T_i. The sign of N_Ti indicates the net partisan affiliation of the territorial unit. As territorial units are assigned to districts by the algorithm, they are deleted from U.

Editor's note: below, T^₁ indicates

I implement the FH packing algorithm by first sorting the territorial units in order of decreasing net vote N _Ti , using a quicksort method [2], and I relabel the elements of the ordered set {Tˆ _i } with 1 ≤ i ≤ n ² . Thus Tˆ ₁ corresponds to the strongest unit vote for the opponent (blue) party, similarly Tˆ _n² is the strongest unit vote for the proponent party. More generally, the strongest unassigned opponent unit is T _i ∈ U such that N _Ti ≥ N _Tj for all T _j ∈ U, or equivalently it is Tˆ _i with i the smallest integer index in the set U. Conversely, Tˆ _i with i the largest integer index in U is the strongest unassigned proponent unit.

The algorithm takes an unformed district, which is initially D_i {}, and iteratively adds first the strongest the unassigned proponent unit followed by the strongest the unassigned opponent units until P_D > P_D−. The algorithm then calculates the district vote N_Di and compares it to the vote threshold w. If N_Di > w and P_D < P_D+ then the district is complete and the algorithm repeats this process for the remaining districts, with the exception of the last district.

It may be the case, however, that in forming a given district once the district satisfies P_D > P_D−, the district vote is calculated to be less than the vote threshold N_Di < w. In this case the algorithm adds the strongest remaining unassigned proponent units until N_Di > w, at each step checks that P_D < P_D+. Once the district vote is sufficiently large, the district is complete. Additionally, when the population limit is exceeded P_D > P_D+ my algorithm will remove the last united added and try the next in the ordered list until it identifies an addition to the district that does not violate the population limit. For large vote thresholds w or small population thresholds t, this districting algorithm may fail (i.e. no district satisfies simultaneously population and vote thresholds), but this is rarely a problem for percent-level w and t.

As alluded to above, the criteria for the last district must be different. If the popular vote is balanced vote, as I assume here, then it is impossible to arrange for all districts to favor the proponent party. Thus, it is expected that for the n_Dth district that N_Dn < 0. The final district is identified with the remaining unassigned territories after construction of the (n_D − 1)th district. By design, the final district is primarily comprised of moderate voters. The only requirement on the final district is that it satisfies the population constraint P_D− ≤ P_Dn ≤ P_D+. In the case that P_Dn > P_D+, the proponent-favoring population units on the exterior of the final district will be transferred to adjacent districts. If P_Dn < P_D−, then the opponent-favoring population units in other districts and adjacent to the final district will be transferred to the final district.

Before examining whether the districts of the Friedman and Holden method are connected, I first shall look to quantify what degree of advantage this gerrymandering procedure gives to the proponent party comparing to a non-partisan model of districting. To assess the impact of gerrymandering via the Friedman and Holden method I take a set of voters and associate each to territorial units which are lattice sites of 21×21 lattice S₂₁, with total population^∗ P_S ≈ 4700 (up to 0.5% fluctuations). This results in a set of territorial units with fixed populations and partisan biases {T_i}.

I then implement the Friedman and Holden algorithm on the set of voters (which neglects all spatial data) and partition the territory into n_D = 5 districts. Following the Friedman-Holden method, I order the units {T_i} by extremity and assign units with opposite partisan biases to districts {D_i} in a manner that benefits the proponent party and gives approximately equal population districts. Since the walker function introduces random fluctuation in the approximately Gaussian population distribution, each run returns a different redistricting. Thus I can assess the impact of gerrymandering for a given set of source points via a statistical approach by multiple runs of the algorithm.

Specifically, I generate a set of different redistricting plans on 30 different S₂₁ lattice population models with 5 benchmark source point placements (as shown in 3 & 4) and partition the territory into n_D = 5 districts. I calculate the average net vote per district N_Di and the predicted number of safe proponent districts (#_safe). In Table 2, I show the average net vote N_Di in each district (where the districts are enumerated by order of construction) following redistricting via the FH method and averaging over 30 runs.

I want to compare these results to some “fair” partition of the population. Since the population has been generated to approximate a two dimensional spherically symmetric Gaussian distribution, that means that any spherically symmetric partition of the population which does not take into account the partisan bias can be considered a non-partisan districting. Specifically, I shall construct a non-partisan n_D = 5 districting by allocating the central cells to District 1 and then partitioning the set of territorial units not assigned to District 1 to create Districts 2-5. I choose to partition Districts 2-5 by simply drawing the district lines along x = 0 and y = 0 and assigning the territorial units on the borders to the adjacent district in the clockwise direction. The size of District 1 is fixed such that the 5 territories have approximately equal populations, up to 5% deviations. The resulting districts are illustrated in Figure 6.

To assess the impact of gerrymandering, I compare predicted election results for the case of aggressively gerrymandered districts (as determined by my algorithm) to the net vote for the symmetric districts outlined above. I generate 30 population distributions on S₂₁ and calculate both the average net vote per district N_Di and the predicted number of safe proponent districts (#_safe), the results are shown in Table 3.

From comparison of Table 2 and 3 it is clear that FH packing significantly impacts the electoral outcome. However, as I show in the next section, the districts constructed are generally disconnected and therefore typically legally prohibited.

Since the Friedman-Holden method includes no spatial data, one might expect disconnected districts; however, I wish to quantify the failure of this approach. I take the districts constructed in Table 2 and output the assignments of the territorial units and identify the number of connected components in each district. For illustrative purposes I show one (of the 30) district compositions output by the algorithm, immediately one observes that the districts are highly disconnected in all cases.

To quantify this statement, I take the outputs of the 30 runs of FH packing on S₂₁ generated previously and calculate the mean number of connected components for each district (labelled D2 to D5) and the mean over all districts for the 5 benchmark source point models. The results are displayed in Table 4.

I find that the approach of Friedman & Holden (2008) typically outputs districts with ∼ 4 components. Importantly, disconnected districts are legally prohibited, thus, while the Friedman-Holden method is simple and easy to implement, it is too simplistic to give a realistic model of redistricting. It is critical that algorithmic approaches take into account the spatial distribution of voters.

I first discuss the general construction of districts, with the exception of the final district. Suppose there are x unassigned territorial units {T_i} for 1 ≤ i ≤ x (for District 1: x = n²). Similar to the FH algorithm, the first step is to sort, via quicksort, the unassigned units in order of decreasing net vote N_Ti and relabel the ordered set {Tˆ_i} with 1 ≤ i ≤ x. To form each new district the algorithm connects the two most oppositely polarized unassigned units (i.e. Tˆ₁ and Tˆ_x) via the shortest path that avoids all existing districts. I use a standard Grassfire algorithm Bium (1964) to remove assigned units when determining the shortest path. In all of the cases I consider, the total population of the path between Tˆ₁ and Tˆ_x is well below the target population P_D±.

While P_Di < P_D−, the algorithm will repeatedly add to the collection the most extreme territorial unit that is unassigned and adjacent to the set. If the net vote of the district does not sufficiently favor the proponent party, as determined by a vote tolerance parameter w (cf. Def. (12)), then the algorithm will successively add proponent units to the collection. Once the net vote favors the proponent, the algorithm adds opponent units to balance the vote. After adding c units to a given district, the algorithm fixes the district when ∑_i≤c+1 P_Tˆi > P_D−. It then checks that ∑_i≤c P_Tˆi < P_D+. If this check fails, the final unit added, T_c, is replaced with an alternative adjacent unit, until the above is satisfied. After a connected set is validated as a district, the algorithm recurs on the remaining sorted list of territorial units. In the end, I expect the algorithm to produce districts in order of decreasing polarity, with the proponent vote being stronger than the opponent vote.

The remaining unassigned units after the construction of n_D − 1 districts are typically disconnected, thus one can not simply identify the remaining voters with the final district. Producing a valid redistricting requires some further manipulation of the districts formed, as I discuss in the next section. This is a feature of all algorithms which do not track the subsequent implications to later districts, whilst assigning territorial units.

Once all priorities are assigned, the algorithm sorts the list of population units in order of decreasing priority. Because negative values of N_T indicate a net vote for the opponent, the population unit with the highest positive priority at the beginning of the sorted list is added to the collection D₁ that will eventually become the first district. Then, the algorithm searches over all population units adjacent to D₁ and adds the highest priority unit to D₁. This last process is repeated until ∑_T∈D1 P_T > P_D−. After this first district is constructed via the Saturation Packing algorithm, all subsequent districts are created using the SRFH Packing algorithm.

In Figure 8, I present six example outputs of my working code in which I partition a 21×21 lattice into five districts. The left most panel shows the voter distribution (two cases: top and bottom) and the five panels to the right show the gerrymandered districts output by the code. My code is most effective for populations of oppositely extreme partisanship situated in close proximity to one another, an example of which for n_D = 5 is shown in the lower panels of Figure 8.

In both cases of Figure 8, districts 1-3 illustrate the pairing of the most highly partisan subpopulations such that the proponent vote overpowers the opponent vote, as advocated in Friedman & Holden (2008). The lower example fixes the two partisanship source points to be proximal and with maximum extremity, in order to maximize the connectedness of the most polar districts. Even with this idealized setting, the outer districts are highly non-compact. This suggests that a raw algorithmic approach of packing and cracking might be easily detected, or constrained, via appropriate measures.

In future work, it would be interesting to explore certain generalizations of the above algorithms, for instance, the prospect of incorporating third-party candidates and nonvoting electors. Furthermore, my current algorithm assumes complete knowledge about the population spread and expected vote outcomes, but in reality, a gerrymanderer has imprecise information about these distributions, which leads to uncertainty in the voter preference distributions. Voter uncertainty can be implemented by replacing v ∈ (−1,1) with a confidence interval v₀ ± c, where v₀ is the expected value, such that v = (v₀ − c, v₀ + c) ⊂ (−1,1). One might also implement ‘voter shocks’ to model swings in the popular vote by ϭ(10%) after redistricting is complete, as discussed in Friedman & Holden (2008). Both of these extensions directly affect the required vote tolerance w, since if w during redistricting is not sufficiently large, the proponent party may lose the election.

The reassignment of power to the electorate is the fundamental strength of representative democracies. Political gerrymandering, if left unchecked, threatens to undermine our democratic systems. Since gerrymandering issues can be formulated as well-stated mathematical and computational problems, one can develop tools and tests to identify and inhibit these practices. Towards this goal, I have developed in this work a lattice model of realistic voter distributions with which to study the process of gerrymandering. I used my lattice models to show that the highly aggressive approach of Friedman & Holden (2008) can be effectively constrained by requiring districts to be connected. Furthermore, I constructed an aggressive gerrymandering algorithm that accounts for the spatial distribution of voters and demonstrated that this approach can be effectively constrained by compactness requirements. Notably, while connectivity is legally mandated, compactness is not. Thus, my work provides quantitative support in favor of implementing some legally mandated compactness requirement for redistricting to inhibit these aggressive gerrymandering strategies.

I am currently extending this research on gerrymandering algorithms by developing a fair districting algorithm. Indeed, the ultimate solution to the gerrymandering problem is not just a detection method but a more equitable districting alternative. It has been shown that no partitioning of a state population into a finite number of voting districts can be entirely fair. Even though election fairness is limited, I can still maximize this fairness by employing a genetic algorithm. Borrowing from the principles of evolution and natural selection, this genetic algorithm evolves a population of increasingly equitable districtings over many generations. By analyzing the throughput of the genetic algorithm, I can better understand the largely uncharted process of determining fair representation for a fair democracy.