論文の概要: Smooth Nash Equilibria: Algorithms and Complexity

• arxiv url: http://arxiv.org/abs/2309.12226v1
• Date: Thu, 21 Sep 2023 16:22:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-22 14:19:55.464731
• Title: Smooth Nash Equilibria: Algorithms and Complexity
• Title（参考訳）: Smooth Nash Equilibria:アルゴリズムと複雑さ
• Authors: Constantinos Daskalakis and Noah Golowich and Nika Haghtalab and Abhishek Shetty
• Abstract要約: ナッシュ均衡の概念の根本的な欠点は、その計算的推論性である。 $sigma$-smooth Nash均衡では、プレイヤーは$sigma$-smooth戦略への最良の偏差よりも少なくとも高いユーティリティを達成する必要がある。 弱いと強い$sigma$-smooth Nash平衡は、Nash平衡よりも優れた計算特性を持つことを示す。
• 参考スコア（独自算出の注目度）: 41.60085486664709
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis, we introduce a relaxed variant of Nash equilibrium called $\sigma$-smooth Nash equilibrium, for a smoothness parameter $\sigma$. In a $\sigma$-smooth Nash equilibrium, players only need to achieve utility at least as high as their best deviation to a $\sigma$-smooth strategy, which is a distribution that does not put too much mass (as parametrized by $\sigma$) on any fixed action. We distinguish two variants of $\sigma$-smooth Nash equilibria: strong $\sigma$-smooth Nash equilibria, in which players are required to play $\sigma$-smooth strategies under equilibrium play, and weak $\sigma$-smooth Nash equilibria, where there is no such requirement. We show that both weak and strong $\sigma$-smooth Nash equilibria have superior computational properties to Nash equilibria: when $\sigma$ as well as an approximation parameter $\epsilon$ and the number of players are all constants, there is a constant-time randomized algorithm to find a weak $\epsilon$-approximate $\sigma$-smooth Nash equilibrium in normal-form games. In the same parameter regime, there is a polynomial-time deterministic algorithm to find a strong $\epsilon$-approximate $\sigma$-smooth Nash equilibrium in a normal-form game. These results stand in contrast to the optimal algorithm for computing $\epsilon$-approximate Nash equilibria, which cannot run in faster than quasipolynomial-time. We complement our upper bounds by showing that when either $\sigma$ or $\epsilon$ is an inverse polynomial, finding a weak $\epsilon$-approximate $\sigma$-smooth Nash equilibria becomes computationally intractable.
• Abstract（参考訳）: ナッシュ均衡の概念の根本的な欠点は計算の難易度であり、正規形式ゲームにおけるナッシュ平衡の近似はPPADハードである。 本稿では、滑らかな解析のアイデアに触発されて、滑らかなパラメータ$\sigma$-smooth Nash平衡と呼ばれる緩和されたナッシュ均衡を導入します。 シュモース・ナッシュ均衡(英語版)では、プレイヤーは任意の固定アクションに対して(シュモース・ナッシュによってパラメータ化されるような)過剰な質量を課さない分布であるシュモース戦略(英語版)への最善の逸脱を少なくとも達成する必要がある。 強固な$\sigma$-smooth nash equilibria は、プレイヤーが均衡プレイの下で$\sigma$-smooth戦略をプレイすることを要求され、弱の$\sigma$-smooth nash equilibria はそのような要求がない。 弱および強の$\sigma$-smooth Nash平衡がナッシュ平衡よりも優れた計算特性を持つことを示す:$\sigma$と近似パラメータ$\epsilon$とプレイヤー数はすべて定数であるとき、正規形式ゲームにおいて弱の$\epsilon$-approximate$\sigma$-smooth Nash平衡を求める定数時間ランダム化アルゴリズムが存在する。 同じパラメータ体系では、正規形式ゲームにおいて強い$\epsilon$-approximate $\sigma$-smooth Nash平衡を求める多項式時間決定論的アルゴリズムが存在する。 これらの結果は、準ポリノミアル時間よりも高速に動作できない$\epsilon$-approximate Nash平衡の最適アルゴリズムとは対照的である。 上限を補うために、$\sigma$ または $\epsilon$ が逆多項式であるとき、弱 $\epsilon$-approximate $\sigma$-smooth nash equilibria を見つけることは計算的に難解になることを示す。

関連論文リスト

• Games played by Exponential Weights Algorithms [0.0]
  各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。 厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
  論文  参考訳（メタデータ） (2024-07-09T08:49:51Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。 また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
  論文  参考訳（メタデータ） (2024-03-13T01:51:30Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricing [0.0]
  競技マルコフゲーム(MG)環境におけるナッシュ均衡学習について検討する。 我々は、近似的なナッシュ平衡を求めるための新しいモデルフリー手法を開発した。 我々は、特に動的価格領域において、近似的なナッシュ均衡を学習できることを実証する。
  論文  参考訳（メタデータ） (2022-07-13T19:27:07Z)
• Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics [28.815822236291392]
  ゲーム力学が$epsilon$-Nash平衡に収束できないことを示す。 また、$epsilon$-approximate Nash equilibriaに対してより強い結果を示す。
  論文  参考訳（メタデータ） (2022-03-26T18:27:40Z)
• Multi-Leader Congestion Games with an Adversary [0.5914780964919123]
  本研究では,複数のユーザ(リーダ)がリソースセットから1つのリソースを選択するマルチリーダシングルフォロワ・コングリゲーションゲームについて検討する。 純粋なナッシュ平衡は存在せず、従って近似平衡を考える。 与えられたインスタンスのすべての$alpha$-approximate equilibriaの中で、最小の$alpha$で、最適な近似平衡を効率的に計算する方法を示す。
  論文  参考訳（メタデータ） (2021-12-14T14:47:43Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。 ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
  論文  参考訳（メタデータ） (2021-08-17T07:06:46Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。 厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。 この結果は,学習過程の結果を予測する上で重要な意味を持つ。
  論文  参考訳（メタデータ） (2020-10-19T13:49:06Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)

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

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