[I wrote this in July, but never got round to posting it.]

Last weekend I visited the U.S. Capitol in Washington, D.C., with my family, and I learned that the House of Representatives has 435 seats which are appointed so that each state has a number of seats that is proportional to its population. It sounded simple when the tour guide said it, but I wondered how are fractions handled fairly? Simply rounding off quotas doesn't work—firstly because some states could get no seats, which would be unfair, and secondly, how do you make sure that the rounding is both fair and assigns all 435 seats?

When I got home I read about the apportionment problem, as it is known, which has a long and interesting history. Wikipedia [1] is a good read, as usual; and [2] goes into the history and mathematics of different apportionment algorithms in depth, at least one of which suffers causes a paradox. Here I'm interested in looking at the algorithm that is used today to calculate apportionments for the House of Representatives, and why it is considered to be the fairest.

The Algorithm

The algorithm in use today for apportioning seats is due to Huntington and Hill and is known as the Huntington-Hill method, or the method of equal proportions. It's best understood as a dynamic process, which works as follows:

To start, each state is given one seat. (This ensures that states with relatively small populations, like Wyoming, get at least one seat.) Then, each remaining seat is allocated in turn to the state is allocated to the state with the highest priority, where the priority of a state of population \(P\) and \(n\) previously-allocated seats is defined as

\begin{align} \frac {P} {\sqrt{n(n+1)}}\label{pri} \end{align}

We'll see why the priority is defined as it is below, but for now notice that it is approximately \(P/n\), so the seat is given to the state that has the least number of representatives per person, roughly speaking.

Results for the 2010 Census

Running the algorithm for the state populations from the 2010 Census (using a program I wrote [5]) gives the following apportionment, which agrees with the U.S. Census Bureau [3]. (The quota column is the percentage of the population for each state.)

State Seats Population Quota People per representative
Alabama 7 4802982 6.76 686140
Alaska 1 721523 1.02 721523
Arizona 9 6412700 9.02 712522
Arkansas 4 2926229 4.12 731557
California 53 37341989 52.54 704565
Colorado 7 5044930 7.10 720704
Connecticut 5 3581628 5.04 716325
Delaware 1 900877 1.27 900877
Florida 27 18900773 26.59 700028
Georgia 14 9727566 13.69 694826
Hawaii 2 1366862 1.92 683431
Idaho 2 1573499 2.21 786749
Illinois 18 12864380 18.10 714687
Indiana 9 6501582 9.15 722398
Iowa 4 3053787 4.30 763446
Kansas 4 2863813 4.03 715953
Kentucky 6 4350606 6.12 725101
Louisiana 6 4553962 6.41 758993
Maine 2 1333074 1.88 666537
Maryland 8 5789929 8.15 723741
Massachusetts 9 6559644 9.23 728849
Michigan 14 9911626 13.94 707973
Minnesota 8 5314879 7.48 664359
Mississippi 4 2978240 4.19 744560
Missouri 8 6011478 8.46 751434
Montana 1 994416 1.40 994416
Nebraska 3 1831825 2.58 610608
Nevada 4 2709432 3.81 677358
New Hampshire 2 1321445 1.86 660722
New Jersey 12 8807501 12.39 733958
New Mexico 3 2067273 2.91 689091
New York 27 19421055 27.32 719298
North Carolina 13 9565781 13.46 735829
North Dakota 1 675905 0.95 675905
Ohio 16 11568495 16.28 723030
Oklahoma 5 3764882 5.30 752976
Oregon 5 3848606 5.41 769721
Pennsylvania 18 12734905 17.92 707494
Rhode Island 2 1055247 1.48 527623
South Carolina 7 4645975 6.54 663710
South Dakota 1 819761 1.15 819761
Tennessee 9 6375431 8.97 708381
Texas 36 25268418 35.55 701900
Utah 4 2770765 3.90 692691
Vermont 1 630337 0.89 630337
Virginia 11 8037736 11.31 730703
Washington 10 6753369 9.50 675336
West Virginia 3 1859815 2.62 619938
Wisconsin 8 5698230 8.02 712278
Wyoming 1 568300 0.80 568300

The Mathematics

The algorithm finally settled on by Congress was chosen because it was thought to be the fairest. There are different ways of defining what "fair" means, and so it cannot be settled mathematically. In this context "fair" is taken to mean "minimizes the relative difference in representatives per person between states".

