zbMATH — the first resource for mathematics

An interdisciplinary approach to coalition formation. (English) Zbl 1159.91311
Summary: A stable government is by definition not dominated by any other government. However, it may happen that all governments are dominated. In graph-theoretic terms this means that the dominance graph does not possess a source. In this paper we are able to deal with this case by a clever combination of notions from different fields, such as relational algebra, graph theory and social choice theory, and by using the computer support system RelView for computing solutions and visualizing the results. Using relational algorithms, in such a case we break all cycles in each initial strongly connected component by removing the vertices in an appropriate minimum feedback vertex set. In this way we can choose a government that is as close as possible to being un-dominated. To achieve unique solutions, we additionally apply the majority ranking recently introduced by Balinski and Laraki. The main parts of our procedure can be executed using the RelView tool. Its sophisticated implementation of relations allows to deal with graph sizes that are sufficient for practical applications of coalition formation.

91A12 Cooperative games
91A43 Games involving graphs
Rath; RelView
Full Text: DOI
[1] Arrow, K.J., Social choice and individual values, (1978), Yale University Press · Zbl 0984.91513
[2] M. Balinski, R. Laraki, A Theory of Measuring, Electing and Ranking. Ecole Polytechnique, Cahier No. 2006-11, 2006, Laboratoire d’Econometrie, Paris. <http://ceco.polytechnique.fr/>. · Zbl 1190.91051
[3] Behnke, R.; Berghammer, R.; Meyer, E.; Schneider, P., R\scelV\sciew - A system for calculation with relations and relational programming, (), 318-321
[4] Berghammer, R.; Leoniuk, B.; Milanese, U., Implementation of relational algebra using binary decision diagrams, (), 241-257 · Zbl 1027.68036
[5] Berghammer, R.; von Karger, B.; Ulke, C., Relation-algebraic analysis of Petri nets with R\scelV\sciew, (), 49-69
[6] Berghammer, R.; Rusinowska, A.; de Swart, H., Applying relational algebra and R\scelV\sciew to coalition formation, European journal of operational research, 178, 530-542, (2007) · Zbl 1171.91312
[7] Berghammer, R.; Schmidt, G.; Winter, M., R\scelV\sciew and R\scath - two systems for dealing with relations, (), 1-16
[8] Berghammer, R.; Fronk, A., Considering design tasks in OO-software engineering using relations and relation-based tools, Journal on relational methods in computer science, 1, 73-92, (2004)
[9] Berghammer, R.; Fronk, A., Exact computation of minimum feedback vertex sets with relational algebra, Fundamenta informaticae, 70, 4, 301-316, (2006) · Zbl 1110.68093
[10] ()
[11] Roubens, M.; Rusinowska, A.; de Swart, H., Using macbeth to determine utilities of governments to parties in coalition formation, European journal of operational research, 172, 2, 588-603, (2006) · Zbl 1120.90355
[12] A. Rusinowska, H. de Swart, Negotiating a stable government - An application of bargaining theory to a coalition formation model, Group Decision and Negotiation. Available from: <http://www.springerlink.com/content/a2838436t8jl7102/>.
[13] Rusinowska, A.; de Swart, H.; van der Rijt, J.W., A new model of coalition formation, Social choice and welfare, 24, 129-154, (2005) · Zbl 1100.91073
[14] Schmidt, G.; Ströhlein, T., Relations and graphs. discrete mathematics for computer scientists, EATCS monographs on theoretical computer science, (1993), Springer · Zbl 0900.68328
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.