Research map / Multi-agent systems and games / Cooperative multi-agent RL

Decentralized Ranking Aggregation via Gossip: Convergence and Robustness

NeurIPS 2026 · Multi-agent systems and games › Cooperative multi-agent RL · approach: Coordination graphs · 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.

Proposes gossip-based decentralized score-based ranking aggregation (Borda, Copeland and others) with exponential convergence bounds in Kendall-tau error and an empirical breakdown-function robustness analysis.

Problem

Computing consensus (median) rankings when preference data is distributed over a communication network without a central aggregator, with convergence guarantees and robustness to corrupted nodes.

Approach

Decompose score-based voting rules as psi(average of phi(sigma_v)) so that nodes can compute the average embedding via gossip averaging and then locally sort the scores; convergence is bounded via a stability radius of the aggregation map, and robustness is characterized by an empirical breakdown function.

Key results

• Gossip-based Borda and Copeland converge exponentially in Kendall-tau error across complete, 2D grid, geometric and Watts-Strogatz topologies; on Sushi and Debian both reach identical consensus.
• Empirical breakdown thresholds for Borda and Copeland (N=3000, n=7, Watts-Strogatz) are substantially higher than the worst-case lower bound epsilon^- from the stability-radius lemma.
• Theoretical bound: average expected Kendall-tau error decays as binom(n,2)/(N r^2) * exp(-sqrt(lambda_W) t) gamma for synchronous Chebyshev-accelerated gossip.

Surprising findings

• Copeland is initially more fragile than Borda under contamination at early iterations but shows lower Kendall-tau error as contamination percolates.
• Breakdown thresholds slightly decrease with t from 7000 to 20000 due to contamination percolation through the network.

Limitations

• Robustness bound degrades as epsilon^- = O(n^{-beta}) with number of alternatives.
• Adversary assumed to follow the averaging protocol; no delayed, selective or adaptive attacks.
• Convergence guarantees are asymptotic; finite-time behavior on sparse graphs may differ.

Experimental setup

Datasets: Mixture of Mallows (synthetic) Sushi (PrefLib) Debian 2005 leader election (PrefLib)

Benchmarks: Sushi Debian 2005 leader election Mixture of Mallows

Metrics: Kendall-tau distance to consensus empirical breakdown curve

Baselines: Borda Copeland

Builds on: gossip averaging Chebyshev acceleration Kemeny consensus Mallows model

Closest papers by meaning

• Robust Consensus in Ranking Data Analysis: Definitions, Properties and Computational Issues (ICML 2023 · similarity 0.88)
• Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means (NeurIPS 2025 · similarity 0.87)
• Beyond Kemeny Medians: Consensus Ranking Distributions. Definition, Properties and Statistical Learning (NeurIPS 2026 · similarity 0.87)
• Unified Breakdown Analysis for Byzantine Robust Gossip (ICML 2025 · similarity 0.86)
• Selective Preference Aggregation (ICML 2025 · similarity 0.85)
• Stability and Multigroup Fairness in Ranking with Uncertain Predictions (ICML 2024 · similarity 0.84)