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