What is "Proportional"? Apportionment algorithms


#1

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.

code here:


#2

Isn’t a simple solution to that to keep going until Wyoming (or whatever the least populous state is) gets an Nth Seat by Apportionment, rather than by Fiat?

For N=1, that comes out to 731 seats, for N=2 it’s 1301, and N=3 it’s 1859 (according to the most recent population estimates I’m aware of)


#3

Here is the utilitarian measure of the geographical proportionality of the house of representitives:

Proportionality = (AL_%of_representation ^ AL%of_population) * (AK%of_representation ^ AK%of_population) * (AZ%of_representation ^ AZ%of_population) * (AR%of_representation ^ AR%of_population) * (CA%of_representation ^ CA%of_population) * (CO%of_representation ^ CO%of_population) * (CT%of_representation ^ CT%of_population) * (DE%of_representation ^ DE%of_population) * (FL%of_representation ^ FL%of_population) * (GA%of_representation ^ GA%of_population) * (HI%of_representation ^ HI%of_population) * (ID%of_representation ^ ID%of_population) * (IL%of_representation ^ IL%of_population) * (IN%of_representation ^ IN%of_population) * (IA%of_representation ^ IA%of_population) * (KS%of_representation ^ KS%of_population) * (KY%of_representation ^ KY%of_population) * (LA%of_representation ^ LA%of_population) * (ME%of_representation ^ ME%of_population) * (MD%of_representation ^ MD%of_population) * (MA%of_representation ^ MA%of_population) * (MI%of_representation ^ MI%of_population) * (MN%of_representation ^ MN%of_population) * (MS%of_representation ^ MS%of_population) * (MO%of_representation ^ MO%of_population) * (MT%of_representation ^ MT%of_population) * (NE%of_representation ^ NE%of_population) * (NV%of_representation ^ NV%of_population) * (NH%of_representation ^ NH%of_population) * (NJ%of_representation ^ NJ%of_population) * (NM%of_representation ^ NM%of_population) * (NY%of_representation ^ NY%of_population) * (NC%of_representation ^ NC%of_population) * (ND%of_representation ^ ND%of_population) * (OH%of_representation ^ OH%of_population) * (OK%of_representation ^ OK%of_population) * (OR_total_representitives ^ OR%of_population) * (PA_total_representitives ^ PA%of_population) * (RI%of_representation ^ RI%of_population) * (SC%of_representation ^ SC%of_population) * (SD%of_representation ^ SD%of_population) * (TN%of_representation ^ TN%of_population) * (TX%of_representation ^ TX%of_population) * (UT%of_representation ^ UT%of_population) * (VT%of_representation ^ VT%of_population) * (VA%of_representation ^ VA%of_population) * (WA%of_representation ^ WA%of_population) * (WV%of_representation ^ WV%of_population) * (WI%of_representation ^ WI%of_population) * (WY%of_representation ^ WY%of_population) * (AS%of_representation ^ AS%of_population) * (DC%of_representation ^ DC%of_population) * (GU%of_representation ^ GU%of_population) * (MP%of_representation ^ MP%of_population) * (PR%of_representation ^ PR%of_population) * (VI%of_representation ^ VI%_of_population).

Maximizing that product will maximize the total proportionality. If you want to measure proportionality among voters instead of proportionality among states and territories, then for each group of voters, you would raise their total satisfaction to the power of their portion of the population and multiply those values together.

Rangevoting.org also has a few pages about different appointment schemes as well as a few appointment criteria.

https://www.rangevoting.org/Apportion.html


#4

One way is to use the apportionment that gives the minimum absolute deviation (MAD). d^2(Sum(|a_i - A|)) = 0 (A = total population over number of seats)

one might also want to use the minimum maximum deviation. or the two in combination - maybe first MMD, then MAD within that. Though realistically the MMD state will always be the lowest population state, so long as you have a fair number of states with only one district. So MMD is unnecessary. Though it occurs to me now that there’s a good chance that the MAD solution has districts with zero seats. so that would have to be a constraint: that all districts have one seat.

In any case one has the obvious constraint that no state should have more than 1 seat too many or two few. And this constraint already limits you to 3 options per state. So that’s no more than 3^50 combinations, and except for edge cases it’s actually 2^50. (a fraction of a seat too many or a fraction of a seat too few.) and in order for the total number to equal N, you need half of the states to have too few, and the other half to have too many. So now you’re already very constrained. For any given N (total districts), there are no more than 50 choose 25 solutions. (50!/(25!*25!))

edit: okay so that’s still about 1e14 combinations. still, way more constrained than what we started with. and if you add a fitness criteria, (such as MAD) you can find a very good solution very quickly with simulated annealing.


#5

if you convert it to an information theoretic problem, you can use kl-divergence as the fitness criterion. each voter is a bit of information and each representative is a bit of information. the voters are the true distribution and the representatives are the model distribution. and you want to minimize divergence of the latter from the former; you want to minimize the kullbach-liebler divergence.


#7

parker: taking the logarithmic of that converts it to:

