IDEAS home Printed from https://ideas.repec.org/a/eee/matsoc/v115y2022icp47-51.html
   My bibliography  Save this article

Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games

Author

Listed:
  • Tanaka, Masato
  • Matsui, Tomomi

Abstract

In this paper, we propose a pseudo polynomial size LP formulation for finding a payoff vector in the least core of a weighted voting game. The numbers of variables and constraints in our formulation are both bounded by O(nW+), where n is the number of players and W+ is the total sum of (integer) voting weights. When we employ our formulation, a commercial LP solver calculates a payoff vector in the least core of practical weighted voting games in a few seconds. We also extend our approach to vector weighted voting games.

Suggested Citation

  • Tanaka, Masato & Matsui, Tomomi, 2022. "Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games," Mathematical Social Sciences, Elsevier, vol. 115(C), pages 47-51.
    • Handle: RePEc:eee:matsoc:v:115:y:2022:i:c:p:47-51
    DOI: 10.1016/j.mathsocsci.2021.12.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0165489621001190
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.mathsocsci.2021.12.002?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Moshé Machover & Dan S. Felsenthal, 2001. "The Treaty of Nice and qualified majority voting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(3), pages 431-464.
    2. Bilbao, J. M. & Fernandez, J. R. & Jimenez, N. & Lopez, J. J., 2002. "Voting power in the European Union enlargement," European Journal of Operational Research, Elsevier, vol. 143(1), pages 181-196, November.
    3. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. 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.
    5. Sascha Kurz, 2012. "On minimum sum representations for weighted voting games," Annals of Operations Research, Springer, vol. 196(1), pages 361-369, July.
    6. Prasad, K & Kelly, J S, 1990. "NP-Completeness of Some Problems Concerning Voting Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(1), pages 1-9.
    7. Xiaotie Deng & Christos H. Papadimitriou, 1994. "On the Complexity of Cooperative Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 257-266, May.
    8. Paola Cappanera & Maria Paola Scaparra, 2011. "Optimal Allocation of Protective Resources in Shortest-Path Networks," Transportation Science, INFORMS, vol. 45(1), pages 64-80, February.
    9. Robert G. Bland & Donald Goldfarb & Michael J. Todd, 1981. "Feature Article—The Ellipsoid Method: A Survey," Operations Research, INFORMS, vol. 29(6), pages 1039-1091, December.
    10. Kurz, Sascha & Napel, Stefan & Nohn, Andreas, 2014. "The nucleolus of large majority games," Economics Letters, Elsevier, vol. 123(2), pages 139-143.
    11. Josep Freixas & Xavier Molinero, 2009. "On the existence of a minimum integer representation for weighted voting systems," Annals of Operations Research, Springer, vol. 166(1), pages 243-260, February.
    12. M. Maschler & B. Peleg & L. S. Shapley, 1979. "Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 303-338, November.
    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. 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.
    2. Michel Le Breton & Karine Van Der Straeten, 2017. "Alliances Électorales et Gouvernementales : La Contribution de la Théorie des Jeux Coopératifs à la Science Politique," Revue d'économie politique, Dalloz, vol. 127(4), pages 637-736.
    3. Yuto Ushioda & Masato Tanaka & Tomomi Matsui, 2022. "Monte Carlo Methods for the Shapley–Shubik Power Index," Games, MDPI, vol. 13(3), pages 1-14, June.
    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. Meinhardt, Holger Ingmar, 2021. "Disentangle the Florentine Families Network by the Pre-Kernel," MPRA Paper 106482, University Library of Munich, Germany.
    6. Benati, Stefano & Rizzi, Romeo & Tovey, Craig, 2015. "The complexity of power indexes with graph restricted coalitions," Mathematical Social Sciences, Elsevier, vol. 76(C), pages 53-63.
    7. Le Breton, Michel & Lepelley, Dominique & Macé, Antonin & Merlin, Vincent, 2017. "Le mécanisme optimal de vote au sein du conseil des représentants d’un système fédéral," L'Actualité Economique, Société Canadienne de Science Economique, vol. 93(1-2), pages 203-248, Mars-Juin.
    8. 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.
    9. 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.
    10. Monisankar Bishnu & Sonali Roy, 2012. "Hierarchy of players in swap robust voting games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(1), pages 11-22, January.
    11. Zaporozhets, Vera & García-Valiñas, María & Kurz, Sascha, 2016. "Key drivers of EU budget allocation: Does power matter?," European Journal of Political Economy, Elsevier, vol. 43(C), pages 57-70.
    12. Martí Jané Ballarín, 2023. "The complexity of power indices in voting games with incompatible players," UB School of Economics Working Papers 2023/441, University of Barcelona School of Economics.
    13. Stefano Benati & Giuseppe Vittucci Marzetti, 2021. "Voting power on a graph connected political space with an application to decision-making in the Council of the European Union," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(4), pages 733-761, November.
    14. Maria Montero & Martin Sefton & Ping Zhang, 2008. "Enlargement and the balance of power: an experimental study," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 30(1), pages 69-87, January.
    15. Roberto Roson & Franz Hubert, 2015. "Bargaining Power and Value Sharing in Distribution Networks: A Cooperative Game Theory Approach," Networks and Spatial Economics, Springer, vol. 15(1), pages 71-87, March.
    16. Sascha Kurz, 2020. "A note on limit results for the Penrose–Banzhaf index," Theory and Decision, Springer, vol. 88(2), pages 191-203, March.
    17. Julio González-Díaz & Estela Sánchez-Rodríguez, 2014. "Understanding the coincidence of allocation rules: symmetry and orthogonality in TU-games," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 821-843, November.
    18. Kar, Anirban & Mitra, Manipushpak & Mutuswami, Suresh, 2009. "On the coincidence of the prenucleolus and the Shapley value," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 16-25, January.
    19. Montero, Maria, 2017. "Proportional Payoffs in Legislative Bargaining with Weighted Voting: A Characterization," Quarterly Journal of Political Science, now publishers, vol. 12(3), pages 325-346, October.
    20. Hubert, Franz & Orlova, Ekaterina, 2018. "Network access and market power," Energy Economics, Elsevier, vol. 76(C), pages 170-185.

    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:eee:matsoc:v:115:y:2022:i:c:p:47-51. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/505565 .

    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.