Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Czasopismo
Rocznik
Tom
Strony
123--145
Opis fizyczny
Bibliogr. 36 poz., tab.
Twórcy
autor
- Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany
autor
- 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
- AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Kraków, Poland
autor
- Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany
autor
- Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany
autor
- Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany
autor
- Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany
autor
- Fakultät Informatik, Hochschule Kempten, Bahnhofstr. 61, 87435 Kempten, Germany
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-d731158f-d8bc-4d53-bec6-dd4102ced279