Abstract
In the past years, a combinatorial method based on generating functions was introduced to compute Shapley–Shubik, Banzhaf and other indices for weighted majority games exactly and efficiently. In this paper, taking inspiration from what has already been done, in view of the efficiency of the generating functions method, we define a generating function for computing the Public Good index, maintaining the property of exactness of the resulting algorithm. The main difference with the existing algorithms derives from the fact that the Public Good index takes into account only minimal winning coalitions and counts how many swings of a player involve them. Moreover, we study the computational complexity of the algorithm and we evaluate the Public Good index for the vote share of the Russian Duma in 1995.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
This property is called monotonicity.
In the literature and in this paper, large voting games are voting games with, generically, a high number of players.
Algorithms available upon request to the author.
For further details on the UNSC see http://www.un.org/Docs/sc/index.html.
References
Algaba E, Bilbao JM, Fernández García JR, López JJ (2003) Computing power indices in weighted multiple majority games. Math Soc Sci 46:63–80
Algaba E, Bilbao JM, Fernández JR (2007) The distribution of power in the European Constitution. Eur J Oper Res 176:1752–1766
Alonso-Meijide JM (2002) Contributiones a la teoría del valor en juegos cooperativos con condicionamientos exógenos. PhD thesis, Santiago de Compostela University
Alonso-Meijide JM, Bowles C (2005) Generating functions for coalitional power indices: an application to the IMF. Ann Oper Res 137:21–44
Alonso-Meijide JM, Bilbao JM, Casas-Méndez B, Fernández García JR (2009) Weighted multiple majority games with unions: generating functions and applications to the European Union. Eur J Oper Res 198:530–544
Alonso-Meijide JM, Casas-Méndez B, Fiestras-Janeiro MG, Holler MJ (2010) Two variations of the Public Good Index for games with a priori unions. Control Cybern 39:839–855
Banzhaf JF (1965) Weighted voting doesn’t work: a mathematical analysis. Rutgers Law Rev 19:317–343
Barry B (1980) Is it better to be powerful or lucky? Polit Stud 28:183–194, 338–352
Bilbao JM, Fernandez JR, Jimenez Losada A, Lopez JJ (2000) Generating functions for computing power indices efficiently. Top 8:191–213
Brams SF, Affuso PJ (1976) Power and size: a new paradox. Theory Decis 7:29–56
Brams SJ, Fishburn PC (1995) When is size a liability? Bargaining power in minimal winning coalitions. J Theor Polit 7:301–316
Brams SJ, Fishburn PC (1996) Minimal winning coalitions in weighted-majority voting games. Soc Choice Welf 13:397–417
Chessa M, Fragnelli V (2012) A note on “Measurement of disproportionality in proportional representation systems”. Math Comput Model 55:1655–1660
Coleman JS (1971) Control of collectivities and the power of a collectivity to act. In: Lieberman B (ed) Social choice. Gordon & Breach, London, pp 269–300
Deegan J, Packel EW (1978) A new index of power for simple n-person games. Int J Game Theory 7:113–123
Deegan J, Packel EW (1980) An axiomatic family of power indices for simple n-person games. Public Choice 35:229–239
Fernández JR, Algaba E, Bilbao JM, Jiménez N, López JJ (2002) Generating functions for computing the Myerson value. Ann Oper Res 109:143–158
Gács P, Lovász L (1999) Complexity of algorithms. Lecture notes, Yale University. Available at http://www.esi2.us.es/~mbilbao/pdffiles/complex.pdf
Holler MJ (1982) Forming coalitions and measuring voting power. Polit Stud 30:262–271
Leech D (2003) Computing power indices for large voting games. Manag Sci 49:831–838
Lucas WF (1975) Measuring power in weighted voting systems. In: Brams SJ, Lucas WF, Straffin PD (eds) Political and related models. Springer, New York, pp 183–238
Mann I, Shapley LS (1960) Value of large games, IV: Evaluating the electoral college by Monte Carlo techniques. RM-2651, The Rand Corporation, Santa Monica, California
Mann I, Shapley LS (1962) Value of large games, VI: Evaluating the electoral college exactly. RM-3158-PR, The Rand Corporation, Santa Monica, California
Matsui T, Matsui Y (2000) A survey of algorithms for calculating power indices of weighted majority games. J Oper Res Soc Jpn 43:71–86
Myerson R (1977) Graphs and cooperation in games. Math Oper Res 2:225–229
Owen G (1972) Multilinear extensions of games. Manag Sci 18:64–79
Owen G (1975) Multilinear extensions and the Banzhaf value. Nav Res Logist Q 22:741–750
Owen G (1977) Values of games with a priori unions. Lect Notes Econ Math Syst 141:76–88
Penrose LS (1946) The elementary statistics of majority voting. J R Stat Soc 109:53–57
Riker WH (1962) The theory of political coalitions. Yale University Press, New Haven
Shapley LS (1953) A value for n-person games. Ann Math Stud 28:307–317
Shapley LS, Shubik M (1954) A method for evaluating the distribution of power in a committee system. Am Polit Sci Rev 48:787–792
Acknowledgements
The author thanks Vito Fragnelli for some useful discussions and two anonymous referees for the interesting suggestions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chessa, M. A generating functions approach for computing the Public Good index efficiently. TOP 22, 658–673 (2014). https://doi.org/10.1007/s11750-013-0286-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-013-0286-8