algorithm - ナッシュ均衡をシミュレートする方法

Question

私は、各人が一連の M 個の個別の戦略を持っている N 人のゲームを持っています。少なくとも 1 つの混合戦略ナッシュ均衡が存在することを理論から知っています。

数値シミュレーションでこれらの平衡点の 1 つを見つける方法を教えてください。

シミュレートする方法の説明が本に見つかりません。基本的な方向性だけが必要です。

私は math.stackexchange でこの質問をしましたが、これがアルゴリズムの正しい場所である場合に備えて、ここでも質問することにしました。

ありがとうございました。

Answer 1

持っているゲームにもよりますが、不可能な場合もあれば (2xN ゼロサム ゲーム、潜在的なゲーム)、コストがかかる場合もあります。

ゲームに純粋なナッシュ均衡がある場合、ブラウンの架空のプレイ アルゴリズムはその後バーガーによって改良され、それを見つけることができます [GW ブラウン、架空のプレイによるゲームの反復ソリューション、MIT プレス、1998 年およびバーガー、ブラウンのオリジナルの架空のプレイ、ジャーナル オブ エコノミック理論、2007]。その確率論的バージョンが Smyrnakis & Leslie によって提案されました [Michail Smyrnakis et David Leslie, Stochastic Fictitious Play using Particle Filters to update thebelions of反対者の戦略、2008]。最初にウィキペディアのページを参照できます: http://en.wikipedia.org/wiki/Fictitious_play。

混合 NE を探している場合は、さらにトリッキーで、一部の学習アルゴリズムは非常に悪く、他のアルゴリズムは優れている場合があります。個人的には、Cesa-Bianchi と Lugosi の本、予測、学習、ゲー​​ム、 http: //homes.di.unimi.it/~cesabian/predbook/ が好きです。Nisan の Algorithmic Game Theory を好む人もいます。