{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:59:50Z","timestamp":1725515990843},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540688655"},{"type":"electronic","value":"9783540688808"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68880-8_18","type":"book-chapter","created":{"date-parts":[[2008,7,31]],"date-time":"2008-07-31T06:37:59Z","timestamp":1217486279000},"page":"177-187","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Power-Index Comparison"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Faliszewski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Bachrach, Y., Elkind, E.: Divide and conquer: False-name manipulations in weighted voting games. In: Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, May 2008 (to appear, 2008)"},{"issue":"3","key":"18_CR2","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1145\/5925.5937","volume":"33","author":"J. Balc\u00e1zar","year":"1986","unstructured":"Balc\u00e1zar, J., Book, R., Sch\u00f6ning, U.: The polynomial-time hierarchy and sparse oracles. Journal of the ACM\u00a033(3), 603\u2013617 (1986)","journal-title":"Journal of the ACM"},{"key":"18_CR3","first-page":"317","volume":"19","author":"J. Banzhaf","year":"1965","unstructured":"Banzhaf, J.: Weighted voting doesn\u2019t work: A mathematical analysis. Rutgers Law Review\u00a019, 317\u2013343 (1965)","journal-title":"Rutgers Law Review"},{"key":"18_CR4","volume-title":"Introduction to the Theory of Complexity","author":"D. Bovet","year":"1993","unstructured":"Bovet, D., Crescenzi, P.: Introduction to the Theory of Complexity. Prentice-Hall, Englewood Cliffs (1993)"},{"issue":"2","key":"18_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.19.2.257","volume":"19","author":"X. Deng","year":"1994","unstructured":"Deng, X., Papadimitriou, C.: On the complexity of comparative solution concepts. Mathematics of Operations Research\u00a019(2), 257\u2013266 (1994)","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"18_CR6","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1287\/moor.4.2.99","volume":"4","author":"P. Dubey","year":"1979","unstructured":"Dubey, P., Shapley, L.: Mathematical properties of the Banzhaf power index. Mathematics of Operations Research\u00a04(2), 99\u2013131 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"18_CR7","first-page":"613","volume-title":"Proceedings of the 10th International World Wide Web Conference","author":"C. Dwork","year":"2001","unstructured":"Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International World Wide Web Conference, pp. 613\u2013622. ACM Press, New York (2001)"},{"key":"18_CR8","unstructured":"Faliszewski, P., Hemaspaandra, L.: The complexity of power-index comparison. Technical Report TR-929, Department of Computer Science, University of Rochester, Rochester, NY (January 2008)"},{"issue":"4","key":"18_CR9","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM Journal on Computing\u00a06(4), 675\u2013695 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L., Rajasethupathy, K., Sethupathy, P., Zimand, M.: Power balance and apportionment algorithms for the United States Congress. ACM Journal of Experimental Algorithmics\u00a03(1) (1998), \n                  \n                    http:\/\/www.jea.acm.org\/1998\/HemaspaandraPower","DOI":"10.1145\/297096.297106"},{"issue":"4","key":"18_CR11","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"H. Hunt","year":"1998","unstructured":"Hunt, H., Marathe, M., Radhakrishnan, V., Stearns, R.: The complexity of planar counting problems. SIAM Journal on Computing\u00a027(4), 1142\u20131167 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"18_CR12","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"Krentel, M.: The complexity of optimization problems. Journal of Computer and System Sciences\u00a036(3), 490\u2013509 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\u20132","key":"18_CR13","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0304-3975(00)00251-6","volume":"263","author":"Y. Matsui","year":"2001","unstructured":"Matsui, Y., Matsui, T.: NP-completeness for calculating power indices of weighted majority games. Theoretical Computer Science\u00a0263(1\u20132), 305\u2013310 (2001)","journal-title":"Theoretical Computer Science"},{"key":"18_CR14","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01753703","volume":"19","author":"K. Prasad","year":"1990","unstructured":"Prasad, K., Kelly, J.: NP-completeness of some problems concerning voting games. International Journal of Game Theory\u00a019(1), 1\u20139 (1990)","journal-title":"International Journal of Game Theory"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"787","DOI":"10.2307\/1951053","volume":"48","author":"L. Shapley","year":"1954","unstructured":"Shapley, L., Shubik, M.: A method of evaluating the distribution of power in a committee system. American Political Science Review\u00a048, 787\u2013792 (1954)","journal-title":"American Political Science Review"},{"key":"18_CR17","unstructured":"Simon, J.: On Some Central Problems in Computational Complexity. PhD thesis, Cornell University, Ithaca, N.Y, Available as Cornell Department of Computer Science Technical Report TR75-224 (January 1975)"},{"issue":"5","key":"18_CR18","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing\u00a020(5), 865\u2013877 (1991)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"18_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"18_CR20","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1142\/S0129054191000066","volume":"2","author":"V. Zank\u00f3","year":"1991","unstructured":"Zank\u00f3, V.: #P-completeness via many-one reductions. International Journal of Foundations of Computer Science\u00a02(1), 76\u201382 (1991)","journal-title":"International Journal of Foundations of Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68880-8_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:17:01Z","timestamp":1620015421000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68880-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540688655","9783540688808"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68880-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}