×

On the use of binary decision diagrams for solving problems on simple games. (English) Zbl 1253.91014

Summary: Simple games are yes/no cooperative games which arise in many practical applications. Recently, we have used reduced ordered binary decision diagrams and quasi-reduced ordered binary decision diagrams (abbreviated as Robdds and Qobdds, respectively) for the representation of simple games and for the computation of some power indices. In the present paper, we continue this work. We show how further important computational problems on simple games can be solved using Qobdds, viz. the identification of some key players, the computation of the desirability relation on individuals, the test whether a simple game is proper and strong, respectively, and the computation of Qobdd-representations for the sets of all minimal winning coalitions, all shift-minimal winning coalitions and all blocking coalitions, respectively. Applications of these solutions include the computation of recent power indices based on shift-minimal winning coalitions and the test for linear separability of a directed simple game.

MSC:

91A12 Cooperative games
91B06 Decision theory

Software:

azove; RelView; CUDD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alonso-Meijide, J.; Freixas, J., A new power index based on minimal winning coalitions without any surplus, Decision Support Systems, 49, 1, 70-76 (2010)
[2] Behle, M., On threshold BDDs and the optimal variable ordering problem, Journal of Combinatorial Optimization, 16, 107-118 (2008) · Zbl 1183.68411
[3] Berghammer, R.; Leoniuk, B.; Milanese, U., Implementation of relation algebra using binary decision diagrams, (de Swart, H., Relational Methods in Computer Science. Relational Methods in Computer Science, LNCS 2561 (2002), Springer), pp. 241-257 · Zbl 1027.68036
[4] Berghammer, R.; Neumann, F., Rel view – an obdd-based computer algebra system for relations, (Gansha, V. G.; Mayr, E. W.; Vorozhtsov, E., Computer Algebra in Scientific Computing. Computer Algebra in Scientific Computing, LNCS 3718 (2005), Springer), pp. 40-51 · Zbl 1144.68384
[5] Berghammer, R.; Rusinowska, A.; de Swart, H., Applying relation algebra and RelView to coalition formation, European Journal of Operational Research, 178, 530-542 (2007) · Zbl 1171.91312
[6] R. Berghammer, On the use of relation algebra and the Bdd-based tool RelView in formal algorithm development, in: B. Steinbach (Ed.), Proc. of the 8th International Workshop on Boolean Problems, TU Bergakademie Freiberg, 2008, pp. 153-162.; R. Berghammer, On the use of relation algebra and the Bdd-based tool RelView in formal algorithm development, in: B. Steinbach (Ed.), Proc. of the 8th International Workshop on Boolean Problems, TU Bergakademie Freiberg, 2008, pp. 153-162.
[7] Berghammer, R.; Rusinowska, A.; de Swart, H., An interdisciplinary approach to coalition formation, European Journal of Operational Research, 195, 487-496 (2009) · Zbl 1159.91311
[8] Berghammer, R.; Rusinowska, A.; de Swart, H., Applying relation algebra and RelView to measures in a social network, European Journal of Operational Research, 202, 182-195 (2010) · Zbl 1173.91446
[9] Bolling, B.; Wegener, I., Improving the variable ordering of Obdds is NP-complete, IEEE Transactions on Computers, 45, 993-1002 (1996) · Zbl 1048.68571
[10] Bolus, S., Power indices of simple games and vector-weighted majority games by means of binary decision diagrams, European Journal of Operations Research, 210, 2, 258-272 (2011) · Zbl 1210.91012
[11] Bryant, R. E., Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Computer Survey, 24, 293-318 (1992)
[12] Carreras, F., Protectionism and blocking power indices, TOP, 17, 70-84 (2009) · Zbl 1187.91047
[13] Carreras, F.; Freixas, J., Complete simple games, Mathematical Social Sciences, 32, 2, 139-155 (1996) · Zbl 0920.90143
[14] Chakravarty, N.; Goel, A. M.; Sastry, T., Easy weighted majority games, Mathematical Social Sciences, 40, 2, 227-235 (2000) · Zbl 0962.91006
[15] Daskalakis, C.; Karp, R. M.; Mossel, E.; Riesenfeld, S. J.; Verbin, E., Sorting and selection in posets, SIAM Journal on Computing, 40, 3, 597-622 (2011) · Zbl 1232.68034
[16] Deegan, J.; Packel, E. W., A new index of power for simple n-Person games, International Journal of Game Theory, 7, 2, 113-123 (1978) · Zbl 0389.90093
[17] van Deemen, A., Dominant players and minimum size coalitions, European Journal of Political Research, 17, 313-332 (1989)
[18] van Deemen, A., Coalition formation in centralized policy games, Journal of Theoretical Politics, 3, 139-161 (1991)
[19] Einy, E., On connected coalitions in dominated simple games, International Journal of Game Theory, 14, 103-125 (1985) · Zbl 0569.90101
[20] Elkind, E.; Goldberg, L. A.; Goldberg, P. W.; Wooldridge, M., On the computational complexity of weighted voting games, Annals of Mathematics and Artificial Intelligence, 56, 109-131 (2009) · Zbl 1185.91081
[21] Felsenthal, D. S.; Machover, M., The treaty of Nice and qualified majority voting, Social Choice and Welfare, 18, 431-464 (2001) · Zbl 1069.91527
[22] Freixas, J., The dimension for the European Union Council under the Nice rules, European Journal of Operational Research, 156, 2, 415-419 (2004) · Zbl 1056.90100
[23] Freixas, J.; Molinero, X., On the existence of a minimum integer representation of weighted voting systems, Annals of Operations Research, 166, 1, 243-260 (2008) · Zbl 1163.91339
[24] Greco, G.; Malizia, E.; Palopoli, L.; Scarcello, F., On the complexity of core, kernel, and bargaining set, Artificial Intelligence, 175, 12-13, 1877-1910 (2011) · Zbl 1233.91018
[25] Holler, M. J., Forming coalitions and measuring voting power, Political Studies, 30, 2, 262-271 (1982)
[26] Isbell, J. R., A class of simple games, Duke Mathematical Journal, 25, 3, 423-439 (1958) · Zbl 0083.14301
[27] Klinz, B.; Woeginger, G., Faster algorithms for computing power indices in weighted voting games, Mathematical Social Sciences, 49, 111-116 (2005) · Zbl 1118.91007
[28] Liaw, H.-T.; Lin, C.-S., On the OBDD-representation of general Boolean functions, IEEE Transactions on Computers, 41, 6, 661-664 (1992) · Zbl 1395.94400
[29] Maddux, R. D., Relation Algebras (2006), Elsevier · Zbl 0903.03039
[30] Matsui, T.; Matsui, Y., A survey of algorithms for calculating power indices of weighted majority games, Journal of the Operations Research Society of Japan, 43, 71-86 (2000) · Zbl 1028.91511
[31] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behaviour (1944), Princeton University Press
[32] Prasad, K.; Kelly, J. S., NP-completeness of some problems concerning voting games, International Journal of Game Theory, 19, 1-9 (1990) · Zbl 0705.90103
[33] Peleg, B., Coalition formation in simple games with dominant players, International Journal of Game Theory, 10, 11-33 (1981) · Zbl 0454.90097
[34] Peleg, B.; Sudhölter, P., Introduction to the Theory of Cooperative Games (2003), Springer
[35] van Roozendaal, P., Centre parties and coalition cabinet formations: a game theoretic approach, European Journal of Political Research, 18, 325-348 (1990)
[36] van Roozendaal, P., Cabinets in the Netherlands (1918-1990): the importance of ‘dominant’ and ‘central’ parties, European Journal of Political Research, 23, 35-54 (1993)
[37] Schmidt, G., Relational mathematics, (Encyclopedia of Mathematics and its Applications, vol. 132 (2011), Cambridge University Press) · Zbl 1214.06001
[38] F. Somenzi, Binary decision diagrams, Calculational System Design, NATO Science Series F: Computer and Systems Sciences, vol. 173, 1999, pp. 303-366.; F. Somenzi, Binary decision diagrams, Calculational System Design, NATO Science Series F: Computer and Systems Sciences, vol. 173, 1999, pp. 303-366. · Zbl 0948.68215
[39] F. Somenzi, CUDD: CU Decision Diagram Package, <http://vlsi.colorado.edu/f˜abio/CUDD/> (accessed January 2012).; F. Somenzi, CUDD: CU Decision Diagram Package, <http://vlsi.colorado.edu/f˜abio/CUDD/> (accessed January 2012).
[40] de Swart, H.; Rusinowska, A.; Berghammer, R., Computational social choice using relation algebra and RelView, (Berghammer, R.; Jaoua, A.; Möller, B., Relations and Kleene Algebra in Computer Science. Relations and Kleene Algebra in Computer Science, LNCS 5827 (2009), Springer), pp. 13-28 · Zbl 1267.91032
[41] Taylor, A. D.; Zwicker, W. S.; voting, Weighted, multicameral representation and power, Games and Economic Behaviour, 5, 170-181 (1993) · Zbl 0765.90030
[42] Taylor, A. D., Mathematics and Politics (1995), Springer · Zbl 0834.90002
[43] Taylor, A. D.; Zwicker, W. S., Simple Games, Desirability Relations, Trading and Pseudoweightings (1999), Princeton University Press · Zbl 0943.91005
[44] Wegener, I., The size of reduced OBDD’s and optimal read-once branching programs for almost all Boolean functions, IEEE Transactions on Computers, 43, 11, 1262-1269 (1994) · Zbl 1068.68685
[45] I. Wegener, Branching Programs and Binary Decision Diagrams: Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications, SIAM, 2000.; I. Wegener, Branching Programs and Binary Decision Diagrams: Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications, SIAM, 2000. · Zbl 0956.68068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.