論文の概要: Equilibria in Two-Stage Facility Location with Atomic Clients
- arxiv url: http://arxiv.org/abs/2403.03114v2
- Date: Tue, 9 Jul 2024 15:31:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-10 23:51:16.448935
- Title: Equilibria in Two-Stage Facility Location with Atomic Clients
- Title(参考訳): アトミッククライアントを用いた2段階施設における平衡
- Authors: Simon Krogmann, Pascal Lenzner, Alexander Skopalik, Marc Uetz, Marnix C. Vos,
- Abstract要約: 2種類のクライアントを持つ2段階のマルチエージェントシステムとして,競争力のある施設配置を検討する。
すべてのクライアント重みが同一であれば、純粋なサブゲーム完全平衡が常に存在することを示す。
- 参考スコア(独自算出の注目度): 46.08471181378526
- 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ドルを課す。
関連論文リスト
- Emulating Full Client Participation: A Long-Term Client Selection Strategy for Federated Learning [48.94952630292219]
本稿では,クライアントの完全参加によって達成されるパフォーマンスをエミュレートする新しいクライアント選択戦略を提案する。
1ラウンドで、クライアントサブセットとフルクライアントセット間の勾配空間推定誤差を最小化し、クライアントを選択する。
複数ラウンド選択において、類似したデータ分布を持つクライアントが選択される頻度に類似することを保証する、新しい個性制約を導入する。
論文 参考訳(メタデータ) (2024-05-22T12:27:24Z) - 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) - Strategic Facility Location with Clients that Minimize Total Waiting Time [52.3893099287099]
本研究では,非協調型施設位置ゲームにおいて,施設やクライアントが戦略的に行動する場所ゲームについて検討する。
サブゲーム完全平衡は、このゲームの全ての事例に存在せず、その存在は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 [50.12183574133361]
我々は,施設と顧客の両方が戦略的かつ大きな影響を与える非協力的な施設位置ゲームについて検討する。
当社のモデルでは,各施設の場所は,顧客を引き寄せる集合体を持ち,各クライアントは,その消費能力に応じた一組のショッピングロケーションと重みを有する。
サブゲーム完全平衡が存在することを示し、アナーキーの価格と安定の価格にほぼ一定の境界を与える。
論文 参考訳(メタデータ) (2021-05-04T11:27:09Z) - Towards Federated Learning With Byzantine-Robust Client Weighting [2.294014185517203]
フェデレート学習のための実践的な重み付けに基づく事前処理手法を提案する。
本手法は, モデル品質とビザンツのロバスト性とのバランスが良好であることを示す。
論文 参考訳(メタデータ) (2020-04-10T10:59:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。