177

数理解析研究所講究録
第 741 巻 1991 年 177-196

Learning Algorithms for$2\cross 2$

Stochastic Games

with Incomplete Information1

鳥取大学工学部

小柳 淳二 (Junji Koyanagi)

京都大学・工学部

大西

京都大学工学部

茨木 俊秀 (Toshihide Ibaraki)

匡光 (Masamitsu Ohnishi)

序論

学習は様々な分野で研究され, いろいろなモデルや学習アルゴリズムが提案されている, 例えば,
コンピュータ科学では最近ニューラルネットワークによる学習の研究が行われ, パターン認識な

どを複雑なプログラムなしで行うことの実用化を目指している.
ゲーム理論の分野においては, 従来学習に関連した研究はあまりなかったようであるが, 最近になって,

ESS (Evolutionary Stable Strategy) の学習や 2 人零和ゲームにおける学習を扱ったものがいくつかなされてきている. ESS とは対称な非零和ゲームにおける Nash 均衡の概念を強めたものであり, その特徴として,ESS をとる個体からなるグループの中では, 他の戦略をとる少数の個体は ESS をとる個体より低い期待利得しか受け取り得ないという性質があげられる. よって

ESS を学習することはグループ内の小数の突然変異体に対する一種の抵抗力を身にっける上で重要である. Harley [1] では過去の履歴に重みづけをし, それに基づいて混合戦略を更新する学習ア
ルゴリズムを考え, シミュレーションを用いて, その学習アルゴリズムの有効性を検証している.

一方 2 入零和確率的ゲームへの学習アルゴリズムの適用を考察したものには LakshmivaIahan andNaiendra [4], [5] がある. [5] では各プレイヤーが 2 個のアクションを持っ 2 人零和確率的ゲームを考え, あるブクションが成功したときにはそのアクションをとる確率を増やし, 失敗したときに178は減らすという Linear Reward-Penalty アルゴリズム (以下では $L_{R-P}$ アルゴリズムと略す) を両者が用いた場合, 両者の混合戦略の極限が 2 人零和ゲームの均衡戦略に任意に近づけられることが示されている. [4] では各プレイヤーが複数のアクションを持ち, 純粋戦略で均衡解を持っ 2 人

零和確率的ゲームを考え, あるアクションが成功したときにはそのアクションをとる確率を増やす
が, 失敗したときには変化させないという Linear Reward-Inaction アルゴリズムを両者が用いた

場合, 両者の混合戦略の極限が均衡戦略になる確率が任意に 1 に近づけられることが示されている.

Lakshmivarahan [3] では, これらの学習アルゴリズムが成功確率が未知の機械の中から最大の成功確率を持っものを選ぶことを目的とする Multi-Armed Bandit 問題にも適用可能であることが示され, さらに他の分野への応用がまとめられている. これら学習アルゴリズムの漸近的性質を導く
上で Norman [7] にある小さなステップで動 \langle Markov 過程における状態の極限分布の性質が重要な役割を演じている. Norman [6] には学習アルゴリズムの数学的側面が詳しく述べられている.
本稿で扱う繰り返し 2 人非零和確率的ゲームは, それぞれのプレイヤーが各ステージごとに 2個のアクションのうちの一方を選び, それらの選ばれたアクションに依存したある確率でそれぞれのプレイヤーが利得 1 または$0$を得るゲームである. ただし, 各プレイヤーはその確率法則にっいて何の知識もなく, さらにプレイヤーは互いに相手を観察することができない, すなわち自分のとったアクションと利得しか情報として得られないものとする. このような状況で一方のプレイ

ヤーがある固定した混合戦略を用いるなら他方のプレイヤーは例えば $L_{R-P}$ アルゴリズムを用いて自分に有利な戦略を学ぶことが可能になり, その結果, 固定した混合戦略を用いている方は不利益をうけることがある. ただし, ある固定した戦略が Nash 解ならば不利益を受けることはない.

Nash 解を求めるには利得を受ける確率法則を知ることが必要であるが, 本稿ではその確率法則が未知の場合にも両方のプレイヤーが LR-P アルゴリズムを適用し, かっそのゲームの Nash 解が

1 個の場合には双方のプレイヤーの戦略は漸近的に Nash 解に収束することを示す.
本稿の構成は次のとうりである. 次章でゲームと LR-P アルゴリズムについて述べ, 3 章ではLR-P アルゴリズムの漸近的性質に関する解析を行う. 4 章では最適反応戦略により 4 つの場合2

$1_{-}79$にゲームを分類し, そのうち唯一の Nash 解をもっ 3 っの場合においては LR-P アルゴリズムにより両者の混合戦略の組は漸近的に Nash 解に収束することを示す. 最後の章では得られた結果についてのまとめと今後の課題について述べる.

2

モデル

21

2

$\cross$2-確率的ゲームと Nash 均衡解

本稿で扱う繰り返し 2 人非零和確率的ゲームは次のようなものである. 2 人のプレイヤー PA, PBがそれぞれ 2 個のアクション 1 と 2 をもち, それぞれのプレイヤーが各ステージごとに 2 個のアクションのうちどちらか一方を選ぶ. PA のアクション$i$に対し, 確率 $R_{ij}(k, l)$ で PA は利得 , PB は利得

$k,$

$k$

クション 1 をとる確率をそれぞれ $p,$

$q$

$l$

