Back to Search
Start Over
Beyond pairwise comparisons in social choice: A setwise Kemeny aggregation problem.
- Source :
-
Theoretical Computer Science . Feb2022, Vol. 904, p27-47. 21p. - Publication Year :
- 2022
-
Abstract
- • We study a k-wise generalization of the Kemeny rule. • We study the properties of this distance, and of the induced aggregation rule. • We introduce a k-wise counterpart of the majority graph. • We provide computational complexity results for the aggregation problem. • A polytime 2-approximation algorithm is provided for the aggregation problem. 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 904
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 154856924
- Full Text :
- https://doi.org/10.1016/j.tcs.2021.07.004