Combinatorial and computational aspects of multiple weighted voting games
Aziz, Haris, Paterson, Michael S. and Leech, Dennis (2007) Combinatorial and computational aspects of multiple weighted voting games. Working Paper. University of Warwick, Department of Economics, Coventry.
WRAP_Aziz_twerp_823.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Official URL: http://www2.warwick.ac.uk/fac/soc/economics/resear...
Weighted voting games are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model situations where agents with variable voting weight vote in favour of or against a decision. A coalition of agents is winning if and only if the sum of weights of the coalition exceeds or equals a specified quota. We provide a mathematical and computational characterization of multiple weighted voting games which are an extension of weighted voting games1. We analyse the structure of multiple weighted voting games and some of their combinatorial properties especially with respect to dictatorship, veto power, dummy players and Banzhaf indices. Among other results we extend the concept of amplitude to multiple weighted voting games. An illustrative Mathematica program to compute voting power properties of multiple weighted voting games is also provided.
|Item Type:||Working or Discussion Paper (Working Paper)|
|Subjects:||H Social Sciences > HB Economic Theory
Q Science > QA Mathematics
|Divisions:||Faculty of Science > Computer Science
Faculty of Social Sciences > Economics
|Library of Congress Subject Headings (LCSH):||Game theory, Power (Social Sciences), Voting, Combinatorial analysis|
|Series Name:||Warwick economic research papers|
|Publisher:||University of Warwick, Department of Economics|
|Place of Publication:||Coventry|
|Number of Pages:||19|
|Status:||Not Peer Reviewed|
|Access rights to Published version:||Open Access|
|Funder:||Engineering and Physical Sciences Research Council (EPSRC), National ICT R&D Fund (Pakistan)|
|References:|| A. Taylor and W. Zwicker, Simple Games: Desirability Relations, Trading, Pseudoweightings, first edition ed. New Jersey: Princeton University Press, 1999.  L. Nordmann and H. Pham, “Weighted voting systems,” IEEE Transactions on Reliability, vol. 48, no. 1, pp. 42–49, Mar 1999.  D. Leech, “Voting power in the governance of the international monetary fund,” Annals of Operations Research, vol. 109, no. 1, pp. 375–397, 2002.  J. Alonso-Meijide, “Generating functions for coalition power indices: An application to the IMF,” Annals of Operations Research, vol. 137, pp. 21–44, 2005.  E. Algaba, J. M. Bilbao, and J. Fernandez, “The distribution of power in the European Constitution,” European Journal of Operational Research, vol. 176, no. 3, pp. 1752–1755, 2007.  J. Bilbao, J. Fernandez, N. Jimenez, and J. Lopez, “Voting power in the European Union Enlargement,” European Journal of Operational Research, vol. 143, no. 1, pp. 181–196, 2002.  A. Laruelle and M. Widgren, “Is the allocation of voting power among EU states fair?” Public Choice, vol. 94, no. 3-4, pp. 317–39, March 1998, available at http://ideas.repec.org/a/kap/pubcho/v94y1998i3-4p317-39.html.  J.-E. Lane and R. Maeland, “Constitutional analysis: The power index approach,” European Journal of Political Research, vol. 37, pp. 31–56, 2000.  D. Leech, “Designing the voting system for the council of the european union volume,” Public Choice, vol. 113, no. 3, pp. 437–464, 1962.  D. S. Felsenthal and M. Machover, “Analysis of QM rules in the draft constitution for Europe proposed by the European Convention, 2003,” Social Choice and Welfare, vol. 23, no. 1, pp. 1–20, 08 2004.  G. Arcaini and G. Gambarelli, “Algorithm for automatic computation of the power variations in share tradings,” Calcolo, vol. 23, no. 1, pp. 13–19, January 1986.  G. Gambarelli, “Power indices for political and financial decision making: A review,” Annals of Operations Research, vol. 51, pp. 1572–9338, 1994.  V. G. Deineko and G. J. Woeginger, “On the dimension of simple monotonic games.” European Journal of Operational Research, vol. 170, no. 1, pp. 315–318, 2006.  J. Freixas and M. A. Puente, “A note about games-composition dimension,” Discrete Appl. Math., vol. 113, no. 2-3, pp. 265–273, 2001.  T. Matsui and Y. Matsui, “A survey of algorithms for calculating power indices of weighted majority games,” Journal of the Operations Research Society of Japan, vol. 43, no. 7186, 2000, available at http://citeseer.ist.psu.edu/matsui00survey.html.  B. Klinz and G. J. Woeginger, “Faster algorithms for computing power indices in weighted voting games,” Mathematical Social Sciences, vol. 49, no. 1, pp. 111–116, January 2005, available at http://ideas.repec.org/a/eee/matsoc/v49y2005i1p111-116.html.  E. Horowitz and S. Sahni, “Computing partitions with applications to the knapsack problem,” J. ACM, vol. 21, no. 2, pp. 277–292, 1974.  D. Leech, “Voting power algorithms website,” http://www.warwick.ac.uk/�ecaae/, 2007.  E. Algaba, J. M. Bilbao, J. R. Fernandez Garcia, and J. J. Lopez, “Computing power indices in weighted multiple majority games,” Mathematical Social Sciences, vol. 46, no. 1, pp. 63–80, 2003.  E. Elkind, L. Goldberg, P. Goldberg, and M. Wooldbridge, “Computational complexity of weighted threshold games,” AAAI-07 (Twenty- Second National Conference on Artificial Intelligence), 2007.|
Actions (login required)