Applications of Relations and Graphs to Coalition Formation
AbstractA 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Fondazione Eni Enrico Mattei in its series Working Papers with number 2006.77.
Date of creation: May 2006
Date of revision:
Graph Theory; RELVIEW; Relational Algebra; Dominance; Stable Government;
Find related papers by JEL classification:
- D85 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Network Formation
- C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
- C88 - Mathematical and Quantitative Methods - - Data Collection and Data Estimation Methodology; Computer Programs - - - Other Computer Software
- D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
- D72 - Microeconomics - - Analysis of Collective Decision-Making - - - Political Processes: Rent-seeking, Lobbying, Elections, Legislatures, and Voting Behavior
This paper has been announced in the following NEP Reports:
- NEP-ALL-2006-07-21 (All new papers)
- NEP-CDM-2006-07-21 (Collective Decision-Making)
- NEP-CMP-2006-07-21 (Computational Economics)
- NEP-GTH-2006-07-21 (Game Theory)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Rudolf Berghammer & Harrie De Swart & Agnieszka Rusinowska, 2007.
"Applying relational algebra and RelView to coalition formation,"
- Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2007. "Applying relational algebra and RelView to coalition formation," European Journal of Operational Research, Elsevier, vol. 178(2), pages 530-542, April.
- Brams, Steven J. & Fishburn, Peter C., 2002.
Handbook of Social Choice and Welfare,
in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 4, pages 173-236
- Brams, Steven J., 1994. "Voting procedures," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 2, chapter 30, pages 1055-1089 Elsevier.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (barbara racah).
If references are entirely missing, you can add them using this form.