Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering

1 Introduction

The question of how to aggregate various peoples' preferences and choose a single option has existed for millennia and is a fundamental issue in social choice theory and practice. Since the early days when humans institutionalized their decision making, manipulation came along with it [Staveley, 1972], as people looked for ways to change the outcome more to their liking, and leaders looked for ways to reduce their rivals' power [Kagan, 1961].

Jumping several centuries ahead, during the late middle ages various European kingdoms established assemblies which included representatives from various areas of their country: the English parliament, the French Estates General, and others. In those assemblies which survived to become significant policy bodies, the issue of which areas received representation became crucial. In Britain, for example, the parliamentary districts still reflected medieval population distribution until the Great Reform Bill of 1832. But just as Britain was trying to solve its district allocation problem, across the Atlantic, American politicians were realizing the potential power that comes with the ability to divide a state into its districts. In 1812, Massachusetts governor Elbridge Gerry gave his name to the practice of gerrymandering - creating oddly shaped districts for political gain.

Dividing a geographic area (e.g., a state into electoral districts; municipality lines for allocating taxes) into subareas subject to constraints is a problem with many possible solutions, and one of them needs be selected. Gerrymandering is a control problem, in which the agent in charge of the division optimizes it for their personal preferred outcome, even if there is a more natural one. From here on we will use political nomenclature, but note that all the results and observations apply to dividing any geographic area with resources (partisan voters are only one example) between agents in a way that can be fair, but can also be highly biased.