(

と PB のアクション $j(i,$$l$は 1 または$0$$j$(は 1 または 2)) を受け取る. PA, PB がアとすると両者の混合戦略はそれぞれ $(p, 1-p)$ と $(q, 1-q)$となる. 混合戦略の組を $(p, q)$ で表すと, それに対して PA の期待利得 $E_{A}(p, q)$ と PB の期待利

得 $E_{B}(p, q)$ は次のようになる.

$E_{A}(p, q)$$=$$pq(R_{11}(1,1)+R_{11}(1,0))$$+p(1-q)(R_{12}(1,1)+R_{12}(1,0))$$+(1-p)q(R_{21}(1,1)+R_{21}(1,0))$$+(1-p)(1-q)(R_{22}(1,1)+R_{22}(1,0))$ ,$E_{B}(p, q)$$=$$pq(R_{11}(1,1)+R_{11}(0,1))$$+p(1-q)(R_{12}(1,1)+R_{12}(0,1))$$+(1-p)q(R_{21}(1,1)+R_{21}(0,1))$$+(1-p)(1-q)(R_{22}(1,1)+R_{22}(0,1))$ .

$E_{A}(p, q),$ $E_{B}(p, q)$を用いて 2 人非零和ゲームにおいて重要な概念である Nash 解を定義する.

3

180
定義 21 戦略の組 $(p^{*}, q^{*})$ が Nash 解であるとは$E_{A}(p, q^{*})\leq E_{A}(p^{*}, q^{*})$

for all$p\neq p^{*}$

for all$q\neq q^{*}$,

かっ$E_{B}(p^{*}, q)\leq E_{B}(p^{*}, q^{*})$

が成り立っときである. 口$a_{ij}=R_{ij}(1,1)+R_{ij}(1,0)$ ,とおけば,$a_{ij}$$([a_{ij}], [b_{ij}] )$$(b_{ij})$$b_{ij}=R_{ij}(1,1)+R_{ij}(0, 1)$

は PA, PB がアクション $i,$$j$を選んだとき PA (PB) が 1 を得る確率であり,を期待利得行列とする双行列ゲームはもとのゲームと同じ Nash 解を持つ.

$a_{ij},$$b\ovalbox{\tt\small REJECT}$の値をプレイヤーが知っていれば Nash 解を知ることができるが, ここでは双方のプレイヤーは$a_{ij},$.

$b_{i_{J}}$について何の知識もなく, さらにお互いに相手を観察することができないものとする.

このゲームは繰り返しプレイされるが, もし一方のプレイヤーがすべてのステージで Nash 解以外の固定した混合戦略をとり, 他方のプレイヤーは以下に述べる LR-P アルゴリズムを用いれば自分に有利な戦略を学ぶことができる.
そこで本稿では双方が $L_{R-P}$ アルゴリズムを用いるとどのようになるかを考察する. 以下では煩雑な場合分けを防ぐため $a_{ij}(b_{ij})$ は相互に全て異なり, かっすべて正で 1 より小さいものとする.

22$L_{R-P}$

アルゴリズム双方のプレイヤーは利得を受ける確率 $R_{\tau j}(k, l)(i, j=1,2, k, l=0,1)$ について何の知識もなく,相手のアクションも利得も観測することができないので, 過去において自分のとったアクションと利得をもとにしてゲームを学習することが必要となる.
以下ではプレイヤーが両方とも LR-P アルゴリズムを適用して混合戦略を更新していく場合を考える. $P_{n}(n=1,2, \cdots)$ を第
なわち PA の第

$n$

$n$

ステージにおいて PA がアクション 1 をとる確率とする. すステージにおける混合戦略は $(P_{n}, 1-P_{n})$ となる. $L_{R-P}$ のもとでは疏は PA

181

がそのステージにおいてとったアクションと得た利得により次のように $P_{n+1}$ に更新される.

$P_{n+1}=\{P_{n}^{n}+\theta^{\alpha_{A}}(1-\cdot P^{n})P_{n}^{n}-\theta\beta_{A}^{A}P_{n}^{n}P-\theta_{\alpha}PP+\theta\beta_{A}(1-P_{n})$ア ク シ ョ ン を と り 利 得 を 得 た と き .’,$2211$PB の漉合戦略に対応する
かえたものを用いる.
と呼ばれる. またる.

$\theta$$Q_{n}$$\beta_{A}(\beta_{B})$(2.1)$0011$の更新も同様である, ただし式 (2.1) における添え字の A をと$\alpha_{A}(\alpha_{B})$$B$にはそれぞれ reward パラメーター, penalty パラメーター

は両方のプレイヤーの学習のステップサイズを変化させるパラメーターであなお $P_{n+1}$ が区間 $[0,1]$ 内にあることを保証するため$\theta,$$\alpha_{A},$$\alpha_{B},$$\beta_{A},$$\beta_{B}$はすべて区間 $(0$ ,1) 内にあるものとする.
両者の戦略の組の時間変化を表す確率過程 $\{(P_{n}, Q_{n});n\geq 1\}$ は単位正方形 $[0,1]\cross[0,1]$ 上の時間斉次な Markov 過程であり, その推移確率は学習に関するパラメーター$\beta_{A}$,$\alpha_{A},$$\beta_{B},$$\theta$$\alpha_{B},$と利得を得る確率 $R_{\tau j}(k, l)(i, j=1,2, k, l=0,1)$ により決定される.
本稿の目的は Markov 過程 $\{(P_{n}, Q_{n});n\geq 1\}$ の $narrow\infty$ における漸近的な挙動が学習パラ

メーターやゲームの構造によりどう変化するかを明らかにすることである.

3

混合戦略の漸近的性質

さて両方のプレイヤーが $L_{R-P}$ アルゴリズムを\alpha A$\{(P_{n}, Q_{n});n\geq 1\}$の $narrow\infty$$<\beta_{A},$$\alpha_{B}<\beta_{B}$の条件のもとで用いた場合の,における漸近的性質にっいて調べる. 上の条件は, 成功を失敗より高く評価することを意味する.

$(\Delta P_{n}, \Delta Q_{n})=(P_{n+1}-P_{n}, Q_{n+1}-Q_{n})$とする. これは両者の混合戦略の組 $(P_{n}, Q_{n})$ の 1 ステージあたりの増分を表わす確率変数であ
る.

$s$

182
という条件の下での$(P_{n}, Q_{n})=(p, q)$

害 ったものを $w(p, q)$ とする. $w(p, q)$ は第$|J$$(\Delta P_{n}, \Delta Q_{n})$$n$の条件付き期待値を考え, それを$\theta$でステージに両者の混合戦略の組が $(p, q)$ であると

きの $(P_{n}, Q_{n})$ の増分の期待方向を示す :$w(p, q)$$=$$(w_{A}(p, q),$$=$$\frac{1}{\theta}E[(\Delta P_{n}, \Delta Q_{n})|(P_{n}, Q_{n})=(p, q)]$$w_{B}(p, q))$

.

(3.2)

この第一成分は$w_{A}(p, q)= \frac{1}{\theta}E[\triangle P_{n}|(P_{n}, Q_{n})=(p, q)]$であり, 起こり得るすべての事象の組み合わせを考えれば$E[\Delta P_{n}|(P_{n}, Q_{n})=(p, q)]$$=$$\theta\beta_{A}a_{11}(1-p)pq-\theta\alpha_{A}(1-a_{11})p^{2}q$$+\theta\beta_{A}a_{12}(1-p)p(1-q)-\theta\alpha_{A}(1-a_{12})p^{2}(1-q)$$-\theta\beta_{A}a_{21}p(1-p)q+\theta\alpha_{A}(1-a_{21})(1-p)^{2}q$$-\theta\beta_{A}a_{22}p(1-p)(1-q)+\theta\alpha_{A}(1-a_{22})(1-p)^{2}(1-q)$となる.
$w_{B}(p, q)$は上式右辺において$a_{ij}$を$b_{ji}$

に,

$p$

を

$q$

に, そして A を $B$ に置き換えることにより得られる.
$w_{A}(p, q),$$w_{B}(p, q)$$w_{A}(p, q)$$=$は次のように整理される.

$\beta_{A}p(1-p)\{(1-q)(a_{12}-a_{22})+(a_{11}-a_{21})q\}$$+\alpha_{A}[(1-p)^{2}\{1-a_{22}+(a_{22}-a_{21})q\}$$-p^{2}\{1-a_{12}+(a_{12}-a_{11})q\}]$$w_{B}(p, q)$

$=$

,

(3.3)

$\beta_{B}q(1-q)\{(1-p)(b_{21}-b_{22})+(b_{11}-b_{12})p\}$$+\alpha_{B}[(1-q)^{2}\{1-b_{22}+(b_{22}-b_{12})p\}$$-q^{2}\{1-b_{21}+(b_{21}-b_{11})p\}]$

6

.

(3.4)

183
$w(p, q)$ の $(p, q)$に関するヤコビアンを$J(p, q)=(\begin{array}{ll}\frac{\partial w_{A}(p,q)}{\partial p} \frac{\partial w_{A}(p,q)}{\partial q}\frac{\partial w_{B}(p,q)}{\partial p} \frac{\partial w_{B}(p,q)}{\partial q}\end{array})$で表すと, 簡単な計算により各成分は以下のようになる.

$\frac{\partial w_{A}(p,q)}{\partial p}$$=$$\beta_{A}(1-2p)\{(1-q)(a_{I2}-a_{22})+(a_{11}-a_{21})q\}$$+\alpha_{A}[-2(1-p)\{1-a_{22}+(a_{22}-a_{21})q\}$$-2p\{1-a_{12}+(a_{12}-a_{11})q\}]$ ,$\frac{\partial w_{A}(p,q)}{\partial q}$$=$$\beta_{AP}(1-p)(a_{11}-a_{21}+a_{22}-a_{12})$$+\alpha_{A}\{(1-p)^{2}(a_{22}-a_{21})-p^{2}(a_{12}-a_{11})\}$$\frac{\partial w_{B}(p,q)}{\partial p}$$=$$\beta_{Bq}(1-q)(b_{11}-b_{21}+b_{22}-b_{12})$$+\alpha_{B}\{(1-q)^{2}(b_{22}-b_{12})-q^{2}(b_{21}-b_{11})\}$$\frac{\partial w_{B}(p,q)}{\partial q}$

$=$

,

,

$\beta_{B}(1-2q)\{(1-p)(b_{21}-b_{22})+(b_{11}-b_{12})p\}$$+\alpha_{B}[-2(1-q)\{1-b_{22}+(b_{22}-b_{12})p\}$$-2q\{1-b_{21}+(b_{21}-b_{11})p\}]$.

さらに $(P_{n}, Q_{n})=(p, q)$ が与えられたという条件のもとでの $(\Delta P_{n}, \Delta Q_{n})$ の条件付き共分

散行列を$C(p, q)=E[[(\Delta P_{n}, \Delta Q_{n})-\theta w(p, q)]^{T}[(\Delta P_{n}, \Delta Q_{n})-\theta w(p, q)]|(P_{n}, Q_{n})=(p, q)]$とする. ここで$T$は転置を表す.

以上で定義された $w(p, q),$ $J(p, q),$ $C(p, q)$ はもちろん $L_{R-P}$ アルゴリズムのパラメーター$\beta_{A},$$\alpha_{A},$$\beta_{B},$$\alpha_{B}$に依存するが, それらを陽には表記しないことにする.

7

184
さて小さなステップで動 \langle Markov 過程の極限分布の漸近的性質に関する Norman の定理 ([7]参照) により次の定理を得る.

定理 3.1 もし $w(p, q)=(0,0)$ の解 ($p_{s}$$l,$。

$q_{sd}$) が唯一で, そこでのヤコビアン$J$($p_{s}$$l,$。

$q_{sd}$) が負定値ならば,( $P_{n}-p_{s}$

。

$l$

。

)

$l\sqrt{\theta}^{Q_{n}-q_{s}}$

の分布は
だし

$\theta\downarrow 0$$\Sigma(\infty)$

かっ $n\thetaarrow\infty$ のとき, 平均 $(0,0)$ 共分散行列の正規分布に弱収束する. た$\Sigma(\infty)$は次の行列方程式の解として得られる :.

$J(p_{sol}, q_{sd})\Sigma(\infty)+\Sigma(\infty)J(p_{sol}, q_{sd})^{T}+C(p_{sol}, q_{sd})=0$(3.5)$\square$

式 (3.5) は Ljapunov 方程式と呼ばれ, 唯一の正定値解をもつことが知られている.

$w(p, q)=(0,0)$ の解を吟味するには $w_{A}(p, q)=0$ となる $(p, q)$ のグラフと $w_{B}(p, q)=0$ となる $(p, q)$ グラフを同じ単位正方形 $[0,1]x[0,1]$ 上に描きそれらの交点をもっか調べればよい.

以下では $w_{A}(p, q)=0$ となる $(p, q)$ のグラフのみにっいて調べる. いま$c_{A}(q)=1-a_{22}+(a_{22}-a_{21})q$ ,$d_{A}(q)=1-a_{12}+(a_{12}-a_{11})q$.

と定義する.
$(1-q)(a_{12}-a_{22})+q(a_{11}-a_{21})=c_{A}(q)-d_{A}(q)$であるので, 式 (3.3) は次のように書き換えることができる :$w_{A}(p, q)=\beta_{A}p(1-p)(c_{A}(q)-d_{A}(q))+\alpha_{A}\{c_{A}(q)(1-p)^{2}-d_{A}(q)p^{2}\}$

以下簡単のため$\gamma_{A}=\frac{\alpha_{A}}{\beta_{A}}$

,
8

.

(3.6)

185

$e_{A}(q)= \frac{d_{A}(q)}{c_{A}(q)}$とする.

補題 $.1 任意の $q\in[0,1]$ に対し $w_{A}(p, q)=0$ は区間 $[0,1]$ 内に次のような唯一解をもち, そ
の解は

$q$

に関して連続である :$p_{A}(q)=\{1/2\ovalbox{\tt\small REJECT} 2\gamma_{A}-(1-e_{A}(q))-\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)}2(1-e_{A}(q))(\gamma_{A}-1)$$c_{A}^{A}(q)=d_{A}^{A}(q)c(q)\neq d(q)$のときのとき

’

(3.7)

$.$

証明 式 (3.6) において $c_{A}(q)=d_{A}(q)$ のとき式 (3.6) は$\alpha_{A}c_{A}(q)\{(1-p)^{2}-p^{2}\}=0$となり, $p=1/2$ が解であることは容易にわかる.
$c_{A}(q)\neq d_{A}(q)$の時には $p=0$ の時と $p=1$ の時の $w_{A}(p, q)$ の値を調べると,$w_{A}(0, q)$$=$$\alpha_{A}c_{A}(q)$$w_{A}(1, q)$$=$$-\alpha_{A}d_{A}(q)$であり, すべての $q\in[0,1]$ にたいし $c_{A}(q),$ $d_{A}(q)\succ 0$ であることから区間 $[0,1]$ 内の $w_{A}(p, q)=$$0$の解は唯一であることがわかる.
$w_{A}(p, q)$は$p$に関して 2 次式であり, $c_{A}(q)>d_{A}(q)$ の時上に凸な関数で, $c_{A}(q)<d_{A}(q)$ の時上に凹な関数である. よって 2 次方程式 $w_{A}(p, q)=0$ の 2 個の解$p_{A}(q)= \frac{2\gamma_{A}-(1-e_{A}(q))\pm\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)}}{2(1-e_{A}(q))(\gamma_{A}-1)}$(3.8)のうち区間 $[0,1]$ 内にある解は $c_{A}(q)>d_{A}(q)$ の時大きい方で, $c_{A}(q)<d_{A}(q)$ の時小さい方である.
$c_{A}(q)>d_{A}(q)$のとき $e_{A}(q)<1$ であり, $\gamma_{A}<1$ であるから式 (3.8) の右辺の分母は負になる.

