In April 2021, the US Census Bureau announced the latest apportionment results. Apportionment answers the question: How many seats will each state get in the House of Representatives? It also factors into the Electoral College. The latest numbers are given below.

Interestingly, New York, which saw its number drop from 27 to 26 seats, would have stayed at 27 if it had just 89 more people! Several other states, like California, Arizona, and Texas, did not receive as many seats as expected. How did the Census arrive at these numbers?

## The Apportionment Problem

In apportionment, we are given the population of each state and are tasked with distributing a certain number of seats among them. That is, we should find an integer number of seats for each state that sum to . In the US, the current number of seats is , and each state must receive at least one seat. Mathematically, the constraints of apportionment dictate that:

(Distribute a total of seats.)

(Each state gets an integer number of seats.)

(Each state gets at least one seat.)

Denote by as the set of apportionments that satisfy these constraints.

The question then becomes: What should be the objective function? What makes one possible apportionment “better” than another?

A typical response is *fairness*, specifically *proportionality*; if a state has twice the population of another, then it should receive twice as many seats. This abides by the “one-person, one-vote” principle. In the ideal case, each state receives a number of seats equal to its *quota* , i.e., its proportion of the country’s population multiplied by the total number of seats:

.

However, the quotas are almost certainly fractional. For example, New York’s 2020 population was 20,215,751 which is roughly 6% of the total US apportionment population (331,108,434) making its quota equal to .

What should we do with the fractions? One idea is to round them up, i.e., set . This will end up distributing more than the allotted 435 seats. Rounding down, , gives a different problem: too few seats distributed. Rounding to the nearest integer will work *sometimes* (e.g., for the 2020 data), but not always. For example, consider a hypothetical instance with three equally populated states and seats to distribute; each state would have a quota of , which, when rounded, would give total seats.

## Enter Thomas Jefferson and Alexander Hamilton

The US Constitution does not specify what method should be used for apportionment. So, when results from the first census arrived in 1791, there were political disputes about how to proceed.

Alexander Hamilton proposed the following method. Choose the number of seats to be apportioned. Find the quotas and give each state its quota’s floor . Assign any leftover seats to those states having the largest remainders .

It turns out that Hamilton’s method solves the optimization problems (code here):

.

.

Thomas Jefferson proposed a different “divisor” method. Normally, the quota is calculated by dividing the population by the divisor . Rounding these quotas down to an integer may distribute too few seats. In this case, Jefferson proposed to instead divide the population by some other divisor. Specifically, pick a divisor that will distribute the appropriate number of seats after rounding down, i.e., so that , and then set for each state

It turns out that Jefferson’s method solves the optimization problem (code):

.

Jefferson’s method was used through the 1830s, but fell out of favor as it became known to advantage large states over smaller states. For example, in 1820, New York received 34 seats (far exceeding its quota of 32.50), while Delaware received just one seat (below its quota of 1.68).

## Enter John Quincy Adams and Daniel Webster

Recognizing Jefferson’s method’s bias towards large states, John Quincy Adams proposed essentially the same method, but chose to round up, i.e., pick a divisor so that and then set for each state . Predictably, this had the opposite effect; it favored small states over large states.

It turns out that Adams’ method solves the optimization problem (code):

.

Daniel Webster proposed a compromise between the methods of Adams and Webster, by rounding to the nearest integer. That is, pick a divisor so that and then set for each state .

It turns out that Webster’s method solves the optimization problems (code):

.

.

Webster’s method was used in the 1840s. Subsequently, in the 1850s, 1860s, and 1870s, Hamilton’s method was adopted, but under a new name: “Vinton’s method” and its output was altered for political reasons.

## Paradoxes and Axioms

With the 1880 census data came some strange results when using Hamilton’s method. If seats were to be distributed, then Alabama would get 8 of them. However, if the allotment increased to 300 seats, then Alabama’s representation would drop to 7 seats. Even though there is more pie to go around, someone gets less! This is the “Alabama paradox.”

There were other problems with Hamilton’s method. In the 1900s, Virginia *grew faster* than Maine in population, but Virginia would lose a seat to Maine. This is the “population paradox.”

Before Oklahoma became a state in 1907, Maine and New York had 3 and 38 seats respectively, out of 386 seats total. When Oklahoma joined and got 5 seats (increasing the total to 391), Maine and New York would swap a seat under Hamilton’s method, going to 4 and 37 seats respectively. This is the “new states paradox.”

