Diversity of Structured Domains via k-Kemeny Scores
In the k-Kemeny problem, we are given an ordinal election, i.e., a collection of votes ranking the candidates from best to worst, and we seek the smallest number of swaps of adjacent candidates that ensure that the election has at most k different rankings. We study this problem for a number of structured domains, including the single-peaked, single-crossing, group-separable, and Euclidean ones. We obtain two kinds of results: (1) We show that k-Kemeny remains intractable under most of these domains, even for k=2, and (2) we use k-Kemeny to rank these domains in terms of their diversity.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Diversity in Kemeny Rank Aggregation: A Parameterized Approach
In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called s…
DiversityParameterized Aspects of Distinct Kemeny Rank Aggregation
The Kemeny method is one of the popular tools for rank aggregation. However, computing an optimal Kemeny ranking is NP-hard. Consequently, the computational task of finding a Kemeny ranking has been studied under the len…
Optimal majority rules and quantitative Condorcet properties of setwise Kemeny voting schemes
The important Kemeny problem, which consists of computing median consensus rankings of an election with respect to the Kemeny voting rule, admits important applications in biology and computational social choice and was …
Space reduction techniques for the $3$-wise Kemeny problem
Kemeny's rule is one of the most studied and well-known voting schemes with various important applications in computational social choice and biology. Recently, Kemeny's rule was generalized via a set-wise approach by Gi…
Beyond Kemeny Medians: Consensus Ranking Distributions Definition, Properties and Statistical Learning
In this article we develop a new method for summarizing a ranking distribution, \textit{i.e.} a probability distribution on the symmetric group $\mathfrak{S}_n$, beyond the classical theory of consensus and Kemeny median…