Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem

Hugo Gilbert, Tom Portoleau, Olivier SpanjaardAAAI 2020 · DOI

TL;DR

This paper introduces a novel approach to rank aggregation by considering "setwise" comparisons of alternatives, going beyond traditional pairwise comparisons. They propose and analyze a "k-wise Kemeny rule" that minimizes disagreements across subsets of candidates, offering a more nuanced aggregation that can better capture voter preferences, especially when dealing with potential conflicts between majority and plurality outcomes.

What Problem Does This Paper Address?

In social choice theory and various applications like preference learning and search engines, the goal of rank aggregation is to combine multiple individual preference rankings into a single "consensus" ranking. Traditional methods, like the Kemeny rule, often rely solely on pairwise comparisons (e.g., "is candidate A preferred to candidate B?"). However, this can lead to counterintuitive results, as illustrated by an example where a candidate with broad but shallow support (plurality winner) might be overlooked in favor of a candidate with strong but narrow support (Condorcet winner). This paper addresses the limitation of pairwise comparisons by proposing an aggregation method that considers how voters rank candidates within subsets of alternatives, aiming to reconcile these potential conflicts and provide a more robust consensus.

Methods

The core contribution is the introduction of the k-wise Kemeny rule. This rule generalizes the standard Kemeny rule by minimizing the number of "k-wise disagreements." A k-wise disagreement occurs when the top-ranked candidate within a subset of size k in an input ranking differs from the top-ranked candidate of that same subset in the output ranking.

The authors develop an algorithmic approach to solve this k-wise Kemeny Aggregation Problem (k-KAP). They propose a dynamic programming solution with a time complexity of O(2^m * m^2 * n), where m is the number of candidates and n is the number of voters. Additionally, they introduce a k-wise majority digraph as a preprocessing step. This digraph captures setwise preferences and can help decompose the aggregation problem into smaller subproblems, potentially speeding up computation, especially for k=3. However, constructing this digraph becomes NP-hard for k ≥ 4.

Datasets

Not discussed in the paper. The authors use synthetic preference profiles generated using the Mallows model for their numerical experiments.

Key Insights and Ideas

  • Beyond Pairwise: The fundamental insight is that focusing solely on pairwise comparisons can miss crucial information about how voters rank candidates within groups, leading to suboptimal consensus rankings.
  • Setwise Contests as a Solution: Considering "setwise contests" (i.e., how voters rank candidates within subsets) provides a richer signal for aggregation, allowing the method to balance different types of voter agreement.
  • Reconciling Plurality and Majority: The k-wise Kemeny rule offers a principled way to address the tension between candidates who are popular overall (plurality winners) and those who consistently win pairwise contests (Condorcet winners).
  • Complexity Trade-offs: While the k-wise Kemeny rule is NP-hard to compute for k ≥ 3, the authors provide an efficient dynamic programming solution that is fixed-parameter tractable with respect to the number of candidates.
  • The k-wise Majority Digraph: This novel data structure offers a promising avenue for preprocessing, particularly for k=3, by identifying strongly connected components that can be aggregated independently.

Key Results

  • NP-Hardness: The k-wise Kemeny Aggregation Problem (k-KAP) is proven to be NP-hard for any constant k ≥ 3.
  • Dynamic Programming Solution: An efficient dynamic programming algorithm is presented, making k-KAP solvable in practice for moderate numbers of candidates (up to 18 in their tests).
  • k-wise Majority Digraph Complexity: Computing the k-wise majority digraph is polynomial for k=3 but NP-hard for k ≥ 4.
  • Impact of k: Increasing k generally leads to a smaller set of consensus rankings, suggesting that higher-order comparisons refine the aggregation outcome.
  • Preprocessing Effectiveness: The k-wise majority digraph preprocessing significantly speeds up computation for k=3, especially when voter preferences are correlated.

Limitations and Future Work

  • Hardness for k ≥ 4: The NP-hardness of constructing the k-wise majority digraph for k ≥ 4 limits its direct applicability as a preprocessing step for larger k.
  • Fixed k Hardness: The NP-hardness results are for fixed values of k. The complexity of k-KAP when k can be as large as the number of candidates (k=m) remains an open question.
  • Alternative Digraphs: The authors suggest exploring alternative definitions of k-wise majority graphs that might be easier to compute for k > 3.
  • Other Setwise SWFs: Investigating other social welfare functions based on setwise contests, beyond the k-wise Kemeny rule, is a promising future direction.
  • Axiomatic Properties: While some axiomatic properties are discussed, a more thorough investigation could be beneficial.

Summary updated

BibTeX
@inproceedings{gilbert2020beyond,
  author = {Hugo Gilbert and Tom Portoleau and Olivier Spanjaard},
  title = {{Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5569},
}
Figure