Diversity of Structured Domains via k-Kemeny Scores
By: Piotr Faliszewski , Krzysztof Sornat , Stanisław Szufa and more
Potential Business Impact:
Makes voting fairer by fixing bad rankings.
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.
Similar Papers
Efficient space reduction techniques by optimized majority rules for the Kemeny aggregation problem
Data Structures and Algorithms
Finds the best election winner faster.
Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
Data Structures and Algorithms
Finds many different good answers to hard problems.
A general framework for finding diverse solutions via network flow and its applications
Data Structures and Algorithms
Finds many different good answers to hard problems.