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 population (state) and then approaches linear after that. Of course 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.
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. “p/s” is population/seat. “target p/s” is just the total population divided by the total number of seats. The House algorithm has some large over-representations of tiny groups and resulting under-representation of other groups. My final algorithm avoids this.