マックスミニとミニマックス

/金融・ゲーム理論

マックスミニ戦略

マックスミニ戦略とは、各プレイヤーが自分の取りうる各選択肢における自分の最小の利得(ミニ)の中で、最大(マックス)の利得を選択する戦略です。このときの利得をマックスミニ値と呼びます。

自分 $A$ の利得 $f_A$ を、自分の戦略 $a$ を、相手の戦略を $b$ とすると、マックスミニ戦略は以下のように表されます。

$$\max_a\min_bf_A(a,b)$$

マックスミニ戦略は、自分の最悪の場合の利得を、より大きくすることができます。このマックスミニ戦略は、主として次に述べる定和ゲーム(またはゼロ和ゲーム)で用いられます。

定和ゲームの場合

マックスミニ戦略を、定和ゲームでの純粋戦略の場合で説明します。定和ゲームとは、プレイヤの利得の合計が一定値になるゲームで、純粋戦略とは、各プレイヤが1つの戦略のみ選択できる場合を言います。

プレイヤが2人(プレイヤ $A$ とプレイヤ $B$ )、戦略が2つ(戦略 $X$ ,戦略 $Y$ )の場合で考えます。以下の利得表では、各プレイヤの戦略と利得の関係を表しています。

$A\backslash B$ $B:X$ $B:Y$
$A:X$ $A=6,B=4$ $A=5,B=5$
$A:Y$ $A=4,B=6$ $A=7,B=3$

プレイヤ $A$ が戦略 $X$ をとった場合の最低の利得は5( $B$ は戦略 $Y$ )になり、戦略 $Y$ をとった場合の最低の利得は4( $B$ は戦略 $X$ )になります。両者を比べるとより大きい利得は5になります。これより、プレイヤ $A$ のマックスミニ戦略は戦略 $X$ で、マックスミニ値は5となります。

一方、プレイヤ $B$ も同様に考えると、プレイヤ $B$ が戦略 $X$ をとった場合の最低の利得は4( $A$ は戦略 $X$ )になり、戦略 $Y$ をとった場合の最低の利得は3( $A$ は戦略 $Y$ )になります。これより、プレイヤ $B$ のマックスミニ戦略は戦略 $X$ で、マックスミニ値は4となります。

従って、両プレイヤのマックスミニ戦略の組は(戦略 $X$ 、戦略 $X$ )となります。しかし、この場合のマックスミニ戦略の組は、ナッシュ均衡(どのプレイヤーも戦略を変更して得をできない)となっていません。なぜなら、$A$ が戦略 $X$ をとった場合の $B$ の利得は、戦略 $X$ より戦略 $Y$ の方が大きいからです。

ミニマックス戦略

ミニマックス戦略とは、各プレイヤーが自分の取りうる各選択肢における相手の利得の最大(マックス)の中で、最小(ミニ)の利得を選択する戦略です。このときの自分の利得をミニマックス値と呼びます。

相手 $B$ の利得 $f_B$ を、自分の戦略を $a$ 、相手の戦略を $b$ とすると、ミニマックス戦略は以下のように表されます。

$$\min_a\max_bf_B(a,b)$$

ミニマックス戦略は、相手の利得の最小が自分の利得の最大となる定和ゲームで成り立つ戦略です。定和ゲームでのミニマックス戦略は、自分が取りうる各選択肢における最大の損失(マックス)の中で、最小の損失(ミニ)を選択する戦略と表現されます。

定和ゲームの場合

ミニマックス戦略を、定和ゲームでの純粋戦略の場合で説明します。

$A\backslash B$ $B:X$ $B:Y$
$A:X$ $A=6,B=4$ $A=5,B=5$
$A:Y$ $A=4,B=6$ $A=7,B=3$

この利得表では、プレイヤ $A$ が戦略 $X$ をとった場合の $B$ の最大の利得は5になり、戦略 $Y$ をとった場合の $B$ の最大の利得は6になります。両者を比べるとより小さい $B$ の利得は5になります。これより、プレイヤ $A$ のミニマックス戦略は戦略 $X$ で、ミニマックス値は5であると言うことができます。

一方、プレイヤ $B$ も同様に考えると、プレイヤ $B$ が戦略 $X$ をとった場合の $A$ の最大の利得は6になり、戦略 $Y$ をとった場合の $A$ の最大の利得は7になります。これより、プレイヤ $B$ のミニマックス戦略は戦略 $X$ で、ミニマックス値は4であると言うことができます。

$$\min_b\max_af_A(a,b)$$

ミニマックス定理

ミニマックス定理とは、プレイヤーが2人の定和ゲーム(またはゼロ和ゲーム)では、混合戦略を含めると、マックスミニ値とミニマックス値が一致することを示す定理です。但し、一般のゲームでは、マックスミニ戦略とミニマックス戦略は異なる概念です。

$$\max_a\min_bf_A(a,b)=\min_b\max_af_A(a,b)$$

ミニマックス定理は、ゲームにはこれ以上保証利得を増やせない値が存在することを示しています。その値をゲームの値(value of the game)と呼びます。尚、保証利得(security level)とは、相手がどのような行動をとっても、自分が少なくとも確保できる利得です。

じゃんけんの場合

じゃんけんをゼロ和ゲームの例に取ると、純粋戦略の場合のプレイヤーの利得表は以下になります。

$A\backslash B$ グー チョキ パー
グー -1
チョキ -1
パー -1

マックスミニ値の計算すると、どれを出しても各行の最小値は -1であるため、

$$\max(-1,-1,-1)=-1$$

ミニマックス値を計算すると、どれを出しても各列の最大値は 1であるため、

$$\min(1,1,1)=1$$

純粋戦略の場合は、マックスミニ値とミニマックス値は一致しません。一方、混合戦略まで含めて、グー/チョキ/バーを出す確率を全て 1/3 とすると、期待値は常に0になります。これがミニマックス定理です。

$$\max_a\min_bf_A(a,b)=\min_b\max_af_A(a,b)=0$$

 

数学
解析学、代数学、幾何学、統計学、論理学、基礎論、特殊関数、物理数学、情報理論、暗号理論、機械学習、金融理論、ゲーム理論、数値計算
散策路TOP
物理学、数学、力学、電磁気学、連続体力学、相対論、熱・統計力学、量子力学、解析学、代数学、幾何学、統計学、論理学、物性論、プラズマ物理、電子工学、情報・暗号、機械学習、金融・ゲーム理論、IT、FP、宗教・思想

 

タイトルとURLをコピーしました