論文の概要: Best of Both Distortion Worlds
- arxiv url: http://arxiv.org/abs/2305.19453v1
- Date: Tue, 30 May 2023 23:24:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 19:17:44.263404
- Title: Best of Both Distortion Worlds
- Title（参考訳）: 両ゆがみの世界のベスト
- Authors: Vasilis Gkatzelis, Mohamad Latifian and Nisarg Shah
- Abstract要約: 我々は、$m$の代替案よりも$n$のエージェントの順序的選好を入力として行う投票規則を設計する問題について検討する。
投票規則への入力は、各エージェントの最も好まれる選択肢から最も好まれる選択肢のランク付けである。
両世界におけるほぼ最適歪み保証を同時に達成する新しい投票規則を設計することで,両世界のベストを達成できることを実証する。
- 参考スコア（独自算出の注目度）: 29.185700008117173
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of designing voting rules that take as input the ordinal
preferences of $n$ agents over a set of $m$ alternatives and output a single
alternative, aiming to optimize the overall happiness of the agents. The input
to the voting rule is each agent's ranking of the alternatives from most to
least preferred, yet the agents have more refined (cardinal) preferences that
capture the intensity with which they prefer one alternative over another. To
quantify the extent to which voting rules can optimize over the cardinal
preferences given access only to the ordinal ones, prior work has used the
distortion measure, i.e., the worst-case approximation ratio between a voting
rule's performance and the best performance achievable given the cardinal
preferences.
The work on the distortion of voting rules has been largely divided into two
worlds: utilitarian distortion and metric distortion. In the former, the
cardinal preferences of the agents correspond to general utilities and the goal
is to maximize a normalized social welfare. In the latter, the agents' cardinal
preferences correspond to costs given by distances in an underlying metric
space and the goal is to minimize the (unnormalized) social cost. Several
deterministic and randomized voting rules have been proposed and evaluated for
each of these worlds separately, gradually improving the achievable distortion
bounds, but none of the known voting rules perform well in both worlds
simultaneously.
In this work, we prove that one can achieve the best of both worlds by
designing new voting rules, that simultaneously achieve near-optimal distortion
guarantees in both distortion worlds. We also prove that this positive result
does not generalize to the case where the voting rule is provided with the
rankings of only the top-$t$ alternatives of each agent, for $t<m$.
- Abstract（参考訳）: 我々は、$m$の代替案よりも$n$のエージェントの日常的嗜好を入力として投票ルールを設計し、エージェントの全体的幸福を最適化することを目的とした1つの代替案を出力する問題について検討する。
投票規則への入力は、各エージェントが最も好む選択肢のランク付けであるが、エージェントは、他の選択肢よりも好まれる強度を捉えるより洗練された(カーディナルな)選好を持っている。
序列のみに与えられる基準優先よりも、投票ルールが最適化できる範囲を定量化するために、事前の作業では、この歪み測定、すなわち、投票ルールの性能と、その基準優先から得られる最高の性能との最悪のケース近似比を用いている。
投票規則の歪みに関する研究は、実用的歪みとメートル法歪みの2つの世界に分けられている。
前者では、エージェントの基準的嗜好は一般的なユーティリティに対応し、目的は正規化された社会福祉を最大化することである。
後者では、エージェントの基数選好は、基礎となる計量空間における距離によって与えられるコストに対応し、目標は(正規化されていない)社会的コストを最小化することである。
決定論的およびランダム化された投票規則がそれぞれ別々に提案され評価され、達成可能な歪み境界が徐々に改善されているが、既知の投票規則は両世界において同時にうまく機能しない。
本研究は,両世界におけるほぼ最適歪み保証を同時に達成する新しい投票規則を設計することにより,両世界のベストを達成できることを実証する。
また、このポジティブな結果が、投票ルールが各エージェントの上位$t$代替品のみを$t<m$で提供する場合に一般化しないことも証明する。
関連論文リスト
- Centralized Selection with Preferences in the Presence of Biases [25.725937202777267]
本論文は,候補を複数のグループに分けた設定に焦点をあて,いくつかのグループにおける候補の観測ユーティリティは,真のユーティリティよりも体系的に低い偏りを呈する。
アルゴリズムは、選好に関して準最適群フェアネスを達成するための選択を生成するとともに、分布的仮定の下で真の効用をほぼ最大化する証明と共に提示される。
論文 参考訳（メタデータ） (2024-09-07T19:47:13Z) - Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。
競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
論文 参考訳（メタデータ） (2024-05-31T19:26:05Z) - Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
オンライン報酬指標の偏りのないオフライン推定を最適化する意思決定ポリシーを学習することを目指している。
学習シナリオにおける同値性に基づく単一のフレームワークを提案する。
我々のフレームワークは、分散最適非バイアス推定器の特徴付けを可能にし、それに対する閉形式解を提供する。
論文 参考訳（メタデータ） (2024-05-09T12:52:22Z) - Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
AWAIREは、適応的に重み付けされたテスト統計量であり、本質的には、テストに有効な仮説のセットを「学習」する。
我々は、より広範囲にスキームと設定を検討し、実践のための効率的な選択を特定し、推奨する。
現在のAWAIRE実装の制限は、少数の候補者に限られている。
論文 参考訳（メタデータ） (2024-02-18T10:13:01Z) - Proportional Aggregation of Preferences for Sequential Decision Making [20.374669324368625]
投票者の選好を適度に決定する問題について検討する。
各ラウンドにおいて、決定ルールは、各投票者が承認した選択肢のどれかを報告する一連の選択肢から決定を選ばなければならない。
比喩的正当化表現に基づく公理を用いて、この目的を定式化する。
論文 参考訳（メタデータ） (2023-06-26T17:10:10Z) - Social Mechanism Design: A Low-Level Introduction [31.564788318133264]
エージェントは、意思決定結果と意思決定に使用されるルールまたは手順の両方を優先していることを示す。
低レベルにおける単純で直感的な選好構造を同定し、より高いレベルにおける選好の構成要素を形成するように一般化する。
非対称的二分法選択と憲法修正という2つの異なる領域における受容のアルゴリズムを解析する。
論文 参考訳（メタデータ） (2022-11-15T20:59:34Z) - Most Equitable Voting Rules [30.930621357547487]
ANRの不合理性 - 匿名性、中立性、解決可能性を満たす投票規則は存在しない - は、2つの選択肢と2つのエージェントの単純な設定でも維持される。
我々は、二つの公理を満たす任意の絶対的規則に対して、匿名性と中立性を最適に保存する、最も公平な洗練の斬新で強力な概念を提案する。
論文 参考訳（メタデータ） (2022-05-30T03:56:54Z) - Inferring Lexicographically-Ordered Rewards from Preferences [82.42854687952115]
本稿では,エージェントの観察された嗜好の多目的報酬に基づく表現を推定する手法を提案する。
我々は,異なる目的に対するエージェントの優先順位を語彙的入力としてモデル化することにより,エージェントがより高い優先順位を持つ目的に対して無関心である場合に限って,より低い優先順位を持つ目的が重要となるようにした。
論文 参考訳（メタデータ） (2022-02-21T12:01:41Z) - Where is the Grass Greener? Revisiting Generalized Policy Iteration for
Offline Reinforcement Learning [81.15016852963676]
オフラインRL体制における最先端のベースラインを、公正で統一的で高分解能なフレームワークの下で再実装する。
与えられたベースラインが、スペクトルの一方の端で競合する相手よりも優れている場合、他方の端では決してしないことを示す。
論文 参考訳（メタデータ） (2021-07-03T11:00:56Z) - Consensus-Guided Correspondence Denoising [67.35345850146393]
本稿では,地域間コンセンサス学習フレームワークと対応関係を異色化し,対応関係をロバストに識別する。
ローカル地域からグローバル地域への動的グラフから推定されるコンセンサススコアに基づいて,信頼度の高い候補を初期マッチングから蒸留する新しい「プルーニング」ブロックを導入した。
本手法は、堅牢なラインフィッティング、ワイドベースライン画像マッチング、画像ローカリゼーションベンチマークを顕著なマージンで上回る。
論文 参考訳（メタデータ） (2021-01-03T09:10:00Z) - Optimal Policies for the Homogeneous Selective Labels Problem [19.54948759840131]
本稿では,選択ラベルに直面する意思決定方針の学習について述べる。
割引総報酬を最大化するためには、最適政策がしきい値ポリシーであることが示される。
数え切れない無限水平平均報酬に対して、最適政策は全ての状態において肯定的な受容確率を持つ。
論文 参考訳（メタデータ） (2020-11-02T23:32:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。