Beyond Kemeny Rank Aggregation: A Parameterizable-penalty Framework for Robust Ranking Aggregation with Ties

Beyond Kemeny Rank Aggregation: A Parameterizable-penalty Framework for Robust Ranking Aggregation with Ties
复制标题

DOI：
10.1016/j.omega.2023.102893
复制
发表时间：
2023-05
期刊：
Omega
影响因子：
--
通讯作者：
S. Akbari;Adolfo R. Escobedo
S. Akbari;Adolfo R. Escobedo
中科院分区：
其他
文献类型：
--
作者：
S. Akbari;Adolfo R. Escobedo

文献摘要

相似文献

秩聚合在运筹学、人工智能、计算社会选择和其他各种领域都有广泛的应用。对这个问题的兴趣已经增加，部分原因是需要合并不同决策过程和算法输出的排名和分数列表。虽然大多数注意力都集中在这个问题的变体引起的Kemeny-Snell距离，其他强大的秩聚合问题已被提出。这项工作深入研究的秩聚合问题下的广义Kendall-tau距离-一个参数化的惩罚距离测量比较排名与领带-其中包含Kemeny聚合作为一个特殊情况。首先，它推导出精确的和启发式的解决方法。其次，它引入了一个社会选择属性（GXCC），将孔多塞标准的现有变化作为特例，从而首次将这一开创性的社会选择概念扩展到Kemeny聚合之外。GXCC提供了计算和理论上的优势。特别是，GXCC可以帮助将原始问题划分为更小的子问题，同时仍然确保独立求解它们会产生原始问题的最优解。本文在两个基准数据集上进行的实验表明，精确和启发式求解方法可以从GXCC中受益。最后，这项工作得出了新的理论见解的影响，广义肯德尔-τ距离惩罚参数的最佳排名和建议的社会选择属性。
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.