論文の概要: Efficient Lower Bounding of Single Transferable Vote Election Margins

• arxiv url: http://arxiv.org/abs/2501.14847v1
• Date: Fri, 24 Jan 2025 13:39:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-28 13:56:57.085346
• Title: Efficient Lower Bounding of Single Transferable Vote Election Margins
• Title（参考訳）: シングルトランスファーブル投票マージンの高効率下界化
• Authors: Michelle Blom, Alexander Ek, Peter J. Stuckey, Vanessa Teague, Damjan Vukcevic,
• Abstract要約: STV (Single Transferable vote) は、複数議席の選挙において、優先的な比例投票方式である。 勝利のマージン(英: margin of victory)または単にマージン(英: margin)は、もし操作された場合、勝者の集合を変えることができる最小数の投票である。 マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。
• 参考スコア（独自算出の注目度）: 56.12949230611067
• License:
• Abstract: The single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections. Each ballot cast by a voter is a (potentially partial) ranking over a set of candidates. The margin of victory, or simply margin, is the smallest number of ballots that, if manipulated (e.g., their rankings changed, or ballots being deleted or added), can alter the set of winners. Knowledge of the margin of an election gives greater insight into both how much time and money should be spent on auditing the election, and whether uncovered mistakes (such as ballot box losses) throw the election result into doubt -- requiring a costly repeat election -- or can be safely ignored. Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute. There is one existing approach to computing lower bounds on the margin of STV elections, while there are multiple approaches to finding upper bounds. In this paper, we present improvements to this existing lower bound computation method for STV margins. In many cases the improvements compute tighter (higher) lower bounds as well as making the computation of lower bounds more computationally efficient. For small elections, in conjunction with existing upper bounding approaches, the new algorithms are able to compute exact margins of victory.
• Abstract（参考訳）: STV (Single transferable voting) は、複数議席制の選挙において、優先的な比例投票方式である。 投票者によって投じられた各投票は、候補者のセットに対して(潜在的に部分的に)ランク付けされる。 勝利のマージン(英: margin of victory)または単にマージン(英: margin)は、操作された場合(例えば、ランキングが変更されたり、投票が削除または追加されたり)、勝者の集合を変更することができる最小数の投票である。 選挙の利益率に関する知識は、選挙の監査にどれだけの時間とお金が費やされるべきか、そして、未公表の誤り(投票箱の損失など)が選挙結果に疑念を抱かせるか(費用がかかる選挙が必要)、あるいは安全に無視されるかの両方について、より深い洞察を与える。 マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。 STV選挙の限界における下位境界の計算には1つの既存のアプローチがあるが、上位境界の探索には複数のアプローチがある。 本稿では,STVマージンに対する既存の下界計算法の改良について述べる。 多くの場合、改善はより厳密な(より高い)下限を計算し、下限の計算をより効率的にする。 小規模な選挙では、既存の上限付けのアプローチとともに、新しいアルゴリズムは勝利のマージンを正確に計算することができる。

関連論文リスト

• Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
  AWAIREは、任意の数の候補でIRVコンテストを監査できるが、当初の実装では、候補数とともに指数関数的に増加するメモリと計算コストが増大していた。 本稿では,従来の6候補と比較して,55候補のIRVコンテストを実際に実施する3つの方法で,AWAIREのアルゴリズム実装を改善した。
  論文  参考訳（メタデータ） (2024-07-23T13:28:00Z)
• Ahead of the Count: An Algorithm for Probabilistic Prediction of Instant Runoff (IRV) Elections [0.0]
  Instant Runoff Voting (IRV) 選挙の結果を予測する新しいアルゴリズムを提案する。 アルゴリズムは、各候補ランキングの投票総数を表す離散確率分布の集合を入力として取る。 IRVラウンドで発生する可能性のあるすべての除去シーケンスを計算し、それぞれに確率を割り当てる。
  論文  参考訳（メタデータ） (2024-05-15T00:25:51Z)
• Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
  AWAIREは、適応的に重み付けされたテスト統計量であり、本質的には、テストに有効な仮説のセットを「学習」する。 我々は、より広範囲にスキームと設定を検討し、実践のための効率的な選択を特定し、推奨する。 現在のAWAIRE実装の制限は、少数の候補者に限られている。
  論文  参考訳（メタデータ） (2024-02-18T10:13:01Z)
• Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
  即時投票(IRV)選挙の監査方法は、リスク制限や、各投票における投票の電子的記録であるキャスト投票記録(CVR)を必要とするものではない。 我々は,CVRが利用できない場合に,適応的に重み付けされたテストスーパーマーチンガルを用いてITV選挙を効率よく監査するRLA手法を開発した。
  論文  参考訳（メタデータ） (2023-07-20T15:55:34Z)
• Accelerating Voting by Quantum Computation [35.03314687289671]
  本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。 我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
  論文  参考訳（メタデータ） (2023-01-08T07:29:38Z)
• Auditing Ranked Voting Elections with Dirichlet-Tree Models: First Steps [23.14629947453497]
  ランク付けされた投票システムは世界中の多くの場所で使用されている。 フルハンドカウント以外に、STVのリスク制限監査(RLA)手法は知られていない。 本稿では,高次元パラメータを計算的に効率的に扱える統計モデルDirichlet-treeを用いたランキングシステムの監査手法を提案する。
  論文  参考訳（メタデータ） (2022-06-29T13:06:42Z)
• Identifying Possible Winners in Ranked Choice Voting Elections with Outstanding Ballots [0.0]
  ランク選択投票(Crown-choice voting、RCV)は、投票者が自分の選択をランク付けでき、その結果はラウンドで計算される。 RCVの選挙結果は、必ずしも選挙の夜には明らかではなく、出版までに数週間かかる可能性がある。 本稿では,一部の投票者によるRCV選挙の勝者を効率よく計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-25T22:08:15Z)
• Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [58.23459346724491]
  我々は、Szufa et al.(AAMAS 2020)の「選挙マップ」アプローチを用いて、よく知られた投票分布を分析します。 分布の「スケルトン写像」を描き、その頑健さを評価し、その性質を分析する。
  論文  参考訳（メタデータ） (2022-05-16T17:40:22Z)
• A First Approach to Risk-Limiting Audits for Single Transferable Vote Elections [27.102139020324678]
  リスク制限監査(RLA)は、報告された選挙結果が実際正しいことを確認するための、ますます重要な方法である。 本稿では,STV選挙におけるリスク限度監査に対する最初のアプローチを提案する。
  論文  参考訳（メタデータ） (2021-12-18T12:36:39Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  有権者が承認投票(すなわち、承認した候補者の集合)を投じた場合のマルチウィナー選挙における贈収賄の問題を研究する。 我々は、いくつかの承認ベースのマルチウィナールール(AV、SAV、GAV、RAV、承認ベースのチェンバリン--Courant、およびPAV)を検討します。 一般に、我々の問題は、勝利した委員会の候補者の承認数を増やすための贈収賄行為を制限した場合、より容易になる傾向がある。
  論文  参考訳（メタデータ） (2021-04-19T08:26:40Z)

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

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