To see how the algorithm meets this definition of fairness, let's see what happens when we examine any two states to see if transferring one seat between them would improve the apportionment. This is the argument published by E. V. Huntington in [4].

Suppose after the apportionment, state \(A\) has received \(x+1\) seats, and state \(B\) has received \(y\) seats. Furthermore, also suppose that \(A\) is over-represented because the number of people per representative is less than for \(B\):

\begin{align} \frac {A} {x+1} &\lt \frac {B} {y}\label{Aover} \end{align}

We can check this in the case of California and New York:

\begin{align} \frac {37,341,989} {53} &\lt \frac {19,421,055} {27}\nonumber \end{align}

Or

\begin{align} 704565.83 &\lt 719298.33 \nonumber \end{align}

Now let's see what happens if we try to transfer one seat from \(A\) to \(B\)—does that make things fairer?

In the round when \(A\) won its last seat (number \(x+1\)), we know that its priority (defined by (\ref{pri})) was higher than \(B\)'s. That is,

\begin{align} \frac {A^2} {x(x+1)} &\gt \frac {B^2} {y(y+1)}\label{priority} \end{align}

(Note that even if \(B\) hadn't won its last seat (number \(y\)) at that point, the inequality still holds, since the number of seats it had would be less than \(y\).)

Again we can check this in the case of California and New York:

\begin{align} \frac {37,341,989^2} {52 \times 53} &\gt \frac {19,421,055^2} {27 \times 28}\nonumber \end{align}

Which is true. (The numbers also tally with the U.S. Census Bureau [6], and my program to calculate apportionments [5], where the priority value for California's last seat is \(711,308\), which is \(37,341,989/\sqrt{52 \times 53}\).)

Dividing (\ref{priority}) by (\ref{Aover}) we get

\begin{align} \frac {A} {x} &\gt \frac {B} {y+1}\label{Bover} \end{align}

which we can interpret as saying that \(B\) would be over-represented if one seat were transferred to it from \(A\). For our example of California and New York, this becomes

\begin{align} 718115.17 &\gt 693609.11 \nonumber \end{align}

The question now is, which over-representation is the smallest? That is, which is fairer, and therefore, to be preferred?

Using (\ref{Aover}), we calculate the relative difference before the transfer as

\begin{align} \newcommand{\slfrac}[2]{\left.#1\middle/#2\right.} \slfrac{ \left( \frac {B} {y} - \frac {A} {x+1} \right) } {\frac {A} {x+1}} = \frac {B(x+1)} {Ay} - 1 \label{Adiff} \end{align}

And, using (\ref{Bover}), the relative difference after the transfer is

\begin{align} \newcommand{\slfrac}[2]{\left.#1\middle/#2\right.} \slfrac{ \left( \frac {A} {x} - \frac {B} {y+1} \right) } {\frac {B} {y+1}} = \frac {A(y+1)} {Bx} - 1 \label{Bdiff} \end{align}

To compare these relative differences, note that we can rewrite (\ref{priority}) as

\begin{align} \frac {A(y+1)} {Bx} &\gt \frac {B(x+1)} {Ay} \end{align}

Thus

\begin{align} \frac {A(y+1)} {Bx} - 1 &\gt \frac {B(x+1)} {Ay} - 1 \end{align}

and the relative difference is smaller before the seat transfer (using (\ref{Adiff}) and (\ref{Bdiff})). So the original apportionment is optimal. There was nothing special about the choice of \(A\) and \(B\), so we can conclude that the apportionment is optimal overall.

Again, this checks out for our example. The relative difference for 53 seats for California and 27 for New York is \(0.021\), versus \(0.035\) for 52 for California and 28 for New York.

References

[1] United States congressional apportionment, Wikipedia. ↩

[2] Apportionment: Introduction, American Mathematical Society. ↩

[3] "APPORTIONMENT POPULATION AND NUMBER OF REPRESENTATIVES, BY STATE: 2010 CENSUS", U.S. Census Bureau. ↩

[4] The Apportionment of Representatives in Congress, E. V. Huntington, Transactions of the American Mathematical Society, Vol. 30, No. 1. (Jan., 1928), pp. 85-110. ↩

[5] A program to calculate apportionments, Tom White, July 2012. ↩

[6] PRIORITY VALUES FOR 2010 CENSUS, U.S. Census Bureau. ↩