《進化と学習のゲーム理論》

【しんかとがくしゅうのげーむりろん (evolutionary game theory and learning in game theory) 】

　伝統的なゲーム理論では, 他のプレイヤーの利得関数などゲームの構造を熟知した「合理的」なプレイヤー像を想定してきた. そして, 非協力ゲーム理論における中心的な解であるナッシュ均衡は, このような合理的なプレイヤーの利得最大化行動の結果達成されると考えられてきた. しかしながら, ゲーム理論の考察の対象は, 必ずしも合理的な意思決定主体に限られない. 実際, ゲームの構造を完全には知らず, ある一定の行動規則に従って行動する「限定合理的」なプレイヤーを想定し, 彼らの意思決定の過程を記述する様々な動学モデルが存在する. そして, これらの動学モデルの定常状態は ナッシュ均衡と密接な関連があることが明らかになってきている. 本項目では, この種の動学モデルのうち代表的なものとして, 1　自己複製子動学 (replicator dynamics), 2　確率的進化 (stochastic evolution), 3　仮想プレイ (fictitious play) の3つ をとりあげて解説する.

1　自己複製子動学：$n\times n\,$ 行列 $A\,$ をプレイヤー1の利得行列とし, $A\,$の転置行列$A^{\top }\,$をプレイヤー2の利得行列とする2人ゲーム$G\,$(以下, 2人対称ゲームと呼ぶ)が, 非常に大きな母集団からその都度ランダムに選ばれた2人のプレイヤーによって, 繰り返しプレイされる状況を考える. 時点 $t\,$ において, 母集団の中で純戦略 $i\,$ ($i=1,\dots ,n\,$) をとるプレイヤーの比率を $x_{i}(t)\,$とする. $x(t)=(x_{1}(t),\dots ,x_{n}(t))\,$の全体を${\mathit {\Delta }}^{n}\,$ とする. ${\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)\geq 0\}\,$である. このとき, ${\mathit {\Delta }}^{n}\,$ 上の微分方程式系

${\frac {{\dot {x}}_{i}}{x_{i}}}=(Ax)_{i}-x\cdot Ax\,$

を自己複製子動学という. ここで, "$\cdot \,$" は内積を, $(Ax)_{i}\,$ は $Ax\,$ の 第 $i\,$ 成分をあらわす. これは, 純戦略 $i\,$ を使うプレイヤーの成長率が, その戦略を使ったときの利得とすべての戦略の利得の平均値との差であるというモデルである. このモデルは, 数理生物学においてダーウィン的自然選択の自然なモデル化とみなされている.

　いま, もとの2人対称ゲームにおいて, 混合戦略の組$(x,x),x\in {\mathit {\Delta }}^{n}\,$, がナッシュ均衡, 即ち, 任意の$y\in {\mathit {\Delta }}^{n}\,$に対して, $x\cdot Ax\geq y\cdot Ax\,$ であり, さらに, $x\cdot Ax=y\cdot Ax\,$ である任意の $y\in {\mathit {\Delta }}^{n}\,$に対して, $x\cdot Ay>y\cdot Ay\,$ となるとき, 戦略$x\,$を進化的安定戦略 (evolutionarily stable strategy) という. 進化的安定戦略であるための条件は, 十分小さな$\epsilon >0\,$に対して, $x\cdot Az>y\cdot Az\,$, ただし$z=(1-\epsilon )x+\epsilon y\,$, と書き変えることができ, 他の戦略yの進入に対して$x\,$が安定であることを表している. 進化的安定戦略$x\,$は自己複製子動学において漸近安定である, つまり, $x\,$においてどのような小さな摂動を受けたとしても, それが十分小さければまた$x\,$ に戻る動きが導かれる, ことが示されている. 自己複製子動学とナッシュ均衡の関係 などより詳しくは, [3], [9] を参照.

2　確率的進化：前項と同様, $n\times n\,$ 行列 $A\,$をプレイヤー1の利得行列とし, $A\,$の転置行列$A^{\top }\,$をプレイヤー2の利得行列とする2人対称ゲーム $G\,$ を考え, このゲーム$G\,$が, $N\,$人 ($N>2\,$)の母集団からその都度ランダムに選ばれた2人のプレイヤーによって繰り返しプレイされるとする.