分子は正号 $+$ をとると正になり, 負号 $-$ をとると負になる. よって大きい方の解は負号 $-$ をとることにより得られる.

9

186
一方 $c_{A}(q)<d_{A}(q)$ のときは $e_{A}(q)>1$ , また $\gamma_{A}<1$ であるから式 (3.8) の右辺の分母は正になる. 分子は常に正であり, 小さい方の解は負号 $-$ をとることにより得られる.

以上のことから任意の $q\in[0,1]$ に対し区間 $[0,1]$ 内にある $w_{A}(p, q)=0$ の解は式 (3.7) で与えられる.
$p_{A}(q)$の$q$に関する連続性は $c_{A}(q)=d_{A}(q)$ のときに問題となる. よって $e_{A}(q)arrow 1$ のとき式(3.7) の右辺の上式が 1/2 に収束することを以下で示す.
$\lim_{e_{A}(q)arrow 1}\frac{2\gamma_{A}-(1-e_{A}(q))-\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)}}{2(1-e_{A}(q))(\gamma_{A}-1)}$$\lim_{xarrow 1}\frac{2\gamma_{A}-(1-x)-(1-x)^{2}\mapsto+4\gamma_{A}^{2}x}{2(1-x)(\gamma_{A}-1),\backslash }$$=$$\lim_{xarrow 1}\frac{1-\frac{-2(1-x)+4\gamma_{A}^{2}}{2\sqrt{(1-x)^{2}+4\gamma_{A}^{2}x}}}{-2(\gamma_{A}-1)}=1/2$$=$