sum over all states of ( %population of state times log(% representation of state),

which is just cross entropy of q from p, where p=voter and q=representative. subtract that from the self entropy of q, and you get kl-divergence.


#8

okay now onto speed.

you can start by rounding to the nearest, with each state having at least one, and then that wont get you the exact number of seats you wanted, so add or subtract a seat from total seats and repeat until you get the desired number back.

then use your fitness criteria - evaluate the fitness of subtracting one seat from each state, so that’s 50 evaluations. then same for adding one. then pick the add that’s most fit and the subtract that’s the most fit, and apply them, and measure the fitness. if it improves, repeat. if not, stop, and use the result of the previous iteration.

this assumes strong local linearity. one could alsi consider all pairs, so 50x50=2500 evaluations per iteration. this is safer and still very fast.


#9

thanks for the range voting link, peter. interesting stuff.

it occurs to me, that if instead of starting with a fixed number of seats or fixed total number of seats per total population, you had a fixed target seats per person, and then for each state you rounded nearest without regard to the final total seat count, wouldn’t that satisfy all three criteria mentioned in that link?

  • global monotonicity
  • pairwise monotonicity
  • a or a+1

#10

Unfortunately, that system doesnt pass the A or A+1 criterion.

Example:
State Texafornia makes up 38% of the population.
State New Yorkissipi makes up 11% of the population.
State Washalaska makes up 11% of the population.
State Vermontana makes up 10% of the population.
State Mainewaii makes up 10% of the population.
State Rhode Islansas makes up 10% of the population.
State Orgutah makes up 10% of the population.

If you were going to allocate 1 rep per about 25% of the population where each state would get round( 4 × portion_of_population ) number of representatives, then Texafornia would get 2 reps and every other state would get 0 reps. The A or A+1 criterion states that:

|seats_allocated_to_state - state’s_portion_of_population × total_seats_allocated| < 1

In this case:

|seats_allocated_to_Texafornia - Texafornia’s_portion_of_population × total_seats_allocated| = 1.24


#11

no, texas would get 2 reps and every other state would get 1.

38/25 rounded down is 1, so a=1. 2 is a+1.
21/25 rounded down is 0, so a=0, 1 is a+1.
21/25 rounded down is 0, so a=0, 1 is a+1.
20/25 rounded down is 0, so a=0, 1 is a+1.


#12

Sorry, I made a mistake. Suppose that there were 6 other states, 2 of which make up 11% of the population, and 2 of which make up 10% of the population.

I have now revised my example.

38/25 rounded is 2
11/25 rounded is 0
11/25 rounded is 0
10/25 rounded is 0
10/25 rounded is 0
10/25 rounded is 0
10/25 rounded is 0

The A or A+1 criterion states that if a total of 2 seats are going to be allocated, Texafornia should get 1 or 0 seats. In this example, Texafornia gets 2 seats.


#13

but i’m saying disregard the final total seats. use the 25% instead. so texas gets 1 or 2, and the others get 0 or 1.

though really you should start with enough seats so that every state rounds nearest to at least 1


#14

if you bring the seat count up high enough to where every state rounds nearest to at least one (which happens to be 6, in this case), then both versions of the a or a+1 criteria are met (initial target seat count and actual resulting seat count). if you keep increasing the seat count, neither criteria is ever violated. (at least for your example) and as the seat count grows, the initial target count and the final actual count approach equivalency.


#15

So does every other proportional allocation method. That does not mean that they all pass Warren’s ‘A or A + 1’ criterion.


#16

yeah, but i’m not sure that’s important.

if the smallest unit is given 1 seat, and there aren’t a very small number of districts, then it will very rarely violate the rule.

and then one can take that and additionally optimize it to minimize kl-divergence, and then it would probably follow that rule exactly, and if it doesn’t, it will follow an even better one: minimum kl-divergence. (maximum cross-entropy).

(sorry if i’m introducing esoteric terms. they’res from information theory.)


#17

My point was not about the importance of Warren’s A or A+1 criterion, but rather whether your method passed that criterion as you claimed it did.

I agree that that specific criterion isn’t as important as the other two Warren listed as long as either the lower or upper bounds of the equality is still satisfied:

lower bounds:

seats_allocated_to_state - state’s_portion_of_population × total_seats_allocated > -1

upper bounds:

seats_allocated_to_state - state’s_portion_of_population × total_seats_allocated < 1

All of the devisor methods as well as your own unfixed legislature size method do satisfy the lower bounds and the maximizing the geometric mean method (or equivalently minimizing kl-divergence) instead satisfies the upper bounds.


#18

yeah, I missed a subtle point in a or a+1: that it was a was the final count divided by the population, rounded down, as opposed the target seats to population ratio, rounded down.

so thinking as I did, a or a+1 seemed to be trivially met by round nearest, or even round up or round down. All in all the solution seemed to be too simple and I worried I might have been missing something. hence I asked.

it appears I was, and thank you for that. also thank you for your discussion of satisfying lower bound and other methods that satisfy it.

slightly off topic since I feel we’ve reached resolution on this topic, in my mind, kl-divergence minimization seems like a very important criteria, arguably even penultimate. a more common use of it is in artificial intelligence, as a way to measure with a single number how well you’ve modeled an unknown external system.