論文の概要: Sink equilibria and the attractors of learning in games
- arxiv url: http://arxiv.org/abs/2502.07975v1
- Date: Tue, 11 Feb 2025 21:40:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-13 13:44:54.282877
- Title: Sink equilibria and the attractors of learning in games
- Title(参考訳): ゲームにおけるシンク均衡と学習の魅力
- Authors: Oliver Biggar, Christos Papadimitriou,
- Abstract要約: ゲーム理論において、学習力学の限界行動(すなわち、引き付け子)を特徴づけることは、最も基本的なオープンな質問の1つである。
位相的構成を通して、一対一予想が偽であることを示す。
第2に,一対一の予想が真であることを示すことによって,二プレーヤゲームにおけるアトラクタ特徴化問題を推し進める。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: Characterizing the limit behavior -- that is, the attractors -- of learning dynamics is one of the most fundamental open questions in game theory. In recent work in this front, it was conjectured that the attractors of the replicator dynamic are in one-to-one correspondence with the sink equilibria of the game -- the sink strongly connected components of a game's preference graph -- , and it was established that they do stand in at least one-to-many correspondence with them. We make threefold progress on the problem of characterizing attractors. First, we show through a topological construction that the one-to-one conjecture is false. Second, we make progress on the attractor characterization problem for two-player games by establishing that the one-to-one conjecture is true in the absence of a local pattern called a weak local source -- a pattern that is absent from zero-sum games. Finally, we look -- for the first time in this context -- at fictitious play, the longest-studied learning dynamic, and examine to what extent the conjecture generalizes there. We establish that under fictitious play, sink equilibria always contain attractors (sometimes strictly), and every attractor corresponds to a strongly connected set of nodes in the preference graph.
- Abstract(参考訳): ゲーム理論において、学習力学の限界行動(すなわち、引き付け子)を特徴づけることは、最も基本的なオープンな質問の1つである。
この分野での最近の研究で、レプリケータのダイナミックな魅力はゲームのシンク平衡(ゲームの嗜好グラフのシンクと強く結びついているコンポーネント)と1対1の対応にあると推測され、それらと少なくとも1対1の対応で立つことが確立された。
我々は、魅力を特徴づける問題を3倍に進める。
まず、トポロジカルな構成を通して、1対1の予想が偽であることを示す。
第2に,ゼロサムゲームにない局所的パターンである弱局所的パターンが存在しない場合に,一対一の予想が真であることを確立することにより,二プレイヤーゲームにおけるアトラクタ特徴づけ問題を進行させる。
最後に、この文脈ではじめて、架空の遊びにおいて、最も長く研究された学習力学を考察し、予想がそこで一般化される程度を調べます。
架空の遊びの下では、シンク平衡は常に誘引子(しばしば厳密には)を含み、全ての誘引子は選好グラフ内の強く連結されたノードの集合に対応する。
関連論文リスト
- Swim till You Sink: Computing the Limit of a Game [26.785274326413585]
本研究では,ノイズレプリケータ力学と呼ばれる自然力学のクラスにおける挙動の計算問題について検討する。
実験により, 標本化とシミュレーションにより, 合理的な大ゲームの限界分布を正確に推定できることを示した。
論文 参考訳(メタデータ) (2024-08-20T19:09:21Z) - A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights [24.800126996235512]
ゲームは、ダイナミクスの長時間動作がよく理解されている単純なコンポーネントに分解する。
特に指数的/乗法的重み(EW)スキームの力学はヘルムホルツの定理のユークリッドアンダーピンニングとは相容れない。
我々は、よく知られたゲームの分解と、ポテンシャルおよび調和成分への深い関係を確立する。
論文 参考訳(メタデータ) (2024-05-12T08:58:35Z) - On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。
我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。
また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
論文 参考訳(メタデータ) (2023-01-26T17:25:45Z) - 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) - Evolutionary Game-Theoretical Analysis for General Multiplayer
Asymmetric Games [22.753799819424785]
不正確さなしに、ペイオフテーブルと動的分析のギャップを埋める。
いくつかの古典ゲームにおいて,本手法を最先端のゲームと比較する。
論文 参考訳(メタデータ) (2022-06-22T14:06:23Z) - Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。
我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。
本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
論文 参考訳(メタデータ) (2020-12-10T18:30:21Z) - No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。
厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。
この結果は,学習過程の結果を予測する上で重要な意味を持つ。
論文 参考訳(メタデータ) (2020-10-19T13:49:06Z) - Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。
我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。
我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
論文 参考訳(メタデータ) (2020-05-28T13:47:09Z) - Real World Games Look Like Spinning Tops [27.182163984605193]
本稿では,実世界のゲーム(例えば,Tic-Tac-Toe,Go,StarCraft II)の幾何学的性質について検討する。
それらの幾何学構造は回転するトップに似ていると仮定する。
我々は、この幾何学が現実世界のゲームに広く存在することを証明し、その時間的性質を明らかにする。
エージェントの訓練に戦略の人口がなぜ必要か,ゲームの構造にどの程度の人口が関係しているかを明らかにする。
論文 参考訳(メタデータ) (2020-04-20T17:41:42Z) - No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。
広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。
提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
論文 参考訳(メタデータ) (2020-04-01T17:39:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。