ただし第 1 の等号は $e_{A}(q)$ を$x$と置くことにより, 第 2 の等号は l’Hospital の定理を用いることにより得られる. よって $p_{A}(q)$ は(1) $p_{A}(q)$ は補題 3.2(2) $p_{A}(q)$ は$\gamma_{A}$

$q$

,

$q$

に関して連続である.

$\square$に関し単調増加あるいは単調減少である.

に関し $c_{A}(q)<d_{A}(q)$ のとき単調増加であり 2 $c_{A}(q)>d_{A}(q)$ のとき単調減少である.

証明 (1)$p_{A}(q)$を$q$に関して微分すると,$\frac{(e_{A}’(q)-\frac{-2e_{A}’(q)(1-e_{A}(q))+4\gamma_{A}^{2}e_{A}’(q)}{2f_{A}(q)})(1-e_{A}(q))+e_{A}^{l}(q)(2\gamma_{A}-1+e_{A}(q)-f_{A}(q))}{2(\gamma_{A}-1)(1-e_{A}(q))^{2}}$$p_{A}^{/}(q)$

$=$

$=$

$g(q)[(1+ \frac{(1-e_{A}(q))-2\gamma_{A}^{2}}{f_{A}(q)}I(1-e_{A}(q))+2\gamma_{A}-1+e_{A}(q)-f_{A}(q))]$$=$$g(q)[ \frac{(1-e_{A}(q))^{2}-2\gamma_{A}^{2}(1-e_{A}(q))}{\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}e_{A}(q)}}+2\gamma_{A}-\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}e_{A}(q)}]$$=$$g(q)[2 \gamma_{A}+\frac{(1-e_{A}(q))^{2}-2\gamma_{A}^{2}(1-e_{A}(q))-(1-e_{A}(q))^{2}-4\gamma_{A}^{2}e_{A}(q)}{\sqrt{(1-e_{A}(q))^{\Delta}+4\gamma_{A}e_{A}(q)}}]$$=$$g(q)[2 \gamma_{A}+\frac{-2\gamma_{A}^{2}-2\gamma_{A}^{2}e_{A}(q)}{\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}e_{A}(q)}}]$

