Power balance and apportionment algorithms for the United States Congress.
We measure the performance, in the task of apportioning the Congress of the United States, of an algorithm combining a heuristic-driven (simulated annealing) search with an exact-computation dynamic programming evaluation of the apportionments visited in the search. We compare this with the actual algorithm currently used in the United States to apportion Congress, and with a number of other algorithms that have been proposed. We conclude that on every set of census data in this country's history, the heuristic-driven apportionment provably yields far fairer apportionments than those of any of the other algorithm considered, including the algorithm currently used by the United States for Congressional apportionment.
1. MOTIVATION AND OVERVIEW
How should the seats in the House of Representatives of the United States be
allocated among the states? The Constitution stipulates only that "Representa-
tives shall be apportioned among the several states according to their respective
numbers, counting the whole numbers of persons in each :." The obvious
implementation of this requirement would almost always yield fractional numbers
of seats. The issue of how to achieve fair integer seat allocations has been controversial
in this country virtually since its founding. In fact, many of the apportionment
algorithms we will discuss have been proposed and debated by famous historical
figures, including John Quincy Adams, Alexander Hamilton, Thomas Jefferson,
and Daniel Webster. The debate is far from over. In fact, the relative fairness of
two of the algorithms we will discuss in this paper was argued before the Supreme
Court in 1992 [Supreme 1992]. 1 We propose an apportionment method consisting
of a simulated-annealing search that is aimed at maximizing the fairness of the
resultant apportionments. Even though the complexity of the algorithm is high,
our implementation shows that the method is feasible for the cases of interest. In-
deed, we have been able to run it on the data conducted during all the census years
in US history and the results are conclusive: In all cases our method was provably
superior with respect to widely agreed fairness criteria to the most prominent
apportionment algorithms that have been used or proposed earlier.
Balinski and Young [1982] (see also [Balinski and Young 1985]) performed a detailed
comparative study, for six historical algorithms of Congressional apportion-
ment, of the degree to which the algorithms' allocations matched states' "quotas,"
i.e., their portion of the population times the House size. Mann and Shapley [Mann
and Shapley 1960; Mann and Shapley 1962] and others studied, for the actual used-
in-Congress seat allocations, the power indices (in the Electoral College) of each
state. This paper attempts to combine the strengths of these two research lines.
In particular, we agree with Balinski and Young both that allocations should be
"fair," and that, in light of 200 years of debate (colorfully recounted and analyzed by
Balinski and Young [1982]), obtaining new insights into the merits and weaknesses
of the six historical algorithms should be a priority. On the other hand, many
feel that "fairness" should be defined by a tight match between power and quotas,
rather than between allocations and quotas. Our feeling is very much in harmony
with modern political science theory, where it is widely recognized that allocations
Briefly put, the Supreme Court ruled that Congress acted within its authority in choosing the
currently used algorithm (the "Huntington-Hill Method"). However, the Supreme Court's decision
left open the possibility that Congress would be acting equally within its authority if it chose to
adopt some other algorithm. The court ruled that "the constitutional framework.delegate[s] to
Congress a measure of discretion broader than that accorded to the States [in terms of choosing
how to apportion], and Congress's apparently good-faith decision to adopt the [Huntington-]Hill
Method commands far more deference, particularly as it was made after decades of experience,
experimentation, and debate, was supported by independent scholars, and has been accepted
for half a century [Supreme 1992]." Regarding the decision, we mention only that the power
balancing issues discussed in this paper were not brought before the court, but that nonetheless
the experimental results of this paper suggest that among the two algorithms being discussed by
the court in the case, the Huntington-Hill algorithm in fact gives fairer apportionments in terms
of power balancing.
Power Balance and Apportionment Algorithms \Delta 3
do not necessarily directly correspond to power, and that power indices (see the
detailed definitions later in this paper) provide a potentially more accurate gauge
of power (see, e.g., the discussions in [Shapley 1981; Riker and Ordeshook 1973]). 2
So, in this light, we repeat the comparative study of Balinski and Young, but we
replace allocation comparisons with power index comparisons.
Of course, the historical algorithms were designed (in part-the full story is more
complex and political, and indeed led to the first presidential veto (see [Balinski
and Young 1982])) to achieve some degree of harmony and fairness between allocations
and quotas. This is not surprising, given that power indices had not
yet been invented. However, given that in this study our comparisons are based on
power indices, it seems natural to add to the six historical algorithms 3 an algorithm
tailored to achieve harmony between power indices and quotas. We have used a
heuristic based on the simulated annealing paradigm (see [Aarts and Korst 1989;
Metropolis et al. 1953; Kirkpatrick et al. 1983]), which finds an apportionment by
seeking to achieve a local minimum of the distance between normalized power indices
and quotas (the attribute "local" is with respect to a natural neighborhood
relation between apportionments). This heuristic yields results that are fairer to
those obtained by all the historical algorithms. We report in Section 3 the results
for the last census, 1990, but we have obtained similar results for all the census
years, 1790, 1800, . , 1980, and 1990.
The function class #P (first defined by Valiant [Valiant 1979a; Valiant 1979b])
is the counting version of NP. #P is the class of all functions f such that, for
some nondeterministic polynomial-time Turing machine N , for all inputs x it holds
that f(x) is the number of accepting computation paths of N(x). One problem in
studying power indices is that power indices are typically #P-complete [Prasad and
Kelly 1990; Garey and Johnson 1979] and, consequently, we perform a combinatorial
search that invokes at each iteration numerous #P-complete computations.
Fortunately, a dynamic programming approach, first proposed by Mann and Shapley
[1962], yields a pseudo-polynomial algorithm for computing the power indices,
i.e., an algorithm whose running time is polynomial in the size of the House and in
the number of states. Since these quantities have had reasonable values throughout
US history (the maximum values have been 435 and 50, which are also the current
values), we have been able to exactly compute the needed power indices.
2 For those unfamiliar with why allocations may not correspond to power, consider the following
typical motivating example. Suppose we have states A, B, and C with 6, 2, and 2 votes respectively.
Note that though between them states B and C have 40 per cent of the seat allocation, nonetheless
it is the case that in a majority-rule vote on some polarizing issue on which states have differing
interests and so their delegations vote as blocs, B and C have no power at all as A by itself is a
majority.
3 By the use of "the" in the context "the six historical algorithms" we do not mean to suggest that
no other algorithms have been proposed. Other algorithms have indeed been proposed (e.g., the
algorithm Condorcet suggested in 1793 ([Condorcet 1847], see [Balinski and Young 1982, p. 63])).
However, these six algorithms have been the key contenders in the apportionment discussion in
the United States.
2. DISCUSSION
In this section, we justify a number of decisions made in designing this study, and
we describe in more detail the background of the study.
2.1 Study Design
Our computer program takes as its input a list of states, hS
tions, h, and some other parameters regarding random
number generation and the implementation of the simulated annealing algorithm.
The program computes, for each state S i , the appropriate quota
We have considered the Banzhaf power index and the Shapley-Shubik power index.
They represent the most widely used quantitative ways to measure the power of a
player (or a state, in our parlance) in a voting game. It is well-known that the two
indices can, at least on artificially constructed examples, differ sharply (see, e.g.,
[Straffin 1978] and the references therein, and [Shapley 1981; Straffin 1977]). We
do not in this paper seek to resolve the broader question of whether power indices
are "correct" or "appealing" measures of power, or whether they thus should be
used to shape voting/apportionment systems (those are more issues of political
science than of experimental algorithms). Though there is much discussion in the
literature on the naturalness and usefulness of power indices, our study simply seeks
to provide-to those who do place value in power indices-quantitative information
on the comparative power distributions for the historical apportionment algorithms
and for simulated annealing. We hope that this information will also be useful
in the political science debate on the more general issue of choosing the "right"
apportionment scheme, and in Section 4 we mention the directions this information
suggests.
The Banzhaf power index (see, e.g., the detailed discussion in [Dubey and Shapley
1979]) is defined in terms of winning coalitions. A winning coalition is a subset S
of states such that the sum of the votes of the states in S is larger than half of the
total number of votes (which, of course, is equal to the House size). A state i is
critical for a coalition S if (a) i 2 S, (b) S is a winning coalition, and (c) S \Gamma fig is
not a winning coalition. The Banzhaf power index of a state i is, by definition, the
probability that for a randomly chosen coalition S (that is, for a coalition chosen
randomly from the set of all possible coalitions, not just from the set of winning
coalitions), it holds that i is critical for S.
The Shapley-Shubik power index [Shapley and Shubik 1954] is defined in terms
of linear orderings of states, which, intuitively, represent the extent to which the
states are interested in passing some bill (the first state in the ordering is the
strongest supporter of the bill, while the last one is the strongest opponent). Let
be such an ordering. A state i is a pivot for the ordering
- if it appears in some position k and i is critical for the coalition formed by the
first k states (in other words, the pivot of an ordering is the state whose joining
turns the developing coalition into a winning coalition). The Shapley-Shubik power
index of a state i is the probability that for a randomly chosen ordering - it holds
that i is the pivot of -.
Power Balance and Apportionment Algorithms \Delta 5
In order to calculate the closeness of the power indices to the quota, we have to
normalize them. That is, if pow i is the power index (Banzhaf or Shapley-Shubik)
of state i, we define
normpow
where, recall, h is the House size. This is the normalization used by Mann and Shapley
[1960]. For the rest of this discussion, by power of a state we will mean its normalized
power index (Banzhaf or Shapley-Shubik). Note that
h, and thus these normalized powers make it easier to compare power-to-quota
closeness. 4 The main metric that we have used to evaluate the power-to-quota
closeness is the L 2 metrics applied on proportions as defined below.
L 2 on proportions:
0-i!n
Although other measures can be used, we feel the L 2 on proportions to be the
most relevant one. We have performed experiments also with respect to the L 1
metric on differences and proportions and L 2 on differences, and in all cases we
reached the same conclusions. For completeness, here are the definitions of these
three other metrics.
L 1 on differences:
0-i!n
L 2 on differences:
0-i!n
L 1 on proportions:
0-i!n
The contrast between the "difference" and the "proportion" measures can be
dramatic. For example, suppose states A and B have quotas 1.5 and 40.5 but are
respectively given 2 and 41 votes. The "differences" measures treat the two states
similarly, but in the "proportions" measures, state A is viewed as being far more out
of balance than state B. However, we repeat, the conclusions of our investigation
remain the same, irrespective of the metric used.
The program apportions the votes via the six historical algorithms-Adams,
Dean, Huntington-Hill (we abbreviate this "H-Hill" in our tables; the method is also
sometimes referred to in the literature simply as the Hill Method), Webster (which
is sometimes also referred to in the literature as the Webster-Willcox Method), Jef-
ferson, and Hamilton-and simulated annealing. The algorithms work as follows.
Let us first discuss the algorithms of Adams, Dean, Huntington-Hill, Webster, and
Jefferson. Informally, they work as follows. One partitions the non-negative real
4 We note that many researchers prefer to use the Banzhaf index without normalization.
6 \Delta L.A. Hemaspaandra et al.
line into adjacent intervals, each corresponding to a number of votes. Then one
seeks an integer such that if one divides each state's population by that integer
and give each state the number of votes corresponding to the interval in which that
value falls, the sum of votes handed out equals the desired house size.
More formally, let I be such that
I
We say an apportionment hv 0 ,v 1 is the 5 sliding divisor apportionment
with respect to I there exists a real number d such that
The five historical sliding divisor algorithms are defined as follows (see also [Balinski
and Young 1982]).
Adams:. I
I
Dean:. I
I
Huntington-Hill:. I
I
Webster:. I
I
Jefferson:. I
Note, in particular, that the Dean, Huntington-Hill, and Webster algorithms describe
the intervals between, respectively, the harmonic, geometric, and arithmetic
means of successive integers. The algorithm currently in use in the United States
is the method of geometric means, i.e., the Huntington-Hill algorithm.
An important caveat is that the Constitution requires that each state be given at
least one representative. However, this artificial requirement would taint the comparative
analysis of the algorithms. In this study, we do allow algorithms to assign
zero votes to a state. For example, for the 1990 census data the Jefferson algorithm
allocates 0 votes to Wyoming. To learn whether our ignoring the Constitution's
"one vote minimum" rule affected our results, we also ran our program with the
added proviso that the sliding divisor algorithms were not allowed to assign 0 votes
to any state (we achieved this by setting I 1 := I 0 [ I 1 and I 0 := ;) and we obtained
the same result: The simulated annealing algorithm was still the best and
the Jefferson algorithm was still the worst.
5 It is not hard to see that if such exists, it is unique. Such solutions do not always exists. For
example, no sliding divisor algorithm can apportion two equal states with any odd House size.
However, for the five historical sliding divisor algorithms and large populations that are random
and independent in their low-order bits (informally, actual populations), nonexistence of solutions
is unlikely to occur, and, for historical census data, has never occurred.
Power Balance and Apportionment Algorithms \Delta 7
The Hamilton algorithm is quite different from the sliding divisor algorithms
described above. The Hamilton algorithm initially assigns to each state, S i , exactly
votes. Then it assigns one extra vote to each of the h \Gamma
states
having the largest values of q that ties in the fractional part can cause
this algorithm to fail to be well-defined, but, again, in practice this is unlikely to
occur, and indeed never has under actual historical census data.)
Finally, the simulated annealing algorithm that we propose works as follows. Let
us say that two apportionments are
neighbors of each other if b is obtained from a by shifting one vote from some
state i to some state j, i.e., there exist i and j, i 6= j, such that
apportionment (summing to h) is made in a
relatively arbitrary way. (The algorithm used in the program intentionally makes
an initial apportionment that gives a terrible match between powers and quotas.
Thus, it is up to the rest of the simulated annealing algorithm to try to fix this poor
initial assignment.) Then, repeatedly, a neighbor b of the current apportionment
a is randomly generated. If b is at least as good as a (in the sense that b has a
power-to-quota distance no greater than that of a), then b becomes the current
apportionment. Even if the new apportionment b is worse, it still has a chance
to become the current apportionment. Namely, let \Delta be the difference between
the power-to-quota distance for b and the power-to-quota distance for a. Since
we are in the case in which b is worse than a, \Delta is positive. Throughout this
process, we consider a current temperature that is gradually decreasing (each time
a given number of iterations have occurred, the current temperature is decreased by
multiplying it by a certain constant that is less than one, which is called the cooling
Let t be the value of the current temperature. We randomly generate a
real number r. If r ! e \Gamma\Delta=t , then b is taken as the current apportionment in place
of a. Observe that as the temperature t approaches the value zero, the probability
that r is less than e \Gamma\Delta=t gets smaller and smaller, and thus after an initial period in
which jumps between various descending hills leading to local optima are likely, the
process is stabilized ("it freezes," i.e., the probability of choosing an apportionment
that is worse than the current one becomes close to zero), with high probability
at some local optimum (and the hope of the simulated annealing approach is that
that local optimum is not too much worse in quality than the global optimum).
The exact stopping criterion is explained in Section 3.
The results of the simulated annealing algorithm are, of course, sensitive to the
values of the initial temperature and of the cooling factor, as well as to the choice
of the initial apportionment. Our intention has been not to fine-tune these values
but rather to prove that the historical methods can be easily, soundly beaten by
a modern computer science-based heuristic approach, on inputs drawn from real
census data. As we want to emphasize the realization of this goal, we report in
Section 3 the results for only one (rather arbitrary) setting of these parameters.
We plan to pursue in the future a more thorough investigation of the impact of the
parameter settings for the apportionment problem.
We digress here to mention that this algorithm can potentially beat the greedy
algorithm, 6 in which at each step we choose a better neighbor of the current ap-
6 However, for the real census data that we have used, the greedy algorithm yielded results very
8 \Delta L.A. Hemaspaandra et al.
portionment until we are stuck at a local optimum. Indeed, we found a four-state
instance in which the greedy algorithm gets stuck at a local optimum that is not a
global optimum. In this instance, 100 representatives must be apportioned between
4 states having populations 823, 801, 105, 101. It can be seen that a = (50; 34; 14; 2)
are two local optima with a being better than b (we are referring
here to the Shapley-Shubik power index, which is defined below). However,
starting from b and going through at-least-as-good-as b neighbors there is no way
to reach a (i.e., (b; a) is not in the transitive closure of the binary relation "neighbor
at-least-as-good-as b") because at some moment we have to pass through an apportionment
of the form (44;  ;  ;  ). But, it can be verified that all apportionments of
this form are worse than b and thus are not reachable from b with the greedy algo-
rithm. In a certain precise sense, this is the smallest such example. In particular,
it is simple to prove that there are no examples such as the one above with 2 or 3
states, that is, in all 2 or 3 state cases, all locally optimal apportionments are also
globally optimal.
Prasad and Kelly [1990] have shown that the Banzhaf power index is #P-complete
and Garey and Johnson [1979] have shown that the Shapley-Shubik power index
is #P-complete, where the complexity class #P as usual denotes the counting version
of NP [Valiant 1979a; Valiant 1979b]-#P is the class of all functions f such
that, for some nondeterministic polynomial-time Turing machine N , for each x it
holds that f(x) is the number of accepting computation paths N has on input x.
Much of the past 20 years of research in theoretical computer science has been
devoted to proving that NP-complete problems (and thus #P-complete functions)
cannot be feasibly computed unless a wide range of implausible consequences occur
(see the survey [Sipser 1992]). For example, Toda [1991] (see also [Beigel et al.
1991; Toda and Ogiwara 1992; Gupta 1995; Regan and Royer 1995]) has shown
that Turing access to #P subsumes the entire polynomial hierarchy. However, a
dynamic programming approach will allow us to perform an exact computation of
both the Banzhaf power index and the Shapley-Shubik power index even for the
relatively large inputs of the censuses involving 50 states. The dynamic programming
approach for this problem was proposed by Mann and Shapley [1962]. We
use the notation from the previous section. The algorithm involves, for each state
constructing a matrix i C of order
House size, and
number of states:
Also, let Q be the minimum number of votes needed for a winning coalition (i.e.,
1). The entries in this matrix have the following
represents the number of coalitions not containing state i and having k states whose
votes sum to j. Let i C '
j;k be the number of coalitions containing k states from
close to those given by the simulated annealing algorithm, in particular also beating the historical
algorithms. This is true even though our implementation of the greedy algorithm accepted the
first local improvement found rather than enumerating all neighbors and accepting one yielding a
steepest descent.
Power Balance and Apportionment Algorithms \Delta 9
whose votes sum up to k. Observe that, for
Also, the following recurrence holds:
(note that in the above recurrence the
predecessor of
j;k . To find the Banzhaf power
index of state S i , we have to compute the number of coalitions for which S i is
critical (and then divide it by the total number of coalitions). This value is given
by
These are all coalitions not containing S i that are losing but with the addition of
To find the Shapley-Shubik power index of state S i , we have to compute the
number of linear orderings for which S i is a pivot (and then divide it by the total
number of linear orderings). This value is given by
Thus, the computation of both power indices reduces to the computation of the
entries of the matrix i C, which can be determined by calculating iteratively the
matrices Some shortcuts can be obtained using the following
observations. Note that in Equations (2.1) and (2.2), we need only the entries with
1. By looking at complementary coalitions, one can see that i C
. Thus, the entries in the matrix with column index k ? (n \Gamma 1)=2
can be computed, using the above formula, from the entries with k - (n \Gamma 1)=2 and
when this is done the largest row index j that we need is still Q\Gamma1. Consequently, we
have to compute only a quarter of the entries in matrix i C, namely those entries with
row index verifying verifying
After we have computed the matrix i C for state S i , we don't have to start from
scratch when passing to state S i+1 to compute i+1 C . Indeed, it is not difficult
to see that i+1 C by convention the
entries with negative row or column index are 0.
This algorithm is polynomial in n and Q (but, of course, it is not polynomial
in the length of a natural encoding of the input instance, because the reasonable
encodings of Q
bits). Nevertheless, since
the censuses so far h - 435, we have been able to compute the exact values of the
Banzhaf and Shapley-Shubik for the census years 1790, 1800, 1810, . , 1980, and
State Pop. Quota SA-B SA-SS Adams Dean H-Hill Webst Jeffer Hamilt
OH 10847115 19.0206 19 19
MI 9295297 16.2995
IN
MO 5117073 8.9729 9 9 9 9 9 9 9 9
WI 4891769 8.5778 9 9 9 9 9 9 9 9
CO
IA
MS
Totals 248072974 435.0000 435 435 435 435 435 435 435 435

Table

1. States, Populations, Quotas, and Apportionments: L2-of-Proportions Evaluation
Power Balance and Apportionment Algorithms \Delta 11
State Quota SA-B Adams Dean H-Hill Webst Jeffer Hamilt
IL 20.0437 19.8279 18.7446 19.7091 19.7097 19.7102 20.6716 19.7102
MI 16.2995 15.7744 15.7255 15.6914 15.6919 15.6924 16.6546 15.6924
GA 11.3597 11.7810 10.7599 10.7400 10.7404 10.7408 10.7208 10.7408
MA 10.5499 10.7900 9.7745 9.7569 10.7404 10.7408 10.7208 10.7408
IN 9.7218 9.8015 9.7745 9.7569 9.7573 9.7577 9.7399 9.7577
MO 8.9729 8.8152 8.7913 8.7758 8.7761 8.7765 8.7609 8.7765
WI 8.5778 8.8152 8.7913 8.7758 8.7761 8.7765 8.7609 8.7765
TN 8.5522 8.8152 8.7913 8.7758 8.7761 8.7765 7.7834 8.7765
MD 8.3844 8.8152 7.8098 7.7964 7.7967 7.7970 7.7834 7.7971
MN 7.6718 7.8308 7.8098 7.7964 7.7967 7.7970 7.7834 7.7971
LA 7.3998 7.8308 7.8098 6.8185 6.8188 6.8191 6.8074 6.8191
AL 7.0852 6.8482 6.8301 6.8185 6.8188 6.8191 6.8074 6.8191
KY 6.4622 6.8482 6.8301 5.8420 5.8422 5.8425 5.8326 5.8425
AZ 6.4270 6.8482 6.8301 5.8420 5.8422 5.8425 5.8326 5.8425
SC 6.1140 5.8671 5.8517 5.8420 5.8422 5.8425 5.8326 5.8425
CO 5.7768 5.8671 5.8517 5.8420 5.8422 5.8425 5.8326 5.8425
CT 5.7640 5.8671 5.8517 5.8420 5.8422 5.8425 5.8326 5.8425
IA 4.8691 4.8873 4.8746 4.8666 4.8668 4.8670 4.8589 4.8670
MS 4.5122 4.8873 4.8746 4.8666 4.8668 3.8925 3.8861 3.8925
KS 4.2919 3.9085 4.8746 3.8922 3.8923 3.8925 3.8861 3.8925
AR 4.1220 3.9085 3.8984 3.8922 3.8923 3.8925 3.8861 3.8925
WV 3.1449 2.9307 2.9231 2.9185 2.9186 2.9187 2.9139 2.9187
UT 3.0210 2.9307 2.9231 2.9185 2.9186 2.9187 2.9139 2.9187
NE 2.7677 2.9307 2.9231 2.9185 2.9186 2.9187 1.9423 2.9187
NM 2.6567 2.9307 2.9231 2.9185 2.9186 2.9187 1.9423 2.9187
HI 1.9433 1.9534 1.9484 1.9453 1.9454 1.9455 1.9423 1.9455
ID 1.7654 1.9534 1.9484 1.9453 1.9454 1.9455 0.9711 1.9455
RI 1.7596 1.9534 1.9484 1.9453 1.9454 1.9455 0.9711 1.9455
MT 1.4012 0.9766 1.9484 1.9453 0.9726 0.9727 0.9711 0.9727
ND 1.1201 0.9766 1.9484 0.9726 0.9726 0.9727 0.9711 0.9727
WY 0.7954 0.9766 0.9741 0.9726 0.9726 0.9727 0.0000 0.9727
Totals 435.0000 435.0000 435.0000 435.0000 435.0000 435.0000 435.0000 435.0000

Table

2. States, Quotas, and Normalized Powers: Banzhaf Power Index and L2-of-Proportions
State Quota SA-SS Adams Dean H-Hill Webst Jeffer Hamilt
IL 20.0437 20.0487 18.9942 19.9876 19.9858 19.9834 20.9756 19.9779
OH 19.0206 19.0005 17.9516
MI 16.2995 15.8872 15.8820 15.8399 15.8385 15.8366 16.8206 15.8324
GA 11.3597 11.8058 10.7941 10.7662 10.7653 10.7640 10.7362 10.7612
MA 10.5499 10.7974 9.7907 9.7656 10.7653 10.7640 10.7362 10.7612
IN 9.7218 9.7938 9.7907 9.7656 9.7647 9.7636 9.7384 9.7611
MO 8.9729 8.7947 8.7920 8.7695 8.7687 8.7677 8.7452 8.7654
WI 8.5778 8.7947 8.7920 8.7695 8.7687 8.7677 8.7452 8.7654
TN 8.5522 8.7947 8.7920 8.7695 8.7687 8.7677 7.7565 8.7654
MD 8.3844 8.7947 7.7977 7.7779 7.7772 7.7763 7.7565 7.7743
MN 7.6718 7.8001 7.7977 7.7779 7.7772 7.7763 7.7565 7.7743
LA 7.3998 7.8001 7.7977 6.7907 6.7902 6.7894 6.7721 6.7876
AL 7.0852 6.8100 6.8080 6.7907 6.7902 6.7894 6.7721 6.7876
KY 6.4622 6.8100 6.8080 5.8079 5.8075 5.8068 5.7921 5.8053
AZ 6.4270 6.8100 6.8080 5.8079 5.8075 5.8068 5.7921 5.8053
SC 6.1140 5.8244 5.8226 5.8079 5.8075 5.8068 5.7921 5.8053
CO 5.7768 5.8244 5.8226 5.8079 5.8075 5.8068 5.7921 5.8053
CT 5.7640 5.8244 5.8226 5.8079 5.8075 5.8068 5.7921 5.8053
OK 5.5158 5.8244 5.8226 5.8079 5.8075 4.8285 4.8164 4.8273
IA 4.8691 4.8430 4.8416 4.8295 4.8291 4.8285 4.8164 4.8273
MS 4.5122 4.8430 4.8416 4.8295 4.8291 3.8545 3.8448 3.8535
KS 4.2919 3.8660 4.8416 3.8553 3.8549 3.8545 3.8448 3.8535
AR 4.1220 3.8660 3.8649 3.8553 3.8549 3.8545 3.8448 3.8535
WV 3.1449 2.8933 2.8924 2.8853 2.8850 2.8847 2.8775 2.8840
UT 3.0210 2.8933 2.8924 2.8853 2.8850 2.8847 2.8775 2.8840
NE 2.7677 2.8933 2.8924 2.8853 2.8850 2.8847 1.9143 2.8840
NM 2.6567 2.8933 2.8924 2.8853 2.8850 2.8847 1.9143 2.8840
NV 2.1074 1.9247 1.9242 1.9194 1.9193 1.9190 1.9143 1.9186
HI 1.9433 1.9247 1.9242 1.9194 1.9193 1.9190 1.9143 1.9186
ID 1.7654 1.9247 1.9242 1.9194 1.9193 1.9190 0.9551 1.9186
RI 1.7596 1.9247 1.9242 1.9194 1.9193 1.9190 0.9551 1.9186
ND 1.1201 0.9603 1.9242 0.9577 0.9576 0.9575 0.9551 0.9573
WY 0.7954 0.9603 0.9600 0.9577 0.9576 0.9575 0.0000 0.9573
Totals 435.0000 435.0000 435.0000 435.0000 435.0000 435.0000 435.0000 435.0000

Table

3. States, Quotas, and Normalized Powers: Shapley-Shubik Power Index and L2-of-
Power Balance and Apportionment Algorithms \Delta 13
Algorithm Quota to Rep-Normed Power Distance
under the L2-of-Proportions Metric
H-Hill 0.375372
Webst 0.387777
Hamilt 0.394220
Dean 0.438127
Adams 1.821126
Jeffer 1.906251

Table

4. Errors Between Quotas and Rep-Normed Power: Banzhaf Power Index and L2-of-
Proportions Evaluation Metric.
Algorithm Quota to Rep-Normed Power Distance
under the L2-of-Proportions Metric
H-Hill 0.382663
Webst 0.401829
Hamilt 0.411409
Dean 0.424247
Adams 1.687721
Jeffer 1.974655

Table

5. Errors Between Quotas and Rep-Normed Power: Shapley-Shubik Power Index and
L2-of-Proportions Evaluation Metric.
3. RESULTS
We present here the results of our program for the 1990 census. Table 1 shows
the populations and quotas for the 1990 census, as well as the apportionments
that result from the six historical algorithms and the simulated annealing algo-
rithm, under both the Banzhaf (with column label SA-B) and the Shapley-Shubik
(with column label SA-SS) power indices. Of course, the columns not reporting
on the results of the simulated annealing algorithm do not need to be labeled with
Banzhaf or Shapley-Shubik, as only in the simulated annealing columns is the apportionment
dependent on the power index being used. Tables 2 and 3 show the
normalized power indices. Tables 4 and 5 show the distance between powers and
quotas according to the L2-on-proportions metric. The tables represent runs with
the following parameters used in the simulated annealing algorithm: the cooling
factor was 0.9, 7 the initial temperature was 100, the number of iterations per-
7 Ideally, simulated annealing should be done with a cooling factor as close to 1 as possible (as,
conceptually, gentle cooling is more likely to achieve a good result). Due to the limited computing
resources we had available-SUN SPARCstation 10's serving as shared cycle servers-we had to
use a cooling factor that is more severe than we would have ideally chosen. Note that this computational
limitation if anything degrades the quality of our simulated annealing apportionment.
Yet, even with this handicap, our simulated annealing algorithm outperformed all the historical
algorithms. Also, we note that if the experimental algorithms paradigm is to be successful, it is
important that it be useful not just to the few people with access to supercomputers, but also to
people using more modest computing facilities. We hope that this study, in which a modest workstation
performed the computations showing that simulated annealing outperforms the currently
used algorithm, is an example of this.
14 \Delta L.A. Hemaspaandra et al.
formed at each temperature was 1000, and the stopping factor was 5. The stopping
factor is used to control termination as follows. Recall that at each temperature
the algorithm generates and considers CoolingIter potential swaps, and then it decreases
the current temperature via Temperature := Temperature   CoolingFactor.
However, the algorithm also keeps track of how many potential swaps have been
considered since the last swap that was performed (recall that a swap is performed
either because it improves the quality of the current state, or because it degrades
the quality of the current state but was randomly chosen via the temperature-
based probabilistic condition discussed in Section 2.1). If this number has reached
CoolingIter   StoppingFactor (informally, at about the last StoppingFactor temperatures
no move has been made-except this analysis can wrap around the border
between temperatures), then the algorithm stops and the current seat allocation is
its output.
4. CONCLUSIONS
For all census years and for both the Banzhaf and Shapley-Shubik power index, the
simulated annealing algorithm provides a power balance more in harmony with quotas
than do any of the historical algorithms. Of course, this is not overly shocking,
as those algorithms were tailored to achieve a certain harmony between quotas and
votes apportioned, rather than between quotas and the normalized power vectors
induced by the votes apportioned. Generally, the simulated annealing algorithm
achieves its strong performance by shifting votes away from the larger state(s),
as even the large-state-hostile Adams algorithm is not quite so large-state-hostile
as the simulated annealing algorithm. In some sense, the fact (which has been
noted elsewhere and which is very apparent in the "State, Quotas, and Normalized
Powers" tables of Section 3) that power indices often disproportionally skew
power towards very large states-the so-called "big state bias"-is something the
simulated annealing algorithm is able to attempt to directly remedy. Thus, if one's
notion of fairness is to have a close match between the normalized Banzhaf or
Shapley-Shubik power indices of the states and the vector of quotas, the simulated
annealing algorithm is a strong contender, and seems to provide a better match
than any of the historical algorithms.
Our results also suggest that, if one limits one's universe to the six historical
algorithms, the United States has chosen the correct one, at least in terms of performance
with respect to historical census data: The Huntington-Hill algorithm
seems the most power-fair of the historical algorithms, albeit far less fair that simulated
annealing. Indeed, in the 1990 tables one can see that simulated annealing
and the Huntington-Hill algorithm treated small states (states receiving no more
than five seats) identically. The only difference in their apportionments is that,
relative to the Huntington-Hill algorithm, simulated annealing shifts voting weight
away from large states and towards middle-sized states.
The political implications of our results are somewhat surprising. The fact that
Adams's algorithm gives large states (e.g., California) far fewer seats than their
quotas would seem to entitle them to might suggest that large states are cheated
under Adams's algorithm, and indeed both some scholarly analyses [Balinski and
Young 1982] and the Supreme Court decision mentioned earlier [Supreme 1992]
have been primarily concerned with the correspondence between seats and quotas.
Power Balance and Apportionment Algorithms \Delta 15
However, our study shows clearly that the bias power indices show towards large
states is so pronounced that it overwhelms the "vote skewing towards small states"
of the Adams algorithm. Of course, as the tables show, a large-state-skewed algorithm
such as Jefferson's even more strikingly grants disproportionately much
power to large states. Overall, in terms of fairness, our results suggest that the
current apportionment algorithm used in the United States (the Huntington-Hill
algorithm) gives disproportionately much power to large states at the cost of giving
disproportionately little power to some middle-sized states, while treating small
states fairly.
As a final note, nothing above is meant to suggest that the simulated annealing
algorithm might be politically feasible. It is quite possible that, in a probabilistic
implementation, the vote allocation chosen might depend on the seed given to the
random number generator. Worse still it is possible, at least in artificial exam-
ples, that different vote allocations would achieve the same degree of quota/power
harmony. Thus, the algorithm itself would suggest no preference between the allo-
cations, but legislators might well have strong (and differing) preferences.

Acknowledgments

: The first author was a Bridging Fellow at the University
of Rochester's Department of Political Science when this work was started. He
thanks that department's faculty for encouraging his interest in political science
and voting systems, and for helpful conversations, in particular including suggesting
the discussion of the final paragraph of the conclusions section. He also thanks the
University of Rochester for the fellowship, and gratefully acknowledges a lifelong
debt to Michel Balinski for, many years ago, introducing him both to the study
of apportionment and to research. The authors are grateful to William Lucas of
the Claremont Graduate School and Peter van Emde Boas of the University of
Amsterdam for proofreading an earlier version and for helpful comments. We also
thank Joe Malkevitch for helpful comments. We are grateful to ACM Journal on
Experimental Algorithmics editor Bernard Moret and two anonymous referees for
valuable comments and suggestions. The authors alone, of course, are responsible
for any errors.



--R

Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial optimization and neural computing.
Fair Representation: Meeting the Ideal of One Man
Fair representation: Meeting the ideal of one man

Probabilistic polynomial time is closed under parity reductions.
Plan de constitution
Mathematical properties of the Banzhaf power index.
Mathematics of Operations Research 4
Computers and Intractability: A Guide to the Theory of NP-Completeness

Closure properties and witness reduction.

Values of large games
Values of large games

Equations of state calculations by fast computing machines.

On closure properties of bounded two-sided error complexity classes
An Introduction to Positive Political Theory.
Measurement of power in political systems.
A method of evaluating the distribution of power in a committee system.
The history and status of the P versus NP question.
Probability models for power indices.


PP is as hard as the polynomial-time hierarchy
Counting classes are at least as hard as the polynomial-time hierarchy
The complexity of computing the permanent.
The complexity of enumeration and reliability problems.
--TR
simulated annealing;power indices;apportionment algorithms