論文の概要: Stable Voting and the Splitting of Cycles

• arxiv url: http://arxiv.org/abs/2512.00616v1
• Date: Sat, 29 Nov 2025 20:13:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:34.327417
• Title: Stable Voting and the Splitting of Cycles
• Title（参考訳）: 安定投票とサイクル分割
• Authors: Wesley H. Holliday, Milan Mossé, Chase Norman, Eric Pacuit, Cynthia Wang,
• Abstract要約: 我々は、単純安定投票の予想を証明し、6つ以上の代替案に対して反論する。 この証明と反例に基づくSATの符号化は、SCやSSVよりもはるかに遠い範囲で適用できる。
• 参考スコア（独自算出の注目度）: 2.689666916482036
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithms for resolving majority cycles in preference aggregation have been studied extensively in computational social choice. Several sophisticated cycle-resolving methods, including Tideman's Ranked Pairs, Schulze's Beat Path, and Heitzig's River, are refinements of the Split Cycle (SC) method that resolves majority cycles by discarding the weakest majority victories in each cycle. Recently, Holliday and Pacuit proposed a new refinement of Split Cycle, dubbed Stable Voting, and a simplification thereof, called Simple Stable Voting (SSV). They conjectured that SSV is a refinement of SC whenever no two majority victories are of the same size. In this paper, we prove the conjecture up to 6 alternatives and refute it for more than 6 alternatives. While our proof of the conjecture for up to 5 alternatives uses traditional mathematical reasoning, our 6-alternative proof and 7-alternative counterexample were obtained with the use of SAT solving. The SAT encoding underlying this proof and counterexample is applicable far beyond SC and SSV: it can be used to test properties of any voting method whose choice of winners depends only on the ordering of margins of victory by size.
• Abstract（参考訳）: 選好集約における多数決サイクルの解消のためのアルゴリズムは、計算社会選択において広範囲に研究されている。 Tideman's Ranked Pairs、Schulze's Beat Path、Heitzig's Riverなどの洗練されたサイクル解決手法は、各サイクルで最も弱い多数派を排除して多数派を解消するSplit Cycle (SC)法の改良である。 近年、ホリデイとパクイットはスプリット・サイクルを改良し、安定投票(stable Voting)、単純投票(Simple Staable Voting、SSV)と呼ばれる単純化を提案した。 彼らは、2つの過半数の勝利が同じ大きさである場合、SSV は SC の洗練であると予想した。 本稿では、この予想を6つの代替案まで証明し、6つ以上の代替案に対して反証する。 従来の数学的推論では, 最大5つの仮説の証明が用いられているが, SAT法を用いて6-代替的証明と7-代替的反例が得られた。 この証明と反例に基づくSATの符号化は、SC や SSV よりもはるかに遠い範囲で適用可能であり、勝者の選択が勝利率の順序にのみ依存する任意の投票方法の特性をテストするのに使用できる。

関連論文リスト

• Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
  STV (Single Transferable vote) は、複数議席の選挙において、優先的な比例投票方式である。 勝利のマージン(英: margin of victory)は、勝利者の集合を変えるために操作される必要のある最小数の投票である。 マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。
  論文  参考訳（メタデータ） (2025-01-24T13:39:23Z)
• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIREは、任意の数の候補でIRVコンテストを監査できるが、当初の実装では、候補数とともに指数関数的に増加するメモリと計算コストが増大していた。 本稿では,従来の6候補と比較して,55候補のIRVコンテストを実際に実施する3つの方法で,AWAIREのアルゴリズム実装を改善した。
  論文  参考訳（メタデータ） (2024-07-23T13:28:00Z)
• Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
  AWAIREは、適応的に重み付けされたテスト統計量であり、本質的には、テストに有効な仮説のセットを「学習」する。 我々は、より広範囲にスキームと設定を検討し、実践のための効率的な選択を特定し、推奨する。 現在のAWAIRE実装の制限は、少数の候補者に限られている。
  論文  参考訳（メタデータ） (2024-02-18T10:13:01Z)
• DCR: Divide-and-Conquer Reasoning for Multi-choice Question Answering with LLMs [9.561022942046279]
  大規模言語モデル(LLM)の推論能力を高めるため,DCR(Divide and Conquer Reasoning)を提案する。 まず、信頼性スコア(mathcalCS$)に基づいて質問を2つのサブセットに分類する。 特に,質問を信頼性スコア(mathcalCS$)に基づいて2つのサブセットに分類する。
  論文  参考訳（メタデータ） (2024-01-10T14:38:46Z)
• Accelerating Voting by Quantum Computation [35.03314687289671]
  本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。 我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
  論文  参考訳（メタデータ） (2023-01-08T07:29:38Z)
• The Complexity of Learning Approval-Based Multiwinner Voting Rules [9.071560867542647]
  本研究は,ABCS(承認ベース委員会スコアリング)ルールのクラスに着目し,マルチウィンナ投票の学習可能性について検討する。 我々のゴールは、少数のプロファイルの勝利委員会に関する情報を用いて、ターゲットルール(すなわち、対応するスコアリング機能を学ぶこと)を学ぶことである。 我々は、ある委員会に与えられたプロファイルで勝利させるABCSルールが存在するかどうかを判断することが難しいことを証明している。
  論文  参考訳（メタデータ） (2021-10-01T08:25:05Z)
• Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
  シュルツ法(schulze method)と呼ばれる,有名な単勝投票ルールの計算的側面について検討した。 私たちの論文は、計算社会的選択の分野に微細な複雑さをもたらす最初のものです。
  論文  参考訳（メタデータ） (2021-03-05T22:27:36Z)

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

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