Research map / Learning theory and algorithms / Optimal transport

Beyond Kemeny Medians: Consensus Ranking Distributions. Definition, Properties and Statistical Learning

NeurIPS 2026 · Learning theory and algorithms › Optimal transport · approach: Wasserstein barycenters and GW · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces consensus ranking distributions (CRD), a sparse mixture of Dirac masses at local Kemeny medians over a partition of the symmetric group, and a top-down tree algorithm (COAST) that learns them from ranking data.

Problem

Summarizing a ranking distribution (probability law on the symmetric group) beyond a single Kemeny median, since a single median is too crude for multimodal or heterogeneous ranking data and n! support makes the raw empirical distribution unusable.

Approach

Approximate a ranking distribution by a mixture of Dirac masses at local Kemeny medians on cells of a partition of S_n; under Kendall tau cost, the optimal distortion bound depends only on local pairwise probabilities, enabling a top-down binary tree (COAST) that splits on pairwise comparisons sigma(i)<sigma(j).</askingcore_idea>

Key results

• Under Kendall tau cost the optimal distortion bound depends only on local pairwise probabilities p_ij(C), with E'(P) = sum P(C)V'(C) upper bounding W_d(P, P_P) up to factor 2.
• On Mallows mixtures with n=50 and K=8 components, the COAST distortion curve plateaus at the correct number of modes.
• L2 distance between the COAST approximant and the true mixture is minimized at K=4 for the 4-component Mallows mixture experiment.

Surprising findings

• Splitting on the pair closest to p=1/2 (a cheaper rule) gives comparable distortion reduction to the exact criterion, though no theory is given for when it is quasi-optimal.

Limitations

• Theoretical bounds rely on choosing partitions with cells of sufficient probability; statistical guarantees depend on chi(Pi_K) and K.
• Model selection for number of cells is only sketched, with details left to the reader.
• Experiments are on synthetic Mallows and Plackett-Luce mixtures only.

Experimental setup

Datasets: synthetic Mallows mixtures synthetic Plackett-Luce mixtures

Metrics: distortion (Kendall tau Wasserstein bound) L2 distance between approximant and mixture local depth separation

Baselines: global Kemeny median raw empirical distribution

Builds on: Kemeny ranking aggregation bucket ranking distribution ranking depth U-statistics concentration

Closest papers by meaning

• Controlling the distance to a Kemeny consensus without computing it (ICML 2016 · similarity 0.89)
• Robust Consensus in Ranking Data Analysis: Definitions, Properties and Computational Issues (ICML 2023 · similarity 0.89)
• Decentralized Ranking Aggregation via Gossip: Convergence and Robustness (NeurIPS 2026 · similarity 0.87)
• Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.85)
• Low-Distortion Clustering with Ordinal and Limited Cardinal Information (AAAI 2024 · similarity 0.85)
• Stability and Multigroup Fairness in Ranking with Uncertain Predictions (ICML 2024 · similarity 0.84)