What is "Proportional"? Apportionment Algorithms

I think by “Proportional” we mean a linear interpolation, the number of seats allocated to various populations should scale linearly with those populations.

I was writing this up in code and ran into some subtleties and wanted to share.

First, the US House apportionment algorithm is not proportional! It allocates one seat to every state and then approaches linear after that. Wyoming never quite comes back in line.

Second, integer linear interpolation on many dimensions simultaneously can be subtle. I modified Bresenham’s integer linear interpolation algorithm (common in computer graphics) but tried two different ways of applying it in parallel to many lines at once and made a minor bug on my first try, so I want to share what I learned. My first attempt was to cycle through all the groups in descending population order to see if they needed a next apportionment seat; and just repeat this until all the seats were apportioned out. My better algorithm does a pass through all the groups, then re-sorts them based on how far behind the line they are and how much they need a next seat. Repeating these two steps works better: passing through all the groups - maybe allocating, then re-sorting all the groups based on updates.

The second line below is populations for 4 hypothetical groups or states. For 9 seats there would be 0.009 people per seat if everything were fair.

target p/s      0.009
pops              15         44        368        573
house              1          1          3          4
house p/s  0.0666667  0.0227273 0.00815217  0.0069808
nb 1               0          1          3          5
nb 1  p/s          0  0.0227273 0.00815217   0.008726
nb 2               0          0          3          6
nb 2  p/s          0          0 0.00815217  0.0104712

Above you can see the House algorithm, my algorithm versions 1 and 2. Each pair of lines shows the seat allocations and the “p/s” population/seat. The House algorithm has some large over-representations of tiny groups and resulting under-representation of other groups. My final algorithm avoids this.

The House algorithm is probably still the right answer for the US House. More broadly I want to figure out a good definition of what is fair for Proportional Representation. In PR one could simply say that a group that is 33% of the population should get 33% of the seats, but if there are 10 seats should they get 3 or 4? That depends on the various sizes of other groups being represented. I want to codify this into good rules for what is fair and ideal, and then do work on practical systems that can as closely as possible achieve this.

My apportionment code in Python on github


Gil v Whitford decision; 2018-06-18

The Supreme Court of the United States (SCOTUS) gave a 41 page document around political gerrymandering in Wisconsin. Below are my notes.

The main decision was a unanimous procedural action to bump the case back down to District Court. A concurring opinion from Kagan, Ginsburg, Breyer, and Sotomayor laid out a road may for the plantiffs to fix their case and come back and try again. I believe there is one more legal challenge not sufficiently pursued in this case.

The Procedural Rebuff

Chief Justice Roberts, et. al., primarily ruled that the plaintiffs had not sufficiently shown 'standing' for their case. They had to show that they had personally been harmed by the effects of gerrymandering. The plaintiff most cited, who must have done most of the talking during the original case, wasn't from a badly gerrymandered district. Even measuring gerrymandering is problematic and they don't like most of the measures.

The Court is aware of the mediocrity they have contributed to this situation. "Our previous attempts at an answer have left few clear landmarks for addressing the question." (p.8)

What they most wind up looking at is 'dilution of votes'. But, "To the extent the plaintiffs’ alleged harm is the dilution of their votes, that injury is district specific." (p.14) SCOTUS seems to want district by district, 'this one was packed', 'this one was cracked'. They disparage systemic, state-wide statistics, but want to focus on effects on concrete single voters.

The main decision claims that the fix could be small:
"Remedying the individual voter’s harm, therefore, does not necessarily require restructuring all of the State’s legislative districts. It requires revising only such districts as are necessary to reshape the voter’s district—so that the voter may be unpacked or uncracked, as the case may be." (p.16)
The concurring decision later suggests getting plaintiffs from every packed or cracked district, so that the result will wind up affecting pretty much all the districts.

On the "Efficiency Gap" measure:
"The difficulty for standing purposes is that these calculations are an average measure. They do not address the effect that a gerrymander has on the votes of particular citizens. Partisan-asymmetry metrics such as the efficiency gap measure something else entirely: the effect that a gerrymander has on the fortunes of political parties." (p.20)

7 of 9 members of the court felt that the case still had a chance though, so they bounced it back down to District Court. Thomas and Gorsuch wanted to just close the case and let the gerrymander stand.

The Concurring Hope

The Kagan, Ginsburg, Breyer, Sotomayor concurring opinion mostly calls out ways to make the anti-gerrymandering case better. They suggest that there's a good First Amendment claim to be made around freedom of association and the ability to effectively coordinate as a political party.
"... a plaintiff presenting such a theory would not need to show that her particular voting district was packed or cracked for standing purposes because that fact would bear no connection to her substantive claim."
"... everything about the litigation of that claim—from standing on down to remedy—would be statewide in nature." (p.2)
The main decision had a few notes, as SCOTUS frequently does, of "not our job" because they want lawmaking to be done by the legislatures and the congress, but this critique notes that,
"... only the courts can do anything to remedy the problem, because gerrymanders benefit those who control the political branches." (p.2)

