Power balance and apportionment algorithms for the United States Congress

ABSTRACT

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.

REFERENCES

• 1: Emile Aarts , Jan Korst, Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing, John Wiley & Sons, Inc., New York, NY, 1989
• 2: BALINSKI, M. AND YOUNG, H. 1982. <i>Fair Representation: Meeting the Ideal of One Man, One Vote</i>. Yale University Press, New Haven.
• 3: BALINSKI, M. AND YOUNG, H. 1985. Fair representation: Meeting the ideal of one man, one vote. In H. YOUNG Ed., <i>Fair Allocation</i>, pp. 1-29. American Mathematical Society. Proceedings of Symposia in Applied Mathematics, V. 33.
• 4: Richard Beigel , Lane A. Hemachandra , Gerd Wechsung, Probabilistic polynomial time is closed under parity reductions, Information Processing Letters, v.37 n.2, p.91-94, Jan. 31, 1991 [doi>10.1016/0020-0190(91)90140-D]
• 5: CONDORCET, J. 1847. Plan de constitution, presenté à la convention nationale les 15 et 16 Fevrier 1793. In A. C. O'CONNOR AND M. ARAGO Eds., <i>Oeuvres de Condorcet, V. 12</i>. Firmin Didot Frères.
• 6: DUBEY, P. AND SHAPLEY, L. 1979. Mathematical properties of the Banzhaf power index. <i>Mathematics of Operations Research 4</i>, 2 (May), 99-131.
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: Sanjay Gupta, Closure properties and witness reduction, Journal of Computer and System Sciences, v.50 n.3, p.412-432, June 1995 [doi>10.1006/jcss.1995.1032]
• 9: KIRKPATRICK, S., GELATT, C., JR., AND VECCHI, M. 1983. Optimization by simulated annealing. <i>Science 220</i>, 4598 (May), 671-680.
• 10: MANN, I. AND SHAPLEY, L. 1960. Values of large games, IV: Evaluating the electoral college by Monte Carlo techniques. Research Memorandum RM-2651 (ASTIA No. AD 246277) (Sept.), The Rand Corporation, Santa Monica, CA.
• 11: MANN, I. AND SHAPLEY, L. 1962. Values of large games, VI: Evaluating the electoral college exactly. Research Memorandum RM-3158-PR, The Rand Corporation, Santa Monica, CA.
• 12: METROPOLIS, N., ROSENBLUTH, A., ROSTENBLUTH, M., TELLER, A., AND TELLER, E. 1953. Equations of state calculations by fast computing machines. <i>Journal of Chemical Physics 21</i>, 6, 1087-1091.
• 13: K. Prasad , J. S. Kelly, NP-completeness of some problems concerning voting games, International Journal of Game Theory, v.19 n.1, p.1-9, Apr. 1990 [doi>10.1007/BF01753703]
• 14: REGAN, K. AND ROYER, J. 1995. On closure properties of bounded two-sided error complexity classes. <i>Mathematical Systems Theory 28</i>, 3, 229-244.
• 15: RIKER, W. AND ORDESHOOK, P. 1973. <i>An Introduction to Positive Political Theory</i>. Prentice-Hall.
• 16: SHAPLEY, L. 1981. Measurement of power in political systems. In W. LUCAS Ed., <i>Game Theory and its Applications</i>, pp. 69-81. American Mathematical Society. Proceedings of Symposia in Applied Mathematics, V. 24.
• 17: SHAPLEY, L. AND SHUBIK, M. 1954. A method of evaluating the distribution of power in a committee system. <i>American Political Science Review 48</i>, 787-792.
• 18: Michael Sipser, The history and status of the P versus NP question, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.603-618, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129771]
• 19: STRAFFIN, P. 1978. Probability models for power indices. In P. ORDESHOOK Ed., <i>Game Theory and Political Science</i>, pp. 477-510. New York University Press.
• 20: STRAFFIN, P., JR. 1977. Homogeneity, independence, and power indices. <i>Public Choice 30 (Summer)</i>.
• 21: Supreme. 1992. United States Department of Commerce et al. versus Montana et al. US Supreme Court Case 91-860. Decided March 31, 1992.
• 22: Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
• 23: Seinosuke Toda , Mitsunori Ogiwara, Counting classes are at least as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.21 n.2, p.316-328, April 1992 [doi>10.1137/0221023]
• 24: VALIANT, L. 1979a. The complexity of computing the permanent. <i>Theoretical Computer Science 8</i>, 189-201.
• 25: VALIANT, L. 1979b. The complexity of enumeration and reliability problems. <i>SIAM Journal on Computing 8</i>, 3, 410-421.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY

General Terms:
Algorithms, Experimentation

Keywords:
apportionment algorithms, power indices, simulated annealing