Optimal Majority Rules and Quantitative Condorcet Properties of Setwise Kemeny Voting Schemes

The Kemeny problem consists of computing consensus rankings of an election with respect to the Kemeny voting rule, admits important applications in biology and computational social choice [1, 2, 4, 6]. The problem was generalized recently via an interesting setwise approach by Gilbert et al. [9, 10] where not only pairwise comparisons but also the discordance between the winners of subsets of three candidates are also taken into account. We elaborate an exhaustive list of quantified axiomatic properties such as the Condorcet and Smith criteria, the 5/6-majority rule, and the Unanimity property of the 3-wise Kemeny rule. Since the 3-wise Kemeny problem is NP-hard, our results also provide some of the first useful search space reduction techniques by determining the relative orders of pairs of alternatives. Our works suggest similar interesting properties of higher setwise Kemeny voting schemes which justify the more expensive computational cost than the classical Kemeny scheme. We also establish optimal quantitative extensions of the Unanimity property and the well-known 3/4-majority rule of Betzler et al. [4] for the classical Kemeny problem.