10

187

$=$

ここで’ は$\frac{\gamma_{A}e_{A}’(q)}{(1-e_{A}(q))^{2}(\gamma_{A}-1)}[1-\frac{\gamma_{A}(1+e_{A}(q))}{\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)}}]$

$q$

,

(3.9)

に関する微分を表し,$f_{A}(q)=\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}e_{A}(q)}$,$g(q)= \frac{e_{A}’(q)}{2(\gamma_{A}-1)(1-e_{A}(q))^{2}}$とおいた.

式 (3.9) の右辺の$[\cdot]$

内の式は常に正であることが以下で示される.

$>$

$=$

$0$

.

以上のことから $p_{A}’(q)$ と $e_{A}’(q)$ とは逆の符号をもっことがわかる. また $e_{A}(q)$ は$q$に関する線形

分数関数なので, $e_{A}’(q)$ はすべての $q\in[0,1]$ にたいし一定の符号をもっ. よって $p_{A}(q)$ は

$q$

に関

して単調である.

(2)$p_{A}(q)$をパラメーター$\frac{\partial p_{A}(q)}{\partial\gamma_{A}}$$=$$\gamma_{A}$に関して偏微分すれば,$\frac{(2-\frac{8\gamma A^{e_{A}(q)}}{2f_{A}(q)})(\gamma_{A}-1)-(2\gamma_{A}-1+e_{A}(q)-f_{A}(q))}{2(1-e_{A}(q))(\gamma_{A}-1)^{2}}$$=$$h(q)[2( \gamma_{A}-1)-\frac{4\gamma_{A}e_{A}(q)(\gamma_{A}-1)}{f_{A}(q)}-2\gamma_{A}+1-e_{A}(q)+f_{A}(q)]$$=$$h(q)[-1-e_{A}(q)+ \frac{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)-4\gamma_{A}e_{A}(q)(\gamma_{A}-1)}{\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)}}]$$=$$h(q)[-1-e_{A}(q)+ \frac{4\gamma_{A}e_{A}(q)+(1-e_{A}(q))^{2}}{\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)}}]$

ただし$h(q)= \frac{1}{2(e_{A}(q)-1)(\gamma_{A}-1)^{2}}$11(3.10)

188

とおいた.

式 (3.10) の右辺の$[\cdot]$

