論文の概要: Approximating Nash Equilibrium in Random Graphical Games

• arxiv url: http://arxiv.org/abs/2112.03442v1
• Date: Tue, 7 Dec 2021 01:40:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-10 05:03:58.728349
• Title: Approximating Nash Equilibrium in Random Graphical Games
• Title（参考訳）: ランダムグラフィカルゲームにおけるナッシュ平衡の近似
• Authors: Morris Yau
• Abstract要約: マルチエージェントゲームにおけるナッシュ均衡は、ゲーム理論とコンピュータ科学のインターフェイスにおける長年の課題である。 確率の高い辺密度のポリ(k, 1/epsilon, ln(N))$より大きいランダムグラフ上で、ポリマトリクスゲームのエプシロン近似ナッシュ平衡を計算するための準ポリリノミカル時間近似スキーム(QPTAS)を提供する。 同じランタイムで、エプシロン近似ナッシュ均衡を計算することができ、エプシロン近似はゲームのナッシュ均衡の最大社会福祉を達成できる。
• 参考スコア（独自算出の注目度）: 3.42658286826597
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Computing Nash equilibrium in multi-agent games is a longstanding challenge at the interface of game theory and computer science. It is well known that a general normal form game in N players and k strategies requires exponential space simply to write down. This Curse of Multi-Agents prompts the study of succinct games which can be written down efficiently. A canonical example of a succinct game is the graphical game which models players as nodes in a graph interacting with only their neighbors in direct analogy with markov random fields. Graphical games have found applications in wireless, financial, and social networks. However, computing the nash equilbrium of graphical games has proven challenging. Even for polymatrix games, a model where payoffs to an agent can be written as the sum of payoffs of interactions with the agent's neighbors, it has been shown that computing an epsilon approximate nash equilibrium is PPAD hard for epsilon smaller than a constant. The focus of this work is to circumvent this computational hardness by considering average case graph models i.e random graphs. We provide a quasipolynomial time approximation scheme (QPTAS) for computing an epsilon approximate nash equilibrium of polymatrix games on random graphs with edge density greater than poly(k, 1/epsilon, ln(N))$ with high probability. Furthermore, with the same runtime we can compute an epsilon-approximate Nash equilibrium that epsilon-approximates the maximum social welfare of any nash equilibrium of the game. Our primary technical innovation is an "accelerated rounding" of a novel hierarchical convex program for the nash equilibrium problem. Our accelerated rounding also yields faster algorithms for Max-2CSP on the same family of random graphs, which may be of independent interest.
• Abstract（参考訳）: マルチエージェントゲームにおけるナッシュ均衡の計算は、ゲーム理論とコンピュータ科学のインターフェイスにおける長年の課題である。 N のプレイヤーと k の戦略における一般的な正規形式ゲームは単に書き下すために指数空間を必要とすることはよく知られている。 このマルチエージェントの曲線は、効率的に書き下ろすことができる簡潔なゲームの研究を促す。 簡潔なゲームの典型例はグラフィカルゲームであり、マルコフランダム場と直接類似して隣人とのみ相互作用するグラフ内のノードとしてプレイヤーをモデル化する。 グラフィックゲームは、無線、金融、ソーシャルネットワークに応用されている。 しかし、グラフィックゲームのnash equilbriumの計算は困難であることが証明されている。 ポリマトリクスゲームにおいても、エージェントへの支払いをエージェントの隣人との相互作用の支払いの和として記述することができるが、エプシロン近似ナッシュ平衡の計算は定数よりも小さいエプシロンに対してPPAD困難であることが示されている。 この研究の焦点は、平均ケースグラフモデル、すなわちランダムグラフを考慮し、この計算困難を回避することである。 確率の高い辺密度のポリ(k, 1/epsilon, ln(N))$より大きいランダムグラフ上で、ポリマトリクスゲームのエプシロン近似ナッシュ平衡を計算するための準多項式時間近似スキーム(QPTAS)を提供する。 さらに、同じランタイムで、ゲームの任意のナッシュ平衡の最大社会福祉を近似するエプシロン近似ナッシュ平衡を計算することができる。 我々の主要な技術的革新は、ナッシュ均衡問題のための新しい階層的凸プログラムの「加速丸め」である。 我々の高速化された丸みは、同じランダムグラフ群上のmax-2cspのより高速なアルゴリズムも生み出します。

関連論文リスト

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics [28.815822236291392]
  ゲーム力学が$epsilon$-Nash平衡に収束できないことを示す。 また、$epsilon$-approximate Nash equilibriaに対してより強い結果を示す。
  論文  参考訳（メタデータ） (2022-03-26T18:27:40Z)
• Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
  状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。 我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。 我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
  論文  参考訳（メタデータ） (2022-02-08T20:09:47Z)
• Learning Graphon Mean Field Games and Approximate Nash Equilibria [33.77849245250632]
  本稿では,弱い相互作用を持つグラノン平均場ゲームに対して,離散時間による新たな定式化を提案する。 理論的には、グラノン平均場解の広範かつ厳密な存在と近似特性を与える。 我々は,多くのエージェントを持つ非実現不可能な大密度グラフゲームにおいて,可塑性近似ナッシュ平衡を得ることに成功した。
  論文  参考訳（メタデータ） (2021-11-29T16:16:11Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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