WIIS

完備情報の動学ゲーム

展開型ゲームの部分ゲーム

目次

関連知識

Mailで保存
Xで共有

展開型ゲームの部分ゲーム

問題としている戦略的状況が完備情報の動学ゲームであり、それが展開型ゲーム\begin{equation*}
\Gamma =\left( I\cup \left\{ 0\right\} ,X,>,A,a,\mathcal{H},i,p,\left\{
u_{i}\right\} _{i\in I}\right)
\end{equation*}として表現されているものとします。ただし、\(I\cup \left\{ 0\right\} \)は自然を含めたプレイヤー集合、\(\left( X,>\right) \)はゲームの木、\(A\)は行動集合、\(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}\)はプレイヤー\(i\in I\)の利得関数です。

展開型ゲーム\(\Gamma \)が与えられたとき、手番\(x\in X\backslash Z\)を適切に選択することにより、\(x\)を初期点とする\(\Gamma \)の部分ゲーム(sub game)と呼ばれる局所的な展開型ゲームを取り出すことができます。初期点を\(x\)とする部分ゲームを、\begin{equation*}\Gamma \left( x\right) =\left( I^{x}\cup \left\{ 0\right\}
,X^{x},>^{x},A^{x},a^{x},\mathcal{H}^{x},i^{x},p^{x},\left\{
u_{i}^{x}\right\} _{i\in I^{x}}\right)
\end{equation*}で表記します。直感的に言うと、展開型ゲーム\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)とは、もとのゲーム\(\Gamma \)に含まれる手番\(x\)を初期点とみなした場合の展開型ゲームであり、それ単独でゲームとして分析可能であるようなものに相当します。以降では、部分ゲーム\(\Gamma \left( x\right) \)を構成する要素と、それらの要素が満たすべき条件について解説します。

 

部分ゲームの初期点

部分ゲーム\(\Gamma \left( x\right) \)の初期点\(x\)は以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ x\in X\backslash Z \\
&&\left( b\right) \ \exists i\in I\cup \left\{ 0\right\} :\left\{ x\right\}
\in \mathcal{H}_{i}
\end{eqnarray*}を満たすものである必要があります。

条件\(\left( a\right) \)は、部分ゲーム\(\Gamma \left( x\right) \)の初期点\(x\)は、もとのゲーム\(\Gamma \)の手番であること、すなわち頂点ではないノードであることを意味します。条件\(\left( b\right) \)は、部分ゲーム\(\Gamma \left( x\right) \)の初期点\(x\)は、もとのゲーム\(\Gamma \)において単独で情報集合を構成するような手番であることを意味します。言い換えると、もとのゲーム\(\Gamma \)においてプレイヤー\(i\)の情報集合\(H_{i}\in \mathcal{H}_{i}\)が複数の手番を要素として持つ場合、その情報集合\(H_{i}\)の要素であるような任意の手番は部分ゲームの初期点にはなり得ません。

例(部分ゲームの初期点)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:部分ゲーム
図:部分ゲーム

手番\(x_{0},x_{1}\)はそれぞれ単独で情報集合を構成しているため、これらの手番は部分ゲームの初期点になり得ます。一方、手番\(x_{2},x_{3}\)は複数のノードを含む情報集合\(\left\{ x_{2},x_{3}\right\} \)を構成しているため、これらの手番は部分ゲームの初期点にはなり得ません。また、\(z_{1},z_{2},z_{3},z_{4}\)は頂点であるため、これらも部分ゲームの初期点にはなり得ません。

 

部分ゲームのプレイヤー

部分ゲーム\(\Gamma \left( x\right) \)のプレイヤー集合\(I^{x}\)は、初期点\(x\)の選び方とは関係なく、もとのゲーム\(\Gamma \)のプレイヤー集合\(I\)と一致するものと定めます。つまり、\begin{equation*}I^{x}=I
\end{equation*}であるということです。したがって、自然がプレイヤーに含まれる場合のプレイヤー集合は、\begin{equation*}
I^{x}\cup \left\{ 0\right\} =I\cup \left\{ 0\right\}
\end{equation*}となります。このような事情を踏まえた上で、\(I^{x}\)を\(I\)と表記してもよいものと定めます。

 

部分ゲームにおける意思決定の順番(ゲームの木)

