論文の概要: Random Rank: The One and Only Strategyproof and Proportionally Fair
Randomized Facility Location Mechanism
- arxiv url: http://arxiv.org/abs/2205.14798v1
- Date: Mon, 30 May 2022 00:51:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 17:54:25.401945
- Title: Random Rank: The One and Only Strategyproof and Proportionally Fair
Randomized Facility Location Mechanism
- Title（参考訳）: ランダムランク: 唯一の戦略的防御と比例的に公平な施設配置機構
- Authors: Haris Aziz, Alexander Lam, Mashbat Suzuki, Toby Walsh
- Abstract要約: 我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。
次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。
我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
- 参考スコア（独自算出の注目度）: 103.36492220921109
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Proportionality is an attractive fairness concept that has been applied to a
range of problems including the facility location problem, a classic problem in
social choice. In our work, we propose a concept called Strong Proportionality,
which ensures that when there are two groups of agents at different locations,
both groups incur the same total cost. We show that although Strong
Proportionality is a well-motivated and basic axiom, there is no deterministic
strategyproof mechanism satisfying the property. We then identify a randomized
mechanism called Random Rank (which uniformly selects a number $k$ between $1$
to $n$ and locates the facility at the $k$'th highest agent location) which
satisfies Strong Proportionality in expectation. Our main theorem characterizes
Random Rank as the unique mechanism that achieves universal truthfulness,
universal anonymity, and Strong Proportionality in expectation among all
randomized mechanisms. Finally, we show via the AverageOrRandomRank mechanism
that even stronger ex-post fairness guarantees can be achieved by weakening
universal truthfulness to strategyproofness in expectation.
- Abstract（参考訳）: Proportionalityは、施設配置問題、社会選択における古典的な問題など、様々な問題に適用された魅力的な公平性の概念である。
本研究で提案するStrong Proportionalityという概念は,異なる場所にエージェントの2つのグループが存在する場合,両者が同じコストを発生させることを保証する。
強比例性は十分動機づけられ基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しない。
次にランダムランキング(Random Rank)と呼ばれるランダム化メカニズム($k$から$n$の数値を均一に選択し、期待するStrong Proportionalityを満たす$k$から$n$の最高エージェントロケーションに施設を配置する)を特定します。
我々の主定理はランダムランクを普遍的真理性、普遍的匿名性、全てのランダム化機構の予測における強比例性を達成するユニークなメカニズムとして特徴づけている。
最後に、AverageOrRandomRank機構を通して、期待する戦略の正当性を弱めることで、ポスト前の公正性を保証することさえも達成できることを示す。
関連論文リスト
- Mechanisms that play a game, not toss a coin [18.168659230989384]
本稿では,コインを投げる代わりにエージェントがゲームをしてランダム化メカニズムをデランドマイズすることを提案する。
このデランドマイゼーションは、元のメカニズムのよい規範的特性の多くを保っているが、決定論的で容易に監査できるメカニズムを与える。
論文 参考訳（メタデータ） (2023-08-21T01:43:08Z) - Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
この問題に対して,距離に基づく比例フェアネスの概念の階層構造を提案する。
決定論的かつランダムなメカニズムを考察し、比例フェアネスの価格に関する厳密な境界を計算する。
モデルの拡張が2つあることを示す。
論文 参考訳（メタデータ） (2023-01-11T07:30:35Z) - Strategyproof and Proportionally Fair Facility Location [77.16035689756859]
簡単な1次元集団決定問題(しばしば施設配置問題と呼ばれる)に焦点を当てる。
比例に基づく様々な強度のフェアネス公理の階層構造を解析する。
各公理に対して、公理と戦略の安全性を満足するメカニズムのファミリーを特徴付ける。
論文 参考訳（メタデータ） (2021-11-02T12:41:32Z) - Towards Assessment of Randomized Smoothing Mechanisms for Certifying
Adversarial Robustness [50.96431444396752]
主な課題は、各ランダム化メカニズムの適切性を評価する方法である。
まず最初に、ガウスのメカニズムが$ell$-normを証明するための適切な選択肢であると結論付ける。
驚いたことに、ガウスのメカニズムは指数機構の代わりに$ell_infty$-normを証明するための適切な選択肢でもある。
論文 参考訳（メタデータ） (2020-05-15T03:54:53Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳（メタデータ） (2020-04-19T18:00:58Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。