Applications of Relations and Graphs to Coalition Formation

Agnieszka Rusinowska, Rudolf Berghammer and Harrie de Swart
Additional contact information
Rudolf Berghammer: University of Kiel
Harrie de Swart: Tilburg University

No 2006.77, Working Papers from Fondazione Eni Enrico Mattei

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, social choice and bargaining 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. So, we can choose an un-dominated government. To achieve unique solutions, we additionally apply social choice rules. 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)
JEL-codes: C63 C88 D71 D72 D85 (search for similar items in EconPapers)
Date: 2006-05
New Economics Papers: this item is included in nep-cdm, nep-cmp and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://feem-media.s3.eu-central-1.amazonaws.com/w ... oads/NDL2006-077.pdf (application/pdf)

Related works:
Working Paper: Applications of Relations and Graphs to Coalition Formation (2006)
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:fem:femwpa:2006.77

Access Statistics for this paper

More papers in Working Papers from Fondazione Eni Enrico Mattei Contact information at EDIRC.
Bibliographic data for series maintained by Alberto Prina Cerai ( this e-mail address is bad, please contact ).