×

zbMATH — the first resource for mathematics

A relation-algebraic approach to simple games. (English) Zbl 1207.90064
Summary: Simple games are a powerful tool to analyze decision-making and coalition formation in social and political life. In this paper, we present relation-algebraic models of simple games and develop relational specifications for solving some basic problems of them. In particular, we test certain fundamental properties of simple games and compute specific players and coalitions. We also apply relation algebra to determine power indices. This leads to relation-algebraic specifications, which can be evaluated with the help of the BDD-based tool RelView after a simple translation into the tool’s programming language. In order to demonstrate the visualization facilities of RelView we consider an example of the Catalonian Parliament after the 2003 election.

MSC:
90B50 Management decision making, including multiple objectives
68W30 Symbolic computation and algebraic computation
91A12 Cooperative games
91A46 Combinatorial games
91A80 Applications of game theory
91F10 History, political science
Software:
Rath; RelView
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alonso-Meijide, J.M.; Casas-Mendez, B.; Holler, M.J.; Lorenzo-Freire, S., Computing power indices: multilinear extensions and new characterizations, European journal of operational research, 188, 540-554, (2008) · Zbl 1149.91014
[2] Banzhaf, J.F., Weighted voting doesn’t work: a mathematical analysis, Rutgers law review, 19, 317-343, (1965)
[3] Berghammer, R., Applying relation algebra and \screl view to solve problems on orders and lattices, Acta informatica, 45, 211-236, (2009)
[4] Berghammer, R.; Fronk, A., Exact computation of minimum feedback vertex sets with relational algebra, Fundamenta informatica, 70, 301-316, (2006) · Zbl 1110.68093
[5] Berghammer, R.; Karger von, B.; Ulke, C., Relation-algebraic analysis of Petri nets with \screlview, (), 49-69
[6] Berghammer, R.; Leoniuk, B.; Milanese, U., Implementation of relational algebra using binary decision diagrams, (), 241-257 · Zbl 1027.68036
[7] Berghammer, R.; Milanese, U., Relational approach to Boolean logic problems, (), 48-59 · Zbl 1185.03090
[8] Berghammer, R.; Rusinowska, A.; de Swart, H., Applying relation algebra and \screl view to coalition formation, European journal of operational research, 178, 530-542, (2007) · Zbl 1171.91312
[9] 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
[10] Berghammer, R.; Rusinowska, A.; de Swart, H., Applying relation algebra and \screl view to measures in a social network, European journal of operational research, 202, 182-195, (2010) · Zbl 1173.91446
[11] Berghammer, R.; Schmidt, G.; Winter, M., \screlview and \scrath - two systems for dealing with relations, (), 1-16
[12] Bolus, S., 2010. Power indices of simple games and vector-weighted majority games by means of binary decision diagrams. Submitted. · Zbl 1210.91012
[13] ()
[14] Deegan, J.; Packel, F.W., A new index of power for simple n-person games, International journal of game theory, 7, 113-123, (1978) · Zbl 0389.90093
[15] van Deemen, A., Dominant players and minimum size coalitions, European journal of political research, 17, 313-332, (1989)
[16] Dubey, P., On the uniqueness of the Shapley value, International journal of game theory, 4, 131-139, (1975) · Zbl 0352.90085
[17] Dubey, P.; Shapley, L.S., Mathematical properties of the Banzhaf power index, Mathematics of operations research, 4, 99-131, (1979) · Zbl 0409.90008
[18] Einy, E., On connected coalitions in dominated simple games, International journal of game theory, 14, 103-125, (1985) · Zbl 0569.90101
[19] Felsenthal, D.S.; Machover, M., The measurement of voting power: theory and practice, problems and paradoxes, (1998), Edward Elgar Publishers London · Zbl 0954.91019
[20] Freixas, J.; Molinero, X., Simple games and weighted games: A theoretical and computational viewpoint, Discrete applied mathematics, 157, 1496-1508, (2009) · Zbl 1168.91011
[21] Gansner, E.R.; Koutsofios, E.; North, S.C.; Vo, K.P., A technique for drawing directed graphs, IEEE transactions on software engineering, 19, 214-230, (1993)
[22] Holler, M.J., Forming coalitions and measuring voting power, Political studies, 30, 262-271, (1982)
[23] Holler, M.J.; Packel, E.W., Power, luck and the right index, Journal of economics, 43, 21-29, (1983)
[24] Hosaka, K.; Takenaga, Y.; Yajima, S., On the size of ordered binary decision diagrams representing threshold functions, (), 584-592 · Zbl 0953.68580
[25] Johnston, R.J., On the measurement of power: some reactions to laver, Environment and planning A, 10, 907-914, (1978)
[26] Klinz, B.; Woeginger, G.J., Faster algorithms for computing power indices in weighted voting games, Mathematical social sciences, 49, 111-116, (2005) · Zbl 1118.91007
[27] Laruelle, A.; Valenciano, F., Shapley – shubik and Banzhaf indices revisited, Mathematics of operations research, 26, 89-104, (2001) · Zbl 1073.91512
[28] Lehrer, E., An axiomatization of the Banzhaf value, International journal of game theory, 17, 89-99, (1988) · Zbl 0651.90097
[29] Leoniuk, B., 2001. ROBDD-basierte Implementierung von Relationen und relationalen Operationen mi Anwendungen. Ph.D. thesis, Universität Kiel.
[30] Lorenzo-Freire, S.; Alonso-Meijide, J.M.; Casas-Mendez, B.; Fiestras-Janeiro, M.G., Characterizations of the deegan – packel and johnston power indices, European journal of operational research, 177, 431-444, (2007) · Zbl 1111.90340
[31] Milanese, U., 2003. Zur Implementierung eines ROBDD-basierten Systems für die Manipulation und Visualisierung von Relationen. Ph.D. thesis, Universität Kiel.
[32] von Neumann, J.; Morgenstern, O., Theory of games and economic behaviour, (1944), Princeton University Press
[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-Verlag New York
[35] 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
[36] van Roozendaal, P., Centre parties and coalition cabinet formations: a game theoretic approach, European journal of political research, 18, 325-348, (1990)
[37] van Roozendaal, P., The effect of dominant and central parties on cabinet composition and durability, Legislative studies quarterly, 17, 5-36, (1992)
[38] van Roozendaal, P., Cabinets in multiparty democracies, (1992), Thesis Publishers Amsterdam
[39] 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)
[40] van Roozendaal, P., Government survival in western multi-party democracies.the effect of credible exit threats via dominance, European journal of political research, 32, 71-92, (1997)
[41] Schmidt, G.; Ströhlein, T., Relations and graphs, Discrete mathematics for computer scientists, EATCS monographs on theoretical computer science, (1993), Springer · Zbl 0581.05026
[42] Shapley, L.S., Simple games: an outline of the descriptive theory, Behavioral science, 7, 59-66, (1962)
[43] Shapley, L.S.; Shubik, M., A method for evaluating the distribution of power in a committee system, American political science review, 48, 787-792, (1954)
[44] Szymanski, O., 2003. Relationale Algebra im dreidimensionalen Software-Entwurf – ein werkzeugbasierter Ansatz. M.Sc. thesis, Universität Dortmund.
[45] Vailant, J.G., The complexity of computing the permanent, Theoretical computer science, 8, 189-201, (1979) · Zbl 0415.68008
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.