内の式は負であることを以下の不等式を証明することにより示す.

(3.11)$1+e_{A}(q)> \frac{(1-e_{A}(q))^{2}+4\gamma_{A}e_{A}(q)}{\sqrt{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)}}$式 (3.11) の両辺を 2 乗した後整理すれば$(1+e_{A}(q))^{2}\{(1-e_{A}(q))^{2}+4\gamma_{A}^{2}e_{A}(q)\}>\{(1-e_{A}(q))^{2}+4\gamma_{A}e_{A}(q)\}^{2}$(3.12)

を得る. 式 (3.12) の左辺から右辺を引けば$(1+e_{A}(q))^{2}(1-e_{A}(q))^{2}+(1+e_{A}(q))^{2}4\gamma_{A}^{2}e_{A}(q)-(1-e_{A}(q))^{4}$$-8\gamma_{A}e_{A}(q)(1-e_{A}(q))^{2}-16\gamma_{A}^{2}e_{A}(q)^{2}$$=$$(1-e_{A}(q))^{2}(1+e_{A}(q))^{2}-(1-e_{A}(q))^{4}-8\gamma_{A}e_{A}(q)(1-e_{A}(q))^{2}$$+(1+e_{A}(q))^{2}4\gamma_{A}^{2}e_{A}(q)-16\gamma_{A}^{2}e_{A}(q)^{2}$$=$$(1-e_{A}(q))^{2}\{(1+e_{A}(q))^{2}-(1-e_{A}(q))^{2}-8\gamma_{A}e_{A}(q)\}$$+4e_{A}(q)\gamma_{A}^{2}\{(1+e_{A}(q))^{2}-4e_{A}(q)\}$$=$$(1-e_{A}(q))^{2}\{4e_{A}(q))-8\gamma_{A}e_{A}(q)\}+4\gamma_{A}^{2}e_{A}(q)(1-e_{A}(q))^{2}$$=$$4e_{A}(q)(1-e_{A}(q))^{2}(\gamma_{A}^{2}-2\gamma_{A}+1)$$=$$4(1-e_{A}(q))^{2}e_{A}(q)(\gamma_{A}-1)^{2}$

$>$

$0$

.

よって式 (3.10) は $c_{A}(q)<d_{A}(q)(e_{A}(q)>1)$ のとき単調増加であり, $c_{A}(q)>d_{A}(q)(e_{A}(q)<1)$のとき単調減少である.

補題 3.$(1) $c_{A}(q)>d_{A}(q)$ のとき,

(2) $c_{A}(q)<d_{A}(q)$ のとき,$\gamma_{A}\downarrow 0$$\gamma_{A}\downarrow 0$とすれば $p_{A}(q)$ は下から単調に 1 に収束する.

とすれば $p_{A}(q)$ は上から単調に(3) $c_{A}(q)=d_{A}(q)$ のとき, $p_{A}(q)=1/2$ .

12

$0$

に収束する.

189
証明$\gamma_{A}\downarrow 0$とすると式 (3.7) より $e_{A}(q)<1$ か $>1$ によって $p_{A}(q)$ が 1 またはことがわかる. 単調性は補題 3.2 (2) からあきらかである.

$q$

が

$0$

$0$

に収束する

$\square$から 1 まで動くとき $c_{A}(q)-d_{A}(q)$ の符号は(3.13)$q^{*}= \frac{a_{22}-a_{12}}{a_{22}-a_{21}-a_{12}+a_{11}}$が区間 $[0,1]$ 内にあればそこで変わることになるが, これは $a_{11}-a_{21}$ の符号と $a_{12}-a_{22}$ の符号が異なるときである.
$w_{B}(p, q)$についても添え字 A を $B,$$p$を $q,$$a_{ij}$を$b_{ji}$に置き換えれば同様の補題が得られる.

44 っの場合
通常双行列ゲーム $([a_{ij}], [b_{j}] )$ は

$a_{1j}$と$b_{1j}$の大小の順によって分類されるが, ここで重要なのは $a_{12}-a_{22},$ $a_{11}-a_{21}(b_{21}-b_{22}, b_{11}-b_{12})$ の符号である. 符号の組合せには 4 通りあり, それらはそのゲームの PA の最適反応戦略と以下に示すような関係がある

Al: $a_{12}-a_{22}<0,$ $a_{11}-a_{21}<0$ のとき, PA の最適反応戦略は PB のアクションにかかわらずアクション 2 をとることである.

A2: $a_{12}-a_{22}<0,$ $a_{11}-a_{21}>0$ のとき, PA の最適反応戦略は PB のアクションと同じアクションをとることである.

$A3;a_{12}-a_{22}>0,$ $a_{11}-a_{21}<0$ のとき, PA の最適反応戦略は PB のアクションと逆のアクショ

ンをとることである.

$A4:a_{12}-a_{22}>0,$ $a_{11}-a_{21}>0$ のとき, PAの最適反応戦略は PB のアクションにかかわらずアクション 1 をとることである.

PB に対しても A を

$B$

にかえ,

$a_{1j}$を$b_{ji}$にかえれば同様の場合わけができる. 全部で $4\cross 4=16$の場合があるように思われるが, アクションやプレイヤーの名前のっけかえにより 4 っの場合を調

13

190
べれば十分であることがわかる. 以下ではそれら 4 っの場合について調べる.

$C$

ase 1.

$a_{11}-a_{21}<0,$ $b_{21}-b_{22}<0,$ $b_{11}-b_{12}<0$$a_{12}-a_{22}<0,$.

