論文の概要: Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion

• arxiv url: http://arxiv.org/abs/2610.24456v1
• Date: Sat, 17 Oct 2026 04:52:34 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 12:00:15.575183
• Title: Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
• Title（参考訳）: 木質多孔性ベト:効率的なコミュニケーションと低メートル歪みを伴う数ラウンドでの投票
• Abstract要約: 投票規則は、有権者の序列選好のみを用いて候補者を選択し、その歪みは、選択された候補者の社会的コストと最小の社会的コストとの最悪のケース比である。 低歪みの決定論的投票プロトコルにおける全通信に対するラウンド複雑性のトレードオフについて検討する。
• 参考スコア（独自算出の注目度）: 7.3027195503125375
• License:
• Abstract: We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a matching-based analysis shows that each level increases the distortion bound by at most $2$.
• Abstract（参考訳）: 我々は、投票のためのメートル法歪みフレームワークを考え、そこでは、$n$の有権者と$m$の候補者が未知のメートル法空間に埋め込まれている。 投票規則は、有権者の序列選好のみを用いて候補者を選択し、その歪みは、選択された候補者の社会的コストと最小の社会的コストとの最悪のケース比である。 低歪みの決定論的投票プロトコルにおける全通信に対するラウンド複雑性のトレードオフについて検討する。 決定論的規則は、$(nm\log)を用いて完全なランク付けを行うことで、1ラウンドで3ドルを最適に歪めることができる。 m)$ bits, while a direct sequence implementation of PluralityVeto is a same distortion using only $O(n\log). m)$ bits, but requires $... (n)$ラウンド。 このプロトコルは最大$r$ラウンドと$O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, ここで$s = \min\{n, m\}$。 このプロトコルは有権者の階層的な分割でPluralityVetoを実行し、各レベルで制限されたランクを並列に収集する。 分岐係数は、ラウンドと通信の間のトレードオフを制御し、マッチングベースの分析により、各レベルが少なくとも2ドル以上の歪みを増大させることを示す。

関連論文リスト

• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• The End Justifies the Mean: A Linear Ranking Rule for Proportional Sequential Decisions [12.640117499079063]
  我々は、繰り返し使用する決定ルールを集合的に選択する方法を研究する。 デフォルトのルールである$(i)$の算術平均は、非常に大義的であることが示されている。 固定線形ルールでは、正確なバッチ毎IPは不可能であるが、バッチ毎IPと長時間IPのギャップはバッチサイズとともに急速に縮小する。
  論文  参考訳（メタデータ） (2026-05-12T20:26:37Z)
• Best-of-Majority: Minimax-Optimal Strategy for Pass@$k$ Inference Scaling [54.50689440956967]
  LLM推論は、しばしばプロンプトの一連の候補を生成し、多数決やBest-of-N (BoN)のような戦略を介して1つを選択する。 我々は,最上位の$k$報酬を選択する前に,上位の$N$サンプルにおいて,高い周波数の応答を候補に限定するピボットステップを備えたBest-of-Majority (BoM)を提案する。 多数決とBoNとは異なり、BoMは重要な利点がある:多数決とBoNとは異なり、そのパフォーマンスはN$を上昇しても低下しない。
  論文  参考訳（メタデータ） (2025-10-03T17:35:45Z)
• Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
  我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。 PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。 我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2025-07-15T20:19:32Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。 我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。 MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
  論文  参考訳（メタデータ） (2024-05-08T02:17:10Z)
• Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion [11.282341369957212]
  メートル法歪みの枠組み nの有権者とmの候補者は 共同でメートル法空間に埋め込まれている 投票ルールの目的は、投票者に対して最短距離の候補者を選ぶことである。 Plurality Veto と呼ばれる単純な投票法則が 3 の最適歪みを達成することを示す。
  論文  参考訳（メタデータ） (2022-06-14T18:32:32Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• Resolving the Optimal Metric Distortion Conjecture [27.344649091365067]
  以下の計量歪み問題を考察する。 点の有限集合である$V$と$C$は、同じ距離空間にある。 我々はこれらのランキングのみを入力として、$C$のポイントを選択するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-16T04:13:06Z)

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

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