Optimization Online


A new binary programming formulation and social choice property for expediting the solution to Kemeny ranking aggregation

Yeawon Yoo(yyoo12***at***asu.edu)
Adolfo Escobedo(adRes***at***asu.edu)

Abstract: We introduce a binary programming formulation for general Kemeny ranking aggregation---for complete and incomplete rankings with and without ties---and compare it to a modified version of a recently developed integer programming formulation for the generalized Kendall-tau distance. Our new formulation provides comparative advantages including reduced memory requirements and computing times when solving large size problems. Moreover, we develop a new social choice property for group decision-making, called the Generalized 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 Generalized Condorcet criterion is adequate for complete and incomplete rankings with and without ties. This property allows a simplification of the exact solution process for certain very large instances of the NP-hard Kemeny ranking aggregation problem. To test the practical implications of the new formulation and property, we work with randomized instances from probabilistic distributions and real-world data.

Keywords: Group decision-making; Ranking aggregation; Computational social choice, Integer programming formulation; Condorcet criterion

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Category 3: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 11/19/2018
Entry Accepted: 11/19/2018
Entry Last Modified: 11/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society