Applications of Relations and Graphs to Coalition Formation

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.


Issue Date:
2006
Publication Type:
Working or Discussion Paper
PURL Identifier:
http://purl.umn.edu/12162
Total Pages:
21
Series Statement:
CTN Nota di Lavoro 77.2006




 Record created 2017-04-01, last modified 2017-04-04

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)