# Diversity in Kemeny Rank Aggregation: A Parameterized Approach

arXiv: https://arxiv.org/abs/2105.09413 · HTML: https://mlsanity.com/paper/2105.09413/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 67 references that are in the map.
- First posted on arXiv 19 May 2021.

## Builds on (most cited first, 8 of 8)

- [Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory](https://mlsanity.com/paper/1903.07410/) (2019)
- [FPT Algorithms for Diverse Collections of Hitting Sets](https://mlsanity.com/paper/1911.05032/) (2019)
- [Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem](https://mlsanity.com/paper/1911.06226/) (2019)
- [Ranking Median Regression: Learning to Order through Local Consensus](https://mlsanity.com/paper/1711.00070/) (2017)
- [Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs](https://mlsanity.com/paper/1907.04585/) (2019)
- [On the Enumeration of Minimal Dominating Sets and Related Notions](https://mlsanity.com/paper/1407.2053/) (2014)
- [Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width](https://mlsanity.com/paper/1509.03753/) (2015)
- [Preparing for the Unexpected: Diversity Improves Planning Resilience in Evolutionary Algorithms](https://mlsanity.com/paper/1810.12483/) (2018)

## Built on by (most cited first, 1 of 1)

- [Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing](https://mlsanity.com/paper/2301.05146/) (2023)

## Abstract (arXiv)

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 solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.