Abstract
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 [1,2,3,4] are used to measure the influence of players in weighted voting games. In such games, it has been studied how a distinguished player’s 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 [7], or via structural control by adding or deleting players [8]. We continue the work on the structural control initiated by Rey and Rothe [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. [7] who manipulate the quota directly without changing the set of players), and we study the corresponding problems in terms of their computational complexity.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Data Availability
Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
References
Banzhaf, J., III.: Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review. 19, 317–343 (1965)
Dubey, P., Shapley, L.: Mathematical properties of the Banzhaf power index. Math. Oper. Res. 4(2), 99–131 (1979)
Penrose, L.: The elementary statistics of majority voting. J. R. Stat. Soc. 109(1), 53–57 (1946)
Shapley, L., Shubik, M.: A method of evaluating the distribution of power in a committee system. Am. Polit. Sci. Rev. 48(3), 787–792 (1954)
Aziz, H., Bachrach, Y., Elkind, E., Paterson, M.: False-name manipulations in weighted voting games. J. Artif. Intell. Res. 40, 57–93 (2011)
Rey, A., Rothe, J.: False-name manipulation in weighted voting games is hard for probabilistic polynomial time. J. Artif. Intell. Res. 50, 573–601 (2014)
Zuckerman, M., Faliszewski, P., Bachrach, Y., Elkind, E.: Manipulating the quota in weighted voting games. Artif. Intell. 180–181, 1–19 (2012)
Rey, A., Rothe, J.: Structural control in weighted voting games. The B.E. Journal on Theoretical Economics. 18(2), 1–15 (2018)
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)
Peleg, B., Sudhölter, P.: Introduction to the Theory of Cooperative Games. Kluwer Academic Publishers, Dordrecht, The Netherlands (2003)
Taylor, A., Zwicker, W.: Simple Games: Desirability Relations, Trading. Pseudoweightings. Princeton University Press, Princeton, NJ, USA (1999)
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–193. Springer, Heidelberg and Berlin, Germany (2015) Chap. 3
Felsenthal, D., Machover, M.: The Treaty of Nice and qualified majority voting. Soc. Choice. Welf. 18(2), 431–464 (2001)
Leech, D.: Voting power in the governance of the international monetary fund. Ann. Oper. Res. 109(1–4), 375–397 (2002)
Arcaini, G., Gambarelli, G.: Algorithm for automatic computation of the power variations in share trading. Calcolo. 23(1), 13–19 (1986)
Gambarelli, G.: Power indices for political and financial decision making: A review. Ann. Oper. Res. 51, 163–173 (1994)
Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge, UK (2016)
Endriss, U. (ed.): Trends in Computational Social Choice. AI Access Foundation, aiaccess.org (2017)
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)
Baumeister, D., Rothe, J., Selker, A.: Strategic behavior in judgment aggregation. In: Endriss, U. (ed.) Trends in Computational Social Choice, pp. 145–168. AI Access Foundation, aiaccess.org (2017). Chap. 8
Tadenuma, K., Thomson, W.: Games of fair division. Games and Economic Behavior. 9(2), 191–204 (1995)
Brânzei, 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–417. AAAI Press, Palo Alto, CA, USA (2016)
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–982. IFAAMAS, www.ifaamas.org (2008)
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–416. IFAAMAS, www.ifaamas.org (2009)
Faliszewski, P., Hemaspaandra, L.: The complexity of power-index comparison. Theor. Comput. Sci. 410(1), 101–107 (2009)
Bartholdi, J., III., Tovey, C., Trick, M.: How hard is it to control an election? Math. Comput. Model. 16(8/9), 27–40 (1992)
Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Anyone but him: The complexity of precluding an alternative. Artif. Intell. 171(5–6), 255–285 (2007)
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–368. Springer, Heidelberg and Berlin, Germany (2022)
Papadimitriou, C., Yannakakis, M.: The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28(2), 244–259 (1984)
Hemachandra, L.: The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39(3), 299–322 (1989)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, USA (1979)
Papadimitriou, C.: Computational Complexity, 2nd edn. Addison-Wesley, Reading, MA, USA (1995)
Rothe, J.: Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoretical Computer Science. Springer, Heidelberg and Berlin, Germany (2005)
Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51(1–2), 53–80 (1987)
Wagner, K.: The complexity of combinatorial problems with succinct input representations. Acta Informatica. 23, 325–356 (1986)
Mundhenk, M., Goldsmith, J., Lusena, C., Allender, E.: Complexity results for finite-horizon Markov decision process problems. J. ACM. 47(4), 681–720 (2000)
Littman, M., Goldsmith, J., Mundhenk, M.: The computational complexity of probabilistic planning. J. Artif. Intell. Res. 9(1), 1–36 (1998)
Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865–877 (1991)
Acknowledgements
We thank the AMAI and the IWOCA’22 reviewers for helpful comments.
Funding
This work was supported in part by Deutsche Forschungsgemeinschaft under grants RO 1202/14-2 and RO 1202/21-1. Open Access funding enabled and organized by Projekt DEAL.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Non-financial interests
Author Jörg Rothe currently is on the following editorial boards of scientific journals:\(\bullet \) Annals of Mathematics and Artificial Intelligence (AMAI), Associate Editor, since 01/2020,\(\bullet \) Journal of Artificial Intelligence Research (JAIR), Associate Editor, since 09/2017, and\(\bullet \) Journal of Universal Computer Science (J.UCS), Editorial Board, since 01/2005.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Kaczmarek, J., Rothe, J. Controlling weighted voting games by deleting or adding players with or without changing the quota. Ann Math Artif Intell 92, 631–669 (2024). https://doi.org/10.1007/s10472-023-09874-x
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-023-09874-x