Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach

DOI10.1016/J.EJOR.2015.08.048zbMATH Open1346.91065arXiv1502.06498OpenAlexW1437742013MaRDI QIDQ62323FDOQ62323

R. Siciliano, S. Amodio, A. D'Ambrosio

Publication date: March 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: Preference rankings virtually appear in all field of science (political sciences, behavioral sciences, machine learning, decision making and so on). The well-know social choice problem consists in trying to find a reasonable procedure to use the aggregate preferences expressed by subjects (usually called judges) to reach a collective decision. This problem turns out to be equivalent to the problem of estimating the consensus (central) ranking from data that is known to be a NP-hard Problem. Emond and Mason in 2002 proposed a branch and bound algorithm to calculate the consensus ranking given $n$ rankings expressed on $m$ objects. Depending on the complexity of the problem, there can be multiple solutions and then the consensus ranking may be not unique. We propose a new algorithm to find the consensus ranking that is equivalent to Emond and Mason's algorithm in terms of at least one of the solutions reached, but permits a really remarkable saving in computational time.

Full work available at URL: https://arxiv.org/abs/1502.06498

zbMATH Keywords

branch-and-bound algorithmKemeny distancemedian rankingpreference rankingssocial choice problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Applications of mathematical programming (90C90) Individual preferences (91B08)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metric methods for analyzing partially ranked data
• The median procedure in cluster analysis and social choice theory
• Probability models on rankings
• A general framework for distance-based consensus in ordinal ranking models
• Generalized permutation polytopes and exploratory graphical methods for ranked data
• Multivariate data analysis and modeling through classification and regression trees
• Geometric representation of association between categories
• Distance-based and ad hoc consensus models in ordinal preference ranking
• Accurate tree-based missing data imputation and data fusion within the statistical learning paradigm
• Social choice and individual values
• A recursive partitioning method for the prediction of preference rankings based upon Kemeny distances
• Preferential Arrangements
• Priority Ranking and Consensus Formation
• Preference structures I: Distances between transitive preference relations†
• Preference Structures. II: Distances Between Asymmetric Relations
• A new rank correlation coefficient with application to the consensus ranking problem
• Social Preference Orderings and Majority Rule
• Multistage Ranking Models
• A NEW MEASURE OF RANK CORRELATION
• Creating a consensus ranking of proposals from reviewers' partial ordinal rankings
• Mixtures of distance-based models for ranking data

Cited In (21)

• Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner
• Bayesian taut splines for estimating the number of modes
• Weighted distance-based trees for ranking data
• A new approach for identifying the Kemeny median ranking
• A New Binary Programming Formulation and Social Choice Property for Kemeny Rank Aggregation
• Approaching rank aggregation problems by using evolution strategies: the case of the optimal bucket order problem
• A new correlation coefficient for comparing and aggregating non-strict and incomplete rankings
• Fixed-parameter algorithms for Kemeny rankings
• Partial evaluation in rank aggregation problems
• ConsRank
• The Bradley-Terry regression trunk approach for modeling preference data with small trees
• Consensus among preference rankings: a new weighted correlation coefficient for linear and weak orderings
• A differential evolution algorithm for finding the median ranking under the Kemeny axiomatic approach
• On weakly and strongly popular rankings
• A recursive partitioning method for the prediction of preference rankings based upon Kemeny distances
• Median constrained bucket order rank aggregation
• Copula-based non-metric unfolding on augmented data matrix
• Efficient algorithms using subiterative convergence for Kemeny ranking problem
• Comparing boosting and bagging for decision trees of rankings
• A new position weight correlation coefficient for consensus ranking process without ties
• Approaching the rank aggregation problem by local search-based metaheuristics

This page was built for publication: Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q62323)