論文の概要: The Smoothed Satisfaction of Voting Axioms
- arxiv url: http://arxiv.org/abs/2106.01947v1
- Date: Thu, 3 Jun 2021 15:55:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-04 16:00:04.280562
- Title: The Smoothed Satisfaction of Voting Axioms
- Title（参考訳）: 投票公理の円滑な満足
- Authors: Lirong Xia
- Abstract要約: 我々は,2つのよく研究された投票公理(コンドルチェット基準と参加)の円滑な満足度を特徴付けることに重点を置いている。
我々は1994年にベルクとレペリーによるこれらのルールに関するオープンな質問に回答し、以下のハイレベルなメッセージを確認した。
- 参考スコア（独自算出の注目度）: 34.65163653153113
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We initiate the work towards a comprehensive picture of the smoothed
satisfaction of voting axioms, to provide a finer and more realistic foundation
for comparing voting rules. We adopt the smoothed social choice framework,
where an adversary chooses arbitrarily correlated "ground truth" preferences
for the agents, on top of which random noises are added. We focus on
characterizing the smoothed satisfaction of two well-studied voting axioms:
Condorcet criterion and participation. We prove that for any fixed number of
alternatives, when the number of voters $n$ is sufficiently large, the smoothed
satisfaction of the Condorcet criterion under a wide range of voting rules is
$1$, $1-\exp(-\Theta(n))$, $\Theta(n^{-0.5})$, $ \exp(-\Theta(n))$, or being
$\Theta(1)$ and $1-\Theta(1)$ at the same time; and the smoothed satisfaction
of participation is $1-\Theta(n^{-0.5})$. Our results address open questions by
Berg and Lepelley in 1994 for these rules, and also confirm the following
high-level message: the Condorcet criterion is a bigger concern than
participation under realistic models.
- Abstract（参考訳）: 我々は,投票公理の円滑な満足度を総合的に図示し,投票ルールを比較するためのより精巧で現実的な基礎を提供する。
本研究では, エージェントに対して任意に相関した「地上真実」選好を選択し, その上にランダムノイズを付加するスムーズな社会選択フレームワークを採用する。
我々は、熟考された2つの投票公理(コンドルセト基準と参加)の円滑な満足度を特徴付けることに集中する。
任意の固定数の選択肢に対して、投票者数n$が十分に大きい場合、幅広い投票規則の下でのコンドルチェット基準の円滑な満足度は、$$$, $1-\exp(-\Theta(n))$, $\Theta(n^{-0.5})$, $ \exp(-\Theta(n))$, $\Theta(1)$, $1-\Theta(1)$, $1-\Theta(1)$であり、参加の円滑な満足度は1-\Theta(n^{-0.5})$であることを示す。
その結果,1994年にberg と lepelley によるこれらのルールに対する疑問に答えるとともに,以下のハイレベルなメッセージを確認した。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Breaking the Metric Voting Distortion Barrier [10.143374372425757]
社会選択における計量歪みの問題を考察する。
歪み3-epsilon$を保証するランダム化ルールを見つけることは、計算社会選択において大きな課題である。
歪みを2.753ドル未満で保証する規則を与えます。
論文 参考訳（メタデータ） (2023-06-30T17:56:33Z) - Proportional Aggregation of Preferences for Sequential Decision Making [20.374669324368625]
投票者の選好を適度に決定する問題について検討する。
各ラウンドにおいて、決定ルールは、各投票者が承認した選択肢のどれかを報告する一連の選択肢から決定を選ばなければならない。
比喩的正当化表現に基づく公理を用いて、この目的を定式化する。
論文 参考訳（メタデータ） (2023-06-26T17:10:10Z) - Differentially Private Condorcet Voting [26.959251649951103]
本稿では,よく知られたCondorcet法に基づくランダム化投票規則の3つのクラスを提案する。
ランダム性によって引き起こされる誤差を正確に推定することにより、ほとんどの場合、$CMEXP_lambda$が最も正確なメカニズムであることを示す。
我々は、差分プライバシーを投票公理とみなし、他の公理との関係について議論する。
論文 参考訳（メタデータ） (2022-06-27T06:55:22Z) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳（メタデータ） (2021-12-13T09:48:54Z) - Truth-tracking via Approval Voting: Size Matters [3.113227275600838]
我々は、投票が承認投票からなる単純な設定を考える。
各投票者は、基本的真実である可能性があると信じている選択肢のセットを承認する。
我々は、Mallowsモデルの投票変種を承認するいくつかのノイズモデルを定義する。
論文 参考訳（メタデータ） (2021-12-07T12:29:49Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - 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) - Rate-adaptive model selection over a collection of black-box contextual
bandit algorithms [0.966840768820136]
文脈的帯域設定におけるモデル選択タスクについて検討する。
我々の提案は、一般的なブラックボックス・コンテクスト・バンディットアルゴリズムの収集に適応する最初のものである。
論文 参考訳（メタデータ） (2020-06-05T18:55:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。