展開形ゲームの定義 定義 (展開形ゲーム extensive form) プレイヤーの手番の系列を樹形図として表現するゲームの表現形式を展開形ゲームという． 展開形ゲームは、ゲームの木 $K$、プレイヤー分割 $P$、偶然手番の確率分布 $p$、情報構造 $U$、利得関数 $h$ で表される. $$\Gamma = (K,P,p,U,h)$$ (7.1) 定義 (自然 nature) プレイヤーの意思決定とは独立した偶然機構のことを自然(nature)という． また、自然が選択する手番を偶然手番(chance move)という． 定義 (ゲームの木 game tree) プレイヤー1と2がそれぞれ2つの選択肢を持っているゲームにおいて、それぞれのとりうる行動と結果との関係を次のように表現したものをゲームの木という． <center> <img src="http://www.digistats.net/math/image/2010_09_05.gif"> </center> ゲームの木は初期点0を持つ有限な有向木であり、点(order)と枝(edge)によって構成される． 定義 (プレイヤー分割 player partition) 各手番(行動の選択)において、選択できるのは1人のプレイヤーだけである． 従って、手番(行動の選択)の集合は、各プレイヤーの手番の集合 $P_{j}$ に分割される．これをプレイヤー分割という． ここで、$P_{0}$ を自然(偶然機構)が選択肢を決める手番の集合とし偶然手番とよぶ． このとき、 $X = P_{0} \cup P_{1} \cup P_{2} \cdots P_{n}$ 任意の2つの $P_{i},P_{j} (i \neq j)$ に対して $P_{i} \cap P_{j} = \emptyset$ $P_{i} \ne \emptyset ,i=1,\cdots,n$ が成り立つ． 定義 (情報分割 information partion) プレイヤー分割 $$P = [P_{0},P_{1},\cdots,P_{n}]$$ (7.2) に対して、 $$P_{i}=\bigcup_{u \in U_{i}} u$$ $U_{i}$ の任意の異なる2つの集合 $u$ と $v$ に対して $u \cap v = \emptyset$ を満たす集合族 $u$ 、すなわち、集合 $P_{i}$ の部分集合族 $u$ の族である $U_{i}$ をプレイヤー $i$ の情報分割という． 定義 (情報集合 information set) 情報分割 $U_{i}(i=0,\cdots,n)$ に属する集合をプレイヤー $i$ の情報集合という． 情報集合 $u$ とは、プレイヤーが選択肢を決定する際に得ることの出来る情報を意味している． プレイヤーの情報集合 $u$ は以下の意味を持つ． ゲームのプレイによって $u$ 内の手番 $x$ に到達したとき、プレイヤーは情報集合 $u$ 内のある手番が到達されたことを知る． ゲームのプレイによって $u$ 内の手番 $x$ に到達したとき、情報集合 $u$ 内のどの手番が実際に到達されたかを知ることが出来ない． 情報集合 $u$ は同じプレイと2回以上交わってはならない． 情報集合 $u$ に含まれる全ての手番は同じ枝を持つ． 定義 (偶然手番の確率分布族) ゲームにおける偶然手番 $x \in P_{0}$ における 各選択肢 $e$ および、各選択肢の集合 $e \in A(x)$ に付与される確率を $p_{x}(e)$ とするとき、$x$ における選択肢の集合 $e \in A(x)$ の確率分布は $$\sum_{e \in A(x)} p_{x}(e)=1 , 0 \leq p_{x}(e) \leq 1$$ (7.3) を満たす． 定義 (利得関数 payoff function) ゲームの木 $K$ の各頂点 $w \in W$ に対する利得ベクトル $$h(w) = (h_{1}(w),\cdots,h_{n}(w))$$ (7.4) を対応させたものを利得関数とする．