Decentralized Ranking Aggregation via Gossip: Convergence and Robustness

Kerrian Le Caillec; Anna Van Elst; Igor Colin; Stephan Clémençon

cs.LGFeb 26, 2026

Decentralized Ranking Aggregation via Gossip: Convergence and Robustness

Authors: Kerrian Le Caillec, Anna Van Elst, Igor Colin, Stephan Clémençon

Organizations: LTCI, Télécom-Paris, Institut Polytechnique de Paris 19 Place Marguerite Perey, 91120 Palaiseau

Abstract

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

Panel of Figure 1 — Figure 1: Illustration of the randomized $(\phi,\psi)$ -gossip. Considering a set of $N=5$ nodes each possessing a ranking, we succinctly present the gossip protocol for rankings.

Figure 2

Panel of Figure 3 — Figure 3: Average Kendall- $\tau$ error vs. contamination for Mallows distribution.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Embedding $\phi(\sigma)$	Aggregation $\psi(\mathbf{x})$	Dim. $\|I\|$
Borda	$(\sigma(1),\dots,\sigma(n))^{\top}$	$\mathrm{Id}$	$n$
Copeland	$(\mathbb{I}\{\sigma(i)<\sigma(j)\})_{i<j}$	$\left(\sum_{j\neq i}\big[\mathbb{I}\{\mathbf{x}_{ij}>\tfrac{1}{2}\}-\mathbb{I}\{\mathbf{x}_{ij}<\tfrac{1}{2}\}\big]\right)_{i=1}^{n}$	$n(n-1)/2$
Bucklin [ erdelyi_control_2015 ]	$(\mathbb{I}\{\sigma(i)=k\})_{i,k\in\llbracket n\rrbracket}$	$\left(\min\left\{k\in\llbracket n\rrbracket\mid\sum^{k}_{\ell=1}\mathbf{x}_{i\ell}>1/2\right\}\right)_{i=1}^{n}$	$n^{2}$
Plurality [ Brandt_Conitzer_Endriss_Lang_Procaccia_2016 ]	$(\mathbb{I}\{\sigma(i)=1\})_{i\in\llbracket n\rrbracket}$	$\mathrm{Id}$	$n$
Maximin [ simpson1969 ]	$(\mathbb{I}\{\sigma(i)<\sigma(j)\})_{i<j}$	$\left(\min_{j\neq i}\mathbf{x}_{ij}\right)_{i=1}^{n}$	$n(n-1)/2$

Appendix

Table 1: Common ranking methods expressed in embedding-aggregation form. The map

\phi

encodes a permutation

\sigma\in\mathfrak{S}_{n}

into the embedding space,

\psi

aggregates information into scores, and

|I|

denotes the dimensionality of the embedding.

Panel of Figure 4 — Figure 4: Convergence of consensus methods (Borda, Copeland, Footrule) on rankings sampled from a Mallows model ( $N=151$ agents, $n=8$ items, $\varphi=0.5$ ) across different graph topologies. Results show mean $\pm$ standard deviation over $100$ trials.

Panel of Figure 5 — Figure 5: Score estimation error and consensus quality under the Mallows model ( $N=1000$ voters, $n=7$ alternatives) across four dispersion levels $\varphi\in\{0.3,0.5,0.7,0.9\}$ (columns, left to right). Small $\varphi$ indicates low noise (rankings concentrated near the central order); large $\varphi$ 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_{\tau}(\cdot,\sigma_{\star})$	$\Delta L_{\widehat{P}_{N}}$ w/o Local Kemenization	$\Delta L_{\widehat{P}_{N}}$ w/ Local Kemenization
Borda	$0.25\pm 0.46$	$0.01\pm 0.03$	$0.00\pm 0.00$
Copeland	$0.07\pm 0.26$	$0.00\pm 0.00$	$0.00\pm 0.00$
Footrule	$1.04\pm 0.81$	$0.17\pm 0.17$	$0.00\pm 0.00$
Kemeny	$0.06\pm 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

\sigma_{\star}

under random contamination. Rankings are sampled from a Mallows model (

N=100

n=8

items,

\varphi=0.5

) where

\varepsilon=0.3

of samples are replaced with uniform random permutations. We report the Kendall-tau distance to the ground truth

d_{\tau}(\cdot,\sigma_{\star})

and the excess risk

\Delta L_{\widehat{P}_{N}}

follows the definition in Equation ( 30 ), where

L_{\widehat{P}_{N}}^{\star}

is the Kemeny optimal value for the empirical distribution

\widehat{P}_{N}

. Results show mean

\pm

standard deviation over

100

trials.

Consensus	$d_{\tau}(\cdot,\sigma_{\star})$	$\Delta L_{\widehat{P}_{N}}$ w/o Local Kemenization	$\Delta L_{\widehat{P}_{N}}$ w/ Local Kemenization
Borda	$0.91\pm 0.85$	$0.03\pm 0.04$	$0.00\pm 0.00$
Copeland	$0.59\pm 0.71$	$0.00\pm 0.02$	$0.00\pm 0.01$
Footrule	$1.26\pm 0.99$	$0.13\pm 0.11$	$0.01\pm 0.02$
Kemeny	$0.58\pm 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

\sigma_{\mathrm{rev}}

rather than uniform random permutations.

Experiments	Time to compute
Experiment 5.1 (Debian)	$<5$ min
Experiment 5.1 (Sushi)	$\sim 1$ h
Experiment 5.1 (Mixture of Mallows)	$\sim 15$ min
Experiment 5.2 (Breakdown study)	$\sim 10$ h
Experiment J.1 (Synthetic data with Spearman Footrule)	$\sim 1$ h
Experiment J.2 (Varying dispersion parameter)	$\sim 1$ h $05$

Appendix

Table 4: Time to compute per simulation.

Rank Aggregation

Rank aggregation combines ranked lists or pairwise preferences into a consensus ordering for tasks such as search, recommendation, and model evaluation.

See all 30 papers

Towards Foundation Models for Consensus Rank Aggregation
Mar 16, 2026Yijun Jin, Simon Klüttermann, Chiara Balestra +1Rank Aggregation Transformer
TU Dortmund University, Dortmund, Germany · Research Center Trustworthy Data Science and Security, University Alliance Ruhr, Dortmund, Germany
DeFiRank: Federated Pairwise Ranking for Governance in Decentralized Financial Networks
Oct 9, 2026Zahra Batool, Michael Duchesne, Kaiwen Zhang +1Decentralized Finance Learning to Rank
Ecole de technologie sup´erieure, Montr´eal, Canada · Mila - Quebec AI Institute, Montr´eal, Canada · T-RIZE GROUP, Montr´eal, Canada
Proportionality in Ranking Compression
Oct 16, 2026Daniel Halpern, Xinyu Liu, Evi Micha +2Rank Aggregation
Google Research · U. of Southern California · National University of Singapore

Mar 16, 2026J/K move · Enter open · S save

Towards Foundation Models for Consensus Rank Aggregation

Yijun Jin, Simon Klüttermann, Chiara Balestra, Emmanuel Müller

TU Dortmund University, Dortmund, Germany · Research Center Trustworthy Data Science and Security, University Alliance Ruhr, Dortmund, Germany

Rank Aggregation Transformer

Open paper AskPDF arXiv

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.

Abstract

Rank Aggregation

Explore similar work

Towards Foundation Models for Consensus Rank Aggregation

DeFiRank: Federated Pairwise Ranking for Governance in Decentralized Financial Networks

Proportionality in Ranking Compression