{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:05:37Z","timestamp":1767236737038},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s10472-009-9162-5","type":"journal-article","created":{"date-parts":[[2009,10,19]],"date-time":"2009-10-19T06:54:04Z","timestamp":1255935244000},"page":"109-131","source":"Crossref","is-referenced-by-count":35,"title":["On the computational complexity of weighted voting games"],"prefix":"10.1007","volume":"56","author":[{"given":"Edith","family":"Elkind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Wooldridge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,10,20]]},"reference":[{"key":"9162_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)"},{"key":"9162_CR2","first-page":"317","volume":"19","author":"JF Banzhaf","year":"1965","unstructured":"Banzhaf, J.F.: Weighted voting doesn\u2019t work: a mathematical analysis. Rutgers Law Rev. 19, 317\u2013343 (1965)","journal-title":"Rutgers Law Rev."},{"key":"9162_CR3","unstructured":"Bilbao, J., Fern\u00e1ndez, J., L\u00f3pez, J.: Complexity in cooperative game theory (manuscript)"},{"key":"9162_CR4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0377-2217(01)00334-4","volume":"143","author":"JM Bilbao","year":"2002","unstructured":"Bilbao, J.M., Fern\u00e1ndez, J.R., Jimin\u00e9z, N., L\u00f3pez, J.J.: Voting power in the European union enlargement. Eur. J. Oper. Res. 143, 181\u2013196 (2002)","journal-title":"Eur. J. Oper. Res."},{"key":"9162_CR5","unstructured":"Conitzer, V., Sandholm, T.: Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In: Proceedings of the Ninteenth National Conference on Artificial Intelligence (AAAI-2004), pp. 219\u2013225, San Jose, CA (2004)"},{"key":"9162_CR6","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/j.artint.2006.01.005","volume":"170","author":"V Conitzer","year":"2006","unstructured":"Conitzer, V., Sandholm, T.: Complexity of constructing solutions in the core based on synergies among coalitions. Artif. Intell. 170, 607\u2013619 (2006)","journal-title":"Artif. Intell."},{"key":"9162_CR7","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/1109557.1109572","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"X Deng","year":"2006","unstructured":"Deng, X., Fang, Q., Sun, X.: Finding nucleolus of flow game. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0124\u2013131. ACM, New York (2006)"},{"issue":"2","key":"9162_CR8","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.19.2.257","volume":"19","author":"X Deng","year":"1994","unstructured":"Deng, X., Papadimitriou, C.H.: On the complexity of cooperative solution concepts. Math. Oper. Res. 19(2), 257\u2013266 (1994)","journal-title":"Math. Oper. Res."},{"key":"9162_CR9","unstructured":"Elkind, E., Chalkiadakis, G., Jennings, N.R.: Coalition structures in weighted voting games. In: Proc. 18th European Conference on Artificial Intelligence (ECAI\u201908) (2008)"},{"key":"9162_CR10","unstructured":"Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M.: Computational complexity of weighted threshold games. In: Proc. 22nd Conference on Artificial Intelligence (AAAI\u201907) (2007)"},{"key":"9162_CR11","unstructured":"Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M.: On the dimensionality of voting games. In: Proc. 23rd Conference on Artificial Intelligence (AAAI\u201908) (2008)"},{"key":"9162_CR12","doi-asserted-by":"crossref","unstructured":"Elkind, E., Pasechnik, D.: Computing the nucleolus of weighted voting games. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909) (2009)","DOI":"10.1137\/1.9781611973068.37"},{"key":"9162_CR13","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1990)"},{"key":"9162_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, 2nd edn. Springer, Berlin (1993)","edition":"2"},{"key":"9162_CR15","doi-asserted-by":"crossref","unstructured":"Ieong, S., Shoham, Y.: Marginal contribution nets: a compact representation scheme for coalitional games. In: Proceedings of the Sixth ACM Conference on Electronic Commerce (EC\u201905), Vancouver, Canada (2005)","DOI":"10.1145\/1064009.1064030"},{"issue":"1","key":"9162_CR16","doi-asserted-by":"crossref","first-page":"71","DOI":"10.15807\/jorsj.43.71","volume":"43","author":"T Matsui","year":"2000","unstructured":"Matsui, T., Matsui, Y.: A survey of algorithms for calculating power indices of weighted majority games. J. Oper. Res. Soc. Jpn 43(1), 71\u201386 (2000)","journal-title":"J. Oper. Res. Soc. Jpn"},{"issue":"1\u20132","key":"9162_CR17","doi-asserted-by":"crossref","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. Theor. Comp. Sci. 263(1\u20132), 305\u2013310 (2001)","journal-title":"Theor. Comp. Sci."},{"key":"9162_CR18","volume-title":"A Course in Game Theory","author":"MJ Osborne","year":"1994","unstructured":"Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT, Cambridge (1994)"},{"key":"9162_CR19","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9162_CR20","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1137\/0116042","volume":"16","author":"B Peleg","year":"1968","unstructured":"Peleg, B.: On weights of constant-sum majority games. SIAM J. Appl. Math. 16, 527\u2013532 (1968)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"9162_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01753703","volume":"19","author":"K Prasad","year":"1990","unstructured":"Prasad, K., Kelly, J.S.: NP-completeness of some problems concerning voting games. Int. J. Game Theory 19(1), 1\u20139 (1990)","journal-title":"Int. J. Game Theory"},{"issue":"1\u20132","key":"9162_CR22","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0004-3702(99)00036-3","volume":"111","author":"T Sandholm","year":"1999","unstructured":"Sandholm, T., Larson, K., Andersson, M., Shehory, O., Tohm\u00e9, F.: Coalition structure generation with worst case guarantees. Artif. Intell. 111(1\u20132), 209\u2013238 (1999)","journal-title":"Artif. Intell."},{"key":"9162_CR23","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1137\/0117107","volume":"17","author":"D Schmeidler","year":"1969","unstructured":"Schmeidler, D.: The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17, 1163\u20131170 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"9162_CR24","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York (2003)"},{"key":"9162_CR25","series-title":"LNAI","first-page":"56","volume-title":"From Reaction to Cognition\u2014Fifth European Workshop on Modelling Autonomous Agents in a Multi-Agent World, MAAMAW-93","author":"O Shehory","year":"1995","unstructured":"Shehory, O., Kraus, S.: Coalition formation among autonomous agents: strategies and complexity. In: Castelfranchim, C., M\u00fcller, J.-P. (eds.) From Reaction to Cognition\u2014Fifth European Workshop on Modelling Autonomous Agents in a Multi-Agent World, MAAMAW-93. LNAI, vol. 957, pp. 56\u201372. Springer, Berlin (1995)"},{"key":"9162_CR26","unstructured":"Shehory, O., Kraus, S.: Task allocation via coalition formation among autonomous agents. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), pp.\u00a0655\u2013661, Montr\u00e9al, Qu\u00e9bec, Canada (1995)"},{"issue":"1\u20132","key":"9162_CR27","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0004-3702(98)00045-9","volume":"101","author":"O Shehory","year":"1998","unstructured":"Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 101(1\u20132), 165\u2013200 (1998)","journal-title":"Artif. Intell."},{"key":"9162_CR28","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/game.1993.1009","volume":"5","author":"A Taylor","year":"1993","unstructured":"Taylor, A., Zwicker, W.: Weighted voting, multicameral representation, and power. Games Econom. Behav. 5, 170\u2013181 (1993)","journal-title":"Games Econom. Behav."},{"key":"9162_CR29","volume-title":"Simple Games: Desirability Relations, Trading, Pseudoweightings","author":"AD Taylor","year":"1999","unstructured":"Taylor, A.D., Zwicker, W.S.: Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton University Press, Princeton (1999)"},{"issue":"4","key":"9162_CR30","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF01761605","volume":"5","author":"LA Wolsey","year":"1976","unstructured":"Wolsey, L.A.: The nucleolus and kernel for simple games or special valid inequalities for 0\u2009\u2212\u20091 linear integer programs. Int. J. Game Theory 5(4), 227\u2013238 (1976)","journal-title":"Int. J. Game Theory"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-009-9162-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-009-9162-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-009-9162-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:58:13Z","timestamp":1559152693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-009-9162-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["9162"],"URL":"https:\/\/doi.org\/10.1007\/s10472-009-9162-5","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}