IDEAS home Printed from https://ideas.repec.org/p/hal/journl/halshs-00406460.html
   My bibliography  Save this paper

An Interdisciplinary Approach to Coalition Formation

Author

Listed:
  • 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)

  • Agnieszka Rusinowska

    (GATE - Groupe d'analyse et de théorie économique - UL2 - Université Lumière - Lyon 2 - ENS LSH - Ecole Normale Supérieure Lettres et Sciences Humaines - CNRS - Centre National de la Recherche Scientifique)

  • Harrie de Swart

    (Faculteit Wijsbegeerte-Logica en taalanalyse - Tilburg University [Netherlands])

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.

Suggested Citation

  • Rudolf Berghammer & Agnieszka Rusinowska & Harrie de Swart, 2009. "An Interdisciplinary Approach to Coalition Formation," Post-Print halshs-00406460, HAL.
    • Handle: RePEc:hal:journl:halshs-00406460
    DOI: 10.1016/j.ejor.2008.02.011
    Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00406460
    as

    Download full text from publisher

    File URL: https://shs.hal.science/halshs-00406460/document
    Download Restriction: no
    File URL: https://libkey.io/10.1016/j.ejor.2008.02.011?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. 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.
    2. Michel L. Balinski & Rida Laraki, 2006. "A Theory of Measuring, Electing and Ranking," Working Papers hal-00243040, HAL.
    3. Roubens, Marc & Rusinowska, Agnieszka & de Swart, Harrie, 2006. "Using MACBETH to determine utilities of governments to parties in coalition formation," European Journal of Operational Research, Elsevier, vol. 172(2), pages 588-603, July.
    4. Agnieszka Rusinowska & Harrie de Swart & Jan-Willem van der Rijt, 2005. "A new model of coalition formation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 24(1), pages 129-154, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2010. "Applying relation algebra and RelView to measures in a social network," European Journal of Operational Research, Elsevier, vol. 202(1), pages 182-195, April.
    2. Rudolf Berghammer & Agnieszka Rusinowska & Harrie de Swart, 2011. "Computations on Simple Games using REL VIEW," Post-Print halshs-00587690, HAL.
    3. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2013. "Computing tournament solutions using relation algebra and RelView," European Journal of Operational Research, Elsevier, vol. 226(3), pages 636-645.
    4. Berghammer, Rudolf & Bolus, Stefan & Rusinowska, Agnieszka & de Swart, Harrie, 2011. "A relation-algebraic approach to simple games," European Journal of Operational Research, Elsevier, vol. 210(1), pages 68-80, April.
    5. repec:hal:wpaper:hal-00756696 is not listed on IDEAS
    6. Nessah, Rabia & Tazdaı¨t, Tarik, 2013. "Absolute optimal solution for a compact and convex game," European Journal of Operational Research, Elsevier, vol. 224(2), pages 353-361.
    7. Berghammer, Rudolf & Bolus, Stefan, 2012. "On the use of binary decision diagrams for solving problems on simple games," European Journal of Operational Research, Elsevier, vol. 222(3), pages 529-541.
    8. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2010. "Applying relation algebra and RelView to measures in a social network," European Journal of Operational Research, Elsevier, vol. 202(1), pages 182-195, April.
    9. Agnieszka Rusinowska & Rudolf Berghammer & Harrie de Swart & Michel Grabisch, 2011. "Social networks: Prestige, centrality, and influence (Invited paper)," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-00633859, HAL.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Agnieszka Rusinowska & Harrie Swart, 2008. "Negotiating a Stable Government: An Application of Bargaining Theory to a Coalition Formation Model," Group Decision and Negotiation, Springer, vol. 17(5), pages 445-464, September.
    2. Jan-Willem Rijt, 2008. "An Alternative Model of the Formation of Political Coalitions," Theory and Decision, Springer, vol. 64(1), pages 81-101, February.
    3. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2013. "Computing tournament solutions using relation algebra and RelView," European Journal of Operational Research, Elsevier, vol. 226(3), pages 636-645.
    4. Tangian, Andranik, 2010. "Evaluation of German parties and coalitions by methods of the mathematical theory of democracy," European Journal of Operational Research, Elsevier, vol. 202(1), pages 294-307, April.
    5. Tangian, Andranik S., 2013. "2013 election to German Bundestag from the viewpoint of direct democracy," WSI Working Papers 186, The Institute of Economic and Social Research (WSI), Hans Böckler Foundation.
    6. Tangian, Andranik S., 2013. "Decision making in politics and economics: 5. 2013 election to German Bundestag and direct democracy," Working Paper Series in Economics 49, Karlsruhe Institute of Technology (KIT), Department of Economics and Management.
    7. Tangian, Andranik S., 2010. "Representativeness of German parties and trade unions with regard to public opinion," WSI Working Papers 173, The Institute of Economic and Social Research (WSI), Hans Böckler Foundation.
    8. Andranik Tangian, 2013. "German parliamentary elections 2009 from the viewpoint of direct democracy," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(3), pages 833-869, March.
    9. Tangian, Andranik S., 2006. "German parliamentary elections 2005 in the mirror of party manifestos," WSI Working Papers 139E, The Institute of Economic and Social Research (WSI), Hans Böckler Foundation.
    10. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2010. "Applying relation algebra and RelView to measures in a social network," European Journal of Operational Research, Elsevier, vol. 202(1), pages 182-195, April.
    11. Patrik Eklund & Agnieszka Rusinowska & Harrie Swart, 2008. "A consensus model of political decision-making," Annals of Operations Research, Springer, vol. 158(1), pages 5-20, February.
    12. repec:hal:wpaper:hal-00756696 is not listed on IDEAS
    13. 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.
    14. Andranik Tangian, 2006. "Evaluation of Parties and Coalitions After Parliamentary Elections," Working Papers 2006.76, Fondazione Eni Enrico Mattei.
    15. Jaime Burgos & María Carmen Carnero, 2020. "Assessment of Social Responsibility in Education in Secondary Schools," Sustainability, MDPI, vol. 12(12), pages 1-38, June.
    16. Balinski, Michel & Jennings, Andrew & Laraki, Rida, 2009. "Monotonic incompatibility between electing and ranking," Economics Letters, Elsevier, vol. 105(2), pages 145-147, November.
    17. Sgobbi, Alessandra & Carraro, Carlo, 2007. "Modelling Negotiated Decision Making: a Multilateral, Multiple Issues, Non-Cooperative Bargaining Model with Uncertainty," Economic Theory and Applications Working Papers 8224, Fondazione Eni Enrico Mattei (FEEM).
    18. Antoinette Baujard & Herrade Igersheim, 2007. "Expérimentation du vote par note et du vote par approbation lors de l'élection présidentielle française du 22 avril 2007," Post-Print halshs-00337290, HAL.
    19. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2006. "Applications of Relations and Graphs to Coalition Formation," Coalition Theory Network Working Papers 12162, Fondazione Eni Enrico Mattei (FEEM).
    20. Agnieszka Rusinowska & Rudolf Berghammer & Harrie de Swart & Michel Grabisch, 2011. "Social networks: Prestige, centrality, and influence (Invited paper)," Post-Print hal-00633859, HAL.
    21. Eklund, Patrik & Rusinowska, Agnieszka & De Swart, Harrie, 2007. "Consensus reaching in committees," European Journal of Operational Research, Elsevier, vol. 178(1), pages 185-193, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:journl:halshs-00406460. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.