論文の概要: Prediction-Augmented Mechanism Design for Weighted Facility Location

• arxiv url: http://arxiv.org/abs/2507.06509v2
• Date: Thu, 10 Jul 2025 01:52:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-11 12:24:00.088962
• Title: Prediction-Augmented Mechanism Design for Weighted Facility Location
• Title（参考訳）: 軽量施設における予測強化機構設計
• Authors: Yangguang Shi, Zhenyu Xue,
• Abstract要約: 非一様重みを持つ戦略エージェントに対して、一貫性と堅牢性のバランスをとるための拡張アルゴリズムフレームワークを提供する。 重み付き FLP における$Oleft(n cdot fracW_maxW_min right)$Oleft(n cdot fracW_maxW_min right)$-robustness in weighted FLP, with fully predictions of all agent。
• 参考スコア（独自算出の注目度）: 1.6552489352816389
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Facility location is fundamental in operations research, mechanism design, and algorithmic game theory, with applications ranging from urban infrastructure planning to distributed systems. Recent research in this area has focused on augmenting classic strategyproof mechanisms with predictions to achieve an improved performance guarantee against the uncertainty under the strategic environment. Previous work has been devoted to address the trade-off obstacle of balancing the consistency (near-optimality under accurate predictions) and robustness (bounded inefficiency under poor predictions) primarily in the unweighted setting, assuming that all agents have the same importance. However, this assumption may not be true in some practical scenarios, leading to research of weighted facility location problems. The major contribution of the current work is to provide a prediction augmented algorithmic framework for balancing the consistency and robustness over strategic agents with non-uniform weights. In particular, through a reduction technique that identifies a subset of \emph{representative} instances and maps the other given locations to the representative ones, we prove that there exists a \emph{strategyproof} mechanism achieving a bounded consistency guarantee of $\frac{\sqrt{(1+c)^2W^2_{\min}+(1-c)^2W^2_{\max}}}{(1+c)W_{\min}}$ and a bounded robustness guarantee of $\frac{\sqrt{(1-c)^2W^2_{\min}+(1+c)^2W^2_{\max}}}{(1-c)W_{\min}}$ in weighted settings, where $c$ can be viewed as a parameter to make a trade-off between the consistency and robustness and $W_{\min}$ and $W_{\max}$ denote the minimum and maximum agents' weight. We also proved that there is no strategyproof deterministic mechanism that reach $1$-consistency and $O\left( n \cdot \frac{W_{\max}}{W_{\min}} \right)$-robustness in weighted FLP, even with fully predictions of all agents.
• Abstract（参考訳）: 施設の位置は、都市インフラ計画から分散システムに至るまで、運用研究、メカニズム設計、アルゴリズムゲーム理論において基本的なものである。 この領域における最近の研究は、戦略環境下での不確実性に対する性能保証を改善するために、予測による古典的な戦略防御機構の強化に重点を置いている。 従来の作業は、すべてのエージェントが同じ重要性を持つと仮定して、主に非重み付け環境での一貫性(正確な予測の下では最適に近い)と堅牢性(予測が不十分な条件下では非効率な境界)のバランスをとるというトレードオフの障害に対処するために費やされてきた。 しかし、この仮定はいくつかの現実的なシナリオでは正しくない可能性があり、重み付けされた施設配置問題の研究につながっている。 この研究の主な貢献は、一様でない重みを持つ戦略エージェントに対する一貫性と堅牢性のバランスをとるための拡張アルゴリズムフレームワークを提供することである。 特に、 \emph{representative} インスタンスのサブセットを識別し、他の場所を代表インスタンスにマップする還元手法により、$\frac{\sqrt{(1+c)^2W^2_{\min}+(1-c)^2W^2_{\max}}}{(1+c)W_{\min}}$と$\frac{\sqrt{(1-c)^2W^2_{\min}+(1+c)^2W^2_{\max}}}{(1-c)W_{\min}}$の有界整合性を保証するためのパラメータとして$c$が存在することを証明する。 また, 重み付き FLP における$-robustness は, 全エージェントの完全予測においても, 1$-consistency および $O\left(n \cdot \frac{W_{\max}}{W_{\min}} \right)$-robustness に到達する戦略的決定機構が存在しないことも証明した。

関連論文リスト

• Minimax-Optimal Multi-Agent Robust Reinforcement Learning [7.237817437521988]
  我々は、生成モデルへのアクセスを前提として、Q-FTRLアルゴリズム citepli2022minimax を有限水平設定で RMG に拡張する。 提案アルゴリズムは$varepsilon$-robust coarse correlation equilibrium (CCE) を$widetildeOleft(H3Ssum_i=1mA_iminleftH,1/Rright/varepsilon2right) のサンプル複雑性(ログファクタまで)で達成している。
  論文  参考訳（メタデータ） (2024-12-27T16:37:33Z)
• Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
  本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。 ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。 Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
  論文  参考訳（メタデータ） (2024-10-10T06:33:41Z)
• MAC Advice for Facility Location Mechanism Design [12.136427429093395]
  我々は、$k$-facility位置決め機構設計問題について検討する。 以前のモデルとは異なり、$k$の最適施設位置の予測は各エージェントの位置の予測に対して$n$の予測を受ける。 予測された位置の$delta$-fractionの一部が任意に誤りを許容され、残りの予測は$varepsilon$-errorまで修正される。
  論文  参考訳（メタデータ） (2024-03-18T18:52:04Z)
• Federated Learning in the Presence of Adversarial Client Unavailability [16.201377650598516]
  フェデレートラーニング(Federated Learning)は、生データを公開せずにコラボレーティブモデルを可能にする、分散機械学習フレームワークである。 多様なハードウェアソフトウェアに制限があるため、クライアントはサーバからの計算要求に対して常に利用できるとは限らない。 戦場のような厳しい環境では、敵は特定のクライアントを選択的に黙らせることができる。
  論文  参考訳（メタデータ） (2023-05-31T15:57:07Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。 本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。 この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
  論文  参考訳（メタデータ） (2022-09-16T09:38:38Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  我々は、強い比例性は動機が良く基本的な公理であるが、その性質を満たす決定論的戦略防御機構は存在しないことを示した。 次に、予測において強い比例性を満たすランダムランクと呼ばれるランダム化メカニズムを同定する。 我々の主な特徴はランダムランクを、普遍的真理性、普遍的匿名性、期待における強い比喩性を達成するユニークなメカニズムとして特徴づけている。
  論文  参考訳（メタデータ） (2022-05-30T00:51:57Z)
• On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
  機構Kは各入力における機構Pよりも社会的コストが小さいことが分かる。 また、メカニズムPの平均ケース近似比は、同じ定数に収束する。
  論文  参考訳（メタデータ） (2022-04-14T20:57:50Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness [50.96431444396752]
  主な課題は、各ランダム化メカニズムの適切性を評価する方法である。 まず最初に、ガウスのメカニズムが$ell$-normを証明するための適切な選択肢であると結論付ける。 驚いたことに、ガウスのメカニズムは指数機構の代わりに$ell_infty$-normを証明するための適切な選択肢でもある。
  論文  参考訳（メタデータ） (2020-05-15T03:54:53Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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