部分ゲーム\(\Gamma \left( x\right) \)のゲームの木\(\left( X^{x},>^{x}\right) \)を以下のように定めます。

部分ゲーム\(\Gamma \left( x\right) \)のノード集合\(X^{x}\)は、初期点\(x\)と、もとのゲーム\(\Gamma \)において\(x\)の後に起こり得るすべてのノードを要素として持つ集合と定めます。つまり、\begin{equation*}X^{x}=\left\{ x\right\} \cup \left\{ x^{\prime }\in X\ |\ x>x^{\prime
}\right\}
\end{equation*}であるということです。したがって、部分ゲーム\(\Gamma \left( x\right) \)の頂点集合は、\begin{equation*}Z^{x}=Z\cap X^{x}
\end{equation*}となります。

部分ゲーム\(\Gamma \left( x\right) \)のノード集合\(X^{x}\)上に定義された前後関係\(>^{x}\)は、もとのゲーム\(\Gamma \)におけるノード集合\(X\)上の前後関係\(>\)を\(X^{x}\)上に縮小したものと定めます。つまり、任意のノード\(x^{\prime },x^{\prime \prime }\in X^{x}\)に対して、\begin{equation*}x^{\prime }>^{x}x^{\prime \prime }\Leftrightarrow x^{\prime }>x^{\prime
\prime }
\end{equation*}を満たすものとして\(>^{x}\)を定義するということです。このような事情を踏まえた上で、\(>^{x}\)を\(>\)と表記してもよいものと定めます。

例(部分ゲームのゲームの木)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:部分ゲーム
図:部分ゲーム

部分ゲームの初期点として\(x_{1}\)を選んだ場合、部分ゲーム\(\Gamma \left(x_{1}\right) \)のノード集合は、\begin{equation*}X^{x_{1}}=\left\{ x_{1},x_{2},x_{3},z_{1},z_{2},z_{3},z_{4}\right\}
\end{equation*}となります。部分ゲーム\(\Gamma \left( x_{1}\right) \)の前後関係\(>^{x}\)は、上図において初期点\(x_{1}\)以降のノードどうしを結ぶ有向線分(上から下へ伸びているものとみなす)として表現されています。また、部分ゲームの初期点として\(x_{0}\)を選んだ場合、部分ゲーム\(\Gamma \left(x_{0}\right) \)のノード集合\(X^{x_{0}}\)はもとのゲーム\(\Gamma \)のノード集合\(X\)と一致し、前後関係\(>^{x_{0}}\)はもとのゲーム\(\Gamma \)の前後関係\(>\)と一致します。

 

部分ゲームにおける行動

部分ゲーム\(\Gamma \left( x\right) \)の行動集合\(A^{x}\)は、初期点\(x\)の選び方とは関係なく、もとのゲーム\(\Gamma \)の行動集合\(A\)と一致するものと定めます。つまり、\begin{equation*}A^{x}=A
\end{equation*}であるということです。このような事情を踏まえた上で、\(A^{x}\)を\(A\)と表記してもよいものと定めます。

部分ゲーム\(\Gamma \left( x\right) \)においてそれぞれのノードへ到達する直前に選択される行動を特定する写像\(a^{x}:X^{x}\backslash\left\{ x\right\} \rightarrow A^{x}\)は、もとのゲーム\(\Gamma \)においてそれぞれのノードへ到達する直前に選択される行動を特定する\(a:X\backslash \left\{ x_{0}\right\} \rightarrow A\)の定義域を\(X^{x}\backslash \left\{ x\right\} \)上に縮小したものと定めます。つまり、任意のノード\(x^{\prime }\in X^{x}\backslash \left\{ x\right\} \)に対して、\begin{equation*}a^{x}\left( x^{\prime }\right) =a\left( x^{\prime }\right)
\end{equation*}を満たすものとして\(a^{x}\)を定義するということです。このような事情を踏まえた上で、\(a^{x}\)を\(a\)と表記してもよいものと定めます。

例(部分ゲームにおける行動)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:部分ゲーム
図:部分ゲーム

