鞍点のない問題：混合戦略問題

$P,Q$の２人がじゃんけんをします。
負けたら10円を相手に払い,勝ったら相手から10円貰うというルールで, じゃんけんを繰り返します。
無論,「アイコ」の場合は,支払うお金,貰うお金とも0円です。

(賭博は法律で禁止されているから考えたくないという方は,これは,仮想の国でのお話しと思って頂くか,お金の替わりにゲーム用のメダルを考えてください。
「じゃんけんぽん,アイコでしょ…」というかけ言葉, 関東近辺でよく使われていますが,他の地域はどんなかけ言葉は？）

前節と同様に,$P$と$Q$の出す手によって,貰えるお金,支払うお金がどうなるか, $P$の立場で以下のように ＜利得表2＞に表しておきます。

＜利得表2＞

	$Gu$	$Choki$	$Pa$
$Gu$	0	-10	10
$Choki$	10	0	-10
$Pa$	-10	10	0

$$\begin{eqnarray*} &&Gu：グー\\ &&Choki：チョキ\\ &&Pa：パー \end{eqnarray*}$$

「-10」は$Q$に10円払う事を表します。

$P$の立場に立ってみます。先ず,このゲームの利得表には、前節で説明した鞍点がありません。双方が選択の余地のない「平衡状態」にする戦略はないわけです。出す手をランダムしてゲームを繰り返す方法以外ありません。このような問題を混合戦略問題といいます。
じゃんけんを繰り返すわけですが,どのような「戦略」があるでしょうか？

グーを出し続ける？ でも,$Q$はそれを直ぐ見破って, パーを出し続けてくるでしょう。続ければ続けるほど$P$は大損です。
同様にパーを出し続けるのも駄目,チョキを出し続けるのも駄目です。
結局,例えば,サイコロを用意して,出た目によって出す手を決めるランダムな手の繰り返す方法でしょう。
(1か6ならグー,2か5ならパー,3か4ならチョキなど)

問題は,どんな割合で（確率で）グー,チョキ,パーを出すべきかです。
相手の$Q$は$P$の出す手を監視しながら $P$と対戦しますので,$P$が選択したグー,チョキ,パーの確率を直ぐに見破り, それでも,自分にとって有利 な手を選択してくると考えるべきです。
$P$と$Q$の立場を替えても全く同じです。

ゲームの理論を創始し,この種の問題に解を与えたのが,ノイマン（ $von Nuemann$ 現在の計算機の原理開発者としても有名）です。

前節の鞍点のある問題と異なり,一工夫が必要です。それは,ゲームの利得 $G(P,Q)$の替わりに期待値$E(P,Q)$を使います。以下、その説明をします。

$P$が選択する戦略（グー,チョキ,パーを出す確率）を$p_1,p_2,p_3$とし, $P=(p_1,p_2,p_3)$で表しておきます。

このゲームの場合、「戦略」は幾つかある「手」をランダムに選んで繰り返す 確率の組み合わせになるわけです。

同様に$Q$が選択する戦略を $Q=(q_1,q_2,q_3)$で表しておきます。

$P$がグーを出し,$Q$もグーを出す確率は$p_1・q_1$でこのとき $P$は損得なし(0円の儲け),

$P$がグーを出し,$Q$がチョキを出す確率 は$p_1・q_2$でこのとき,$P$は10円の儲け,

$P$がグーを出し,$Q$がパーを出す確率は$p_1・q_3$でこのとき, $P$は10円の損失(-10の儲け),

という計算を全て行いますと

$$P=(p_1,p_2,p_3),Q=(q_1,q_2,q_3)$$

での$P$の儲けの期待値$E(P,Q)$は

$$\begin{eqnarray*} &&E(P,Q)=0・p_1・q_1+10・p_1・q_2+(-10)・p_1・q_3\\ &&+(‐10)... ...2+10・p_2・q_3 \\ &&+10・p_3・q_1+(‐10)・p_3・q_2+0・p_3・q_3 \end{eqnarray*}$$

です。

$$P=(p_1,p_2,p_3),Q=(q_1,q_2,q_3)$$

は それぞれ,グー,チョキ,パーを出す確率を表していますから, これらについての制約は

$$\begin{eqnarray*} &&1 \ge p_1 \ge 0,1 \ge p_2 \ge 0,1 \ge p_3 \ge 0, p_1+p_2+p_3... ...&&1 \ge q_1 \ge 0,1 \ge q_2 \ge 0,1 \ge q_3 \ge 0, q_1+q_2+q_3=1 \end{eqnarray*}$$

です。

簡単のため$P,Q$の採り得る集合を

$$\begin{eqnarray*} &&P_O= \{ (p_1,p_2,p_3)\vert 1 \ge p_1 \ge 0,1 \ge p_2 \ge 0,1... ...1 \ge q_1 \ge 0,1 \ge q_2 \ge 0,1 \ge q_3 \ge 0, q_1+q_2+q_3=1\} \end{eqnarray*}$$

で表しておきます。前節の$P_0,Q_0$と異なり,それぞれ,確率を要素にもつベクトルの 集合になっています。

$P=(p_1,p_2,p_3)$が$P_O$の中から選択されると$Q$はこれに対抗して $E(P,Q)$が最小になるように （自分の損失が最小になるように） $Q=(q_1,q_2,q_3)$を$Q_O$中で選択するはずです。
すなわち

$$\min \{ E(P,Q) \vert Q \in Q_O\}$$

が実現されるとなるような$Q$を$Q_O$の中で探します。
この最小値を

$$\min_Q E(P,Q)$$

で表しておきます。
$P$はこれを見越して,自分の利益が最大になるようにするため,

$$\max \{ \min_Q E(P,Q) \vert P \in P_O\}$$

が実現されるとなるような$P$を$P_O$の中から探すことになります。 この最大値を

$$\max_P \min_Q E(P,Q)$$

で表しておきます。

まっく逆のQの立場からは, $Q=(q_1,q_2,q_3)$が$Q_0$の中から選択されると$P$はこれに対抗して $E(P,Q)$が最大になるように $P=(p_1,p_2,p_3)$を$P_O$中で選択するはずです。
すなわち

$$\max \{ E(P,Q) \vert P \in P_O\}$$

が実現されるとなるような$P$を$P_O$の中から探します。この最小値を

$$\min_P E(P,Q)$$

で表しておきます。 $Q$はこれを見越して,自分の損失を最小にするため,

$$\min \{ \max_P E(P,Q) \vert Q \in Q_O\}$$

が実現されるとなるような$Q$を$Q_0$の中で探すことになります。この最大値を

$$\min_Q \max_P E(P,Q)$$

で表しておきます。

以上出てきた,２つの値には一般には

$$\max_P \min_Q E(P,Q) \le \min_Q \max_P E(P,Q)$$

という関係が成り立っています。
証明は前節の$G(P,Q)$の場合と全く同じなので 省略します。

ノイマンは上のような問題では,$P_O,Q_O$の中に

$$P^*=(p_1^*,p_2^*,p_3^*), Q^*=(q_1^*,q_2^*,q_3^*)$$

があって

$$\begin{eqnarray*} &&\max_P \min_Q E(P,Q) = \min_Q \max_P E(P,Q)=E(P^*,Q^*)\\ &&\max_P E(P,Q^*)=E(P^*,Q^*)= \min_Q E(P^*,Q) \end{eqnarray*}$$

となることを証明しました。
その証明についての話しは後の章ということにして, この$P^*$と$Q^*$を具体的求めることにします。

問題を解きやすくするため,最初に出てきた＜利得表＞ (損失と利益の表)の要素に全て10を加えて おきます。

＜利得表2＞

	$Gu$	$Choki$	$Pa$
$Gu$	10	0	20
$Choki$	20	10	0
$Pa$	0	20	10

$$\begin{eqnarray*} &&Gu：グー\\ &&Choki：チョキ\\ &&Pa：パー \end{eqnarray*}$$

これでは,一方的な$P$のゲームじゃないかと思われるかもしれませんが,

$$P^*=(p_1^*,p_2^*,p_3^*), Q^*=(q_1^*,q_2^*,q_3^*)$$

を計算するためだけにします。 このような,利得表の平行移動やっても解は同じです。

$P^*$も,$Q^*$も,$E(P^*,Q^*)$も未知な量ですが $E(P^*,Q^*)$は判っているもの として

$$\max_P E(P,Q^*)=E(P^*,Q^*)=\min_Q E(P^*,Q)$$

に注目します。

$$\begin{eqnarray*} &&E(P,Q)=q_1 \{ 10p_1+0p_2+20p_3\} \\ &&+q_2 \{ 20p_1+10p_2+0p_3\} +q_3 \{ 0p_1+20p_2+10p_3\} \end{eqnarray*}$$

で,

$$1 \ge q_1 \ge 0,1 \ge q_2 \ge 0,1 \ge q_3 \ge 0, q_1+q_2+q_3=1$$

ですので

$$\begin{eqnarray*} && E(P^*,Q^*) \le 10p_1+0p_2+20p_3~ (1)\\ && E(P^*,Q^*) \le 20p_1+10p_2+0p_3~ (2)\\ && E(P^*,Q^*) \le 0p_1+20p_2+10p_3~ (3) \end{eqnarray*}$$

という条件を満たせば,任意の$Q \in Q_O$について

$$E(P^*,Q^*) \le E(P,Q)$$

が成り立ちます。従って

$$E(P^*,Q^*) \le \min_Q E(P,Q)$$

が成り立ちます。
$(1)$〜$(3)$と$P \in P_O$即ち

$$1 \ge p_1,p_2,p_3 \ge 0, p_1+p_2+p_3=1$$

の制約条件下で

$$E(P,Q^*)=\max_P E(P,Q^*)$$

となる$P$ を求めれば,

$$E(P,Q^*)=E(P^*,Q^*)$$

となるわけです。 しかし,これではまだ$E(P^*,Q^*)$が未知量ですので,

$(1)$〜$(3)$の両辺を$E(P,Q^*)$で割り,

$$\begin{eqnarray*} &&r_1=p_1/E(P,Q^*)\\ &&r_2=p_2/E(P,Q^*)\\ &&r_3=p_3/E(P,Q^*) \end{eqnarray*}$$

として,

$$E(P^*,Q^*)/E(P,Q^*) \ge 1$$

に注意すると

$$\begin{eqnarray*} &&1 \le 10r_1＋0r_2＋20r_3~(1') \\ &&1 \le 20r_1＋10r_2＋0r_3~(2') \\ &&1 \le 0r_1＋20r_2＋10r_3~(3') \end{eqnarray*}$$

$$\begin{eqnarray*} &&r_1＋r_2＋r_3 \\ &&=(p_1＋p_2＋p_3)/E(P,Q^*)\\ &&=1/E(P,Q^*) \end{eqnarray*}$$

から

$$E(P,Q^*)のPについての最大化 \Leftrightarrow 「r_1+r_2+r_3の最小化」$$

結局,線形計画法の問題

$$\begin{eqnarray*} && 1 \le 10r_1+0r_2+20r_3(1') \\ && 1 \le 20r_1+10r_2+0r_3(2') \\ && 1 \le 0r_1+20r_2+10r_3(3') \end{eqnarray*}$$

かつ

$$r_1,r_2,r_3 \ge 0$$

の制約条件で

$$r_1+r_2+r_3$$

を最小化する。
という問題が出てきます。後は,先日から御紹介しているMicrosoft Excel のsolver などツールが利用できます。実際,この問題を解いてみて下さい。
その解から

$$\begin{eqnarray*} &&p_1^*=r_1/(r_1+r_2+r_3) \\ &&p_2^*=r_2/(r_1+r_2+r_3) \\ &&p_3^*=r_3/(r_1+r_2+r_3) \end{eqnarray*}$$

とすれば,$P^*$の最適戦略が求まります。

$P$と$Q$の役目を交換しても全く同じなので,$P^*=Q^*$です。 最初の＜利得表2＞を用いれば,$E(P^*,Q^*)$も求まります。