意思決定とゲームの理論

1. １．確率的（既知）
2. ２．確率的（未知）
3. ３．ゲームの理論
   1. ３．１ 純粋戦略
   2. ３．２ 混合戦略

　　意思決定とは，将来の状態を予測し，最適な結果が得られるように，取るべき行動を決定することです．この際，将来における状態の性質や予測可能性によって，以下のようないくつかのタイプに分類できます．

1. 将来の状態が確定的である場合　　通常の最適化問題となりますので，ここでは扱いません．

2. 将来の状態が確率的で，かつ，その分布が既知である場合　　第 1 節で扱います

3. 将来の状態が確率的で，かつ，その分布が未知である場合　　第 2 節で扱います

4. 将来の状態が競争相手によって決まり，競争相手の行動を予測できない場合　　このタイプの問題としてゲームの理論があります．第 3 節で扱います．

１．確率的（既知）

　　どのような行動を取ったら，どのような結果になるかを，将来の状態毎に表した以下に示すような表を利得表と呼びます．この表において，r_ij は，行動 i を取ったとき，将来の状態が j である場合に得られる利得を表しています．

	状態 A	状態 B	状態 C
行動 a	raA	raB	raC
行動 b	rbA	rbB	rbC
行動 c	rcA	rcB	rcC
行動 d	rdA	rdB	rdC

　　今，利得表が以下のようであったとします．

表1　利得表の例

	状態 A	状態 B	状態 C	状態 D
行動 a	8	3	4	7
行動 b	3	5	3	2
行動 c	8	5	2	0
行動 d	9	3	2	1
行動 e	0	10	0	1

また，各状態となる確率は，以下のようであるとします．

	状態 A	状態 B	状態 C	状態 D
確率	0.2	0.5	0.2	0.1

このとき，以下のような方法で，取るべき行動を決定します．

1. 期待値基準
   　　各行動に対し，獲得可能な利得の期待値を計算し，その最大のものを選択します．表1 の場合に対する期待値は，

   行動	利得の期待値
   行動 a	8 * 0.2 + 3 * 0.5 + 4 * 0.2 + 7 * 0.1 = 4.6
   行動 b	3 * 0.2 + 5 * 0.5 + 3 * 0.2 + 2 * 0.1 = 3.9
   行動 c	8 * 0.2 + 5 * 0.5 + 2 * 0.2 + 0 * 0.1 = 4.5
   行動 d	9 * 0.2 + 3 * 0.5 + 2 * 0.2 + 1 * 0.1 = 3.8
   行動 e	0 * 0.2 + 10 * 0.5 + 0 * 0.2 + 1 * 0.1 = 5.1

   となりますので，行動 e を選択することになります．

2. 満足度基準
   　　満足度を，ある行動をとったとき S 以上の利得を得られる確率，つまり，

   満足度 = Σ_状態 P(利得 ≧ S)

   と定義し，満足度を最大にするような行動を選びます．例えば，表1 の場合，S = 5 としたとき，各行動に対する満足度は，

   行動 a ： 満足度 = 0.2 + 0.1 = 0.3
   行動 b ： 満足度 = 0.5
   行動 c ： 満足度 = 0.2 * 0.5 = 0.7
   行動 d ： 満足度 = 0.2
   行動 e ： 満足度 = 0.5

   となりますので，行動 c を選択することになります．

２．確率的（未知）

　　将来の状態に対する確率分布が未知の場合，以下に示すような方法があります．

1. ラプラス基準
   　　すべての状態が同じ確率で実現するとみて，期待値を計算し，その最大のものを選びます．表1 の場合に対する期待値は，

   行動	利得の期待値
   行動 a	(8 + 3 + 4 + 7) / 4 = 5.5
   行動 b	(3 + 5 + 3 + 2) / 4 = 3.25
   行動 c	(8 + 5 + 2 + 0) / 4 = 3.75
   行動 d	(9 + 3 + 2 + 1) / 4 = 3.75
   行動 e	(0 + 10 + 0 + 1) / 4 = 2.75

   となりますので，行動 a を選択することになります．

2. ミニ・マックス基準（マックス・ミニ基準）
   　　結果が費用の場合は，起こりうる最大の損失を最小にするような，また，結果が利得の場合は，起こりうる最小の利得を最大にするような行動を選択します．表1 の場合，各行動に対する最小の利得は，

   a : 3, 　b : 2, 　c : 0, 　d : 1, 　e : 0

   となりますので，行動 a を選択することになります．

3. マックス・マックス基準（ミニ・ミニ基準）
   　　常に最良の状態が実現すると信じて行動を決定する方法です．結果が費用の場合は，起こりうる最小の損失を最小にするような，また，結果が利得の場合は，起こりうる最大の利得を最大にするような行動を選択します．表1 の場合，各行動に対する最大の利得は，

   a : 8, 　b : 5, 　c : 8, 　d : 9, 　e : 10

   となりますので，行動 e を選択することになります．

4. ハーウィツ基準
   　　ミニ・マックス（マックス・ミニ）基準とマックス・マックス（ミニ・ミニ）基準の折衷案です．2 つの方法の重み付き平均値を最大にするような行動を選択します．表1 の場合，ミニ・マックス（マックス・ミニ）基準に対する重みを 0.7 とすると，

   行動	ミニ・マックス基準	マックス・マックス基準	重み付き平均
   行動 a	3	8	3 * 0.7 + 8 * 0.3 = 4.5
   行動 b	2	5	2 * 0.7 + 5 * 0.3 = 2.9
   行動 c	0	8	0 * 0.7 + 8 * 0.3 = 2.4
   行動 d	1	9	1 * 0.7 + 9 * 0.3 = 3.4
   行動 e	0	10	0 * 0.7 + 10 * 0.3 = 3.0

   となりますので，行動 a を選択することになります．

