IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v281y2020i2p388-401.html
   My bibliography  Save this article

A new approach for identifying the Kemeny median ranking

Author

Listed:
  • Azzini, Ivano
  • Munda, Giuseppe

Abstract

Condorcet consistent rules were originally developed for preference aggregation in the theory of social choice. Nowadays these rules are applied in a variety of fields such as discrete multi-criteria analysis, defence and security decision support, composite indicators, machine learning, artificial intelligence, queries in databases or internet multiple search engines and theoretical computer science. The cycle issue, known also as Condorcet's paradox, is the most serious problem inherent in this type of rules. Solutions for dealing with the cycle issue properly already exist in the literature; the most important one being the identification of the median ranking, often called the Kemeny ranking. Unfortunately its identification is a NP-hard problem. This article has three main objectives: (1) to clarify that the Kemeny median order has to be framed in the context of Condorcet consistent rules; this is important since in the current practice sometimes even the Borda count is used as a proxy for the Kemeny ranking. (2) To present a new exact algorithm, this identifies the Kemeny median ranking by providing a searching time guarantee. (3) To present a new heuristic algorithm identifying the Kemeny median ranking with an optimal trade-off between convergence and approximation.

Suggested Citation

  • Azzini, Ivano & Munda, Giuseppe, 2020. "A new approach for identifying the Kemeny median ranking," European Journal of Operational Research, Elsevier, vol. 281(2), pages 388-401.
    • Handle: RePEc:eee:ejores:v:281:y:2020:i:2:p:388-401
    DOI: 10.1016/j.ejor.2019.08.033
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719307039
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.08.033?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Truchon M., 1996. "Voting games and acyclic collective choice rules," Mathematical Social Sciences, Elsevier, vol. 31(1), pages 55-55, February.
    2. Cook, Wade D., 2006. "Distance-based and ad hoc consensus models in ordinal preference ranking," European Journal of Operational Research, Elsevier, vol. 172(2), pages 369-385, July.
    3. Laurent Vidu, 2002. "Majority cycles in a multi-dimensional setting," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 20(2), pages 373-386.
    4. Barthelemy, J. P. & Guenoche, A. & Hudry, O., 1989. "Median linear orders: Heuristics and a branch and bound algorithm," European Journal of Operational Research, Elsevier, vol. 42(3), pages 313-325, October.
    5. Young, H. P., 1988. "Condorcet's Theory of Voting," American Political Science Review, Cambridge University Press, vol. 82(4), pages 1231-1244, December.
    6. Ali, Alnur & Meilă, Marina, 2012. "Experiments with Kemeny ranking: What works when?," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 28-40.
    7. Giuseppe Munda, 2012. "Intensity of preference and related uncertainty in non-compensatory aggregation rules," Theory and Decision, Springer, vol. 73(4), pages 649-669, October.
    8. Laurent Vidu, 2002. "Majority cycles in a multi-dimensional setting," Post-Print halshs-00069541, HAL.
    9. Peyton Young, 1995. "Optimal Voting Rules," Journal of Economic Perspectives, American Economic Association, vol. 9(1), pages 51-64, Winter.
    10. Giuseppe Munda & Michela Nardo, 2009. "Noncompensatory/nonlinear composite indicators for ranking countries: a defensible setting," Applied Economics, Taylor & Francis Journals, vol. 41(12), pages 1513-1523.
    11. Jairo Cugliari & Antoine Rolland, 2018. "Simulation of multicriteria data," EURO Journal on Decision Processes, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 21-37, June.
    12. Kenneth J. Arrow & Herve Raynaud, 1986. "Social Choice and Multicriterion Decision-Making," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262511754, April.
    13. Ceberio, Josu & Mendiburu, Alexander & Lozano, Jose A., 2015. "The linear ordering problem revisited," European Journal of Operational Research, Elsevier, vol. 241(3), pages 686-696.
    14. Amodio, S. & D’Ambrosio, A. & Siciliano, R., 2016. "Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach," European Journal of Operational Research, Elsevier, vol. 249(2), pages 667-676.
    15. Moulin, Herve, 1985. "From social welfare ordering to acyclic aggregation of preferences," Mathematical Social Sciences, Elsevier, vol. 9(1), pages 1-17, February.
    16. James S. Weber, 2002. "How many voters are needed for paradoxes?," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 20(2), pages 341-355.
    17. Truchon, M., 1998. "Figure Skating and the Theory of Social Choice," Papers 9814, Laval - Recherche en Politique Economique.
    18. Giuseppe Munda, 2008. "Social Multi-Criteria Evaluation for a Sustainable Economy," Springer Books, Springer, number 978-3-540-73703-2, January.
    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. Noelia Rico & Camino R. Vela & Raúl Pérez-Fernández & Irene Díaz, 2021. "Reducing the Computational Time for the Kemeny Method by Exploiting Condorcet Properties," Mathematics, MDPI, vol. 9(12), pages 1-12, June.
    2. Akbari, Sina & Escobedo, Adolfo R., 2023. "Beyond kemeny rank aggregation: A parameterizable-penalty framework for robust ranking aggregation with ties," Omega, Elsevier, vol. 119(C).
    3. Giuseppe Munda, 2022. "Qualitative reasoning or quantitative aggregation rules for impact assessment of policy options? A multiple criteria framework," Quality & Quantity: International Journal of Methodology, Springer, vol. 56(5), pages 3259-3277, October.
    4. Rico, Noelia & Vela, Camino R. & Díaz, Irene, 2023. "Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1323-1336.

    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. Giuseppe Munda, 2012. "Choosing Aggregation Rules for Composite Indicators," Social Indicators Research: An International and Interdisciplinary Journal for Quality-of-Life Measurement, Springer, vol. 109(3), pages 337-354, December.
    2. Munda, Giuseppe, 2009. "A conflict analysis approach for illuminating distributional issues in sustainability policy," European Journal of Operational Research, Elsevier, vol. 194(1), pages 307-322, April.
    3. Giuseppe Munda, 2015. "Beyond Gdp: An Overview Of Measurement Issues In Redefining ‘Wealth’," Journal of Economic Surveys, Wiley Blackwell, vol. 29(3), pages 403-422, July.
    4. Giuseppe Munda, 2022. "Qualitative reasoning or quantitative aggregation rules for impact assessment of policy options? A multiple criteria framework," Quality & Quantity: International Journal of Methodology, Springer, vol. 56(5), pages 3259-3277, October.
    5. Truchon, Michel, 1999. "La démocratie : oui, mais laquelle?," L'Actualité Economique, Société Canadienne de Science Economique, vol. 75(1), pages 189-214, mars-juin.
    6. Noelia Rico & Camino R. Vela & Raúl Pérez-Fernández & Irene Díaz, 2021. "Reducing the Computational Time for the Kemeny Method by Exploiting Condorcet Properties," Mathematics, MDPI, vol. 9(12), pages 1-12, June.
    7. Rico, Noelia & Vela, Camino R. & Díaz, Irene, 2023. "Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1323-1336.
    8. Yoo, Yeawon & Escobedo, Adolfo R. & Skolfield, J. Kyle, 2020. "A new correlation coefficient for comparing and aggregating non-strict and incomplete rankings," European Journal of Operational Research, Elsevier, vol. 285(3), pages 1025-1041.
    9. Tommaso Agasisti & Giuseppe Munda & Ralph Hippe, 2019. "Measuring the efficiency of European education systems by combining Data Envelopment Analysis and Multiple-Criteria Evaluation," Journal of Productivity Analysis, Springer, vol. 51(2), pages 105-124, June.
    10. Fujun Hou, 2024. "A new social welfare function with a number of desirable properties," Papers 2403.16373, arXiv.org.
    11. Truchon, Michel & Gordon, Stephen, 2009. "Statistical comparison of aggregation rules for votes," Mathematical Social Sciences, Elsevier, vol. 57(2), pages 199-212, March.
    12. Yeawon Yoo & Adolfo R. Escobedo, 2021. "A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation," Decision Analysis, INFORMS, vol. 18(4), pages 296-320, December.
    13. Salvatore Greco & Alessio Ishizaka & Menelaos Tasiou & Gianpiero Torrisi, 2019. "On the Methodological Framework of Composite Indices: A Review of the Issues of Weighting, Aggregation, and Robustness," Social Indicators Research: An International and Interdisciplinary Journal for Quality-of-Life Measurement, Springer, vol. 141(1), pages 61-94, January.
    14. Giuseppe Munda, 2012. "Intensity of preference and related uncertainty in non-compensatory aggregation rules," Theory and Decision, Springer, vol. 73(4), pages 649-669, October.
    15. Lozano-Oyola, Macarena & Contreras, Ignacio & Blancas, Francisco Javier, 2019. "An Operational Non-compensatory Composite Indicator: Measuring Sustainable Tourism in Andalusian Urban Destinations," Ecological Economics, Elsevier, vol. 159(C), pages 1-10.
    16. Truchon, Michel, 1998. "Figure Skating and the Theory of Social Choice," Cahiers de recherche 9814, Université Laval - Département d'économique.
    17. William Gehrlein, 2002. "Condorcet's paradox and the likelihood of its occurrence: different perspectives on balanced preferences ," Theory and Decision, Springer, vol. 52(2), pages 171-199, March.
    18. Stephen Gordon & Michel Truchon, 2008. "Social choice, optimal inference and figure skating," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 30(2), pages 265-284, February.
    19. Andrea Aveni & Ludovico Crippa & Giulio Principi, 2024. "On the Weighted Top-Difference Distance: Axioms, Aggregation, and Approximation," Papers 2403.15198, arXiv.org, revised Mar 2024.
    20. Nehring, Klaus & Pivato, Marcus & Puppe, Clemens, 2011. "Condorcet admissibility: Indeterminacy and path-dependence under majority voting on interconnected decisions," MPRA Paper 32434, University Library of Munich, Germany.

    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:eee:ejores:v:281:y:2020:i:2:p:388-401. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.