An Interdisciplinary Approach to Coalition Formation

Rudolf Berghammer, Agnieszka Rusinowska and Harrie de Swart
Additional contact information
Rudolf Berghammer: Computer-Aided Program Development - Institute of Computer Science - CAU - Christian-Albrechts-Universität zu Kiel = Christian-Albrechts University of Kiel = Université Christian-Albrechts de Kiel
Harrie de Swart: Faculteit Wijsbegeerte-Logica en taalanalyse - Tilburg University [Netherlands]

Post-Print from HAL

Abstract: 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.

Keywords: Graph theory; RelView; relational algebra; dominance; stable government (search for similar items in EconPapers)
Date: 2009
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00406460v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (21)

Published in European Journal of Operational Research, 2009, 195 (2), pp.487-496. ⟨10.1016/j.ejor.2008.02.011⟩

Downloads: (external link)
https://shs.hal.science/halshs-00406460v1/document (application/pdf)

Related works:
Journal Article: An interdisciplinary approach to coalition formation (2009)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00406460

DOI: 10.1016/j.ejor.2008.02.011

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().