論文の概要: Bribery as a Measure of Candidate Success: Complexity Results for
Approval-Based Multiwinner Rules
- arxiv url: http://arxiv.org/abs/2104.09130v1
- Date: Mon, 19 Apr 2021 08:26:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-20 13:39:20.483757
- Title: Bribery as a Measure of Candidate Success: Complexity Results for
Approval-Based Multiwinner Rules
- Title（参考訳）: 候補者成功の指標としての贈賄:承認型マルチウィンナールールの複雑度結果
- Authors: Piotr Faliszewski and Piotr Skowron and Nimrod Talmon
- Abstract要約: 有権者が承認投票(すなわち、承認した候補者の集合)を投じた場合のマルチウィナー選挙における贈収賄の問題を研究する。
我々は、いくつかの承認ベースのマルチウィナールール(AV、SAV、GAV、RAV、承認ベースのチェンバリン--Courant、およびPAV)を検討します。
一般に、我々の問題は、勝利した委員会の候補者の承認数を増やすための贈収賄行為を制限した場合、より容易になる傾向がある。
- 参考スコア（独自算出の注目度）: 58.8640284079665
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of bribery in multiwinner elections, for the case where
the voters cast approval ballots (i.e., sets of candidates they approve) and
the bribery actions are limited to: adding an approval to a vote, deleting an
approval from a vote, or moving an approval within a vote from one candidate to
the other. We consider a number of approval-based multiwinner rules (AV, SAV,
GAV, RAV, approval-based Chamberlin--Courant, and PAV). We find the landscape
of complexity results quite rich, going from polynomial-time algorithms through
NP-hardness with constant-factor approximations, to outright inapproximability.
Moreover, in general, our problems tend to be easier when we limit out bribery
actions on increasing the number of approvals of the candidate that we want to
be in a winning committee (i.e., adding approvals only for this preferred
candidate, or moving approvals only to him or her). We also study parameterized
complexity of our problems, with a focus on parameterizations by the numbers of
voters or candidates.
- Abstract（参考訳）: 複数人の選挙における贈収賄の問題について検討する。投票者が承認票(すなわち、承認した候補者の集合)を投じた場合と、贈収賄行動は、投票に承認を加えること、投票から承認を取り消すこと、または、ある候補者から別の候補者に承認を移すことである。
承認ベースマルチウィンナルール(AV, SAV, GAV, RAV, 承認ベースCurberlin-Courant, PAV)について検討する。
多項式時間アルゴリズムから定数係数近似によるNPハードネスから、完全不近似まで、複雑性の展望は非常にリッチである。
さらに、一般には、勝利した委員会に指名したい候補者の承認数を増やすための贈収賄行為を制限した場合、我々の問題はより容易になる傾向がある(すなわち、この望ましい候補者にのみ承認を加えるか、あるいは承認を彼または彼女だけに移す)。
また,問題のパラメータ化複雑性についても検討し,投票者数や候補者数によるパラメータ化に着目した。
関連論文リスト
- 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) - Multiwinner Temporal Voting with Aversion to Change [30.15852603215344]
我々は、有権者が候補者よりもダイナミックに選好する2段階の委員会選挙を調査する。
各段階において、委員会は所定の投票規則の下で選ばれる。
ティーレ則のクラスに対する完全複雑性二分法を示す。
論文 参考訳（メタデータ） (2024-08-20T17:16:54Z) - 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) - Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
即時投票(IRV)選挙の監査方法は、リスク制限や、各投票における投票の電子的記録であるキャスト投票記録(CVR)を必要とするものではない。
我々は,CVRが利用できない場合に,適応的に重み付けされたテストスーパーマーチンガルを用いてITV選挙を効率よく監査するRLA手法を開発した。
論文 参考訳（メタデータ） (2023-07-20T15:55:34Z) - On the Complexity of Winner Determination and Strategic Control in
Conditional Approval Voting [13.207754600697138]
条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。
我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
論文 参考訳（メタデータ） (2022-02-03T16:15:54Z) - The Complexity of Learning Approval-Based Multiwinner Voting Rules [9.071560867542647]
本研究は,ABCS(承認ベース委員会スコアリング)ルールのクラスに着目し,マルチウィンナ投票の学習可能性について検討する。
我々のゴールは、少数のプロファイルの勝利委員会に関する情報を用いて、ターゲットルール(すなわち、対応するスコアリング機能を学ぶこと)を学ぶことである。
我々は、ある委員会に与えられたプロファイルで勝利させるABCSルールが存在するかどうかを判断することが難しいことを証明している。
論文 参考訳（メタデータ） (2021-10-01T08:25:05Z) - Modeling Voters in Multi-Winner Approval Voting [24.002910959494923]
我々は,不確実性の度合いの異なる単入投票と多入投票の投票行動について検討した。
概して、人々はより良い結果を得るために投票を操作しているが、しばしば最適な操作を特定できない。
本稿では,勝利集合の大きさと人間の認知的制約を考慮に入れた新しいモデルを提案する。
論文 参考訳（メタデータ） (2020-12-04T19:24:28Z) - Evaluating approval-based multiwinner voting in terms of robustness to
noise [10.135719343010177]
承認ベースのマルチウィンナー投票は常に妥当な雑音に対して堅牢であることを示す。
ノイズに対する頑丈さの観点から、ルールの階層構造を提示することで、この発見をさらに洗練します。
論文 参考訳（メタデータ） (2020-02-05T13:17:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。