Congressional Apportionment
Learn about the problem of congressional apportionment and its historical context.
Here is another real-world example of an algorithm of significant political importance. Article I, Section 2 of the United States Constitution requires that:
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 is 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 , where ...