Beyond kemeny rank aggregation: A parameterizable-penalty framework for robust ranking aggregation with ties

Sina Akbari and Adolfo R. Escobedo

Omega, 2023, vol. 119, issue C

Abstract: Rank Aggregation has ubiquitous applications in operations research, artificial intelligence, computational social choice, and various other fields. Interest in this problem has increased due in part to the need to consolidate lists of rankings and scores output by different decision-making processes and algorithms. Although most attention has focused on the variant of this problem induced by the Kemeny-Snell distance, other robust rank aggregation problems have been proposed. This work delves into the rank aggregation problem under the generalized Kendall-tau distance —a parameterizable-penalty distance measure for comparing rankings with ties— which contains Kemeny aggregation as a special case. First, it derives exact and heuristic solution methods. Second, it introduces a social choice property (GXCC) that encloses existing variations of the Condorcet criterion as special cases, thereby expanding this seminal social choice concept beyond Kemeny aggregation for the first time. GXCC offers both computational and theoretical advantages. In particular, GXCC may help to divide the original problem into smaller subproblems, while still ensuring that solving them independently yields the optimal solution to the original problem. Experiments on two benchmark datasets conducted herein show that the featured exact and heuristic solution methods can benefit from GXCC. Finally, this work derives new theoretical insights into the effects of the generalized Kendall-tau distance penalty parameter on the optimal ranking and on the proposed social choice property.

Keywords: Decision making/process; Rank aggregation; Kemeny aggregation; Kendall-tau distance; Condorcet criterion; Computational social choice (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048323000579
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:119:y:2023:i:c:s0305048323000579

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2023.102893

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().