[go: up one dir, main page]

IDEAS home Printed from https://ideas.repec.org/a/inm/ordeca/v18y2021i4p296-320.html
   My bibliography  Save this article

A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation

Author

Listed:
  • Yeawon Yoo

    (Department of Applied Mathematics and Statistics, SNF Agora Institute, Johns Hopkins University, Baltimore, Maryland 21218)

  • Adolfo R. Escobedo

    (School of Computing and Augmented Intelligence, Arizona State University, Tempe, Arizona 85281)

Abstract
Rank aggregation is widely used in group decision making and many other applications, where it is of interest to consolidate heterogeneous ordered lists. Oftentimes, these rankings may involve a large number of alternatives, contain ties, and/or be incomplete, all of which complicate the use of robust aggregation methods. In particular, these characteristics have limited the applicability of the aggregation framework based on the Kemeny-Snell distance, which satisfies key social choice properties that have been shown to engender improved decisions. This work introduces a binary programming formulation for the generalized Kemeny rank aggregation problem—whose ranking inputs may be complete and incomplete, with and without ties. Moreover, it leverages the equivalence of two ranking aggregation problems, namely, that of minimizing the Kemeny-Snell distance and of maximizing the Kendall- τ correlation, to compare the newly introduced binary programming formulation to a modified version of an existing integer programming formulation associated with the Kendall- τ distance. The new formulation has fewer variables and constraints, which leads to faster solution times. Moreover, we develop a new social choice property, the nonstrict extended Condorcet criterion, which can be regarded as a natural extension of the well-known Condorcet criterion and the Extended Condorcet criterion. Unlike its parent properties, the new property is adequate for handling complete rankings with ties. The property is leveraged to develop a structural decomposition algorithm, through which certain large instances of the NP-hard Kemeny rank aggregation problem can be solved exactly in a practical amount of time. To test the practical implications of the new formulation and social choice property, we work with instances constructed from a probabilistic distribution and with benchmark instances from PrefLib, a library of preference data.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:ordeca:v:18:y:2021:i:4:p:296-320
    DOI: 10.1287/deca.2021.0433
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/deca.2021.0433
    Download Restriction: no

    File URL: https://libkey.io/10.1287/deca.2021.0433?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
    ---><---

    References listed on IDEAS

    as
    1. Wade D. Cook & Lawrence M. Seiford, 1978. "Priority Ranking and Consensus Formation," Management Science, INFORMS, vol. 24(16), pages 1721-1732, December.
    2. Noah Streib & Stephen J. Young & Joel Sokol, 2012. "A Major League Baseball Team Uses Operations Research to Improve Draft Preparation," Interfaces, INFORMS, vol. 42(2), pages 119-130, April.
    3. Michael Dummett, 1998. "The Borda count and agenda manipulation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 15(2), pages 289-296.
    4. Per Ahlgren & Bo Jarneving & Ronald Rousseau, 2003. "Requirements for a cocitation similarity measure, with special reference to Pearson's correlation coefficient," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 54(6), pages 550-560, April.
    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. Pierre Favardin & Dominique Lepelley & Jérôme Serais, 2002. "Borda rule, Copeland method and strategic manipulation," Post-Print halshs-00069522, HAL.
    7. Smith, John H, 1973. "Aggregation of Preferences with Variable Electorate," Econometrica, Econometric Society, vol. 41(6), pages 1027-1041, November.
    8. Wade D. Cook & Tal Raviv & Alan J. Richardson, 2010. "Aggregating Incomplete Lists of Journal Rankings: An Application to Academic Accounting Journals," Accounting Perspectives, John Wiley & Sons, vol. 9(3), pages 217-235, September.
    9. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    10. Scott Feld & Bernard Grofman, 1988. "The Borda count in n-dimensional issue space," Public Choice, Springer, vol. 59(2), pages 167-176, November.
    11. Irurozki, Ekhine & Calvo, Borja & Lozano, Jose A., 2016. "PerMallows: An R Package for Mallows and Generalized Mallows Models," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 71(i12).
    12. Jeffrey Keisler, 2004. "Value of Information in Portfolio Decision Analysis," Decision Analysis, INFORMS, vol. 1(3), pages 177-189, September.
    13. Pierre Favardin & Dominique Lepelley & Jérôme Serais, 2002. "original papers : Borda rule, Copeland method and strategic manipulation," Review of Economic Design, Springer;Society for Economic Design, vol. 7(2), pages 213-228.
    14. Robert E. Goodin & Christian List, 2006. "A Conditional Defense of Plurality Rule: Generalizing May's Theorem in a Restricted Informational Environment," American Journal of Political Science, John Wiley & Sons, vol. 50(4), pages 940-949, October.
    15. Erick Moreno-Centeno & Adolfo R. Escobedo, 2016. "Axiomatic aggregation of incomplete rankings," IISE Transactions, Taylor & Francis Journals, vol. 48(6), pages 475-488, June.
    16. Martin S. Schilling & Nadine Oeser & Cornelius Schaub, 2007. "How Effective Are Decision Analyses? Assessing Decision Process and Group Alignment Effects," Decision Analysis, INFORMS, vol. 4(4), pages 227-242, December.
    17. Jean-Paul Doignon & Aleksandar Pekeč & Michel Regenwetter, 2004. "The repeated insertion model for rankings: Missing link between two subset choice models," Psychometrika, Springer;The Psychometric Society, vol. 69(1), pages 33-54, March.
    18. Josu Ceberio & Ekhine Irurozki & Alexander Mendiburu & Jose Lozano, 2015. "A review of distances for the Mallows and Generalized Mallows estimation of distribution algorithms," Computational Optimization and Applications, Springer, vol. 62(2), pages 545-564, November.
    19. Peyton Young, 1995. "Optimal Voting Rules," Journal of Economic Perspectives, American Economic Association, vol. 9(1), pages 51-64, Winter.
    20. 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.
    21. 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.
    22. Willem Heiser, 2004. "Geometric representation of association between categories," Psychometrika, Springer;The Psychometric Society, vol. 69(4), pages 513-545, December.
    23. Wade D. Cook & Moshe Kress, 1985. "Ordinal Ranking with Intensity of Preference," Management Science, INFORMS, vol. 31(1), pages 26-32, 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. Francisco Salas-Molina & Filippo Bistaffa & Juan A. Rodriguez-Aguilar, 2024. "A General Approach for Computing a Consensus in Group Decision Making That Integrates Multiple Ethical Principles," Papers 2401.07818, arXiv.org, revised Mar 2024.
    2. Nathan Atkinson & Scott C. Ganz & Dorit S. Hochbaum & James B. Orlin, 2023. "The Strong Maximum Circulation Algorithm: A New Method for Aggregating Preference Rankings," Papers 2307.15702, arXiv.org, revised Oct 2024.
    3. 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).
    4. Yangming Zhou & Jin-Kao Hao & Zhen Li, 2024. "Heuristic Search for Rank Aggregation with Application to Label Ranking," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 308-326, March.
    5. 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.
    6. Adolfo R. Escobedo & Romena Yasmin, 2023. "Derivations of large classes of facet defining inequalities of the weak order polytope using ranking structures," Journal of Combinatorial Optimization, Springer, vol. 46(3), pages 1-45, October.
    7. Salas-Molina, Francisco & Bistaffa, Filippo & Rodríguez-Aguilar, Juan A., 2023. "A general approach for computing a consensus in group decision making that integrates multiple ethical principles," Socio-Economic Planning Sciences, Elsevier, vol. 89(C).
    8. Fu, Yelin & Lu, Yihe & Yu, Chen & Lai, Kin Keung, 2022. "Inter-country comparisons of energy system performance with the energy trilemma index: An ensemble ranking methodology based on the half-quadratic theory," Energy, Elsevier, vol. 261(PA).

    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. 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).
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Fujun Hou, 2024. "A new social welfare function with a number of desirable properties," Papers 2403.16373, arXiv.org.
    8. Hiroki Nishimura & Efe A. Ok, 2022. "A class of dissimilarity semimetrics for preference relations," Papers 2203.04418, arXiv.org.
    9. 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.
    10. Green-Armytage, James, 2011. "Strategic voting and nomination," MPRA Paper 32200, University Library of Munich, Germany.
    11. Federica Ceron & Stéphane Gonzalez, 2019. "A characterization of Approval Voting without the approval balloting assumption," Working Papers halshs-02440615, HAL.
    12. Jabeur, Khaled & Martel, Jean-Marc, 2007. "A collective choice method based on individual preferences relational systems (p.r.s.)," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1549-1565, March.
    13. Qi Wei & Rui Wang & Chuan-Yang Ruan, 2024. "Similarity Measures of Probabilistic Interval Preference Ordering Sets and Their Applications in Decision-Making," Mathematics, MDPI, vol. 12(20), pages 1-26, October.
    14. Aki Lehtinen, 2007. "The Borda rule is also intended for dishonest men," Public Choice, Springer, vol. 133(1), pages 73-90, October.
    15. Burka, Dávid & Puppe, Clemens & Szepesváry, László & Tasnádi, Attila, 2022. "Voting: A machine learning approach," European Journal of Operational Research, Elsevier, vol. 299(3), pages 1003-1017.
    16. 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.
    17. 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.
    18. J González-Pachón & C Romero, 2006. "An analytical framework for aggregating multiattribute utility functions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(10), pages 1241-1247, October.
    19. Marcus Pivato, 2013. "Voting rules as statistical estimators," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(2), pages 581-630, February.
    20. Diss, Mostapha & Tsvelikhovskiy, Boris, 2021. "Manipulable outcomes within the class of scoring voting rules," Mathematical Social Sciences, Elsevier, vol. 111(C), pages 11-18.

    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:inm:ordeca:v:18:y:2021:i:4:p:296-320. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.