論文の概要: An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems
- arxiv url: http://arxiv.org/abs/2410.02400v1
- Date: Thu, 3 Oct 2024 11:27:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 03:30:37.560710
- Title: An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems
- Title(参考訳): 良性一般化ナッシュ平衡問題に対するオンライン対応点法
- Authors: Sarah Sachs, Hedi Hadiji, Tim van Erven, Mathias Staudigl,
- Abstract要約: 一般化されたナッシュ均衡ゲームのための新しいオンライン実現可能な点法を提案する。
エージェント間の通信が制限されているという仮定の下で、本手法は実現可能性を保証する。
我々は、我々の方法の平衡への収束が保証される良性一般化ナッシュ均衡問題のクラスを特定する。
- 参考スコア(独自算出の注目度): 4.243592852049963
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We consider a repeatedly played generalized Nash equilibrium game. This induces a multi-agent online learning problem with joint constraints. An important challenge in this setting is that the feasible set for each agent depends on the simultaneous moves of the other agents and, therefore, varies over time. As a consequence, the agents face time-varying constraints, which are not adversarial but rather endogenous to the system. Prior work in this setting focused on convergence to a feasible solution in the limit via integrating the constraints in the objective as a penalty function. However, no existing work can guarantee that the constraints are satisfied for all iterations while simultaneously guaranteeing convergence to a generalized Nash equilibrium. This is a problem of fundamental theoretical interest and practical relevance. In this work, we introduce a new online feasible point method. Under the assumption that limited communication between the agents is allowed, this method guarantees feasibility. We identify the class of benign generalized Nash equilibrium problems, for which the convergence of our method to the equilibrium is guaranteed. We set this class of benign generalized Nash equilibrium games in context with existing definitions and illustrate our method with examples.
- Abstract(参考訳): 繰り返しプレイされた一般化ナッシュ均衡ゲームを考える。
これにより、共同制約を伴う複数エージェントのオンライン学習問題が発生する。
この設定における重要な課題は、各エージェントの実行可能なセットが他のエージェントの同時移動に依存するため、時間とともに変化することである。
その結果、エージェントは時間的な制約に直面し、逆境ではなく、システムに内在的である。
この設定における以前の研究は、目的の制約をペナルティ関数として統合することで、限界における実現可能な解への収束に焦点を当てていた。
しかしながら、すべての反復に対して制約が満たされることを保証し、同時に一般化されたナッシュ均衡への収束を保証するような既存の作業は存在しない。
これは基本的な理論的関心と実践的関連性の問題である。
本研究では,新しいオンライン・ファジブル・ポイント・メソッドを提案する。
エージェント間の通信が制限されているという仮定の下で、本手法は実現可能性を保証する。
我々は、我々の方法の平衡への収束が保証される良性一般化ナッシュ均衡問題のクラスを特定する。
このような良質な一般化されたナッシュ均衡ゲームは、既存の定義とコンテキストで設定し、実例で方法を説明する。
関連論文リスト
- Independent RL for Cooperative-Competitive Agents: A Mean-Field Perspective [11.603515105957461]
この論文では、各チーム間には協力関係があるが、異なるチーム間での一般的な競争があるように、チームにグループ化されるエージェント間の強化学習(RL)に対処する。
論文 参考訳(メタデータ) (2024-03-17T21:11:55Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
論文 参考訳(メタデータ) (2024-03-13T01:51:30Z) - Independent Learning in Constrained Markov Potential Games [19.083595175045073]
制約付きマルコフゲームは、マルチエージェント強化学習問題をモデル化するための正式なフレームワークを提供する。
近似的制約付きナッシュ平衡を学習するための独立ポリシー勾配アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-27T20:57:35Z) - Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。
従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。
我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
論文 参考訳(メタデータ) (2023-12-13T09:31:30Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳(メタデータ) (2023-03-02T05:08:15Z) - Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。
低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。
上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
論文 参考訳(メタデータ) (2023-02-20T16:05:04Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳(メタデータ) (2022-11-29T05:16:41Z) - Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution
Concept over Nash Equilibria [61.093297204685264]
マルチエージェント強化学習における効果的なアプローチは,エージェントの学習プロセスを検討し,今後の政策に影響を与えることである。
この新たな解の概念は、ナッシュ均衡のような標準解の概念が活性平衡の特別な場合である、という一般的なものである。
我々は,ゲーム理論の観点から,ナッシュ平衡が知られている実例を綿密に研究することにより,アクティブ平衡を解析する。
論文 参考訳(メタデータ) (2022-10-28T14:45:39Z) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳(メタデータ) (2022-10-24T09:32:40Z) - Personalized incentives as feedback design in generalized Nash
equilibrium problems [6.10183951877597]
定常および時間変化の非単調なナッシュ平衡問題について検討する。
半分散Nash平衡探索アルゴリズムを設計する。
いくつかの企業が提供している配車サービスについては,サービスオーケストレーションとして検討しています。
論文 参考訳(メタデータ) (2022-03-24T09:24:29Z) - Survival of the strictest: Stable and unstable equilibria under
regularized learning with partial information [32.384868685390906]
一般Nプレイヤーゲームにおける非回帰学習のナッシュ平衡収束特性について検討する。
ナッシュ平衡の安定性と支持との包括的な等価性を確立します。
ゲームにおける非学習の日々の行動を予測するための明確な洗練基準を提供する。
論文 参考訳(メタデータ) (2021-01-12T18:55:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。