部分ゲームの初期点として\(x_{1}\)を選んだ場合、写像\(a^{x_{1}}:\left\{x_{2},x_{3},z_{1},z_{2},z_{3},z_{4}\right\} \rightarrow A^{x_{1}}\)は、\begin{eqnarray*}a^{x_{1}}\left( x_{2}\right) &=&a_{21} \\
a^{x_{1}}\left( x_{3}\right) &=&a_{22} \\
a^{x_{1}}\left( z_{1}\right) &=&a^{x_{1}}\left( z_{3}\right) =a_{13} \\
a^{x_{1}}\left( z_{2}\right) &=&a^{x_{1}}\left( z_{4}\right) =a_{14}
\end{eqnarray*}を満たします。また、部分ゲームの初期点として\(x_{0}\)を選んだ場合、写像\(a^{x_{0}}\)はもとのゲーム\(\Gamma \)の写像\(a\)と一致します。

 

部分ゲームにおける情報(情報集合)

部分ゲーム\(\Gamma \left( x\right) \)の手番集合は\(X^{x}\backslash Z^{x}\)であるため、もとのゲーム\(\Gamma \)の情報集合\(H\in \mathcal{H}\)を任意に選んだとき、この情報集合\(H\)に含まれる手番の中でも部分ゲーム\(\Gamma \left( x\right) \)の手番でもあるようなものからなる集合を\(H^{x}\)と表記するのであれば、これは、\begin{equation*}H^{x}=H\cap \left( X^{x}\backslash Z^{x}\right)
\end{equation*}となります。部分ゲーム\(\Gamma \left( x\right) \)では、もとのゲーム\(\Gamma \)における情報集合\(H\)を\(H^{x}\)へと縮小します。したがって、部分ゲーム\(\Gamma\left( x\right) \)の情報分割\(\mathcal{H}^{x}\)は、\begin{eqnarray*}\mathcal{H}^{x} &=&\left\{ H^{x}\ |\ H\in \mathcal{H}\right\} \backslash
\left\{ \phi \right\} \\
&=&\left\{ H\cap \left( X^{x}\backslash Z^{x}\right) \ |\ H\in \mathcal{H}\right\} \backslash \left\{ \phi \right\}
\end{eqnarray*}となります。ただし、もとのゲーム\(\Gamma \)におけるある情報集合\(H\in \mathcal{H}\)が部分ゲーム\(\Gamma\left( x\right) \)の手番集合\(X^{x}\backslash Z^{x}\)と交わらない可能性があるため(\(H\cap \left(X^{x}\backslash Z^{x}\right) =\phi \)となる可能性)、部分ゲーム\(\Gamma\left( x\right) \)が空集合であるような情報集合を持つ可能性を排除するために、上の定義では情報分割\(\mathcal{H}^{x}\)の中から空集合を除いています。

部分ゲーム\(\Gamma \left( x\right) \)のそれぞれの情報集合において意思決定を行うプレイヤーを特定する写像\(i^{x}:\mathcal{H}^{x}\rightarrow I^{x}\cup \left\{ 0\right\} \)は、もとのゲーム\(\Gamma \)においてそれぞれの情報集合において意思決定を行うプレイヤーを特定する写像\(i:\mathcal{H}\rightarrow I\cup \left\{ 0\right\} \)の定義域を\(\mathcal{H}^{x}\)上に縮小したものと定めます。つまり、任意の情報集合\(H^{x}\in \mathcal{H}^{x}\)に対して、\begin{equation*}i^{x}\left( H^{x}\right) =i\left( H\right)
\end{equation*}を満たすものとして\(i^{x}\)を定義するということです。このような事情を踏まえた上で、\(i^{x}\)を\(i\)と表記してもよいものと定めます。

例(部分ゲームの情報集合)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:部分ゲーム
図:部分ゲーム

部分ゲームの初期点として\(x_{1}\)を選んだ場合、部分ゲーム\(\Gamma \left(x_{1}\right) \)の情報分割は、\begin{equation*}\mathcal{H}^{x_{1}}=\left\{ \left\{ x_{1}\right\} ,\left\{
x_{2},x_{3}\right\} \right\}
\end{equation*}であり、写像\(i^{x_{1}}:\mathcal{H}^{x_{1}}\rightarrow I\)は、\begin{eqnarray*}i^{x_{1}}\left( \left\{ x_{1}\right\} \right) &=&1 \\
i^{x_{1}}\left( \left\{ x_{2},x_{3}\right\} \right) &=&2
\end{eqnarray*}を満たします。また、部分ゲームの初期点として\(x_{0}\)を選んだ場合、情報分割\(\mathcal{H}^{x_{0}}\)はもとのゲーム\(\Gamma \)の情報分割\(\mathcal{H}\)と一致し、写像\(i^{x_{0}}\)はもとのゲーム\(\Gamma \)の写像\(i\)と一致します。

 

