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$ and $R = 435$.) The output array $Rep[1 .. n]$ records the number of representatives allocated to each state.

$\underline{ApportionCongress(Pop[1 .. n], R):} \\ \hspace{0.4cm} PQ ← NewPriorityQueue$

〈〈Give every state its first representative〉〉

$\\ \hspace{0.4cm} for\space s ← 1\space to\space n \\ \hspace{1cm} Rep[s] ← 1 \\ \hspace{1cm} Insert (PQ, s, Pop[i]/\sqrt{2})$

〈〈Allocate the remaining R − n representatives〉〉

$\\ \hspace{0.4cm} for\space i ← 1\space to\space R − n \\ \hspace{1cm} s ← ExtractMax(PQ) \\ \hspace{1cm} Rep[s] ← Rep[s] + 1 \\ \hspace{1cm} priority←Pop[s]/\sqrt{Rep[s](Rep[s]+1)} \\ \hspace{1cm} Insert(PQ, s, priority)$

$\hspace{0.4cm} return Rep[1 .. n]$

Explanation

• Lines 14–17: This loop gives every state its first representative by pushing each state onto the priority queue, with its priority set to its population divided by the square root of 2.

• Lines 20–28: The for loop allocates the remaining representatives to the states by popping the state with the highest priority from the priority queue, incrementing its number of representatives in Rep, calculating its new priority, and pushing it back onto the priority queue.

Implementation and variations of apportionment algorithms

This implementation of Huntington-Hill uses a priority queue that supports the operations NewPriorityQueue, Insert, and ExtractMax. (The actual law doesn’t say anything about priority queues, of course.) The output of the algorithm, and therefore its correctness, does not depend at all on how this priority queue is implemented. The Census Bureau uses a sorted array stored in a single column of an Excel spreadsheet, which is recalculated from scratch at every iteration. You (should have) learned a more efficient implementation in your undergraduate data structures class.

Similar apportionment algorithms are used in multi-party parliamentary elections around the world, where the number of seats allocated to each party is supposed to be proportional to the number of votes that a party receives. The two most common are the D’Hondt method and the Webster–Sainte-Laguë method, which respectively use the priorities $P/(r + 1)$ and $P/(2r + 1)$ in place of the square-root expression in Huntington-Hill. The Huntington-Hill method is essentially unique to the United States House of Representatives, thanks in part to the constitutional requirement that each state must be allocated at least one representative.

A bad example

Now, let’s learn how a simple set of instructions can’t be considered an algorithm with an example.

Martin’s algorithm

As a prototypical example of a sequence of instructions that isn’t actually an algorithm, we’ll consider Martin’s algorithm:

$\underline{BeAMillionaireAndNeverPayTaxes( ):} \\ \hspace{0.4cm} \text{Get a million dollars.} \\ \hspace{0.4cm} \text{If the tax man comes to your door and says,} \mathit{“You\space have\space never\space paid\space taxes!"} \\ \hspace{1cm} \text{Say} \mathit{“I\space forgot.”}$

Pretty simple, except for that first step; it’s a doozy! A group of billionaire CEOs, Silicon Valley venture capitalists, or New York City real-estate hustlers might consider this an algorithm because, for them, the first step is both unambiguous and trivial. However, for the rest of us, Martin’s procedure is too vague to be considered an actual algorithm. On the other hand, this is a perfect example of a reduction—it reduces the problem of being a millionaire and never paying taxes to the easier problem of acquiring a million dollars. We’ll see reductions over and over again in this course. As hundreds of businessmen and politicians have demonstrated, if you know how to solve the easier problem, a reduction tells you how to solve the harder one.

Martin’s algorithm, like some of our previous examples, isn’t the kind of algorithm that computer scientists are used to thinking about, because it’s phrased in terms of operations that are difficult for computers to perform. This course focuses (almost!) exclusively on algorithms that can be reasonably implemented on a standard digital computer. Each step in these algorithms is either directly supported by common programming languages (such as arithmetic, assignments, loops, or recursion) or something that you’ve already learned how to do (like sorting, binary search, tree traversal, or singing $n$ Bottles of Beer on the Wall).