この場合 Nash 解は $(0,0)$ すなわち双方のプレイヤーがアクション 2 をとることである. また$C_{A(q)}<d_{A}(q),$$(p_{sol}, q_{sd})$は$C_{B(p)}<d_{B}(p)$$\gamma_{A}\downarrow 0$,のとき $(0,0)$ に収束することがわかる (図 1 参照).

$\gamma_{B}\downarrow 0$

次にヤコビアン $I$ ($p_{sd},$が任意の $(p, q)$ について成り立っので補題 3.3 (2) を用いれば$q_{s}$。
$\iota$) は$J(0,0)=(\begin{array}{lll}\beta_{A}(a_{12}-a_{22})-2\alpha_{A}(1- a_{22}) \alpha_{A}(a_{22}-a_{21})b_{12}\alpha_{B}(b_{22}-) \beta_{B}(b_{21}-b_{22})-2\alpha_{B}(1-b_{12})\end{array})$で近似される. これは負定値であるから $J(p_{sol}, q_{sd})$ も$\gamma_{A},$$\gamma_{B}$を十分小さくとることにより負定値にすることができる.

Case 2.

$a_{11}-a_{21}<0,$ $b_{21}-b_{22}<0,$ $b_{11}-b_{12}>0$$a_{12}-a_{22}<0,$.

この場合も Nash 解は $(0,0)$ すなわち双方のプレイヤーがアクション 2 をとることである.

しかし Case 1 では双方のプレイヤーは相手のアクションにかかわらずアクション 2 をとるのが最適反応戦略であったが, この場合は PB は PA がどちらのアクションをとるかにより自分のアクショ

ンを変える必要がある.

$c_{A}(q)<d_{A}(q)$であるから, 補題 3.3 (2) より $p_{A}(q)$ はに収束する. 一方 $p<p^{*}$ に対しては $c_{B}(p)<d_{B}(p),$ら $q_{B}(p)$ は$\gamma_{B}\downarrow 0$とすれば$p>p^{*}$$\gamma_{A}\downarrow 0$

とすれば

$0$

対しては $C_{B(p)}>d_{B}(p)$ であるか

( $p<p^{*}$ のとき) または 1( $p>p^{*}$ のとき) に収束することが補題$0$

3.3 (1) および (2) からわかる. $p=p^{*}$ のときには補題 3.3 (3) より $q_{B}(p)=1/2$ である. 以上より($p_{s}$$l,$。

$q_{sd}$) は$\gamma_{A}\downarrow 0,$$\gamma_{B}\downarrow 0$のとき $(0,0)$ に収束することがわかる (図 2 参照).

ヤコビアンは Case 1 と同様であるので省略する.

Case 3.

$a_{12}-a_{22}<0,$$a_{11}-a_{21}>0,$ $b_{21}-b_{22}>0,$ $b_{11}-b_{12}<0$.

