BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Author
Staudacher Jochen (Hochschule Kempten, Kempten, Germany), Kóczy László Á. (Centre for Economic and Regional Studies, Budapest, Hungary; Budapest University of Technology and Economics, Budapest, Hungary), Stach Izabella (AGH University of Science and Technology Kraków, Poland), Filipp Jan (Hochschule Kempten, Kempten, Germany), Kramer Marcus (Hochschule Kempten, Kempten, Germany), Noffke Till (Hochschule Kempten, Kempten, Germany), Olsson Linus (Hochschule Kempten, Kempten, Germany), Pichler Jonas (Hochschule Kempten, Kempten, Germany), Singer Tobias (Hochschule Kempten, Kempten, Germany)
Title
Computing Power Indices for Weighted Voting Games Via Dynamic Programming
Source
Operations Research and Decisions, 2021, vol. 31, no. 2, s. 123-145, tab., bibliogr. 36 poz.
Keyword
Teoria gier, Gry kooperacyjne, Programowanie dynamiczne
Game theory, Cooperative game, Dynamic programming
Note
summ.
The first author thanks the funding of the Bavarian State Ministry of Science and Arts. The second author thanks the funding of the National Research, Development and Innovations Office (NKFIH, K-128573)
Abstract
We study the efficient computation of power indices for weighted voting games using the paradigm of dynamic programming. We survey the state-of-the-art algorithms for computing the Banzhaf and Shapley-Shubik indices and point out how these approaches carry over to related power indices. Within a unified framework, we present new efficient algorithms for the Public Good index and a recently proposed power index based on minimal winning coalitions of the smallest size, as well as a very first method for computing the Johnston indices for weighted voting games efficiently. We introduce a software package providing fast C++ implementations of all the power indices mentioned in this article, discuss computing times, as well as storage requirements. (original abstract)
Accessibility
The Main Library of the Cracow University of Economics
The Library of Warsaw School of Economics
The Library of University of Economics in Katowice
Full text
Show
Bibliography
Show
  1. ALGABA E., BILBAO J.M., GARCIA J.F., LÓPEZ J., Computing power indices in weighted multiple majority games, Math. Soc. Sci., 2003, 46 (1), 63-80.
  2. ALGABA E., BILBAO J.M., FERNÁNDEZ J.R., The distribution of power in the European Constitution, Eur. J. Oper. Res., 2007, 176 (3), 1752-1766.
  3. ÁLVAREZ-MOZOS M., FERREIRA F., ALONSO-MEIJIDE J.M., PINTO A.A., Characterizations of power indices based on null player free winning coalitions, Optimization, 2015, 64 (3), 675-686.
  4. BANZHAF J.F., Weighted voting doesn't work: A mathematical analysis, Rutgers Law Rev., 1965, 19, 317.
  5. BERGHAMMER R., BOLUS S., RUSINOWSKA A., DE SWART H., A relation-algebraic approach to simple games, Eur. J. Oper. Res., 2011, 210 (1), 68-80.
  6. BERGHAMMER R., BOLUS S., On the use of binary decision diagrams for solving problems on simple games, Eur. J. Oper. Res., 2012, 222 (3), 529-541.
  7. BERTINI C., GAMBARELLI G., STACH I., A Public Help index, [In:] M. Braham, F. Steffen (Eds.), Power, freedom, and voting, Springer, Berlin 2008, 83-98.
  8. BERTINI C., STACH I., Banzhaf voting power measure, [In:] K. Dowding (Ed.), Encyclopedia of Power, SAGE, Los Angeles 2011, 54.
  9. BERTINI C., FREIXAS J., GAMBARELLI G., STACH I., Comparing power indices, Int. Game Theory Rev., 2013, 15 (2), 1340004.
  10. BERTINI C., STACH I., On public values and power indices, Dec. Mak. Manuf. Serv., 2015, 9 (1), 9-25.
  11. BERTINI C., MERCIK J., STACH I., Indirect control and power, Oper. Res. Dec., 2016, 26 (2), 7-30.
  12. BILBAO J.M., FERNANDEZ J.R., JIMÉNEZ LOSADA A., LOPEZ J.J., Generating functions for computing power indices efficiently, Top, 2000, 8 (2), 191-213.
  13. BOLUS S., Power indices of simple games and vector-weighted majority games by means of binary decision diagrams, Eur. J. Oper. Res., 2011, 210 (2), 258-272.
  14. BOLUS S., A QOBDD-based approach to simple games, PhD thesis, Christian-Albrechts Universität Kiel, Kiel 2012.
  15. CHAKRAVARTY S.R., MITRA M., SARKAR P., A Course on Cooperative Game Theory, Cambridge University Press, Cambridge 2015.
  16. DEEGAN J., PACKEL E.W., A new index of power for simple n-person games, Int. J. Game Theory, 1978, 7 (2), 113-123.
  17. DUBEY P., SHAPLEY L.S., Mathematical properties of the Banzhaf power index, Math. Oper. Res., 1979, 4 (2), 99-131.
  18. FELSENTHAL D.S., A well-behaved index of a priori p-power for simple n-person games, Homo Oecon., 2016, 33 (4), 367-381.
  19. https://gmplib.org/ (URL consulted in November 2020).
  20. HOLLER M.J., Forming coalitions and measuring voting power, Pol. Studies, 1982, 30 (2), 262-271.
  21. HOLLER M.J., RUPP F., Power in networks. A PGI analysis of Krackhardt's kite network, Springer Lecture Notes in Computer Science 11890, 2019, 21-34.
  22. JOHNSTON R.J., On the measurement of power. Some reactions to Laver, Environ. Plan. A, 1978, 10 (8), 907-914.
  23. KÖNIG T., BRÄUNINGER T., The inclusiveness of European decision rules, J. Theor. Pol., 1998, 10 (1), 125-142.
  24. KÓCZY L.Á., Beyond Lisbon. Demographic trends and voting power in the European Union Council of Ministers, Math. Soc. Sci., 2012, 63 (2), 152-158.
  25. KÓCZY L.Á., Power indices when players can commit to reject coalitions, Homo Oecon., 2016, 33 (1-2), 77-91.
  26. KURZ S., Computing the power distribution in the IMF, arXiv preprint, Comp. Sci. Game Theeory, 2016, arXiv: 1603.01443.
  27. LUCCHETTI R., RADRIZZANI P., Microarray data analysis via weighted indices and weighted majority games, [In:] F. Masulli, L.E. Peterson, R. Tagliaferri (Eds.), International meeting on computational intelligence methods for bioinformatics and biostatistics, Springer, Berlin 2009, 179-190.
  28. MATSUI T., MATSUI Y., A survey of algorithms for calculating power indices of weighted majority games, J. Oper. Res. Soc. Japan, 2000, 43 (1), 71-86.
  29. MATSUI Y., MATSUI T., NP-completeness for calculating power indices of weighted majority games, Theor. Comp. Sci., 2001, 263 (1-2), 305-310.
  30. MERCIK J., LOBOS K., Index of implicit power as a measure of reciprocal ownership, Springer Lecture Notes in Computer Science 9760, 2016, 128-140.
  31. MERCIK J., STACH I., On measurement of control in corporate structures, Springer Lecture Notes in Computer Science 11290, 2018, 64-79.
  32. NEVISON H., Structural power and satisfaction in simple games, [In:] S.J. Brams, A. Schotter, G. Schwödiauer (Eds.), Appl. Game Theory, Phys., Heidelberg 1979, 39-57.
  33. SHAPLEY L.S., SHUBIK M., A method for evaluating the distribution of power in a committee system, Amer. Pol. Sci. Rev., 1954, 48 (3), 787-792.
  34. STACH I., Shapley-Shubik index, [In:] K. Dowding (Ed.), Encyclopedia of Power, SAGE, Los Angeles 2011, 603-606.
  35. TANENBAUM P., Power in weighted voting games, Math. J., 1997, 7, 58-63.
  36. UNO T., Efficient computation of power indices for weighted majority games, Springer Lecture Notes in Computer Science 7676, 2012, 679-689.
Cited by
Show
ISSN
2081-8858
Language
eng
URI / DOI
http://dx.doi.org/10.37190/ord210206
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu