Congressional Apportionment

“Representatives and direct Taxes shall be apportioned among the several States which may be included within this Union, according to their respective Numbers. The Number of representatives shall not exceed one for every thirty thousand, but each state shall have at least one representative. . . .”

The Huntington-Hill method

Because there are only a finite number of seats in the House of Representatives, exact proportional representation requires either shared or fractional representatives, neither of which are legal. As a result, over the next several decades, many different apportionment algorithms were proposed and used to round the ideal fractional solution fairly. The algorithm actually used today, called the Huntington-Hill method or the method of equal proportions, was first suggested by Census Bureau statistician Joseph Hill in 1911, refined by Harvard mathematician Edward Huntington in 1920, adopted into Federal law (2 U.S.C. §2a) in 1941, and survived a Supreme Court challenge in 1992.

The Huntington-Hill method allocates representatives to states one at a time. First, in the preprocessing stage, each state is allocated one representative. Then, in each iteration of the main loop, the next representative is assigned to the state with the highest priority. The priority of each state is defined to be $P/\sqrt{r(r + 1)}$, where $P$ is the state’s population and $r$ is the number of representatives already allocated to that state.

The algorithm is described in pseudocode below. The input consists of an array $Pop[1 .. n]$ storing the populations of the $n$ states and an integer $R$ equal to the total number of representatives; the algorithm assumes $R ≥ n$. (Currently, in the United States, $n = 50$ ...