論文の概要: The Complexity of Learning Approval-Based Multiwinner Voting Rules
- arxiv url: http://arxiv.org/abs/2110.00254v1
- Date: Fri, 1 Oct 2021 08:25:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-04 23:39:47.637727
- Title: The Complexity of Learning Approval-Based Multiwinner Voting Rules
- Title（参考訳）: 承認に基づくマルチウィンナー投票ルールの学習の複雑さ
- Authors: Ioannis Caragiannis and Karl Fehrs
- Abstract要約: マルチウィンナー投票におけるPAC学習可能性について検討し,ABCSルールのクラスに着目した。
ABCSのルールは、各投票者から$k$の候補者の委員会にスコアが与えられると仮定して、単一投票者投票におけるポジションスコアルールに適合する。
我々の目標は、少数のサンプルプロファイルの勝者委員会に関する情報を用いて、目標ルール(すなわち、対応するスコアリング関数を学習すること)を学習することである。
- 参考スコア（独自算出の注目度）: 15.155649115863783
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the PAC learnability of multiwinner voting, focusing on the class of
approval-based committee scoring (ABCS) rules. These are voting rules applied
on profiles with approval ballots, where each voter approves some of the
candidates. ABCS rules adapt positional scoring rules in single-winner voting
by assuming that each committee of $k$ candidates collects from each voter a
score, that depends on the size of the voter's ballot and on the size of its
intersection with the committee. Then, committees of maximum score are the
winning ones. Our goal is to learn a target rule (i.e., to learn the
corresponding scoring function) using information about the winning committees
of a small number of sampled profiles. Despite the existence of exponentially
many outcomes compared to single-winner elections, we show that the sample
complexity is still low: a polynomial number of samples carries enough
information for learning the target committee with high confidence and
accuracy. Unfortunately, even simple tasks that need to be solved for learning
from these samples are intractable. We prove that deciding whether there exists
some ABCS rule that makes a given committee winning in a given profile is a
computationally hard problem. Our results extend to the class of sequential
Thiele rules, which have received attention due to their simplicity.
- Abstract（参考訳）: マルチウィンナー投票におけるPAC学習可能性について検討し,ABCSルールのクラスに着目した。
これらは、各投票者が候補者の幾らかを承認する、承認投票を伴うプロファイルに適用される投票規則である。
abcsルールは、k$の候補者の各委員会が各投票者から得票数を収集し、投票者のサイズと委員会との交点の大きさに依存すると仮定することで、シングルウィンナー投票におけるポジションスコアルールを適合させる。
そして、最高得点の委員会が勝利者となる。
我々の目標は、少数のサンプルプロファイルの勝者委員会に関する情報を用いて、目標ルール(すなわち、対応するスコアリング関数を学習すること)を学習することである。
単勝選挙と比較して指数関数的に多くの結果が存在するにもかかわらず、サンプルの複雑さは依然として低い: 多項式数のサンプルは、高い信頼と正確さでターゲット委員会を学ぶのに十分な情報を持っている。
残念ながら、これらのサンプルから学ぶのに必要な単純なタスクでさえ難解です。
我々は、ある委員会が与えられたプロファイルに勝つようなABCSルールが存在するかどうかを判断することは、計算的に難しい問題であることを示す。
我々の結果は、その単純さから注目を集めているシーケンシャルなTieleルールのクラスにまで及んでいる。
関連論文リスト
- DeepVoting: Learning Voting Rules with Tailored Embeddings [13.037431161285971]
我々は、よい投票規則を設計する問題は、投票規則の確率的なバージョンを学ぶことの1つに再キャストする。
社会的選択文献からの選好プロファイルの埋め込みにより,既存の投票ルールをより効率的に学習できることを示す。
また、埋め込みを用いて学習したルールを微調整して、公理特性を改善した新しい投票ルールを作成することも示している。
論文 参考訳（メタデータ） (2024-08-24T17:15:20Z) - 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) - Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
我々は、有権者に$t m$の候補者を問うことで計算可能な投票ルールについて検討する。
限定的なクエリで計算可能なルールを評価するために、パラメータ化された上と下の境界をそのようなクエリの数に割り当てる。
論文 参考訳（メタデータ） (2024-02-16T22:17:01Z) - Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
即時投票(IRV)選挙の監査方法は、リスク制限や、各投票における投票の電子的記録であるキャスト投票記録(CVR)を必要とするものではない。
我々は,CVRが利用できない場合に,適応的に重み付けされたテストスーパーマーチンガルを用いてITV選挙を効率よく監査するRLA手法を開発した。
論文 参考訳（メタデータ） (2023-07-20T15:55:34Z) - Data as voters: instance selection using approval-based multi-winner voting [1.597617022056624]
機械学習(あるいはデータマイニング)におけるインスタンス選択問題に対する新しいアプローチを提案する。
私たちのモデルでは、インスタンスは有権者と候補者として二重の役割を担います。
SVM では,EJR や PJR を満たすいくつかの投票規則を用いて,平均精度をわずかに向上させた。
論文 参考訳（メタデータ） (2023-04-19T22:00:23Z) - Expected Frequency Matrices of Elections: Computation, Geometry, and
Preference Learning [58.23459346724491]
我々は、Szufa et al.(AAMAS 2020)の「選挙マップ」アプローチを用いて、よく知られた投票分布を分析します。
分布の「スケルトン写像」を描き、その頑健さを評価し、その性質を分析する。
論文 参考訳（メタデータ） (2022-05-16T17:40:22Z) - Obvious Manipulability of Voting Rules [105.35249497503527]
Gibbard-Satterthwaite の定理は、全会一致で非独裁的な投票規則は、戦略的なものではないと述べる。
我々は投票規則を再検討し、明らかでない操作性という戦略的安全性の弱い概念を考察する。
論文 参考訳（メタデータ） (2021-11-03T02:41:48Z) - 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) - Evaluating approval-based multiwinner voting in terms of robustness to
noise [10.135719343010177]
承認ベースのマルチウィンナー投票は常に妥当な雑音に対して堅牢であることを示す。
ノイズに対する頑丈さの観点から、ルールの階層構造を提示することで、この発見をさらに洗練します。
論文 参考訳（メタデータ） (2020-02-05T13:17:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。