### The Interesting Math Behind Congressional Reapportionment

Data,Politics — Zac Townsend @ December 22, 2010 12:31 pm

Computational Complexity has a short blog post on the algorithm used to find the new House of Representative's apportionment. The method currently in use is called Huntington–Hill method. To give you a snippet of this problems illustrious past: past solutions that were put in practice include those created by Daniel Webster, Thomas Jefferson and Alexander Hamilton.

Why is it called Huntington-Hill? This column I found from the AMS outlines the history of the method. The introduction also puts the problem quite well:

We can formulate the [apportionment problem] mathematically as follows:

Given states s1, ..., sn with populations P1, ..., Pn and a positive integer h (think of h as the number of seats in the legislature), determine non-negative integers a1, ..., an where a1 + ... + an = h. (It is customary to think of the value h as given in advance and fixed, since currently the size of the House of Representatives is fixed; however, for some applications one might have the freedom to vary h as part of solving the problem.)

The CAP problem differs from the one above in requiring that each ai be greater than or equal to 1, or more generally (mathematicians like to generalize!) greater than or equal to bi where bi is some positive integer. The Constitution does not specify the h which started at 65 in 1790 and has grown to the now permanent value of 435, though when Alaska and Hawaii were admitted to the Union the value of h rose temporarily to 437.

At first glance the AP problem does not seem hard. If a state has 10 percent of the population and there are 37 items (seats in the parliament, computer systems, libraries, etc.) to apportion, then .10 (37) equals 3.7. In a parliament interpretation, the problem is we can not send 3.7 people to the legislature (though some feel they do not get full representation from whole bodies); 3.7 is not an integer! What should be done with those nuisance fractions? The quota principle (fairness rule) would say, in this example, that 3 or 4 representatives be assigned. With 3 representatives a state would be underrepresented, with 4 it would be over represented, but the method we currently use to apportion the House of Representatives could assign fewer than 3 or more than 4 representatives!

The algorithm ultimately devised by Huntington (improving on the work of Hill) works as follows:

1. Calculate something called the standard divisor, which is the average number of people in each district over the population of the US. That is roughly 309 million divided by 435.
2. Calculate each state’s standard quota, which is the state's population divided by the standard divisor. This is how you get a number like 3.7 above.
3. For each state, you take the lower rounding bound (3) and the upper round bound (4) and you take the geometric average of them, $\sqrt{U\cdot L}$. Then  you compare the old quota (3.7) and round down if its below this mean and up if its above it. So in this case, the geometric mean is 3.46, and you would round 3.7 up.
4. Then you add up all of these quotas, and if they equal 435, you're done. If they don't you repeat step 3 with a smaller or larger divisor than the standard one depending on whether you're summed quotas are above or below your goal.

A not particularly efficient algorithm for this process is given by Computational Complexity:

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

This algorithm isn't working as I described above, but is using the same method to add individual representatives to the state "most deserving." Its the same method, and actually shows how Huntington-Hill works efficient to change the number of representatives. The Census has a pretty well made video on this whole thing: