Search⌘ K
AI Features
Home
Courses
Mastering Algorithms for Problem Solving in Java

Congressional Apportionment

Learn about the Huntington-Hill algorithm used for U.S. congressional apportionment, including its priority queue implementation in Java. Understand how this method fairly distributes representatives based on population and explore similar apportionment techniques used worldwide.

We'll cover the following...

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 P/r(r+1)P/\sqrt{r(r + 1)}, where PP is the state’s population and rr 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]Pop[1 .. n] storing the populations of the nn states and an integer RR equal to the total number of representatives; the algorithm assumes R≥nR ≥ n. (Currently, in the United States, nn = 50 and RR = 435.) The output array Rep[1..n]Rep[1 .. n] records the number of representatives allocated to each state.

Algorithm

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

〈〈Give every state its first representative〉〉\color{Red}〈〈Give \space every \space state \space its \space first \space representative〉〉

for s←1 to nRep[s]←1Insert(PQ,s,Pop[i]/2)\\ \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〉〉\color{Red}〈〈Allocate \space the \space remaining \space R − n \space representatives〉〉

for i←1 to R−ns←ExtractMax(PQ)Rep[s]←Rep[s]+1priority←Pop[s]/Rep[s](Rep[s]+1)Insert(PQ,s,priority)\\ \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)

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

Implementation:

Java
import java.util.*;
class Pair < T, U > {
    private final T first;
    private final U second;
    public Pair(T first, U second) {
        this.first = first;
        this.second = second;
    }
    public T getFirst() {
        return first;
    }
    public U getSecond() {
        return second;
    }
}
public class ApportionCongress {
    public static Vector < Integer > apportionCongress(Vector < Integer > pop, int R) {
        int n = pop.size();
        Vector < Integer > rep = new Vector < Integer > (Collections.nCopies(n, 1)); // initialize Rep to all ones
        PriorityQueue < Pair < Double, Integer >> pq = new PriorityQueue < > (new Comparator < Pair < Double, Integer >> () {
            @Override
            public int compare(Pair < Double, Integer > p1, Pair < Double, Integer > p2) {
                if (p1.getFirst() > p2.getFirst()) {
                    return -1;
                } else if (p1.getFirst() < p2.getFirst()) {
                    return 1;
                } else {
                    return 0;
                }
            }
        });
        // Give every state its first representative
        for (int s = 1; s <= n; s++) {
            pq.add(new Pair < > (pop.get(s - 1) / Math.sqrt(2), s - 1));
        }
        // Allocate the remaining R - n representatives
        for (int i = 1; i <= R - n; i++) {
            // start from 0 instead of 1
            int s = pq.peek().getSecond();
            pq.remove();
            rep.set(s, rep.get(s) + 1);
            double priority = pop.get(s) / Math.sqrt(rep.get(s) * (rep.get(s) + 1));
            pq.add(new Pair < > (priority, s));
        }
        return rep;
    }
    public static void main(String[] args) {
        Vector < Integer > pop = new Vector < Integer > (Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
                                                                    11, 12, 13, 14, 15, 16, 17, 18,
                                                                    19, 20, 21, 22, 23, 24, 25, 26,
                                                                    27, 28, 29, 30, 31, 32, 33, 34,
                                                                    35, 36, 37, 38, 39, 40, 41, 42,
                                                                    43, 44, 45, 46, 47, 48, 49, 50));
        int R = 435;
        Vector < Integer > rep = apportionCongress(pop, R);
        for (int r: rep) {
            System.out.print(r + " ");
        }
    }
}

Explanation

  • Lines 3–18: These lines define a generic class named Pair with two type parameters, T and U. The class has two private final instance variables, first and second, of type T and U, respectively, which are initialized through the constructor.
  • Lines 20–53: This part of the code defines a public class called ApportionCongress. Within this class, there is a public static method called apportionCongress that takes two arguments: a Vector<Integer> called pop and an int called R. The method returns a Vector<Integer>.

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’re likely to 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 the party receives. The two most common are the D’Hondt method and the Webster–Sainte-Laguë method, which respectively use priorities P/(r+1)P/(r + 1) and P/(2r+1)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 cannot be considered an algorithm, with an example.

Martin’s algorithm

As a prototypical example of a sequence of instructions that is not actually an algorithm, consider Martin’s algorithm:

Algorithm

BeAMillionaireAndNeverPayTaxes():‾Get a million dollars.If the tax man comes to your door and says,“You have never paid taxes!"Say“I forgot.”\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, but for the rest of us poor folk, 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, is not the kind of algorithm that computer scientists are used to thinking about, because it is 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 we’ve already learned how to do (like sorting, binary search, tree traversal, or singing “nn Bottles of Beer on the Wall”).