Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem

Hugo Gilbert, Tom Portoleau, Olivier Spanjaard
AAAI 2020

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. It reveals useful to divide the aggregation problem into several sub-problems. We conclude with numerical tests.