{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:18:23Z","timestamp":1778296703916,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540679011","type":"print"},{"value":"9783540446125","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_5","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:28:20Z","timestamp":1178357300000},"page":"64-83","source":"Crossref","is-referenced-by-count":11,"title":["Computational Politics: Electoral Systems"],"prefix":"10.1007","author":[{"given":"Edith","family":"Hemaspaandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"5_CR1","volume-title":"Technical Report MIT\/LCS\/TM-131","author":"L. Adleman","year":"1979","unstructured":"L. Adleman. Time, space, and randomness. Technical Report MIT\/LCS\/TM-131, MIT, Cambridge, MA, April1979."},{"key":"5_CR2","unstructured":"K. Arrow. Social Choice and Individual Values. John Wiley and Sons, 1951 revised editon, 1963."},{"key":"5_CR3","volume-title":"Fair Representation: Meeting the Ideal of One Man, One Vote","author":"M. Balinski","year":"1982","unstructured":"M. Balinski and H. Young. Fair Representation: Meeting the Ideal of One Man, One Vote. Yale University Press, New Haven, 1982."},{"key":"5_CR4","unstructured":"M. Balinski and H. Young. Fair representation: Meeting the ideal of one man, one vote. In H. Young, editor, Fair Allocation, pages 1\u201329. American Mathematical Society, 1985. Proceedings of Symposia in Applied Mathematics, V. 33."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/BF00295861","volume":"6","author":"J. Bartholdi III","year":"1989","unstructured":"J. Bartholdi, III, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227\u2013241, 1989.","journal-title":"Social Choice and Welfare"},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00303169","volume":"6","author":"J. Bartholdi III","year":"1989","unstructured":"J. Bartholdi III, C. Tovey, and M. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6:157\u2013165, 1989.","journal-title":"Social Choice and Welfare"},{"issue":"8\/9","key":"5_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0895-7177(92)90085-Y","volume":"16","author":"J. Bartholdi III","year":"1992","unstructured":"J. Bartholdi III, C. Tovey, and M. Trick. How hard is it to control an election ? Mathematical and Computer Modeling, 16(8\/9):27\u201340, 1992.","journal-title":"Mathematical and Computer Modeling"},{"issue":"2","key":"5_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0020-0190(91)90140-D","volume":"37","author":"R. Beigel","year":"1991","unstructured":"R. Beigel, L. Hemachandra, and G. Wechsung. Probabilistic polynomial time is closed under parity reductions. Information Processing Letters, 37(2):91\u201394, 1991.","journal-title":"Information Processing Letters"},{"key":"5_CR9","unstructured":"D. Black. Theory of Committees and Elections. Cambridge University Press, 1958."},{"issue":"1","key":"5_CR10","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"91","author":"S. Buss","year":"1991","unstructured":"S. Buss and L. Hay. On truth-table reducibility to SAT. Information and Computation, 91(1):86\u2013102, 1991.","journal-title":"Information and Computation"},{"issue":"6","key":"5_CR11","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232\u20131252, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"5_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95\u2013111, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR13","unstructured":"M. J. A. N. de Caritat, Marquis de Condorcet. Essai sur l\u2019Application de L\u2019Analyse \u00e1 la Probabilit\u00e9 des D\u00e9cisions Rendues \u00e1 la Pluraliste des Voix. 1785. Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale."},{"key":"5_CR14","unstructured":"C. Dodgson. A method of taking votes on more than two issues, 1876. Pamphlet printed by the Clarendon Press, Oxford, and headed \u201cnot yet published\u201d (see the discussions in [31,9], both of which reprint this paper)."},{"issue":"2","key":"5_CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1287\/moor.4.2.99","volume":"4","author":"P. Dubey","year":"1979","unstructured":"P. Dubey and L. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99\u2013131, May 1979.","journal-title":"Mathematics of Operations Research"},{"key":"5_CR16","volume-title":"An introduction to probability theory and its applications","author":"W. Feller","year":"1968","unstructured":"W. Feller. An introduction to probability theory and its applications. Wiley, New York, 1968."},{"key":"5_CR17","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 439\u2013445. IEEE Computer Society Press, 1983.","DOI":"10.1109\/SFCS.1983.21"},{"issue":"3","key":"5_CR19","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299\u2013322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0304-3975(91)90282-7","volume":"83","author":"L. Hemachandra","year":"1991","unstructured":"L. Hemachandra and G. Wechsung. Kolmogorov characterizations of complexity classes. Theoretical Computer Science, 83:313\u2013322, 1991.","journal-title":"Theoretical Computer Science"},{"key":"5_CR21","unstructured":"E. Hemaspaandra. The complexity of Kemeny elections. In preparation."},{"issue":"6","key":"5_CR22","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E. Hemaspaandra","year":"1997","unstructured":"E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Exact analysis of Dodgson elections: Lewis Carroll\u2019s 1876 voting system is complete for parallel access to NP. Journal of the ACM, 44(6):806\u2013825, 1997.","journal-title":"Journal of the ACM"},{"issue":"2","key":"5_CR23","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/261342.261344","volume":"28","author":"E. Hemaspaandra","year":"1997","unstructured":"E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Raising NP lower bounds to parallel NP lower bounds. SIGACT News, 28(2):2\u201313, 1997.","journal-title":"SIGACT News"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"L. Hemaspaandra, K. Rajasethupathy, P. Sethupathy, and M. Zimand. Power balance and apportionment algorithms for the United States Congress. ACM Journal of Experimental Algorithmics, 3(1), 1998. URL http:\/\/www.jea.acm.org\/1998\/HemaspaandraPower , 16pp.","DOI":"10.1145\/297096.297106"},{"issue":"3","key":"5_CR25","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","volume":"39","author":"J. Kadin","year":"1989","unstructured":"J. Kadin. PNP[logn] and sparse Turing-complete sets for NP. Journal of Computer and System Sciences, 39(3):282\u2013298, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR26","unstructured":"J. Kemeny and L. Snell. Mathematical Models in the Social Sciences. Ginn, 1960."},{"key":"5_CR27","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and K. Wagner. The difference and truth-table hierarchies for NP. RAIRO Theoretical Informatics and Applications, 21:419\u2013435, 1987.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"issue":"2","key":"5_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103\u2013124, 1975.","journal-title":"Theoretical Computer Science"},{"key":"5_CR29","volume-title":"Research Memorandum RM-2651 (ASTIA No. AD 246277)","author":"I. Mann","year":"1960","unstructured":"I. Mann and L. Shapley. Values of large games, IV: Evaluating the electoral college by Monte Carlo techniques. Research Memorandum RM-2651 (ASTIA No. AD 246277), The Rand Corporation, Santa Monica, CA, September 1960."},{"key":"5_CR30","volume-title":"Research Memorandum RM-3158-PR","author":"I. Mann","year":"1962","unstructured":"I. Mann and L. Shapley. Values of large games, VI: Evaluating the electoral college exactly. Research Memorandum RM-3158-PR, The Rand Corporation, Santa Monica, CA, 1962."},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"I. McLean and A. Urken. Classics of Social Choice. University of Michigan Press, 1995.","DOI":"10.3998\/mpub.12736"},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1038\/scientificamerican0676-21","volume":"234","author":"R. Niemi","year":"1976","unstructured":"R. Niemi and W. Riker. The choice of voting systems. Scientific American, 234:21\u201327, 1976.","journal-title":"Scientific American"},{"key":"5_CR33","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis. On complexity as bounded rationality. In Proceedings of the 26th ACM Symposium on Theory of Computing, pages 726\u2013733. ACM Press, 1994.","DOI":"10.1145\/195058.195445"},{"key":"5_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01753703","volume":"19","author":"K. Prasad","year":"1990","unstructured":"K. Prasad and J. Kelly. NP-completeness of some problems concerning voting games. International Journal of Game Theory, 19:1\u20139, 1990.","journal-title":"International Journal of Game Theory"},{"issue":"3","key":"5_CR35","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF01303057","volume":"28","author":"K. Regan","year":"1995","unstructured":"K. Regan and J. Royer. On closure properties of bounded two-sided error complexity classes. Mathematical Systems Theory, 28(3):229\u2013244, 1995.","journal-title":"Mathematical Systems Theory"},{"key":"5_CR36","doi-asserted-by":"crossref","unstructured":"L. Shapley. Measurement of power in political systems. In W. Lucas, editor, Game Theory and its Applications, pages 69\u201381. American Mathematical Society, 1981. Proceedings of Symposia in Applied Mathematics, V. 24.","DOI":"10.1090\/psapm\/024\/637485"},{"key":"5_CR37","doi-asserted-by":"publisher","first-page":"787","DOI":"10.2307\/1951053","volume":"48","author":"L. Shapley","year":"1954","unstructured":"L. Shapley and M. Shubik. A method of evaluating the distribution of power in a committee system. American Political Science Review, 48:787\u2013792, 1954.","journal-title":"American Political Science Review"},{"key":"5_CR38","unstructured":"H. Simon. The Sciences of the Artificial. MIT Press, 1969. Second edition, 1981."},{"key":"5_CR39","doi-asserted-by":"crossref","unstructured":"M. Sipser. Borel sets and circuit complexity. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 61\u201369. ACM Press, 1983.","DOI":"10.1145\/800061.808733"},{"key":"5_CR40","doi-asserted-by":"crossref","unstructured":"P Straffin, Jr. Homogeneity, independence, and power indices. Public Choice, 30 (Summer), 1977.","DOI":"10.1007\/BF01718820"},{"key":"5_CR41","unstructured":"United States Department of Commerce et al. versus Montana et al. US Supreme Court Case 91\u2013860. Decided March 31, 1992."},{"issue":"5","key":"5_CR42","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865\u2013877, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"5_CR43","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomialtime hierarchy. SIAM Journal on Computing, 21(2):316\u2013328, 1992.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"5_CR44","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"5_CR45","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"issue":"1\u20132","key":"5_CR46","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. Wagner","year":"1987","unstructured":"K. Wagner. More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science, 51(1\u20132):53\u201380, 1987.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"5_CR47","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"K. Wagner. Bounded query classes. SIAM Journal on Computing, 19(5):833\u2013846, 1990.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"5_CR48","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0135023","volume":"35","author":"H. Young","year":"1978","unstructured":"H. Young and A. Levenglick. A consistent extension of Condorcet\u2019s election principle. SIAM Journal on Applied Mathematics, 35(2):285\u2013300, 1978.","journal-title":"SIAM Journal on Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T14:41:20Z","timestamp":1556376080000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}