IDEAS home Printed from https://ideas.repec.org/a/gam/jgames/v13y2021i1p6-d711371.html
   My bibliography  Save this article

Dynamic Programming for Computing Power Indices for Weighted Voting Games with Precoalitions

Author

Listed:
  • Jochen Staudacher

    (Fakultät Informatik, Hochschule Kempten, 87435 Kempten, Germany)

  • Felix Wagner

    (Fakultät Informatik, Hochschule Kempten, 87435 Kempten, Germany)

  • Jan Filipp

    (Fakultät Informatik, Hochschule Kempten, 87435 Kempten, Germany)

Abstract

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–Shubik 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–Owen 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.

Suggested Citation

  • Jochen Staudacher & Felix Wagner & Jan Filipp, 2021. "Dynamic Programming for Computing Power Indices for Weighted Voting Games with Precoalitions," Games, MDPI, vol. 13(1), pages 1-17, December.
    • Handle: RePEc:gam:jgames:v:13:y:2021:i:1:p:6-:d:711371
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2073-4336/13/1/6/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2073-4336/13/1/6/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Algaba, E. & Bilbao, J.M. & Fernandez, J.R., 2007. "The distribution of power in the European Constitution," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1752-1766, February.
    2. Kóczy, László Á., 2012. "Beyond Lisbon: Demographic trends and voting power in the European Union Council of Ministers," Mathematical Social Sciences, Elsevier, vol. 63(2), pages 152-158.
    3. László Á. Kóczy, 2021. "Brexit and Power in the Council of the European Union," Games, MDPI, vol. 12(2), pages 1-10, June.
    4. Cesarino Bertini & Josep Freixas & Gianfranco Gambarelli & Izabella Stach, 2013. "Comparing Power Indices," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 15(02), pages 1-19.
    5. Shapley, L. S. & Shubik, Martin, 1954. "A Method for Evaluating the Distribution of Power in a Committee System," American Political Science Review, Cambridge University Press, vol. 48(3), pages 787-792, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Somdeb Lahiri, 2021. "Pattanaik's axioms and the existence of winners preferred with probability at least half," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 109-122.
    2. D'ora Gr'eta Petr'oczy & L'aszl'o Csat'o, 2023. "Voting power in the Council of the European Union: A comprehensive sensitivity analysis," Papers 2312.16878, arXiv.org, revised Sep 2024.
    3. repec:has:discpr:1611 is not listed on IDEAS
    4. Le Breton, Michel & Montero, Maria & Zaporozhets, Vera, 2012. "Voting power in the EU council of ministers and fair decision making in distributive politics," Mathematical Social Sciences, Elsevier, vol. 63(2), pages 159-173.
    5. László Á. Kóczy & Balázs Sziklai, 2013. "Electing the Pope," Working Paper Series 1301, Óbuda University, Keleti Faculty of Business and Management.
    6. Fabien Lange & László Kóczy, 2013. "Power indices expressed in terms of minimal winning coalitions," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(2), pages 281-292, July.
    7. Biró, Péter & Kóczy, László Á. & Sziklai, Balázs, 2015. "Fair apportionment in the view of the Venice Commission’s recommendation," Mathematical Social Sciences, Elsevier, vol. 77(C), pages 32-41.
    8. Michela Chessa, 2014. "A generating functions approach for computing the Public Good index efficiently," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 658-673, July.
    9. D'ora Gr'eta Petr'oczy & Mark Francis Rogers & L'aszl'o 'A. K'oczy, 2018. "Brexit: The Belated Threat," Papers 1808.05142, arXiv.org.
    10. Sylvain Béal & Marc Deschamps & Mostapha Diss & Issofa Moyouwou, 2022. "Inconsistent weighting in weighted voting games," Public Choice, Springer, vol. 191(1), pages 75-103, April.
    11. Antonakakis, Nikolaos & Badinger, Harald & Reuter, Wolf Heinrich, 2014. "From Rome to Lisbon and Beyond: Member States' Power, Efficiency, and Proportionality in the EU Council of Ministers," Department of Economics Working Paper Series 175, WU Vienna University of Economics and Business.
    12. László Á. Kóczy, 2018. "Partition Function Form Games," Theory and Decision Library C, Springer, number 978-3-319-69841-0, September.
    13. Izabella Stach, 2022. "Reformulation of Public Help Index θ Using Null Player Free Winning Coalitions," Group Decision and Negotiation, Springer, vol. 31(2), pages 317-334, April.
    14. László Á. Kóczy, 2021. "Brexit and Power in the Council of the European Union," Games, MDPI, vol. 12(2), pages 1-10, June.
    15. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2010. "Applying relation algebra and RelView to measures in a social network," European Journal of Operational Research, Elsevier, vol. 202(1), pages 182-195, April.
    16. László Á. Kóczy, 2016. "Power Indices When Players can Commit to Reject Coalitions," Homo Oeconomicus: Journal of Behavioral and Institutional Economics, Springer, vol. 33(1), pages 77-91, August.
    17. Bhattacherjee, Sanjay & Chakravarty, Satya R. & Sarkar, Palash, 2022. "A General Model for Multi-Parameter Weighted Voting Games," MPRA Paper 115407, University Library of Munich, Germany.
    18. Alonso-Meijide, J.M. & Bilbao, J.M. & Casas-Méndez, B. & Fernández, J.R., 2009. "Weighted multiple majority games with unions: Generating functions and applications to the European Union," European Journal of Operational Research, Elsevier, vol. 198(2), pages 530-544, October.
    19. Karos, Dominik & Peters, Hans, 2018. "Effectivity and power," Games and Economic Behavior, Elsevier, vol. 108(C), pages 363-378.
    20. Diego Varela & Javier Prado-Dominguez, 2012. "Negotiating the Lisbon Treaty: Redistribution, Efficiency and Power Indices," Czech Economic Review, Charles University Prague, Faculty of Social Sciences, Institute of Economic Studies, vol. 6(2), pages 107-124, July.
    21. Qianqian Kong & Hans Peters, 2021. "An issue based power index," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(1), pages 23-38, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jgames:v:13:y:2021:i:1:p:6-:d:711371. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.