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

Computing tournament solutions using relation algebra and RelView

Author

Listed:
  • Rudolf Berghammer

    (Institut für Informatik - CAU - Christian-Albrechts-Universität zu Kiel = Christian-Albrechts University of Kiel = Université Christian-Albrechts de Kiel)

  • Agnieszka Rusinowska

    (CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique, PSE - Paris School of Economics - UP1 - Université Paris 1 Panthéon-Sorbonne - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris Sciences et Lettres - EHESS - École des hautes études en sciences sociales - ENPC - École des Ponts ParisTech - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement)

  • Harrie de Swart

    (Department of Philosophy - Erasmus University Rotterdam)

Abstract

We describe a simple computing technique for the tournament choice problem. It rests upon relational modeling and uses the BDD-based computer system RelView for the evaluation of the relation-algebraic expressions that specify the solutions and for the visualization of the computed results. The Copeland set can immediately be identified using RelView's labeling feature. Relation-algebraic specifications of the Condorcet non-losers, the Schwartz set, the top cycle, the uncovered set, the minimal covering set, the Banks set, and the tournament equilibrium set are delivered. We present an example of a tournament on a small set of alternatives, for which the above choice sets are computed and visualized via RelView. The technique described in this paper is very flexible and especially appropriate for prototyping and experimentation, and as such very instructive for educational purposes. It can easily be applied to other problems of social choice and game theory.

Suggested Citation

  • Rudolf Berghammer & Agnieszka Rusinowska & Harrie de Swart, 2013. "Computing tournament solutions using relation algebra and RelView," PSE-Ecole d'économie de Paris (Postprint) hal-00756696, HAL.
    • Handle: RePEc:hal:pseptp:hal-00756696
    DOI: 10.1016/j.ejor.2012.11.025
    Note: View the original document on HAL open archive server: https://hal.science/hal-00756696
    as

    Download full text from publisher

    File URL: https://hal.science/hal-00756696/document
    Download Restriction: no
    File URL: https://libkey.io/10.1016/j.ejor.2012.11.025?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, 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. Michel Grabisch & Agnieszka Rusinowska, 2010. "A model of influence in a social network," Theory and Decision, Springer, vol. 69(1), pages 69-96, July.
    3. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2009. "An interdisciplinary approach to coalition formation," European Journal of Operational Research, Elsevier, vol. 195(2), pages 487-496, June.
    4. Elizabeth Penn, 2006. "Alternate Definitions of the Uncovered Set and Their Implications," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 27(1), pages 83-87, August.
    5. Bolus, Stefan, 2011. "Power indices of simple games and vector-weighted majority games by means of binary decision diagrams," European Journal of Operational Research, Elsevier, vol. 210(2), pages 258-272, April.
    6. I. Good, 1971. "A note on condorcet sets," Public Choice, Springer, vol. 10(1), pages 97-101, March.
    7. Deb, Rajat, 1977. "On Schwartz's rule," Journal of Economic Theory, Elsevier, vol. 16(1), pages 103-110, October.
    8. Nicolas Houy, 2009. "Still more on the Tournament Equilibrium Set," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 32(1), pages 93-99, January.
    9. 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.
    10. Brandt, Felix & Fischer, Felix, 2008. "Computing the minimal covering set," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 254-268, September.
    11. 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.
    12. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    13. Dutta, Bhaskar, 1988. "Covering sets and a new condorcet choice correspondence," Journal of Economic Theory, Elsevier, vol. 44(1), pages 63-80, February.
    14. John Duggan, 2011. "Uncovered Sets," Wallis Working Papers WP63, University of Rochester - Wallis Institute of Political Economy.
    15. Smith, John H, 1973. "Aggregation of Preferences with Variable Electorate," Econometrica, Econometric Society, vol. 41(6), pages 1027-1041, November.
    16. 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. Andrea C. Hupman & Jay Simon, 2023. "The Legacy of Peter Fishburn: Foundational Work and Lasting Impact," Decision Analysis, INFORMS, vol. 20(1), pages 1-15, March.
    2. Berghammer, Rudolf & Schnoor, Henning, 2015. "Control of Condorcet voting: Complexity and a Relation-Algebraic approach," European Journal of Operational Research, Elsevier, vol. 246(2), pages 505-516.

    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. repec:hal:pseose:hal-00756696 is not listed on IDEAS
    2. repec:hal:wpaper:hal-00756696 is not listed on IDEAS
    3. Agnieszka Rusinowska & Rudolf Berghammer & Harrie de Swart & Michel Grabisch, 2011. "Social networks: Prestige, centrality, and influence (Invited paper)," Post-Print hal-00633859, HAL.
    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. 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.
    6. Fujun Hou, 2024. "A new social welfare function with a number of desirable properties," Papers 2403.16373, arXiv.org.
    7. 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.
    8. Brandt, Felix, 2011. "Minimal stable sets in tournaments," Journal of Economic Theory, Elsevier, vol. 146(4), pages 1481-1499, July.
    9. Felix Brandt & Markus Brill & Felix Fischer & Paul Harrenstein, 2014. "Minimal retentive sets in tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 551-574, March.
    10. Felix Brandt & Markus Brill & Hans Georg Seedig & Warut Suksompong, 2018. "On the structure of stable tournament solutions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(2), pages 483-507, March.
    11. Aleksei Y. Kondratev & Vladimir V. Mazalov, 2020. "Tournament solutions based on cooperative game theory," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 119-145, March.
    12. Costa, Matheus & Riella, Gil, 2022. "King-chicken choice correspondences," Mathematical Social Sciences, Elsevier, vol. 120(C), pages 113-118.
    13. Subochev, Andrey, 2008. "Dominant, weakly stable, uncovered sets: properties and extensions," MPRA Paper 53421, University Library of Munich, Germany.
    14. Daniel Carroll & Jim Dolmas & Eric Young, 2021. "The Politics of Flat Taxes," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 39, pages 174-201, January.
    15. Felix Brandt & Chris Dong, 2022. "On Locally Rationalizable Social Choice Functions," Papers 2204.05062, arXiv.org, revised Mar 2024.
    16. Raúl Pérez-Fernández & Bernard De Baets, 2019. "The superdominance relation, the positional winner, and more missing links between Borda and Condorcet," Journal of Theoretical Politics, , vol. 31(1), pages 46-65, January.
    17. Berghammer, Rudolf & Schnoor, Henning, 2015. "Control of Condorcet voting: Complexity and a Relation-Algebraic approach," European Journal of Operational Research, Elsevier, vol. 246(2), pages 505-516.
    18. Thomas Demuynck, 2014. "The computational complexity of rationalizing Pareto optimal choice behavior," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 529-549, March.
    19. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    20. Daniel R. Carroll & Jim Dolmas & Eric Young, 2015. "Majority Voting: A Quantitative Investigation," Working Papers (Old Series) 1442, Federal Reserve Bank of Cleveland.
    21. Vincent Anesi, 2012. "A new old solution for weak tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(4), pages 919-930, October.
    22. Joseph, Rémy-Robert, 2010. "Making choices with a binary relation: Relative choice axioms and transitive closures," European Journal of Operational Research, Elsevier, vol. 207(2), pages 865-877, December.

    More about this item

    Keywords

    Tournament; relational algebra; RelView; Copeland set; Condorcet non-losers; Schwartz set; top cycle; uncovered set; minimal covering set; Banks set; tournament equilibrium set;
    All these keywords.

    JEL classification:

    • D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
    • 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

    Statistics

    Access and download statistics

    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:pseptp:hal-00756696. 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: Caroline Bauer (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.