Decentralized Ranking Aggregation: Gossip Algorithms for Borda and Copeland Consensus

• URL: http://arxiv.org/abs/2602.22847v1
• Date: Thu, 26 Feb 2026 10:37:23 GMT
• Title: Decentralized Ranking Aggregation: Gossip Algorithms for Borda and Copeland Consensus
• Abstract summary: We study how to achieve reliable consensus on collective rankings using classical rules in a decentralized setting.<n>We provide convergence guarantees, including explicit rate bounds, for the Borda and Copeland consensus methods.<n>Our algorithms converge quickly and reliably to the correct ranking aggregation.
• Score: 2.4382430407654767
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• On Gossip Algorithms for Machine Learning with Pairwise Objectives [17.859587616935002]
  In the IoT era, information is more and more frequently picked up by connected smart sensors with increasing, though limited, storage, communication and computation abilities.<n>The development of statistical learning methods dedicated to data that are shared over a network is now a major issue.<n>Gossip-based algorithms have been developed for the purpose of solving a wide variety of statistical learning tasks.
  arXiv  Detail & Related papers  (2026-03-25T09:43:17Z)
• Robust Distributed Learning under Resource Constraints: Decentralized Quantile Estimation via (Asynchronous) ADMM [2.6636053598505307]
  We propose AsylADMM, a novel gossip algorithm for decentralized median and quantile estimation.<n>We show that our algorithm enables quantile-based trimming, geometric median estimation, and depth-based trimming.
  arXiv  Detail & Related papers  (2026-01-28T13:09:10Z)
• Asynchronous Gossip Algorithms for Rank-Based Statistical Methods [2.6636053598505307]
  We introduce the first gossip algorithm for Wilcoxon rank-sum tests.<n>We provide rigorous convergence guarantees, including the first convergence rate bound for asynchronous gossip-based rank estimation.
  arXiv  Detail & Related papers  (2025-09-09T09:23:36Z)
• An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks [8.319127681936815]
  We propose a method for identifying $k$ polarized communities.<n>We introduce a novel optimization objective that avoids size-imbalanced solutions.<n> Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-art baselines in solution quality.
  arXiv  Detail & Related papers  (2025-02-04T10:22:01Z)
• Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration [66.43954501171292]
  We introduce Catalyst Acceleration and propose an acceleration Decentralized Federated Learning algorithm called DFedCata. DFedCata consists of two main components: the Moreau envelope function, which addresses parameter inconsistencies, and Nesterov's extrapolation step, which accelerates the aggregation phase. Empirically, we demonstrate the advantages of the proposed algorithm in both convergence speed and generalization performance on CIFAR10/100 with various non-iid data distributions.
  arXiv  Detail & Related papers  (2024-10-09T06:17:16Z)
• Networked Communication for Mean-Field Games with Function Approximation and Empirical Mean-Field Estimation [59.01527054553122]
  Decentralised agents can learn equilibria in Mean-Field Games from a non-episodic run of the empirical system.<n>We introduce function approximation to the existing setting, drawing on the Munchausen Online Mirror Descent method.<n>We show theoretically that exchanging policy information helps networked agents outperform both independent and even centralised agents in function-approximation settings.
  arXiv  Detail & Related papers  (2024-08-21T13:32:46Z)
• Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacy [86.61829236732744]
  This work considers the problem of Distributed Mean Estimation (DME) over networks with intermittent connectivity. The goal is to learn a global statistic over the data samples localized across distributed nodes with the help of a central server. We study the tradeoff between collaborative relaying and privacy leakage due to the additional data sharing among nodes.
  arXiv  Detail & Related papers  (2023-02-28T19:17:03Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  We consider distributed variational inequalities (VIs) on domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that covers the settings of fully decentralized calculations. We theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone settings.
  arXiv  Detail & Related papers  (2021-06-15T17:45:51Z)
• DeEPCA: Decentralized Exact PCA with Linear Convergence Rate [26.819982387028595]
  textttDe EPCA is the first decentralized PCA algorithm with the number of communication rounds for each power independent of target precision. Compared to existing algorithms, the proposed method is easier to tune in practice, with an improved overall communication cost.
  arXiv  Detail & Related papers  (2021-02-08T03:53:09Z)
• Determinantal consensus clustering [77.34726150561087]
  We propose the use of determinantal point processes or DPP for the random restart of clustering algorithms. DPPs favor diversity of the center points within subsets. We show through simulations that, contrary to DPP, this technique fails both to ensure diversity, and to obtain a good coverage of all data facets.
  arXiv  Detail & Related papers  (2021-02-07T23:48:24Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)
• Quantized Decentralized Stochastic Learning over Directed Graphs [54.005946490293496]
  We consider a decentralized learning problem where data points are distributed among computing nodes communicating over a directed graph.<n>As the model size gets large, decentralized learning faces a major bottleneck that is the communication load due to each node transmitting messages (model updates) to its neighbors.<n>We propose the quantized decentralized learning algorithm over directed graphs that is based on the push-sum algorithm in decentralized consensus optimization.
  arXiv  Detail & Related papers  (2020-02-23T18:25:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.