論文の概要: Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion
- arxiv url: http://arxiv.org/abs/2206.07098v1
- Date: Tue, 14 Jun 2022 18:32:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-16 14:31:39.436841
- Title: Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion
- Title(参考訳): Plurality Veto: 最適なメトリック歪みを実現するシンプルな投票ルール
- Authors: Fatih Erdem Kizilkaya and David Kempe
- Abstract要約: メートル法歪みの枠組み nの有権者とmの候補者は 共同でメートル法空間に埋め込まれている
投票ルールの目的は、投票者に対して最短距離の候補者を選ぶことである。
Plurality Veto と呼ばれる単純な投票法則が 3 の最適歪みを達成することを示す。
- 参考スコア(独自算出の注目度): 11.282341369957212
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The metric distortion framework posits that n voters and m candidates are
jointly embedded in a metric space such that voters rank candidates that are
closer to them higher. A voting rule's purpose is to pick a candidate with
minimum total distance to the voters, given only the rankings, but not the
actual distances. As a result, in the worst case, each deterministic rule picks
a candidate whose total distance is at least three times larger than that of an
optimal one, i.e., has distortion at least 3. A recent breakthrough result
showed that achieving this bound of 3 is possible; however, the proof is
non-constructive, and the voting rule itself is a complicated exhaustive
search.
Our main result is an extremely simple voting rule, called Plurality Veto,
which achieves the same optimal distortion of 3. Each candidate starts with a
score equal to his number of first-place votes. These scores are then gradually
decreased via an n-round veto process in which a candidate drops out when his
score reaches zero. One after the other, voters decrement the score of their
bottom choice among the standing candidates, and the last standing candidate
wins. We give a one-paragraph proof that this voting rule achieves distortion
3. This rule is also immensely practical, and it only makes two queries to each
voter, so it has low communication overhead.
We also generalize Plurality Veto into a class of randomized voting rules in
the following way: Plurality veto is run only for k < n rounds; then, a
candidate is chosen with probability proportional to his residual score. This
general rule interpolates between Random Dictatorship (for k=0) and Plurality
Veto (for k=n-1), and k controls the variance of the output. We show that for
all k, this rule has distortion at most 3.
- Abstract(参考訳): 計量歪みフレームワークは、n人の有権者とm人の候補者が互いにメートル法空間に埋め込まれており、投票者がそれに近い候補者をランク付けすることを示している。
投票規則の目的は、投票者までの距離が最小の候補者を選ぶことである。
その結果、最悪の場合、各決定論的ルールは、全距離が最適なものよりも少なくとも3倍大きい候補、すなわち少なくとも3倍の歪みを持つ候補を選択する。
最近のブレークスルーの結果、この3の限界を達成することは可能であることが示されているが、証明は非構成的であり、投票ルール自体が複雑な徹底的な探索である。
我々の主な結果は、Plurality Vetoと呼ばれる非常に単純な投票規則であり、これは3の最適歪みを達成している。
各候補者は1位の得票数に等しいスコアでスタートする。
これらのスコアは、候補がスコアが0に達したときにドロップアウトするnラウンドベトプロセスによって徐々に減少する。
次から次へと、有権者は最下位の候補のうち最下位のスコアを割り出し、最後の候補が勝利する。
この投票規則が歪み 3 を達成することを1パラグラフで証明する。
このルールは極めて実用的であり、各投票者に対して2つのクエリしか行わないため、通信オーバーヘッドが低い。
また、複数のvetoをランダム化された投票ルールのクラスに一般化する: 複数のvetoは、k < n ラウンドに対してのみ実行され、残りのスコアに比例する確率で候補が選択される。
この一般規則はランダムディクターシップ(k=0 の場合)と Plurality Veto(k=n-1 の場合)を補間し、k は出力の分散を制御する。
すべての k に対して、この規則は最大で 3 つの歪みを持つ。
関連論文リスト
- Learning to Manipulate under Limited Information [49.1574468325115]
私たちは、26のサイズの約4万のニューラルネットワークをトレーニングし、8つの異なる投票方法に対処しました。
ボルダなど一部の投票手法は限られた情報を持つネットワークで高度に操作可能であるのに対して、Instant Runoffのような投票手法はそうではない。
論文 参考訳(メタデータ) (2024-01-29T18:49:50Z) - Breaking the Metric Voting Distortion Barrier [13.765996791591153]
一定の$varepsilon$に対して、歪み3 - varepsilon$を保証する規則を見つける。
ゆがみ3-varepsilon$を一定の$varepsilon$で保証するルールを見つけることは、計算社会選択において大きな課題である。
論文 参考訳(メタデータ) (2023-06-30T17:56:33Z) - Large Language Models are not Fair Evaluators [60.27164804083752]
候補回答の品質ランキングは,文脈の出現順序を変えることで容易にハックできることがわかった。
この操作により、評価結果をスキューし、一方のモデルを他方よりもかなり優れているようにすることができる。
この問題を緩和するための3つのシンプルかつ効果的な戦略を持つフレームワークを提案する。
論文 参考訳(メタデータ) (2023-05-29T07:41:03Z) - Accelerating Voting by Quantum Computation [35.03314687289671]
本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。
我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
論文 参考訳(メタデータ) (2023-01-08T07:29:38Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳(メタデータ) (2022-03-18T08:03:20Z) - Truth-tracking via Approval Voting: Size Matters [3.113227275600838]
我々は、投票が承認投票からなる単純な設定を考える。
各投票者は、基本的真実である可能性があると信じている選択肢のセットを承認する。
我々は、Mallowsモデルの投票変種を承認するいくつかのノイズモデルを定義する。
論文 参考訳(メタデータ) (2021-12-07T12:29:49Z) - Obvious Manipulability of Voting Rules [105.35249497503527]
Gibbard-Satterthwaite の定理は、全会一致で非独裁的な投票規則は、戦略的なものではないと述べる。
我々は投票規則を再検討し、明らかでない操作性という戦略的安全性の弱い概念を考察する。
論文 参考訳(メタデータ) (2021-11-03T02:41:48Z) - The Complexity of Learning Approval-Based Multiwinner Voting Rules [9.071560867542647]
本研究は,ABCS(承認ベース委員会スコアリング)ルールのクラスに着目し,マルチウィンナ投票の学習可能性について検討する。
我々のゴールは、少数のプロファイルの勝利委員会に関する情報を用いて、ターゲットルール(すなわち、対応するスコアリング機能を学ぶこと)を学ぶことである。
我々は、ある委員会に与えられたプロファイルで勝利させるABCSルールが存在するかどうかを判断することが難しいことを証明している。
論文 参考訳(メタデータ) (2021-10-01T08:25:05Z) - FastCorrect 2: Fast Error Correction on Multiple Candidates for
Automatic Speech Recognition [92.12910821300034]
本稿では,複数のASR候補を入力として取り込んだ誤り訂正モデルFastCorrect 2を提案する。
FastCorrect 2は、カスケードされた再描画と修正パイプラインよりも優れたパフォーマンスを実現している。
論文 参考訳(メタデータ) (2021-09-29T13:48:03Z) - 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) - Random errors are not necessarily politically neutral [25.75404628089468]
ランダムな誤りがSTV(Single Transferable Vote)選挙に与える影響について検討する。
ランダムエラーの最も重要な影響は、投票を無効にすることである。
投票スタイルの異なる妥当性ルールは、エラーが他のものよりもある種の投票を罰する可能性がずっと高いことを意味する。
論文 参考訳(メタデータ) (2020-07-02T03:37:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。