Computing Power Indices for Weighted Voting Games Via Dynamic Programming

• Autorzy: Jochen Staudacher , László Á. Kóczy , Izabella Stach , Jan Filipp , Marcus Kramer , Till Noffke , Linus Olsson , Jonas Pichler , Tobias Singer
• Języki publikacji: EN

Abstrakty

EN

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)

Słowa kluczowe

EN

Game theory; Cooperative game; Dynamic programming

PL

Teoria gier; Gry kooperacyjne; Programowanie dynamiczne

• Czasopismo: Operations Research and Decisions
• Rocznik: 2021
• Tom: 31
• Numer: nr 2
• Strony: 123--145

Twórcy

autor

Jochen Staudacher

• Hochschule Kempten, Kempten, Germany

autor

László Á. Kóczy

• Centre for Economic and Regional Studies, Budapest, Hungary; Budapest University of Technology and Economics, Budapest, Hungary

autor

Izabella Stach

• AGH University of Science and Technology Kraków, Poland

autor

Jan Filipp

• Hochschule Kempten, Kempten, Germany

autor

Marcus Kramer

• Hochschule Kempten, Kempten, Germany

autor

Till Noffke

• Hochschule Kempten, Kempten, Germany

autor

Linus Olsson

• Hochschule Kempten, Kempten, Germany

autor

Jonas Pichler

• Hochschule Kempten, Kempten, Germany

autor

Tobias Singer

• Hochschule Kempten, Kempten, Germany

Bibliografia

• [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.

Identyfikatory

DOI

10.37190/ord210206