University of Augsburg, a
Abstract
The rank aggregation problem, which has many real-world applications, refers
to the process of combining multiple input rankings into a single aggregated
ranking. In dynamic settings, where new rankings arrive over time, efficiently
updating the aggregated ranking is essential. This paper develops a fast,
theoretically and practically efficient dynamic rank aggregation algorithm.
First, we develop the LR-Aggregation algorithm, built on top of the LR-tree
data structure, which is itself modeled on the LR-distance, a novel and
equivalent take on the classical Spearman's footrule distance. We then analyze
the theoretical efficiency of the Pick-A-Perm algorithm, and show how it can be
combined with the LR-aggregation algorithm using another data structure that we
develop. We demonstrate through experimental evaluations that LR-Aggregation
produces close to optimal solutions in practice. We show that Pick-A-Perm has a
theoretical worst case approximation guarantee of 2. We also show that both the
LR-Aggregation and Pick-A-Perm algorithms, as well as the methodology for
combining them can be run in $O(n \log n)$ time. To the best of our knowledge,
this is the first fast, near linear time rank aggregation algorithm in the
dynamic setting, having both a theoretical approximation guarantee, and
excellent practical performance (much better than the theoretical guarantee).
AI Insights - Borda count assigns points inversely proportional to rank position, making it resilient to minor rank shifts.
- Pairwise comparison aggregates by majority preference between each pair, yielding a Condorcet‑consistent ranking when it exists.
- Dynamic aggregation of streaming gene lists adapts to new experiments with negligible recomputation, as shown in Wang et al. 2022.
- Robust variants like median rank or trimmed Borda mitigate outlier influence, addressing weaknesses highlighted in the paper.
- Wang et al.'s 2024 survey offers a taxonomy of aggregation methods across domains, from social choice to bioinformatics.
- Teng et al. 2018 present a voting aggregation algorithm that optimizes social satisfaction under cardinal utilities, a useful benchmark.
Princeton University
Abstract
This paper studies human preference learning based on partially revealed
choice behavior and formulates the problem as a generalized Bradley-Terry-Luce
(BTL) ranking model that accounts for heterogeneous preferences. Specifically,
we assume that each user is associated with a nonparametric preference
function, and each item is characterized by a low-dimensional latent feature
vector - their interaction defines the underlying low-rank score matrix. In
this formulation, we propose an indirect regularization method for
collaboratively learning the score matrix, which ensures entrywise
$\ell_\infty$-norm error control - a novel contribution to the heterogeneous
preference learning literature. This technique is based on sieve approximation
and can be extended to a broader class of binary choice models where a smooth
link function is adopted. In addition, by applying a single step of the
Newton-Raphson method, we debias the regularized estimator and establish
uncertainty quantification for item scores and rankings of items, both for the
aggregated and individual preferences. Extensive simulation results from
synthetic and real datasets corroborate our theoretical findings.
AI Insights - Leave‑one‑out analysis of nonconvex gradient descent iterates yields sharp Frobenius, spectral, and infinity‑norm error bounds.
- The regularization parameter scales as λ = Cλ p d̄/ p̄, ensuring entry‑wise ℓ∞ control across heterogeneous users.
- Iterations are capped at t₀ = O(d̄²), guaranteeing convergence with probability 1−O(d̄⁻¹⁰).
- Singular values of the ground‑truth matrix satisfy σ₁(F⋆)=pσ⋆max/2 and σ_R(F⋆)=pσ⋆min/2, anchoring the low‑rank structure.
- Leave‑one‑out subproblems f^(ℓ)(X,Y) are defined separately for ℓ∈[1,d₁] and ℓ∈[d₁+1, d̄], enabling decoupled analysis.
- The gradient descent iterates Ft,^(ℓ) are constructed via (H.3), preserving the low‑rank manifold throughout optimization.
- These techniques are broadly applicable to any binary choice model with a smooth link, beyond the BTL framework.