Forms of representation for simple games: Sizes, conversions and equivalences

Akers, 1978, Binary decision diagrams, IEEE Trans. Comput., C-27, 509, 10.1109/TC.1978.1675141 Algaba, 2003, Computing power indices in weighted multiple majority games, Math. Social Sci., 46, 63, 10.1016/S0165-4896(02)00086-0 Aziz, H., 2008. Complexity of comparison of influence of players in simple games. In: U. Endriss and P. W. Goldberg, (Eds.), Proceedings of the 2nd International Workshop on Computational Social Choice, COMSOC 2008, pp. 61–72. Aziz, 2009 Aziz, H., Brandt, F., Harrenstein, P., 2010. Monotone cooperative games and their threshold versions. In: W. van der Hoek, G. A. Kaminka, Y. Lespérance, M. Luck, and S. Sen, (Eds.), 9th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2010, Toronto, Canada, May 10–14, 2010, Vol. 1–3, pp. 1107–1114. Aziz, 2009, Power indices in spanning connectivity games, vol. 5564, 55 Bachrach, Y., Elkind, E., Faliszewski, P., 2011. Coalitional voting manipulation: A game-theoretic perspective. In: T. Walsh, (Ed.), IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16–22, 2011, pp. 49–54. Bachrach, 2008, Sharing rewards in cooperative connectivity games, J. Artificial Intelligence Res., 47, 281, 10.1613/jair.3841 Bachrach, 2009, Power in threshold network flow games, Auton. Agents Multi-Agent Syst., 18, 106, 10.1007/s10458-008-9057-6 Ball, 1988, Disjoint products and efficient computation of reliability, Oper. Res., 36, 703, 10.1287/opre.36.5.703 Behle, 2008, On threshold BDDs and the optimal variable ordering problem, J. Comb. Optim., 16, 107, 10.1007/s10878-007-9123-z Berghammer, 2012, On the use of binary decision diagrams for solving problems on simple games, European J. Oper. Res., 222, 529, 10.1016/j.ejor.2012.04.015 Bertini, 2013, Comparing power indices, Int. Game Theory Rev., 15, 1, 10.1142/S0219198913400045 Bollig, 1996, Improving the variable ordering of OBDDs is NP-complete, IEEE Trans. Comput., 45, 993, 10.1109/12.537122 Bolus, 2011, Power indices of simple games and vector-weighted majority games by means of binary decision diagrams, European J. Oper. Res., 210, 258, 10.1016/j.ejor.2010.09.020 Bolus, 2012 Bolus, S., 2015. SimpleGame Lab, February. http://www.informatik.uni-kiel.de/~progsys/simple_games/lab. Boute, 1976, The binary decision machine as a programmable controller, EUROMICRO Newsl., 1, 16, 10.1016/0303-1268(76)90033-X Brams, 1979, Prisoners’ dilemma and the professional sports drafts, Amer. Math. Monthly, 86, 80 Brams, 1999 Bryant, 1986, Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., C-35, 677, 10.1109/TC.1986.1676819 Bryant, 1992, Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Comput. Surv., 24, 293, 10.1145/136035.136043 Carreras, 1984, A characterization of the Shapley–Shubik index of power via automorphisms, Stochastica, 8, 171 Carreras, 1996, Complete simple games, Math. Social Sci., 32, 139, 10.1016/0165-4896(96)00815-3 Chalkiadakis, 2011 Crama, 2011, vol. 142 Deegan, 1978, A new index of power for simple n-person games, Internat. J. Game Theory, 7, 113, 10.1007/BF01753239 Deĭneko, 2006, On the dimension of simple monotonic games, European J. Oper. Res., 170, 315, 10.1016/j.ejor.2004.09.038 Einy, 1989, Regular simple games, Internat. J. Game Theory, 18, 195, 10.1007/BF01268159 Eiter, 2008, Computational aspects of monotone dualization: A brief survey, Discrete Appl. Math., 156, 2035, 10.1016/j.dam.2007.04.017 Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M., 2008. On the dimensionality of voting games. In: D. Fox and C. P. Gomes, (Eds.), Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13–17, 2008, pp. 69–74. Fishburn, 1969, Preference, summation, and social welfare functions, Manage. Sci., 16, 179, 10.1287/mnsc.16.3.179 Fragnelli, 2000, On shortest path games, Math. Methods Oper. Res., 52, 251, 10.1007/s001860000061 Fredman, 1996, On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21, 618, 10.1006/jagm.1996.0062 Freixas, 1994 Freixas, 2011, Power indices Freixas, 2014, On minimal integer representations of weighted games, Math. Social Sci., 67, 9, 10.1016/j.mathsocsci.2013.10.005 Freixas, 2009, A minimum dimensional class of simple games, TOP: Off. J. Span. Soc. Stat. Oper. Res., 17, 407, 10.1007/s11750-009-0115-2 Freixas, 2009, On the existence of a minimum integer representation for weighted voting systems, Ann. Oper. Res., 166, 243, 10.1007/s10479-008-0422-2 Freixas, 2010, Weighted games without a unique minimal representation in integers, Optim. Methods Softw., 25, 203, 10.1080/10556780903057333 Freixas, 2011, On the complexity of problems on simple games, RAIRO Oper. Res., 45, 295, 10.1051/ro/2011115 Gilbert, 1954, Lattice theoretic properties of frontal switching functions, J. Math. Phys., 33, 57, 10.1002/sapm195433157 Gillies, 1953 Golumbic, 1980 Granovetter, 1978, Threshold models of collective behavior, Am. J. Sociol., 83, 1420, 10.1086/226707 Gwehenberger, 1968, Anwendung einer binären verweiskettenmethode beim aufbau von listen (use of a binary tree structure for processing files), Elektron. Rechenanl., 10, 223 Hammer, 2000, Evaluation, strength, and relevance of variables of Boolean functions, SIAM J. Discrete Math., 13, 302, 10.1137/S089548019732787X Hayase, 1995, Output-size sensitiveness of OBDD construction through maximal independent set problem, vol. 959, 229 Holler, 1982, Forming coalitions and measuring voting power, Polit. Stud., 30, 262, 10.1111/j.1467-9248.1982.tb00537.x Hosaka, 1997, Size of ordered binary decision diagrams representing threshold functions, Theoret. Comput. Sci., 180, 47, 10.1016/S0304-3975(97)83807-8 Hu, 1965 Isbell, 1956, A class of majority games, Q. J. Math. Oxford Scr., 7, 183, 10.1093/qmath/7.1.183 Isbell, 1958, A class of simple games, Duke Math. J., 25, 423, 10.1215/S0012-7094-58-02537-7 Ishiura, 1991, A class of logic functions expressible by polynomial-size binary decision diagrams, RIMS Kokyuroku, 754, 65 Jeroslow, 1975, On defining sets of vertices of the hypercube by linear inequalities, Discrete Math., 11, 119, 10.1016/0012-365X(75)90003-5 Johnson, 1988, On generating all maximal independent sets, Inform. Process. Lett., 27, 119, 10.1016/0020-0190(88)90065-8 Kalai, 1982, Totally balanced games and games of flow, Math. Oper. Res., 7, 476, 10.1287/moor.7.3.476 Kempe, D., Kleinberg, J., Tardos, E., 2003. Maximizing the spread of influence through a social network. In: L. Getoor, T. E. Senator, P. Domingos, and C. Faloutsos, (Eds.), Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24–27, 2003, pp. 137–146. Khachiyan, 1979, A polynomial algorithm in linear programming, Sov. Math. Dokl., 20, 191 Krohn, 1995, Directed and weighted majority games, Math. Methods Oper. Res., 42, 189, 10.1007/BF01415753 Kurz, 2013, On Dedekind’s problem for complete simple games, Internat. J. Game Theory, 42, 411, 10.1007/s00182-012-0327-9 Lee, 1959, Representation of switching circuits by binary-decision programs, Bell Syst. Tech. J., 38, 985, 10.1002/j.1538-7305.1959.tb01585.x Mahadev, 1995, vol. 56 Makino, 2002, A linear time algorithm for recognizing regular Boolean functions, J. Algorithms, 43, 155, 10.1016/S0196-6774(02)00003-2 Maschler, 1966, A characterization, existence proof and dimension bounds for the kernel of a game, Pacific J. Math., 18, 289, 10.2140/pjm.1966.18.289 Matsui, 2000, A survey of algorithms for calculating power indices of weighted majority games, J. Oper. Res. Soc. Japan, 43, 71 McCulloch, 1943, A logical calculus of the ideas immanent in nervous activity, Bull. Math. Biophys., 5, 115, 10.1007/BF02478259 McNaughton, 1961, Unate truth functions, IRE Trans. Electron. Comput., EC-10, 1, 10.1109/TEC.1961.5219145 Meinel, 1989, vol. 370 Molinero, X., Olsen, M., Serna, M., 2015a. On the complexity of exchanging, March. http://arxiv.org/abs/1503.06052v2. Molinero, 2015, Cooperation through social influence, European J. Oper. Res., 242, 960, 10.1016/j.ejor.2014.11.006 Morrison, 1968, Patricia—practical algorithm to retrieve information coded in alphanumeric, J. ACM, 15, 514, 10.1145/321479.321481 Muroga, 1971 Muroga, 1961, Theory of majority decision elements, J. Franklin Inst., 271, 376, 10.1016/0016-0032(61)90702-5 National Institute of Standards and Technology, 2015. Dictionary of algorithms and data structures, February. http://xlinux.nist.gov/dads. Nebel, 2010 Ostmann, 1985, Decisions by players of comparable strength, J. Econ., 45, 267 Ostmann, A., 1987. Life-length of a process with elements of decreasing importance. Working Paper 156. Institut für Mathematische Wirtschaftsforschung, Universität Bielefeld. Parberry, 1994 Peled, 1985, Polynomial-time algorithms for regular set-covering and threshold synthesis, Discrete Appl. Math., 12, 57, 10.1016/0166-218X(85)90040-X Peled, 1994, An O(nm)-time algorithm for computing the dual of a regular Boolean function, Discrete Appl. Math., 49, 309, 10.1016/0166-218X(94)90215-1 Polyméris, 2008, Stability of two player game structures, Discrete Appl. Math., 156, 2636, 10.1016/j.dam.2007.11.009 Post, 1921, Introduction to a general theory of elementary propositions, Amer. J. Math., 43, 163, 10.2307/2370324 Reiterman, 1985, Threshold hypergraphs, Discrete Math., 54, 193, 10.1016/0012-365X(85)90080-9 Riquelme, 2014 Riquelme, 2011, On the complexity of the decisive problem in simple and weighted games, Electron. Notes Discrete Math., 37, 21, 10.1016/j.endm.2011.05.005 Sheng, 1969 Sperner, 1928, Ein satz über untermengen einer endlichen menge, Math. Z., 27, 544, 10.1007/BF01171114 Sudhölter, 1996, Star-shapedness of the kernel for homogeneous games and some applications to weighted majority games, Math. Social Sci., 32, 179, 10.1016/S0165-4896(96)00816-5 Taylor, 1992, A characterization of weighted voting, Proc. Amer. Math. Soc., 115, 1089, 10.1090/S0002-9939-1992-1092927-0 Taylor, 1993, Weighted voting, multicameral representation, and power, Games Econom. Behav., 5, 170, 10.1006/game.1993.1009 Taylor, 1999 von Neumann, 1944 Voorneveld, 2002, Cost allocation in shortest path games, Math. Methods Oper. Res., 56, 323, 10.1007/s001860200222 Wegener, 1987 Wegener, 1988, On the complexity of branching programs and decision trees for clique functions, J. ACM, 35, 461, 10.1145/42282.46161 Wegener, 1994, The size of reduced OBDD’s and optimal read-once branching programs for almost all Boolean functions, IEEE Trans. Comput., 43, 1262, 10.1109/12.324559 Wegener, 2000 West, 1985, Parameters of partial orders and graphs: packing, covering, and representation, vol. 147, 267 Winder, 1960, Single stage threshold logic, 321 Winder, 1962 Zuckerman, 2012, Manipulating the quota in weighted voting games, Artificial Intelligence, 180–181, 1, 10.1016/j.artint.2011.12.003