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

Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach

Author

Listed:
  • Amodio, S.
  • D’Ambrosio, A.
  • Siciliano, R.

Abstract

Preference rankings virtually appear in all fields of science (political sciences, behavioral sciences, machine learning, decision making and so on). The well-known social choice problem consists in trying to find a reasonable procedure to use the aggregate preferences or rankings expressed by subjects to reach a collective decision. This turns out to be equivalent to estimate the consensus (central) ranking from data and it is known to be a NP-hard problem. A useful solution has been proposed by Emond and Mason in 2002 through the Branch-and-Bound algorithm (BB) within the Kemeny and Snell axiomatic framework. As a matter of fact, BB is a time demanding procedure when the complexity of the problem becomes untractable, i.e. a large number of objects, with weak and partial rankings, in presence of a low degree of consensus. As an alternative, we propose an accurate heuristic algorithm called FAST that finds at least one of the consensus ranking solutions found by BB saving a lot of computational time. In addition, we show that the building block of FAST is an algorithm called QUICK that finds already one of the BB solutions so that it can be fruitfully considered to speed up even more the overall searching procedure if the number of objects is low. Simulation studies and applications on real data allows to show the accuracy and the computational efficiency of our proposal.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:249:y:2016:i:2:p:667-676
    DOI: 10.1016/j.ejor.2015.08.048
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715008048
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.08.048?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. Antonio D’Ambrosio & Massimo Aria & Roberta Siciliano, 2012. "Accurate Tree-based Missing Data Imputation and Data Fusion within the Statistical Learning Paradigm," Journal of Classification, Springer;The Classification Society, vol. 29(2), pages 227-258, July.
    2. Wade D. Cook & Lawrence M. Seiford, 1978. "Priority Ranking and Consensus Formation," Management Science, INFORMS, vol. 24(16), pages 1721-1732, December.
    3. Cook, Wade D. & Kress, Moshe & Seiford, Lawrence M., 1997. "A general framework for distance-based consensus in ordinal ranking models," European Journal of Operational Research, Elsevier, vol. 96(2), pages 392-397, January.
    4. Pierre Barthelemy, Jean & Monjardet, Bernard, 1981. "The median procedure in cluster analysis and social choice theory," Mathematical Social Sciences, Elsevier, vol. 1(3), pages 235-267, May.
    5. 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.
    6. Siciliano, Roberta & Mola, Francesco, 2000. "Multivariate data analysis and modeling through classification and regression trees," Computational Statistics & Data Analysis, Elsevier, vol. 32(3-4), pages 285-301, January.
    7. Willem Heiser, 2004. "Geometric representation of association between categories," Psychometrika, Springer;The Psychometric Society, vol. 69(4), pages 513-545, December.
    8. Murphy, Thomas Brendan & Martin, Donal, 2003. "Mixtures of distance-based models for ranking data," Computational Statistics & Data Analysis, Elsevier, vol. 41(3-4), pages 645-655, January.
    9. Davis, Otto A & DeGroot, Morris H & Hinich, Melvin J, 1972. "Social Preference Orderings and Majority Rule," Econometrica, Econometric Society, vol. 40(1), pages 147-157, 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. Antonella Plaia & Simona Buscemi & Mariangela Sciandra, 2021. "Consensus among preference rankings: a new weighted correlation coefficient for linear and weak orderings," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 15(4), pages 1015-1037, December.
    2. Cascón, J.M. & González-Arteaga, T. & de Andrés Calle, R., 2022. "A new preference classification approach: The λ-dissensus cluster algorithm," Omega, Elsevier, vol. 111(C).
    3. 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.
    4. Antonio D’Ambrosio & Carmela Iorio & Michele Staiano & Roberta Siciliano, 2019. "Median constrained bucket order rank aggregation," Computational Statistics, Springer, vol. 34(2), pages 787-802, June.
    5. Carmela Iorio & Giuseppe Pandolfo & Antonio D’Ambrosio & Roberta Siciliano, 2020. "Mining big data in tourism," Quality & Quantity: International Journal of Methodology, Springer, vol. 54(5), pages 1655-1669, December.
    6. 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.
    7. Antonella Plaia & Mariangela Sciandra, 2019. "Weighted distance-based trees for ranking data," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 13(2), pages 427-444, June.
    8. Antonella Plaia & Simona Buscemi & Johannes Fürnkranz & Eneldo Loza Mencía, 2022. "Comparing Boosting and Bagging for Decision Trees of Rankings," Journal of Classification, Springer;The Classification Society, vol. 39(1), pages 78-99, March.
    9. 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.
    10. Antonio D’Ambrosio & Willem J. Heiser, 2016. "A Recursive Partitioning Method for the Prediction of Preference Rankings Based Upon Kemeny Distances," Psychometrika, Springer;The Psychometric Society, vol. 81(3), pages 774-794, September.
    11. 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.
    12. 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.

    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. Fujun Hou, 2015. "A Consensus Gap Indicator and Its Application to Group Decision Making," Group Decision and Negotiation, Springer, vol. 24(3), pages 415-428, May.
    2. Antonio D’Ambrosio & Carmela Iorio & Michele Staiano & Roberta Siciliano, 2019. "Median constrained bucket order rank aggregation," Computational Statistics, Springer, vol. 34(2), pages 787-802, June.
    3. 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.
    4. Antonio D’Ambrosio & Willem J. Heiser, 2016. "A Recursive Partitioning Method for the Prediction of Preference Rankings Based Upon Kemeny Distances," Psychometrika, Springer;The Psychometric Society, vol. 81(3), pages 774-794, September.
    5. Yeşilçimen, Ali & Yıldırım, E. Alper, 2019. "An alternative polynomial-sized formulation and an optimization based heuristic for the reviewer assignment problem," European Journal of Operational Research, Elsevier, vol. 276(2), pages 436-450.
    6. Jabeur, Khaled & Martel, Jean-Marc, 2007. "An ordinal sorting method for group decision-making," European Journal of Operational Research, Elsevier, vol. 180(3), pages 1272-1289, August.
    7. Hanna Bury & Dariusz Wagner, 2009. "Group judgement with ties. A position-based approach," Operations Research and Decisions, Wroclaw University of Technology, Institute of Organization and Management, vol. 4, pages 9-26.
    8. Cook, Wade D. & Kress, Moshe & Seiford, Lawrence M., 1997. "A general framework for distance-based consensus in ordinal ranking models," European Journal of Operational Research, Elsevier, vol. 96(2), pages 392-397, January.
    9. Yucheng Dong & Yao Li & Ying He & Xia Chen, 2021. "Preference–Approval Structures in Group Decision Making: Axiomatic Distance and Aggregation," Decision Analysis, INFORMS, vol. 18(4), pages 273-295, December.
    10. Bowen Zhang & Yucheng Dong & Enrique Herrera-Viedma, 2019. "Group Decision Making with Heterogeneous Preference Structures: An Automatic Mechanism to Support Consensus Reaching," Group Decision and Negotiation, Springer, vol. 28(3), pages 585-617, June.
    11. Hiroki Nishimura & Efe A. Ok, 2022. "A class of dissimilarity semimetrics for preference relations," Papers 2203.04418, arXiv.org.
    12. Gong, Zaiwu & Xu, Xiaoxia & Zhang, Huanhuan & Aytun Ozturk, U. & Herrera-Viedma, Enrique & Xu, Chao, 2015. "The consensus models with interval preference opinions and their economic interpretation," Omega, Elsevier, vol. 55(C), pages 81-90.
    13. Roberta Siciliano & Antonio D’Ambrosio & Massimo Aria & Sonia Amodio, 2017. "Analysis of Web Visit Histories, Part II: Predicting Navigation by Nested STUMP Regression Trees," Journal of Classification, Springer;The Classification Society, vol. 34(3), pages 473-493, October.
    14. Fujun Hou, 2018. "Mutual Conversion Between Preference Maps And Cook-Seiford Vectors," Papers 1812.03566, arXiv.org.
    15. Hanna Bury & Dariusz Wagner, 2009. "Group judgment with ties. A position-based approach," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 19(4), pages 7-26.
    16. Akram Dehnokhalaji & Pekka J. Korhonen & Murat Köksalan & Nasim Nasrabadi & Diclehan Tezcaner Öztürk & Jyrki Wallenius, 2014. "Constructing a strict total order for alternatives characterized by multiple criteria: An extension," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(2), pages 155-163, March.
    17. Hou, Fujun & Triantaphyllou, Evangelos, 2019. "An iterative approach for achieving consensus when ranking a finite set of alternatives by a group of experts," European Journal of Operational Research, Elsevier, vol. 275(2), pages 570-579.
    18. Ignacio Contreras, 2010. "A Distance-Based Consensus Model with Flexible Choice of Rank-Position Weights," Group Decision and Negotiation, Springer, vol. 19(5), pages 441-456, September.
    19. Fujun Hou, 2016. "The Prametric-Based GDM Procedure Under Fuzzy Environment," Group Decision and Negotiation, Springer, vol. 25(5), pages 1071-1084, September.
    20. Ivan Miguel Pires & Faisal Hussain & Nuno M. Garcia & Eftim Zdravevski, 2020. "Improving Human Activity Monitoring by Imputation of Missing Sensory Data: Experimental Study," Future Internet, MDPI, vol. 12(9), pages 1-18, September.

    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:249:y:2016:i:2:p:667-676. 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.