{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T15:45:52Z","timestamp":1750347952149,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T00:00:00Z","timestamp":1688601600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T00:00:00Z","timestamp":1688601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RO 1202\/21-1"],"award-info":[{"award-number":["RO 1202\/21-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Weighted voting games are a well-studied class of succinct simple games that can be used to model collective decision-making in, e.g., legislative bodies such as parliaments and shareholder voting. Power indices\u00a0[1\u20134] are used to measure the influence of players in weighted voting games. In such games, it has been studied how a distinguished player\u2019s power can be changed, e.g., by merging or splitting players (the latter is a.k.a. false-name manipulation) [5, 6], by changing the quota\u00a0[7], or via structural control by adding or deleting players\u00a0[8]. We continue the work on the structural control initiated by Rey and Rothe\u00a0[8] by solving some of their open problems. In addition, we also modify their model to a more realistic setting in which the quota is indirectly changed during the addition or deletion of players (in a different sense than that of Zuckerman et al.\u00a0[7] who manipulate the quota directly without changing the set of players), and we study the corresponding problems in terms of their computational complexity.<\/jats:p>","DOI":"10.1007\/s10472-023-09874-x","type":"journal-article","created":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T14:02:29Z","timestamp":1688652149000},"page":"631-669","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Controlling weighted voting games by deleting or adding players with or without changing the quota"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6652-6433","authenticated-orcid":false,"given":"Joanna","family":"Kaczmarek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,6]]},"reference":[{"key":"9874_CR1","first-page":"317","volume":"19","author":"J Banzhaf III","year":"1965","unstructured":"Banzhaf, J., III.: Weighted voting doesn\u2019t work: A mathematical analysis. Rutgers Law Review. 19, 317\u2013343 (1965)","journal-title":"Rutgers Law Review."},{"issue":"2","key":"9874_CR2","doi-asserted-by":"publisher","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. Math. Oper. Res. 4(2), 99\u2013131 (1979)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9874_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/2981392","volume":"109","author":"L Penrose","year":"1946","unstructured":"Penrose, L.: The elementary statistics of majority voting. J. R. Stat. Soc. 109(1), 53\u201357 (1946)","journal-title":"J. R. Stat. Soc."},{"issue":"3","key":"9874_CR4","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. Am. Polit. Sci. Rev. 48(3), 787\u2013792 (1954)","journal-title":"Am. Polit. Sci. Rev."},{"key":"9874_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1613\/jair.3166","volume":"40","author":"H Aziz","year":"2011","unstructured":"Aziz, H., Bachrach, Y., Elkind, E., Paterson, M.: False-name manipulations in weighted voting games. J. Artif. Intell. Res. 40, 57\u201393 (2011)","journal-title":"J. Artif. Intell. Res."},{"key":"9874_CR6","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1613\/jair.4293","volume":"50","author":"A Rey","year":"2014","unstructured":"Rey, A., Rothe, J.: False-name manipulation in weighted voting games is hard for probabilistic polynomial time. J. Artif. Intell. Res. 50, 573\u2013601 (2014)","journal-title":"J. Artif. Intell. Res."},{"key":"9874_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2011.12.003","volume":"180\u2013181","author":"M Zuckerman","year":"2012","unstructured":"Zuckerman, M., Faliszewski, P., Bachrach, Y., Elkind, E.: Manipulating the quota in weighted voting games. Artif. Intell. 180\u2013181, 1\u201319 (2012)","journal-title":"Artif. Intell."},{"key":"9874_CR8","doi-asserted-by":"crossref","unstructured":"Rey, A., Rothe, J.: Structural control in weighted voting games. The B.E. Journal on Theoretical Economics. 18(2), 1\u201315 (2018)","DOI":"10.1515\/bejte-2016-0169"},{"key":"9874_CR9","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers, Kentfield, CA, USA (2011)","DOI":"10.1007\/978-3-031-01558-8"},{"key":"9874_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0308-8","volume-title":"Introduction to the Theory of Cooperative Games","author":"B Peleg","year":"2003","unstructured":"Peleg, B., Sudh\u00f6lter, P.: Introduction to the Theory of Cooperative Games. Kluwer Academic Publishers, Dordrecht, The Netherlands (2003)"},{"key":"9874_CR11","volume-title":"Simple Games: Desirability Relations, Trading","author":"A Taylor","year":"1999","unstructured":"Taylor, A., Zwicker, W.: Simple Games: Desirability Relations, Trading. Pseudoweightings. Princeton University Press, Princeton, NJ, USA (1999)"},{"key":"9874_CR12","doi-asserted-by":"crossref","unstructured":"Elkind, E., Rothe, J.: Cooperative game theory. In: Rothe, J. (ed.) Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer Texts in Business and Economics, pp. 135\u2013193. Springer, Heidelberg and Berlin, Germany (2015) Chap. 3","DOI":"10.1007\/978-3-662-47904-9_3"},{"issue":"2","key":"9874_CR13","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s003550100137","volume":"18","author":"D Felsenthal","year":"2001","unstructured":"Felsenthal, D., Machover, M.: The Treaty of Nice and qualified majority voting. Soc. Choice. Welf. 18(2), 431\u2013464 (2001)","journal-title":"Soc. Choice. Welf."},{"issue":"1\u20134","key":"9874_CR14","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1023\/A:1016324824094","volume":"109","author":"D Leech","year":"2002","unstructured":"Leech, D.: Voting power in the governance of the international monetary fund. Ann. Oper. Res. 109(1\u20134), 375\u2013397 (2002)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"9874_CR15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02576905","volume":"23","author":"G Arcaini","year":"1986","unstructured":"Arcaini, G., Gambarelli, G.: Algorithm for automatic computation of the power variations in share trading. Calcolo. 23(1), 13\u201319 (1986)","journal-title":"Calcolo."},{"key":"9874_CR16","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF02032761","volume":"51","author":"G Gambarelli","year":"1994","unstructured":"Gambarelli, G.: Power indices for political and financial decision making: A review. Ann. Oper. Res. 51, 163\u2013173 (1994)","journal-title":"Ann. Oper. Res."},{"volume-title":"Handbook of Computational Social Choice","year":"2016","key":"9874_CR17","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge, UK (2016)"},{"key":"9874_CR18","unstructured":"Endriss, U. (ed.): Trends in Computational Social Choice. AI Access Foundation, aiaccess.org (2017)"},{"key":"9874_CR19","doi-asserted-by":"crossref","unstructured":"Rothe, J. (ed.): Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer Texts in Business and Economics. Springer, Heidelberg and Berlin, Germany (2015)","DOI":"10.1007\/978-3-662-47904-9"},{"key":"9874_CR20","unstructured":"Baumeister, D., Rothe, J., Selker, A.: Strategic behavior in judgment aggregation. In: Endriss, U. (ed.) Trends in Computational Social Choice, pp. 145\u2013168. AI Access Foundation, aiaccess.org (2017). Chap. 8"},{"issue":"2","key":"9874_CR21","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/game.1995.1015","volume":"9","author":"K Tadenuma","year":"1995","unstructured":"Tadenuma, K., Thomson, W.: Games of fair division. Games and Economic Behavior. 9(2), 191\u2013204 (1995)","journal-title":"Games and Economic Behavior."},{"key":"9874_CR22","doi-asserted-by":"crossref","unstructured":"Br\u00e2nzei, S., Caragiannis, I., Kurokawa, D., Procaccia, A.: An algorithmic framework for strategic fair division. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence, pp. 411\u2013417. AAAI Press, Palo Alto, CA, USA (2016)","DOI":"10.1609\/aaai.v30i1.10042"},{"key":"9874_CR23","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, pp. 975\u2013982. IFAAMAS, www.ifaamas.org (2008)"},{"key":"9874_CR24","unstructured":"Aziz, H., Paterson, M.: False name manipulations in weighted voting games: Splitting, merging and annexation. In: Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, pp. 409\u2013416. IFAAMAS, www.ifaamas.org (2009)"},{"issue":"1","key":"9874_CR25","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2008.09.034","volume":"410","author":"P Faliszewski","year":"2009","unstructured":"Faliszewski, P., Hemaspaandra, L.: The complexity of power-index comparison. Theor. Comput. Sci. 410(1), 101\u2013107 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"8\/9","key":"9874_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0895-7177(92)90085-Y","volume":"16","author":"J Bartholdi III","year":"1992","unstructured":"Bartholdi, J., III., Tovey, C., Trick, M.: How hard is it to control an election? Math. Comput. Model. 16(8\/9), 27\u201340 (1992)","journal-title":"Math. Comput. Model."},{"issue":"5\u20136","key":"9874_CR27","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.artint.2007.01.005","volume":"171","author":"E Hemaspaandra","year":"2007","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Anyone but him: The complexity of precluding an alternative. Artif. Intell. 171(5\u20136), 255\u2013285 (2007)","journal-title":"Artif. Intell."},{"key":"9874_CR28","doi-asserted-by":"crossref","unstructured":"Kaczmarek, J., Rothe, J.: Controlling weighted voting games by deleting or adding players with or without changing the quota. In: Proceedings of the 33rd International Workshop on Combinatorial Algorithms, pp. 355\u2013368. Springer, Heidelberg and Berlin, Germany (2022)","DOI":"10.1007\/978-3-031-06678-8_26"},{"issue":"2","key":"9874_CR29","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C Papadimitriou","year":"1984","unstructured":"Papadimitriou, C., Yannakakis, M.: The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28(2), 244\u2013259 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9874_CR30","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L Hemachandra","year":"1989","unstructured":"Hemachandra, L.: The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39(3), 299\u2013322 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9874_CR31","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, USA (1979)"},{"key":"9874_CR32","volume-title":"Computational Complexity","author":"C Papadimitriou","year":"1995","unstructured":"Papadimitriou, C.: Computational Complexity, 2nd edn. Addison-Wesley, Reading, MA, USA (1995)","edition":"2"},{"key":"9874_CR33","volume-title":"Complexity Theory and Cryptology","author":"J Rothe","year":"2005","unstructured":"Rothe, J.: Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoretical Computer Science. Springer, Heidelberg and Berlin, Germany (2005)"},{"issue":"1\u20132","key":"9874_CR34","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K Wagner","year":"1987","unstructured":"Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51(1\u20132), 53\u201380 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"9874_CR35","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K Wagner","year":"1986","unstructured":"Wagner, K.: The complexity of combinatorial problems with succinct input representations. Acta Informatica. 23, 325\u2013356 (1986)","journal-title":"Acta Informatica."},{"issue":"4","key":"9874_CR36","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/347476.347480","volume":"47","author":"M Mundhenk","year":"2000","unstructured":"Mundhenk, M., Goldsmith, J., Lusena, C., Allender, E.: Complexity results for finite-horizon Markov decision process problems. J. ACM. 47(4), 681\u2013720 (2000)","journal-title":"J. ACM."},{"issue":"1","key":"9874_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1613\/jair.505","volume":"9","author":"M Littman","year":"1998","unstructured":"Littman, M., Goldsmith, J., Mundhenk, M.: The computational complexity of probabilistic planning. J. Artif. Intell. Res. 9(1), 1\u201336 (1998)","journal-title":"J. Artif. Intell. Res."},{"issue":"5","key":"9874_CR38","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 J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-023-09874-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-023-09874-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-023-09874-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,8]],"date-time":"2024-06-08T09:14:27Z","timestamp":1717838067000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-023-09874-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,6]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9874"],"URL":"https:\/\/doi.org\/10.1007\/s10472-023-09874-x","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2023,7,6]]},"assertion":[{"value":"28 May 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Author J\u00f6rg Rothe currently is on the following editorial boards of scientific journals:<i>Annals of Mathematics and Artificial Intelligence<\/i> (AMAI), Associate Editor, since 01\/2020,<i>Journal of Artificial Intelligence Research<\/i> (JAIR), Associate Editor, since 09\/2017, and<i>Journal of Universal Computer Science<\/i> (J.UCS), Editorial Board, since 01\/2005.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Non-financial interests"}}]}}