These paradoxes led mathematicians to study apportionment methods in more detail and axiomatize their study. Some prominent theorems include:

- Divisor methods (e.g., Jefferson, Adams, Webster) are the only methods that avoid the population paradox.
- All divisor methods avoid the Alabama paradox.
- All divisor methods avoid the new states paradox.

Based on these results, it seems that a divisor method should be chosen. Intuitively, one should avoid Jefferson’s and Adam’s methods because they exhibit bias towards large and small states, respectively. How many other divisor methods are there? Which should be used?

## Enter Huntington and Hill

Joseph A. Hill began doing statistical work for the US Census Bureau in 1899 and later became chief statistician in 1909. He (essentially) proposed an objective function for apportionment. It amounts to a local search condition, as shown by Edward V. Huntington, a professor at Harvard. Huntington called it the method of equal proportions which has been used in the US since the 1940s.

Consider two states and in a possible apportionment . State is *favored relative to* state if it has more seats per person, i.e., if . The *amount of inequality* between these states might then be measured by the quantity . If moving a seat from state to state reduces the amount of inequality, then do so. Repeat until no such transfers reduce the pairwise amounts of inequality. (Note: this procedure does terminate.) This is one way to describe the Huntington-Hill method. There is also a construction procedure that starts with zero seats assigned and greedily adds seats to states according to a particular rule. Python code is available here.

It turns out that the Huntington-Hill method of equal proportions solves the optimization problem (code):

.

Interestingly, Huntington’s measure of inequality can be changed to create local search versions of the methods of Adams, Dean, Webster, and Jefferson.

- Adams:
- Dean:
- Webster:
- Jefferson: .

## Solving the MINLPs on 2020 Census Data

The codes solve the associated MINLPs with the Gurobi solver. Each MINLP is applied to Example 1.1 from the appendix of Balinski and Young‘s 1982 book *Fair Representation*.

I also tried applying them to the 2020 Census data, but Gurobi gave very strange results. For example, Gurobi would sometimes suggest to give one seat to each state (except California) and give California the remaining seats. This is clearly not optimal for the given objective function.

My suspicion is that numerical instability is to blame. For example, some of the constraints of Jefferson’s model (after linearization) have the form , with the integer variable likely taking a small value (up to 52), being a large number (up to 40 million), and being a continuous variable. Big-M constraints like these are known to cause numerical problems, so this should not be a huge surprise. I tried tightening Gurobi’s tolerances, but to no avail. So, while these apportionment instances cannot reliably be handled with commercial MIP solvers, they might serve as interesting test cases for MIP solvers that use exact rational arithmetic since the answers can be double-checked with simple algorithms.

## Further Reading

This post is based primarily on Balinski and Young’s 1982 book *Fair Representation* and their 1983 *Interfaces *paper “Apportioning the United States House of Representatives.”

Their opinion, which they back up with theorems and empirical evidence, is that Webster’s method is preferable to the Huntington-Hill method, because:

- Webster’s method is the only “unbiased” divisor method (not favoring large or small states).
- Another desirable property of an apportionment method is to
*stay within the quota*, i.e., to give each state a number of seats equal to its quota’s floor or ceiling, i.e., to have . Unfortunately, there is no method that simultaneously avoids the population paradox and stays within quota. However, Webster’s method is the least likely (among divisor methods) to violate quota. It is also the only divisor method that stays “near” the quota.

In their words, “while it is not possible to to satisfy all of the principles all of the time, it is possible to satisfy all of them *almost* all of the time.”

Balinski was quite active in the optimization and OR communities before his passing in 2019. Here are some select tidbits from his INFORMS biography:

…Balinski went on to Princeton University and studied under Albert W. Tucker and Ralph E. Gomory, earning a PhD in mathematics in 1959.

…His 1965 Management Science article, “Integer Programming: Methods, Uses, Computation” was awarded INFORMS’s Frederick W. Lanchester Prize.

…In 2013, the Institute for Operations Research and the Management Sciences (INFORMS) awarded him the John von Neumann Theory Prize, one of the highest honors an operations researcher can receive… The following year he was elected an INFORMS Fellow.

…He was one of the six founding members and was the founder and first editor-in-chief of its journal,

Mathematical Programming(1970-1980). He went on to serve as MPS president for three years in the late 1980s.

Young also frequently publishes in INFORMS journals and wrote a great paper showing the limitations of various compactness measures in redistricting.