「《進化と学習のゲーム理論》」の版間の差分
| (4人の利用者による、間の4版が非表示) | |||
| 1行目: | 1行目: | ||
'''【しんかとがくしゅうのげーむりろん (evolutionary game theory and learning in game theory) 】''' | '''【しんかとがくしゅうのげーむりろん (evolutionary game theory and learning in game theory) 】''' | ||
| − | + | 伝統的な[[ゲーム理論]]では, 他の[[プレイヤー]]の[[利得関数]]などゲームの構造を熟知した「合理的」なプレイヤー像を想定してきた. そして, [[非協力ゲーム理論]]における中心的な解である[[ナッシュ均衡]]は, このような合理的なプレイヤーの[[利得 (ゲームの)|利得]]最大化行動の結果達成されると考えられてきた. しかしながら, ゲーム理論の考察の対象は, 必ずしも合理的な意思決定主体に限られない. 実際, ゲームの構造を完全には知らず, ある一定の行動規則に従って行動する「[[限定合理性|限定合理的]]」なプレイヤーを想定し, 彼らの意思決定の過程を記述する様々な動学モデルが存在する. そして, これらの動学モデルの定常状態は ナッシュ均衡と密接な関連があることが明らかになってきている. 本項目では, この種の動学モデルのうち代表的なものとして, 1 [[自己複製子動学]] (replicator dynamics), 2 [[確率的進化 (ゲーム理論における)|確率的進化]] (stochastic evolution), 3 [[仮想プレイ]] (fictitious play) の3つ をとりあげて解説する. | |
| − | 1 自己複製子動学： | + | 1 自己複製子動学：<math>n\times n\, </math> 行列 <math>A\, </math> をプレイヤー1の利得行列とし, <math>A\, </math>の転置行列<math>A^{\top}\, </math>をプレイヤー2の利得行列とする2人ゲーム<math>G\, </math>(以下, 2人対称ゲームと呼ぶ)が, 非常に大きな母集団からその都度ランダムに選ばれた2人のプレイヤーによって, 繰り返しプレイされる状況を考える. 時点 <math>t\, </math> において, 母集団の中で[[純戦略]] <math>i\, </math> (<math>i=1, \dots, n\, </math>) をとるプレイヤーの比率を <math>x_i(t)\, </math>とする. <math>x(t)=(x_1(t), \dots, x_n(t))\, </math>の全体を<math>{\mathit\Delta}^n\, </math> とする. <math>{\mathit\Delta}^n=\{x(t)=(x_1(t), \dots, x_n(t)) | x_1(t)+\cdots+x_n(t)=1, x_1(t), \dots, x_n(t)\ge 0\}\, </math>である. このとき, <math>{\mathit\Delta}^n\, </math> 上の微分方程式系 |
| − | |||
| − | + | <center> | |
| + | <math>\frac{\dot x_i}{x_i}=(Ax)_i-x\cdot Ax\, </math> | ||
| + | </center> | ||
| − | |||
| − | + | を自己複製子動学という. ここで, "<math>\cdot\, </math>" は内積を, <math>(Ax)_i\, </math> は <math>Ax\, </math> の 第 <math>i\, </math> 成分をあらわす. これは, 純戦略 <math>i\, </math> を使うプレイヤーの成長率が, その戦略を使ったときの利得とすべての戦略の利得の平均値との差であるというモデルである. このモデルは, 数理生物学においてダーウィン的自然選択の自然なモデル化とみなされている. | |
| − | + | いま, もとの2人対称ゲームにおいて, [[混合戦略]]の組<math>(x, x), x\in{\mathit\Delta}^n\, </math>, がナッシュ均衡, 即ち, 任意の<math>y\in{\mathit\Delta}^n\, </math>に対して, <math>x\cdot Ax \ge y\cdot Ax\, </math> であり, さらに, <math>x\cdot Ax=y\cdot Ax\, </math> である任意の <math>y\in{\mathit\Delta}^n\, </math>に対して, <math>x\cdot Ay >y\cdot Ay\, </math> となるとき, 戦略<math>x\, </math>を[[進化的安定戦略]] (evolutionarily stable strategy) という. 進化的安定戦略であるための条件は, 十分小さな<math>\epsilon >0\, </math>に対して, <math>x\cdot Az>y\cdot Az\, </math>, ただし<math>z=(1-\epsilon)x+\epsilon y\, </math>, と書き変えることができ, 他の戦略yの進入に対して<math>x\, </math>が安定であることを表している. 進化的安定戦略<math>x\, </math>は自己複製子動学において漸近安定である, つまり, <math>x\, </math>においてどのような小さな摂動を受けたとしても, それが十分小さければまた<math>x\, </math> に戻る動きが導かれる, ことが示されている. 自己複製子動学とナッシュ均衡の関係 などより詳しくは, [3], [9] を参照. | |
| − | + | 2 確率的進化：前項と同様, <math>n\times n\, </math> 行列 <math>A\, </math>をプレイヤー1の利得行列とし, <math>A\, </math>の転置行列<math>A^{\top}\, </math>をプレイヤー2の利得行列とする2人対称ゲーム <math>G\, </math> を考え, このゲーム<math>G\, </math>が, <math>N\, </math>人 (<math>N>2\, </math>)の母集団からその都度ランダムに選ばれた2人のプレイヤーによって繰り返しプレイされるとする. | |
| − | + | まず, 動学過程の状態集合として <math>\textstyle S=\{s=(s_1, \dots, s_n)|\sum_is_i=N, s_i\, </math>\ は自然数<math>\}\, </math> をとる. <math>s_i\, </math> は純戦略 <math>i\, </math> (<math>i=1, \ldots, n\, </math>) をとるプレイヤーの人数である. 任意の <math>s\in S\, </math> および <math>i\, </math> (<math>i=1, \ldots, n\, </math>)について, <math>\textstyle x_i(s)=\frac{1}{N-1}(s_1, \dots, s_i-1, \dots, s_n)\in{\mathit\Delta}^n\, </math> とする. <math>x_i(s)\, </math> は, プレイヤー <math>i\, </math> から見た状態 <math>s\, </math> における他者の戦略分布である. <math>t\, </math> 期の状態が <math>s\in S\, </math> とき, 戦略 <math>i\, </math> をとるプレイヤーは <math>t+1\, </math> 期に, 確率 <math>1-\epsilon\, </math>で<math>x_{i}(s)\, </math>に対する[[最適反応 (ゲーム理論における)|最適反応]]戦略<math>s\, </math>を選択し, 確率 <math>\epsilon\, </math> である外生的に与えられた確率分布 <math>q=(q_1, \dots, q_n)\, </math>にしたがって戦略を選択するものとする. ここで, <math>\epsilon>0\, </math> かつ <math>q_1, \dots, q_n>0\, </math> である. これは, 戦略の選択にあたって確率 <math>\epsilon\, </math> で「ミス」または「突然変異」が起こることを表している. | |
| − | + | このモデルは状態の集合 <math>S\, </math> 上の唯1つの定常確率分布 <math>\mu_\epsilon\, </math>を持つ有限マルコフ連鎖を導く. いま, <math>\epsilon\to 0\, </math> としたときの極限分布<math>\textstyle \mu^*=\lim_{\epsilon\to 0}\mu_\epsilon\, </math> について, <math>\mu^*(s)>0\, </math> となる状態<math>s\, </math>を確率的安定状態という. 確率的安定状態に対応するゲーム <math>G\, </math>の戦略分布は, この動学過程を十分長期に観察した場合に, 最も頻繁に観察される戦略分布である. 確率的安定状態の集合は, <math>\epsilon=0\, </math>の場合のこの過程の再帰集合の1つとなる. <math>\epsilon=0\, </math>の場合の再帰集合は一般に複数個存在するので, 確率的安定性は複数の再帰集合から「もっとも起こりやすい」ものを1つ特定することとなる. 特に, <math>G\, </math>が[[狭義ナッシュ均衡]]を複数個持つ場合, 一般にこの中の唯1つが確率的安定状態に対応する. 従って, 確率的安定性により複数個の狭義ナッシュ均衡から1つを選び出すことができる. 確率的安定な状態に対応するナッシュ均衡を, [[確率的安定均衡 (ゲーム理論の)|確率的安定均衡]] (stochastically stable equilibrium)という. 確率的進化については, [2], [7], [8], [10] が詳しい. | |
| − | 任意の | + | 3 仮想プレイ：<math>n\, </math> 人[[戦略形ゲーム]] <math>G=(N=\{1, \ldots, n\}, S_1, \ldots, S_n, u_1, \ldots, u_n)\, </math> が <math>t=1, 2, \ldots\, </math>の各期 にプレイされる状況を考える. <math>t\, </math> 期に実現した戦略の組を <math>x^t=(x^t_1, \dots, x^t_n)\, </math> とすると, <math>t\, </math> 期までにとられた戦略の組の列 <math>h^t=(x^1, \dots, x^t)\, </math> によってプレイヤー <math>j\, </math> が戦略集合 <math>S_j\, </math> の各戦略を<math>t\, </math>期までにとった頻度の分布が定まる. これを<math>p_j^t\, </math>で表す. |
| + | |||
| + | <math>p_{-i}^t\, </math> を <math>i\, </math>以外のプレイヤー<math>j\, </math>に関する <math>p_j^t\, </math> の直積分布とする. 各プレイヤー <math>i\, </math> が, <math>t+1\, </math> 期において <math>p_{-i}^t\, </math> に対する最適反応戦略 <math>x^{t+1}_i\, </math> をプレイすることにより, <math>x^{t+1}=(x^{t+1}_1, \dots, x^{t+1}_n)\, </math> が定まる. <math>t=1\, </math> 期の戦略は初期状態として外生的に与えられるとする. 以上のように戦略が選択されていく動学過程を仮想プレイとよぶ. | ||
| + | |||
| + | 任意の <math>i\, </math> について <math>\textstyle p_{i}^*=\lim_{t\to\infty}p_{i}^t\, </math> が存在するとき, 仮想プレイは収束するという. 仮想プレイが収束するならば, <math>(p_{1}^*, \dots, p_{n}^*)\, </math> はゲーム <math>G\, </math> のナッシュ均衡である. 2人ゼロ和ゲームや2人のプレイヤーがそれぞれ2つの純戦略を持つ <math>2\times 2\, </math> ゲームにおいては, 仮想プレイは収束することが知られているが, 一般には仮想プレイは収束するとは限らない. 仮想プレイが収束しないゲームの例として, シャープレイ(L. S. Shapley)の <math>3\times 3\, </math> ゲームの例が有名である. 仮想プレイの詳細および一般化については, [1], [2], [6]が詳しい. | ||
なお, 他のプレイヤーの戦略などに対する予想を, ゲームの繰り返しを通じて逐次ベイズ的に更新していく合理的なプレイヤーを想定した学習モデルもある. [4] および [5] を参照されたい. | なお, 他のプレイヤーの戦略などに対する予想を, ゲームの繰り返しを通じて逐次ベイズ的に更新していく合理的なプレイヤーを想定した学習モデルもある. [4] および [5] を参照されたい. | ||
| 28行目: | 32行目: | ||
---- | ---- | ||
| − | |||
'''参考文献''' | '''参考文献''' | ||
| 50行目: | 53行目: | ||
[10] H. P. Young, ''Individual Strategy and Social Structure'', Princeton University Press, 1998. | [10] H. P. Young, ''Individual Strategy and Social Structure'', Princeton University Press, 1998. | ||
| + | |||
| + | [[category:ゲーム理論|しんかとがくしゅうのげーむりろん]] | ||
2007年8月7日 (火) 02:34時点における最新版
【しんかとがくしゅうのげーむりろん (evolutionary game theory and learning in game theory) 】
伝統的なゲーム理論では, 他のプレイヤーの利得関数などゲームの構造を熟知した「合理的」なプレイヤー像を想定してきた. そして, 非協力ゲーム理論における中心的な解であるナッシュ均衡は, このような合理的なプレイヤーの利得最大化行動の結果達成されると考えられてきた. しかしながら, ゲーム理論の考察の対象は, 必ずしも合理的な意思決定主体に限られない. 実際, ゲームの構造を完全には知らず, ある一定の行動規則に従って行動する「限定合理的」なプレイヤーを想定し, 彼らの意思決定の過程を記述する様々な動学モデルが存在する. そして, これらの動学モデルの定常状態は ナッシュ均衡と密接な関連があることが明らかになってきている. 本項目では, この種の動学モデルのうち代表的なものとして, 1 自己複製子動学 (replicator dynamics), 2 確率的進化 (stochastic evolution), 3 仮想プレイ (fictitious play) の3つ をとりあげて解説する.
1 自己複製子動学： 行列 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A\, } をプレイヤー1の利得行列とし, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A\, } の転置行列構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A^{\top}\, } をプレイヤー2の利得行列とする2人ゲーム(以下, 2人対称ゲームと呼ぶ)が, 非常に大きな母集団からその都度ランダムに選ばれた2人のプレイヤーによって, 繰り返しプレイされる状況を考える. 時点 において, 母集団の中で純戦略 (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i=1, \dots, n\, } ) をとるプレイヤーの比率を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_i(t)\, } とする. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x(t)=(x_1(t), \dots, x_n(t))\, } の全体を とする. である. このとき, 上の微分方程式系
構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{\dot x_i}{x_i}=(Ax)_i-x\cdot Ax\, }
を自己複製子動学という. ここで, "構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \cdot\, }
" は内積を, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (Ax)_i\, }
は の 第 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, }
成分をあらわす. これは, 純戦略 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, }
を使うプレイヤーの成長率が, その戦略を使ったときの利得とすべての戦略の利得の平均値との差であるというモデルである. このモデルは, 数理生物学においてダーウィン的自然選択の自然なモデル化とみなされている.
いま, もとの2人対称ゲームにおいて, 混合戦略の組構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x, x), x\in{\mathit\Delta}^n\, } , がナッシュ均衡, 即ち, 任意のに対して, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\cdot Ax \ge y\cdot Ax\, } であり, さらに, である任意の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y\in{\mathit\Delta}^n\, } に対して, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\cdot Ay >y\cdot Ay\, } となるとき, 戦略構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\, } を進化的安定戦略 (evolutionarily stable strategy) という. 進化的安定戦略であるための条件は, 十分小さな構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon >0\, } に対して, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\cdot Az>y\cdot Az\, } , ただし, と書き変えることができ, 他の戦略yの進入に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\, } が安定であることを表している. 進化的安定戦略は自己複製子動学において漸近安定である, つまり, においてどのような小さな摂動を受けたとしても, それが十分小さければまた構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\, } に戻る動きが導かれる, ことが示されている. 自己複製子動学とナッシュ均衡の関係 などより詳しくは, [3], [9] を参照.
2 確率的進化：前項と同様, 行列 をプレイヤー1の利得行列とし, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A\, } の転置行列構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A^{\top}\, } をプレイヤー2の利得行列とする2人対称ゲーム 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } を考え, このゲーム構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } が, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } 人 (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N>2\, } )の母集団からその都度ランダムに選ばれた2人のプレイヤーによって繰り返しプレイされるとする.
まず, 動学過程の状態集合として 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle S=\{s=(s_1, \dots, s_n)|\sum_is_i=N, s_i\, } \ は自然数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \}\, } をとる. は純戦略 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i=1, \ldots, n\, } ) をとるプレイヤーの人数である. 任意の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s\in S\, } および 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i=1, \ldots, n\, } )について, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle x_i(s)=\frac{1}{N-1}(s_1, \dots, s_i-1, \dots, s_n)\in{\mathit\Delta}^n\, } とする. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_i(s)\, } は, プレイヤー 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } から見た状態 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s\, } における他者の戦略分布である. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t\, } 期の状態が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s\in S\, } とき, 戦略 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } をとるプレイヤーは 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t+1\, } 期に, 確率 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1-\epsilon\, } で構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_{i}(s)\, } に対する最適反応戦略構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s\, } を選択し, 確率 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon\, } である外生的に与えられた確率分布 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle q=(q_1, \dots, q_n)\, } にしたがって戦略を選択するものとする. ここで, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon>0\, } かつ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle q_1, \dots, q_n>0\, } である. これは, 戦略の選択にあたって確率 で「ミス」または「突然変異」が起こることを表している.
このモデルは状態の集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S\, } 上の唯1つの定常確率分布 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mu_\epsilon\, } を持つ有限マルコフ連鎖を導く. いま, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon\to 0\, } としたときの極限分布構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \mu^*=\lim_{\epsilon\to 0}\mu_\epsilon\, } について, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mu^*(s)>0\, } となる状態構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s\, } を確率的安定状態という. 確率的安定状態に対応するゲーム 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } の戦略分布は, この動学過程を十分長期に観察した場合に, 最も頻繁に観察される戦略分布である. 確率的安定状態の集合は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon=0\, } の場合のこの過程の再帰集合の1つとなる. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon=0\, } の場合の再帰集合は一般に複数個存在するので, 確率的安定性は複数の再帰集合から「もっとも起こりやすい」ものを1つ特定することとなる. 特に, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } が狭義ナッシュ均衡を複数個持つ場合, 一般にこの中の唯1つが確率的安定状態に対応する. 従って, 確率的安定性により複数個の狭義ナッシュ均衡から1つを選び出すことができる. 確率的安定な状態に対応するナッシュ均衡を, 確率的安定均衡 (stochastically stable equilibrium)という. 確率的進化については, [2], [7], [8], [10] が詳しい.
3 仮想プレイ：構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 人戦略形ゲーム 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G=(N=\{1, \ldots, n\}, S_1, \ldots, S_n, u_1, \ldots, u_n)\, } が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t=1, 2, \ldots\, } の各期 にプレイされる状況を考える. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t\, } 期に実現した戦略の組を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x^t=(x^t_1, \dots, x^t_n)\, } とすると, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t\, } 期までにとられた戦略の組の列 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h^t=(x^1, \dots, x^t)\, } によってプレイヤー 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } が戦略集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S_j\, } の各戦略を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t\, } 期までにとった頻度の分布が定まる. これを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_j^t\, } で表す.
構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_{-i}^t\, } を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } 以外のプレイヤー構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } に関する 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_j^t\, } の直積分布とする. 各プレイヤー 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } が, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t+1\, } 期において 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_{-i}^t\, } に対する最適反応戦略 をプレイすることにより, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x^{t+1}=(x^{t+1}_1, \dots, x^{t+1}_n)\, } が定まる. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle t=1\, } 期の戦略は初期状態として外生的に与えられるとする. 以上のように戦略が選択されていく動学過程を仮想プレイとよぶ.
任意の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } について 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle p_{i}^*=\lim_{t\to\infty}p_{i}^t\, } が存在するとき, 仮想プレイは収束するという. 仮想プレイが収束するならば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (p_{1}^*, \dots, p_{n}^*)\, } はゲーム 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\, } のナッシュ均衡である. 2人ゼロ和ゲームや2人のプレイヤーがそれぞれ2つの純戦略を持つ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 2\times 2\, } ゲームにおいては, 仮想プレイは収束することが知られているが, 一般には仮想プレイは収束するとは限らない. 仮想プレイが収束しないゲームの例として, シャープレイ(L. S. Shapley)の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 3\times 3\, } ゲームの例が有名である. 仮想プレイの詳細および一般化については, [1], [2], [6]が詳しい.
なお, 他のプレイヤーの戦略などに対する予想を, ゲームの繰り返しを通じて逐次ベイズ的に更新していく合理的なプレイヤーを想定した学習モデルもある. [4] および [5] を参照されたい.
参考文献
[1] D. Fudenberg and D. Kreps, "Learning Mixed Equilibria," Games and Economic Behavior, 5 (1993), 320-367.
[2] D. Fudenberg and D. Levine, The Theory of Learning in Games, MIT Press, 1998.
[3] J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, 1988. 竹内康博, 「生物の進化と微分方程式」, 現代数学社, 1990.
[4] J. S. Jordan, "Bayesian Learning in Normal Form Games," Games and Economic Behavior, 3 (1991), 60-81.
[5] E. Kalai and E. Lehrer, "Rational Learning Leads to Nash Equilibria," Econometrica, 61 (1993), 1019-1046.
[6] P. Milgrom and J. Roberts, "Adaptive and Sophisticated Learning in Normal Form Games," Games and Economic Behavior, 3 (1991), 82-100.
[7] L. Samuelson, Evolutionary Games and Equilibrium Selection, MIT Press, 1997.
[8] F. Vega-Redondo, Evolution, Games, and Economic Behavior, Oxford University Press, 1996.
[9] J. Weibull, Evolutionary Game Theory, MIT Press, 1995. 大和瀬達二監訳, 「進化ゲームの理論」, 文化書房博文社, 1998.
[10] H. P. Young, Individual Strategy and Social Structure, Princeton University Press, 1998.