[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 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.
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 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.
[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. ↩
whirr run-script at the command line to use this feature. There's a contrib script to run the Yahoo! Cloud Serving Benchmark (YCSB) against an HBase cluster, which takes advantage of the run-script command (WHIRR-287).whirr run-script, run arbitrary scripts on them to bring them into the state you want.whirr.zookeeper.tarball.url as a local file:// URL pointing to your tarball. Whirr will push the tarball to a temporary blob store container, then each node will download from there.