Computing power indices for weighted voting games via dynamic programming

• Authors: STAUDACHER Jochen , KÓCZY László Á. , STACH Izabella , FILIPP Jan , KRAMER Marcus , NOFFKE Till , OLSSON Linus , PICHLER Jonas , SINGER Tobias
• Languages of publication: EN

Abstracts

EN

We study the efficient computation of power indices for weighted voting games using the para- digm 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.

Keywords

EN

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

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2021
• Volume: 31
• Issue: 2
• Pages: 123-145

Contributors

author

STAUDACHER Jochen

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

author

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

author

STACH Izabella

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

author

FILIPP Jan

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

author

KRAMER Marcus

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

author

NOFFKE Till

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

author

OLSSON Linus

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

author

PICHLER Jonas

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

author

SINGER Tobias

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

References

• 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.
• 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.
• Á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.
• BANZHAF J.F., Weighted voting doesn’t work: A mathematical analysis, Rutgers Law Rev., 1965, 19, 317.
• 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.
• 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.
• 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.
• BERTINI C., STACH I., Banzhaf voting power measure, [In:] K. Dowding (Ed.), Encyclopedia of Power, SAGE, Los Angeles 2011, 54.
• BERTINI C., FREIXAS J., GAMBARELLI G., STACH I., Comparing power indices, Int. Game Theory Rev., 2013, 15 (2), 1340004.
• BERTINI C., STACH I., On public values and power indices, Dec. Mak. Manuf. Serv., 2015, 9 (1), 9–25.
• BERTINI C., MERCIK J., STACH I., Indirect control and power, Oper. Res. Dec., 2016, 26 (2), 7–30.
• 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.
• 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.
• BOLUS S., A QOBDD-based approach to simple games, PhD thesis, Christian-Albrechts Universität Kiel, Kiel 2012.
• CHAKRAVARTY S.R., MITRA M., SARKAR P., A Course on Cooperative Game Theory, Cambridge University Press, Cambridge 2015.
• DEEGAN J., PACKEL E.W., A new index of power for simple n-person games, Int. J. Game Theory, 1978, 7 (2), 113–123.
• DUBEY P., SHAPLEY L.S., Mathematical properties of the Banzhaf power index, Math. Oper. Res., 1979, 4 (2), 99–131.
• FELSENTHAL D.S., A well-behaved index of a priori p-power for simple n-person games, Homo Oecon., 2016, 33 (4), 367–381.
• https://gmplib.org/ (URL consulted in November 2020).
• HOLLER M.J., Forming coalitions and measuring voting power, Pol. Studies, 1982, 30 (2), 262–271.
• 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.
• JOHNSTON R.J., On the measurement of power. Some reactions to Laver, Environ. Plan. A, 1978, 10 (8), 907–914.
• KÖNIG T., BRÄUNINGER T., The inclusiveness of European decision rules, J. Theor. Pol., 1998, 10 (1), 125–142.
• 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.
• KÓCZY L.Á., Power indices when players can commit to reject coalitions, Homo Oecon., 2016, 33 (1–2), 77–91.
• KURZ S., Computing the power distribution in the IMF, arXiv preprint, Comp. Sci. Game Theeory, 2016, arXiv: 1603.01443.
• 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.
• 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.
• MATSUI Y., MATSUI T., NP-completeness for calculating power indices of weighted majority games, Theor. Comp. Sci., 2001, 263 (1–2), 305–310.
• MERCIK J., LOBOS K., Index of implicit power as a measure of reciprocal ownership, Springer Lecture Notes in Computer Science 9760, 2016, 128–140.
• MERCIK J., STACH I., On measurement of control in corporate structures, Springer Lecture Notes in Computer Science 11290, 2018, 64–79.
• 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.
• 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.
• STACH I., Shapley–Shubik index, [In:] K. Dowding (Ed.), Encyclopedia of Power, SAGE, Los Angeles 2011, 603–606.
• TANENBAUM P., Power in weighted voting games, Math. J., 1997, 7, 58–63.
• UNO T., Efficient computation of power indices for weighted majority games, Springer Lecture Notes in Computer Science 7676, 2012, 679–689.

Identifiers

DOI

10.37190/ord210206