Weighted voting systems: A threshold- Boolean perspective
Tóm tắt
Weighted voting systems play a crucial role in the investigation and modeling of many engineering structures and political and socio-economic phenomena. There is an urgent need to describe these systems in a simplified powerful mathematical way that can be generalized to systems of any size. An elegant description of voting systems is presented in terms of threshold Boolean functions. This description benefits considerably from the wealth of information about these functions, and of the potpourri of algebraic and map techniques for handling them. The paper demonstrates that the prime implicants of the system threshold function are its Minimal Winning Coalitions (MWC). The paper discusses the Boolean derivative (Boolean difference) of the system threshold function with respect to each of its member components. The prime implicants of this Boolean difference can be used to deduce the winning coalitions (WC) in which the pertinent member cannot be dispensed with. Each of the minterms of this Boolean difference 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 number of these minterms is identified as the Banzhaf index of voting power. The concepts introduced are illustrated with detailed demonstrative examples that also exhibit some of the known paradoxes of voting- system theory. Finally, the paper stresses the utility of threshold Boolean functions in the understanding, study, analysis, and design of weighted voting systems irrespective of size.
Tài liệu tham khảo
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 19: 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–612.
Reed, I. S. 1973. Boolean Difference Calculus and Fault Finding, SIAM Journal on Applied Mathematics 24(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): 891–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): 299–312.
Rushdi, A. M. 1993. Reliability of k-out-of-n Systems, Chap. 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): 769–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): 505–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.