論文の概要: 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ハードネスから、完全不近似まで、複雑性の展望は非常にリッチである。
さらに、一般には、勝利した委員会に指名したい候補者の承認数を増やすための贈収賄行為を制限した場合、我々の問題はより容易になる傾向がある(すなわち、この望ましい候補者にのみ承認を加えるか、あるいは承認を彼または彼女だけに移す)。
また,問題のパラメータ化複雑性についても検討し,投票者数や候補者数によるパラメータ化に着目した。
関連論文リスト
- 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) - Adaptive Combinatorial Allocation [77.86290991564829]
割り当てが繰り返し選択され、戻り値は不明だが学習可能であり、決定には制約が伴う。
我々のモデルは、複雑な制約があっても、両側のマッチングと一方のマッチングをカバーしています。
論文 参考訳（メタデータ） (2020-11-04T15:02:59Z) - Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。
任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
論文 参考訳（メタデータ） (2020-02-12T18:59:18Z) - Evaluating approval-based multiwinner voting in terms of robustness to
noise [10.135719343010177]
承認ベースのマルチウィンナー投票は常に妥当な雑音に対して堅牢であることを示す。
ノイズに対する頑丈さの観点から、ルールの階層構造を提示することで、この発見をさらに洗練します。
論文 参考訳（メタデータ） (2020-02-05T13:17:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。