Forms of representation for simple games: sizes, conversions and equivalences. (English) Zbl 1331.91023
Summary: Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems.
MSC:
| 91A12 | Cooperative games |
| 91B12 | Voting theory |
| 68Q25 | Analysis of algorithms and problem complexity |
| 91-02 | Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance |
References:
| [1] | Akers, S., Binary decision diagrams, IEEE Trans. Comput., C-27, 6, 509-516 (1978) · Zbl 0377.94038 |
| [2] | Algaba, E.; Bilbao, J. M.; Fernández-García, J. R.; López, J. J., Computing power indices in weighted multiple majority games, Math. Social Sci., 46, 1, 63-80 (2003) · Zbl 1053.91009 |
| [4] | Aziz, H., Algorithmic and complexity aspects of simple coalitional games (2009), Department of Computer Science, University of Warwick, (Ph.D. thesis) |
| [6] | Aziz, H.; Lachish, O.; Paterson, M.; Savani, R., Power indices in spanning connectivity games, (Goldberg, A. V.; Zhou, Y., Algorithmic Aspects in Information and Management, 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings. Algorithmic Aspects in Information and Management, 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5564 (2009)), 55-67 · Zbl 1246.91009 |
| [8] | Bachrach, Y.; Porat, E.; Rosenschein, J. S., Sharing rewards in cooperative connectivity games, J. Artificial Intelligence Res., 47, 281-311 (2008) · Zbl 1267.68244 |
| [9] | Bachrach, Y.; Rosenschein, J. S., Power in threshold network flow games, Auton. Agents Multi-Agent Syst., 18, 1, 106-132 (2009) |
| [10] | Ball, M. O.; Provan, J. S., Disjoint products and efficient computation of reliability, Oper. Res., 36, 5, 703-715 (1988) · Zbl 0665.90034 |
| [11] | Behle, M., On threshold BDDs and the optimal variable ordering problem, J. Comb. Optim., 16, 2, 107-118 (2008) · Zbl 1183.68411 |
| [12] | Berghammer, R.; Bolus, S., On the use of binary decision diagrams for solving problems on simple games, European J. Oper. Res., 222, 3, 529-541 (2012) · Zbl 1253.91014 |
| [13] | Bertini, C.; Freixas, J.; Gambarelli, G.; Stach, I., Comparing power indices, Int. Game Theory Rev., 15, 2, 1-19 (2013) · Zbl 1274.91037 |
| [14] | Bollig, B.; Wegener, I., Improving the variable ordering of OBDDs is NP-complete, IEEE Trans. Comput., 45, 9, 993-1002 (1996) · Zbl 1048.68571 |
| [15] | Bolus, S., Power indices of simple games and vector-weighted majority games by means of binary decision diagrams, European J. Oper. Res., 210, 2, 258-272 (2011) · Zbl 1210.91012 |
| [16] | Bolus, S., A QOBDD-based approach to simple games (2012), Department of Computer Science, University of Kiel, (Ph.D. thesis) |
| [18] | Boute, R., The binary decision machine as a programmable controller, EUROMICRO Newsl., 1, 2, 16-22 (1976) |
| [19] | Brams, S.; Straffin, P., Prisoners’ dilemma and the professional sports drafts, Amer. Math. Monthly, 86, 2, 80-88 (1979) · Zbl 0399.90120 |
| [20] | Brams, S.; Taylor, A., The Win-Win Solution: Guaranteeing Fair Shares to Everybody (1999), W. W. Norton & Company: W. W. Norton & Company New York, NY |
| [21] | Bryant, R., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., C-35, 8, 677-691 (1986) · Zbl 0593.94022 |
| [22] | Bryant, R., Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Comput. Surv., 24, 3, 293-318 (1992) |
| [23] | Carreras, F., A characterization of the Shapley-Shubik index of power via automorphisms, Stochastica, 8, 2, 171-179 (1984) · Zbl 0559.90102 |
| [24] | Carreras, F.; Freixas, J., Complete simple games, Math. Social Sci., 32, 2, 139-155 (1996) · Zbl 0920.90143 |
| [25] | Chalkiadakis, G.; Elkind, E.; Wooldridge, M., (Computational Aspects of Cooperative Game Theory. Computational Aspects of Cooperative Game Theory, Synthesis Lectures on Artificial Intelligence and Machine Learning (2011), Morgan & Claypool Publishers) · Zbl 1258.91005 |
| [26] | Crama, Y.; Hammer, P. L., (Boolean Functions: Theory, Algorithms, and Applications. Boolean Functions: Theory, Algorithms, and Applications, Encyclopedia of Mathematics and its Applications, vol. 142 (2011), Cambridge University Press: Cambridge University Press New York, NY) · Zbl 1237.06001 |
| [27] | Deegan, J.; Packel, E. W., A new index of power for simple \(n\)-person games, Internat. J. Game Theory, 7, 2, 113-123 (1978) · Zbl 0389.90093 |
| [28] | Deĭneko, V. G.; Woeginger, G. J., On the dimension of simple monotonic games, European J. Oper. Res., 170, 1, 315-318 (2006) · Zbl 1134.68369 |
| [29] | Einy, E.; Lehrer, E., Regular simple games, Internat. J. Game Theory, 18, 2, 195-207 (1989) · Zbl 0676.90103 |
| [30] | Eiter, T.; Makino, K.; Gottlob, G., Computational aspects of monotone dualization: A brief survey, Discrete Appl. Math., 156, 11, 2035-2049 (2008) · Zbl 1160.68016 |
| [32] | Fishburn, P., Preference, summation, and social welfare functions, Manage. Sci., 16, 3, 179-186 (1969) · Zbl 0186.30602 |
| [33] | Fragnelli, V.; Garcia-Jurado, I.; Mendez-Naya, L., On shortest path games, Math. Methods Oper. Res., 52, 2, 251-264 (2000) · Zbl 1103.91313 |
| [34] | Fredman, M.; Khachiyan, L. G., On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21, 3, 618-628 (1996) · Zbl 0864.68038 |
| [35] | Freixas, J., Estructura de los juegos simples (1994), Technical University of Catalonia, (in Spanish) |
| [36] | Freixas, J., Power indices, (Cochran, J. J.; Cox, L. A.; Keskinocak, P.; Kharoufeh, J. P.; Smith, J. C., Wiley Encyclopedia of Operations Research and Management Science. Vol. 8 (2011), John Wiley & Sons) |
| [37] | Freixas, J.; Kurz, S., On minimal integer representations of weighted games, Math. Social Sci., 67, 9-22 (2014) · Zbl 1286.91014 |
| [38] | Freixas, J.; Marciniak, D., A minimum dimensional class of simple games, TOP: Off. J. Span. Soc. Stat. Oper. Res., 17, 2, 407-414 (2009) · Zbl 1227.91003 |
| [39] | Freixas, J.; Molinero, X., On the existence of a minimum integer representation for weighted voting systems, Ann. Oper. Res., 166, 1, 243-260 (2009) · Zbl 1163.91339 |
| [40] | Freixas, J.; Molinero, X., Weighted games without a unique minimal representation in integers, Optim. Methods Softw., 25, 2, 203-215 (2010) · Zbl 1198.91030 |
| [41] | Freixas, J.; Molinero, X.; Olsen, M.; Serna, M., On the complexity of problems on simple games, RAIRO Oper. Res., 45, 4, 295-314 (2011) · Zbl 1235.68082 |
| [42] | Gilbert, E., Lattice theoretic properties of frontal switching functions, J. Math. Phys., 33, 57-67 (1954) · Zbl 0055.20109 |
| [43] | Gillies, D. B., Some theorems on \(n\)-person games (1953), Department of Mathematics, Princeton University, (Ph.D. thesis) · Zbl 0050.14406 |
| [44] | Golumbic, M., (Algorithmic Graph Theory and Perfect Graphs. Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics (1980), Academic Press: Academic Press New York, NY) · Zbl 0541.05054 |
| [45] | Granovetter, M., Threshold models of collective behavior, Am. J. Sociol., 83, 6, 1420-1443 (1978) |
| [46] | Gwehenberger, G., Anwendung einer binären verweiskettenmethode beim aufbau von listen (use of a binary tree structure for processing files), Elektron. Rechenanl., 10, 5, 223-226 (1968), (in German) · Zbl 0165.52007 |
| [47] | Hammer, P.; Kogan, A.; Rothblum, U., Evaluation, strength, and relevance of variables of Boolean functions, SIAM J. Discrete Math., 13, 3, 302-312 (2000) · Zbl 0954.06010 |
| [48] | Hayase, K.; Sadakane, K.; Tani, S., Output-size sensitiveness of OBDD construction through maximal independent set problem, (Lecture Notes in Computer Science, vol. 959 (1995)), 229-234 · Zbl 1527.68049 |
| [49] | Holler, M. J., Forming coalitions and measuring voting power, Polit. Stud., 30, 2, 262-271 (1982) · Zbl 0519.00015 |
| [50] | Hosaka, K.; Takenaga, Y.; Kaneda, T.; Yajima, S., Size of ordered binary decision diagrams representing threshold functions, Theoret. Comput. Sci., 180, 1-2, 47-60 (1997) · Zbl 0898.94018 |
| [51] | Hu, S., Threshold Logic (1965), University of California Press: University of California Press Berkeley and Los Angeles, CA · Zbl 0166.27101 |
| [52] | Isbell, J., A class of majority games, Q. J. Math. Oxford Scr., 7, 1, 183-187 (1956) · Zbl 0073.13401 |
| [53] | Isbell, J., A class of simple games, Duke Math. J., 25, 3, 423-439 (1958) · Zbl 0083.14301 |
| [54] | Ishiura, N.; Yajima, S., A class of logic functions expressible by polynomial-size binary decision diagrams, RIMS Kokyuroku, 754, 65-71 (1991) |
| [55] | Jeroslow, R. G., On defining sets of vertices of the hypercube by linear inequalities, Discrete Math., 11, 2, 119-124 (1975) · Zbl 0297.52009 |
| [56] | Johnson, D.; Yannakakis, M.; Papadimitriou, C., On generating all maximal independent sets, Inform. Process. Lett., 27, 3, 119-123 (1988) · Zbl 0654.68086 |
| [57] | Kalai, E.; Zemel, E., Totally balanced games and games of flow, Math. Oper. Res., 7, 3, 476-478 (1982) · Zbl 0498.90030 |
| [59] | Khachiyan, L. G., A polynomial algorithm in linear programming, Sov. Math. Dokl., 20, 191-194 (1979) · Zbl 0414.90086 |
| [60] | Krohn, I.; Sudhölter, P., Directed and weighted majority games, Math. Methods Oper. Res., 42, 2, 189-216 (1995) · Zbl 0841.90134 |
| [61] | Kurz, S.; Tautenhahn, N., On Dedekind’s problem for complete simple games, Internat. J. Game Theory, 42, 2, 411-437 (2013) · Zbl 1267.91031 |
| [62] | Lee, C., Representation of switching circuits by binary-decision programs, Bell Syst. Tech. J., 38, 4, 985-999 (1959) · Zbl 0222.94042 |
| [63] | Mahadev, M. V.R.; Peled, U. N., (Threshold Graphs and Related Topics. Threshold Graphs and Related Topics, Annals of Discrete Mathematics, vol. 56 (1995), Elsevier: Elsevier Amsterdam) · Zbl 0852.05001 |
| [64] | Makino, K., A linear time algorithm for recognizing regular Boolean functions, J. Algorithms, 43, 2, 155-176 (2002) · Zbl 1005.68180 |
| [65] | Maschler, M.; Peleg, B., A characterization, existence proof and dimension bounds for the kernel of a game, Pacific J. Math., 18, 2, 289-328 (1966) · Zbl 0144.43403 |
| [66] | Matsui, T.; Matsui, Y., A survey of algorithms for calculating power indices of weighted majority games, J. Oper. Res. Soc. Japan, 43, 1, 71-86 (2000) · Zbl 1028.91511 |
| [67] | McCulloch, W.; Pitts, W., A logical calculus of the ideas immanent in nervous activity, Bull. Math. Biophys., 5, 4, 115-133 (1943) · Zbl 0063.03860 |
| [68] | McNaughton, R., Unate truth functions, IRE Trans. Electron. Comput., EC-10, 1, 1-6 (1961) |
| [69] | Meinel, C., (Modified Branching Programs and their Computational Power. Modified Branching Programs and their Computational Power, Lecture Notes in Computer Science, vol. 370 (1989), Springer-Verlag: Springer-Verlag New York, NY) · Zbl 0669.68042 |
| [71] | Molinero, X.; Riquelme, F.; Serna, M., Cooperation through social influence, European J. Oper. Res., 242, 3, 960-974 (2015) · Zbl 1341.91014 |
| [72] | Morrison, D., Patricia—practical algorithm to retrieve information coded in alphanumeric, J. ACM, 15, 4, 514-534 (1968) |
| [73] | Muroga, S. I., Threshold Logic and its Applications (1971), Wiley-Interscience, John Wiley & Sons: Wiley-Interscience, John Wiley & Sons New York, NY · Zbl 0243.94014 |
| [74] | Muroga, S. I.; Toda, I.; Takasu, S., Theory of majority decision elements, J. Franklin Inst., 271, 5, 376-418 (1961) · Zbl 0196.51705 |
| [76] | Nebel, F., Shortest path games: computational complexity of solution concepts (2010), Institute for Logic, Language and Computation, University of Amsterdam, (Master’s thesis) |
| [77] | Ostmann, A., Decisions by players of comparable strength, J. Econ., 45, 3, 267-284 (1985) · Zbl 0576.90105 |
| [79] | Parberry, I., (Circuit Complexity and Neural Networks. Circuit Complexity and Neural Networks, Foundations of Computers (1994), MIT Press: MIT Press Cambridge, MA) · Zbl 0864.68082 |
| [80] | Peled, U.; Simeone, B., Polynomial-time algorithms for regular set-covering and threshold synthesis, Discrete Appl. Math., 12, 1, 57-69 (1985) · Zbl 0619.05020 |
| [81] | Peled, U.; Simeone, B., An \(O(n m)\)-time algorithm for computing the dual of a regular Boolean function, Discrete Appl. Math., 49, 1-3, 309-323 (1994) · Zbl 0802.90078 |
| [82] | Polyméris, A., Stability of two player game structures, Discrete Appl. Math., 156, 14, 2636-2646 (2008) · Zbl 1151.91318 |
| [83] | Post, E., Introduction to a general theory of elementary propositions, Amer. J. Math., 43, 3, 163-185 (1921) · JFM 48.1122.01 |
| [84] | Reiterman, J.; Rodl, V.; Sinajova, E.; Tuma, M., Threshold hypergraphs, Discrete Math., 54, 2, 193-200 (1985) · Zbl 0564.05043 |
| [85] | Riquelme, F., Structural and computational aspects of simple and influence games (2014), Department of Computer Science, Universitat Politècnica de Catalunya, (Ph.D. thesis) |
| [86] | Riquelme, F.; Polyméris, A., On the complexity of the decisive problem in simple and weighted games, Electron. Notes Discrete Math., 37, 21-26 (2011) · Zbl 1268.91064 |
| [87] | Sheng, C. L., (Threshold Logic. Threshold Logic, Electrical Science: A Series of Monographs and Texts (1969), The Ryerson Press, Academic Press: The Ryerson Press, Academic Press Toronto, London, New York) |
| [88] | Sperner, E., Ein satz über untermengen einer endlichen menge, Math. Z., 27, 1, 544-548 (1928), (in German) · JFM 54.0090.06 |
| [89] | Sudhölter, P., Star-shapedness of the kernel for homogeneous games and some applications to weighted majority games, Math. Social Sci., 32, 3, 179-214 (1996) · Zbl 0920.90146 |
| [90] | Taylor, A.; Zwicker, W., A characterization of weighted voting, Proc. Amer. Math. Soc., 115, 4, 1089-1094 (1992) · Zbl 0764.90018 |
| [91] | Taylor, A.; Zwicker, W., Weighted voting, multicameral representation, and power, Games Econom. Behav., 5, 1, 170-181 (1993) · Zbl 0765.90030 |
| [92] | Taylor, A.; Zwicker, W., Simple Games: Desirability Relations, Trading, Pseudoweightings (1999), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0943.91005 |
| [93] | von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1944), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0063.05930 |
| [94] | Voorneveld, M.; Grahn, S., Cost allocation in shortest path games, Math. Methods Oper. Res., 56, 2, 323-340 (2002) · Zbl 1071.91007 |
| [95] | Wegener, I., (The Complexity of Boolean Functions. The Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science (1987), John Wiley & Sons: John Wiley & Sons New York, NY) · Zbl 0623.94018 |
| [96] | Wegener, I., On the complexity of branching programs and decision trees for clique functions, J. ACM, 35, 2, 461-471 (1988) · Zbl 0652.68063 |
| [97] | Wegener, I., The size of reduced OBDD’s and optimal read-once branching programs for almost all Boolean functions, IEEE Trans. Comput., 43, 11, 1262-1269 (1994) · Zbl 1068.68685 |
| [98] | Wegener, I., (Branching Programs and Binary Decision Diagrams: Theory and Applications. Branching Programs and Binary Decision Diagrams: Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications (2000), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA) · Zbl 0956.68068 |
| [99] | West, D. B., Parameters of partial orders and graphs: packing, covering, and representation, (Rival, I., Graphs and Order. Graphs and Order, NATO ASI Series, vol. 147 (1985), D. Reidel Publishing), 267-350 · Zbl 0568.05042 |
| [100] | Winder, R. O., Single stage threshold logic, (1st Annual Symposium on Switching Circuit Theory and Logical Design, Chicago, Illinois, USA, October 9-14, 1960 (1960), IEEE Computer Society), 321-332 |
| [101] | Winder, R., Threshold logic (1962), Mathematics Department, Princeton University, (Ph.D. thesis) · Zbl 0207.02101 |
| [102] | Zuckerman, M.; Faliszewski, P.; Bachrach, Y.; Elkind, E., Manipulating the quota in weighted voting games, Artificial Intelligence, 180-181, 1-19 (2012) · Zbl 1238.91056 |
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.
