A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation
A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation
复制标题
DOI：
10.1287/deca.2021.0433
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Yeawon Yoo;Adolfo R. Escobedo
中科院分区：
文献类型：
--
作者：
Yeawon Yoo;Adolfo R. Escobedo
等级聚合被广泛应用于群体决策和许多其他应用中，这些应用对整合异构有序列表很感兴趣。通常，这些排名可能涉及大量的选择，包含联系，和/或不完整，所有这些都使健壮的聚合方法的使用复杂化。特别是，这些特征限制了基于Kemeny-Snell距离的聚合框架的适用性，该框架满足已被证明可以产生改进决策的关键社会选择属性。本文介绍了广义Kemeny排序聚合问题的二进制规划公式，该问题的排序输入可以是完全的，也可以是不完全的，有和没有联系。此外，它利用两个排序聚合问题的等价性，即最小化Kemeny-Snell距离和最大化Kendall-τ相关性，将新引入的二进制规划公式与与Kendall-τ距离相关的现有整数规划公式的修改版本进行比较。新的公式有更少的变量和约束，这导致更快的解决时间。此外，我们还提出了一种新的社会选择性质——非严格扩展孔多塞准则，它可以看作是众所周知的孔多塞准则和扩展孔多塞准则的自然扩展。与其父属性不同，新属性足以处理带有关系的完整排名。利用该特性开发了一种结构分解算法，通过该算法可以在实际时间内精确地解决NP-hard Kemeny秩聚集问题的某些大型实例。为了测试新公式和社会选择属性的实际含义，我们使用了从概率分布构建的实例和来自PrefLib（偏好数据库）的基准实例。
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.