Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem
Preprint
Abstract
In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k-wise Kemeny aggregation problem, we introduce a k-wise counterpart of the majority graph. This graph reveals useful to divide the aggregation problem into several sub-problems, which enables to speed up the exact computation of a consensus ranking. By introducing a k-wise counterpart of the Spearman distance, we also provide a 2-approximation algorithm for the k-wise Kemeny aggregation problem. We conclude with numerical tests.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- An updated survey on the linear ordering problem for weighted or unweighted tournamentsAnnals of Operations Research, 2009
- Fixed-parameter algorithms for Kemeny rankingsTheoretical Computer Science, 2009
- Consensus Genetic Maps as Median Orders from Inconsistent SourcesIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008
- Axiomatic Foundations for Ranking SystemsJournal of Artificial Intelligence Research, 2008
- Voting schemes for which it can be difficult to tell who won the electionSocial Choice and Welfare, 1989
- A Consistent Extension of Condorcet’s Election PrincipleSIAM Journal on Applied Mathematics, 1978
- Condorcet Social Choice FunctionsSIAM Journal on Applied Mathematics, 1977
- Spearman's Footrule as a Measure of DisarrayJournal of the Royal Statistical Society Series B: Statistical Methodology, 1977
- An axiomatization of Borda's ruleJournal of Economic Theory, 1974
- A Difficulty in the Concept of Social WelfareJournal of Political Economy, 1950