There has been much research concerning gerrymandering in the United States, and since the 1965 Voting Rights Act particular attention has been given to minority representation issues. This interest has accelerated in the past two decades (and even more so in todays' political atmosphere), with much effort devoted to denunciations of gerrymandering, and arguing that it is a danger to the US political wellbeing [Klaas, 2017; New York Times Editorial Board, 2017]. However, despite substantial effort, it is still not clear what constitutes a "good" or "fair" district map [Wang, 2016]. Is it district compactness? Is it population homogeneity [Wasserman, 2018]? But the main criticism of gerrymandering seems to be that it produces results that are unrepresentative of the overall population's desires and preferences [Nurmi, 1999].

In parallel a different dynamic is taking place in the US: for a variety of reasons, individuals are residing near people with similar party affiliation. In particular, supporters of one party cluster in urban areas, while rural areas are becoming the domain of their political opponents [Bishop, 2009]. Many commentators are mixing this with the negative effect of gerrymandering [Enten, 2018; Rumi, 2017].

We examine the relation between gerrymandering and partisanship distribution. We explore several theoretical insights, and construct a simulation tool and an algorithm to find highly gerrymandered district divisions. We propose a novel metric, gerrymandering power, which measures how much gerrymandering can make a party powerful beyond its vote share in the population. We work with a synthetic grid map in order to focus more on the effect of a party's vote share and the distribution of its voters on its gerrymandering power.

Contrary to common opinion [Wang, 2013], our results suggest that as partisan separation grows and urban voters cluster, the rural party's ability to gerrymander drops. Once a certain (fairly low) urban party concentration is exceeded, a party's gerrymandering power seems to depend almost entirely on the density of the urban centre and not on its share of the population. As partisan separation grows, the gerrymandering power of both parties converges so that the parties are limited in their ability to gain much more than what their share of the population warrants, bringing about a more representative outcome. We also observe complex effects in close elections with moderate concentration levels. Moreover, our results suggest a basic asymmetry between the gerrymandering power of the urban and rural parties, wherein the rural party has a stronger gerrymandering ability.

2 RelatedWork

Research on gerrymandering has been done, throughout the years, from sociological vantage points [Lublin, 1997], historical ones [Engstrom, 2006; Butler, 1992], and, particularly since the 1965 Voting Rights Act, legal ones [Schuck, 1987; Issacharoff, 2002; Friedman and Holden, 2009]. Naturally, however, it has been mainly explored in the political science arena [Erikson, 1972], primarily based on analysis of past elections [Grofman et al., 1997; Tangian, 2010; Felsenthal and Miller, 2015] - trying to figure out if it occurred, and trying to calculate some measure of its effects. In the past few years the computational social choice community has also taken interest in this topic, on issues such as worst case analysis of how districts effect voting rules [Bachrach et al., 2016], and the computational complexity of gerrymandering [Lewenberg et al., 2017; van Bevern et al., 2015]. Recently, [Pegden et al., 2017] suggested a "cut and choose"- like mechanism to divide districts in practice.

The work of [Lewenberg et al., 2017] is closest to ours, they also provide an algorithm for gerrymandering over a graph. Unlike our algorithm, their greedy algorithm produces districts which may differ in population by up to 6500%. However, most US congressional districts must be within 1% of each other, and that algorithm will fail with this constraint.

Finding an optimal gerrymandering division of a geographical area has long been viewed as a planar graph related problem, in which precincts (which are, practically, our undivisible smallest unit) are nodes in the graph, and one looks for cuts in the graph that will result in sub-graphs with particular properties (e.g., contiguity). [Dyer and Frieze, 1985] hypothesized that even the complexity of finding a division of the graph to equal-sized connected parts (akin to contiguous, equal population districts) is NP-hard, and had several related results which seem to indicate that this is, indeed, the case. Further papers have further tried to attack this problem (e.g., [Yang, 2014]), but without significant breakthrough. [Apollonio et al., 2009] limited themselves to the grid, as we do, and found some bounds on gerrymandering there.

The discussion of algorithmically finding optimal districts has been with us since it became feasible to consider such an option in the '60s (see summary in [Altman, 1997]), and work on it has gone hand-in-hand with considering what are metrics to measure gerrymandering, and avoiding such settings (see [Wang, 2016; Grofman and King, 2007] on the various metrics that have been suggested). [Puppe and Tasn´adi, 2008] axiomatize a districting division that strives to optimize gerrymandering for one of the parties. More practically, [Fifield et al., 2018], tried to produce a random sample of district maps under some constraints, suggest a method that takes an existing partition of the graph, and slowly changes it, as it slowly "swaps" precincts bordering on the dividing line between districts. To achieve a similar goal, [Chen and Cottrell, 2016] take a more classic local search approach.

The observation that voter distribution is not uniform, and instead follows a clustering of one party into dense cities, was made prominent by the book "The Big Sort" [Bishop, 2009]. Following research has corroborated this observation [Chen and Rodden, 2013; 2009].

3 Model

We use a graph-theoretic formulation of the districting problem. In our formulation, a state is represented by a graph G, where the vertex set V (G) contains a vertex for every precinct, and the edge set E(G) contains an edge between every pair of precincts that share a physical boundary. Because the map of a state is two-dimensional, we assume that G is planar. Let nv denote the number of voters in vertex v. For simplicity, we assume that voters are divided between two major political parties, P1 and P2. For P ∈ {P1, P2}, let nPv denote the number of voters of party P in vertex v, and let N P = ∑v∈V (G) nPv denote the total number of voters of party P. Let N = N P1 + N P2 denote the total number of voters. We use αP1 = N P1 /N and αP2 = N P2 /N to denote the proportional vote shares of the two parties.

Given a desired number of districts K ∈ N, the districting problem is to partition the graph G into K vertex-disjoint subgraphs G1, . . . ,GK (districts) that satisfy a number of constraints. We focus on two constraints that exist widely in practice.

1. Contiguity. For each district k ∈ [K], Gk must be a connected subgraph of G.
2. Equal Population. The total number of voters in each district should be approximately equal. Formally, given a tolerance level δ, we need that for each k ∈ [K],

We say that a districting is valid if it satisfies both these constraints. Let R denote the set of valid districtings. There are additional criteria that districting should satisfy such as compactness of districts, preservation of existing political communities, and racial fairness. However, we overlook these criteria, as there is still work to be done on formulating a consensus on their quantitative definitions. Given a districting R ∈ R, we say that party P wins district k if it has a majority in the district: ∑v∈V (Gk) nPv > (1/2) · ∑v∈V (Gk) nv 1 . Let KP (R) denote the number of districts won by party P in districting R, and let σP (R) = KP (R)/K.

There may be many solutions to the districting problem satisfying the contiguity and equal population constraints. The goal of gerrymandering is to find the districting that maximally favors one party. In this work, we focus on partisan gerrymandering (henceforth, simply gerrymandering) where the goal is to maximally favor a given party. Partisan fairness would require choosing a districting R in which σP (R) is as close to αP as possible. We define the gerrymandering power of party P to be maxR∈RσP (R) - αP , i.e., the maximum boost the party can get through gerrymandering above their proportional share of the districts. Note that negative gerrymandering power implies that the voters are distributed in such a way that the party falls short of its proportional share of the districts even with maximum gerrymandering.

In this paper, we make some simplifying assumptions. First, we assume that graph G is an n × n grid. Grids are among the simplest planar graphs that still present nontrivial challenges. Second, we assume that each vertex of the grid has an equal number of voters: let nv = T for each v ∈ V (G), for a sufficiently large constant T . Third, we mandate that all districts be of equal size, i.e., we set δ = 0 in the equal population constraint. Finally, we assume voter preferences to be fixed. While these assumptions drag our model a bit farther from reality, they allow us to focus on the dependence of a party's gerrymandering power on its vote share and the geographic distribution of its voters. As we discuss in Section 7, we believe our observations would not change qualitatively when moving to general graphs as the key insights from Sections 4 and 6 are applicable to general graphs.

4 AWorst-Case Viewpoint

Our goal is to study the effect of voters' geographic distribution on the gerrymandering power of the parties. In this section, we take a worst-case point of view: How does the gerrymandering power of a party change with its vote share when its voters are distributed in the worst possible way? Formally, given a party P and its vote share αP , we want to analyze the maximum fraction of districts the party can win in the worst case choice of {nPv }v∈V (G) that satisfies 0 ≤ nPv ≤ T for each v ∈ V (G) and ∑v∈V (G) nPv = αP · N. For the grid graph, N = n2 · T is the total number of voters.

We begin by making an observation in the large-graph limit. Imagine the n×n grid embedded in a bounded convex region. As n → ∞, one can treat the graph as a continuous convex region in R2 endowed with two measures µP1 and µP2 that represent how the voters of the two parties are distributed across the region. Here, we show there is a sharp transition where a party can win every district or no district depending on whether it has a majority or a minority vote share.

The high level idea is as follows: When αP < 1/2, P wins no districts if its voters are uniformly spread, i.e., if it has αP fraction of the voters in each individual vertex. When

1 We break ties in favour of the gerrymandering party.

αP ≥ 1/2, we invoke a generalization of the popular Ham Sandwich Theorem [Sober´on, 2012; Karasev, 2010], which states that given d measures in Rd , there exist K interiordisjoint convex partitions that divide each measure equally. Applying this to measures µP1 and µP2 in R2 , we get a valid districting in which party P has a majority in every district.

Theorem 1. Suppose an n × n grid is embedded into a bounded convex region. As n → ∞, for every K ∈ N, party P (which controls the districting) can guarantee winning every district if its vote share is αP ≥ 1/2, and wins no districts in the worst case if its vote share is αP < 1/2.

When n is finite and αP < 1/2, uniform voter distribution still remains a worst case for party P regardless of the number of districts K, and prevents the party from winning any district. However, the case of αP ≥ 1/2 becomes more finegrained. For a constant K, increasing the graph size (i.e., increasing n) gives the party more gerrymandering power. We illustrate this using the case of two districts (K = 2). For n = 2 (i.e., in a 2 × 2 grid), it is easy to show that a party needs 75% vote share to win both districts in the worst case.

Proposition 1. For n = K = 2, if party P controls the districting, in the worst case for them the following hold.

1. If αP ≥ 3/4, the party wins both districts.
2. If 1/2 ≤ αP < 3/4, the party wins a single district.
3. If αP < 1/2, the party wins no districts.

However, as n increases, we can show that the required vote share for winning both districts quickly converges to the 50% limit indicated by Theorem 1. In the next result, we only consider even n because creating two districts of equal size is impossible when n is odd.

Theorem 2. For even n and K = 2, if a party controls the districting and their vote share is at least 1/2 + 1/n, then they can win both districts.

Proof. Consider an n × n grid. Suppose party P has vote share αP ≥ 1/2 + 1/n. We want to show that there exists a valid districting in which the party wins both districts.

To take care of the contiguity and equal population constraints, let us impose a specific structure on the districting. We assign the top row consisting of n vertices to district 1, and the bottom row consisting of n vertices to district 2. This leaves n columns of height n - 2 each, which we call strips. Note that every solution in which n/2 strips are assigned to each district gives a valid districting. We want to show that one such assignment results in party P winning both districts.

Suppose this is not true. Consider the assignment that maximizes the minimum vote share of party P across the two districts. Without loss of generality, suppose party P wins district 1, but loses district 2. Let nP1 , nP2 , and nPt denote the number of voters of party P in district 1, district 2, and a strip t, respectively. Recall that the total number of voters is N.

Since party P loses in district 2, which has N/2 voters, we have nP2 < N/4. Hence, there exists a strip t in district 2 such that nPt ≤ nP2 /(n/2) < (N/4)/(n/2) = N/(2n).

On the other hand, we have nP1 = αP N - nP2 > αP N - N/4. Even after discounting the top row which has N/n voters, there must exist a strip t′ in district 1 such that

(1)

Let us consider the (valid) districting obtained by exchanging strips t and t′ between the two districts. We observe that party P still wins district 1 because by losing strip t′ , it loses at most N/n of its own voters, and

where the last inequality follows because αP ≥ 1/2 + 1/n. On the other hand, district 2 now has strictly more voters of party P because it loses at most nPt < N/(2n) such voters, but gains at least nPt′ such voters. From Equation (1) and the fact that αP ≥ 1/2 + 1/n, it readily follows that nPt′ ≥ N/(2n). This completes our proof.

While the party with a majority vote share can easily gerrymander large graphs when K is fixed, it is much more difficult to do so when K is large as well. At the extreme, when K = n2 , it is easy to show that party P wins max(0, 2αP -1) fraction of the districts in the worst case. This fraction is zero for αP ≤ 1/2, and linearly increases to 1 as αP goes to 1. This is in sharp contrast to Theorem 2, where the fraction jumps from 0 to 1 when going from αP = 1/2 to αP = 1/2 + 1/n.

While our results are for the extreme cases (Theorem 1 holds as n goes to infinity and Theorem 2 holds for K = 2), the worst-case viewpoint leads to a key insight: a party's gerrymandering power significantly depends on the relationship between n and K. While large graphs are easy to gerrymander, a large number of districts make it hard to gerrymander.

5 Simulating Optimal Gerrymandering

We now conduct an empirical study of the gerrymandering power of political parties. Instead of the worst case partisanship distribution we considered in the previous section, we adopt a more realistic model based on the urban-rural divide referenced in the introduction. We also use grid graphs with a less extreme ratio of the graph size to the number of districts (in fact, we use numbers that are similar some states within the American Congressional system).

5.1 An Urban-Rural Model

To model an urban-rural divide on a graph G, we use two parameters. The fraction of the urban party U's voters, αU ∈ [0, 1], and the strength of an urban-rural divide parameter φ ∈ R≥0 . Given G, φ and αU , we use the following process:

1. Set all voters in G to be for the rural party R.
2. Pick a set of urban centres C ⊂ V randomly. For v ∈ V , let d(v) be the minimum distance of v to any c ∈ C.
3. Pick a node v (with at least one R voter left) with probability proportional to 1 1+(d(v))φ .
4. Convert one of its R voters into a U voter.
5. Repeat steps 3 and 4 until the fraction of U voters in G is at least αU .

See Figure 1 for sample heat maps generated by this process. Note that in step 3, we pick a node with a probability that decays polynomially in d(v); we also conducted experiments with exponentially decaying probabilities and did not notice a qualitative difference in our results.

5.2 An Algorithm to Gerrymander

Our starting point for an algorithm for optimal gerrymandering is to formulate a Mixed Integer Linear Program (MILP), which uses network flow constraints to ensure connectedness of the districts. Unfortunately, this program does not scale well, and takes hours on grids with a hundred nodes. Let us call the MILP approach algorithm A. We devise a bottom-up algorithm B, which uses A as a subroutine to optimally solve small sub-problems with at most β nodes. To divide G into K components in favour of party P, algorithm B works as follows:

1. Find an arbitrary division of G into K connected components (G1 · · ·GK) of equal or near-equal size.
2. Randomly pick two adjacent components Gi and Gj.
3. Merge them into a new component GM = Gi ∪Gj. If |V (GM)| ≤ β, use algorithm A to optimally gerrymander GM into K′ districts, where K′ is the number of districts in Gi and Gj. Otherwise, let the districting of GM be dictated by the districtings of Gi and Gj .
4. Repeat steps 2 and 3 until there is one component left.

Finally, we chain B with itself by feeding the districting found in one execution of B to step 1 in the next execution of B, and repeating until there are no improvements. We call this algorithm B+. While the algorithm is not guaranteed to find an optimal gerrymandering, we see (see Section 5.4) that it finds highly gerrymandered districting on large instances; in contrast, algorithm A fails to work for large instances.

In order to find a districting for step 1 in the first execution of algorithm B, we simply use our MILP but without an objective function, which is reasonably fast. Once we find one valid districting, we can find more for different executions of B+ using an iterative process I, where we take a pair of adjacent districts Gi and Gj, find one node from each district such that exchanging them gives another valid districting (if possible), and repeat this for a number of steps.

5.3 Simulation Setup

For all of our experiments we use a 16 × 16 grid graph (i.e., 256 nodes) with 10 voters per node, and divide it into 32 equal sized districts. This problem size is about the same as Vermont's state senate (270 precincts and 30 districts). For the urban party vote share, we use αU ∈ {0.40, 0.45, 0.48, 0.5, 0.52, 0.55, 0.6}, and for the strength of the urban-rural divide, we use φ ∈ {0, 1, . . . , 10}. Using our urban-rural model, we generate 20 graphs G for each combination of αU and φ, each with a randomly chosen urban centre (more centres would be too crammed with n = 16). For each G, we run B+ 20 times to find the best gerrymandering for each party 2 . To generate the 20 sufficiently different starting points, we use process I with 100,000 swaps. We use IBM CPLEX for solving the MILP in algorithm A, and use β = 16, i.e., we solve instances with at most 16 nodes optimally using algorithm A. Overall, when provided with a starting point, algorithm B+ was able to solve any of our instances within 2 minutes. Finding a starting point did take significantly longer, but since all of our experiments were on the same graph structure, this point could be reused for generating starting points for all our problem instances.

5.4 Some Basic Results

In Section 4, we show that for K = 2, a party needs at least 50% vote share to guarantee winning at least one district in the worst case. In our simulations with a moderate urbanrural divide (φ = 5), we observe that just 26% vote share allows a party to win one district with n as low as 8.

For most combinations of αU and φ, our approach was able to secure more districts for the gerrymandering party than its proportional vote share, resulting in a positive gerrymandering power. We also tested our algorithm on several examples (located on the grid), where we knew the optimal gerrymandering outcomes. Our algorithm was always able to get at least 60% of the optimal. We note that these examples had a unique optimal outcome, so discovering it was difficult.

6 Simulation Results

We now describe the results of our simulations, and explain several important trends based on three key figures. Figure 2 shows the gerrymandering power of the two parties for different vote shares as a function of the urban-rural divide. Figure 3 focuses on the particular trends in a highly unbalanced election (αU = 0.4) and a balanced election (αU = 0.5).

2 For fixed values of φ and αU the standard deviation over the 20 maps was always under 1.4 (over 32 districts).

6.1 Highly Unbalanced Elections

In highly unbalanced elections with vote share difference of at least 20% (e.g., see Figure 3), we see an expected trend. At φ = 0, when the voters are spread uniformly at random, the party with a majority vote share holds a majority in most precincts despite the randomness in our generation process. This makes it trivial for the majority party to gerrymander to win almost all districts, but difficult for the minority party to gerrymander well. In fact, the minority party has a negative gerrymandering power, i.e., it wins less fraction of districts than its vote share despite gerrymandering.

However, as the voters of the minority party concentrate, this disparity reduces. The majority party sees a reduction in its gerrymandering power as it can no longer avoid forming districts where the minority party wins due to its concentrated voters. Similarly, the minority party finds it easy to gerrymander to win a larger number of districts. At the extreme, with φ = 10, it is able to win almost half the districts despite being at a 20% vote share disadvantage.

6.2 Close Elections

Arguably, the more interesting elections in practice are the close elections with vote share difference of less than 20%. The trend is very different in these elections. For instance, consider Figure 3 with αU = 0.5. At φ = 0, the voters are spread uniformly at random, which makes it easy for the gerrymandering party to put precincts with a slight majority together with precincts with a slight minority to form many districts with a slight majority, leading to a high gerrymandering power. Further, this holds for each party due to symmetry.

As the divide strengthens, the rural party witnesses a diminishing gerrymandering power as in the case of unbalanced elections. However, an interesting pattern emerges in the gerrymandering power of the urban party. As φ increases, we see that the gerrymandering power decreases suddenly till φ = 2, then increases slowly, and finally levels out, forming a trough.

We do not believe this trough to be an artifact of our algorithm B+. On a smaller number of instances, we ran the iterative algorithm I for several hours to come up with hundreds of thousands of districting plans, and chose the most gerrymandered of them. A similar pattern again emerges, though this approach returns less gerrymandered solutions than B+, making the pattern a bit less emphasized.

We hypothesize that with a moderate φ, there are still many urban voters in deeply rural regions, which constitutes a lot of wasted votes for the urban party as it is unable to put them together with other urban voters and form a district it can win. However, as the concentration further increases, these voters are brought closer to the urban center, allowing the party to utilize their votes to win a few additional districts.

Due to a similar reason, when the rural party has a minority vote share (say αR = 0.45), we see an inverse pattern with its gerrymandering power initially increasing, and then slightly decreasing, thus forming a peak. Again, this is because with a moderate φ, the urban party has a lot of wasted votes within rural regions, which helps the rural party gerrymander well.

6.3 Concentration Leads to Fairer Districting

Interestingly, Figure 2 shows that across all vote shares, the gerrymandering power of both parties converges to 1/16 (i.e., 2 more districts compared to the vote share with K = 32) as φ goes to 10. In fact, the convergence seems to begin at a fairly low concentration level (around φ = 2.5). That is, at an extreme level of concentration, both parties are able to gerrymander and win about two more districts than their proportional share (dictated by their share of the votes).

Intuitively, at extreme concentration levels, there is a densely packed region of urban voters near the urban centre, a densely packed region of rural voters surrounding it, and a much sharper boundary in between (Figure 1). Irrespective of which party gerrymanders, districts near the urban centre are won by the urban party, and districts densely packed with rural voters are won by the rural party. This ensures each party approximately its proportional share of the districts. The only control that the gerrymandering party has is near the boundary, where it can merge its own voters with voters of the opponent, creating districts with a slight majority. This is reflected in the urban-gerrymandered and rural-gerrymandered districting shown in Figure 1. Since both parties control the same boundary region when they gerrymander, their gerrymandering power becomes identical with such extreme concentration. Further, because the number of vertices on the boundary is a small fraction of the total number of vertices, this gerrymandering power is relatively small.

6.4 ARural Advantage

Finally, we observe that the gerrymandering power is not symmetric between the urban and rural parties. The rural party almost always has a higher gerrymandering power than the urban party, even in the case of proportional vote split (Figure 3). This asymmetry is not surprising. As Figure 1 shows, the distribution of voters is also not symmetric; the urban party's voters congregate together in a tight area, while the rural party's voters surround them on all sides.

7 Discussion

Our definition of the gerrymandering power of a political party, the theoretical model for a worst-case analysis, and our empirical observations raise many interesting open questions.

On the theoretical level, our results consider extreme cases of an infinite graph or just two districts. Solving the case of a finite graph with more than two districts is an immediate open question. We also note that while we use convex districts in Theorem 1, our proof of Theorem 2 uses districts that are far from convex. An interesting direction is to incorporate a formal requirement of district compactness into our framework.

Extending our techniques to large real-world planar graphs is clearly the most interesting future direction. For instance, in Theorem 2, how does the vote share needed to win both districts change in non-grid graphs? Insights from our simulations lead us to believe that in close elections on real graphs, the gerrymandering power of both parties will eventually decrease with voter concentration, simply because extreme concentration limits the gerrymandering possibilities to a sharper boundary between voters of the two parties. Note that while our model does not explicitly postulate suburban areas, our party affiliation dispersion model does provide an implicit sense of the more mixed affiliation nature of suburban areas.

We believe that our model is just a starting point to developing a more precise understanding of the gerrymandering power so as to address gerrymandering in the real world.

Acknowledgments

The authors thank Andrew Perrault for many helpful discussions. This research was supported by NSERC grants 482671 and 503949.