こんにちわ。ゲーム理論使ってポケモンやりたいと思ってふわふわ知識を振り回しつつあるぴらんです。

今回はポケモンについて考えるためにこういう近似あったら便利なのになーと思った解法があるので、ちょっと真面目な近似法のお話です。数学強い人マサカリ歓迎。既に有名だよとかの指摘もお願いです。(連絡先:twitter@pyran19)

始めに

利得行列$${A_0}$$のゲームの解が既知でありナッシュ均衡やその時の評価値がよくわかっている時に利得行列が少しだけ変わったらそれらの解がどう変化するか知りたい状況が応用上よくあります。

例えばじゃんけんで勝った時の利得を少しだけ修正して「グーであいこだったら普通に勝った時の1/10の点が片方のプレイヤーにもらえる」みたいなハンデを付けるとしたらこのハンデによってどれだけ有利になるか・最適な手の出し方はどうなるか？といったように元のゲームを少しだけ修正したい時の近似法を考えたいです。このような問題の解は元のゲームの解の性質を強く残していることが予想され、元の問題の解を元にした解法を考えられると省力化して解くことが期待でき、また結果を解釈する上でも便利になります。

問題設定

行列$${A_0}$$のナッシュ均衡の戦略が既知であり、それぞれのプレイヤーの戦略が$${x_0,y_0}$$で表されるとします。この時$${\epsilon}$$を小さい数として$${\epsilon A_1}$$が加わった$${A}$$の解を調べます。

$$
A=A_0+\epsilon A_1
$$

$${A}$$の解を$${x,y}$$と書くとします。$${\epsilon}$$が小さいのでテイラー展開を行い、$${\epsilon}$$の高次の項を無視することができると考えます。 $${x=x_0+x_1\epsilon +O(\epsilon^2)}$$,$${y=y_0+y_1\epsilon +O(\epsilon^2)}$$

ゲームの評価値は$${v=x^T A y}$$で計算できます。ここに上の関係式を代入して$${\epsilon}$$の高次を無視することで近似計算を行います。

$$
v=(x_0+x_1\epsilon+O(\epsilon^2))^T (A_0+\epsilon A_1)(y_0+y_1+O(\epsilon^2))\\
=x_0^TA_0y_0 +\epsilon x_0^TA_1y_0 +\epsilon(x_1^TA_0y_0+x_0^TA_0y_1)+O(\epsilon^2)\\
=x_0^TA_0y_0 +\epsilon x_0^TA_1y_0+O(\epsilon^2)
$$

つまり非摂動解$${x_0^TA_0y_0}$$に$${\epsilon x_0^TA_1y_0 }$$が加わる形になります。

また、戦略に関しても$${\epsilon}$$の一次までで求めます。評価値$${x^TAy}$$が$${x}$$に関してmax、yに関してminになっていることから$${x}$$の微小量$${\delta x}$$の変化に対して増分が０になることが期待されます。

$$
(x+\delta x )^TAy - x^T A y = 0\\
\delta x^T Ay  = 0\\
$$

確率の合計値が１になるという条件から$${\delta x}$$は(1,1,1)方向には動けませんが、それ以外の方向の任意の微小変化$${\delta x}$$に対して上の式が成り立つためには以下の式が成り立つ必要があります。

$$
Ay=\begin{pmatrix}
1\\
1\\
1\end{pmatrix}\lambda\\
(A0+\epsilon A_1)(y_0+\epsilon y_1+O(\epsilon^2))=\begin{pmatrix}
1\\
1\\
1\end{pmatrix}\lambda
$$

$${\epsilon}$$が小さい仮定から一次の項までを取り出します。

$$
\epsilon A_1y0+\epsilon A_0y_1
=\begin{pmatrix}1\\1\\1\end{pmatrix}\lambda
$$

$${y_0}$$が既知で知りたいのは$${y_1}$$であるため$${y_1=\dots}$$の形を目指して変形していきます。

$$
A_0 y_1=-A_1y_0+\begin{pmatrix}1\\1\\1\end{pmatrix}\lambda\\
y_1=-A_0^{-1}A_1y_0+\lambda A_0^{-1}\begin{pmatrix}1\\1\\1\end{pmatrix}
$$

