論文の概要: Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion
- arxiv url: http://arxiv.org/abs/2206.07098v2
- Date: Fri, 30 Jun 2023 00:54:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-03 16:00:48.159330
- 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 つの歪みを持つ。
関連論文リスト
- How many classifiers do we need? [50.69951049206484]
分類器間の不一致と偏極が、個々の分類器を集約することで得られる性能向上とどのように関連しているかを詳細に分析する。
分類器の個数で不一致の挙動を示す。
我々の理論と主張は、様々なタイプのニューラルネットワークを用いた画像分類タスクに関する経験的な結果によって裏付けられている。
論文 参考訳（メタデータ） (2024-11-01T02:59:56Z) - NoVo: Norm Voting off Hallucinations with Attention Heads in Large Language Models [70.02816541347251]
本稿では,注意基準の未適用ポテンシャルを利用して,事実の精度を高める軽量なノム投票法(Nom Voting, NoVo)を提案する。
TruthfulQA MC1では、NoVoは現在の最先端および過去のすべてのメソッドを、驚くべきマージン -- 少なくとも19の精度ポイントで上回る。
論文 参考訳（メタデータ） (2024-10-11T16:40:03Z) - 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) - Breaking the Metric Voting Distortion Barrier [10.143374372425757]
社会選択における計量歪みの問題を考察する。
歪み3-epsilon$を保証するランダム化ルールを見つけることは、計算社会選択において大きな課題である。
歪みを2.753ドル未満で保証する規則を与えます。
論文 参考訳（メタデータ） (2023-06-30T17:56:33Z) - Candidate Incentive Distributions: How voting methods shape electoral incentives [0.0]
Instant Runoff Votingは、Plurality Votingよりも幅広い有権者にアピールするよう、候補者にインセンティブを与える。
コンドルチェット法とSTAR (Score Then Automatic Runoff) Votingが最もバランスのとれたインセンティブを提供する。
論文 参考訳（メタデータ） (2023-06-12T14:32:46Z) - Accelerating Voting by Quantum Computation [35.03314687289671]
本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。
我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
論文 参考訳（メタデータ） (2023-01-08T07:29:38Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。