論文の概要: Strategy Proof Mechanisms for Facility Location in Euclidean and Manhattan Space

• arxiv url: http://arxiv.org/abs/2009.07983v1
• Date: Thu, 17 Sep 2020 00:25:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 11:55:58.634777
• Title: Strategy Proof Mechanisms for Facility Location in Euclidean and Manhattan Space
• Title（参考訳）: ユークリッド空間とマンハッタン空間における施設配置の戦略実証機構
• Authors: Toby Walsh
• Abstract要約: 1次元から2次元(またはそれ以上)への移動は、しばしば公理的性質を達成しにくくする。 2次元(またはそれ以上)に移動すると近似比が増加する可能性がある。
• 参考スコア（独自算出の注目度）: 17.68987003293372
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the impact on mechanisms for facility location of moving from one dimension to two (or more) dimensions and Euclidean or Manhattan distances. We consider three fundamental axiomatic properties: anonymity which is a basic fairness property, Pareto optimality which is one of the most important efficiency properties, and strategy proofness which ensures agents do not have an incentive to mis-report. We also consider how well such mechanisms can approximate the optimal welfare. Our results are somewhat negative. Moving from one dimension to two (or more) dimensions often makes these axiomatic properties more difficult to achieve. For example, with two facilities in Euclidean space or with just a single facility in Manhattan space, no mechanism is anonymous, Pareto optimal and strategy proof. By contrast, mechanisms on the line exist with all three properties.We also show that approximation ratios may increase when moving to two (or more) dimensions. All our impossibility results are minimal. If we drop one of the three axioms (anonymity, Pareto optimality or strategy proofness) multiple mechanisms satisfy the other two axioms.
• Abstract（参考訳）: 1次元から2次元(以上)、ユークリッド距離やマンハッタン距離における施設配置のメカニズムへの影響について検討した。 基本的な公理的性質は, 基本的公正性である匿名性, 最も重要な効率性の一つであるパレート最適性, エージェントが誤報告のインセンティブを持たないことを保証する戦略実証性, の3つである。 また,このメカニズムがいかに最適な福祉を近似できるかについても考察する。 私たちの結果はやや否定的です。 1次元から2次元(またはそれ以上)に移動すると、これらの公理的性質がより困難になる。 例えば、ユークリッド空間の2つの施設やマンハッタン空間の1つの施設では、匿名のメカニズムやパレートの最適証明、戦略証明などは存在しない。 対照的に、直線上のメカニズムは3つの性質全てで存在し、また2次元(またはそれ以上)に移動すると近似比が増加することも示している。 不可能な結果はすべて最小限です。 3つの公理(匿名性、パレート最適性、戦略証明性)の1つを落とすと、他の2つの公理を複数の機構で満たす。

関連論文リスト

• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  この問題に対して,距離に基づく比例フェアネスの概念の階層構造を提案する。 決定論的かつランダムなメカニズムを考察し、比例フェアネスの価格に関する厳密な境界を計算する。 モデルの拡張が2つあることを示す。
  論文  参考訳（メタデータ） (2023-01-11T07:30:35Z)
• Mechanism Design With Predictions for Obnoxious Facility Location [0.0]
  本研究では,施設の無害な位置問題に対する予測を用いたメカニズム設計について検討する。 本稿では, セグメント, 正方形, 円, 木における頑健性と整合性のトレードオフを示す決定論的戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2022-12-19T15:04:11Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。 次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。 我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
  論文  参考訳（メタデータ） (2022-05-30T00:51:57Z)
• Strategyproof and Proportionally Fair Facility Location [77.16035689756859]
  簡単な1次元集団決定問題(しばしば施設配置問題と呼ばれる)に焦点を当てる。 比例に基づく様々な強度のフェアネス公理の階層構造を解析する。 各公理に対して、公理と戦略の安全性を満足するメカニズムのファミリーを特徴付ける。
  論文  参考訳（メタデータ） (2021-11-02T12:41:32Z)
• Pure Exploration in Kernel and Neural Bandits [90.23165420559664]
  我々は、特徴表現の次元が腕の数よりもはるかに大きい帯域における純粋な探索について研究する。 そこで本研究では,各アームの特徴表現を低次元空間に適応的に埋め込む手法を提案する。
  論文  参考訳（メタデータ） (2021-06-22T19:51:59Z)
• Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach [8.932080210400535]
  我々は、レポートのペアをスコアにマッピングするスコア関数を持つメカニズムのファミリーを設計する。 異なる種類の先行作業に必要なタスク数に対して、適切な境界を導出する方法を示す。 これはマルチタスク設定用に設計された連続信号に対する最初のピア予測機構である。
  論文  参考訳（メタデータ） (2020-09-30T15:09:56Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。 私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。 次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
  論文  参考訳（メタデータ） (2020-06-22T14:35:33Z)
• Near Instance-Optimality in Differential Privacy [38.8726789833284]
  古典統計理論に着想を得た差分プライバシーにおけるインスタンス最適性の概念を考案する。 また、大規模な推定値に対してインスタンス最適(もしくはほぼインスタンス最適)な逆感度機構も開発する。
  論文  参考訳（メタデータ） (2020-05-16T04:53:48Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)
• An Inductive Bias for Distances: Neural Nets that Respect the Triangle Inequality [38.95108641775682]
  距離は機械学習に広く浸透し、類似性尺度、損失関数、学習目標として機能する。 三角形の不等式を尊重する深い計量学習アーキテクチャは、ほとんど独占的に、潜在空間におけるユークリッド距離に依存している。 我々のアーキテクチャは、グラフ距離をモデル化する際の既存のメトリックアプローチよりも優れており、トレーニングデータに制限がある場合の非メトリックアプローチよりも優れた帰納バイアスを有することを示す。
  論文  参考訳（メタデータ） (2020-02-14T00:47:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。