Weighted Voting Systems: A Threshold- Boolean Perspective
Abstract
Weighted voting systems play a crucial role in the investigation and modeling of manyengineering structures and political and socio-economic phenomena. There is an urgentneed to describe these systems in a simplified powerful mathematical way that can begeneralized to systems of any size. An elegant description of voting systems is presentedin terms of threshold Boolean functions. This description benefits considerably fromthe wealth of information about these functions, and of the potpourri of algebraic andmap techniques for handling them. The paper demonstrates that the prime implicantsof the system threshold function are its Minimal Winning Coalitions (MWC). Thepaper discusses the Boolean derivative (Boolean difference) of the system thresholdfunction with respect to each of its member components. The prime implicants of thisBoolean difference can be used to deduce the winning coalitions (WC) in which thepertinent member cannot be dispensed with. Each of the minterms of this Booleandifference is a winning coalition in which this member plays a pivotal role. However,the coalition ceases to be winning if the member defects from it. Hence, the numberof these minterms is identified as the Banzhaf index of voting power. The conceptsintroduced are illustrated with detailed demonstrative examples that also exhibit someof the known paradoxes of voting- system theory. Finally, the paper stresses the utilityof threshold Boolean functions in the understanding, study, analysis, and design ofweighted voting systems irrespective of size.
References
Alonso-Meijide, J. M. & Freixas, J. 2010. A new power index based on minimal winning coalitions
without any surplus. Decision Support Systems 49(1): 70-76.
Alonso-Meijide, J. M., Freixas, J. & Molinero, X. 2012. Computation of several power indices by
generating functions. Applied Mathematics and Computation 219(8): 3395-3402.
Axenovich, M. & Roy, S. 2010. On the structure of minimal winning coalitions in simple voting games.
Social Choice and Welfare 34(3): 429-440
Banzhaf, J. F., III. 1964. Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review
: 317-343.
Butterworth, R. L. 1971. A Research Note on the Size of Winning Coalitions. The American Political
Science Review 65: 741-748
Butterworth R. L. 1974. Comment on Shepsle’s “On the Size of Winning Coalitions“. The American
Political Science Review 68(2): 519-521.
Crama, Y. & Hammer, P. L. 2011. Boolean Functions: Theory, Algorithms, and Applications. Cambridge
University Press, Cambridge, United Kingdom.
Cross, J. G. 1967. Some Theoretic Characteristics of Economic and Political Coalitions. The Journal of
Conflict Resolution, 11(2): 184-195.
Das, S. & Rezek, I. 2012. Voting power: A generalised framework. arXiv preprint, arXiv:1201.4743.
Dubey, P. & Shapley, L. S. 1979. Mathematical properties of the Banzhaf power index. Mathematics of
Operations Research 4(2): 99-131.
Eryilmaz, S. 2015. Capacity loss and residual capacity in weighted k-out-of-n: G systems. Reliability
Engineering and Systems Safety 136: 140-144.
Fishburn, P. C. & Brams, S. J. 1996. Minimal winning coalitions in weighted-majority voting games. Social Choice and Welfare 13: 397-417.
Freixas, J. & Kaniovski, S. 2014. The minimum sum representation as an index of voting power. European
Journal of Operational Research 233(3): 739-748.
Freixas, J. & Pons, M. 2008. Identifying optimal components in a reliability system. IEEE Transactions
on Reliability 57: 163-170.
Freixas, J. & Puente, M. A. 2002. Reliability importance measures of the components in a system based
on semi-values and probabilistic values. Annals of Operations Research 109(1-4): 331-342.
Hammer, P. L. & Holzman, R. 1992. Approximations of pseudo-Boolean functions; Applications to
game theory. Zeitschrift für Operations Research 36(1): 3-21.
Hershey, M. R. 1973. Incumbency and the minimum winning coalition. American Journal of Political
Science 17(3): 631-637.
Holler, M. J. 1982. Forming coalitions and measuring voting power. Political studies 30(2): 262-271.
Holler, M. J. & Nurmi, H. 2013. Reflections on power, voting, and voting power. In Power, Voting, and
Voting Power: 30 Years After (pp. 1-24). Springer, Berlin-Heidelberg, Germany.
Houy, N. & Zwicker, W. S. 2014. The geometry of voting power: weighted voting and hyper-ellipsoids.
Games and Economic Behavior 84: 7-16.
Hurst, S. L., Miller, D. M. & Muzio, J. C. 1985. Spectral Techniques in Digital Logic, Academic Press,
London, UK.
Jelnov, A. & Tauman, Y. 2014. Voting power and proportional representation of voters. International
Journal of Game Theory 43(4), 747-766
Kirsch, W. & Langner, J. 2010. Power indices and minimal winning coalitions. Social Choice and
Welfare 34(1): 33-46.
Kuo, W. & Zhu, X. 2012. Importance Measures in Reliability, Risk, and Optimization: Principles and
Applications. John Wiley & Sons, New York, NY, USA.
Lee, S. C. 1978. Modern Switching Theory and Digital Design, Prentice-Hall, Englewood Cliffs, New
Jersey, NJ, USA.
March, J. G. 1962. The Business Firm as a Political Coalition, The Journal of Politics 24(4): 662-678.
Michael L. & Benoit K. 2015. The basic arithmetic of legislative decisions. American Journal of Political
Science 59 (2): 275-291.
Morgan, J. & Várdy, F. 2012. Negative vote buying and the secret ballot. Journal of Law, Economics,
and Organization 28 (4): 818-849.
Muroga, S. 1971. Threshold Logic and Its Applications, Wiley-Interscience, New York: NY, USA.
Muroga, S. 1979. Logic Design and Switching Theory, John Wiley & Sons, New York, NY, USA.
Nurmi, H., 1997. On power indices and minimal winning coalitions, Control and Cybernetics 26: 609-
Reed , I. S. 1973. Boolean Difference Calculus and Fault Finding, SIAM Journal on Applied Mathematics
(1): 134-143.
Rushdi, A. M. 1986a. Utilization of symmetric switching functions in the computation of k-out-of-n
system reliability. Microelectronics and Reliability 26(5): 973-987.
Rushdi, A. M. 1986b. Map differentiation of switching functions. Microelectronics and Reliability 26(5):
-908, 1986.
Rushdi, A. M. 1987a. On computing the syndrome of a switching function. Microelectronics and
Reliability 27(4): 703-716.
Rushdi, A. M. 1987b. On computing the spectral coefficients of a switching function. Microelectronics
and Reliability 27(6): 965-79.
Rushdi, A. M. 1990. Threshold systems and their reliability. Microelectronics and Reliability 30(2):
-312.
Rushdi, A. M. 1993. Reliability of k-out-of-n Systems, Chapter 5 in Misra, K. B. (Editor), New Trends
in System Reliability Evaluation. Vol. 16, Fundamental Studies in Engineering, Elsevier Science
Publishers, Amsterdam, The Netherlands, pp. 185-227.
Rushdi, A. M. 1997. Karnaugh map, Encyclopaedia of Mathematics, Supplement Volume I, M. Hazewinkel
(editor), Boston, Kluwer Academic Publishers, pp. 327-328. Available at http://eom.springer.de/K/
k110040.htm.
Rushdi, A. M. & Al-Yahya, H. A., 2000. A Boolean minimization procedure using the variable-entered
Karnaugh map and the generalized consensus concept. International Journal of Electronics 87(7):
-794.
Rushdi, A. M. & Al-Yahya, H. A. 2001a. Derivation of the complete sum of a switching function
with the aid of the variable-entered Karnaugh map. Journal of King Saud University: Engineering
Sciences 13(2): 239-269. Available at http://digital.library.ksu.edu.sa/paper818.html.
Rushdi, A. M. & Al-Yahya, H. A.. 2001b. Further improved variable-entered Karnaugh map procedures
for obtaining the irredundant forms of an incompletely-specified switching function. Journal
of King Abdulaziz University: Engineering Sciences 13(1): 111-152. Available at http://www.
kau.edu.sa/AccessPage.aspx.
Rushdi, A. M. A. 2010. Partially-redundant systems: Examples, reliability, and life expectancy.
International Magazine on Advances in Computer Science and Telecommunications 1(1): 1-13.
Rushdi, A. M. & Ba-Rukab, O. M. 2004. A map procedure for two-level multiple-output logic
minimization. Proceedings of the Seventeenth National Computer Conference, Al-Madinah Al-
Munw’ warah, Saudi Arabia, pp. 517-528.
Rushdi, A. M. & Ba-Rukab, O. M. 2007, A purely-map procedure for two-level multiple-output logic
minimization. International Journal of Computer Mathematics 84(1): 1-10.
Rushdi, A. M. A. & Albarakati, H. M. 2012. Using variable-entered Karnaugh maps in determining
dependent and independent sets of Boolean functions. Journal of King Abdulaziz University:
Computers and Information Technology 1(2): 45-67.
Rushdi, A. M. A. & Alturki, A.M. 2015. Reliability of coherent threshold systems. Journal of Applied
Science 15(3): 431-443.
Rushdi, A. M. A. & Hassan A. K. 2015. Reliability of migration between habitat patches with
heterogeneous ecological corridors. Ecological Modelling 304: 1-10.
Rushdi, A. M. A. & Hassan A. K. 2016. An exposition of system reliability analysis with an ecological
perspective, Ecological Indicators, 63:282-295.
Russell H. 1976. Hollow victory: The minimum winning coalition. The American Political Science
Review 70(4): 1202-1214
Shepsle, K. A. 1974a. On the size of winning coalitions. The American Political Science Review 68(02):
-518.
Shepsle, K. A. 1974b. On the Size of Winning Coalitions: Minimum Winning Coalitions Reconsidered: A
Rejoinder to Butterworth’s “Comment“. The American Political Science Review 68(2): 522-524.
Steen, L.A. 1994. For All Practical Purposes: Introduction to Contemporary Mathematics, Third Edition,
W.H. Freeman and Company, New York, NY, USA.
Steiner, H. G. 1967. An example of the axiomatic method in instruction: The Mathematics Teacher: 520-
Stewart, I. 1995., Election fever in Blockvotia, Scientific American 274(1): 80-81.
Taylor, A. D. & Pacelli, A. M. 2008. Mathematics and Politics: Strategy, Voting, Power, and Proof, Second
Edition, Springer Science+Business Media, New York, NY, USA.
Yamamoto, Y. 2012. Banzhaf index and Boolean difference, Proceedings of the 42nd IEEE International
Symposium on Multiple-Valued Logic (ISMVL): 191-196.
Zhu, X. & Kuo, W. 2014. Importance measures in reliability and mathematical programming, Annals of
Operations Research 212(1): 241-267.
