完全記憶ゲームと不完全記憶ゲーム
問題としている戦略的状況が完備情報の動学ゲームであるとともに、それが展開型ゲーム\begin{equation*}
\Gamma =\left( I\cup \left\{ 0\right\} ,A,X,>,a,\mathcal{H},i,p,\left\{
u_{i}\right\} _{i\in I}\right)
\end{equation*}として記述されているものとします。ただし、\(I\cup \left\{ 0\right\} \)は自然に相当するプレイヤー\(0\)を含めたプレイヤー集合、\(A\)は行動集合、\(\left( X,>\right) \)はゲームの木、\(a:X\backslash \left\{ x_{0}\right\} \rightarrow A\)はそれぞれの手番へ到達する直前に選択される行動を特定する写像、\(\mathcal{H}\)は情報分割、\(i:\mathcal{H}\rightarrow I\cup \left\{ 0\right\} \)はそれぞれの情報集合において意思決定を行うプレイヤーを特定する写像、\(p:\mathcal{H}_{0}\times A\rightarrow \left[0,1\right] \)は自然による意思決定を記述する確率分布、\(u_{i}:Z\rightarrow \mathbb{R} \)はプレイヤー\(i\)の利得関数です。
動学ゲームのプレイヤーは意思決定を行う際に、ゲーム内において自身が観察した情報を記憶しているとは限りません。つまり、それ以前に自身が行った意思決定の内容を覚えているとは限りませんし、また、他のプレイヤーによる意思決定の内容を観察しても、それを覚えているとは限りません。何かを観察できることと、それを覚えていることは概念として一致するとは限りません。自分や他のプレイヤーが行った意思決定を覚えている場合とそうでない場合とではプレイヤーによる意思決定の内容が変わってくるため、動学ゲームを分析する際には、プレイヤーが観察した情報をどの程度覚えているかを事前に明らかにしておく必要があります。
動学ゲームに参加するすべてのプレイヤーが、自身が意思決定を行うすべての局面において、自身がすでに観察した自分ないし他のプレイヤーによる意思決定の内容をすべて覚えているのであれば、そのようなゲームを完全記憶ゲーム（game of
perfect recall）と呼びます。逆に、動学ゲームが完全記憶ゲームでない場合には、すなわち、少なくとも1人のプレイヤーが、自身が意思決定を行う少なくとも1つの局面において、自身がすでに観察した自分ないし他のプレイヤーによる意思決定を完全には覚えていない場合には、そのようなゲームを不完全記憶ゲーム（game of imperfect recall）と呼びます。
では、完全記憶ゲームや不完全記憶ゲームをどのような形で定式化すればよいでしょうか。例を交えながら順番に考えます。
プレイヤー\(1\)が初期点\(x_{0}\)において行動\(a_{12}\)を選択するとゲームは手番\(x_{1}\)へ到達しますが、このゲームでは2つの手番\(x_{0},x_{1}\)は同一の情報集合\(H_{1}\)に属しているため、プレイヤー\(1\)は自身が\(x_{0}\)と\(x_{1}\)のどちらにいるかを識別できません。プレイヤー\(1\)が、初期点\(x_{0}\)において自身が行動\(a_{12}\)を選択したことを記憶しているのであれば、自分が\(x_{0}\)ではなく\(x_{1}\)にいることを認識できるため、このような事態は起こり得ません。逆に、このゲームは、プレイヤー\(1\)が初期点\(x_{0}\)において行った自身の意思決定を記憶していない状況を記述していることになります。したがってこれは不完全記憶ゲームです。
上の例のように、少なくとも1人のプレイヤー（上の例におけるプレイヤー\(1\)）について、そのプレイヤーが意思決定を行う複数の手番（上の例における手番\(x_{0},x_{1}\)）が同一の経路上にあり、なおかつそれらの手番が同一の情報集合（上の例における情報集合\(H_{1}\)）に属する場合には、そのゲームは不完全記憶ゲームであると言えます。言い換えると、何らかの情報集合が何らかの頂点への経路と複数の点で交わる場合、そのゲームは不完全記憶ゲームです（上の例では、情報集合\(H_{1}\)が頂点\(z_{2}\)への経路や頂点\(z_{3}\)への経路と複数の点\(x_{0},x_{1}\)で交わっている）。なぜなら、そのような条件を満たす情報集合に属する手番\(x_{i},x_{j}\)を任意に選んだとき、\(x_{i}>x_{j}\)であるならば、ゲームが\(x_{j}\)へ到達したときに、そのプレイヤーは\(x_{i}\)において行った自身の行動を記憶していないことを意味するからです。
逆に、ゲームが完全記憶であるためには、任意のプレイヤーについて、そのプレイヤーが意思決定を行う複数の手番が同一経路上に存在する場合、それらが同一の情報集合に属するような可能性を排除する必要があります。言い換えると、頂点\(z\in Z\)と情報集合\(H\in \mathcal{H}\)をそれぞれ任意に選んだとき、頂点\(z\)への経路上にあり、なおかつ\(H\)の要素であるような手番が複数存在する可能性を排除する必要があります。そこで、これを完全記憶ゲームが満たすべき1つ目の条件と定めます。
逆に、上の条件が満たされない場合、それは不完全記憶ゲームです。つまり、展開型ゲーム\(\Gamma \)において、何らかの頂点\(z\in Z\)と情報集合\(H\in \mathcal{H}\)に関して、頂点\(z\)への経路上にあり、なおかつ情報集合\(H\)の要素でもあるような手番の個数が\(2\)以上であるならば、それは不完全記憶ゲームです。繰り返しになりますが、先の例は不完全記憶ゲームの具体例です。実際、頂点\(z_{2}\)（または頂点\(z_{2}\)）と情報集合\(H_{1}\)が条件を満たします。
ただ、以上の条件は完全記憶ゲームが満たすべきものの1つに過ぎず、完全記憶ゲームの定義として不十分です。実際、以上の条件を満たすような不完全記憶ゲームが存在し得るからです。したがって、完全記憶ゲームに要求すべき追加的な条件が存在します。以下の例より明らかです。
プレイヤー\(1\)が初期点\(x_{0}\)において行動\(a_{11}\)を選択すれば手番\(x_{1}\)へ到達します。一方、初期点\(x_{0}\)において行動\(a_{12}\)を選択し、移動先の手番\(x_{2}\)において行動\(a_{11}\)を選択すれば手番\(x_{3}\)へ到達します。ただ、2つの手番\(x_{1},x_{3}\)は同一の情報集合\(H_{1}\)に属しているため、プレイヤー\(1\)は自身が\(x_{1}\)と\(x_{3}\)のどちらにいるかを識別できません。\(x_{1}\)と\(x_{3}\)の双方について、直前に選択している行動は\(a_{11}\)であるため、プレイヤー\(1\)が\(x_{1}\)ないし\(x_{3}\)へ到達する直前に選択した行動を覚えているかどうかはここでの問題ではありません。さて、プレイヤー\(1\)が\(x_{1}\)へ到達するためには\(x_{0}\)において合計1回の意思決定を行う必要がある一方、\(x_{3}\)へ到達するためには\(x_{0}\)と\(x_{2}\)において合計2回の意思決定を行う必要があります。したがって、プレイヤー\(1\)が常に自身が意思決定を行った回数を記憶しているのであれば、自分が\(x_{1}\)と\(x_{3}\)のどちらにいるかを識別できるため、このような事態は起こり得ません。逆に、このゲームは、プレイヤー\(1\)が自身が意思決定を行った回数を記憶していない状況を記述していることになります。したがってこれは不完全記憶ゲームです。
上の例のように、少なくとも1人のプレイヤー（上の例におけるプレイヤー\(1\)）と、そのプレイヤーが意思決定を行う少なくとも1つの情報集合（上の例における\(H_{1}\)）について、その要素であるような異なる手番\(x_{i},x_{j}\)（上の例における\(x_{1},x_{3}\)）に注目したとき、初期点\(x_{0}\)から手番\(x_{i}\)への経路上に存在するそのプレイヤーの手番の個数と、初期点\(x_{0}\)から手番\(x_{j} \)への経路上に存在するそのプレイヤーの手番の個数が異なる場合、そのゲームは不完全記憶ゲームです。なぜなら、そのような条件を満たす手番\(x_{i},x_{j}\)が存在することは、プレイヤーが自身が意思決定を行った回数を記憶していないことを意味するからです。
逆に、ゲームが完全記憶であるためには、プレイヤーと、そのプレイヤーが意思決定を行う情報集合、そしてその情報集合に属する手番\(x_{i},x_{j}\)をそれぞれ任意に選んだとき、初期点から手番\(x_{i}\)への経路上に存在するそのプレイヤーの手番の個数と、初期点から手番\(x_{j}\)への経路上に存在するプレイヤーの手番の個数が同じである必要があります。そこで、これを完全記憶ゲームが満たすべき2つ目の条件と定めます。
\end{equation*}で表記する。また、初期点\(x_{0}\)から手番\(\hat{x}\)への経路上にあるノードの中でもプレイヤー\(i\)が意思決定を行う手番を初期点から近い順に、\begin{equation*}\hat{x}_{i}^{1},\hat{x}_{i}^{2},\cdots ,\hat{x}_{i}^{\hat{L}}
\end{equation*}で表記する。このとき、\begin{equation*}
L=\hat{L}
\end{equation*}が成り立つ。
先の条件と同様、これもまた完全記憶ゲームの定義ではなく、完全記憶ゲームが満たすべき条件の1つです。逆に、上の条件が満たされない場合、それは不完全記憶ゲームです。つまり、展開型ゲーム\(\Gamma \)において、何らかのプレイヤー\(i\)の何らかの情報集合\(H\in \mathcal{H}_{i}\)およびその要素であるような何らかの手番\(x,\hat{x}\in H\)について、上のように定義される手番の個数\(L,\hat{L}\)が\(L\not=\hat{L}\)を満たすならば、それは不完全記憶ゲームです。繰り返しになりますが、先の例は不完全記憶ゲームの具体例です。実際、プレイヤー\(1\)の情報集合\(H_{1}\)の要素である手番\(x_{1},x_{3}\)について\(1\not=2\)が成り立ちます。
ただ、以上の条件は完全記憶ゲームが満たすべきものの1つに過ぎず、完全記憶ゲームの定義として不十分です。実際、これまで提示した条件を満たすような不完全記憶ゲームが存在し得るからです。したがって、完全記憶ゲームに要求すべき追加的な条件が存在します。以下の例より明らかです。
プレイヤー\(1\)の立場からこのゲームを観察します。プレイヤー\(1\)は初期点\(x_{0}\)における自身の意思決定を観察できますが、相手であるプレイヤー\(2\)が情報集合\(\left\{ x_{1},x_{2}\right\} \)において行う意思決定を観察することはできません。ただ、自身が\(x_{0}\)において行動\(a_{11}\)を選択したことを覚えているならば、プレイヤー\(2\)による意思決定の後に自身が情報集合\(\left\{ x_{3},x_{4}\right\} \)へ到達することは認識できますし、逆に、自身が\(x_{0}\)において行動\(a_{12}\)を選択したことを覚えているならば、プレイヤー\(2\)による意思決定の後に自身が情報集合\(\left\{ x_{5},x_{6}\right\} \)へ到達することは認識できます。ただ、実際には、このゲームにおいて手番\(x_{3},x_{4},x_{5},x_{6}\)は同一の情報集合の要素であるため、プレイヤー\(1\)は自身が\(\left\{ x_{3},x_{4}\right\} \)と\(\left\{x_{5},x_{6}\right\} \)のどちらかにいるかを識別できません。このような事態が起こる理由は、プレイヤー\(1\)が初期点\(x_{0}\)において自身が\(a_{11}\)と\(a_{12}\)のどちらを選択したかを記憶していないことにあります。したがってこれは不完全記憶ゲームです。
上の例のように、少なくとも1人のプレイヤー（上の例におけるプレイヤー\(1\)）と、そのプレイヤーが意思決定を行う少なくとも1つの情報集合（上の例における\(\left\{x_{3},x_{4},x_{5},x_{6}\right\} \)）について、その要素であるような異なる手番\(x_{i},x_{j}\)（上の例における\(x_{3},x_{5}\)など）に注目したとき、初期点\(x_{0}\)から手番\(x_{i} \)へ到達するために選択すべき行動の列（上の例において\(x_{3}\)へ到達するために選択すべき行動は\(a_{11}\)）と、初期点\(x_{0}\)から手番\(x_{j} \)へ到達するために選択すべき行動の列が異なる場合（上の例において\(x_{5}\)へ到達するために選択すべき行動は\(a_{12}\)）、そのゲームは不完全記憶ゲームです。なぜなら、そのような条件を満たす手番\(x_{i},x_{j}\)が存在することは、それ以前の何らかの手番において自身が行った選択の内容（上の例における手番\(x_{0}\)における意思決定）を記憶していないことを意味しているからです。
逆に、ゲームが完全記憶であるためには、プレイヤーと、そのプレイヤーが意思決定を行う情報集合、そしてその情報集合に属する手番\(x_{i},x_{j}\)をそれぞれ任意に選んだとき、初期点から手番\(x_{i}\)へ到達するために選択すべき行動の列と、初期点\(x_{0}\)から手番\(x_{j}\)へ到達するために選択すべき行動の列が同じである必要があります。同一の情報集合上にある手番へは、常に同じ行動の列のもとで到達する必要があるということです。そこで、これを完全記憶ゲームが満たすべき3つ目の条件と定めます。先に提示した2番目の条件と合わせると、これを以下のように定式化できます。
\end{equation*}で表記する。また、初期点\(x_{0}\)から手番\(\hat{x}\)への経路上にあるノードの中でもプレイヤー\(i\)が意思決定を行う手番を初期点から近い順に、\begin{equation*}\hat{x}_{i}^{1},\hat{x}_{i}^{2},\cdots ,\hat{x}_{i}^{\hat{L}}
\end{equation*}で表記する。このとき、\begin{equation*}
L=\hat{L}
\end{equation*}とともに、\begin{equation*}
\forall l\in \left\{ 1,\cdots ,L\right\} :a_{i}\left( x_{i}^{l}\rightarrow
x\right) =a_{i}\left( \hat{x}_{i}^{l}\rightarrow \hat{x}\right)
\end{equation*}が成り立つものとする。ただし、\(a_{i}\left(x_{i}^{l}\rightarrow x\right) \)はプレイヤー\(i\)が手番\(x\)へ到達するために手番\(x_{i}^{l}\)において選択すべき行動である。\(a_{i}\left( \hat{x}_{i}^{l}\rightarrow \hat{x}\right) \)についても同様である。
逆に、上の条件が満たされない場合、それは不完全記憶ゲームです。つまり、展開型ゲーム\(\Gamma \)において、何らかのプレイヤー\(i\)の何らかの情報集合\(H\in \mathcal{H}_{i}\)およびその要素であるような何らかの手番\(x,\hat{x}\in H\)に注目したとき、上のように定義される手番の個数\(L,\hat{L}\)について\(L=\hat{L}\)が成り立つ一方で、何らかの\(l\in \left\{ 1,\cdots ,L\right\} \)について\(x_{i}^{l}=\hat{x}_{i}^{l}\)かつ\(a_{i}\left( x_{i}^{l}\rightarrow x\right) \not=a_{i}\left( \hat{x}_{i}^{l}\rightarrow \hat{x}\right) \)が成り立つならば、それは不完全記憶ゲームです。繰り返しになりますが、先の例は不完全記憶ゲームの具体例です。実際、プレイヤー\(1\)の情報集合\(\left\{x_{3},x_{4},x_{5},x_{6}\right\} \)の要素である手番\(x_{3},x_{5}\)に対して、手番\(x_{0}\)が、\begin{equation*}a_{1}\left( x_{0}\rightarrow x_{3}\right) \not=a_{1}\left( x_{0}\rightarrow
x_{5}\right)
\end{equation*}を満たします。
ただ、以上の条件は完全記憶ゲームが満たすべきものの1つに過ぎず、完全記憶ゲームの定義として不十分です。実際、これまで提示した条件を満たすような不完全記憶ゲームが存在し得るからです。したがって、完全記憶ゲームに要求すべき追加的な条件が存在します。以下の例より明らかです。
プレイヤー\(2\)の立場からこのゲームを観察します。プレイヤー\(2\)は初期点\(x_{0}\)におけるプレイヤー\(1\)の意思決定を観察できますが、観察した情報を覚えているならば、後の時点において自分が\(\left\{ x_{5}\right\} \)と\(\left\{ x_{6}\right\} \)のどちらにいるかを識別できます。ただ、実際には、このゲームにおいて手番\(x_{5},x_{6}\)は同一の情報集合の要素であるため、プレイヤー\(2\)は自身が\(\left\{x_{5}\right\} \)と\(\left\{ x_{6}\right\} \)のどちらにいるかを識別できません。このような事態が起こる理由は、プレイヤー\(1\)が初期点\(x_{0}\)において\(a_{11}\)と\(a_{12}\)のどちらの行動を選択したかをプレイヤー\(2\)が記憶していないことにあります。したがってこれは不完全記憶ゲームです。
上の例のように、少なくとも1人のプレイヤー（上の例におけるプレイヤー\(2\)）と、そのプレイヤーが意思決定を行う少なくとも1つの情報集合（上の例における\(\left\{x_{5},x_{6}\right\} \)）について、その要素であるような異なる手番\(x_{i},x_{j}\)（上の例における\(x_{5},x_{6}\)）に注目したとき、\(x_{i}\)ないし\(x_{j}\)へ到達するまでのそのプレイヤーが自身の異なる情報集合を経由する場合（上の例において\(x_{5}\)へ到達する以前に通る\(\left\{ x_{1}\right\} \)と\(x_{6}\)へ到達する以前に通る\(\left\{ x_{2}\right\} \)が異なる）、そのゲームは不完全記憶ゲームです。そのような異なる情報集合が存在することは、それ以前に行われた他のプレイヤーの意思決定を観察できたことを意味する一方、手番\(x_{i},x_{j}\)が同一の情報集合に属することは、先述の観察した情報を忘れてしまったことを意味するからです。そこで、これを完全記憶ゲームが満たすべき4つ目の条件と定めます。先に提示した2番目の条件と合わせると、これを以下のように定式化できます。
\end{equation*}で表記する。また、初期点\(x_{0}\)から手番\(\hat{x}\)への経路上にあるノードの中でもプレイヤー\(i\)が意思決定を行う手番を初期点から近い順に、\begin{equation*}\hat{x}_{i}^{1},\hat{x}_{i}^{2},\cdots ,\hat{x}_{i}^{\hat{L}}
\end{equation*}で表記する。このとき、\begin{equation*}
L=\hat{L}
\end{equation*}とともに、\begin{equation*}
\forall l\in \left\{ 1,\cdots ,L\right\} :H\left( x_{i}^{l}\right) =H\left(
\hat{x}_{i}^{l}\right)
\end{equation*}が成り立つものとする。ただし、\(H\left( x_{i}^{l}\right) \)は手番\(x_{i}^{l}\)が属する情報集合である。\(H\left( \hat{x}_{i}^{l}\right) \)についても同様である。
逆に、上の条件が満たされない場合、それは不完全記憶ゲームです。つまり、展開型ゲーム\(\Gamma \)において、何らかのプレイヤー\(i\)の何らかの情報集合\(H\in \mathcal{H}_{i}\)およびその要素であるような何らかの手番\(x,\hat{x}\in H\)に注目したとき、上のように定義される手番の個数\(L,\hat{L}\)について\(L=\hat{L}\)が成り立つ一方で、何らかの\(l\in \left\{ 1,\cdots ,L\right\} \)について\(H\left( x_{i}^{l}\right) \not=H\left( \hat{x}_{i}^{l}\right) \)が成り立つならば、それは不完全記憶ゲームです。繰り返しになりますが、先の例は不完全記憶ゲームの具体例です。実際、プレイヤー\(1\)の情報集合\(\left\{ x_{5},x_{6}\right\} \)の要素である手番\(x_{5},x_{6}\)に対して、手番\(x_{1},x_{2}\)が、\begin{equation*}H\left( x_{1}\right) \not=H\left( x_{2}\right)
\end{equation*}を満たします。
完全記憶ゲームと不完全記憶ゲームの定義
以上の諸条件によって完全記憶ゲームの定義とします。つまり、展開型ゲーム\(\Gamma \)が完全記憶ゲームであることは、以下の条件がすべて満たされることを意味します。
- 頂点\(z\in Z\)と情報集合\(H\in \mathcal{H}\)をそれぞれ任意に選んだとき、頂点\(z\)への経路上にあり、なおかつ情報集合\(H\)の要素でもあるような手番の個数は\(0\)または\(1\)である。
- プレイヤー\(i\in I\)と、プレイヤー\(i\)の情報集合\(H\in \mathcal{H}_{i}\)およびその要素であるような手番\(x,\hat{x}\in H\)をそれぞれ任意に選ぶ。初期点\(x_{0}\)から手番\(x\)への経路上にあるノードの中でもプレイヤー\(i\)が意思決定を行う手番を初期点から近い順に、\begin{equation*}x_{i}^{1},x_{i}^{2},\cdots ,x_{i}^{L}\end{equation*}で表記する。また、初期点\(x_{0}\)から手番\(\hat{x}\)への経路上にあるノードの中でもプレイヤー\(i\)が意思決定を行う手番を初期点から近い順に、\begin{equation*}\hat{x}_{i}^{1},\hat{x}_{i}^{2},\cdots ,\hat{x}_{i}^{\hat{L}}
\end{equation*}で表記する。このとき、\begin{eqnarray*}
&&\left( a\right) \ L=\hat{L} \\
&&\left( b\right) \ \forall l\in \left\{ 1,\cdots ,L\right\} :a_{i}\left(
x_{i}^{l}\rightarrow x\right) =a_{i}\left( \hat{x}_{i}^{l}\rightarrow \hat{x}\right) \\
&&\left( c\right) \ \forall l\in \left\{ 1,\cdots ,L\right\} :H\left(
x_{i}^{l}\right) =H\left( \hat{x}_{i}^{l}\right)
\end{eqnarray*}が成り立つ。ただし、\(a_{i}\left( x_{i}^{l}\rightarrow x\right) \)はプレイヤー\(i\)が手番\(x\)へ到達するために手番\(x_{i}^{l}\)において選択すべき行動であり、\(a_{i}\left( \hat{x}_{i}^{l}\rightarrow \hat{x}\right) \)はプレイヤー\(i\)が手番\(\hat{x}\)へ到達するために手番\(\hat{x}_{i}^{l}\)において選択すべき行動である。また、\(H\left(x_{i}^{l}\right) \)は手番\(x_{i}^{l}\)が属する情報集合であり、\(H\left( \hat{x}_{i}^{l}\right) \)は手番\(\hat{x}_{i}^{l}\)が属する情報集合である。
逆に、展開型ゲーム\(\Gamma \)が以上の条件の中の少なくとも1つを満たさない場合、それは不完全記憶ゲームです。
完全情報ゲームと完全記憶ゲームの関係
展開型ゲーム\(\Gamma \)が完全情報ゲームである場合、すべての情報集合は1点集合であるため、これは明らかに完全記憶ゲームが要求する条件をすべて満たします。つまり、完全情報ゲームは完全記憶ゲームであるということです。
上の命題の逆は成立するとは限りません。つまり、完全記憶ゲームは完全情報ゲームであるとは限りません。以下の例より明らかです。
演習問題
プレミアム会員専用コンテンツです
【ログイン】【会員登録】