Decentralized Ranking Aggregation: Gossip Algorithms for Borda and Copeland Consensus
| Authors | Anna Van Elst et al. |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2602.22847 |
| Download | |
| Categories | cs.LG, cs.AI, stat.ML |
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 in a decentralized setting, i.e., 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 consensus on collective rankings using classical rules (e.g. Borda, Copeland) 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 random gossip communication, allowing autonomous agents to compute global ranking consensus using only local interactions, without coordination or central authority. We provide rigorous convergence guarantees, including explicit rate bounds, for the Borda and Copeland consensus methods. Beyond these rules, we also provide a decentralized implementation of consensus according to the median rank rule and local Kemenization. Extensive empirical evaluations on various network topologies and real and synthetic ranking datasets demonstrate that our algorithms converge quickly and reliably to the correct ranking aggregation.
Engineering Breakdown
Plain English
This paper solves the problem of computing consensus rankings in decentralized networks where ranking data is distributed across multiple nodes rather than centralized in one location. The authors develop gossip-based algorithms that adapt classical ranking aggregation methods—specifically Borda and Copeland consensus—to work in peer-to-peer, IoT, and multi-agent systems without requiring all data to be moved to a central server. The key insight is that gossip algorithms (where nodes iteratively exchange and update information with neighbors) can converge to the same median ranking across all nodes, providing theoretical guarantees about correctness and convergence speed even when preference data never leaves the distributed network.
Core Technical Contribution
The core novelty is extending two social choice theory ranking aggregation methods (Borda and Copeland) from centralized to decentralized computation through gossip algorithms, with formal convergence proofs. Prior work on decentralized computation focused mainly on statistics (means, sums) and optimization, but not on ranking aggregation which has fundamentally different properties—rankings are discrete, non-Euclidean objects without standard averaging operations. The authors prove that their gossip variants converge to the correct consensus ranking in finite time, even with asynchronous communication and unreliable networks. This is non-trivial because ranking aggregation cannot simply apply standard gossip templates; it requires careful algorithm design specific to how rankings combine and update.
How It Works
The algorithms work by having each node in the network maintain its own local ranking estimate and iteratively communicate with neighboring nodes in a gossip pattern. At each communication round, a node receives ranking information from a random neighbor and updates its local ranking using a modified Borda or Copeland rule that incorporates both its current estimate and the neighbor's estimate. For Borda consensus, nodes track scores for each ranked item and average these scores with neighbors; for Copeland, nodes track pairwise comparisons and aggregate wins across the network. The algorithm repeats these exchanges until all nodes converge to the same consensus ranking, with convergence speed depending on network topology, gossip frequency, and the number of ranked items. The theoretical analysis shows that under standard gossip assumptions (connected graphs, symmetric communication), both algorithms achieve linear convergence rates proportional to the spectral gap of the underlying communication graph.
Production Impact
This directly enables production systems to aggregate preferences without centralizing sensitive ranking data, critical for privacy-preserving recommendation systems, federated voting systems, and collaborative filtering in edge networks. Engineers can deploy ranking aggregation in IoT sensor networks, peer-to-peer applications, and multi-agent systems without building a central aggregation service—reducing latency, eliminating single points of failure, and avoiding data movement costs. The trade-off is increased network communication: each node must exchange messages multiple times to converge, so total bandwidth scales with network size and convergence iterations; in practice this means gossip solutions work best for moderate network sizes (dozens to thousands of nodes) rather than millions. Latency also increases compared to centralized methods since convergence time depends on network diameter and gossip rounds, though this is often acceptable since the computation happens continuously in background; integration complexity is moderate, requiring only local state management and neighbor communication abstractions.
Limitations and When Not to Use This
The paper assumes reliable symmetric communication between neighbors and does not address Byzantine failures or adversarial nodes injecting false rankings, limiting deployment in untrusted networks. Convergence speed degrades significantly on sparse or poorly-connected topologies, and the theoretical guarantees assume static network structure—mobile or frequently-changing networks require additional protocol complexity not addressed here. The approach also assumes all nodes eventually want the same consensus ranking, which breaks down in federated settings where different regions legitimately prefer different rankings or have privacy requirements preventing consensus. Follow-up work is needed on asynchronous gossip variants with weaker synchronization assumptions, convergence under node churn, Byzantine-robust variants, and practical guidance on choosing Borda vs. Copeland based on ranking properties.
Research Context
This work bridges social choice theory (which has decades of research on ranking aggregation) and modern decentralized computing (gossip algorithms, distributed optimization). It builds directly on classical gossip algorithm frameworks used for distributed averaging and optimization, adapting them to the discrete, non-convex setting of ranking aggregation. The research opens a new direction in decentralized preference learning, complementing recent work on federated machine learning and privacy-preserving collaborative systems. The paper likely benchmarks against centralized baselines and naive decentralized approaches, establishing that gossip variants match central computation within reasonable convergence time while avoiding data centralization.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::