部分ゲームにおける自然による行動

部分ゲーム\(\Gamma \left( x\right) \)における自然による意思決定を記述する確率分布\(p^{x}:\mathcal{H}_{0}^{x}\times A^{x}\rightarrow \left[ 0,1\right] \)は、もとのゲーム\(\Gamma \)における自然による意思決定を記述する確率分布\(p:\mathcal{H}_{0}\times A\rightarrow \left[ 0,1\right] \)の定義域を\(\mathcal{H}_{0}^{x}\times A^{x}\)に縮小したものと定めます。つまり、自然が意思決定を行う情報集合\(H\in \mathcal{H}_{0}^{x}\)と行動\(a\in A^{x}\)をそれぞれ任意に選んだとき、\begin{equation*}p^{x}\left( H,a\right) =p\left( H,a\right)
\end{equation*}を満たすものとして\(p^{x}\)を定義するということです。このような事情を踏まえた上で、\(p^{x}\)を\(p\)と表記してもよいものと定めます。

 

部分ゲームにおける結果と利得による行動

部分ゲーム\(\Gamma \left( x\right) \)の頂点集合は、\begin{equation*}Z^{x}=Z\cap X^{x}
\end{equation*}ですが、部分ゲーム\(\Gamma \left( x\right) \)におけるプレイヤー\(i\in I^{x}\)の利得関数\(u_{i}^{x}:Z^{x}\rightarrow \mathbb{R} \)は、もとのゲーム\(\Gamma \)におけるプレイヤー\(i\)の利得関数\(u_{i}:Z\rightarrow \mathbb{R} \)の定義域を\(Z^{x}\)に縮小したものと定めます。つまり、頂点\(z\in Z^{x}\)を任意に選んだとき、\begin{equation*}u_{i}^{x}\left( z\right) =u_{i}\left( z\right)
\end{equation*}を満たすものとして\(u_{i}^{x}\)を定義するということです。このような事情を踏まえた上で、\(u_{i}^{x}\)を\(u_{i}\)と表記してもよいものと定めます。

例(部分ゲームの利得関数)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:部分ゲーム
図:部分ゲーム

部分ゲームの初期点として\(x_{1}\)を選んだ場合、部分ゲーム\(\Gamma \left(x_{1}\right) \)におけるそれぞれのプレイヤー\(i\ \left(=1,2\right) \)の利得関数は、\begin{eqnarray*}u_{i}^{x_{1}}\left( z_{1}\right) &=&u_{i}\left( z_{1}\right) \\
u_{i}^{x_{1}}\left( z_{2}\right) &=&u_{i}\left( z_{2}\right) \\
u_{i}^{x_{1}}\left( z_{3}\right) &=&u_{i}\left( z_{3}\right) \\
u_{i}^{x_{1}}\left( z_{4}\right) &=&u_{i}\left( z_{4}\right)
\end{eqnarray*}を満たすものとして定義されます。ただし、\(u_{i}\)はもとのゲーム\(\Gamma \)におけるプレイヤー\(i\)の利得関数です。また、部分ゲームの初期点として\(x_{0}\)を選んだ場合、それぞれのプレイヤー\(i\)の利得関数\(u_{i}^{x_{0}}\)は\(u_{i}\)と一致します。

 

部分ゲームの直感的な理解

以上により、展開型ゲーム\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)を構成する要素と、それらの要素が満たすべき条件がすべて明らかになりました。では、部分ゲームが満たすべき条件は、どのような要求を反映しているのでしょうか。その意味を理解するために、逆に、部分ゲームとしての条件が満たされない場合に起こり得る問題を例を通じて確認します。

例(初期点が存在しない場合)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:初期点が存在しない場合
図:初期点が存在しない場合

