{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:24:01Z","timestamp":1772252641178,"version":"3.50.1"},"reference-count":49,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,12,26]],"date-time":"2021-12-26T00:00:00Z","timestamp":1640476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>We study the efficient computation of power indices for weighted voting games with precoalitions amongst subsets of players (reflecting, e.g., ideological proximity) using the paradigm of dynamic programming. Starting from the state-of-the-art algorithms for computing the Banzhaf and Shapley\u2013Shubik indices for weighted voting games, we present a framework for fast algorithms for the three most common power indices with precoalitions, i.e., the Owen index, the Banzhaf\u2013Owen index and the symmetric coalitional Banzhaf index, and point out why our new algorithms are applicable for large numbers of players. We discuss implementations of our algorithms for the three power indices with precoalitions in C++ and review computing times, as well as storage requirements.<\/jats:p>","DOI":"10.3390\/g13010006","type":"journal-article","created":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T01:00:54Z","timestamp":1640566854000},"page":"6","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic Programming for Computing Power Indices for Weighted Voting Games with Precoalitions"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0619-4606","authenticated-orcid":false,"given":"Jochen","family":"Staudacher","sequence":"first","affiliation":[{"name":"Fakult\u00e4t Informatik, Hochschule Kempten, 87435 Kempten, Germany"}]},{"given":"Felix","family":"Wagner","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t Informatik, Hochschule Kempten, 87435 Kempten, Germany"}]},{"given":"Jan","family":"Filipp","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t Informatik, Hochschule Kempten, 87435 Kempten, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1340004","DOI":"10.1142\/S0219198913400045","article-title":"Comparing power indices","volume":"15","author":"Bertini","year":"2013","journal-title":"Int. Game Theory Rev."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.2307\/2981392","article-title":"The elementary statistics of majority voting","volume":"109","author":"Penrose","year":"1946","journal-title":"J. R. Stat. Soc."},{"key":"ref_3","first-page":"317","article-title":"Weighted voting doesn\u2019t work: A mathematical analysis","volume":"19","author":"Banzhaf","year":"1964","journal-title":"Rutgers L. Rev."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"787","DOI":"10.2307\/1951053","article-title":"A method for evaluating the distribution of power in a committee system","volume":"48","author":"Shapley","year":"1954","journal-title":"Amer. Pol. Sci. Rev."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1752","DOI":"10.1016\/j.ejor.2005.12.002","article-title":"The distribution of power in the European Constitution","volume":"176","author":"Algaba","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.mathsocsci.2011.08.005","article-title":"Beyond Lisbon. Demographic trends and voting power in the European Union Council of Ministers","volume":"63","year":"2012","journal-title":"Math. Soc. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"K\u00f3czy, L.A. (2021). Brexit and Power in the Council of the European Union. Games, 12.","DOI":"10.3390\/g12020051"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kurz, S. (2016). Computing the power distribution in the IMF. arXiv.","DOI":"10.2139\/ssrn.2742118"},{"key":"ref_9","first-page":"179","article-title":"Microarray Data Analysis via Weighted Indices and Weighted Majority Games","volume":"Volume 6160","author":"Masulli","year":"2009","journal-title":"Computational Intelligence Methods for Bioinformatics and Biostatistics. CIBB 2009. Lecture Notes in Computer Science"},{"key":"ref_10","unstructured":"Bachrach, Y., Rosenschein, J.S., and Porat, E. (2008, January 12\u201316). Power and stability in connectivity games. Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Estoril, Portugal."},{"key":"ref_11","first-page":"116","article-title":"Some propositions of approaches for measuring indirect control power of firms and mutual connections in corporate shareholding structures","volume":"Volume 12330","author":"Nguyen","year":"2020","journal-title":"Transactions on Computational Collective Intelligence XXXV. Lecture Notes in Computer Science"},{"key":"ref_12","first-page":"97","article-title":"Measurement of control power in corporate networks","volume":"31","author":"Stach","year":"2021","journal-title":"Oper. Res. Dec."},{"key":"ref_13","first-page":"73","article-title":"Implicit power indices for measuring indirect control in corporate structures","volume":"Volume 13010","author":"Nguyen","year":"2021","journal-title":"Transactions on Computational Collective Intelligence XXXVI. Lecture Notes in Computer Science"},{"key":"ref_14","first-page":"21","article-title":"Power in Network","volume":"Volume 11890","author":"Nguyen","year":"2019","journal-title":"Transactions on Computational Collective Intelligence XXXIV. Lecture Notes in Computer Science"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s41412-021-00108-1","article-title":"Power in Networks: The Medici","volume":"38","author":"Holler","year":"2021","journal-title":"Homo Oecon."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0165-4896(97)00018-8","article-title":"Owen\u2019s coalitional value and aircraft landing fees","volume":"34","year":"1997","journal-title":"Math. Soc. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10479-005-2242-y","article-title":"Generating Functions for Coalitional Power Indices: An Application to the IMF","volume":"137","author":"Bowles","year":"2005","journal-title":"Ann. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s11238-005-0944-x","article-title":"The multilinear extension and the symmetric coalition Banzhaf value","volume":"59","author":"Carreras","year":"2005","journal-title":"Theory Decis."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Mayer, A. (2018). Luxembourg in the Early Days of the EEC: Null Player or Not?. Games, 9.","DOI":"10.3390\/g9020029"},{"key":"ref_20","unstructured":"Owen, G. (1995). Game Theory, Academic Press. [3rd ed.]."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/978-3-642-45494-3_7","article-title":"Values of Games with a Priori Unions","volume":"Volume 141","author":"Henn","year":"1977","journal-title":"Mathematical Economics and Game Theory. Lecture Notes in Economics and Mathematical Systems"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-1-4020-2936-3_10","article-title":"\u201cCounting\u201d Power Indices for Games with a Priori Unions","volume":"Volume 36","author":"Gambarelli","year":"2004","journal-title":"Essays in Cooperative Games. Theory and Decision Library"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s11238-008-9114-2","article-title":"Monotonicity of power in games with a priori unions","volume":"66","author":"Bowles","year":"2009","journal-title":"Theory Decis."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1023\/A:1016356303622","article-title":"Modification of the Banzhaf value for games with a coalition structure","volume":"109","year":"2002","journal-title":"Ann. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Holler, M.J. (1981). Modification of the Banzhaf-Coleman Index for Games with a Priori Unions. Power, Voting, and Voting Power, Physica.","DOI":"10.1007\/978-3-662-00411-1"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0304-3975(00)00251-6","article-title":"NP-completeness for calculating power indices of weighted majority games","volume":"263","author":"Matsui","year":"2001","journal-title":"Theor. Comp. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0165-4896(02)00086-0","article-title":"Computing power indices in weighted multiple majority games","volume":"46","author":"Algaba","year":"2003","journal-title":"Math. Soc. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02628555","article-title":"Generating functions for computing power indices efficiently","volume":"8","author":"Bilbao","year":"2000","journal-title":"TOP"},{"key":"ref_29","first-page":"58","article-title":"Power in weighted voting games","volume":"7","author":"Tanenbaum","year":"1997","journal-title":"Math. J."},{"key":"ref_30","first-page":"71","article-title":"A survey of algorithms for calculating power indices of weighted majority games","volume":"43","author":"Matsui","year":"2000","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"ref_31","first-page":"679","article-title":"Efficient Computation of Power Indices for Weighted Majority Games","volume":"Volume 7676","author":"Chao","year":"2020","journal-title":"International Symposium on Algorithms and Computation. ISAAC 2012. Lecture Notes in Computer Science"},{"key":"ref_32","first-page":"123","article-title":"Computing power indices for weighted voting games via dynamic programming","volume":"31","author":"Staudacher","year":"2021","journal-title":"Oper. Res. Dec."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1068\/a100907","article-title":"On the measurement of power. Some reactions to Laver","volume":"10","author":"Johnston","year":"1978","journal-title":"Environ. Plan. A"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01753239","article-title":"A new index of power for simple n-person games","volume":"7","author":"Deegan","year":"1978","journal-title":"Int. J. Game Theory"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1111\/j.1467-9248.1982.tb00537.x","article-title":"Forming coalitions and measuring voting power","volume":"30","author":"Holler","year":"1982","journal-title":"Pol. Stud."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s41412-016-0031-2","article-title":"A well-behaved index of a priori p-power for simple n-person games","volume":"33","author":"Felsenthal","year":"2016","journal-title":"Homo Oecon."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Molinero, X., and Blasco, J. (2020, January 22\u201324). Coalitional power indices applied to voting systems. Proceedings of the 9th International Conference on Operations Research and Enterprise Systems, Valletta, Malta.","DOI":"10.5220\/0009166803720376"},{"key":"ref_38","first-page":"87","article-title":"The effect of Brexit on the balance of power in the European Union Council: An approach based on pre-coalitions","volume":"Volume 10480","author":"Nguyen","year":"2017","journal-title":"Transactions on Computational Collective Intelligence XXVII. Lecture Notes in Computer Science"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Chakravarty, S.R., Mitra, M., and Sarkar, P. (2015). A Course on Cooperative Game Theory, Cambridge University Press.","DOI":"10.1017\/CBO9781107415997"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.mathsocsci.2015.04.008","article-title":"Forms of representation for simple games: Sizes, conversions and equivalences","volume":"76","author":"Molinero","year":"2015","journal-title":"Math. Soc. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s11238-004-5639-1","article-title":"On the meaning of Owen\u2013Banzhaf coalitional value in voting situations","volume":"56","author":"Laruelle","year":"2004","journal-title":"Theory Decis."},{"key":"ref_42","unstructured":"(2021, November 17). The GNU Multiple Precision Arithmetic Library. Available online: https:\/\/gmplib.org\/."},{"key":"ref_43","first-page":"839","article-title":"Two variations of the Public Good Index for games with a priori unions","volume":"39","author":"Holler","year":"2010","journal-title":"Control. Cybern."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s11135-009-9306-z","article-title":"The Deegan-Packel index for simple games with a priori unions","volume":"45","author":"Holler","year":"2011","journal-title":"Qual. Quant."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ejor.2010.09.006","article-title":"A relation-algebraic approach to simple games","volume":"210","author":"Berghammer","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/j.ejor.2012.04.015","article-title":"On the use of binary decision diagrams for solving problems on simple games","volume":"222","author":"Berghammer","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.ejor.2010.09.020","article-title":"Power indices of simple games and vector-weighted majority games by means of binary decision diagrams","volume":"210","author":"Bolus","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_48","unstructured":"Bolus, S. (2012). A QOBDD-Based Approach to Simple Games. [Ph.D. Thesis, Christian-Albrechts Universit\u00e4t Kiel]."},{"key":"ref_49","unstructured":"Staudacher, J., and Anwander, J. (2021, November 17). Using the R Package CoopGame for the Analysis, Solution and Visualization of Cooperative Games with Transferable Utility. R Vignette for Package Version 0.2.2, Available online: https:\/\/cran.r-project.org\/package=CoopGame."}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/13\/1\/6\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:53:38Z","timestamp":1760169218000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/13\/1\/6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,26]]},"references-count":49,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["g13010006"],"URL":"https:\/\/doi.org\/10.3390\/g13010006","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202111.0462.v1","asserted-by":"object"}]},"ISSN":["2073-4336"],"issn-type":[{"value":"2073-4336","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,26]]}}}