論文の概要: Determining Winners in Elections with Absent Votes
- arxiv url: http://arxiv.org/abs/2310.07150v1
- Date: Wed, 11 Oct 2023 02:52:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-13 00:46:35.284068
- Title: Determining Winners in Elections with Absent Votes
- Title(参考訳): 無投票選挙における勝者決定
- Authors: Qishen Han and Am\'elie Marian and Lirong Xia
- Abstract要約: 我々は、投票が最上位の場合に、不在の投票問題で決定的な勝者を調査する。
単一の投票でWAV問題はNP完全であることを示す。
本稿では、時間内に問題を計算できるように、位置スコアリングルールの特別な場合を提案する。
- 参考スコア(独自算出の注目度): 26.675597212113658
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An important question in elections is the determine whether a candidate can
be a winner when some votes are absent. We study this determining winner with
the absent votes (WAV) problem when the votes are top-truncated. We show that
the WAV problem is NP-complete for the single transferable vote, Maximin, and
Copeland, and propose a special case of positional scoring rule such that the
problem can be computed in polynomial time. Our results in top-truncated
rankings differ from the results in full rankings as their hardness results
still hold when the number of candidates or the number of missing votes are
bounded, while we show that the problem can be solved in polynomial time in
either case.
- Abstract(参考訳): 選挙における重要な質問は、候補者が不在時に勝者になれるかどうかを決定することである。
投票が最上位の場合に、不在得票(WAV)問題でこの決定的勝者について検討する。
本報告では,wav問題は1票,最大票,コープランドに対してnp完全であることを示すとともに,多項式時間で計算可能な位置採点規則の特別な場合を提案する。
最上位のランキングにおける結果は,候補者数や欠落票数に制限がある場合,その難易度は依然として保持されるが,いずれの場合においても多項式時間で解くことができることを示すため,全ランキングの結果と異なる。
関連論文リスト
- Verifying Proportionality in Temporal Voting [29.69443607539022]
本研究では,時間的地平線が一定である時間的投票モデルについて検討し,各投票ラウンドにおいて,候補者に対する選好を報告する。
与えられた結果が比例表現を提供するかどうかを検証する複雑さに焦点を当てる。
論文 参考訳(メタデータ) (2025-02-09T16:30:34Z) - Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
STV (Single Transferable vote) は、複数議席の選挙において、優先的な比例投票方式である。
勝利のマージン(英: margin of victory)または単にマージン(英: margin)は、もし操作された場合、勝者の集合を変えることができる最小数の投票である。
マージンの低い境界は、正確なマージンを計算するのが難しい場合、この目的のためにも使われる。
論文 参考訳(メタデータ) (2025-01-24T13:39:23Z) - Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
我々は、投票者が何回も不満を抱いていないことを保証し、永遠の投票方法を考える。
我々は、不満のサブ線形成長が可能な有権者行動に関する十分な条件を特定する。
本稿では,専門家の助言による予測から得られた標準手法に基づいて,紛争条件下での不満をサブ線形に保証する投票手法を提案する。
論文 参考訳(メタデータ) (2024-12-20T19:58:55Z) - Improving the Computational Efficiency of Adaptive Audits of IRV Elections [54.427049258408424]
AWAIREは、任意の数の候補でIRVコンテストを監査できるが、当初の実装では、候補数とともに指数関数的に増加するメモリと計算コストが増大していた。
本稿では,従来の6候補と比較して,55候補のIRVコンテストを実際に実施する3つの方法で,AWAIREのアルゴリズム実装を改善した。
論文 参考訳(メタデータ) (2024-07-23T13:28:00Z) - Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
即時投票(IRV)選挙の監査方法は、リスク制限や、各投票における投票の電子的記録であるキャスト投票記録(CVR)を必要とするものではない。
我々は,CVRが利用できない場合に,適応的に重み付けされたテストスーパーマーチンガルを用いてITV選挙を効率よく監査するRLA手法を開発した。
論文 参考訳(メタデータ) (2023-07-20T15:55:34Z) - 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) - The Complexity of Learning Approval-Based Multiwinner Voting Rules [9.071560867542647]
本研究は,ABCS(承認ベース委員会スコアリング)ルールのクラスに着目し,マルチウィンナ投票の学習可能性について検討する。
我々のゴールは、少数のプロファイルの勝利委員会に関する情報を用いて、ターゲットルール(すなわち、対応するスコアリング機能を学ぶこと)を学ぶことである。
我々は、ある委員会に与えられたプロファイルで勝利させるABCSルールが存在するかどうかを判断することが難しいことを証明している。
論文 参考訳(メタデータ) (2021-10-01T08:25:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。