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

Yeawon Yoo () and Adolfo R. Escobedo ()
Additional contact information
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

Decision Analysis, 2021, vol. 18, issue 4, 296-320

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.

Keywords: group decision making; rank aggregation; computational social choice; combinatorial optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/deca.2021.0433 (application/pdf)

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:inm:ordeca:v:18:y:2021:i:4:p:296-320

Access Statistics for this article

More articles in Decision Analysis from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().