対称なゲームでは$${A_0}$$は交代行列になり(1,1,1)ベクトルの固有値が０になるため逆行列を持ちません。しかし$$A_0$$が逆行列を持たない場合は疑似逆行列というものを用いれば良いようです。この場合(1,1,1)ベクトルの項は$${A_0^{-1}}$$の作用で消えて$${y_1=-A_0^{-1}A_1y_0}$$とすっきりした形に書けます。

まとめ

$${A_0}$$が既知のゲームであり、最適な戦略が$${x_0,y_0}$$で表される時、そこから微小に変化したゲーム$${A=A_0+\epsilon A_1}$$の解は以下のように近似できます。

• 評価関数$${v=x_0^T \epsilon A_1 y_0}$$

• 戦略$${y-y_0=\epsilon y_1=\epsilon A_0^{-1}A_1y_0\\x-x_0=\epsilon x_1=\epsilon x_0A_1A_0^{-1}}$$

すなわち、元のゲームの解や利得行列の逆行列がよくわかっている場合は$${A_1}$$を作用させるだけで手軽に近似が可能です。

どれくらい楽になるか次節で具体的な問題に応用して試してみます。

具体例

冒頭に書いたじゃんけんの例を考えます。利得行列は↓のようになります。列や行はグーチョキパーの順で利得を表しています。

$$
A=
\begin{pmatrix}
0.1 & 1 & -1 \\
-1 & 0 & 1\\
1& -1 & 0
\end{pmatrix}
$$

通常のじゃんけんの利得は下記の$${A_0}$$に対してあいこならプレイヤー１が1/10勝を得られるというハンデにより次の$${A_1}$$の分の修正を受けたことを表しています。

$$
A_0=
\begin{pmatrix}
0 & 1 & -1 \\
-1 & 0 & 1\\
1& -1 & 0
\end{pmatrix}\\
A_1=
\begin{pmatrix}
0.1 & 0 & 0 \\
0 & 0 & 0\\
0& 0 & 0
\end{pmatrix}\\
A=A_0+A_1
$$

$${A_0}$$はじゃんけんなので全ての手を1/3ずつで出すのが最適な戦略です。また逆行列はもたず疑似逆行列は次のようになります。

$$
A_0^{-1}=\frac13 
\begin{pmatrix}
0 & -1 & 1 \\
1 & 0 & -1\\
-1& 1 & 0
\end{pmatrix}
$$

したがって今回調べた近似式により今回のハンデで勝率がどれだけ増えるか調べると次のようになります

$$
勝率の増分＝(\frac13,\frac13,\frac13)A_1
\begin{pmatrix}\frac13\\\frac13\\\frac13\end{pmatrix}\\
=\frac19\times 0.1=0.01111
$$

また最適な戦略について調べると次のようになります。

$$
x-x_0=-x_0 A_1 A_0^{-1}\\
=-\begin{pmatrix}\frac13& \frac13& \frac13\end{pmatrix}\begin{pmatrix}0.1&0&0\\0&0&0\\0&0&0\end{pmatrix}\frac13\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix}\\
=\begin{pmatrix}0\\ \frac19\\ -\frac19\end{pmatrix}
$$

つまりチョキの割合を少し増やし、その分パーを出す比率を少し下げるのが最適な戦略ということがわかります。グーであいこになると有利になるゲームに関わらずグーの割合を増やさないのが正解なのは面白い点だと思います。

これらの結果は近似をせずに正しく解いた結果と高精度で一致します。このように元のゲーム$${A_0}$$について詳しくわかっていれば簡単な行列計算をするのみで近似解を求めることが可能になる強力な武器になります。

終わりに

いかがでしたか？ちょっと今回はゲームのお話は抜きで純粋に数学的な関係にのみ焦点を絞って記事を書いてみました。（その割に証明が雑とか言わない！！）

応用分野においてこのような「少しだけ元から変化した」的な状況はよく発生するためこのような方法を知っておくと楽に解けたり、結果を説明する時に役立ったりします。読んでくれた方頭の片隅にでも入れておいてもらってどこかで役立つことがあればうれしいです。

では次回＾－＾ノシノシ