繰り返しゲームにおけるZero-determinant戦略

Zero-determinant strategies in repeated games

間宮 安曇
静岡大学 大学院総合科学技術研究科 工学専攻 数理システム工学コース

本稿の内容は,A. Mamiya and G. Ichinose, Zero-determinant strategies under observation errors in repeated games, 2020(Under Review)で示したZero-determinant(ZD)戦略の導出方法について解説していきます.上の論文では,割引因子(Discount factor)と観測エラー(Observation error)を仮定し,いろいろ解析していますが,本題とはあまり関係ないので,ここでは観測エラーは考えないこととします.観測エラーを仮定する場合でも,遷移行列$M$が変わるだけなので,すぐに適用可能です.この論文で,私が最も重要だと考えている結果は,今回説明するように,割引因子を仮定した繰り返しゲームにおいても,利得の期待値を行列式という数式で記述できたいうことです.このことによって,割引因子付繰り返しゲームでも,PressとDysonらが示したZD戦略の導出ができるようになりました.また,その後の研究でPressらの行列式を使って,研究されてきたものがいくつかあります.最近の私たちの研究では,観測エラーを仮定した場合(割引因子なし)で,その行列式を使って,解析を行ってきました(https://doi.org/10.1016/j.jtbi.2019.06.009).今回の割引因子付繰り返しゲームにおける私たちの発見で,この解析をさらに観測エラー&割引因子付繰り返しゲームにも適用することができました.したがって,今回解説する内容は,ZD戦略の研究をより発展させることができると考えています.

繰り返し囚人のジレンマゲーム

2人プレイヤーi$\in\{X,Y\}$の繰り返し囚人のジレンマゲームを考える.ゲームのそれぞれのラウンドで,プレイヤーは,協力(C)か裏切り(D)の行動を選ぶ.プレイヤーの利得は,自分と相手の行動によって決まる.利得行列は
C D
C R S
D T P
で与えられる.繰り返し囚人のジレンマゲームを考えているので,$T>R>P>S$と$2R>T+S$を仮定する.このゲームを無限期にわたって繰り返す. プレイヤーの戦略は,Memory-one戦略であると仮定する.この戦略は,前回の自分と相手の行動から今回の行動を確率的に決定する.したがって,プレイヤー$X$の戦略は, \begin{equation} \bm p =(p_{\rm CC},p_{\rm CD},p_{\rm DC},p_{\rm DD};p_0) \end{equation} と定義する($0\le p_i\le 1, \in \{ 0,{\rm CC},{\rm CD},{\rm DC},{\rm DD} \}$).$p_{\rm CC}$は前回のラウンドで$X$と$Y$が協力したとき,今回,$X$が協力する確率である.$p_{\rm CD}$は前回のラウンドで$X$が協力で,$Y$が裏切りのとき,今回,$X$が協力する確率である.$p_{\rm DC}$は前回のラウンドで$X$が裏切り,$Y$が協力したとき,今回,$X$が協力する確率である.$p_{\rm DD}$は前回のラウンドで$X$と$Y$が裏切りであったとき,今回,$X$が協力する確率である.$p_0$は初期ラウンドで協力する確率である.同様に,プレイヤー$Y$の戦略は, \begin{equation} \bm q =(q_{\rm CC},q_{\rm CD},q_{\rm DC},q_{\rm DD};q_0) \end{equation} と定義する.

Zero-determinant戦略の導出

繰り返しゲームの初期ラウンドを$t=0$とする.また,プレイヤーの戦略はMemory-one戦略を使っているので,$t\ (t \ge 0)$期目の2人プレイヤーのゲームの状態は, \begin{equation}\label{def:v} \bm v(t)=(v_{\rm CC}(t),v_{\rm CC}(t),v_{\rm CC}(t),v_{\rm CC}(t)) \end{equation} で与えられる.$v_{\rm CC}(t)$は,$t$期目で,$X$と$Y$が両方ともCであった確率,$v_{\rm CD}(t)$は,$X$がC,$Y$がDであった確率,$v_{\rm DC}(t)$は,$X$がD,$Y$がCであった確率,$v_{\rm DD}(t)$は,$X$がD,$Y$がDであった確率である.また,初期状態は式\eqref{def:v}より \begin{equation} \bm v(0)=(p_0 q_0,p_0 (1-q_0),(1-p_0)q_0,(1-p_0)(1-q_0)) \end{equation} で与えられる.プレイヤー$X$の利得行列を$\bm S_X=(R,S,T,P)$とする(プレイヤー$X$の利得行列を$\bm S_Y=(R,T,S,P)$とする)と,$t$期目での利得は,$\bm v(t)\bm S_X^T$で計算できる.したがって,プレイヤー$X$の割引平均利得は, \begin{equation}\label{per-round-payoff_X} s_X=(1-\delta)\sum^{\infty} _{t=0} \delta^t \bm v(t) \bm S_X^T \end{equation} となる($0< \delta < 1$).また,ゲームの状態遷移行列は, \begin{equation} \label{eq:M} M = \left( \begin{array}{cccc} p_{\rm CC} q_{\rm CC} & p_{\rm CC}(1-q_{\rm CC}) & (1-p_{\rm CC})q_{\rm CC} &(1-p_{\rm CC})(1-q_{\rm CC})\\ p_{\rm CD} q_{\rm DC} & p_{\rm CD}(1-q_{\rm DC}) & (1-p_{\rm CD})q_{\rm DC} &(1-p_{\rm CD})(1-q_{\rm DC})\\ p_{\rm DC} q_{\rm CD} & p_{\rm DC}(1-q_{\rm CD}) & (1-p_{\rm DC})q_{\rm DC} &(1-p_{\rm DC})(1-q_{\rm CD})\\ p_{\rm DD} q_{\rm DD} & p_{\rm DD}(1-q_{\rm DD}) & (1-p_{\rm DD})q_{\rm DD} &(1-p_{\rm DD})(1-q_{\rm DD}) \end{array} \right) \end{equation} である.遷移行列$M$のそれぞれの行と列は,前回のゲームの状態と次の状態を表している.よって,$t$期目でのゲームの状態は,遷移行列$M$を使うと, \begin{equation} \bm v(t)=\bm v(0) M^t \end{equation} と表せる.これを式\eqref{per-round-payoff_X}に代入すると, \begin{equation} \begin{split} s_X&=(1-\delta)\bm v(0)\sum^{\infty} _{t=0} (\delta M)^t \bm S_X^T \\ &=(1-\delta)\bm v(0)(I-\delta M)^{-1}\bm S_X^T \end{split} \end{equation} が得られる.ここで, \begin{eqnarray}\label{eq:u} \bm v^T \equiv (v_1,v_2,v_3,v_4) =(1-\delta)\bm v(0)(I-\delta M)^{-1} \end{eqnarray} とおく.これは,平均分布と呼ばれる.また,以下のように行列を定義する. \begin{equation} \bm M_0 \equiv \left( \begin{array}{cccc} p_0 q_0 & p_0(1-q_0) & (1-p_0)q_0 &(1-p_0)(1-q_0)\\ p_0 q_0 & p_0(1-q_0) & (1-p_0)q_0 &(1-p_0)(1-q_0)\\ p_0 q_0 & p_0(1-q_0) & (1-p_0)q_0 &(1-p_0)(1-q_0)\\ p_0 q_0 & p_0(1-q_0) & (1-p_0)q_0 &(1-p_0)(1-q_0) \end{array} \right) \end{equation} $v_1+v_2+v_3+v_4=1$であるので,$\bm v(0)=\bm v^T M_0$が成り立つ.式\eqref{eq:u}について,$\bm v(0)=\bm v^T M_0$を代入し,両辺に右から$(I-\delta M)$をかけると, \begin{equation} \label{eq:u2_2} \bm v^T (I-\delta M)=\bm v^T M_0 \end{equation} が得られる\cite{MamiyaIchinose2020bioRxiv}.式\eqref{eq:u2_2}と$M^\prime \equiv \delta M+(1-\delta)M_0-I$とする.$Adj(M^\prime)$の4行目をベクトルとして,$\bm u$とおくと,Press-Dysonが行った操作によって,$\bm u$と任意のベクトル$\bm f=(f_1,f_2,f_3,f_4)$の内積は, \begin{equation} \label{eq:D_err} \bm u\cdot \bm f= \left| \begin{array}{cccc} \delta p_1 q_1-1 +p_0 q_0(1-\delta)& \delta p_1-1 +p_0(1-\delta)& \delta q_1-1 +q_0 (1-\delta)& f_1\\ \delta p_2 q_3+p_0 q_0(1-\delta)& \delta p_2-1+p_0(1-\delta)& \delta q_3 +q_0 (1-\delta)& f_2\\ \delta p_3 q_2+p_0 q_0(1-\delta)& \delta p_3 +p_0(1-\delta)& \delta q_2-1+q_0 (1-\delta)& f_3\\ \delta p_4 q_4+p_0 q_0(1-\delta)& \delta p_4 +p_0(1-\delta)& \delta q_4 +q_0 (1-\delta)& f_4 \end{array} \right| \equiv D(\bm p,\bm q,\bm f) \end{equation} と書ける.さらに,式\eqref{eq:D_err}を正規化すると,平均分布$\bm v$と$\bm f$の内積が得られる.したがって,プレイヤーXの期待利得は \begin{equation} s_X=\bm v \cdot \bm S_X=\frac{\bm u \cdot \bm S_X}{\bm u \cdot \bm 1} =\frac{D(\bm p,\bm q,\bm S_X)}{D(\bm p,\bm q,\bm 1)} \end{equation} となる.同様に,プレイヤーYでは, \begin{equation} s_Y=\bm v \cdot \bm S_Y=\frac{\bm u \cdot \bm S_Y}{\bm u \cdot \bm 1} =\frac{D(\bm p,\bm q,\bm S_Y)}{D(\bm p,\bm q,\bm 1)} \end{equation} となる.$s_X$と$s_Y$を線形結合すると,行列式の性質から \begin{equation}\label{liner_eq_2} \alpha s_X +\beta s_Y +\gamma= \frac{D(\bm p,\bm q,\alpha \bm S_X+\beta \bm S_Y+\gamma \bm 1)}{D(\bm p,\bm q,\bm 1)} \end{equation} と表せる.ここで,相手の戦略にかかわらず,$D(\bm p,\bm q,\alpha \bm S_X+\beta \bm S_Y+\gamma \bm 1)=0$を成り立たせることができたとき, \begin{equation}\label{eq:linear_eq} \alpha s_X +\beta s_Y +\gamma= 0 \end{equation} の関係を強いることができる.つまり,自分と相手の利得の期待値の関係が線形にさせることができる.また,式\eqref{liner_eq_2}の右辺の分子は以下の行列式の形で与えられる. \begin{equation}\label{eq:det_numerator} \begin{split} &D(\bm p,\bm q,\alpha \bm S_X+\beta \bm S_Y+\gamma \bm 1)=\\ & \left| \begin{array}{cccc} \delta p_1 q_1-1 +p_0 q_0(1-\delta)& \delta p_1-1 +p_0(1-\delta)& \delta q_1-1 +q_0 (1-\delta)& \alpha R+\beta R +\gamma\\ \delta p_2 q_3+p_0 q_0(1-\delta)& \delta p_2-1+p_0(1-\delta)& \delta q_3 +q_0 (1-\delta)& \alpha S+\beta T +\gamma\\ \delta p_3 q_2+p_0 q_0(1-\delta)& \delta p_3 +p_0(1-\delta)& \delta q_2-1+q_0 (1-\delta)& \alpha T+\beta S +\gamma\\ \delta p_4 q_4+p_0 q_0(1-\delta)& \delta p_4 +p_0(1-\delta)& \delta q_4 +q_0 (1-\delta)& \alpha P+\beta P +\gamma \end{array} \right| \end{split} \end{equation} よって,Zero-determinant戦略は, \begin{equation} \label{zd_equation} \begin{split} \delta p_1-1+p_0(1-\delta)&=\alpha R+\beta R+\gamma \\ \delta p_2-1+p_0(1-\delta)&=\alpha S+\beta T+\gamma \\ \delta p_3+p_0(1-\delta) &=\alpha T+\beta S+\gamma \\ \delta p_4+p_0(1-\delta) &=\alpha P+\beta P+\gamma \end{split} \end{equation} で与えられる.