How to aggregate Top-lists: Approximation algorithms via scores and average ranks

Claire Mathieu, Simon MaurasSODA 2020 · OpenReview

TL;DR

This paper tackles the problem of aggregating incomplete rankings (top-lists), a common scenario in applications like meta-search engines. The authors introduce several new approximation algorithms, including a 2-approximation based on generalizing the Footrule algorithm and a PTAS (Polynomial Time Approximation Scheme) for the general case, effectively solving an open problem.

What Problem Does This Paper Address?

The core problem is "top-list aggregation" (TOP-AGG). Imagine you're building a search engine that aggregates results from multiple other search engines. Each search engine provides a ranked list of results, but they might not rank all possible results – they often just give their top few. This is a "top-list." The challenge is to combine these incomplete, ranked lists into a single, complete ranking that minimizes "upsets" – pairs of items ranked in opposite orders in the aggregated list compared to the input lists. This is a generalization of the classic rank aggregation problem, which deals with complete rankings. The paper aims to find efficient algorithms that produce rankings close to the optimal one, even if finding the absolute best is computationally hard.

Methods

The paper proposes several algorithms, building upon existing rank aggregation techniques:

  • Generalized Footrule Algorithm (FOOTRULE+): This algorithm extends the classic Footrule algorithm (which minimizes Spearman's footrule distance) to handle top-lists. It uses a min-cost perfect matching approach and achieves a 2-approximation.
  • Randomized Algorithms (RANDOMSORT): Inspired by Ailon's REPEATCHOICE algorithm for bucket orders, this randomized approach uses scores (frequency of being ranked) and average ranks to construct a ranking. It's a 2-approximation algorithm.
  • Generalized Borda's Algorithm (BORDA+): This algorithm sorts candidates by their average rank. While simple, it's shown not to be a constant-factor approximation in general.
  • Two-Phase Algorithms:
    • SCORE-THEN-BORDA+: This algorithm first roughly sorts candidates by their scores and then uses average ranks to break ties. It provides a constant-factor approximation.
  • SCORE-THEN-PTAS: This algorithm uses a similar score-based partitioning but then employs a known PTAS for full-ranking aggregation (FASTER-SCHEME) within each partition. This yields a (1+ε)-approximation algorithm, solving an open problem.
  • EPTAS for Top-k-AGG (SCORE-THEN-ADJUST): For the specific case where all input top-lists have a fixed length k, they develop an Efficient PTAS (EPTAS). This algorithm is particularly efficient when k is small compared to n (the total number of candidates).

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and uses synthetic examples for illustration.

Key Insights and Ideas

  • Scores are Crucial: The paper highlights that simply using average ranks (like in Borda's method) isn't sufficient for top-list aggregation. The "score" of a candidate (how often they appear in any top-list) becomes a primary factor for good approximation.
  • Two-Phase Approach is Powerful: Combining score-based partitioning with a secondary sorting criterion (like average rank or a PTAS) is a robust strategy for achieving good approximation guarantees.
  • Generalizing Existing Algorithms: The work demonstrates that many successful rank aggregation techniques for full rankings can be adapted to the more challenging top-list setting, often with similar approximation factors.
  • Solving an Open Problem: The development of a PTAS for top-list aggregation directly addresses a question posed by previous research.

Key Results

  • FOOTRULE+: A simple 2-approximation algorithm.
  • RANDOMSORT: A randomized 2-approximation algorithm.
  • SCORE-THEN-BORDA+: A constant-factor approximation algorithm using scores and average ranks.
  • SCORE-THEN-PTAS: A (1+ε)-approximation algorithm (PTAS) for general top-list aggregation.
  • SCORE-THEN-ADJUST: An EPTAS for the specific TOP-k-AGG problem, with complexity dependent on k.

Limitations and Future Work

  • Approximation Ratios: While constant-factor approximations are provided, the exact ratios (e.g., 8ε + 4) are not necessarily the tightest possible. The authors mention they didn't focus on optimizing these specific constants.
  • Bucket Orders: The paper briefly mentions "bucket orders" as a further generalization of rankings. It poses the existence of an approximation scheme for this more general setting as an open problem.
  • Computational Complexity: While many algorithms are efficient (quasi-linear or polynomial), the PTAS and EPTAS have complexities that can grow significantly with the desired approximation factor ε or the list length k. The paper notes that for SCORE-THEN-ADJUST, the complexity is quasi-linear if k is small (k = o(log n)).

Summary updated

Abstract

A top-list is a possibly incomplete ranking of elements: only a subset of the elements are ranked, with all unranked elements tied for last. Top-list aggregation, a generalization of the well-known rank aggregation problem, takes as input a collection of top-lists and aggregates them into a single complete ranking, aiming to minimize the number of upsets (pairs ranked in opposite order in the input and in the output). In this paper, we give simple approximation algorithms for top-list aggregation.•We generalize the footrule algorithm for rank aggregation (which minimizes Spearman's footrule distance), yielding a simple 2-approximation algorithm for top-list aggregation.•Ailon's RepeatChoice algorithm for bucket-orders aggregation yields a 2-approximation algorithm for top-list aggregation. Using inspiration from approval voting, we define the score of an element as the frequency with which it is ranked, i.e. appears in an input top-list. We reinterpret RepeatChoice for top-list aggregation as a randomized algorithm using variables whose expectations correspond to score and to the average rank of an element given that it is ranked.•Using average ranks, we generalize and analyze Borda's algorithm for rank aggregation. We observe that the natural generalization is not a constant approximation.•We design a simple 2-phase variant of the Generalized Borda's algorithm, roughly sorting by scores and breaking ties by average ranks, yielding another simple constant-approximation algorithm for top-list aggregation.•We then design another 2-phase variant in which in order to break ties we use, as a black box, the Mathieu-Schudy PTAS for rank aggregation, yielding a PTAS for top-list aggregation. This solves an open problem posed by Ailon.•Finally, in the special case in which all input lists have length at most k, we design another simple 2-phase algorithm based on sorting by scores, and prove that it is an EPTAS – the complexity is (n log n) when k = o(log n).
BibTeX
@inproceedings{mathieu2020how,
  author = {Claire Mathieu and Simon Mauras},
  title = {{How to aggregate Top-lists: Approximation algorithms via scores and average ranks}},
  booktitle = {SODA},
  year = {2020},
  url = {https://openreview.net/forum?id=rU4pz80T1w},
}
Figure