5. サーベジュのミニ・マックス落胆基準
   　　落胆を，各状態から得られる最良の結果と実現した結果との差として定義します．結果が費用の場合は，各状態に対する費用から同じ状態の最小の費用を引いたものに，また，結果が利得の場合は，ある状態の最大の利得から同じ状態に対する利得を引いたものになります．起こりうる最大の落胆を最小にするような行動を選択します．誤った行動を選択したときの責任が重要である場合に用いられます．表1 の場合，各行動に対する落胆は，

   	状態 A	状態 B	状態 C	状態 D	落胆の最大値
   行動 a	9 - 8 = 1	10 - 3 = 7	4 - 4 = 0	7 - 7 = 0	7
   行動 b	9 - 3 = 6	10 - 5 = 5	4 - 3 = 1	7 - 2 = 5	6
   行動 c	9 - 8 = 1	10 - 5 = 5	4 - 2 = 2	7 - 0 = 7	7
   行動 d	9 - 9 = 0	10 - 3 = 7	4 - 2 = 2	7 - 1 = 6	7
   行動 e	9 - 0 = 9	10 - 10 = 0	4 - 0 = 4	7 - 1 = 6	9

   となりますので，行動 b を選択することになります．

３．ゲームの理論

　　ここでは，最も単純なモデルであるゼロ和 2 人ゲームについて説明します．ゼロ和 2 人ゲームとは，2 人で行い，利得の合計が常に 0 になる（プレーヤーⅠが払った金額とプレーヤーⅡが得た金額が等しくなる）ようなゲームです．

３．１ 純粋戦略

　　プレーヤーⅠが手 i (i = 1, 2, ･･･, m)，プレーヤーⅡが手 j (j = 1, 2, ･･･, n) を選択したとき，プレーヤーⅡは，プレーヤーⅠに金額 c_ij を支払うものとします．この関係を表にしたものを，ゲームにおける利得表と呼びます．

　　各プレーヤーが，確率 1 で各手を選択する（相手の手によって，取るべき手が確定的に決まる）場合，各プレーヤーは純粋戦略を使用していると言います．

　　また，各プレーヤは，ミニ・マックス戦略を使用するものとします．ミニ・マックス戦略とは，以下のような戦略です．各プレーヤーは，自分にとって最前の手を取るものとします．例えば，プレーヤーⅠが手 i を取ると，プレーヤーⅡは，失うべき金額を最小にするような手を打つはずです．したがって，プレーヤーⅠが手 i を取った場合，プレーヤーⅠが得る金額は，

min_j c_ij

となるはずです．そこで，プレーヤーⅠは，上記の値を最大にする，つまり，

v_Ⅰ = max_i min_j c_ij

となるような手を選択することになります．同様に，プレーヤーⅡは，以下に示す利得を得るような手を選択することになります．

v_Ⅱ = min_j max_i c_ij

　　一般に，

v_Ⅰ ≦ v_Ⅱ

という関係が成立します．特に，

v^* = v_Ⅰ = v_Ⅱ

ならば，ゲームは安定的であるといい，このときの戦略を最適純粋戦略と呼びます．また，v^* を，ゲームの値と呼びます．

　　ここで，例を一つ考えてみます．利得表は，以下の通りであるとします．

Ⅰ＼Ⅱ	１	２	３	mini
１	4	2	5	2
２	5	4	6	4
３	6	3	3	3
maxj	6	4	6

このとき，各プレーヤの利得は以下のようになります．

v_Ⅰ = max_i min_j c_ij = max_i {2, 4, 3} = 4

v_Ⅱ = min_j max_i c_ij = min_j {6, 4, 6} = 4

このゲームは安定的であり，ゲームの値は 4，各プレーヤーの最適戦略は，いずれも，i = j = 2 となります．

３．２ 混合戦略

　　各プレーヤーが，各手を，確率 1 ではなく，ある確率に従って選択するものとします．今，

x_i： プレーヤーⅠが戦略 i を選ぶ確率　　i = 1, 2, ･･･, m

y_j： プレーヤーⅡが戦略 j を選ぶ確率　　j = 1, 2, ･･･, n

　　　　　ただし，Σx_i = Σy_j = 1

としたとき，x = (x₁, x₂, ･･･, x_m) と y = (y₁, y₂, ･･･, y_n）をプレーヤーⅠ及びⅡの混合戦略と呼びます．

　　プレーヤーⅠが混合戦略 x を，プレーヤーⅡが混合戦略 y をとったとき，プレーヤーⅠが得る期待金額を，

c(x,y) = ΣΣc_ijx_iy_j

と定義すると，純粋戦略の場合と同様，ミニ・マックス戦略を採用した場合，各プレーヤの期待利得は以下のようになります．

v_Ⅰ = max_x min_y c(x,y)

v_Ⅱ = min_y max_x c(x,y)

　　このとき，以下の定理が成立します．

［ミニ・マックス定理］　どんなゲームに対しても

c(x^*,y^*) = v_Ⅰ = v_Ⅱ = v^*

となるような最適な混合戦略 x^* と y^* が存在する．

　　最適な混合戦略は，一般に，線形計画法を利用して求めることができますが，詳細については省略します．