Search papers, labs, and topics across Lattice.
This paper addresses the challenge of decentralized ranking aggregation, crucial for technologies like peer-to-peer networks and multi-agent systems, by extending classical ranking rules (Borda, Copeland) to distributed settings. The authors propose a gossip-based algorithm where autonomous agents compute global ranking consensus through local interactions, achieving robustness and scalability. They provide rigorous convergence guarantees and explicit rate bounds for Borda and Copeland consensus, validated through empirical evaluations on diverse datasets and network topologies.
Achieve reliable ranking consensus in decentralized systems with provable convergence guarantees using gossip algorithms for Borda and Copeland rules.
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.
