The concept of ranking aggregation plays a central role in preference analysis, and numerous algorithms for calculating median rankings, often originating in social choice theory, have been documented in the literature, offering theoretical guarantees in a centralized setting, i.e., when all the ranking data to be aggregated can be brought together in a single computing unit. For many technologies (e.g. peer-to-peer networks, IoT, multi-agent systems), extending the ability to calculate consensus rankings with guarantees of convergence and resilience to potential contamination in a decentralized setting, when preference data is initially distributed across a communicating network, remains a major methodological challenge. Indeed, in recent years, the literature on decentralized computation has mainly focused on computing or optimizing statistics such as arithmetic means using gossip algorithms. The purpose of this article is precisely to study how to achieve reliable and resilient consensus on collective rankings in a decentralized setting, thereby raising new questions, robustness to corrupted nodes, and scalability through reduced communication costs in particular. The approach proposed and analyzed here relies on the robustness guarantees offered by random gossip communication, which allows autonomous agents to compute a global ranking consensus using local interactions only, without coordination or a central authority.
Figures & tables
Figure 1: Illustration of the randomized (ϕ,ψ) -gossip. Considering a set of N=5 nodes each possessing a ranking, we succinctly present the gossip protocol for rankings.
Figure 2
Figure 2: Average local dτ error to respective consensus for the randomized gossip process.
Figure 3: Average Kendall- τ error vs. contamination for Mallows distribution.
Table 1: Common ranking methods expressed in embedding-aggregation form. The map ϕ encodes a permutation σ∈Sn into the embedding space, ψ aggregates information into scores, and ∣I∣ denotes the dimensionality of the embedding.
Figure 4: Convergence of consensus methods (Borda, Copeland, Footrule) on rankings sampled from a Mallows model ( N=151 agents, n=8 items, φ=0.5 ) across different graph topologies. Results show mean ± standard deviation over 100 trials.
Figure 5: Score estimation error and consensus quality under the Mallows model ( N=1000 voters, n=7 alternatives) across four dispersion levels φ∈{0.3,0.5,0.7,0.9} (columns, left to right). Small φ indicates low noise (rankings concentrated near the central order); large φ indicates high noise (near-uniform preferences). Rows 1-2 show the MSE of estimated Borda and Copeland scores, respectively, as a function of the number of sampled rankings. Row 3 compares the consensus rankings produced by the two rules, measured by their distance to the ground-truth central ranking.
Consensus
dτ(⋅,σ⋆)
ΔLPN w/o Local Kemenization
ΔLPN w/ Local Kemenization
Borda
0.25±0.46
0.01±0.03
0.00±0.00
Copeland
0.07±0.26
0.00±0.00
0.00±0.00
Footrule
1.04±0.81
0.17±0.17
0.00±0.00
Kemeny
0.06±0.24
N/A 2 2 2 For the global Kemeny consensus, the system is already locally Kemeny optimal.
N/A † † footnotemark:
Appendix
Table 2: Robustness of consensus methods for recovering the central ranking σ⋆ under random contamination. Rankings are sampled from a Mallows model ( N=100 , n=8 items, φ=0.5 ) where ε=0.3 of samples are replaced with uniform random permutations. We report the Kendall-tau distance to the ground truth dτ(⋅,σ⋆) and the excess risk ΔLPN follows the definition in Equation ( 30 ), where LPN⋆ is the Kemeny optimal value for the empirical distribution PN . Results show mean ± standard deviation over 100 trials.
Consensus
dτ(⋅,σ⋆)
ΔLPN w/o Local Kemenization
ΔLPN w/ Local Kemenization
Borda
0.91±0.85
0.03±0.04
0.00±0.00
Copeland
0.59±0.71
0.00±0.02
0.00±0.01
Footrule
1.26±0.99
0.13±0.11
0.01±0.02
Kemeny
0.58±0.67
N/A † † footnotemark:
N/A † † footnotemark:
Appendix
Table 3: Robustness of consensus methods under adversarial contamination. Setup is identical to Table 2 , except contaminated samples are drawn from a Mallows model centered at the reversed ranking σrev rather than uniform random permutations.
Experiments
Time to compute
Experiment 5.1 (Debian)
<5 min
Experiment 5.1 (Sushi)
∼1 h
Experiment 5.1 (Mixture of Mallows)
∼15 min
Experiment 5.2 (Breakdown study)
∼10 h
Experiment J.1 (Synthetic data with Spearman Footrule)
Rank aggregation combines ranked lists or pairwise preferences into a consensus ordering for tasks such as search, recommendation, and model evaluation.
Aggregating a consensus ranking from multiple input rankings is a fundamental problem with applications in recommendation systems, search engines, job recruitment, and elections. Despite decades of research in consensus ranking aggregation, minimizing the Kemeny distance remains computationally intractable. Specifically, determining an optimal aggregation of rankings with respect to the Kemeny distance is an NP-hard problem, limiting its practical application to relatively small-scale instances. We propose the Kemeny Transformer, a novel Transformer-based algorithm trained via reinforcement learning to efficiently approximate the Kemeny optimal ranking. Experimental results demonstrate that our model outperforms classical majority-heuristic and Markov-chain approaches, achieving substantially faster inference than integer linear programming solvers. Our approach thus offers a practical, scalable alternative for real-world ranking-aggregation tasks.
Yijun Jin, Simon Klüttermann, Chiara Balestra +1
TU Dortmund University, Dortmund, Germany · Research Center Trustworthy Data Science and Security, University Alliance Ruhr, Dortmund, Germany
Existing governance approaches in decentralized financial networks rely on manual review processes conducted by human committees, which introduces subjective bias, creates a scalability bottleneck under high network volume, and fails to capture complex behavioural patterns and evolving network dynamics. To address these limitations, we propose \name, a federated learning-based pairwise ranking framework in which multiple institutions collaboratively train a ranking model without sharing their private transaction data. This collaborative learning enables the model to capture network-wide behavioural patterns that signify strong network participation and directly contribute to the network effect, including diversity of counterparties, usage of multiple applications, and frequency of transactions. The proposed system ranks providers based on the authenticity of their actions, promoting genuine contributors and demoting those exhibiting suspicious behaviour. We evaluate \name\ on a real-world blockchain transaction dataset. Results demonstrate that the federated approach achieves ranking performance modestly below the centralized baseline (NDCG@15: ≈0.87 vs.\ ≈0.92) while preserving data privacy and matching its ranking stability (Kendall τ: ≈0.70 for both regimes), producing reliable governance decisions, including provider promotion and demotion (648 and 39 unique providers, respectively), without requiring centralized access to sensitive transaction data.
Zahra Batool, Michael Duchesne, Kaiwen Zhang +1
Ecole de technologie sup´erieure, Montr´eal, Canada · Mila - Quebec AI Institute, Montr´eal, Canada · T-RIZE GROUP, Montr´eal, Canada
Motivated by applications in reinforcement learning from human feedback, we consider a setting where a given collection of rankings needs to be compressed into a smaller collection of rankings. This can also be seen as a combination of two fundamental social choice frameworks: ranking aggregation and multiwinner voting. We propose three proportionality notions that capture different types of representation in this setting: positional proportionality, pairwise proportionality, and proportionality for solid coalitions (PSC). On the one hand, we show that positional proportionality and PSC are always satisfiable for any input rankings and target compression size, and a desired output can be found in polynomial time. On the other hand, we prove that pairwise proportionality cannot be satisfied in general, but can nevertheless be attained when the input rankings are single-peaked or single-crossing.
Daniel Halpern, Xinyu Liu, Evi Micha +2
Google Research · U. of Southern California · National University of Singapore