論文の概要: Two-Stage Facility Location Games with Strategic Clients and Facilities
- arxiv url: http://arxiv.org/abs/2105.01425v1
- Date: Tue, 4 May 2021 11:27:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-05 12:49:56.343155
- Title: Two-Stage Facility Location Games with Strategic Clients and Facilities
- Title(参考訳): 戦略的顧客と施設を有する二段階施設配置ゲーム
- Authors: Simon Krogmann, Pascal Lenzner, Louise Molitor, Alexander Skopalik
- Abstract要約: 施設と顧客の両方が戦略的かつ大きな影響を与える非協力的な施設配置ゲームについて考察する。
当社のモデルでは,各施設の場所は,顧客を引き寄せる集合体を持ち,各クライアントは,その消費能力に応じた一組のショッピングロケーションと重みを有する。
我々は,準ゲーム完全平衡が存在することを示し,無政府価格と安定価格にほぼ一定の定数を与える。
- 参考スコア(独自算出の注目度): 64.89284690002836
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider non-cooperative facility location games where both facilities and
clients act strategically and heavily influence each other. This contrasts
established game-theoretic facility location models with non-strategic clients
that simply select the closest opened facility. In our model, every facility
location has a set of attracted clients and each client has a set of shopping
locations and a weight that corresponds to her spending capacity. Facility
agents selfishly select a location for opening their facility to maximize the
attracted total spending capacity, whereas clients strategically decide how to
distribute their spending capacity among the opened facilities in their
shopping range. We focus on a natural client behavior similar to classical load
balancing: our selfish clients aim for a distribution that minimizes their
maximum waiting times for getting serviced, where a facility's waiting time
corresponds to its total attracted client weight.
We show that subgame perfect equilibria exist and give almost tight constant
bounds on the Price of Anarchy and the Price of Stability, which even hold for
a broader class of games with arbitrary client behavior. Since facilities and
clients influence each other, it is crucial for the facilities to anticipate
the selfish clients' behavior when selecting their location. For this, we
provide an efficient algorithm that also implies an efficient check for
equilibrium. Finally, we show that computing a socially optimal facility
placement is NP-hard and that this result holds for all feasible client weight
distributions.
- Abstract(参考訳): 我々は,施設と顧客の両方が戦略的かつ大きな影響を与える非協力的な施設位置ゲームを考える。
これは、ゲーム理論的な施設配置モデルと、最も近いオープン施設を選択する非ストラテジッククライアントとは対照的である。
当社のモデルでは,各施設の場所は,顧客を引き寄せる集合体を持ち,各クライアントは,その消費能力に応じた一組のショッピングロケーションと重みを有する。
施設のエージェントは自発的に施設の開設場所を選択して総支出量を最大化し、一方、顧客はショッピングエリアのオープン施設間での支出能力の分配を戦略的に決定する。
私たちは、従来のロードバランシングと同じような自然なクライアントの振る舞いに注目しています。 当社の利己的なクライアントは、サービスを受けるための最大待ち時間を最小にするディストリビューションを目標としています。
サブゲーム完全平衡が存在し、任意のクライアント動作を持つより広いクラスのゲームにさえ耐えうる、アナーキーの価格と安定の価格にほぼ一定の境界を与えることを示す。
施設とクライアントは相互に影響しあうため,立地選択時の利己的なクライアントの行動を予測することが重要である。
このために,平衡の効率的なチェックを示唆する効率的なアルゴリズムを提案する。
最後に、社会的に最適な施設配置の計算はNPハードであり、この結果が全てのクライアント重量分布に成り立つことを示す。
関連論文リスト
- Equilibria in Two-Stage Facility Location with Atomic Clients [48.83208975886834]
2種類のクライアントを持つ2段階のマルチエージェントシステムとして,競争力のある施設配置を検討する。
すべてのクライアント重みが同一であれば、純粋なサブゲーム完全平衡が常に存在することを示す。
論文 参考訳(メタデータ) (2024-03-05T16:56:09Z) - Facility Location Games with Scaling Effects [69.28397508730046]
古典的な施設配置問題を考慮し、各エージェントの個々のコスト関数が、スケーリング係数によって乗算された施設からの距離と等しくなる変動を考察する。
戦略と匿名のメカニズムによって達成できる総コストと最大コストの近似比について結果が得られた。
論文 参考訳(メタデータ) (2024-02-29T07:08:18Z) - Online Resource Allocation with Non-Stationary Customers [1.4886278504056065]
非定常的な顧客到着率と未知のクリックスルー率を持つオンラインリソースアロケーションのための新しいアルゴリズムを提案する。
さまざまな顧客シナリオに対して,アプローチが最適に近い収益を生み出すことを示すため,広範な数値実験を実施している。
論文 参考訳(メタデータ) (2024-01-30T12:19:09Z) - Nash Welfare and Facility Location [82.81742334337336]
沿線にエージェントを配置する施設を配置することの問題点を考察する。
エージェントのユーティリティの産物として定義されたナッシュの福祉目的機能は、公正性と効率性の妥協をもたらすことが知られている。
論文 参考訳(メタデータ) (2023-10-06T09:06:44Z) - Federated Learning as a Network Effects Game [32.264180198812745]
Federated Learning (FL) は、ローカルデータを直接共有することなく、機械学習の精度を向上させるために、多くのクライアント間のコラボレーションを促進することを目的としている。
実際には、クライアントは、特にプライバシや計算などの問題に関連する潜在的なコストを考慮して、FLに参加することの恩恵を受けないかもしれません。
私たちはFLにおけるクライアントの振る舞いをネットワークエフェクトゲームとしてモデル化し、各クライアントの利点はネットワークに参加する他のクライアントに依存します。
論文 参考訳(メタデータ) (2023-02-16T19:10:12Z) - Strategic Facility Location with Clients that Minimize Total Waiting
Time [74.49811067467118]
本研究では,非協調型施設位置ゲームにおいて,施設やクライアントが戦略的に行動する場所ゲームについて検討する。
サブゲーム完全平衡は、このゲームの全ての事例に存在せず、その存在はNPハードで決定できることを証明している。
論文 参考訳(メタデータ) (2022-11-25T10:43:57Z) - Personalized Federated Learning with First Order Model Optimization [76.81546598985159]
そこで我々は,各クライアントが他のクライアントと連携して,クライアント固有の目的ごとのより強力なモデルを得る,フェデレーション学習の代替案を提案する。
基礎となるデータ分布やクライアントの類似性に関する知識を前提とせず、各クライアントが関心のある任意のターゲット分布を最適化できるようにします。
この手法は既存の代替品を上回り、ローカルデータ配信以外の転送のようなパーソナライズされたFLの新機能を可能にする。
論文 参考訳(メタデータ) (2020-12-15T19:30:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。