They cite "Wesberry v. Sanders, 376 U. S. 1, 7 (1964)" for the "one-person, one-vote" principle and how fractionally diluting a vote is bad.

This to me sounds like an endorsement of the rising "ensemble" method of statistically challenging gerrymanders:
"In many partisan gerrymandering cases, that threshold showing will not be hard to make. Among other ways of proving packing or cracking, a plaintiff could produce an alternative map (or set of alternative maps)—comparably consistent with traditional districting principles—under which her vote would carry more weight." (p.3)

How to get a state wide effect for the state wide problem, more plaintiffs from all the packed and cracked districts:
"Assuming that is true, the plaintiffs should have a mass of packing and cracking proof, which they can now also present in district-by-district form to support their standing. In other words, a plaintiff residing in each affected district can show, through an alternative map or other evidence, that packing or cracking indeed occurred there." (p.6)
"... with enough plaintiffs joined together—attacking all the packed and cracked districts in a statewide gerrymander—those obligatory revisions could amount to a wholesale restructuring of the State’s districting plan." (p.7)

The main opinion claimed that the intent of the legislature didn't matter (documents were presented about deliberate gerrymandering) only the resulting injury to specific voters. Kagan, et.al., cite "Alabama Legislative Black Caucus v. Alabama" claiming that motive evidence counts and that statewide systemic evidence counts.

Getting back to the First Amendment free-association claim:
"The complaint in such a case is instead that the gerrymander has burdened the ability of like-minded people across the State to affiliate in a political party and carry out that organization’s activities and objects." (p.10)
"... nothing in the Court’s opinion prevents the plaintiffs on remand from pursuing an associational claim, or from satisfying the different standing requirement that theory would entail." (p.11)
The opinion closes with notes about how gerrymandering is bad and it hurts America and it has gotten a lot worse in the last two decades.

One More Thing

From the main opinion:
"The 99 members of the Assembly are chosen from single districts that must “consist of contiguous territory and be in as compact form as practicable.” §4. " (p.2)
What if the whole case is really much simpler? I can trivially show that the Wisconsin districts are not as compact as practicableThe Legislature of Wisconsin broke Wisconsin's laws. Just as in the recent Pennsylvania case, that's all you need. State court can throw out the gerrymandering.


Another Gerrymandering Game

Here's a game to practice your gerrymandering by packing and cracking. It starts pretty simple on a 3x3 board making districts of 3 blocks and builds up to a 7x7 board building 7 block districts. I am frequently a completionist on little games like this, but when you get to level 50 it will just keep going forever, so when you get there, congratulations, you won the game.


Partisan Outcome of Compact Districts

I have often been asked what the likely partisan breakdown of my maps would be. I never had the data to do that analysis, but FiveThirtyEight got the data and analyzed my maps and 7 other plans for various notions of gerrymandered and fair.
In short, my compact maps are very slightly less Republican and a bit more competitive. I've always believed that on average in the last two districtings Republicans have done more of the gerrymandering and stolen more US House seats than the Democrats have. The difference was smaller than I expected though. The difference is probably smaller than this model can usefully tell us about. All models are wrong, some models are useful, and this model is certainly not destiny but can maybe tell us something useful about the biases in the system.
FiveThirtyEight estimates that the current map has 195 safe Republican seats, 168 safe Democratic seats, and 72 competitive seats; and that this will on average elect 234.4 Republicans and 200.6 Democrats. Actually in 2016 we got 241 Republicans and 194 Democrats. 7 seats out of 435, 1.6% off, not bad.
They estimate that under my compact map that goes to 180 safe Republican seats (-15), 151 safe Democratic seats (-17), and 104 competitive seats (+32); with an expected outcome of 232.2 R and 202.8 D (D +2.2).
That 2.2 seat change looks pretty small, but I want to be optimistic about the 32 additional competitive districts. The US may be self-sorting, but while gerrymandering deliberately creates uncompetitive districts on both sides, simply not gerrymandering creates additional competitive districts. I'm not in favor of distorting districts specifically to create competitive districts (which 538 explored and created a whopping 242 competitive districts) but not deliberately creating uncompetitive districts is something I'm solidly behind. Uncompetitive districts make democracy depressing when you know you don't really have any choice, and I want this country to have more democracy.


Pennsylvania Fair District Rules

In a decision handed down on January 22, 2018 by the Pennsylvania Supreme Court, they decreed that gerrymandered districts shall be thrown out and replaced such that (emphasis mine):
any congressional districting plan shall consist of: congressional districts composed of compact and contiguous territory; as nearly equal in population as practicable; and which do not divide any county, city, incorporated town, borough, township, or ward, except where necessary to ensure equality of population. 
I stared at this paragraph for a boggled minute because the English clauses aren't clearly laid out in a prioritized order. Rationalizing it combined with what I know of redistricting law, I think the priority has to work out to be:

  1. contiguous
  2. equal population
  3. whole towns
  4. compact
If that is a complete statement of what the Pennsylvania courts want out of a district map, it's relatively simple. I clearly need to get hacking on the municipality-preserving version of my compact district solver.