Computing power indices for weighted voting games via dynamic programming

• Autorzy: Staudacher Jochen , Kóczy László Á. , Stach Izabella , Filipp Jan , Kramer Marcus , Noffke Till , Olsson Linuss , Pichler Jonas , Singer Tobias

Identyfikatory

DOI

10.37190/ord210206

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

Słowa kluczowe

EN

cooperative game theory; power indices; weighted voting games; dynamic programming; minimal winning coalitions

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2021
• Tom: Vol. 31, No. 2
• Strony: 123--145
• Opis fizyczny: Bibliogr. 36 poz., tab.

Twórcy

autor

Staudacher Jochen

• Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany

autor

Kóczy László Á.

• Institute of Economics, Centre for Economic and Regional Studies, Tóth Kálmán u. 4, H-1097 Budapest, Hungary
• Department of Finance, Budapest University of Technology and Economics, Magyar tudósok körútja 2, H-1112 Budapest, Hungary

autor

Stach Izabella

• AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Kraków, Poland

autor

Filipp Jan

• Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany

autor

Kramer Marcus

• Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany

autor

Noffke Till

• Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany

autor

Olsson Linuss

• Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany

autor

Pichler Jonas

• Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany

autor

Singer Tobias

• Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).