　まず, 動学過程の状態集合として $\textstyle S=\{s=(s_{1},\dots ,s_{n})|\sum _{i}s_{i}=N,s_{i}\,$\ は自然数$\}\,$ をとる. $s_{i}\,$ は純戦略 $i\,$ ($i=1,\ldots ,n\,$) をとるプレイヤーの人数である. 任意の $s\in S\,$ および $i\,$ ($i=1,\ldots ,n\,$)について, $\textstyle x_{i}(s)={\frac {1}{N-1}}(s_{1},\dots ,s_{i}-1,\dots ,s_{n})\in {\mathit {\Delta }}^{n}\,$ とする. $x_{i}(s)\,$ は, プレイヤー $i\,$ から見た状態 $s\,$ における他者の戦略分布である. $t\,$ 期の状態が $s\in S\,$ とき, 戦略 $i\,$ をとるプレイヤーは $t+1\,$ 期に, 確率 $1-\epsilon \,$で$x_{i}(s)\,$に対する最適反応戦略$s\,$を選択し, 確率 $\epsilon \,$ である外生的に与えられた確率分布 $q=(q_{1},\dots ,q_{n})\,$にしたがって戦略を選択するものとする. ここで, $\epsilon >0\,$ かつ $q_{1},\dots ,q_{n}>0\,$ である. これは, 戦略の選択にあたって確率 $\epsilon \,$ で「ミス」または「突然変異」が起こることを表している.

　このモデルは状態の集合 $S\,$ 上の唯1つの定常確率分布 $\mu _{\epsilon }\,$を持つ有限マルコフ連鎖を導く. いま, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon\to 0\, } としたときの極限分布$\textstyle \mu ^{*}=\lim _{\epsilon \to 0}\mu _{\epsilon }\,$ について, $\mu ^{*}(s)>0\,$ となる状態$s\,$を確率的安定状態という. 確率的安定状態に対応するゲーム $G\,$の戦略分布は, この動学過程を十分長期に観察した場合に, 最も頻繁に観察される戦略分布である. 確率的安定状態の集合は, $\epsilon =0\,$の場合のこの過程の再帰集合の1つとなる. $\epsilon =0\,$の場合の再帰集合は一般に複数個存在するので, 確率的安定性は複数の再帰集合から「もっとも起こりやすい」ものを1つ特定することとなる. 特に, $G\,$が狭義ナッシュ均衡を複数個持つ場合, 一般にこの中の唯1つが確率的安定状態に対応する. 従って, 確率的安定性により複数個の狭義ナッシュ均衡から1つを選び出すことができる. 確率的安定な状態に対応するナッシュ均衡を, 確率的安定均衡 (stochastically stable equilibrium)という. 確率的進化については, [2], [7], [8], [10] が詳しい.

3　仮想プレイ：$n\,$ 人戦略形ゲーム $G=(N=\{1,\ldots ,n\},S_{1},\ldots ,S_{n},u_{1},\ldots ,u_{n})\,$ が $t=1,2,\ldots \,$の各期 にプレイされる状況を考える. $t\,$ 期に実現した戦略の組を $x^{t}=(x_{1}^{t},\dots ,x_{n}^{t})\,$ とすると, $t\,$ 期までにとられた戦略の組の列 $h^{t}=(x^{1},\dots ,x^{t})\,$ によってプレイヤー $j\,$ が戦略集合 $S_{j}\,$ の各戦略を$t\,$期までにとった頻度の分布が定まる. これを$p_{j}^{t}\,$で表す.

　$p_{-i}^{t}\,$ を $i\,$以外のプレイヤー$j\,$に関する $p_{j}^{t}\,$ の直積分布とする. 各プレイヤー $i\,$ が, $t+1\,$ 期において $p_{-i}^{t}\,$ に対する最適反応戦略 $x_{i}^{t+1}\,$ をプレイすることにより, $x^{t+1}=(x_{1}^{t+1},\dots ,x_{n}^{t+1})\,$ が定まる. $t=1\,$ 期の戦略は初期状態として外生的に与えられるとする. 以上のように戦略が選択されていく動学過程を仮想プレイとよぶ.

　任意の $i\,$ について $\textstyle p_{i}^{*}=\lim _{t\to \infty }p_{i}^{t}\,$ が存在するとき, 仮想プレイは収束するという. 仮想プレイが収束するならば, $(p_{1}^{*},\dots ,p_{n}^{*})\,$ はゲーム $G\,$ のナッシュ均衡である. 2人ゼロ和ゲームや2人のプレイヤーがそれぞれ2つの純戦略を持つ $2\times 2\,$ ゲームにおいては, 仮想プレイは収束することが知られているが, 一般には仮想プレイは収束するとは限らない. 仮想プレイが収束しないゲームの例として, シャープレイ(L. S. Shapley)の $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.