繰り返しゲームにおける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戦略の研究をより発展させることができると考えています．
繰り返し囚人のジレンマゲーム
２人プレイヤーi$\in\{X,Y\}$の繰り返し囚人のジレンマゲームを考える．ゲームのそれぞれのラウンドで，プレイヤーは，協力（C）か裏切り（D）の行動を選ぶ．プレイヤーの利得は，自分と相手の行動によって決まる．利得行列は
で与えられる．繰り返し囚人のジレンマゲームを考えているので，$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}
で与えられる．