UPDATE! The Pennsylvania Supreme Court has ruled in the LWV vs PA General Assembly case. I was an expert witness in this case, presenting an analysis based on our joint work with Alan Frieze and Maria Chikina (discussed below). The State Supreme Court has ordered PA's map redrawn on an accelerated schedule (before the 2018 midterm elections.) My expert report (along with testimony and other case documents) can be found at the second link above.

This page gives an overview of some of our work on gerrymandering. This work is on mathematics relevant to gerrymandering. In particular, we are proving mathematical theorems which are intended to be useful for the purpose of evaluating and addressing the gerrymandering problem in practice.

This work falls into two categories:

- Giving ways to rigorously detect gerrymandering. This is a subject of our paper "Assessing significance in a Markov chain without mixing" with Alan Frieze and Maria Chikina. Essentially, our method detects whether a districting has
**carefully crafted**partisan bias—that is, partisan bias which quickly evaporates when small random changes are made to the districting—and quantifies rigorously the chances that a districting could have the appearance of having carefully crafted partisan bias just by chance. - Defining protocols to choose fairer districtings. This is the subject of our paper "A partisan districting protocol with provably nonpartisan outcomes" with Ariel Procaccia and Dingli Yu.

We discuss each of these below.

In our paper with Ariel Procaccia and Dingli Yu, we define the following simple protocol for districting a state:

**I-cut-you-freeze protocol:**

Suppose we need to divide a state into *n* districts. Initially, we have *k*=0 frozen districts. On each turn:

- The dividing player divides the unfrozen part of the state into
*n-k*districts and passes the result to the freezing player. - The freezing player chooses one district drawn by the dividing player in this unfrozen part and freezes it. This district will be in the final districting.

The players then switch roles; so the freezing player becomes the dividing player, and they go back to step 1. This continues until all of the state is frozen, after *n* steps (or really *n-1*, since in the last step, there is no division to make).

