Gödel's Lost Letter and P=NP

David Wasserman is an elections analyst for the Cook Political Report. He is known for forecasting the results of elections after people have voted. His words “I’ve seen enough” to declare an outcome are taken as seriously as any network election call.

This week, with nine US House races uncalled and control of the chamber still unknown, he is working overtime.

So have been your humble blog staff, in various life-necessary ways besides this blog. For me (Ken) it is not just being referenced six times in a $100M lawsuit—much else has been going on. Right now I am preparing a full formal report to the International Chess Federation (FIDE) for their own investigation.

The election has also diverted our time. Insofar as both of us have involvements in predictive analytics, it behooves us to examine how well election models have been faring and where they may have systematic failings. The Washington Post shows its models of several of the uncalled House races in California plus one in Oregon. The New York Times showed its “needle” on Election Night but stopped its prognostications once the long-count stage began. As we write, the Republicans are on the cusp of the House majority threshold of 218 and will likely exceed it by two or three seats, but they are not yet declared the winner. The winners we can declare, however, are the gerrymanders

Redistricting

Wasserman goes by the handle @Redistrict on Twitter. Redistricting is a neutral name for the re-drawing of boundaries of a region in which an election occurs. This is not confined to the US, but has special status because the US Constitution requires updating the number of Representatives for each state after each decennial US Census, and districts can be redrawn to reflect population shifts within a state even if the state has not gained or lost a member. The political science of drawing these maps is Wasserman’s specialty.

To illustrate how the choice of boundaries can affect election outcomes, say we have a “state” of just nine people to divide equally into three districts:

• Nathaniel Bleu, Carrie Cyan, Alberto Azúl, Sandy Sapphire.

• Nathan Redd, Corrie Crimson, Philip Roth, Sally Scarlet, Ruby Rover.

The “red voters” have an overall 5-4 majority. But if the districts are drawn like so, then the state will elect more blue than red representatives:

1. Bleu, Cyan, Redd.

2. Azúl, Sapphire, Crimson.

3. Roth, Scarlet, Ruby.

What happened is that the red votes in district 3 were overkill. This is shown at left in the picture below. Two other natural ways of drawing the boundaries, however, result in two majority red districts.

The third map at right favors Red more robustly in the following sense: If Ruby Rover is any of the bottom three red dots and flips to blue, Red will still win two seats. Whereas, in the second map, any of four flips costs Red a seat.

The second map, however, gives Red a chance of a clean sweep if either of the two blue voters at left flips to red. Whereas, the third map gives no such chance.

Redistricting becomes gerrymandering when one side has control to draw a map yielding outcomes out of proportion to the other side’s voters. The Elections Clause of the US Constitution empowers state legislatures to prescribe the manner of state elections, subject to regulation and revision by the US Congress. Some states’ legislatures have vested non-partisan commissions with districting power, while others’ legislatures assume this power to benefit the side currently controlling them.

Mathematics of Redistricting

Dick wrote a 2019 post on the mathematics of gerrymanders. It includes a richer graphic on how they work. Here we will take a view from 20,000 feet and begin with some airy generalities.

• Random assignment amplifies the majority. One might think that a completely random assignment of voters to districts would be fairest. But doing so amplifies a distinct majority party into total command of the state’s races. If we multiplied our 9 people into 900 while keeping proportions, and then chose three groups of 300 at random, it is overwhelmingly likely that majority vote in each group would go red.

• Gerrymanders can favor or disfavor the minority. This is exemplified by both our graphic above and the richer one in Dick’s post. They are, however, all fairer to the minority than random assignment.

• Proportional representation is practiced in several foreign countries, notably in Europe. This is generally most fair, but runs counter to the notion of geographical community as especially enshrined in US traditions.

• In any map, the higher one side’s percentage of voters in any one district, the lower the efficiency of each of those voters. Broadly speaking, one side’s objective in any gerrymander is to minimize the efficiency of the other side’s voters. There are various metrics for quantifying this.

The US has an organic tendency toward gerrymanders through its rural-suburban-urban spectrum. The rural and urban sides have become more partisan during our lifetimes. When a city has population near the share of one Representative, it is natural to make it into one district. If the blue voters are, say, 80% in that district, then they are individually highly inefficient. Meanwhile, a higher number of red voters—those besides the 20% inside the city district—are freed to be efficient elsewhere.

The logic of clustering a blue city can, however, turn on a dime if the surrounding areas are red and populous enough. Then the city can be divided into pizza slices, each joined with enough red to overpower it. This recently happened with Nashville in Tennessee:

This change strikes us as increasing the efficiency of the Nashville voters—and the surrounding rural voters too. Thus efficiency is not the only metrizable notion that is relevant to fairness.

Difference Makers

A key episode in this year’s redistricting was the rejection by the New York Court of Appeals of the district map drawn up by the Democratic-controlled state legislature. The map at left below, was replaced by the map at right.

Among several of the first map’s sins was lack of geometric contiguity as codified in law in one district that hopped over the Long Island Sound. Three consequential changes were Syracuse losing its reach down to Ithaca while absorbing red areas northeast, Long Island’s red area being divided between two districts, and Staten Island being joined to red rather than blue areas of Brooklyn. The City published an analysis from last week’s voting records that the district with Staten Island would have gone blue with the original map. All close districts went Republican, and this alone may make the difference in tbe majority.

Even while Illinois lost a seat from population shifts, their Democrats conjured a new blue seat snaking through Springfield. Again the maps are mashups of ones created by FiveThirtyEight, not by Bart Simpson.

Meanwhile, Florida not only gained a seat, but their Republicans created three more strong ones for themselves even before considering their increased Election Day margins on the whole.

Variability

We have tried to be balanced in our choice of examples. Our main point is not whether the changes are signed blue or red, but rather their absolute value. The variance alone is likely to dwarf the margin of the final House majority.

Thus, instead of trying to define districts according to some criterion of fairness, can we instead postulate that revisions adhere to metrics for minimizing variability? This requires maintaining the sequence of past maps and population distributions as a reference, rather than treating each new map ab ovo.

To be sure, it is possible for maps to conserve variability while defying any notions of geometric regularity. Here are the 2000 and 2002 maps for one Chicago area district:

As recounted here, only one element of variability mattered most to the incumbent about the right-hand map. That was to exclude the home marked by the blue pin at upper right. It was the residence of a potential challenger: Barack Obama.

Open Questions

Have we shed any more light on mathematical criteria that might curtail the variability and arbitrariness of redistricting?

Here is a second question, along lines of my saying above that how election models fare can matter to my chess work. FiveThirtyEight are catching heat for their modeling of Washington’s Third Congressional District, where Marie Gluesenkamp Perez upset the Republican Joe Kent. They had Perez at only a 2% chance to win:

Our question is, given that over a hundred races were under the 99%-lock level, and allowing for covariance over all races, shouldn’t one expect to have one such case? If “a 2% chance to win” really means what it says in your model, not just a hedge for modeling uncertainty, then it should have 2% expectation, no? This can be argued back-and-forth a few more rounds based on how FiveThirtyEight’s simulations work, but my point will remain—and it is important in both my top-level need to gauge unlikelihoods longer than 2% and my model’s internal need for precision and accuracy on estimating low-probability moves, especially blunders.

[fixed Obama pin, added to end question, some small word changes]