グレーで囲われた領域は初期点を持たず、複数のノードを含む情報集合\(\left\{ x_{1},x_{2}\right\} \)が最初の意思決定点となっているため、これはそもそも展開型ゲームではありません。したがって、これは部分ゲームではありません。プレイヤーたちはゲームの初期点が\(x_{2}\)と\(x_{3}\)のどちらであるかを判別できず、また、自然がどちらか一方を初期点として選ぶという構造にもなっていないため、どちらが初期点であるかを確率的に考察することさえもできません。部分ゲームを独立したゲームとして分析するためには、そもそも部分ゲームは展開型ゲームでなければなりません。

例(初期点が単独で情報集合を構成しない場合)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:初期点が単独で情報集合を構成しない場合
図:初期点が単独で情報集合を構成しない場合

グレーで囲われた領域は初期点\(x_{3}\)を持ちますが、この初期点はもとの展開型ゲーム\(\Gamma \)において複数の手番を要素として持つ情報集合\(\left\{ x_{2},x_{3}\right\} \)の要素であるため、これは部分ゲームではありません。もとのゲーム\(\Gamma \)においてプレイヤー\(1\)の情報集合が\(\left\{ x_{2},x_{3}\right\} \)であることは、プレイヤー\(1\)は情報集合\(\left\{ x_{1}\right\} \)におけるプレイヤー\(2\)の意思決定の内容を観察でないことを意味します。一方、グレーの領域では1つのノードだけを含む情報集合\(\left\{ x_{3}\right\} \)が最初の意思決定点となっているため、プレイヤー\(1\)はもとのゲーム\(\Gamma \)において観察できなかった情報を観察できていることになります。以上を踏まえると、部分ゲーム\(\Gamma\left( x\right) \)の初期点\(x\)はもとのゲーム\(\Gamma \)において単独で情報集合を構成するような手番でなければならないという条件は、部分ゲームにおいてそれぞれのプレイヤーが観察可能な情報は、もとのゲームにおいて観察可能な情報と等しいことを保証する役割を担っています。

例(初期点の後に起こり得るノードを含まない場合)
以下のゲームの木として表現される展開型ゲーム\(\Gamma \)について考えます。

図:初期点の後に起こり得るノードを含まない場合
図:初期点の後に起こり得るノードを含まない場合

グレーで囲われた領域は初期点\(x_{3}\)を持ちますが、もとのゲームにおいてノード\(x_{3}\)の後に起こり得るノード\(z_{1},z_{2},z_{3},z_{4}\)がグレーの領域に含まれていないため、これは部分ゲームではありません。頂点がなければ利得も分からないため、グレーの領域を独立したゲームとして分析することはできません。

部分ゲーム\(\Gamma \left( x\right) \)の初期点\(x\)はもとのゲーム\(\Gamma \)において単独で情報集合\(\left\{ x\right\} \)を構成するため、プレイヤーが手番\(x\)へ到達したとき、彼はその直前に選択された行動を観察できていることになります。加えて、部分ゲーム\(\Gamma \left( x\right) \)のノード集合\(X^{x}\)には、もとのゲーム\(\Gamma \)において手番\(x\)の後に起こり得るノードだけが含まれます。したがって、部分ゲーム\(\Gamma \left( x\right) \)に直面したプレイヤーたちは、もとのゲーム\(\Gamma \)においてノード\(x\)の直前までに行われたすべての意思決定を観察できていることになります。

部分ゲーム\(\Gamma \left( x\right) \)の頂点集合\(Z^{x}\)に含まれる頂点はいずれももとのゲーム\(\Gamma \)の頂点でもあるため、部分ゲームが終了するときには、もとのゲームもまた終了します。また、部分ゲーム\(\Gamma \left( x\right) \)のそれぞれの頂点\(z\in Z^{x}\)においてそれぞれのプレイヤー\(i\)が得る利得\(u_{i}^{x}\left( z\right) \)は、もとのゲーム\(\Gamma \)においてその頂点\(z\)においてそのプレイヤー\(i\)が得る利得\(u_{i}\left( z\right) \)と一致します。したがって、もとのゲーム\(\Gamma \)の部分集合であるようなゲームの中でも単独でゲームとして分析可能であるようなものが部分ゲーム\(\Gamma \left( x\right) \)であると言えます。

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録