論文の概要: Nash, Conley, and Computation: Impossibility and Incompleteness in Game
Dynamics
- arxiv url: http://arxiv.org/abs/2203.14129v1
- Date: Sat, 26 Mar 2022 18:27:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-29 17:48:02.337580
- Title: Nash, Conley, and Computation: Impossibility and Incompleteness in Game
Dynamics
- Title（参考訳）: Nash, Conley, and Computation:ゲームダイナミクスにおける不可能性と不完全性
- Authors: Jason Milionis, Christos Papadimitriou, Georgios Piliouras, Kelly
Spendlove
- Abstract要約: ゲーム力学が$epsilon$-Nash平衡に収束できないことを示す。
また、$epsilon$-approximate Nash equilibriaに対してより強い結果を示す。
- 参考スコア（独自算出の注目度）: 28.815822236291392
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Under what conditions do the behaviors of players, who play a game
repeatedly, converge to a Nash equilibrium? If one assumes that the players'
behavior is a discrete-time or continuous-time rule whereby the current mixed
strategy profile is mapped to the next, this becomes a problem in the theory of
dynamical systems. We apply this theory, and in particular the concepts of
chain recurrence, attractors, and Conley index, to prove a general
impossibility result: there exist games for which any dynamics is bound to have
starting points that do not end up at a Nash equilibrium. We also prove a
stronger result for $\epsilon$-approximate Nash equilibria: there are games
such that no game dynamics can converge (in an appropriate sense) to
$\epsilon$-Nash equilibria, and in fact the set of such games has positive
measure. Further numerical results demonstrate that this holds for any
$\epsilon$ between zero and $0.09$. Our results establish that, although the
notions of Nash equilibria (and its computation-inspired approximations) are
universally applicable in all games, they are also fundamentally incomplete as
predictors of long term behavior, regardless of the choice of dynamics.
- Abstract（参考訳）: ゲームを繰り返しプレイするプレイヤーの振る舞いは,どのような条件下でナッシュ均衡に収束するのだろうか?
プレイヤーの行動が離散時間または連続時間規則であると仮定すると、現在の混合戦略プロファイルは次の状態にマッピングされるので、力学系の理論における問題となる。
我々は、この理論、特に連鎖再帰、アトラクタ、およびコンリー指数の概念を適用して、一般的な不可能性の結果を証明する:任意の力学がナッシュ平衡に達しない開始点を持つように束縛されたゲームが存在する。
また、$\epsilon$-approximate Nash equilibriaに対してより強い結果が証明される: ゲーム力学が(適切な意味で)$\epsilon$-Nash equilibriaに収束できないようなゲームがあり、実際にはそのようなゲームの集合は正の測度を持つ。
さらなる数値的な結果は、ゼロから0.09$の間の任意の$\epsilon$に対して成り立つことを示している。
我々の結果は、ナッシュ平衡の概念(および計算にインスパイアされた近似)は全てのゲームに普遍的に適用可能であるが、力学の選択にかかわらず、長期挙動の予測因子として根本的に不完全であることを示す。
関連論文リスト
- 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) - Smooth Nash Equilibria: Algorithms and Complexity [38.08108978808664]
ナッシュ均衡の概念の根本的な欠点は、その計算的推論性である。
$sigma$-smooth Nash均衡では、プレイヤーは$sigma$-smooth戦略への最良の偏差よりも少なくとも高いユーティリティを達成する必要がある。
弱いと強い$sigma$-smooth Nash平衡は、Nash平衡よりも優れた計算特性を持つことを示す。
論文 参考訳（メタデータ） (2023-09-21T16:22:07Z) - Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。
この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。
これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
論文 参考訳（メタデータ） (2023-01-22T16:54:06Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - 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 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) - Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。
我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。
我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
論文 参考訳（メタデータ） (2020-05-28T13:47:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。