Since 1940 the apportionment is not done by a specific formula but by an algorithm.
- Input: Pop, a population array for the 50 states.
- Output: Rep, a representatives array for the 50 states.
- Let Rep[i] = 1 for each state i.
- For j = 51 to 435
- Let i = arg max Pop[i]/sqrt(Rep[i]*(Rep[i]+1))
- Rep[i] = Rep[i]+1
Check out the Census Bureau video The Amazing Apportionment Machine.
Implemented naively the running time is O(rn) for n the number of states and r the number of representatives. I'll leave it to you readers to find better implementations. Can I compute how many representatives New Jersey gets from Pop in o(n) space?
Of course with n=50 and r=435 the numbers don't get big enough to cause any problem at all for today's computers. I wonder how long it took in 1940?
Of course with n=50 and r=435 the numbers don't get big enough to cause any problem at all for today's computers. I wonder how long it took in 1940?
It makes a nice programming exercise for an introductory algorithms and data structures course. If someone wants to use it, description and data files can be found at tinyurl.com/345l72t .
ReplyDeleteData files include US census data, but as you point out, they are actually too small. The files called huge-*.in are fictional population data for planets, the largest of these distributes the 1 million seats in the galactic senate among 200,000 planets. (I had fun with this. The names of the planets are created by an algorithm similar to what was used in the 1984 computer game Elite, picking random digrams from “..LEXEGEZACEBISOUSESARMAINDIREA.ERATENBERALAVETIEDORQUANTEISRION”.)
I have a couple of questions.
ReplyDelete1) What happens when the populations of all states are equal?
2) Is it possible for a state to "rig up" its population so that it can have desired number of representatives? What happens if all states try to do this? - Do we have a game theoretic framework?
Should you be using j somewhere in the for loop?
ReplyDeleteNo, "j" does not have to appear in the body of that loop.
ReplyDeleteIf you follow this algorithm by hand, (as was probably done in 1940), then it is clear that only one value of rep[i] changes in each iteration and only one update is required.
ReplyDeleteProbably the first person who implemented this algorithm saw the efficient way to implement it.
Except that this algorithm is probably not "fair" (in the same sense that Arrow proved that no voting system is fair) because of the Apportionment paradox.
ReplyDeleteI'm wondering how that video was made....it would be cool to have something like that for other algorithms
ReplyDelete@Tyson: The Huntington-Hill method avoids the Alabama paradox and the population paradox, while violating the quota rule. Given that one cannot avoid losing one of the above three properties, this is about as good as one can hope for. See
ReplyDeletehttp://www.ams.org/samplings/feature-column/fcarc-apportionii3
The fact that one has monotonicity (i.e. no Alabama or population paradox) more or less eliminates the opportunity for 'gaming' the system as raised by the first anonymous; assuming that states desire as many seats as possible, the incentive is always to report the population as fully as possible.
Well, i used this method on Indian Census data 2001 .. the results : http://goo.gl/Bq6Es
ReplyDeletethe number of seats can be computed in o(n) space. It first needs to compute the truncated integer according to proportion (of remainder using plus one seat rule). Then it needs to add all these truncated integers, to compute the still remaining number of seats r. Then it needs to check if the score m/sqrt(n(n+1)) is in the first r scores. This can be done using just O(1) numbers to keep the intermediate scores and counters.
ReplyDeleteThe number of House seats is fixed at 435 even if the national population doubles? That can't be right.
ReplyDeleteThe Apportionment Act of 1911 set that number in place (population of around 90 million). The Reapportionment Act of 1929 kept it at that number (population around 120 million). The Apportionment Act of 1941 basically locked it in as that (population around 130 million). The number did increase temporarily when Alaska and Hawaii joined (they each got one representative without any existing state losing one) but the total count went back down to 435 after the 1960 Census (population around 180 million) and is still at that number today (population around 310 million).
ReplyDelete