Cases 1 と 2 では Nash 解は純粋戦略の組であったがこの場合は混合戦略の組$(p^{*}, q^{*})=( \frac{b_{22}-b_{21}}{b_{22}-b_{21}-b_{12}+b_{11}}\frac{a_{22}-a_{12}}{a_{22}-a_{21}-a_{12}+a_{11}}I$14.

(4.14)

191
が Nash 解である.

Case 2 と同様の議論を $p_{A}(q)$ ,$q_{A}(p)$に適用すれば$\gamma_{A}\downarrow 0$

かつ$\gamma_{B}\downarrow 0$のとき $(p_{S\text{。}}\iota, q_{sol})arrow(p^{*}, q^{*})$ がわかる (図 3 参照).
ヤコビアン

$J(p_{sol}, q_{sol})$は$+\alpha_{A}^{22}[(1-p^{*})^{2}(a_{a_{11}^{*})]}(a-a_{22^{*}}-a_{21_{22}}+_{*}-p^{A}(a_{12}+(b-b_{12}^{-})p^{22})^{a_{1})}-2\alpha_{B}(1-\beta_{*2}p_{12}(1-p_{b})_{-a^{1_{21}})}\ovalbox{\tt\small REJECT}\cdot$$J(p^{*}, q^{*})=\ovalbox{\tt\small REJECT}+\alpha_{B}^{22^{+(a_{b^{22_{*}}-b^{21}+_{-b^{1_{12}})}^{*}}}}[(1-q^{*})(b_{b^{a_{11}}}^{q)_{)^{b_{1})}}}(b--q^{B}(b_{21}^{-a_{-}^{-})_{*}q)_{]}}-2\alpha_{A}(1_{2}\beta_{*2}q_{21}(1-12_{22^{22_{\backslash }}}$

で近似される. $tr(J(p^{*}, q^{*}))$ と $[tr(J(p^{*}, q^{*}))]^{2}-4[\det(J(p^{*}, q^{*}))]$ は共に負であるので, この行列は負定値であることがわかる.

Case 4.

$a_{12}-a_{22}<0,$$a_{11}-a_{21}>0,$ $b_{21}-b_{22}<0,$ $b_{11}-b_{12}>0$.

この場合 Nash 解は 3 つ $(0,0),$ $(1,1),$ $(p^{*}, q^{*})$ あり, それに応じて $p_{A}(q),$ $q_{B}(p)$ の交点も 3 つある. 各交点は$\gamma_{A}\downarrow 0$

かつ$\gamma_{B}\downarrow 0$のときそれぞれ 3 つの Nash 解に収束し (図 4 参照), $(0,0),$ $(1$ ,1) の近傍にある交点ではヤコビアンは負定値であることが容易にわかる. 直感的には混合戦略の組はこのどちらかの Nash 解に収束しそうだがはっきりしたことは現在のところ不明である.

5

結論

本稿では不完全情報を持つ繰り返し 2$x$2-確率的ゲームを扱い, もしゲームが唯一の Nash 解を持ち, 両方のプレイヤーが $L_{R-P}$ アルゴリズムを適切なパラメーターのもとで用いれば, 両者の混合

15

192

戦略の組は漸近的に Nash 解に収束することを示した. .
しかし 2$\cross$2-確率的ゲームの中で Nash 解を 3 っ持っものにっいては, LR-P アルゴリズムの漸近的性質について十分な考察を加えることができなかった. 今後の課題としたい.

References[1] Harley, C. B., Learning the evolutionarily stable strategy, J. Theoretical Biology, 89 (1981),

pp. 611-633.
[2] Hines W. G. S. and Bishop D. T., On learning and the evolutionarily stable strategy,$J$.

Applied Probability, 20 (1983), pp. 689-695.

[3] Lakshmivarahan, S., Learning Algorithms Theory and Applications, Springer-Verlag, New
York, 1981.
[4] Lakshmivarahan, S. and Narendra, K. S., Learning algorithms for two-person zero-somestochastic games with incomplete information, Mathematics of Operations Research, 6(1981), pp. 379-386.

[5] Lakshmivarahan, S. and Narendr a, K. S. , Learning algorithms for two-person zero-somestochastic games with incomplete information: a unified approach, SIAM J. Control andoptimization, 20 (1982), pp. 541-552.
[6] Norman, M. F., Markov Processes and Learning Models, Academic Press, New York, 1972.

[7] Norman, M. F., A central limit theorem for Markov processes that move by small steps,

Annals of Probability, 6 (1974), pp. 1065-1074.
[8] Norman, M. F., Markovian learning processes, SIAM Review, 16 (1974), pp. 143-162.

16

193
Appendix
増分の規模を示すパラメーター $\theta\in(0,1)$ に対し,空間に持つ時間斉次なマルコフ過程とする. このとき$\{X_{n}^{\theta}; n\geq 0\}$を$\mathcal{R}^{M}$の部分集合

として以下を仮定する.

Al: $E[\Delta X_{n}^{\theta}|X_{n}^{\theta}=x]=\theta w(x)+O(\theta^{2})$ ,A2: $E[(\Delta X_{n}^{\theta}-\theta w(x))^{T}(\Delta X_{n}^{\theta}-\theta w(x))|X_{n}^{\theta}=x]=\theta^{2}C(x)+o(\theta^{2})$,
A$: $E[|\Delta X_{n}^{\theta}|^{3}|X_{n}^{\theta}=x]=O(\theta^{3})$ , ここで$|\cdot|l$

ま $I$ で定義されたノルムであり,Al, A2, A3 に現れるオーダーは $x\in I$ で一様とする.
$A4:I$ はコンパクト,$A5:w(x)$ は bounded Lipschitz derivative をもち,

A6: $C(x)$ は$I$

で Lipschitz,$A7:w(x)=0$ となる解 $x_{sd}\in I$ が唯一,

A8: $w(x)$ のヤコビアン $I(x)$ が$x_{s}$

$l$

。

で負定値.

ここで

,

$\mu_{n}^{\theta}(x)$$=$$E[X_{n}^{\theta}|X_{0}^{\theta}=x]$$\omega_{n}^{\theta}(x)$$=$$E[(X_{n}^{\theta}-\mu_{n}^{\theta}(x))^{T}(X_{n}^{\theta}-\mu_{n}^{\theta}(x))|X_{0}^{\theta}=x]$.

と置く.
仮定 Al から A8 が満たされていると, 以下のことが成り立っ.
定理 5.1(Norman の定理)

17

を状態

かっ $n\thetaarrow\infty$ の時の漸近的な性質に$\theta\downarrow 0$

っいて次のことが解っている.
$\Delta X_{n}^{\theta}=X_{n+1}^{\theta}-X_{n}^{\theta}$

$I$

194

(a)

$x\in I$と$n\geq 0$

に関し一様に$\omega_{n}^{\theta}(x)=O(\theta)$.

(b) 任意の $x\in I$ に対し, 次の (ベクトル) 微分方程式$\frac{d}{dt}f(t)=w[f(t)]$の解は唯一であり,, $f(0)=x$$\mu_{n}^{\theta}(x)=f(n\theta)+O(\theta)$

が $x\in I$ とに関して一様に成り立っ.

$n\geq 0$(c) 次の (行列) 微分方程式$\frac{d}{dt}\Sigma(t)=J[f(t)]\Sigma(t)+\Sigma(t)J[f(t)]^{T}+C[f(t)]$

は唯一の解

(d)

$\Sigma(t)$$(X_{n}^{\theta}-f(n\theta))/v\theta$

,

を持つ.

の分布は

$n\thetaarrow t\leq\infty$$\theta\downarrow 0,$, の時, 平均布に弱収束する. 特に $narrow\infty$ のときには $f(n\theta)arrow x_{s}$ことにより得られる.

$J$($x_{s}$$l$。

)$\Sigma(0)=0$$\Sigma(\infty)+\Sigma(\infty)J(x_{s}$$\iota)^{T}+C(x_{sd})=0$

。

18

. 口

$l$

。

$0$

, 共分散行列$\Sigma(t)$の正規分

で\Sigma (\infty ) は次の行列方程式を解く

195

$p$

196