論文の概要: Swim till You Sink: Computing the Limit of a Game

• arxiv url: http://arxiv.org/abs/2408.11146v1
• Date: Tue, 20 Aug 2024 19:09:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-22 21:16:53.884934
• Title: Swim till You Sink: Computing the Limit of a Game
• Title（参考訳）: Swim until You Sink: ゲームの限界を計算する
• Authors: Rashida Hakim, Jason Milionis, Christos Papadimitriou, Georgios Piliouras,
• Abstract要約: 本研究では,ノイズレプリケータ力学と呼ばれる自然力学のクラスにおける挙動の計算問題について検討する。 実験により, 標本化とシミュレーションにより, 合理的な大ゲームの限界分布を正確に推定できることを示した。
• 参考スコア（独自算出の注目度）: 26.785274326413585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: During 2023, two interesting results were proven about the limit behavior of game dynamics: First, it was shown that there is a game for which no dynamics converges to the Nash equilibria. Second, it was shown that the sink equilibria of a game adequately capture the limit behavior of natural game dynamics. These two results have created a need and opportunity to articulate a principled computational theory of the meaning of the game that is based on game dynamics. Given any game in normal form, and any prior distribution of play, we study the problem of computing the asymptotic behavior of a class of natural dynamics called the noisy replicator dynamics as a limit distribution over the sink equilibria of the game. When the prior distribution has pure strategy support, we prove this distribution can be computed efficiently, in near-linear time to the size of the best-response graph. When the distribution can be sampled -- for example, if it is the uniform distribution over all mixed strategy profiles -- we show through experiments that the limit distribution of reasonably large games can be estimated quite accurately through sampling and simulation.
• Abstract（参考訳）: 2023年、ゲーム力学の極限挙動について2つの興味深い結果が証明された。 第2に,ゲームにおけるシンク平衡は,自然ゲーム力学の限界挙動を適切に捉えていることを示した。 これらの2つの結果は、ゲーム力学に基づくゲームの意味の原理的な計算理論を明確にする必要性と機会を生み出している。 正規形式の任意のゲームと事前のプレイ分布が与えられた場合、我々はゲームのシンク平衡上の極限分布としてノイズレプリケータ力学と呼ばれる自然力学のクラスの漸近挙動を計算する問題を研究する。 先行分布が純粋戦略サポートを持つ場合、この分布を最適応答グラフのサイズにほぼ直線的に効率よく計算できることを示す。 例えば、全ての混合戦略プロファイルに対する均一分布であるような分布をサンプリングできる場合、実験を通して、合理的に大きなゲームの極限分布をサンプリングとシミュレーションによって正確に推定できることが示される。

関連論文リスト

• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• 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)
• Provably convergent quasistatic dynamics for mean-field two-player zero-sum games [10.39511271647025]
  我々は、ある確率分布がワッセルシュタイン勾配の流れに従うような準静的ワッセルシュタイン勾配流れのダイナミクスを考察し、他方の確率分布は常に平衡状態にある。 確率分布の連続力学に着想を得て、内外反復を伴う擬静的なランゲヴィン勾配降下法を導出する。
  論文  参考訳（メタデータ） (2022-02-15T20:19:42Z)
• Multiplayer Performative Prediction: Learning in Decision-Dependent Games [18.386569111954213]
  本稿では,マルチプレイヤー演奏予測のための新たなゲーム理論の枠組みを定式化する。 我々は、(i)パフォーマンス的に安定な平衡と(ii)ゲームのナッシュ平衡という、2つの異なる解の概念に焦点を当てる。 軽微な仮定の下では、様々なアルゴリズムにより、性能的に安定な平衡を効率的に見つけることができることを示す。
  論文  参考訳（メタデータ） (2022-01-10T15:31:10Z)
• Online Learning in Periodic Zero-Sum Games [27.510231246176033]
  これらの力学系の複雑で非自律的な性質にもかかわらず、ポアンカーの再発は確実に一般化することを示す。
  論文  参考訳（メタデータ） (2021-11-05T10:36:16Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。 我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。 我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
  論文  参考訳（メタデータ） (2020-05-28T13:47:09Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。 また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
  論文  参考訳（メタデータ） (2020-02-19T21:36:58Z)

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

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