Diversity in Kemeny Rank Aggregation: A Parameterized Approach

Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra WolfIJCAI 2021 · DOI

TL;DR

This paper tackles the challenge of finding a diverse set of "good enough" solutions for the Kemeny Rank Aggregation problem, a core issue in social choice theory. By combining ideas from parameterized complexity theory and solution diversity, the authors develop efficient algorithms that can find multiple, distinct, and high-quality rankings, offering users more flexibility and insight into the solution space.

What Problem Does This Paper Address?

Traditional optimization theory focuses on finding a single "best" solution. However, in many real-world scenarios, especially those involving subjective preferences like elections or rankings, a single optimal solution might not be ideal. Users might prefer a small set of "good" solutions that are diverse from each other, allowing them to choose the one that best fits their specific context or criteria. This is particularly relevant for Kemeny Rank Aggregation (KRA), a problem that aims to find a consensus ranking from a set of individual rankings (votes). KRA is known to be computationally hard (NP-complete). Furthermore, when dealing with "partial orders" as votes (allowing for ties), the problem becomes even more complex. The paper addresses the need for algorithms that can find not just one, but a diverse set of high-quality solutions for KRA, especially in the more general setting of partial order votes.

Methods

The core of this work lies in combining two powerful theoretical frameworks:

  • Parameterized Complexity Theory: This approach breaks down computational problems by identifying specific "parameters" (like the number of solutions desired, or the degree of diversity) and aims to find algorithms whose runtime is exponential only in these parameters, not in the overall input size. This allows for efficient solutions when these parameters are small in practice.
  • Solution Diversity: This paradigm shifts the goal from finding a single optimal solution to finding a small set of "sufficiently good" solutions that are also "diverse" from each other. The paper defines diversity using the Kendall-Tau distance between rankings.

The authors develop a multiparametric algorithm for "Diverse Kemeny Rank Aggregation" (Diverse KRA). They achieve this by:

  1. Reducing KRA to Completion of an Ordering (CO): They show that KRA can be elegantly transformed into a more general problem called Completion of an Ordering (CO). This allows them to leverage existing or develop new algorithms for CO and then apply them back to KRA.
  2. Developing FPT Algorithms for CO: They design fixed-parameter tractable (FPT) algorithms for both the single-solution and diverse versions of CO. These algorithms are parameterized by:
  3. Solution Imperfection (d): How close a solution is to the optimal cost.
  4. Number of Solutions (r): The size of the desired diverse set.
  5. Scatteredness (s): A measure to ensure solutions are truly distinct.
  6. Unanimity Width (w): A parameter related to the disagreement among votes, quantified by the pathwidth of the cocomparability graph of the unanimity order of the votes.
  7. Leveraging Path Decomposition: A key technical tool used is the concept of path decomposition of graphs, which is particularly effective for cocomparability graphs (graphs related to partial orders). They show how to construct "p-consistent" path decompositions efficiently.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • Diversity is Crucial for Subjectivity: The paper strongly argues that for problems involving subjective preferences (like social choice), a diverse set of solutions is often more valuable than a single optimal one. This allows users to make informed choices based on context.
  • Bridging KRA and CO: The reduction of KRA to CO is a significant theoretical contribution, unifying these problems and allowing for the transfer of algorithmic techniques.
  • Parameterizing Diversity: The authors successfully formalize and parameterize the notion of diversity for KRA, making it amenable to FPT algorithms. This allows for efficient computation when the desired diversity or the number of solutions is small.
  • Unanimity Width as a Key Parameter: The unanimity width (related to pathwidth) is identified as a crucial parameter that quantifies disagreement among voters and is effectively used in their FPT algorithms.
  • Partial Orders Enable More Meaningful Diversity: The paper highlights that in the context of partial order votes (allowing ties), meaningful diversity can exist even when voters have low disagreement, unlike the case with strictly ordered votes.

Key Results

The paper presents several key theoretical results:

  • FPT Algorithm for Diverse KRA: They provide a fixed-parameter tractable algorithm for Diverse Kemeny Rank Aggregation with partially ordered votes. The algorithm's runtime is parameterized by solution imperfection (d), number of solutions (r), scatteredness (s), and unanimity width (w).
  • FPT Algorithms for Diverse CO: As a stepping stone, they develop FPT algorithms for the Diverse Completion of an Ordering problem, parameterized by similar factors.
  • Sub-exponential Algorithm for PCO: They present a new sub-exponential time algorithm for the Positive Completion of an Ordering (PCO) problem, which is a restriction of CO. This algorithm is parameterized by the cost (k) and runs in time $O(|C| \cdot 2^{O(\sqrt{k})})$.
  • Corollaries for Specific Cases: They derive several corollaries for specific scenarios, such as finding multiple optimal solutions or maximizing diversity for a given cost bound. For instance, Corollary 17 shows how to find r different optimal solutions in time $O((w! \cdot \delta)^{O(r)} \cdot 2^{2r} \cdot n \cdot \log(n^2 m))$.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on algorithm design and complexity analysis. It does not include experimental evaluations or comparisons on real-world datasets.
  • Parameter Dependence: While FPT algorithms are efficient for small parameter values, their runtime can still be prohibitive if these parameters become large.
  • Future Work: The authors suggest that their work has a positive impact on various fields like artificial intelligence, graph drawing, and computational biology, implying potential for future applications and extensions. The development of sub-exponential algorithms for PCO also opens doors for further research in related combinatorial problems.

Summary updated

BibTeX
@inproceedings{arrighi2021diversity,
  author = {Emmanuel Arrighi and Henning Fernau and Daniel Lokshtanov and Mateus de Oliveira Oliveira and Petra Wolf},
  title = {{Diversity in Kemeny Rank Aggregation: A Parameterized Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/2},
}
Figure