論文の概要: Decentralized Ranking Aggregation: Gossip Algorithms for Borda and Copeland Consensus

• arxiv url: http://arxiv.org/abs/2602.22847v1
• Date: Thu, 26 Feb 2026 10:37:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-27 18:41:22.649155
• Title: Decentralized Ranking Aggregation: Gossip Algorithms for Borda and Copeland Consensus
• Title（参考訳）: 分散ランキングアグリゲーション:ボルダとコペランドの合意のためのゴシップアルゴリズム
• Authors: Anna Van Elst, Kerrian Le Caillec, Igor Colin, Stephan Clémençon,
• Abstract要約: 我々は,古典的ルールを分散した環境で,集団ランキングに関する信頼性の高いコンセンサスを実現する方法について検討する。 我々はボルダとコープランドのコンセンサス法に対して、明示的なレート境界を含む収束保証を提供する。 我々のアルゴリズムは、正しいランキングアグリゲーションに迅速かつ確実に収束する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: ランキングアグリゲーションの概念は選好分析において中心的な役割を担い、社会選択理論でしばしば生じる中央値ランキングを計算するアルゴリズムが文献に記録されており、集約されるすべてのランキングデータを単一の計算ユニットにまとめることができるような集中的な環境で理論的な保証を提供している。 多くの技術(例えばピアツーピアネットワーク、IoT、マルチエージェントシステム)では、分散化された環境で保証されたコンセンサスランキングを計算する能力が拡張されている。 実際、近年、分散化された計算に関する文献は、主にゴシップアルゴリズムを用いて計算や算術などの統計を最適化することに焦点を当てている。 本稿の目的は,古典的ルール(例えばボルダ,コペランド)を用いて,分散化された環境での集合的ランキングに対する信頼性の高いコンセンサスを実現する方法を検討することである。 ここで提案され分析されたアプローチは、ランダムなゴシップ通信に依存しており、自律エージェントは、調整や中央の権限なしに、局所的な相互作用のみを使用して、グローバルなランキングコンセンサスを計算することができる。 我々はボルダとコペランドのコンセンサス法に対して、明示的なレート境界を含む厳密な収束保証を提供する。 これらのルールを超えて、中央の階級ルールと局所的なケメン化に従って、コンセンサスの分散的な実装も提供します。 様々なネットワークトポロジおよび実・合成ランキングデータセットに対する広範囲な実験的な評価は、アルゴリズムが正しいランキングアグリゲーションに迅速かつ確実に収束することを証明している。

関連論文リスト

• Asynchronous Gossip Algorithms for Rank-Based Statistical Methods [2.6636053598505307]
  ウィルコクソンランクサム検定のための最初のゴシップアルゴリズムを提案する。 非同期ゴシップに基づくランク推定のための第1収束率を含む厳密な収束保証を提供する。
  論文  参考訳（メタデータ） (2025-09-09T09:23:36Z)
• An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks [8.319127681936815]
  そこで本研究では,$k$の偏光コミュニティを同定する手法を提案する。 サイズ不均衡な解を避けるための新しい最適化手法を提案する。 実世界のデータセットと合成データセットの実験は、我々の手法がソリューション品質の最先端のベースラインを一貫して上回っていることを示している。
  論文  参考訳（メタデータ） (2025-02-04T10:22:01Z)
• Networked Communication for Mean-Field Games with Function Approximation and Empirical Mean-Field Estimation [59.01527054553122]
  分散エージェントは、経験的システムの非絶対的実行から平均フィールドゲームにおいて平衡を学ぶことができる。 既存の設定に関数近似を導入し,Munchausen Online Mirror Descent 方式で描画する。 ポリシー情報の交換は,ネットワーク化されたエージェントが,機能近似設定において,独立エージェントと集中エージェントの両方より優れていることを示す。
  論文  参考訳（メタデータ） (2024-08-21T13:32:46Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  我々は、不均一(非IID)で多くのデバイスに分散する問題データを持つ領域上での分散変分不等式(VIs)を考察する。 我々は、完全に分散化された計算の設定を網羅する計算ネットワークについて、非常に一般的な仮定を行う。 理論的には, モノトン, モノトンおよび非モノトンセッティングにおける収束速度を理論的に解析する。
  論文  参考訳（メタデータ） (2021-06-15T17:45:51Z)
• DeEPCA: Decentralized Exact PCA with Linear Convergence Rate [26.819982387028595]
  textttDe EPCAは、ターゲット精度に依存しない各パワーに対する通信ラウンド数を持つ最初の分散PCAアルゴリズムである。 既存のアルゴリズムと比較して,提案手法は実際のチューニングが容易であり,全体の通信コストが向上する。
  論文  参考訳（メタデータ） (2021-02-08T03:53:09Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。 本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。 当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
  論文  参考訳（メタデータ） (2020-04-17T14:56:29Z)
• Quantized Decentralized Stochastic Learning over Directed Graphs [54.005946490293496]
  有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。 モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。 本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-23T18:25:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。