We prove in a mathematical model of a state that the number of districts won by each party will have a reasonable and symmetric relationship with the number of voters loyal to each party in the state (e.g., it doesn't matter much who goes first, as long as the number of districts is not very small), and also that neither player can pack a specific population of voters into a single district against the wishes of the other player.

One nice thing about this kind of protocol is that it doesn't require a reconception of traditional districting requirements. For example, whatever requirements are imposed in a state currently on the people responsible for drawing its districts (e.g., that the districts are connected, are roughly equal in population, etc.) can be imposed in the context of this protocol.

One key task is to be able to rigorously *identify* gerrymandering. It is not hard to tell that a districting favors one political party or another; for example, in 2012, the new Congressional districting of Pennsylvania resulted in Democrats winning only 5 out of the 18 seats up for election, despite winning a majority of the total Congressional vote in the state. Metrics such as the efficiency gap capture this advantage that one party may enjoy from the particular characteristics of a districting.

It has been pointed out, however, that this kind of advantage can arise naturally, without bias in how districtings are drawn, simply because of the differences in how Democrats and Republicans are distributed in various states. For example, when Democrats are more clustered in cities, it makes it more likely that "blue" districts in a state will be more heavily Democratic than "red" districts are Republican; in this scenario, Democrat voters are concentrated in fewer districts, and elect fewer representatives than would be proportional to their number.

The task then is to evaluate whether a districting not only favors a given political party, but does so to a degree that is atypical for the particular political geography of the state. For example, if we drew new district lines for Pennsylvania from scratch, would we be likely to see a districting with the same characteristics as the current one? Or is the current districting really an outlier in the space of possible districtings of Pennsylvania? **Moreover**, even when circumstantial evidence makes such a judgment obvious, we wish to give **objective mathematical tools** for the problem, which can be embraced as part of a rigorous legal framework for adjudicating gerrymandering questions.

To make a rigorous analysis of the outlier status of a districting of a state, we need a notion of what constitutes a *valid* districting of a state. This allows us, in principle, to compare the current districting to the space of a valid districtings. Our analysis uses on simple criteria for validity of a districtings of a state into a prescribed number of districts, for example:

- Each district should be contiguous,
- The districts should have nearly equal population, and
- The districts should have reasonable shapes.

In practice, there are many possible ways of formalizing this last constraint; one simple way is to require that the total perimeter of all districts is not too large. It is also possible to add more constraints on districtings: for example that they avoid splitting certain counties, or include specified majority-minority districts. Given a notion of what constitutes a valid districting, our task is to compare hypothetical election outcomes from the present districting of a state with the those which would result from the other valid districtings of the same state. However, the space of possible valid districtings of a state is enormous, and far too large to be enumerable by a computer, even if districts are restricted to being made up of discrete units like municipal wards or census blocks. Thus the way to compare the districting of a state with the set of possible valid districtings is to make a statistical comparison. This requires being able to draw valid districtings randomly; here, we do not mean randomly as in "haphazardly", but really randomly, in the sense that we can randomly choose valid districtings in a way such that each valid districting is equally likely to be chosen.

Markov Chains are well-studied probabilistic processes which, among other things, can be used to generate random samples from complicated sets. The basic idea of a Markov Chain is simple: suppose I have some space of objects *A* I would like to draw a random sample from, but I don't have random access to the elements of the set. Instead, I begin with an arbitrary element *X _{0}* of the set (which may not be a typical random element) and make small iterative changes to the initial element

Markov chains can thus be used to generate random valid districtings of a state quite easily. In this application, *A* is the set of all districtings of the state into the prescribed number of districts. Even though we have no direct way of accessing random elements of *A*, we do know at least one member of *A*; namely, the current districting of the state, and we can use this as *X _{0}*. Small random changes can be made to districtings by swapping small areas on the boundary of a district to the neighboring district, so long as the change preserves the requirements on valid districtings. Thus by making many such swaps, we get a long sequence

**The problem** with this method is that while mathematical theorems guarantee in principle that *X _{n}* is random if

Our method gives a way around this problem uses Markov Chains to demonstrate that the element *X _{0}* is an outlier in the set

In the language of redistricting, this amounts to a test which examines whether a districting has **carefully crafted** partisan bias—that is, partisan bias which evaporates when small random changes are made to the districting. In the context of redistricting, the theorem from our paper proves rigorously that it is impossible for any state, with any hypothetical political geography, to have the proprerty that typical districtings have a partisan bias which evaporates quickly when small changes are made to the districtings.

We have applied our test to the current Congressional districting of Pennsylvania, and to the current state assembly districting of Wisconsin. In each case, we have tried various notions how to formalize the requirement that districts have reasonable shapes. The way each of these conditions works is discussed in detail to the supplement of our paper. Roughly speaking, the perimeter constraint cares about the total perimeter of all districtings, the L1 constraint cares about the how much larger the perimeter of each district is relative to what you would expect just from its area, and the L2 constraint cares about the same thing, but heavily penalizes districtings which have even a few bad districts in them.
In the tables below, each entry corresponds to a Markov sequence with 2^{40} (roughly 1 trillion) districtings, generated with the indicated parameters. The ε value, as above, is the fraction of observed districtings which were as bad as the initial districting. This is generally tiny. In fact, for some parameters, no districting in the sequence of 1 trillion districtings was as bad as the initial districting! The *p* value in the table is the statistical significance of the outlier status from this run, computed simply as √ 2ε .

Shape constraint | (Steps) | metric | ε | p= |
---|---|---|---|---|

Perimeter | 2^{40} |
ω_{var} |
3.0974 · 10^{−8} |
2.4889 · 10^{−4} |

Perimeter | 2^{40} |
ω_{MM} |
5.7448 · 10^{−10} |
3.3896 · 10^{−5} |

L^{1} |
2^{40} |
ω_{var} |
5.0123 · 10^{−11} |
1.0012 · 10^{−5} |

L^{1} |
2^{40} |
ω_{MM} |
5.6936 · 10^{−10} |
3.3745 · 10^{−5} |

L^{2} |
2^{40} |
ω_{var} |
8.2249 · 10^{−11} |
1.2826 · 10^{−5} |

L^{2} |
2^{40} |
ω_{MM} |
6.8038 · 10^{−10} |
3.6888 · 10^{−5} |

L^{∞} |
2^{40} |
ω_{var} |
3.3188 · 10^{−13} |
8.1472 · 10^{−7} |

L^{∞} |
2^{40} |
ω_{MM} |
6.9485 · 10^{−8} |
3.7279 · 10^{−4} |

The *metric* column gives the technical parameter used to compare the level of electoral bias between districtings; these precise choices are discussed in the supplement of our paper. Since our method is based on *relative* bias of districtings, however, the precise metric we use is not so important (as demonstrated by the consistency achieved from two very different metrics in the case of Pennsylvania). For our analysis of Wisconsin, the results in the following table use the efficiency gap as a metric, because of the attention given to that metric in the Gill v. Whitford case:

Shape constraint | (Steps) | Preserve Counties? | Preserve MM districts? | ε | p= |
---|---|---|---|---|---|

Perimeter | 2^{40} |
yes | yes | 2.7317 · 10^{−8} |
2.3374 · 10^{−4} |

L1 | 2^{40} |
yes | yes | 1.6378 · 10^{−8} |
1.8099 · 10^{−4} |

L^{2} |
2^{40} |
yes | yes | 1.0051 · 10^{−8} |
1.4178 · 10^{−4} |

L^{1} |
2^{40} |
no | no | 3.5840 · 10^{−7} |
8.4664 · 10^{−4} |

For Wisconsin, we took the additional step of designing a Markov Chain which left unaltered any parts of the state belonging to counties lying entirely in one of the current districts of the Wisconsin assembly map, or any lying in one of the current Majority-Minority districts. These constraints are designed to show that the method is robust even when respecting a wide range of valid considerations map designers may have followed when designing the current districting. Our table also includes a run of the chain without these constraints.

For both states, the *p* values obtained are thus quite small; in principle we expect even smaller *p* values could be obtained with longer runs of the Markov Chain, but our relatively short runs (1 trillion steps, taking a week or two) have the advantage that they can be easily verified by third parties.

For more results on Pennsylvania, incorporating constraints on county splits and considering possible Majority Minority district issues, refer to to the report from the LWV vs PA General Assembly case.