論文の概要: Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model

• arxiv url: http://arxiv.org/abs/2204.11282v2
• Date: Mon, 15 Apr 2024 13:51:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-18 03:19:56.149504
• Title: Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
• Title（参考訳）: シングル・ピークネスを超える施設配置ゲーム:入場料モデル
• Authors: Mengfan Ma, Mingyu Xiao, Tian Bai, Bakh Khoussainov,
• Abstract要約: 各施設が入場料を課金する新しいモデルを導入する。 本モデルでは,入場料関数を任意の関数とする。 近似比が好ましい戦略防御機構を設計する。
• 参考スコア（独自算出の注目度）: 18.86193543684732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility. In this paper, we introduce a novel model where each facility charges an entrance fee. Thus, the cost of each agent is determined by both the distance to the facility and the entrance fee of the facility. In our model, the entrance fee function is allowed to be an arbitrary function, causing agents' preferences may no longer be single-peaked anymore: This departure from the classical model introduces additional challenges. We systematically delve into the intricacies of the model, designing strategyproof mechanisms with favorable approximation ratios. Additionally, we complement these ratios with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms with respect to utilitarian and egalitarian objectives.
• Abstract（参考訳）: 施設位置ゲームは機構設計において広く研究されている。 古典的なモデルでは、各エージェントのコストは、最も近い施設までの距離によって決定される。 本稿では,各施設が入場料を課金する新しいモデルを提案する。 これにより、各エージェントのコストは、施設への距離と施設の入場料の両方によって決定される。 我々のモデルでは、入場料関数は任意の関数として認められ、エージェントの選好はもはや単一話者化されないかもしれない。 モデルの複雑さを体系的に探究し、近似比が好ましい戦略防御機構を設計する。 さらに、これらの比率をほぼ八度不合理な結果で補完する。 具体的には, 1-facility と 2-facility のゲームにおいて, 実用的・平等的目的に対する決定的・ランダム化機構によって与えられる近似比の上限を上下に設定する。

関連論文リスト

• Facility Location Games with Scaling Effects [69.28397508730046]
  古典的な施設配置問題を考慮し、各エージェントの個々のコスト関数が、スケーリング係数によって乗算された施設からの距離と等しくなる変動を考察する。 戦略と匿名のメカニズムによって達成できる総コストと最大コストの近似比について結果が得られた。
  論文  参考訳（メタデータ） (2024-02-29T07:08:18Z)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。 この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
  論文  参考訳（メタデータ） (2023-10-11T20:34:17Z)
• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  この問題に対して,距離に基づく比例フェアネスの概念の階層構造を提案する。 決定論的かつランダムなメカニズムを考察し、比例フェアネスの価格に関する厳密な境界を計算する。 モデルの拡張が2つあることを示す。
  論文  参考訳（メタデータ） (2023-01-11T07:30:35Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。 次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。 我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
  論文  参考訳（メタデータ） (2022-05-30T00:51:57Z)
• Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse [34.39887495671287]
  本稿では,達成された(反感)と所望のリコース無効率とのギャップを同時に最小化する目的関数を提案する。 我々は,任意のインスタンスに対応するリコース無効化率を特徴付けるために,新しい理論的結果を開発した。 複数の実世界のデータセットを用いた実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2022-03-13T21:39:24Z)
• Automated Mechanism Design for Classification with Partial Verification [64.69418921224529]
  部分検証による自動機構設計の問題点について検討する。 私たちは、すべてのタイプが結果よりも同じ好みを共有する設定における真実のメカニズムに焦点を当てています。
  論文  参考訳（メタデータ） (2021-04-12T03:29:31Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)

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

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