論文の概要: Equilibria in Two-Stage Facility Location with Atomic Clients
- arxiv url: http://arxiv.org/abs/2403.03114v1
- Date: Tue, 5 Mar 2024 16:56:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-06 14:12:54.512738
- Title: Equilibria in Two-Stage Facility Location with Atomic Clients
- Title(参考訳): 原子クライアントを持つ2段階施設における平衡
- Authors: Simon Krogmann, Pascal Lenzner, Alexander Skopalik, Marc Uetz and
Marnix C. Vos
- Abstract要約: 2種類のクライアントを持つ2段階のマルチエージェントシステムとして,競争力のある施設配置を検討する。
すべてのクライアント重みが同一であれば、純粋なサブゲーム完全平衡が常に存在することを示す。
- 参考スコア(独自算出の注目度): 48.83208975886834
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider competitive facility location as a two-stage multi-agent system
with two types of clients. For a given host graph with weighted clients on the
vertices, first facility agents strategically select vertices for opening their
facilities. Then, the clients strategically select which of the opened
facilities in their neighborhood to patronize. Facilities want to attract as
much client weight as possible, clients want to minimize congestion on the
chosen facility.
All recently studied versions of this model assume that clients can split
their weight strategically. We consider clients with unsplittable weights, but
allow mixed strategies. So clients may randomize over which facility to
patronize. Besides modeling a natural client behavior, this subtle change
yields drastic changes, e.g., for a given facility placement, qualitatively
different client equilibria are possible.
As our main result, we show that pure subgame perfect equilibria always exist
if all client weights are identical. For this, we use a novel potential
function argument, employing a hierarchical classification of the clients and
sophisticated rounding in each step. In contrast, for non-identical clients, we
show that deciding the existence of even approximately stable states is
computationally intractable. On the positive side, we give a tight bound of 2
on the price of anarchy which implies high social welfare of equilibria, if
they exist.
- Abstract(参考訳): 2種類のクライアントを持つ2段階マルチエージェントシステムとして,競争力のある施設配置を検討する。
頂点上の重み付きクライアントを持つ所定のホストグラフに対して、最初の施設エージェントは、施設を開くための頂点を戦略的に選択する。
そして、クライアントは、近隣のオープン施設のどれかを戦略的に選択する。
施設は可能な限りクライアントの重みを引き付け、顧客は選択した施設の混雑を最小限に抑えることを望んでいる。
最近研究された全てのモデルでは、クライアントは戦略的に重量を分割できると仮定している。
我々は、分割不能な重みを持つ顧客について検討するが、混合戦略を許容する。
したがって、クライアントはどの施設をパトロンにするかをランダム化することができる。
自然なクライアントの振る舞いをモデル化するのに加えて、この微妙な変更は、例えば所定の施設配置に対して、質的に異なるクライアント平衡が可能であるなど、劇的な変化をもたらす。
主結果として,すべてのクライアント重みが同一であれば,純部分ゲーム完全平衡が常に存在することを示す。
このために,クライアントの階層的分類と,各ステップにおける洗練された丸め法を用いて,新しい潜在的な関数引数を用いる。
対照的に、非同一のクライアントに対しては、概安定状態の存在を決定することは計算的に難解であることを示す。
正の面では、もし存在すれば、均衡の社会福祉が高いことを意味する無政府価格の2つに厳密な境界を与える。
関連論文リスト
- Decentralized Personalized Online Federated Learning [13.76896613426515]
バニラ連合学習は、オンライン環境での学習、各クライアントでパーソナライズされたモデル学習、分散環境での学習をサポートしない。
我々は,これら3つの側面を同時に考慮した,分散化された個人化オンラインフェデレーションラーニングを新たに提案する。
提案手法の有効性とロバスト性を実世界の3項目推薦データセットと1つの空気質予測データセットで検証した。
論文 参考訳(メタデータ) (2023-11-08T16:42:10Z) - Timely Asynchronous Hierarchical Federated Learning: Age of Convergence [59.96266198512243]
クライアント-エッジ-クラウドフレームワークを用いた非同期階層型フェデレーション学習環境について検討する。
クライアントはトレーニングされたパラメータをエッジサーバと交換し、ローカルに集約されたモデルを更新する。
各クライアントの目標は、クライアントのタイムラインを維持しながら、グローバルモデルに収束することだ。
論文 参考訳(メタデータ) (2023-06-21T17:39:16Z) - Federated Learning of Shareable Bases for Personalization-Friendly Image
Classification [54.72892987840267]
FedBasisは、いくつかの共有可能なベースモデルの集合を学習し、リニアに組み合わせて、クライアント用のパーソナライズされたモデルを形成することができる。
具体的には、新しいクライアントの場合、モデルの重みではなく、小さな組み合わせ係数のみを学ぶ必要がある。
また、FedBasisの有効性と適用性を示すために、画像分類のためのより実用的なPFLテストベッドを提案する。
論文 参考訳(メタデータ) (2023-04-16T20:19:18Z) - Client-specific Property Inference against Secure Aggregation in
Federated Learning [52.8564467292226]
フェデレートラーニングは、さまざまな参加者の間で共通のモデルを協調的に訓練するための、広く使われているパラダイムとなっている。
多くの攻撃は、メンバーシップ、資産、または参加者データの完全な再構築のような機密情報を推測することは依然として可能であることを示した。
単純な線形モデルでは、集約されたモデル更新からクライアント固有のプロパティを効果的にキャプチャできることが示される。
論文 参考訳(メタデータ) (2023-03-07T14:11:01Z) - Strategic Facility Location with Clients that Minimize Total Waiting
Time [74.49811067467118]
本研究では,非協調型施設位置ゲームにおいて,施設やクライアントが戦略的に行動する場所ゲームについて検討する。
サブゲーム完全平衡は、このゲームの全ての事例に存在せず、その存在はNPハードで決定できることを証明している。
論文 参考訳(メタデータ) (2022-11-25T10:43:57Z) - Personalized Federated Learning with Exact Stochastic Gradient Descent [15.666401346622575]
我々は、勾配SGD降下の正確な更新を実現するためのパーソナライズされたベンチマークに対する新しいアプローチを提案する。
本稿では、各最適化ラウンドにおいて、ランダムに選択されたクライアントが、損失関数の最適化に向けてクライアント固有の更新を行う新しいSGD型スキームを提案する。
これにより、クライアントと一般的なパラメータによって実行されるパーソナライズされたパラメータの正確な最小化が可能になる。
論文 参考訳(メタデータ) (2022-02-20T16:11:20Z) - Two-Stage Facility Location Games with Strategic Clients and Facilities [64.89284690002836]
施設と顧客の両方が戦略的かつ大きな影響を与える非協力的な施設配置ゲームについて考察する。
当社のモデルでは,各施設の場所は,顧客を引き寄せる集合体を持ち,各クライアントは,その消費能力に応じた一組のショッピングロケーションと重みを有する。
我々は,準ゲーム完全平衡が存在することを示し,無政府価格と安定価格にほぼ一定の定数を与える。
論文 参考訳(メタデータ) (2021-05-04T11:27:09Z) - Towards Federated Learning With Byzantine-Robust Client Weighting [2.294014185517203]
フェデレート学習のための実践的な重み付けに基づく事前処理手法を提案する。
本手法は, モデル品質とビザンツのロバスト性とのバランスが良好であることを示す。
論文 参考訳(メタデータ) (2020-04-10T10:59:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。