{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T06:20:49Z","timestamp":1778739649128,"version":"3.51.4"},"reference-count":23,"publisher":"EDP Sciences","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1051\/ro\/2011115","type":"journal-article","created":{"date-parts":[[2012,1,19]],"date-time":"2012-01-19T08:17:58Z","timestamp":1326961078000},"page":"295-314","source":"Crossref","is-referenced-by-count":13,"title":["On the complexity of problems on simple games"],"prefix":"10.1051","volume":"45","author":[{"given":"Josep","family":"Freixas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xavier","family":"Molinero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Olsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Serna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2012,1,19]]},"reference":[{"key":"R1","unstructured":"Carreras F. and Freixas J., Complete simple games.Math. Soc. Sci.32(1996) 139\u2013155."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"De\u012dneko V.G. and Woeginger G.J., On the dimension of simple monotonic games.Eur. J. Oper. Res.170(2006) 315\u2013318.","DOI":"10.1016\/j.ejor.2004.09.038"},{"key":"R3","unstructured":"Deng X. and Papadimitriou C.H., On the complexity of cooperative solution concepts.Math. Oper. Res.19(1994) 257\u2013266."},{"key":"R4","unstructured":"E. Elkind and D. Pasechnik, Computing the nucleolus of weighted voting games, inSODA \u201909 : Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. Philadelphia, PA, USA (2009) 327\u2013335."},{"key":"R5","unstructured":"E. Elkind, L.A. Goldberg, P.W. Goldberg and M. Wooldridge, Computational complexity of weighted threshold games, inProceedings of the Twenty-Second AAAI Conference on Artificial Intelligence. Vancouver, British Columbia, Canada (2007) 718\u2013723."},{"key":"R6","unstructured":"E. Elkind, L.A. Goldberg, P.W. Goldberg and M. Wooldridge, On the dimensionality of voting games, inProceedings of the Twenty-Second AAAI Conference on Artificial Intelligence. Hyatt Regency McCormick Place, Chicago (2008) 69\u201374."},{"key":"R7","unstructured":"Freixas J. and Molinero X., Simple games and weighted games : A theoretical and computational viewpoint.Discrete Appl. Math.157(2009) 1496\u20131508."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Freixas J. and Zwicker W.S., Weighted voting, abstention, and multiple levels of approval.Soc. Choice Welfare21(2003) 399\u2013431.","DOI":"10.1007\/s00355-003-0212-3"},{"key":"R9","unstructured":"M.R. Garey and D.S. Johnson,Computers and Intractability : A Guide to the Theory of NP-Completness, edited by W.H. Freeman. San Francisco, New York, USA (1979)."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Harrison G.W. and McDaniel T., Voting games and computational complexity.Oxford Econ. Papers602008 546\u2013565.","DOI":"10.1093\/oep\/gpm045"},{"key":"R11","unstructured":"Heged\u00fcs T. and Megiddo N., On the geometric separability of Boolean functions.Discrete Appl. Math.66(1996) 205\u2013218."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Karmarkar N., A new polynomial-time algorithm for linear programming.Combinatorica4(1984) 373\u2013395.","DOI":"10.1007\/BF02579150"},{"key":"R13","unstructured":"Khachiyan L.G., A polynomial algorithm for linear programming.Dokl. Akad. Nauk. SSSR244(1979) 1093\u20131096; English translationSoviet Math. Dokl.20(1979) 191\u2013194."},{"key":"R14","unstructured":"Matsui Y. and Matsui T., NP-completeness for calculating power indices of weighted majority games.Theor. Comput. Sci.263(2001) 305\u2013310."},{"key":"R15","unstructured":"Mehta D. and Raghavan V., Decision tree approximations of Boolean functions.Theor. Comput. Sci.270(2002) 609\u2013623."},{"key":"R16","unstructured":"G. Owen,Game Theory, 3th edition. Academic Press, San Diego, USA (1995)."},{"key":"R17","unstructured":"C.H. Papadimitriou,Computational Complexity. Addison Wesley (1994)."},{"key":"R18","unstructured":"Peled U.N. and Simeone B., Polynomial-time algorithms for regular set-covering and threshold synthesis.Discrete Appl. Math.12(1985) 57\u201369."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Prasad K. and Kelly J.S., NP-completeness of some problems concerning voting games.Int. J. Game Theory19(1990) 1\u20139.","DOI":"10.1007\/BF01753703"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"J. Rosenm\u00fcller, An algorithm for the construction of homogeneous games, in \u00d6konomie und Mathematik, edited by O. Opitz and B. Rauhut. Springer-Verlag (1987) 63\u201374.","DOI":"10.1007\/978-3-642-72672-9_8"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Taylor A.D. and Zwicker W.S., Simple games and magic squares.J. Comb. Theory, Ser. A71(1995) 67\u201368.","DOI":"10.1016\/0097-3165(95)90016-0"},{"key":"R22","unstructured":"A.D. Taylor and W.S. Zwicker,Simple games : desirability relations, trading, and pseudoweightings. Princeton University Press, New Jersey, USA (1999)."},{"key":"R23","unstructured":"J. Von Neumann and O. Morgenstern,Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey, USA (1944)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2011115\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,22]],"date-time":"2019-06-22T17:46:28Z","timestamp":1561225588000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2011115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":23,"journal-issue":{"issue":"4"},"alternative-id":["ro110016"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2011115","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10]]}}}