論文の概要: Optimal bounds for dissatisfaction in perpetual voting
- arxiv url: http://arxiv.org/abs/2501.01969v1
- Date: Fri, 20 Dec 2024 19:58:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-12 03:46:01.942241
- Title: Optimal bounds for dissatisfaction in perpetual voting
- Title(参考訳): 永年投票における不満の最適境界
- Authors: Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer,
- Abstract要約: 我々は、投票者が何回も不満を抱いていないことを保証し、永遠の投票方法を考える。
我々は、不満のサブ線形成長が可能な有権者行動に関する十分な条件を特定する。
本稿では,専門家の助言による予測から得られた標準手法に基づいて,紛争条件下での不満をサブ線形に保証する投票手法を提案する。
- 参考スコア(独自算出の注目度): 84.02572742131521
- License:
- Abstract: In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior -- which we call 'bounded conflicts' condition -- under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
- Abstract(参考訳): 永遠の投票では、異なるタイミングで複数の決定が下される。
過去の決定の歴史を考慮に入れれば、時間的比例のような特性を満足させることができる。
本稿では, 投票者が何回も不満を抱いていないことを保証し, 永遠の投票方法が存在するか, という課題を考察する。
我々は、不満のサブ線形成長が可能な有権者の行動に関する十分な条件、すなわち「境界紛争」状態を特定する。
我々は、コルモゴロフ複雑性の手法を用いて、有界紛争下での不満の増大に厳密な上限を与える。
また、二項選択による承認投票は、専門家のアドバイスによる予測の機械学習設定を模倣していることも観察した。
これにより、専門家の助言による予測から得られる標準手法に基づいて、境界紛争下での不満をサブ線形に保証する投票方法を提案することができる。
関連論文リスト
- 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) - Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - The Distortion of Binomial Voting Defies Expectation [26.481697906062095]
本稿では,投票者の効用に対する基本的分布に関する投票規則の歪曲について検討する。
私たちの主な貢献は、新鮮で直感的なルール、二項投票の設計と分析です。
論文 参考訳(メタデータ) (2023-06-27T17:50:58Z) - Fairly Allocating Utility in Constrained Multiwinner Elections [0.0]
このような文脈にまたがる公平性を保証する一般的な分母は、制約の使用である。
これらの状況の中で、与えられた制約を満たすために選ばれた候補者は、歴史的に不利な有権者の集団に対して、体系的に不公平な結果をもたらす可能性がある。
投票者間の制約を公平に満たす候補を選択するモデルを構築した。
論文 参考訳(メタデータ) (2022-11-23T10:04:26Z) - On the Complexity of Winner Determination and Strategic Control in
Conditional Approval Voting [13.207754600697138]
条件最小 (Conditional Minisum, CMS) は、優先的な依存関係を持つ多問題選挙の投票規則である。
我々は,CMSを表現性と計算効率の良好なトレードオフを実現するソリューションとみなすことができることを示す。
論文 参考訳(メタデータ) (2022-02-03T16:15:54Z) - 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) - Adaptive Combinatorial Allocation [77.86290991564829]
割り当てが繰り返し選択され、戻り値は不明だが学習可能であり、決定には制約が伴う。
我々のモデルは、複雑な制約があっても、両側のマッチングと一方のマッチングをカバーしています。
論文 参考訳(メタデータ) (2020-11-04T15:02:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。